この記事は書きかけです
今回は前回作った LISP インタプリタにマクロを実装します。 構文木 Eval 式だと最適化の余地とかあんまりなくて面白くないんで、 次回は大きくリファクタリングしてバイトコード VM の導入ですかねぇ。
各章の先頭の煽り文句は、昔某掲示板に投稿した銀河帝国ネタからの抜粋です。↓こんなの。 もちろん第二ファウンデーションは Scheme 使いの集団の予定でした。第一とは仲が悪いあたりも似てますね。
第一銀河帝国は、何世紀にもわたって少しずつ頽廃と崩壊を続けていた。 だが、その事実を理解している人間は、帝国の生んだ最後の天才科学者、ハリ・セルダンだけだった！ 彼は自ら完成させたλ歴史学を用いて帝国の滅亡とその後に続く３万年の暗黒時代を予言したのだ。 この暗黒時代をただの千年に短縮するため、セルダンは二つのファウンデーションを設立した…
ガールはセルダンに尋ねた。
「でも、なぜ強制的にマイナーにならなければならなかったのですか？」間を置いて、「私には教えていただけないのですか？」
「まだ、だめだ。今のところは次の事を知っているだけで十分だ。実用的な Common Lisp がターミナスに建設されるということ。 そして、もうひとつが銀河系の反対側の端に。つまり、”星界の果て”に建設されるということ。」
ついにセルダンは計算をやめて、いった。「これは１０年後の LispOS だ。これをどう解釈するかね？」
かれは小首を傾げて、待った。
ガールは信じられないようにいった。
「完全な滅亡です！GUI を装備していたということすら忘れられている！しかし…しかし、そんなことはありえません。 いまだかつて… MAC LISP コンパイラは Fortran コンパイラにさえ負けなかったというのに…」
「これこれ、この結果がどうやって出たか見ただろうに。しばらく記号体系は忘れて、言葉で表現してみたまえ」
「Lisp マシンそのものが増大する汎用マイクロプロセッサのパワーに押されて性能的に厳しい状態に置かれます。 また、CPU パワーやメモリを有効活用するために C のような言語が普及し、それにつれて、 Lisp の GC 等は性能上の問題とみなされるようになります。 その結果、S 式に対する反感が増大し、メモリ管理は原始的な手動管理に退行し、 バッファオーバーフローが社会的問題になります」
「問題の真の解決は、次のバージョンアップの中にあるという理事会の結論を隠しても無意味だと思われます」
「それが、この問題へのあなたの意見なのですか？」
「ええ」
「つまり、次のバージョンアップから飛び出す救いの神に全幅の信頼を置いて、心静かに待つ以外、何もすべきではないというのですか？」
「感情的な言い回しを剥ぎ取れば、主旨はそうゆう事です」
「なんと厚かましい逃避主義であることか！まさに、天才の発想ですな。下等な精神では思いつけないものです」
なんでマクロかというと、システムを拡張できるシンプルで簡単な仕組みだからです。 前回の LISP には、なんと let 構文すらありません。これでは使い難いですね。 では let を実装するには？最も安易な方法はインタプリタを拡張して評価器に let 構文を認識して処理させることでしょう。
(defun interpret (sexp env)
"Lisp インタプリタ本体"
(cond ((symbolp sexp) (lookup-value sexp env))
((atom sexp) sexp)
(t
(case (first sexp)
(quote (second sexp))
(progn (loop for exp in (cdr sexp)
for val = (interpret exp env)
finally (return val)))
(if (if (interpret (second sexp) env)
(interpret (third sexp) env)
(interpret (fourth sexp) env)))
(lambda (let ((args (second sexp))
(body (nthcdr 2 sexp)))
#'(lambda (&rest rest)
(let ((newenv (extend-env args rest env)))
(interpret (cons 'progn body) newenv)))))
(let ...) ;;; let 構文を実装する
(t (apply (interpret (first sexp) env)
(mapcar #'(lambda (e) (interpret e env)) (rest sexp))))))))
では、 let* は？
(defun interpret (sexp env)
"Lisp インタプリタ本体"
(cond ((symbolp sexp) (lookup-value sexp env))
((atom sexp) sexp)
(t
(case (first sexp)
(quote (second sexp))
(progn (loop for exp in (cdr sexp)
for val = (interpret exp env)
finally (return val)))
(if (if (interpret (second sexp) env)
(interpret (third sexp) env)
(interpret (fourth sexp) env)))
(lambda (let ((args (second sexp))
(body (nthcdr 2 sexp)))
#'(lambda (&rest rest)
(let ((newenv (extend-env args rest env)))
(interpret (cons 'progn body) newenv)))))
(let ...) ;;; let 構文を実装する
(let* ...) ;;; let* 構文を実装する
(t (apply (interpret (first sexp) env)
(mapcar #'(lambda (e) (interpret e env)) (rest sexp))))))))
このように構文を追加する毎にインタプリタを拡張すればいいわです。が、逆に言えば、この方式では構文を追加するためには いちいちインタプリタを修正する必要があるという事です。欲しい機能があった時に、いちいち次のバージョンアップまで待つか、 自力でパッチをあてるか、どちらにしても現実的ではありませんね。そこでマクロの出番です。
システムは最低限のプリテミティブとマクロシステムを提供します。マクロはプログラム変換されて最終的にプリミティブに展開されるのです。 たとえば、let はプログラム変換によって lambda に展開する事で実現できます。
(let ((x 0))
(print x))
↓
((lambda (x) (print x)) 0)
(let ((x 0)
(y 1))
(print x)
(print y))
↓
((lambda (x y) (print x) (print y)) 0 1)
さらに、この let を使えば let* も容易に実装できます。
(let* ((x 0)
(y (+ x 1)))
(print y))
↓
(let ((x 0))
(let ((y (+ x 1)))
(print y)))
↓
((lambda (x)
((lambda (y)
(print y))
(+ x 1))
0))
結局のところ、今回の目標はインタプリタを次のような形式にするということになります。
(defun interpret (sexp env)
"Lisp インタプリタ本体"
(cond ((symbolp sexp) (lookup-value sexp env))
((atom sexp) sexp)
;;; マクロシステム (マクロをプリミティブのみを含むフォームに展開する)
((macrop sexp) ....)
(t
;;; プリミティブの実行
(case (first sexp)
(quote (second sexp))
(progn (loop for exp in (cdr sexp)
for val = (interpret exp env)
finally (return val)))
(if (if (interpret (second sexp) env)
(interpret (third sexp) env)
(interpret (fourth sexp) env)))
(lambda (let ((args (second sexp))
(body (nthcdr 2 sexp)))
#'(lambda (&rest rest)
(let ((newenv (extend-env args rest env)))
(interpret (cons 'progn body) newenv)))))
(t (apply (interpret (first sexp) env)
(mapcar #'(lambda (e) (interpret e env)) (rest sexp))))))))
let の例だと、新しい構文 let をマクロシステムがプリミティブ lambda のみを含むフォームに展開します。 このようにマクロが入力フォームをプリミティブに分解するため、インタプリタのコア部分には手を入れなくていいわけですね。
「その当時かれが、問題を予見できたということはありえるとして、同様に今われわれは問題をはっきり見ることができるということを忘れてはいけません。 要するに彼は魔法使いではないんです。彼には見えて、我々には見えないというジレンマを脱け出すトリックは存在しないのです！」
「しかし、我々には見えないんですよ。」
「見ようとしなかったからです。一度だって見ようとしなかった。そもそも、最初は問題が存在することさえ認めなかった！ 次に諸君らは規格への絶対的、盲目的な信頼の上にあぐらをかいた！今度はそれをスティールの上に移した！ 諸君は徹頭徹尾、権威または過去を頼りにして−−−決して自分自身を頼りにしたことがない」
かれの握りしめた拳がぶるぶる震えた。
「これは結局病的な態度です−−−権威に反対するという問題が生じるたびに、心の独立を脇に逸らすという、一種の条件反射なのです。 どうやら自分よりも規格のほうが偉いとか、スティールのほうが賢いということについて、諸君の心の中には疑いは全然ないみたいですねぇ。 間違っているのはそこなんですよ」
let 構文を組み込むために、インタプリタを拡張するのではなく、マクロという新しい仕組みを導入するのは何故でしょうか？ もし、let があなたの関心のある構文のすべてであるなら、マクロという大袈裟な機能はコストに見合わないと感じるかもしれません。 しかし、他にも導入したい構文があるのです。例えば when や unless, cond といったお馴染の構文などです。これらは、if のみで表現できます。
let 以外の構文もインタプリタそのものの拡張ではなく、マクロシステムを使って実装できるという事です。ここでは制御構文 when と unless と cond のマクロによる実装を考えてみましょう。
(when 条件 本文)
↓
(if 条件
(progn 本文))
(unless 条件 本文)
↓
(if 条件
nil
(progn 本文))
(cond (条件1 本文1)
(条件2 本文2)
(条件3 本文3))
↓
(if 条件1
(progn 本文1)
(if 条件2
(progn 本文2)
(if 条件3
(progn 本文3))))
また、どうしても (if 条件 文 else-if 条件 文 else 文) のような形式でないとイヤという人も要るでしょう。この構文も if のみで実現できます。
(if 条件1
文1
else-if 条件2
文2
else-if 条件3
文3
else
文4)
↓
(if 条件1
文1
(if 条件2
文2
(if 条件3
文3
文4)))
どうですか？そう、今やプログラムの表現はあなたの思いのままです _1 。たとえ GLS を含む ANSI 委員会が if と when と unless と cond しか用意しなかったら、 それだけに固執する事はないのです。あなたの処理系は今は if しか備えていませんが……そう、マクロシステムを導入すれば when でも cond でも elseif でも あなたが 望むものなら何でも実現できるのです。それを制限するのは、 あなたの
.. 1 : まだ S 式に縛られていると感じるかもしれませんが、その壁を超えるにはリーダーマクロが必要です。
「帝国の大臣はマクロを使える技術者がいないといって、こぼしている。そして解決策は？新しい技術者を養成する？とんでもない！そうする代わりにマクロを制限するのです」
というわけで、マクロを実装してみましょう。ここが今回の山場です。マクロとはプログラムの変形とか強力とか言われますが、そのシンプルさこそが 重要な点です。まず、一番シンプルなプログラム変換 when 構文を if に展開してみましょう。
'(when condition1
exp1
exp2)
↓
'(if condition1
(progn exp1 exp2))
難易度が高そうですね？
(lambda (condition1 &rest body)
;; condition1 := condition1
;; body := (exp1 exp2)
...)
;; 実装例1
(lambda (condition1 &rest body)
(list 'if condition1
(cons 'progn body)))
;; 実装例2
(lambda (condition1 &rest body)
`(if ,condition1
(progn
,@body)))
どうでしょう？バッククォート記法に慣れると実装例2 が自然に見えるようになります。
posted: 2007/02/25 22:54 | permanent link to this entry | Tags: LISP