2010-06-10

PostScript版色相環

PostScript

sethsbcolorというそのものずばりのオペレータがあったので確認用にPostScript版も書いてみた。
やっぱり黄色や紫のところにはうっすらと線が見える気がする。

%!PS-Adobe-3.0
1 1 256 {
  /r exch def
  0 1 360 {
    /th exch def
    th 360 div r 256 div 1 sethsbcolor
    297 421 r th th 1 add arc stroke
  } for
} for
showpage

括弧が要らないのが逆ポーランド記法の特徴だけど、
(th 360 div) (r 256 div) 1 sethsbcolor
みたいな感じで意味的なまとまりを表現する括弧はほしい気もする。

sethsbcolor

PostScriptではsethsbcolorでHSBの色指定が出来る
S,BだけでなくHも0〜1.0で指定する。(0〜360ではない)

h s b sethsbcolor
h.. hue (色相) 0=赤, 1/3=緑, 2/3=青, 0〜1.0 の値)
s.. saturation (飽和度) 0=白, 1=純色
b.. brightness (明るさ) 0=暗い, 1=明るい
色の例 (h,s,b)=(0,1,1) 赤
(h,s,b)=(any,0,1) 白
(h,s,b)=(0.17,0.5,1) レモンイエロー
違う色を何色か用意したいときに、色相を適当に(for 等で)変えると楽です。
r g b setrgbcolor
r .. 赤の濃さ ( 0 =< r =< 1.0 )
g .. 緑の濃さ ( 0 =< g =< 1.0 )
b .. 青の濃さ ( 0 =< b =< 1.0 )
http://www.kwasan.kyoto-u.ac.jp/~tonooka/Howto/PS_nyumon.txt

2010-06-08

canvasで色相環

JavaScript

canvasを使って色相環を描いてみた
http://kar.s206.xrea.com/js/colors.html
色の変化のさせかたを自分で考えるのが目的だったのでグラデーションの技は使わず１ピクセルずつ処理してる。
なのでかなり重い処理になってるので注意。
RGB各色が0〜255の256階調なので、半径256ドット、60度(π/3ラジアン)を256分割にした。
関数psetsの引数でrのみの指定がメインとなる色、r*th/255が徐々に混じる色、0が使わない色。
関数nの255-rを生かすと中央が白から始まる円、0(=255-255)にすると中央が黒から始まる円になる。

<html>
<head>
<title>Colors</title>
<script>
window.onload = function(){
  c = document.getElementsByTagName('canvas')[0].getContext('2d');
  for(r=0;r<256;r++) for(th=0;th<256;th+=255/r){
    psets(r,    -th,       r,       0,r*th/255);
    psets(r,     th,       r,r*th/255,      0);
    psets(r, 512-th,r*th/255,       r,      0);
    psets(r, 512+th,       0,       r,r*th/255);
    psets(r,1024-th,       0,r*th/255,      r);
    psets(r,1024+th,r*th/255,       0,      r);
  }
}
function psets(r,th,rr,gg,bb){
  x = 255.5 + r * Math.cos(th * Math.PI / 768); // 256 * 3 = 768
  y = 255.5 - r * Math.sin(th * Math.PI / 768);
  c.strokeStyle = "rgb("+n(rr,r)+","+n(gg,r)+","+n(bb,r)+")";
  c.strokeRect(x,y,1,1);
  c.strokeStyle = "rgb("+n(rr,255)+","+n(gg,255)+","+n(bb,255)+")";
  c.strokeRect(1024-x,y,1,1);
}
function n(cc,r){return Math.round(cc) + 255-r}
</script>
</head>
<body><canvas width=1024 height=512></canvas></body>
</html>

縦横１ピクセルのstrokeRectで点を描いてるつもりなんだけどなぜか１ピクセル以上の幅になってしまう。
→与える座標を0.5ずらしたら解決した。なんて律儀なモデルなんだ。

