Christopher Stracheyという名前を初めて見たのは1959年にパリで開催された第1回のIFIPの会議の報告書で, そのpp.336-341に彼の
Time sharing in large, fast computers
という論文があった.
要するに割込みの機能を使ってのマルチプログラミングの提案であるが, 当時我々東大物理の高橋研のパラメトロン計算機でも, すでに割込みと並列計算の実験を始めていたので, 同じようなことは, 洋の東西で同じ頃に気附くものだと思った.
そのStracheyに出逢ったのは, 1971年4月 英国Warwick大学で開かれたIFIP WG2.2の会議でであった. この会議には主査の
Mike Woodger(NPL)を始め,
Edsger Dijkstra,
Willem van der Poel, Simulaを開発した
Ole-Johan Dahlなど有名な計算機科学者が大勢いた.
その会議中 パーティーが主催者の
John Buxtonの超古い家で開催され, みなが車に分乗して行くことになった. その時昔の小さいMiniに乗せてくれたのが大柄なStracheyであった. 「Eiitiは後に入れ」と私を後部座席に押し込み, 助手席に乘った
Brian Randellと機関銃のような英語で話し合っていた.
さて最近のIEEE Annals of the History of Computing(July-September 2013)を眺めていたら, 何年か前に私が情報処理学会誌に「Wilkes先生を悼む」を執筆した時にWilkes先生の写真を
送ってくれた
David HartleyさんがCPLのことを書いていて, その参考文献を辿っているうちに, CPLのアセンブラをGPM(General Purpose Macrogenerator)で作ったという話から, GPMを開発したStracheyがComputer Journalに寄せた論文
C. Strachey, A general purpose macrogenerator, Computer Journal Vol.8, No.3, 225-241
を探しあてた.
CPLはCambridge Plus Londonとも思えるが, Combined Programming Languageのアクロニムである. この言語はその後
Martin RichardsがMITにいるころ, BCPLに単純化して開発し, さらにベル研究所に行ってC言語になった, ということを覚えている人はもう少ないに違いない.
ところでそのmacrogeneratorである.
macroというからにはマクロ定義とマクロ呼出しがあるわけで, aというマクロをb~1dと定義すると, aがマクロ名, b~1dがマクロ本体で, 本体のうちbとdは定数, ~1は第1引数である. 一方, $a,c;がマクロ呼出しで, (もとの論文では先頭は§であるがASCII文字にないので, 以下では$を使う.) マクロ名の本体に対して, cが第1実引数となって, 呼出しの結果はbcdとなる.
マクロ呼出しは $マクロ名,引数1,引数2,...; の形. このマクロ名は引数0としても使うことが出来る.
マクロ呼出しは $ と ; で, 定数は < と > で囲まれているから, マクロ名や引数の中に再帰的に書くことが出来る. その場合, 局所的なマクロ呼出しは呼出しの結果, 局所的な定数は, 一番外の < と > を外した定数本体でその部分を置き換える. 置き換えて出来た結果の文字列で外側のマクロを呼び出す.
GPMではマクロ定義もマクロ呼出しの形で, 上のマクロaの定義は
$def,a,<b~1d>;
のように書く. このマクロ呼出しは空の文字列を結果として返す.
マクロ本体は, この例のように, 本体を評価されたくない時は < と > で囲む.
マクロ呼出しの入れ子の例は次の通り:
引数にマクロ呼出しがある例
$def,a,<b~1d>;
と定義し,
$a,$a,c;;
と呼び出すと,
bbcdd
が返る.
マクロ名にマクロ呼出しがある例
$def,a,<b~1d>;$def,bcd,<b~1c~2d>;
と定義し
$$a,c;,e,f;
と呼び出すと
bdcfd
が返る.
Stracheyの論文にはsucとsuccessorというマクロの例がある.
$def,suc,<$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;>;
$def,successor,
<$~2,$def,~2,~1<,$suc,>~2<;>;$def,9,<$suc,>~1<;,0>;;>;
sucは$suc,4;のように呼び出す. すると本体の1というマクロを呼び出すが, 引数の評価中にマクロ1が定義される. 引数~1が4なのでこのマクロの本体は~4になり, 1のマクロから5がとられて4の次の5が返る.
successorは
2桁の数の次を返す. $successor,3,4;だと3,5が, $successor,2,9;だと3,0が返るものだ.
3,4の場合はsuccessorの本体が
$4,$def,4,3,$suc,4;;$def,9.$suc,3;,0;;
となりマクロ4を呼び出そうとする. その$に対応する;は一番右にあるので, その前にマクロ4と9を定義する.
$def,4,3,$suc,4;;
だからマクロ4は3,5になり
$def,9,$suc,3;,0:
だからマクロ9は4,0になる. この状態でマクロ4を呼び出すから3,5か返る.
1の桁が9だと, マクロ9が2回定義され, その状態でマクロ9を呼び出すから後で定義した繰り上げのあるマクロの結果が返るのである.
この例にあるように, 本体評価中に定義されたものは, 評価が終わると定義のリストから削除されることに注意しよう.
Stracheyの元の論文にはCPLで書いたGPMの実装が載っている. CPLには再帰呼出しなどないから, スタックの上にリンクをつなげたりしていて, あまり読みたいとも思わない.
以下は私がSchemeで実装したものである. StracheyのGPMには四則演算の機能もあるが, そういうのはGPMの本質的なものではないから, 割愛した.
(define ch '())
(define (gpm str env args)
(let ((outs "") (index 0))
(define (getch)
(set! ch (string-ref str index))
(set! index (+ index 1))
(if (or (char=? ch #\space) (char=? ch #\newline)) (getch)))
(define (readquote)
(let ((outs ""))
(define (rq)
(getch)
(cond ((char=? ch #\>) outs)
((char=? ch #\<)
(set! outs
(string-append outs "<" (readquote) ">"))
(rq))
(else
(set! outs (string-append outs (string ch)))
(rq))))
(rq)))
(define (readstring)
(let ((outs ""))
(define (rs)
(if (= index (string-length str)) outs
(begin (getch)
(cond ((char=? ch #\,) (cons ch outs))
((char=? ch #\;) (cons ch outs))
((char=? ch #\<)
(set! outs (string-append outs (readquote)))
(rs))
((char=? ch #\~)
(getch)
(set! outs (string-append outs
(list-ref args (- (char->integer ch) 48))))
(rs))
((char=? ch #\$)
(set! outs (string-append outs (readmacrocall)))
(rs))
(else
(set! outs (string-append outs (string ch)))
(rs))))))
(rs)))
(define (readmacrocall)
(let ((actuals '()))
(define (rm)
(let* ((result (readstring))
(ch (car result)) (s (cdr result)))
(cond ((char=? ch #\,)
(set! actuals (cons s actuals)) (rm))
((char=? ch #\;)
(set! actuals (cons s actuals))
(macrocall (reverse actuals))))))
(rm)))
(define (macrocall actuals)
(cond ((string=? (car actuals) "def")
(set! env (cons (cdr actuals) env)) "")
(else
(let ((def (assoc (car actuals) env)))
(apply (cons (cadr def) actuals))))))
(define (apply expr)
(gpm (car expr) env (cdr expr)))
(define (gloop)
(let ((result (readstring)))
(cond ((string? result) (string-append outs result))
((char=? (car result) #\,)
(set! outs (string-append outs (cdr result) ","))
(gloop)))))
(gloop)))
上の例を実行してみよう.
(define str "$def,a,;$a,c;")
(gpm str '() '()) => bcd
(define str "$def,a,;$a,$a,c;;")
(gpm str '() '()) => bbcdd
(define str "$def,a,;$def,bcd,;$$a,c;,e,f;")
(gpm str '() '()) => becfd
(define str "$def,suc,<$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;>;
$suc,4;")
(gpm str '() '()) => 5
(define str "$def,suc,<$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;>;
$def,successor,
<$~2,$def,~2,~1<,$suc,>~2<;>;$def,9,<$suc,>~1<;,0>;;>;
$successor,3,4;,$successor,2,9;")
(gpm str '() '()) => 3,5,3,0
ついでに, 論文にあったsumは
$sum,α,β,γ;
で2桁の十進数α,βに1桁の数γを足すもので, $3,4,2;は以下のように3,6になる.
(define str "$def,suc,<$1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;>;
$def,successor,
<$~2,$def,~2,~1<,$suc,>~2<;>;$def,9,<$suc,>~1<;,0>;;>;
$def,sum,<$s,~1,~2,0,
$def,s,<$~3,$def,~3,<$s,>$successor,~1,~2;
<,>$suc,~3;<;>;$def,>~3<,~1<,>~2;;>;;>;
$sum,3,4,2;")
(gpm str '() '()) => 3,6
これは難しいからマクロ呼出しのトレースをしてみる.
00 (def suc $1,2,3,4,5,6,7,8,9,10,$def,1,<~>~1;;)
01 (def successor $~2,$def,~2,~1<,$suc,>~2<;>;
$def,9,<$suc,>~1<;,0>;;)
02 (def sum $s,~1,~2,0,$def,s,<$~3,$def,~3,<$s,>
$successor,~1,~2;<,>$suc,~3;<;>;$def,>~3<,~1<,>~2;;>;;)
03 (sum 3 4 2)
04 (def s $~3,$def,~3,<$s,>$successor,~1,~2;<,>
$suc,~3;<;>;$def,2,~1<,>~2;;)
05 (s 3 4 0 )
06 (successor 3 4)
07 (def 4 3,$suc,4;)
08 (def 9 $suc,3;,0)
09 (4 )
10 (suc 4)
11 (def 1 ~4)
12 (1 2 3 4 5 6 7 8 9 10 )
13 (suc 0)
14 (def 1 ~0)
15 (1 2 3 4 5 6 7 8 9 10 )
16 (def 0 $s,3,5,1;)
17 (def 2 3,4)
18 (0 )
19 (s 3 5 1)
20 (successor 3 5)
21 (def 5 3,$suc,5;)
22 (def 9 $suc,3;,0)
23 (5 )
24 (suc 5)
25 (def 1 ~5)
26 (1 2 3 4 5 6 7 8 9 10 )
27 (suc 1)
28 (def 1 ~1)
29 (1 2 3 4 5 6 7 8 9 10 )
30 (def 1 $s,3,6,2;)
31 (def 2 3,5)
32 (1 )
33 (s 3 6 2)
34 (successor 3 6)
35 (def 6 3,$suc,6;)
36 (def 9 $suc,3;,0)
37 (6 )
38 (suc 6)
39 (def 1 ~6)
40 (1 2 3 4 5 6 7 8 9 10 )
41 (suc 2)
42 (def 1 ~2)
43 (1 2 3 4 5 6 7 8 9 10 )
44 (def 2 $s,3,7,3;)
45 (def 2 3,6)
46 (2 )
行0,1,2はマクロ定義, 3が呼出しだ. sumを呼び出すと$s,3,4,0とマクロを呼び出す準備をするが ;はまだないので$def,s,...をやってsを定義する.
この際殆どの引数は< >に囲まれているが, 右から15文字目くらいの~3はsumの最後の引数2になる. 4行目で見るとおり. ここでsを呼び出す($s,3,4,0;).
sの本体は$0の呼出しをしようとするが$def,0,があるので0を定義する(16行目). 3,5は$successor,~1,~2;で, 1は$suc,~3;で作られる. それを作るのがトレースの15行目までだ. 次にマクロ2を定義する(17行目).
やっと0が呼び出せ(18行目), Ss,3,5,1;を呼び出す(19行目).
今度はマクロ1と2を同じように定義し, $s,3,6,2;を呼び出す(33行目).
するとマクロ2と2が定義され(44, 45行目), 後から定義された2の本体3,6が返るのである.
万歳. うまくいっているようだ.
