遅延リスト遊び - 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ですからね
遅延リスト遊び - Emacsで学ぶLazyな世界(後編)
前編に引き続き、使うのはEmacs Lispです。
-*- 遅延リスト -*-
ものすごく基本的なことを書きます。
二つのオブジェクトのペアを作る関数consがあります。このペアはドット対とも呼ばれますが、cdr部がnilの場合、真のリスト*1になります。またcdr部が真のリストであるペアもまた真のリストになります。
(setq c (cons 1 2)) ;=> (1 . 2) ;ドット対 (car c) ;=> 1 car部 (cdr c) ;=> 2 cdr部 (setq ls (cons 1 (cons 2 (cons 3 nil)))) ;=> (1 2 3) ;リスト (car ls) ;=> 1 (cdr ls) ;=> (2 3) (car (cdr ls)) ;=> 2 (car (cdr (cdr ls)) ;=> 3 (car (cdr (cdr (cdr ls)))) ;=> nil
consによってリストが構築され、car, cdrでリストを分解できます。多くのリスト操作関数はこの基本となる３関数により実装できます。
遅延リストもこれとよく似た仕組みになります。まずは遅延リスト用の基本３関数を作りましょう。
(defmacro lz-cons (a b) `(cons ,a (delay ,b))) (defalias 'lz-car 'car) (defun lz-cdr (s) (force (cdr s)))
ここではプレフィックスにlzを付けて遅延(lazy)の意味としています。lz-carはただのcar, lz-cdrはcdr部をforceする関数です。
lz-consはconsに展開されますが、cdr部はdelayされます。delayが作るのはnilでもリストでもなくpromiseというオブジェクトですからこれで構築されるのものは、Lisp的にはただのドット対です。
では遅延リストを作ってみます。
(lz-cons 1 (lz-cons 2 (lz-cons 3 nil)))))
lz-consはマクロなのでEmacsのバッファでこの式を評価するとマクロ展開後評価されます。lz-consの中のconsが実行されるわけですね。
(1 . [cl-struct-promise (lambda (&rest --cl-rest--) (apply '(lambda (G154156 G154157) (if (symbol-value G154156) (prog1 (set G154157 (funcall (symbol-value G154156))) (set G154156 nil)) (symbol-value G154157))) '--func-- '--memo-- --cl-rest--))])
一番外側のlz-consの展開されたものだということは分かりますが、内側の2つのlz-consはどこにいってしまったんでしょうか？ よくわかりませんが、これがちゃんとリストのように扱えるのだから不思議です。
(setq lz (lz-cons 1 (lz-cons 2 (lz-cons 3 nil)))) ;=> 1,2,3を要素にもつ遅延リスト (lz-car lz) ;=> 1 (lz-cdr lz) ;=> 2,3を要素にもつ遅延リスト (lz-car (lz-cdr lz)) ;=> 2 (lz-car (lz-cdr (lz-cdr lz))) ;=> 3 (lz-car (lz-cdr (lz-cdr (lz-cdr lz)))) ;=> nil
冒頭のリスト操作と同じ結果になっています。
リスト構築関数
lz-consを使って、遅延リストを作る関数を作ってみましょう。
(defun lz-repeat (x) "引数が無限につづく遅延リスト" (lexical-let ((x x)) (lz-cons x (lz-repeat x)))) (defun lz-iota (n m) "初期値n, ステップmの無限等差数列" (lexical-let ((n n) (m m)) (lz-cons n (lz-iota (+ n m) m))))
いきなり無限リスト構築関数が二つ。無限リストは終了判定がいらないので簡単に作れるんですよね。どちらも再帰関数っぽいですが、再帰はdelay*2されるので実際は再帰呼び出しにはなりません。ドット対を返す関数にすぎません。
(lz-repeat "a") ;=> ("a" . [cl-struct-promise (lambda (... (lz-iota 1 2) ;=> (1 . [cl-struct-promise (lambda (...
でもリストのようにふるまいます
(setq lz1 (lz-repeat "a")) (lz-car lz1) ;=> "a" (lz-car (lz-cdr lz1)) ;=> "a" (lz-car (lz-cdr (lz-cdr lz1))) ;=> "a" (setq lz2 (lz-iota 1 2)) (lz-car lz2) ;=> 1 (lz-car (lz-cdr lz2)) ;=> 3 (lz-car (lz-cdr (lz-cdr lz2))) ;=> 5
遅延リスト、無限リストができました。
-*- 遅延リスト操作関数 -*-
遅延リストの基本はこれだけです。あとは遅延リストを操作するための関数を黙々と作る作業になります。まずはtakeがほしいですね。
(defun lz-take (n lz) (when (and lz (> n 0)) (lexical-let ((n n) (lz lz)) (lz-cons (lz-car lz) (lz-take (1- n) (lz-cdr lz)))))) (defun lz-take-while (pred lz) (when (and lz (funcall pred (lz-car lz))) (lexical-let ((pred pred) ((lz lz))) (lz-cons (lz-car lz) (lz-take-while pred (lz-cdr lz)))))) (defun lz-drop (n lz) (do ((n n (1- n)) (lz lz (lz-cdr lz))) ((or (>= 0 n) (null (cdr lz))) lz))) (defun lz-drop-while (pred lz) (do ((lz lz (lz-cdr lz))) ((or (not (funcall pred (lz-car lz))) (null (cdr lz))) lz)))
遅延リストからn件切り出すlz-take, predが成立する限り取り出すlz-take-while, ついでにdropも作りました。dropは遅延評価ではない手続ループで作りました。
あと遅延リストを普通のリストに変換する関数もあった方が結果の確認に便利ですね。ついでなので相互変換関数を作ります。
(defun lzlist-to-list (lz) (do ((lz lz (lz-cdr lz)) (ls nil (append ls (list (lz-car lz))))) ((null (cdr lz)) ls))) (defun list-to-lzlist (ls) (when ls (lexical-let ((ls ls)) (lz-cons (car ls) (list-to-lzlist (cdr ls))))))
リスト操作関数と相性のよいスレッドマクロと、部分適用関数の短縮名も用意しましょう。そうしましょう。
(defmacro ->> (&rest exprs) (when exprs (reduce (lambda (acc e) (if (listp e) `(,@e ,acc) `(,e ,acc))) exprs))) (defalias 'pa$ 'apply-partially)
つかってみよう。
(->> (lz-iota 0 7) ; 7の倍数の (lz-drop-while (pa$ '> 5000)) ; 5000未満を捨てた後 (lz-take 5) ; 5件を取得して lzlist-to-list) ; リストにする ;;=> (5005 5012 5019 5026 5033)
5005って7の倍数なんですね。できてます！
次はunfoldを作ってみよう
(defun lz-unfold (endp elem next seed) (when (not (funcall endp seed)) (lexical-let ((endp endp) (elem elem) (next next) (seed seed)) (lz-cons (funcall elem seed) (lz-unfold endp elem next (funcall next seed))))))
unfoldの引数で変化するのはseedだけ。それ以外は常に同じ関数を使います。ということは毎回引数渡すのは無駄ですよね？ うまくレキシカルスコープを使えないでしょうか？
(defun lz-unfold (endp elem next seed) (lexical-let ((endp endp) (elem elem) (next next)) (labels ((rec (s) (when (not (funcall endp s)) (lexical-let ((s s)) (lz-cons (funcall elem s) (rec (funcall next s))))))) (rec seed))))
ローカル関数recでsの値を変えながら遅延再帰しています。引数が１つだから呼び出しオーバーへッド少ない...のかな？ この手法はいろいろなところで使えそうです。
フィボナッチ数列を作ってみましょう。
(->> (lz-unfold (lambda (_) nil) 'cadr (lambda (ls) (list (apply '+ ls) (car ls))) '(1 0)) (lz-take 20) lzlist-to-list) ;;=> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
おお！できてますね。これは楽しい。
きりがないのでこのへんでやめておきますが、他にもfilter, mapcar, zip, reduce, 素数列生成...といくらでも考えられますね。
はっきり言って、遅延評価はオーバヘッドが大きく特にEmacs Lispではクリティカルな場所で使うことは難しいと思います。でも、末尾再帰最適化がないEmacs Lispですから、スタックを食いつぶさない遅延再帰が役立つ場面はありそうな気がするのですが、どうでしょうかね...
-*- おわりに -*-
今月の初めごろとあるブログの記事へのtwitter上での反応をきっかけに「遅延評価」について考える機会がありました。普段Clojureで遅延評価の恩恵を受けているわりに突っ込んで理解してないな気づき、そしてこのエントリができました。
どうせやるなら最初から遅延評価を持っているClojureではなく、あえてEmacs Lispでを選びましたが勉強になりました。動的スコープのEmacs Lispだからこそレキシカルの有難さ、そしてレキシカルスコープが遅延評価においてどの部分で役立っているかなんとなく見えた気がします。
