Ackermann関数
再帰呼出しというとすぐに出てくるのがAckermann関数である.(define (a x y) (cond ((= x 0) (+ y 1)) ((= y 0) (a (- x 1) 1)) (else (a (- x 1) (a x (- y 1))))))SICPの定義は少し違う. (演習問題1.10)
(define (a x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (a (- x 1) (a x (- y 1))))))SICPの著者のSussman君はもちろんこの方が正しいというが, ここでは巷間に伝わる前の定義に従う.
$def,a,<$~1, $def,~1,<$>~2<, $def,>~2<,<$a,$1-,>>~1<<;, $a,>>~1<<,$1-,>>~2<<;;;>;, $def,0,<$a,$1-,>>~1<<;,1;>;;>;, $def,0,<$1+,>~2<;>;;>; $a,0,0;,$a,0,1;,$a,0,2;,$a,0,3;, => 1,2,3,4, $a,1,0;,$a,1,1;,$a,1,2;,$a,1,3;, => 2,3,4,5, $a,2,0;,$a,2,1;,$a,2,2;,$a,2,3;, => 3,5,7,9, $a,3,0; => 51桁の世界ではこの辺までしか計算できないから, あっという間に終るのは有難い. 特にコメントすることもあるまい.
Catalan三角形
TAOCPの式7.2.1.6-(22)にCatalan数とかCatalan三角形というのがある. このブログに「入れ子のかっこ」という話を書いたが, 4組の(,)の並べ方が14通りあり, それがCatalan数Cを使いC(4)=14と表現出来るという話題だ. 三角形の方はのような形で, Catalan数Cnは図のCnnである.
C00=1,
Cp,q=Cp(q-1)+C(p-1)q 0≤p≤q≠0の時
=0 p<0 または p>qの時
だからSchemeでは
(define (c p q) (cond ((and (= p 0) (= q 0)) 1) ((or (< p 0) (> p q)) 0) (else (+ (c p (- q 1)) (c (- p 1) q)))))GPMでは
$def,c,<$~1~2, $def,~1~2,<$$|,$lt,>~1<,0;,$lt,>~2<,>~1<;;, $def,t,0;, $def,f,<$+,$c,>>~1<<,$1-,>>~2<<;;,$c,$1-,>>~1<<;,>>~2<<;;>;;>;, $def,00,1;;>; $c,0,0;,$c,1,1;,$c,2,2;, => 1,1,2, $c,0,3;,$c,1,3;,$c,2,3;,$c,3,3;, => 1,3,5,5, $c,0,4;,$c,1,4;,$c,2,4; => 1,4,9と書ける.
論理関数
andやorはどうなるだろうか. 四則演算も自分で定義したくらいだから, 論理演算も出来るであろう. and, or, notはSchemeで書くと(define (and x y) (if x y #f)) (define (or x y) (if x #t y)) (define (not x) (if x #f #t))つまり(and x y)はxが真なら結果はyの真偽による; xが偽ならもちろん偽という定義でよい. (or x y)はxが真なら即真, 偽ならyに依存する. (not x)も見ての通り. これをGPMのif then elseで実装する. 真偽値はltと時と同様, tとfとする.
$def,&,<$~1,$def,~1,f;,$def,t,~2;;>; $def,|,<$~1,$def,~1,t;,$def,f,~2;;>; $def,\,<$~1,$def,f,t;,$def,t,f;;>;マクロ名には大体の文字が使えるから, andは&, orは|, notは\を使った.
$&,f,f;,$&,f,t;,$&,t,f;,$&,t,t; => f,f,f,t $|,f,f;,$|,f,t;,$|,t,f;,$|,t,t; => f,t,t,t $\,f;,$\,t; => t,fとなる. これを使って多数決maj(majority)と排他的論理和xorを定義する.
$def,maj,<$|,$|,$&,~1,~2;, $&,~2,~3;;,$&,~3,~1;;>; $def,xor,<$|,$&,~1,$\,~2;;, $&,$\,~1;,~2;;>; $maj,f,f,f;,$maj,f,f,t;, => f,f, $maj,f,t,t;,$maj,t,t,t; => t,t $xor,f,f;,$xor,f,t;,$xor,t,f;,$xor,t,t; =>f,t,t,fという次第だ. 二進の加算器が得られた気分だ.
Hilbert曲線
GPMはもともとプログラムの前処理系だったから, これを使ってプログラムの一部を発生させてみたい.PostScriptでHilbert曲線を描いてみよう. もちろんPostScriptには再帰呼出しの機能があるから, PostScriptだけで簡潔にプログラムできるわけだが, GPMを 使うのも一興である.
まずはHilbert曲線の描き方の復習から.
左下のpは左から進んで来て, +が示すように左折する(+は反時計方向に曲り, - は時計方向に曲る), 左中央のfを左回転したf+分だけ進み, -で右折, fと進み, -で右折, 右回転したf-と進み +で左折して右へ抜ける.
左上のqの描き方も同様に出来ている.
これらp, qから中央のp'を描くのも図の通りで, +で左折, 左回転したq+, 左回転したf+, 右折, p, f, pと進み, 右折, f-, q-と進んで左折する.
q'も同様.
次に大きいp'', q''は今のp, qをp', q' に変更するだけである.
これだけ分ればSchemeで実装できる.
(define (^ x) (modulo (+ x 1) 4)) (define (_ x) (modulo (+ x 3) 4)) (define (f d) (display (list-ref '( "l 0 rlineto " "0 l rlineto " "l neg 0 rlineto " "0 l neg rlineto ") d))) (define (p n d) (if (> n 0) (begin (q (- n 1) (^ d)) (f (^ d)) (p (- n 1) d) (f d) (p (- n 1) d) (f (_ d)) (q (- n 1) (_ d))))) (define (q n d) (if (> n 0) (begin (p (- n 1) (_ d)) (f (_ d)) (q (- n 1) d) (f d) (q (- n 1) d) (f (^ d)) (p (- n 1) (^ d)))))関数 ^ は4を法として1を足す, _ は4を法として1を引く.
(f d)はd向きのfを引くPostScriptの命令を返す. つまりd=0なら l 0 rlineto (x 方向へl ,y 方向へ0だけ移動,) d=1なら 0 l rlineto(x 方向へ0, y 方向へl だけ移動)のようになっている. negはその前の値の符号を変える.
(p n d)は大きさnのpを描く. q+, f+ ...だったから(q (- n 1) (^ d)), 1小さいqを(^ d)向きに描き, (f (^ d)), fを(^ d)向きに描き, ...と定義する.
(q n d)も同じだ.
これをGPMにしたのが次だ.
$def,1-,<$-1,0,1,2,3,4,5,6,7,8, $def,-1,<~>~1;;>; $def,^,<$1,2,3,0,$def,1,<~>~1;;>; $def,_,<$3,0,1,2,$def,3,<~>~1;;>; $def,f,<$~1, $def,0,<l 0 rlineto >;, $def,1,<0 l rlineto >;, $def,2,<l neg 0 rlineto >;, $def,3,<0 l neg rlineto >;;>; $def,p,<$~1, $def,~1, <$q,$1-,>~1<;,$^,>~2<;;$f,$^,>~2<;; $p,$1-,>~1<;,>~2<;$f,>~2<; $p,$1-,>~1<;,>~2<;$f,$_,>~2<;; $q,$1-,>~1<;,$_,>~2<;;>;, $def,0,;;>; $def,q,<$~1, $def,~1, <$p,$1-,>~1<;,$_,>~2<;;$f,$_,>~2<;; $q,$1-,>~1<;,>~2<;$f,>~2<; $q,$1-,>~1<;,>~2<;$f,$^,>~2<;; $p,$1-,>~1<;,$^,>~2<;;>;, $def,0,;;>; /l 20 def 100 100 moveto $p,3,0; stroke大部分はマクロの定義で, 最後の方 /l 20 def 100 100 moveto はこのまま出力にコピーされる. これはPostScriptのプログラムで, 変数lの値を20に設定する; 座標100 100 に移動する; という指令だ.
次の$p,3,0;でサイズ3, 進行方向0のHilbert曲線を描く命令
0 l rlineto l 0 rlineto 0 l neg rlineto l 0 rlineto l 0 rlineto 0 l rlineto (この後同様な28行省略) 0 l neg rlinetoが出力され, 最後に strokeの命令がコピーされる.
出来上がった図は
上に2つ並ぶ凹のような形に足のついたものの辺の数は15で, それが全部で4個あり, 左と上と右のそれらを繋ぐ辺が3こあるから, この図全体の辺は63個.
上の出力は28行の省略があるから全体で32行. 最後の行以外はrlinetoが2個ずつあるからrlineto, つまり辺の数は63個あるわけだ.
GPMの例題はまだ続く.
0 件のコメント:
コメントを投稿