遅延リスト遊び - Emacsで学ぶLazyな世界(前編)
（これは、Lisp Advent Calendar 2012の20日目の記事です。）
長いので前後編に分けます。お暇な方はどうぞ。
-*- delayとforce -*-
正格評価の言語でもクロージャがあれば遅延評価を行うことができます。計算式をクロージャに包んでしまえば、クロージャが呼び出されるまで中の式は評価されません。*1
先行評価
(+ 2 3) ;=> 5
遅延評価
(setq p (lambda () (+ 2 3))) ;=> 計算式を包んだクロージャ (funcall p) ;=> 5
遅延評価したい式をいちいちlambdaで包むのは面倒だし、lambdaだけでは「式を遅延評価させたい」という意図が伝わりません。ライブラリにしましょう。
(defmacro delay (expr) `(lambda () ,expr)) (defalias 'force 'funcall)
delayはマクロでなければなりません。関数だとlambda式に包む前に式（引数）が評価されてしまいます。それでは遅延評価になりません。*2
遅延させるdelayだけでなく、評価を実行する関数forceも作りました。見ての通りただのfuncallのaliasです。使い方は次のようになります。
(setq p (delay (+ 2 3))) ;=> 計算式を遅延する (force p) ;=> 5
シンプルな仕組みですがこのdelayとforceが遅延評価の基礎となります。
delayが作る「計算式を包んだクロージャ」のことをpromiseと呼びます。すぐには評価しないけど、いざとなれば評価値を生成してくれる「約束」のインスタンスです。
-*- 遅延評価と評価順 -*-
遅延評価の評価順がどうなるか確認してみます。こちらのHaskellのエントリー「遅延評価だけだと出力の順番が定まらない例」が例としてよさそうなので真似してみます。
;;引数をmessageバッファに出力したのち、引数を関数の戻値とする。 (defun debugPrint (x) (princ x) (princ " ") x) ;;先行評価 (defun main-eager () (let ((a (debugPrint 1)) (b (debugPrint 2))) (debugPrint (+ b a)) t)) ;;遅延評価 (defun main-lazy () (let ((a (delay (debugPrint 1))) (b (delay (debugPrint 2)))) (debugPrint (+ (force b) (force a))) t))
結果
(main-eager) ;=> 1 2 3 t (main-lazy) ;=> 2 1 3 t
遅延評価(main-lazy)の結果が上記リンク先のHaskellの例と同じ順序になっていますね。main-lazyのletで束縛されるa,bはpromiseなのでそのままでは関数「+」に適用できません。forceによって評価を強制する必要があります。強制の行われる順番が遅延評価の評価順となります。
-*- 評価のためのユーティリティ -*-
式の中にforceをいくつも挿入するのは面倒なので次のようなユーティリティを書いてみました。
;;promiseをforceしてからfに適用する。 (defun call-forces (f &rest args) (apply f (mapcar 'force args)))
これによりmain-lazyは次のように書き換えることができます。
(defun main-lazy() (let ((a (delay (debugPrint 1))) (b (delay (debugPrint 2)))) (debugPrint (call-forces '+ b a)) ;いちいちforceしなくていい t))
call-forcesはfuncallと同じように扱える関数ですが、関数適用の前に引数をすべてforceする点が異なります。
-*- メモ化するpromise -*-
遅延評価を実装するうえでメモ化は必須の概念ではありませんが、計算が参照透明である場合メモ化が有効なケースが多いです。多分。
ともかくpromiseにはメモ化の機能を持たせるのが常となっています。
;;メモ化版delay (defmacro delay (expr) `(lexical-let ((memo) (func (lambda () ,expr))) (lambda () (if func (prog1 (setq memo (funcall func)) (setq func nil)) memo))))
delayが作るpromiseが少し複雑になりました。これまで作っていたクロージャはfuncというレキシカル変数に束縛され、別のクロージャの中でfuncallされる二重構造になっています。funcはfuncall後にnilでクリアされるで「評価済みかどうか」のフラグにもなっています。*3
前節のmain-lazyに少し手を加えて、新delayを試してみましょう。
(defun main-lazy-and-memo () (let ((a (delay (debugPrint (+ 1 2)))) (b (delay (debugPrint (+ 10 20)))) (c (delay (debugPrint (+ 100 200)))) (debugPrint (call-forces '+ b a b a b a)) t)) (main-lazy-and-memo) ;=> 30 3 99 t
bとaの評価値を3個づつ合計(+ 30 3 30 3 30 3)して99。b,aはこの順にそれぞれ1回しか計算していません(debugPrintの表示が1回づつしかない)。また評価が不要なcは一度も評価されていません。メモ化と遅延評価は確かに働いています。
-*- Emacs Lispとクロージャ -*-
Emacs Lispは他の多くのLisp処理系とは異なり動的スコープでシンボルを解決します。そのため静的なレキシカル束縛を前提とするクロージャを作ることができません。この事は遅延評価の基本であるdelayとpromiseに影響を及ぼします。
次のようにletにより束縛した変数をdelayに適用しても、letのスコープ外でエラーになってしまいます。
(let ((x 2)) (setq p (delay (* x 10)))) (force p) ;=> Debugger entered--Lisp error: (void-variable x)
同じ名前のシンボルがグローバルにあった場合、エラーにはなりませんがpromiseが作られた時点の計算式とは異なる評価値になってしまいます。さらにメモ化が働くとおかしなことになります。
(let ((x 2)) (setq p (delay (* x 10)))) ;=> この時点では x は 2 (setq x 50) (force p) ;=> 500 スペシャル変数のxが反映される。 (setq x 1) (force p) ;=> 500 スペシャル変数は関係なくメモされた値がかえる。
これではforceで何が帰ってくるのか予想できません。しかもdelayに適用したはずのx=2の評価値は二度と得ることができません。関数からpromiseを返す場合も同様です。
(defun foo (a b) (delay (+ a b))) (setq p (foo 10 20)) (force p) ;=> Debugger entered--Lisp error: (void-variable a) (setq a 1 b 1) (force p) ;=> 2 (setq a 100 b 100) (force p) ;=> 2
明らかにおかしいですね。forceにより返される値はfooに適用している引数とは無関係な物になっています。この問題はclモジュールのlexical-letフォームを使うことで解決できます。
(require 'cl) (lexical-let ((x 2)) (setq p (delay (* x 10)))) (force p) ;=> 20 (setq x 50) (force p) ;=> 20 (setq x 1) (force p) ;=> 20 (defun foo (a b) (lexical-let ((a a) (b b)) (delay (+ a b)))) (setq p (foo 10 20)) (force p) ;=> 30 (setq a 1 b 1) (force p) ;=> 30 (setq a 100 b 100) (force p) ;=> 30
promiseが生成された時点の値（環境）を保持し後で評価された時に正しく値を返すためには、delayに適用する式の中の自由変数をすべてlexical-letで束縛しておく必要があります*4。 この点にさえ気を付ければEmacs Lispでも遅延評価を行うことはできます。
-*- たらい回し関数 -*-
遅延評価、メモ化ときたら、たらい回し関数(竹内関数)を書かないわけにはいきません。たらい回し関数は単純な構造の再帰関数ですが、非正格（関数の引数が遅延評価）なシステムにおいて計算量が桁違いに少なくなる特徴があり、Haskellの利点を語るときなどによく引き合いに出されます。Emacs Lispで書くとどうなるでしょう。
正格評価版たらい回し関数
(defun tarai (x y z) (if (<= x y) y (tarai (tarai (1- x) y z) (tarai (1- y) z x) (tarai (1- z) x y))))
遅延評価版たらい回し関数
;;再帰処理部（サブルーチン） (defun --lz-tarai (x y z) (lexical-let ((x x) (y y) (z z)) (if (<= (force x) (force y)) (force y) (--lz-tarai (delay (--lz-tarai (delay (1- (force x))) y z)) (delay (--lz-tarai (delay (1- (force y))) z x)) (delay (--lz-tarai (delay (1- (force z))) x y)))))) ;;処理開始部 (defun lz-tarai (x y z) (lexical-let ((x x)(y y)(z z)) (--lz-tarai (delay x) (delay y) (delay z))))
遅延評価版の再帰部のx,y,zはpromiseを期待しますが、ユーザインタフェースとなる処理開始部のx,y,zは数値です。この違いを吸収するために二段構えの構造にしました。delayでクローズしたい自由変数をlexical-let束縛しなければならないのはこの場合でも同様です。
たらい回し関数の再帰回数比較
x=12,y=5,z=0とした時の再帰回数*5を確認したところ次のような結果になりました。遅延評価版は「メモ化ありdelay」と「メモ化なしdelay」の両方で試しました。
[正格評価 ] 10,362,209回 [遅延評価(メモ化なし)] 253回 [遅延評価(メモ化あり)] 106回
遅延評価版は正格評価と比べ再帰１回あたりの処理内容にはオーバーヘッドがあります。しかしそんなものは再帰回数の差で消し飛んでしまい誤差にすらならない要素と言えます。メモ化の有無による差も倍以上あるのですが、それすら霞んでしまいますね。
-*- 判断するforce -*-
前節の「遅延評価版たらい回し関数」は「正格版」と比べ随分と複雑な構造でした。これはforceの引数に関数(promise)しか適用できない*6ことが原因の一つになっています。そこでforceの仕様を次のように拡張します。
1. 引数がpromiseならばpromiseに評価を強制する。 2. 引数がpromiseでなければ、引数をそのまま返す。
コードで書いた方が分かり易いかもしれません。つまり現状できないこれをやりたい。
(mapcar 'force (list (delay 1) 2 (delay 3) 4)) ;=> (1 2 3 4)
forceの仕様がこのようになるだけで、遅延評価版たらい回し関数はもう少しシンプルに書き直すことができます。
(defun lz-tarai (x y z) (lexical-let ((x x) (y y) (z z)) (if (<= (force x) (force y)) (force y) (lz-tarai (delay (lz-tarai (1- (force x)) y z)) (delay (lz-tarai (1- (force y)) z x)) (delay (lz-tarai (1- (force z)) x y))))))
前節のlz-taraiと比較すると分かりますが、関数が一つに纏まったのみならず再帰部のdelayが3つ減っています。これでも再帰回数は同じです。
では、上記の仕様を満たすためにforceを改造しましょう。例えばこんな感じになります。
(defstruct promise closure) (defmacro delay (expr) `(make-promise :closure (lexical-let ((memo) (func (lambda () ,expr))) (lambda () (if func (prog1 (setq memo (funcall func)) (setq func nil)) memo))))) (defun force (x) (if (promise-p x) (funcall (promise-closure x)) x))
forceにpromiseか否かを判断させるためには、delayの方で判断材料を仕込んでおく必要があります。これまでdelayで作っていたクロージャをそっくりそのまま構造体promiseに格納することで対応します。構造体を作れば自動的にmake-promise(コンストラクタ)、promise-closure(メンバアクセッサ)、promise-p(述語関数)が生成されます。述語関数があればforceでpromiseを判定するのは簡単です。
当然ながらここで作ったdelayとforceは実装の一例にすぎません。「On Lisp」には構造体とslotを使ったCLの例がありますし、schemeではdelayとforceは組み込み関数として存在しsrfi等で長年議論されているようです。ClojureのdelayはDelayというJavaのクラスのインスタンスに計算をクローズするマクロで、forceはDelayオブジェクトのforceメソッドを呼ぶラッパーになっています。
なんにせよクロージャを大量に使用する遅延評価システムはコストの高い計算になりがちです。実用レベルにするためには処理系による最適化は必須なんでしょうね。
-*- 続くよ -*-
後編は、遅延リストについてです。
*1:Emacs Lispの無名関数は厳密にはクロージャとは言えませんが、それは取りあえず置いておきましょう。
*2:逆に言うと、Lispにはマクロがあるからこそdelayのようなフォームが作れると言えます。
*3:nilクリアで束縛を断ち切ることで不要なfuncがGCされる可能性もあるかもしれません。Emacs LispのGCはよくしりませんが。
*4:スルーしましたがメモ化するpromiseの節で既にlexical-letを使っています。メモ化もまたレキシカル変数が必須なので動的スコープでは実現ができません。そもそもpromise自体の実装がレキシカル変数無しには不可能です。
*5:再帰部のトータルのコール回数です。再帰の深さではないのでご注意ください。
*6:forceは単なるfuncallのaliasですからね
もう一度、関数の引数をlexical-letするマクロ
昨日の「関数の引数をlexical-letするマクロ」が中途半端だったので、拡張してみた。
組み込みdefunと, clモジュールのdefun*のそれぞれに対応したものを作成。ヘルプで見たときにdocstringの位置が明示されるように、引数の調整もしました。
(require 'cl) (defmacro --impl-defun-lx (form name args docstr body keywords) (multiple-value-bind (docstr body) (cond ((null docstr) (values nil nil)) ((stringp docstr) (values docstr body)) (t (values nil (cons docstr body)))) (let* ((--pred (lambda (x) (memq x keywords))) (--make-binding (lambda (a) (cond ((not (listp a)) `((,a ,a))) ((> 3 (length a)) (let ((a (car a))) `((,a ,a)))) (t (let ((a (car a)) (b (caddr a))) `((,a ,a) (,b ,b))))))) (--lx-bindings (mapcan --make-binding (remove-if --pred args))) (--body (cond ((null body) nil) ((null --lx-bindings) body) (t `((lexical-let ,--lx-bindings ,@body)))))) (append `(,form ,name ,args) (when docstr `(,docstr)) --body)))) (defmacro defun-lx (name args &optional docstr &rest body) "define static lexical scope args function by `defun'. " `(--impl-defun-lx defun ,name ,args ,docstr ,body (&optional &rest))) (defmacro defun*-lx (name args &optional docstr &rest body) "define static lexical scope args function by `defun*'" `(--impl-defun-lx defun* ,name ,args ,docstr ,body (&optional &rest &key &allow-other-keys &aux &body)))
◆何が嬉しいのか(追記 2012/12/12)
defunやdefun*でクロージャーを作るとき、たとえば次のコード。
(setq x 1000 y 500) (defun* make-counter (x &optional (y 1)) (lambda () (prog1 x (setq x (+ x y))))) (let ((a (make-counter 1)) ;初期値1 増加量は規定(=1)のカウンタ (b (make-counter 1 10))) ;初期値1 増加量10のカウンタ (mapcar 'funcall (list a a a b b b))) ;;=> (1000 1500 2000 2500 3000 3500) ;期待通りにならない。
a, b はfuncallの度にカウントアップする互いに独立したカウンタのつもりなのですが期待通りにいきません。defun*の引数が動的スコープのためカウンタが参照するx,yはmake-counterの仮引数ではなくグローバルなx,yであることが原因です。
そこでdefun*の代わりに今回作ったdefun*-lxを使うとグローバルではなく、クロージャー毎に独立した局所変数を参照するようになります。
(setq x 1000 y 500) (defun*-lx make-counter (x &optional (y 1)) (lambda () (prog1 x (setq x (+ x y))))) (let ((a (make-counter 1)) (b (make-counter 1 10))) (mapcar 'funcall (list a a a b b b))) ;;=> (1 2 3 1 11 21) ;; 期待通り！
◆注意
レキシカルになるのはあくまでも関数の引数だけだという点に注意しください。
関数内の自由変数がすべて静的レキシカルスコープになるわけではありません。
関数の引数をlexical-letするマクロ
◎続編を書きましたのでそちらもよろしく。
Emacs Lispを書いていると関数の引数が動的スコープで困ることがある。で、書いてみたマクロ
(require 'cl) (defmacro* defun% (name args &rest rest) (let* ((docstr (when (and rest (stringp (car rest))) (car rest))) (body (if docstr (cdr rest) rest)) (pred (lambda (x) (string-prefix-p "&" (symbol-name x)))) (args- (remove-if pred args)) (args- (mapcar (lambda (a) `(,a ,a)) args-))) (append `(defun ,name ,args) (when docstr `(,docstr)) `((lexical-let ,args- ,@body)))))
たとえば
(defun% foo (x y z) (+ x y z))
と書くと
(defun foo (x y z) (lexical-let ((x x) (y y) (z z)) (+ x y z)))
という風に展開してくれる。
制限事項
- &optional はデフォルト値指定不可（elispだとそもそも無理？）
&key はサポートしてない。
追記(2012/12/11)
emacs lispのdefunは、&keyも&auxもサポートしていませんでした。&restと&optionalがサポートされていますが、&optionalはデフォルト値は指定できません。これらを使いたいときはclモジュールで定義されているマクロdefun*を使いましょう。ただしdefun*の引数もdefun同様に動的スコープみたいです。
