続 L2Lisp: 従来の約３倍の速さの実現
2007.6.1 (2010.8.11 リンク修正) (鈴)- 前回 L2Lisp: 標準 Pascal によるモダンな Lisp の小さな実装 (L2Lisp 1.1 版) 2007.4.28 - 2007.5.18
- 1. はじめに
- 2. ラムダ式のコンパイルとマクロ展開
- 3. 未インターン・シンボルの実現
- 4. おわりに
- 次回 続々 L2Lisp: マクロの健全化 (L2Lisp 3.0 版) 2007.6.11 - 2007.7.4
- L2Lisp.p 2.0 版, UTF-8, CR/LF, 1449 行, 50666 バイト, MD5: fad0f894bf127f1ac7a3e3e1d3832652
- l2init 2.0 版, CR/LF, 109 行, 2927 バイト, MD5: f610522d0de82358aff36cd49a87c7fa
- 上記の Web 閲覧用ファイル: L2Lisp.p (HTML 形式), l2init (HTML 形式)
- 1.1 版 からの変更点
L2Lisp.p の変更点 ・入れ子のラムダ式のコンパイル ・入れ子マクロ定義の陽な禁止 ・未インターン・シンボルの実現 ・make-symbol 関数を非組込みに l2init の変更点 ・make-symbol を定義 ・gentemp に替え gensym を定義
1. はじめに
L2Lisp (Little Lambda Lisp) 1.1 版は， 前回 §7 で示したように 下記の簡単なプログラムを実行するときは適度に高速である。
(defun fib (n)
(if (< n 2)
n
(+ (fib (- n 1))
(fib (- n 2)))))
(fib 30)
しかし，次のような，より複雑なプログラムを実行するときは， それほど速くない。
;; N クイーン問題
;; 猪股・益崎「Schemeによる記号処理入門」森北出版 1994年
;; §8.2 の Scheme コードから
(defun node-expand (n lst)
(if (= n 0) nil
(cons (cons n lst)
(node-expand (- n 1) lst))))
(defun safe? (lst)
(let ((new (car lst))
(hlst (cdr lst)))
(if (null hlst) t
(safe-aux? new (+ new 1) (- new 1) hlst))))
(defun safe-aux? (new up down hlst)
(if (null hlst) t
(let ((pos (car hlst)))
(and (not (= pos new))
(not (= pos up))
(not (= pos down))
(safe-aux? new (+ up 1) (- down 1) (cdr hlst))))))
(defun goal? (x n) (= (length x) n))
(defun nqueens (n)
(let (lst solution x pop push search)
(setq lst (node-expand n nil))
(setq solution nil)
(setq x nil)
(defun pop () (let ((y (car lst)))
(setq lst (cdr lst))
y))
(defun push (y) (setq lst (append y lst)))
(defun search ()
(if (null lst)
solution
(setq x (pop))
;; (princ "lst = ") (princ lst)
;; (princ " x = ") (princ x) (terpri)
(if (safe? x)
(if (goal? x n)
(setq solution (cons x solution))
(push (node-expand n x))))
(search)))
(search)))
(nqueens 6) ; ((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5))
(length (nqueens 10)) ; 724
その主な理由は L2Lisp 1.1 版が入れ子のラムダ式をその都度毎回 "コンパイル" するからである。
前回 §6 で説明したように， L2Lisp は，let や defun を，ラムダ式を含んだ式へのマクロとして実装している。 上記のプログラムは，入れ子のラムダ式を大量に含んだ S 式の並びになる。 しかし，1.1 版は，ラムダ式を評価するとき，最外のラムダ式だけをコンパイルする。 内側のラムダ式は必要になったとき，その都度コンパイルする。
そこで L2Lisp 2.0 版では， ラムダ式を評価するとき，入れ子のラムダ式を再帰的に一括してコンパイルするように改めた。 これにより，上記のプログラムに対し，次に示すように 1.1 版に比べて 約３倍の速さが得られた*1。
$ time ./llsp11.exe < 10queens.l > node-expand > safe? > safe-aux? > goal? > nqueens > ((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5)) > 724 > Goodbye. real 0m19.782s user 0m19.702s sys 0m0.046s
テスト環境は前回 §7 と同様である。 上記の 1.1 版の結果に対し，2.0 版は下記のとおり起動も含め約 1/3 の時間で終了した。
$ time ./llsp.exe < 10queens.l > node-expand > safe? > safe-aux? > goal? > nqueens > ((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5)) > 724 > Goodbye. real 0m6.406s user 0m6.280s sys 0m0.092s
この高速化を実現した 2.0 版のラムダ式のコンパイルとマクロ展開の方法を §2 で説明する。
2.0 版は make-symbol 関数がインターン済みのシンボルを作ってしまう問題 (前回 §5) も解決した。 P. Graham 著 On Lisp 9. "変数捕捉" で説明されているように，Lisp のマクロ定義は，名前の衝突を回避するため， 新しくその場でシンボルを作る必要がしばしばある。 しかし，インターン済みのシンボルを作ると，回収困難なかたちで資源を消費するため，マクロの使用が高くつく。 L2Lisp の実装では，やがてシンボル領域を使い尽くし，新しいシンボルを定義できなくなる。 未インターン・シンボルの一つの実現方法を §3 で説明する。
2.0 版の処理系のコンパイルと実行の方法は 1.1 版の場合と同じである。
むしろ，2.0 版のねらいは，ローカル変数やマクロを使うとやたらに遅くなるのでは？ という心配を取り除くことによって，気兼ねなく，素直なプログラムを L2Lisp で書けるようにすることです。
2. ラムダ式のコンパイルとマクロ展開
1.1 版でラムダ式を評価すると，入れ子のラムダ式は，最外ラムダ式の仮引数の出現を除き，そのまま残される。 1.1 版による下記の例では， シンボル a の出現がレベル 0 オフセット 0 のローカル変数参照へ変換されていることを除き， 入れ子のラムダ式は変更を受けていない。
> (lambda (a) (lambda (b) (foo a b))) (#<lambda> (1) (lambda (b) (foo (#<arg> 0 0 . a) b)))
1.1 版でこのようなラムダ式で関数を定義すると， 入れ子のラムダ式が関数の実行ごとに使い捨てでコンパイルされるため，効率的でない。 一つの解決方法は，入れ子のラムダ式が評価される都度，その結果を使い捨てにせずにメモすることである。 しかし，2.0 版では，その方法はとらず， ラムダ式の評価時に入れ子のラムダ式も一括して再帰的にコンパイルする方法をとった。 手続き EvalTop とその内部手続き CompileLambda (前回 §4 を参照) の局所的な改修だけで大半を実現できるからである。
2.0 版による例を示す。
> (lambda (a) (lambda (b) (foo a b))) (#<closure> (1) (#<lambda> 1 (foo (#<arg> 1 0 . a) (#<arg> 0 0 . b))))
したがって，典型的には，関数を定義したとき，そのコンパイルはすべて済んでいる。
> (defun bar (a) (lambda (b) (foo a b))) bar > bar (#<closure> (1) (#<lambda> 1 (foo (#<arg> 1 0 . a) (#<arg> 0 0 . b))))
今までの方法では，ラムダ式をコンパイルするとき，仮引数の変換と字句的環境の付加の両方をおこなっていた。 しかし，最外ラムダ式を除き，コンパイル時に字句的環境はまだない。 そこで，コンパイル済みラムダ式を，#<lambda> を先頭要素とする字句的環境なしの式と， #<closure> を先頭要素とする字句的環境ありの式の２種類に分ける。
#<lambda> を先頭要素とする字句的環境なしの式は，仮引数並びにかえて，期待される引数の個数 (arity) をおく (上記の例では 1)。
#<closure> を先頭要素とする字句的環境ありの式は，仮引数並びにかえて， arity と字句的環境のリストのペアをおく (上記の例では (1) つまり (1 . nil))。
手続き CompileLambda は，相互再帰的な内部手続き Compile と CompileInners を使って， 与えられたラムダ式を再帰的に字句的環境なしの式にコンパイルし， 最後に最外ラムダ式を，手続き MakeClosure を使って， (その時点での処理系の大域変数 environ を字句的環境のリンクとして) 字句的環境ありの式に替える。
手続き EvalTop は，字句的環境なしの式を評価する都度，それを手続き MakeClosure を使って字句的環境ありの式に替える。
手続き MakeClosure を下記に示す。 ValType, Push, Cons, cell については前回 §3 を参照されたい。 EvalTop は，#<closure> を表す大域定数 ClosureImp を引数 newkar として MakeClosure 手続きを呼び出す。
procedure MakeClosure(newkar, j : ValType); { j = (arity . body) }
begin
Push(newkar);
Push(cell[j].car);
Push(environ); { newkar arity link }
Cons; { newkar (arity . link) }
Push(cell[j].cdr);
Cons;
Cons { (newkar (ariy . link) . body) }
end; { MakeClosure }
ラムダ式をコンパイルするとき，それぞれのラムダ式本体に対してマクロ展開を行う。 展開は，コンパイル済みマクロ式，またはコンパイル済みマクロ式に束縛された大域変数が， 関数の位置にあったときに行う。例を示す。
> if (#<macro> (-3) (cons cond (cons (list (#<arg> 0 0 . test) (#<arg> 0 1 . then)) ( cond ((#<arg> 0 2 . else) (list (cons t (#<arg> 0 2 . else)))))))) > (lambda (a) (if a (lambda (b) (if b (foo a b))))) (#<closure> (1) (cond ((#<arg> 0 0 . a) (#<lambda> 1 (cond ((#<arg> 0 0 . b) (fo o (#<arg> 1 0 . a) (#<arg> 0 0 . b))))))))
内部手続き Compile は，ラムダ式の仮引数を変換した後で， ラムダ式本体にあるマクロを，手続き ExpandGlobalMacros を使って展開する。 ExpandGlobalMacros はそれ自身では入れ子のラムダ式の中に立ち入らない。 入れ子のラムダ式に対し再帰的に Compile が呼び出されたとき， そこから呼び出される ExpandGlobalMacros が入れ子のラムダ式本体をマクロ展開する。 この方法の帰結として On Lisp 9. で説明されている "フリーシンボルの捕捉" は発生しない。 例えば，
> (defmacro m (n) (list 'setq 'w n)) m > ((lambda (w) (m 3) (print w) ((lambda (w) (m 4) (print w)) 100)) 200) 200 100 100 > w 4
マクロ m が展開する変数 w への代入に，ラムダ式の仮引数 w は影響を受けない。 マクロによる変数 w への代入は大域的に行われる。 これはラムダ算法 (のアルファ変換) を考慮すれば妥当な振舞であろう。 実装上，なぜこうなるかはラムダ式の評価値から明らかである。
> (lambda (w) (m 3) (print w) ((lambda (w) (m 4) (print w)) 100)) (#<closure> (1) (setq w 3) (print (#<arg> 0 0 . w)) ((#<lambda> 1 (setq w 4) (pr int (#<arg> 0 0 . w))) 100))
仮引数が変換された後でマクロを展開しているから，あえて内部実装シンボル #<arg> をじかに扱わない限り，捕捉は起こらない。
しかし，この振舞は Common Lisp と異なる。 Cygwin 上の clisp の実行例を示す。 Emacs Lisp も (ささいな表現の違いを除けば) これと同様である*2。
[1]> (defmacro m (n) (list 'setq 'w n)) M [2]> ((lambda (w) (m 3) (print w) ((lambda (w) (m 4) (print w)) 100)) 200) 3 4 4 [3]> w *** -EVAL: variable W has no value
なお，L2Lisp 2.0 版が現在のような仕様になっているのは， (名前の由来でもある) ラムダ算法との適合性を考慮して…というより， 実はむしろ，お手軽な実装で済ませたためでした。 仮引数を変換した後に残存しているのは自由なシンボルだけのはずですから， 関数位置にあるシンボルのうち (#<macro> …) を値としているものをどんどん展開していけばよいわけです。
可能性としてはマクロ式もラムダ式と同じく字句的環境をもてるが， 2.0 版では簡単のため，大域的な (つまり空の字句的環境をもつ) マクロ式だけを許す。 展開対象のラムダ式と同じ字句的環境を共有している場合，ラムダ式のコンパイル時には，まだその環境はない。 さしあたり今は非大域的なマクロ式を一律に禁止して微妙な問題の発生を避ける。 生のマクロ式 (macro …) からコンパイル済みマクロ式 (#<macro> …) への変換は (ラムダ式の場合とほとんどの処理が共通だから) 手続き CompileLambda が行う。 CompileLambda は内部手続き CompileInners での入れ子のマクロ式のコンパイルをエラー扱い (goto でエラー処理へ大域脱出) するとともに， 最外のマクロ式に対して，environ が nil 値であることをチェックして，大域的であることを保証する。
ローカル変数が大域的なコンパイル済みマクロ式に束縛されている場合，コンパイル時には展開されず， 適用時に展開と評価が行われる。 処理系の大域定数 MaxMacroExps で規定される限度を超えて再帰的に展開しようとするマクロ式も， 限度超過分は，適用時に展開と評価が行われる。 前者の例を示す。
> (defmacro m (e) (list 'progn (list 'print e) (list 'print e) nil)) m > (m "hi") "hi" "hi" nil > (defun f (x) (x (progn (prin1 "hi") "ho"))) f > f (#<closure> (1) ((#<arg> 0 0 . x) (cond (t (prin1 "hi") "ho")))) > (f m) "hi""ho" "hi""ho" nil >
3. 未インターン・シンボルの実現
前節で述べたとおり L2Lisp ではフリーシンボルの捕捉は発生しない。 しかし，On Lisp 9. で述べられているもう一種類の変数捕捉 "マクロ引数の捕捉" は L2Lisp でも発生する。 次の例は，大域変数であれ，ローカル変数であれ，シンボル a を引数に渡したときだけ，変数捕捉による奇妙な振舞を示す。
> (defmacro m (x)
(list 'let '((a 4))
(list 'if (list '< 'a x) (list 'print x))))
m
> (m 10)
10
10
> (m 1)
nil
> (setq a 10)
10
> (m a)
nil
> (let ((a 10)) (m a))
nil
> (let ((b 10)) (m b))
10
10
ダミーのラムダ式に入れてコンパイル結果を確認すると，マクロ引数として与えたシンボル a が，マクロ展開されるラムダ式の仮引数 a と混同されていることが分かる。
> (lambda () (m a)) (#<closure> (0) ((#<lambda> 1 (cond ((< (#<arg> 0 0 . a) (#<arg> 0 0 . a)) (prin t (#<arg> 0 0 . a))))) 4)) > (lambda () (let ((a 10)) (m a))) (#<closure> (0) ((#<lambda> 1 ((#<lambda> 1 (cond ((< (#<arg> 0 0 . a) (#<arg> 0 0 . a)) (print (#<arg> 0 0 . a))))) 4)) 10))
こうなる理由は，前者については，シンボルと大域変数の区別がないことが原因である。 解決にはおそらく新しい構文要素が必要である。 後者については，束縛変数はあくまで変数だから，本来，捕捉は回避可能である。 ここで捕捉が発生しているのは，ラムダ式をコンパイルするとき， もしも入れ子のラムダ式の仮引数名と，取り囲むラムダ式の仮引数名が一致したならば， (たとえ，その仮引数が変換済みであっても) 入れ子のラムダ式の仮引数として再解釈するからである。 この再解釈は，L2Lisp が現在の実装方法のもとで下記のように振る舞うために必要だが， Common Lisp や Emacs Lisp と同様の "マクロ引数の捕捉" を発生させる直接の原因になっている*3。
> (let ((a 10))
(let ((a 20))
(print a)))
20
20
はじめに 述べたように，この問題に対する Common Lisp 等での標準の解決方法は未インターン・シンボルの利用である。 しかし，L2Lisp は，前回 §3 で示したように シンボルをシンボル表 symbol の添え字の値として表現するから，本来，未インターン・シンボルは表現できない。 シンボルであることと，シンボル表に登録されていること (＝インターンされていること) が等価だからである。
そこで，新しくデータ型を作るのではなく， 先頭がシンボル *symbol*, 次が文字列，その次が任意の値である長さ３のリストを シンボル扱いして，未インターン・シンボルとして利用できるようにする。 リストの第３要素をシンボルの大域変数としての値とし，処理系の次の箇所でシンボル扱いする。
- 組込み関数 atom で (手続き ApplySymbol)
- ラムダ式の仮引数として (手続き Scan, 関数 ArgList)
- スペシャルフォーム setq で代入される大域変数として (手続き EvalSetqBody)
- 評価される大域変数として (手続き EvalTop)
このとき， 文字列から未インターン・シンボルを作る関数を l2init で次のように定義できる。*symbol* は自己評価的に定義されているから，クォートは不要である。 ここでは大域変数としての初期値を nil とした。
(defun make-symbol (s) (list *symbol* s nil))
例えば
> (setq a (make-symbol "poi")) (*symbol* "poi" nil) > a (*symbol* "poi" nil) > (eval (list 'setq a 4)) 4 > a (*symbol* "poi" 4)
未インターン・シンボルを次々と作る gensym 関数は次のように書ける。 48 は '0' に対する ASCII コードである。 L2Lisp の文字列の表現方法については前回 §1 の 12. を参照されたい。
(let ((counter 0))
(defun gensym ()
(setq counter (+ counter 1))
(let ((c counter) d4 d3 d2 d1)
(setq d4 (/ c 1000) c (- c (* d4 1000))
d3 (/ c 100) c (- c (* d3 100))
d2 (/ c 10) c (- c (* d2 10))
d1 c)
(make-symbol
(append "G" (mapcar (lambda (d) (+ d 48)) (list d4 d3 d2 d1)))))))
> (gensym) (*symbol* "G0001" nil) > (gensym) (*symbol* "G0002" nil) > (gensym) (*symbol* "G0003" nil)
これにより，前回 §6 の while マクロは， 実行時のラムダ式の入れ子を減らして，多少なりとも，より効率的に実現できる (どちらにしても while によるループは末尾再帰として最適化されるが， 今回の書き方ではループ内部に展開される各マクロ引数の実行効率が改善される)。
(defmacro while (test &rest body)
(let ((a (gensym)))
(list let (list a)
(list setq a
(list lambda ()
(list cond (cons test (append body (list (list a)))))))
(list a))))
マクロ展開で作るラムダ式の仮引数を，(gensym) で生成した新しい未インターン・シンボルで表しているから，変数捕捉は発生しない。
> (let ((a 0))
(while (< a 5)
(print a)
(setq a (+ a 1))))
0
1
2
3
4
nil
4. おわりに
ここでは L2Lisp にあった弱点の比較的小規模な改修による解決を報告した。 標準 Pascal によるプログラミングは， 特定の言語の機能に依存しすぎないデータ構造と処理方法を表すためには妥当だが， コマンド行引数を直接扱えないなど，そのままの実用化には困難がある。 この実装をひながたとして，さまざまな言語への移植を試みることは興味深い課題であろう。 小型ながらモダンな Lisp プログラミングが可能なスクリプティング・エンジンが成果として得られると期待される。
ただし，マクロ展開による変数捕捉に関して，現行の仕様は中途半端とも言える。 ２種類の変数捕捉とも Common Lisp や Emacs Lisp と互換にするか， あるいはどちらに対しても健全さを保つようにするか，いずれかにまとめることが望ましいかもしれない。
次回へつづく