2015年1月27日火曜日

Christopher StracheyのGPM

このブログでGPMのことを書いたのは2013年12月だから1年以上前になる. 英国の計算機保存団体の発行するComputer Resurrectionの昨年の夏号にStrachey's General Purpose Macrogeneratorという記事を見付けたのを切っ掛けに元の論文にあった例題以外のマクロを書こうと思いたった.

かなりたくさんのマクロを書いたので, 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;  => f
ltつまり<は, この世界の下が-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;; をやると定義してある.

結果は上のようだ. 次のブログへ続く.

0 件のコメント: