かなりたくさんのマクロを書いたので, GPMの楽しさを紹介しようとして今年のプログラミング・シンポジウムでそれに関する話をした.
これとそれに続く何回かのブログでは, それらのマクロについて書きたい.
まず簡単におさらいをしておく.
"$def,a,<b~1d>;" はマクロ "a" が "<b~1d>" であると定義する. "$a,c;" でマクロ "a" を実引数 "c" をもって呼び出すと, マクロ本体の第1引数 "~1" に "c" が代入されて "bcd" が返る. "~0" は第0引数を表わすから, マクロ "a'" を "$def,a',<~0b~1d>;" と定義し "$a',c;" と呼び出すと "a'bcd" が返る.
マクロ呼出しは "$マクロ名, 実引数1, 実引数2, ... ;" の形で, マクロ名も実引数もまず評価される, つまりマクロ呼出しがあれば実行し, 引数"~n" があれば置き換える. それ以外はそのまま. 評価を避けたい時は"<" と ">" で囲むが評価が済むと両端の "<" と ">" がなくなる.
上の "a" の定義があった時, "$a,$a,c;;" と呼び出すと, 第1引数 "$a,c;" がまず評価されて "bcd" になり, それで "$a,bcd;" と呼び出すから "bbcdd" が返る.
マクロ呼出しの実引数の並びの中に局所定義を書くことが出来る. 定義されてから呼び出すから, "$a,c,$def,a,<b~1d>;;" のように書くと, "bcd" が返る. 局所定義は呼出しが終わると消える.
同じマクロ名の定義はスタック状に記憶され, 最新のものを使う. 定義が消えるともとの定義が見えるようになる.
"$def,a,b;" と定義しておき, "$a,$def,a,c;,$def,a,d;;" と呼び出すと, "a" の最後の定義が "$def,a,d;" だから "d" が返り, それが済むと最初の定義がスタックの上に来るから, ここで "$a;" と呼び出すと "b" が返る.
この機能を使うと条件式が書ける.
"(if (eq? α β) γ δ)" は"$α,$def,α,δ;,$def,β,γ;;" と書く. αとβが同じ時は, 2つの局所定義の後のもαになるからそちらを使い, γになり, 違う時は, 前の局所定義を使い, δになる.
これだけ知っていれば, GPMのマクロを書くことが出来る.
基本演算
GPMには算術演算もないから, その辺から始めなければならない. 最初は引数に1を足すマクロ "1+". 定義と使用例は次のとおり.$def,1+,<$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;>; $1+,0; => 1 $1+,4; => 5 $1+,9; => 10"$1+,4;" の場合, マクロ "1+" の本体 "$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;" が評価される. つまりマクロ "1" を実引数 "2,3,4,5,6,7,8,9,10" で呼び出す. その"1"の局所定義は後にあり, "~1" に "4" が代入されて "$def,1,~4;" になっている. 従って第4引数 "5" が返る.
$def,1-,<$-1,0,1,2,3,4,5,6,7,8,$def,-1,<~>~1;;>; $1-,0; => -1 $1-,9; => 8"1-"も上のマクロ "1+" と殆ど同じ. 引数が"~"の後の1文字なので, ここで使う整数は0から9までということになる.
$def,+,<$~1, $def,~1,<$1+,$+,$1-,>~1<;,>~2<;;>;, $def,0,~2;;>; $+,0,3; => 3 $+,3,5; => 8マクロ "+" は条件式になっている. 最後の行 "def,0,~2;" は, 第1引数が "0" なら第2引数が答, そうでないなら, 第1引数から1を引いたものと第2引数と足してそれに1を足すと再帰的に定義する.
Scheme流に書けば
(λ (x y) (if (= x 0) y (1+ (+ (1- x) y))))
$def,-,<$~2, $def,~2,<$-,$1-,>~1<;,$1-,>~2<;;>;, $def,0,~1;;>; $-,3,0; => 3 $-,6,4; => 2第2引数による条件式で, 0なら第1引数が答. そうでないなら第1引数から1を引いたものから第2引数から1を引くと再帰的に定義する.
(λ (x y) (if (= y 0) x (- (1- x) (1- y))))
$def,*,<$~1, $def,~1,<$+,$*,$1-,>~1<;,>~2<;,>~2<;>; $def,0,0;;>; $*,0,5; => 0 $*,1,4; => 4 $*,2,3; => 6
(λ (x y) (if (= x 0) 0 (+ (* (1- x) y) y)))
$def,lt,<$~1, $def,~1,<$p,>~1<,>~2<,$def,p,$lt,$1-,>~1<;,>~2<;;;>; $def,-1,t;$def,~2,f;;>; $lt,-1,-1; => f $lt,-1,0; => t $lt,0,-1; => fltつまり<は, この世界の下が-1までであることを利用している.
(λ(x y) (cond ((= x y) f) ((= x -1) t) (else (lt (1- x) y))))
これを使って剰余を書く.
$def,r,<$$lt,~1,~2;, $def,t,~1;,$def,f,<$r,$-,>~1<,>~2<;,>~2<;>;;>; $r,9,5; => 4(λ (x y) (if (< x y) x (r (- x y) y)))
基本演算ばかりでは面白くないので, 応用として情報科学標準問題のHanoiの塔をやってみよう.
Hanoiの塔
$def,1-,<$-1,0,1,2,3,4,5,6,7,8, $def,-1,<~>~1;;>; $def,hanoi,<$~4, $def,~4,<$hanoi,>~1<,>~3<,>~2<,$1-,>~4<;; +>~1<->~3<+ $hanoi,>~2<,>~1<,>~3<,$1-,>~4<;;>; $def,0,<>~1<->~3<>;;>; $hanoi,a,b,c,0; => a-c $hanoi,a,b,c,1; => a-b+a-c+b-c $hanoi,a,b,c,2; => a-c+a-b+c-b+a-c+b-a+b-c+a-c$hanoi,a,b,c,n;はn枚の円板をaからcへbを中継点として移動する手続きで, nが0なら$def,0,にあるように ~1-~3とする. -は引き算ではなく, 引数の間に-を書くことである. そうでないなら, $hanoi,~1,~3,~2,$1-,~4;; をやり +~1-~3+とし, $hanoi,~2,~1,~3,$1-,~4;; をやると定義してある.
結果は上のようだ. 次のブログへ続く.
のように出力するには, スペースの位置の下の数と, 最後の桁の上の数を足したものがパラメタの値であり, 28行目は3072+32=3104となっている.