線の太さが 1.0 で (3,1) から (3,5) までのパスを考えた場合、中央の図のようになります。実際に塗りつぶされる領域 (暗い青色) は中間からパスの両側のピクセルまで広がり、考えていたパスに近いものが描画されます。つまり、これらのピクセルのみが部分的に薄くされ、領域全体 (明るい青色と暗い青色) の半分が、実際に描く色として暗く塗りつぶされます。これが先のコード例の 1.0 幅の線で起こったことです。
これを修正するには、とても正確にパスを作成しなければなりません。知ってのとおり、1.0 幅の線は線幅を単位の半分からパスの両側まで広げます。右端の図は、(3.5,1) から (3.5,5) までのパスを作成した場合の結果です。最終的に 1.0 幅の線は完成し、単一ピクセルの垂直線を正確に塗りつぶすことができました。
https://developer.mozilla.org/ja/Canvas_tutorial/Applying_styles_and_colors

黄色や紫のところにうっすらと線が見えるのも気になる。境界処理をミスってるのだろうか…。

2010-05-24

ポイントフリー

Haskell

一つの値を名前に束縛せずに複数箇所で使うってどうやるんだ。Sコンビネータ的なものが用意されてる？
cube = (((*).((*)<*>id))<*>id) -- \x -> x * x * x
fib = (flip(if'.(< 2))1)<*>((+).fib.(-1 +)<*>fib.(-2 +))
http://d.hatena.ne.jp/nishiohirokazu/20100520/1274364170

言われてみれば cube とか fib って Sコンビネータにぴったりのいい例題だ。
というわけで自分もやってみた。
上記の cube は、(x * x) * x としているが、以下は x * (x * x) としたバージョン
上記の fib は、if x<2 then 1 ...としているが、以下は if x<2 then x ...としたバージョン

import Control.Applicative
cube = (*) <*> ((*) <*> id)
if' b x y = if b then x else y
fib = if'.(<2) <*> id <*> ((+).fib.(-1 +) <*> fib.(-2 +))

2010-05-20

コンビネータ一覧表

コンビネータ

この間Gaucheで作ったラムダ式からの変換プログラム(とその後の調査)からわかったことを表にまとめてみた。

name	in	out	memo
I	x	x	S K _ , W K , C K _ , R _ K
M	x	x x	O I , W I , W T
Y	x	x (Y x)	M2 L , U U , M2 (B M2 B)
i	x	x S K	V S K , S (O (K S)) (K K)
K	x y	x	K
KI	x y	y	K I , S K
T	x y	y x	C I , S (K O) K
W	x y	x y y	S1 I , S S (K I) , S T , C W1
W1	x y	y x x	C W , W V , M2 R , H R
W2	x y	x y x	W C , S S K
L	x y	x (y y)	Q M , W* B , R M B
O	x y	y (x y)	S I , Q Q W
U	x y	y (x x y)	B O M , L O
M2	x y	x y (x y)	W S , B M , S S I
C	x y z	x z y	S (D S) (K K) , C R , R R R
R	x y z	y z x	D T , C C , J T
V	x y z	z x y	C* T , C F
F	x y z	z y x	C V , C* R
B	x y z	x (y z)	S (K S) K , C Q , C* Q1
Q	x y z	y (x z)	C B , R B R
Q1	x y z	x (z y)	C* B , C Q2 , J I
Q2	x y z	y (z x)	B Q T , C Q1 , R* B
Q3	x y z	z (x y)	B T , C Q4 , V* B , G I
Q4	x y z	z (y x)	C Q3 , F* B
S	x y z	x z (y z)	W** G
S1	x y z	y z (x z)	C S
H	w x y	w x y x	S R , W* C*
W*	w x y	w x y y	B W
C*	w x y z	w x z y	B C , C* R*
R*	w x y z	w y z x	C* C*
V*	w x y z	w z x y	C** C , C* F*
F*	w x y z	w z y x	C* V* , C** R*
D	w x y z	w x (y z)	B B
B1	w x y z	w (x y z)	D B
B3	w x y z	w (x (y z))	D1 B
G	w x y z	w z (x y)	D C
G2	w x y z	w z (w z) (x y)	G1 M2
J	w x y z	w x (w z y)	S (C* E) C
Φ	w x y z	w (x z) (y z)	B (B S) B
Ψ	w x y z	w (x y) (x z)	H* D2 , Γ (K K)
H*	v w x y	v w x y x	B H , W C
W**	v w x y	v w x y y	B W*
C**	v w x y z	v w x z y	B C* , C R
R**	v w x y z	v w y z x	B R* , C C
V**	v w x y z	v w z x y	B V* , C F
F**	v w x y z	v w z y x	B F* , C V
D1	v w x y z	v w x (y z)	B D
E	v w x y z	v w (x y z)	B B1 , D1 D
B2	v w x y z	v (w x y z)	D B1 , E B
D2	v w x y z	v (w x) (y z)	D D , D3 B
G1	v w x y z	v w z (x y)	B G
Γ	v w x y z	w (x y) (v w x y z)	Φ (Φ (Φ B)) B
D3	u v w x y z	u v w x (y z)	B D1
E^	t u v w x y z	t (u v w) (x y z)	E E

出力の並び順

	x y z	x (y z)	w x y z	v w x y z
x y z	I = C T	B = C Q	I	B I
y x z	T = C I	Q = C B	C	C* = B C
x z y	C = C R	Q1 = C Q2 = C* B = B C B	C* = B C	C** = B C* = C R
y z x	R = C C = B B T	Q2 = C Q1 = R* B = B Q T	R* = C* C*	R** = B R* = C C
z x y	V = C F = B C T	Q3 = C Q4 = V* B = B T	V* = C* F*	V** = B V* = C F
z y x	F = C V	Q4 = C Q3 = F* B = B Q3 T	F* = C* V*	F** = B F* = C V
x x y	M = W I = W T	W B	W	W* = B W
y y x	M1 = C M	M1* B = B O T	M1* = C* W	B M1*
x y y	W = C W1 = S T	L = Q M = W* B	W* = B W	W** = B W*
y x x	W1 = C W = W V	C L = Q3 M = W1* B	W1* = W* V*	W V
x y x	W2 = W C	C O = H B	H = W* C*	H* = B H* = W C
y x y	W3 = W* T	O = W3* B	W3* = W** C	B W3*

W2,W3,D3は勝手に名前をつけただけ。正式な名前は不明。
本当はW2のところがHになるべきだったんじゃないかという気がする。

2010-05-13

ラムダ式からの変換

コンビネータ

Schemeのラムダ式に対応するコンビネータ表記を求めるプログラムを作った。

使い方

lambdaをlambdaccにして、通常のlambdaと同じように引数と本体を与える。

gosh> (lambdacc (x y z) (x (y z)))
B
gosh> (lambdacc (x y) (x (y y)))
(C B M)

ソースコード

(use util.match)

(define-syntax lambdacc (syntax-rules ()
  ((_ var body ...) (uncurry (lcc 'var (curry '(body ...)))))))

(define lcc (match-lambda*
  ((() x) x)
  (((v . vs) x) (lcc v (lcc vs x)))
  ((v (x y)) (match `(,(in? v x) ,(in? v y))
    ((#f   #f)       `( K (,x ,y)))
    ((#f  'eq)          x)
    (('eq  #f)       `( T ,y))
    (('eq 'eq)         'M)
    (('eq (not #f))  `( O ,(lcc v y)))
    (((not #f) 'eq)  `( W ,(lcc v x)))
    ((#f    _)       `((B ,x)         ,(lcc v y)))
    ((_    #f)       `((C ,(lcc v x)) ,y))
    ( _              `((S ,(lcc v x)) ,(lcc v y)))))
  ((v x) (if (eq? v x) 'I `(K ,x)))))

(define in? (match-lambda*
  ((v (x y)) (if (or (in? v x) (in? v y)) 'in #f))
  ((v  x)    (if     (eq? v x)            'eq #f))))

(define (curry l)
  (if (pair? l) (currys (reverse l)) l))
(define currys (match-lambda
  ((x)                      (curry x))
  ((x . xs) `(,(currys xs) ,(curry x)))))

(define (uncurry l)
  (if (pair? l) (uncurrys l) l))
(define uncurrys (match-lambda
  ((xs x) `(,@(uncurrys xs) ,(uncurry x)))
  (    x  `(                ,(uncurry x)))))

バリエーション

なるべく後のパターンほど広くマッチするようにしたので、不要なパターンを削ればそれなりの動作をする。
例えば以下はSKIコンビネータのみの表記を求めるバージョン。

(define lcc (match-lambda*
  ((() x) x)
  (((v . vs) x) (lcc v (lcc vs x)))
  ((v (x y)) (match `(,(in? v x) ,(in? v y))
    ((#f   #f)       `( K (,x ,y)))
    ((#f  'eq)          x)
   ;(('eq  #f)       `( T ,y))
   ;(('eq 'eq)         'M)
   ;(('eq (not #f))  `( O ,(lcc v y)))
   ;(((not #f) 'eq)  `( W ,(lcc v x)))
   ;((#f    _)       `((B ,x)         ,(lcc v y)))
   ;((_    #f)       `((C ,(lcc v x)) ,y))
    ( _              `((S ,(lcc v x)) ,(lcc v y)))))
  ((v x) (if (eq? v x) 'I `(K ,x)))))

実行結果

gosh> (lambdacc (x y z) (x (y z)))
(S (K S) K)
gosh> (lambdacc (x y) (x (y y)))
(S (S (K S) K) (K (S I I)))

対応表

	v	y	yv
v	Mv	Tyv	Oyv
x	xv	K(xy)v	Bxyv
xv	Wxv	Cxyv	Sxyv

2010-05-12

ポリモルフィズムのレベル

プログラミング言語

ポリモルフィズムなし	→普通の関数	例：C言語等
１つの引数(self)の型に応じてポリモルフィズム	→普通のオブジェクト指向のメソッド	例：Smalltalk等
全ての引数の型に応じてポリモルフィズム	→ジェネリックファンクション	例：CLOS等
さらに戻り値の型にも応じてポリモルフィズム	→いまここ	例：Scala等

って感じ？

Island Life - 静的型がうらやましいとき
「戻り値の型によって多相化できる」っていうのは静的型の強力なところ
http://blog.practical-scheme.net/shiro/20100508a-static-or-dynamic

Togetter - まとめ「型付けについてのまつもとさんとみずしまさんのやりとり」
RubyのmapがHashを返せたとして、{}.map{|e| e[0]} と {}.map{|e| [e[1],e[0]} だとどうなります？Procを実際に適用してみることができないので、とりあえずArray返すくらいしか選択肢ないですよね。
引数として渡される関数(Rubyだとブロック)の型情報に基づいて、どの種類のコレクション(RubyならArrayかMapか)を返すか、を変えたい、ということです。
http://togetter.com/li/19536

JavaやRubyを2番目の例に入れようと思ったけど、なんか拡張機能があるらしいのでやめておいた。

多重ディスパッチ - Wikipedia
一般的なオブジェクト指向言語での単一ディスパッチでは、メソッド呼び出し（Smalltalkなら「メッセージ送信」、C++なら「メンバ関数呼び出し」）を行ったとき、その引数の1つが特別に扱われ、呼び出すべきメソッドの特定に使われる。多くの言語では、この特別な引数は構文上も特別な指定をされる。例えば、その特別な引数を最初に記して、その後にドットを挟んで呼び出すべきメソッドの名前を記述する（例えば special.meth(other,args,here)）。
多重ディスパッチを採用する言語では、全ての引数がメソッド選択という観点では平等に扱われる。第一引数、第二引数、第三引数とマッチングを行うが、どれか特定の引数がその関数やメソッドを「所有」しているわけではない。
初期の多重ディスパッチを採用した例として Common Lisp Object System がある。
何らかの拡張でマルチメソッドをサポートする言語として、次のものがある。
* Scheme (TinyCLOS)
* Python (gnosis.magic.multimethods)
* Perl (Class:Multimethods)
* Java (MultiJava)
* Ruby (The Multiple Dispatch Library, Multimethod Package)
http://ja.wikipedia.org/wiki/%E5%A4%9A%E9%87%8D%E3%83%87%E3%82%A3%E3%82%B9%E3%83%91%E3%83%83%E3%83%81

2010-04-30

各コンビネータに対応する関数

Haskell

type	Combinator	Prelude	Monad	Applicative
a -> a	I x = x	id	ask
a -> b -> a	K x y = x	const	return	pure
(a -> b) -> (c -> a) -> c -> b	B x y z = x (y z)	(.)	liftM
(a -> b -> c) -> b -> a -> c	C x y z = x z y	flip
(a -> a) -> a	Y x = x (Y x)	fix
(a -> b -> c) -> (a -> b) -> a -> c	S x y z = x z (y z)	??	ap	<*>

Sコンビネータの型は(a -> b -> c) -> (a -> b) -> a -> c
これで調べると、Readerモナドのap、Applicativeの<*>等が対応するようだ。

あまり深く考えずに Reader a を a -> と読み替えると、関数の型は以下のようになります。

関数型等価な関数

ap (a->b->c) -> (a->b) -> a -> c <*>

つまり Reader モナドは引数隠蔽モナドだと思えばいいわけですね。本当は第一引数があるのだけれども、あたかもそれが引数に存在しないかのように記述できると。
http://d.hatena.ne.jp/rst76/20091006/1254835633

*1 -> (a -> b) -> (a -> c)
というわけで，これが S コンビネータ
あと、Monad のインスタンスである(Reader r)に対応する(>>=)が CSかも。
http://practical-scheme.net/chaton/haskell-ja/a/2009/11/02

Applicativeについて

どうやらMonadやArrowのようなフレームワーク(?)の一種らしい

Applicativeの使い方が少し見えてきました。
mapでこうやることが：
map (+ 1) [1, 2, 3] = [2, 3, 4]
Applicativeだとこうできる：
pure (+1) <*> [1, 2, 3] = [2, 3, 4]
いくつのリストを対象に関数を適用するかで、map = 1, zipWith = 2, zipWith3 = 3,...と使う関数を変えていかなくてはならないのですが、Applicativeであれば、pureと<*>だけで何個リストがあっても大丈夫...これはきれいです。
http://d.hatena.ne.jp/Otter_O/20080301/1204363038

そもそも、PreludeとControl.MonadとControl.ArrowとControl.Applicativeはそれぞれ導入の時期もずれていて、十分に整理されているわけではありません。
http://practical-scheme.net/chaton/haskell-ja/a/2009/10/30

追記
次のエントリーに求めていたものズバリがあった。

Sコンビネータいろいろ
モナドとコンビネータ論理のコラボ！とか喜んでたら、既に先達が。
http://d.hatena.ne.jp/rst76/20091006/1254840491

PreludeにSかWを入れる提案があったが却下されてたらしい。

Joe Fasel argued for the inclusion of S or W in the prelude
on the grounds that a complete combinator base would be "neat".
But the majority of the Haskell committee didn't buy that.
http://www.haskell.org/pipermail/haskell-cafe/2005-February/009117.html

*1:->) a) がApplicativeクラスのインスタンスなので，この場合メソッド<*>の型は <*> :: ((->) a (b -> c) -> ((->) a b) -> ((->) a c) すなわち <*> :: (a -> (b -> c

関数	型	等価な関数
ap	(a->b->c) -> (a->b) -> a -> c	<*>