Common Lispで遅延評価を作って遊ぶ（1）
目標：無限長数列
遅延評価というものを始めて耳にしたのはHaskellの入門書*1ですが、印象的だったのはやはり"[1..]"、ご存知無限リストですね。CやC#の世界で平和に暮らしていた人間にとっては中々衝撃的でした。
ということで、Common Lispで遅延評価（Lazy Evaluation）を使って無限長数列で遊ぶことを目標にします。まず今回は、基本的な遅延評価ライブラリから無限長数列を作るところまで。
遅延評価ライブラリ
Common Lispは遅延評価ベースな言語…では全然無いですが、クロージャとマクロを使って20～30行もあればベース（lazy, force, lcons, lcar, lcdr）ができあがります。こうして世の中で何千何万と作られたと思われる遅延評価ライブラリ群*2にまた一つのライブラリcl-lazy（名前衝突が起きている気しかしない）が加わりました。
一応cl-lazyのインストール方法ですが、quicklispによるインストールに対応しているため、ql:*quicklisp-home*配下にgit cloneした上で、REPLから(ql:quickload :cl-lazy)してください*3。Clozure CL上でしかテストしていないので他では動かないかもしれませんが。また、下記の例はuse-packageをした想定で、作成した関数の呼び出し時にはパッケージ名を省略しています。
lazyとforce
色々試行錯誤した結果、結局基礎部分はLand of Lispに載っているものと同じようなものにしかなりませんでした。ということで詳しく書いても仕方がないので簡潔に。
(defmacro lazy (&body body) (let ((value (gensym)) (evaluated (gensym))) `(let ((,value nil) (,evaluated nil)) (lambda () (unless ,evaluated (setf ,value (progn ,@body)) (setf ,evaluated t)) ,value)))) (defun force (lazy-value) (funcall lazy-value))
lazyで包んだ処理本体bodyはこの時点では単に無名関数として返されるので計算は行われません。force（funcall）すると始めて計算されてvalueに計算結果が保存されます。二回目以降のforceでは単にvalueが返されるだけので高速、という代物です。
Land of Lispとの差分として、evaluatedを用意しています。valueを直接unlessに渡して判定すると計算結果がnilだった時に何度も評価されてしまうため、なのですがその稀？な機会のためにメモリ使うのはどうなの、と聞かれると正直微妙です…。
使用例。10を返すだけです。一緒に置いたprintの動作を見ると、最初のforceの時だけ評価されていて二回目は保存された値を返しているだけである様子が分かるかと思います。
CL-USER> (defparameter x (lazy (print 'first) 10)) X CL-USER> (force x) FIRST 10 CL-USER> (force x) 10
lcons, lcar, lcdr
数列を作るということで、リスト操作がないことには始まりません。リスト作成用にlconsを、リストから値を取り出すためにlcar, lcdrを作成します。それぞれCommon Lisp標準のcons, car, cdrに対応します。
(defmacro lcons (a b) `(lazy (cons ,a ,b))) (defmacro lcar (l-lst) `(if (null ,l-lst) nil (car (force ,l-lst)))) (defmacro lcdr (l-lst) `(if (null ,l-lst) nil (cdr (force ,l-lst))))
lconsのlazyをどこに置くか試行錯誤したのですが、結局Land of Lispと同じに落ち着きました。やっぱり対称性って大事ですね。不満な点として(lcar (lcons a b))とした時にaだけで十分なのにa, b両方評価されてしまうということがあるのですが、結局bにはlazyな何かが入ることがほとんどなので、影響はさほど大きくないと判断しました。
lcar, lcdrについては、car, cdrと同様に利用するため、値がnilの場合の対応をしました。
以下の使用例から、lcons, lcar, lcdrがそれぞれcons, car, cdrに対応して使えていることが分かるかと思います*4。なお、紛らわしいのでlet式の評価値NILの表示は省略しています。
; (1 2) という2要素のリストの作成と操作 CL-USER> (let ((x (cons 1 (cons 2 nil)))) (print (car x)) (print (car (cdr x))) (print (car (cdr (cdr x)))) (print (car (cdr (cdr (cdr x)))))) 1 2 NIL NIL CL-USER> (let ((x (lcons 1 (lcons 2 nil)))) (print (lcar x)) (print (lcar (lcdr x))) (print (lcar (lcdr (lcdr x)))) (print (lcar (lcdr (lcdr (lcdr x)))))) 1 2 NIL NIL
lnth
一応上記で最低限だと思いますが、リストの後ろにある値を取り出すためにlcdrを何個も重ねるのはさすがに面倒なので、lnthも作っておきます。標準のnthと同じく(lnth 2 lst)のようにするとlstの第2要素（0始まり）が取れます。0未満を渡した時の動作が違います（エラーにならない）が、こだわらないことにしました。
(defun lnth (n l-lst) (if (<= n 0) (lcar l-lst) (lnth (1- n) (lcdr l-lst))))
リスト作成を簡略化するためのllist（標準のlistに対応）も作りましたが、今回の範囲ではlconsで十分なため次回に。
無限長数列
偶数列を作る
本題です。例として偶数列anができたとして、以下のように操作できることが目標です。
(lnth 0 an) -> 0 (lnth 1 an) -> 2 (lnth 2 an) -> 4 ... (lnth 50 an) -> 100 ...
まずイメージを考えます。無限長偶数列を生み出す関数f[n]があったとします。f[n]は実際にアクセスするまで評価されない関数のような何かです。下に、コロンの左側に操作、右側に操作後のanの状態（あくまでイメージ）を書きます。関数f[n]が「第n要素の値」と「以降の値を生み出すf[n+1]」の組み合わせで段々と置き換えられていく様子が分かる…ように書けているといいのですがどうでしょう。
(defvar an f[0]): f[0] (lnth 0 an) : (0 f[1]) # f[0]が評価されて0とf[1]の組みができる (lnth 1 an) : (0 (2 f[2]) # f[1]が評価されて2とf[2]の組みができる (lnth 2 an) : (0 (2 (4 f[3])) # f[2]が評価されて4とf[3]の組みができる
アクセスするまで評価されないf[n]…、ということは遅延評価ですね。右側に書いたanの各状態をもう少しLispのコードらしく書き下すと以下のようになります。
(f 0) (lcons 0 (f 1)) (lcons 0 (lcons 2 (f 2))) (lcons 0 (lcons 2 (lcons 4 (f 3))))
ということで、(f n)を(lcons (* n 2) (f (+ n 1)))を返す関数として定義すれば良さそうです。実際、以下のように意図通り動くことがわかります。気になる部分として、評価順序の問題か警告が出てしまっていますね…。f内でlabelsを使って適当な内部関数を定義して呼び出すようにすると、警告を出さずに定義できます。まあ見づらいのでここでは置いておきます。
CL-USER> (defun f (n) (lcons (* n 2) (f (+ n 1)))) ;Compiler warnings : ; In an anonymous lambda form inside F: Undefined function F F CL-USER> (defparameter an (f 0)) AN CL-USER> (lnth 0 an) 0 CL-USER> (lnth 1 an) 2 CL-USER> (lnth 2 an) 4 CL-USER> (lnth 50 an) 100
以上で論理上無限の長さを持つ偶数列を作成することができました。
遅延評価（Lazy Evaluation）になっていることを確認する
以下のようにして、メモリアロケーションに注目すると、遅延評価（Lazy Evaluation）であることが簡単に確認できます。一回目の(lnth 50 b)の呼び出しでは6.5KB程度のメモリが割り当てられています（リスト作成のため）が、二回目は計算された値を読み出しているだけであるため、メモリの割り当ては発生していません。
CL-USER> (defparameter b (f 0)) B CL-USER> (time (lnth 50 b)) (LNTH 50 B) took 20 microseconds (0.000020 seconds) to run. During that period, and with 2 available CPU cores, 0 microseconds (0.000000 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode 6,528 bytes of memory allocated. 100 CL-USER> (time (lnth 50 b)) (LNTH 50 B) took 11 microseconds (0.000011 seconds) to run. During that period, and with 2 available CPU cores, 0 microseconds (0.000000 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode 100
ついでにフィボナッチ数列を作ってみる
数列といえばフィボナッチ数列。作ってみます。無限長偶数列との主な差分は引数が2つになることぐらいです。引数の足し算を二度しているのは少々無駄ですが目をつむります。
CL-USER> (defun fib (a b) (lcons (+ a b) (fib b (+ a b)))) ;Compiler warnings : ; In an anonymous lambda form inside FIB: Undefined function FIB FIB CL-USER> (defparameter x (fib 0 1)) X CL-USER> (dotimes (i 7) (print (lnth i x))) 1 2 3 5 8 13 21 NIL
フィボナッチ数列…と言い切っていいかもしれませんが、初期値の0と1が消えてしまっていますね。次のように後から初期値を付け加えればなんとか…。
CL-USER> (defparameter y (lcons 0 (lcons 1 (fib 0 1)))) Y CL-USER> (dotimes (i 7) (print (lnth i y))) 0 1 1 2 3 5 8 NIL
次回へ
なんとか無限数列ができました。偶数列やフィボナッチ数列だけでなく色々作れそうですね。
ただ、上記の関数定義を見ても、リスト（コンスセル）を作成しているだけで、いまいち数列を作っているという感じがしません。一回作り方を忘れるとあれlcons一個でいいんだっけ、どこにつけるんだっけ、となること請け合いです。少なくとも自分は（lconsの定義が右往左往していたせいもありますが）ドハマりしてました。さらに言うと、フィボナッチ数列のように初期値だけ後から付け加えるというのもしっくり来ません。
そんなわけで、次回はマクロを使ってもう少し直感的な数列作成方法を模索してみたいと思います。
シリーズリンク
- 第一回：Common Lispで遅延評価を作って遊ぶ（1） - eshamster’s diary
- 第二回：Common Lispで遅延評価を作って遊ぶ（2） － 数列生成マクロ - eshamster’s diary
- 第三回
- 付録：リードマクロ入門、の10分の1歩ぐらい後か前 - eshamster’s diary
- 第四回：Common Lispで遅延評価を作って遊ぶ － 数列生成リードマクロ - eshamster’s diary
*1:今でも入門レベルで知識が止まってます…。色々と印象深かったのでいずれまた勉強し直したいです。
*2:実際、quicklisp（Common Lispのライブラリマネージャ）を「lazy」で検索してみるとすでに誰かが作ったそれらしいものが登録されています。が、お遊びなので堂々と再発明します。
*3:参考：Modern Common Lisp: 第6回 Common Lispライブラリを書く
*4:setfなどset系に対応できていませんが、いかにも関数型な世界で値を書き換えようなんて野暮というものです、と逃げます
