2015年2月22日日曜日

Christopher StracheyのGPM

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; => 5
1桁の世界ではこの辺までしか計算できないから, あっという間に終るのは有難い. 特にコメントすることもあるまい.

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 件のコメント: