付録: 簡単な遅延評価のプログラム例
2008.4.4 - 2008.4.10 (鈴)1. はじめに
L2Lisp は Scheme にならってスペシャルフォーム
(delay expression)
で任意の式 expression の約束 (promise) を作る。
そして，著者が知る限りのすべての Scheme 実装と異なり，
組込み関数などで約束の値が必要とされたときは自動的に約束が果たされ
(be delivered)，式が評価される。
L2Lisp では (delay expression) は
~expression と略記できる。
今のところ，
L2Lisp の標準の事前定義のうち (range m n)
関数以外は約束を作らない。
range と delay と ~ を使わない限り，
L2Lisp は遅延評価と無関係な普通の Lisp として使用できる。
しかし，その場合，言語の重要な能力が生かされない。
そもそも遅延評価の有用性について，一部のコミュニティを除き，一般に広く理解されているとは言いがたい。
ここでは，L2Lisp の遅延評価機能を活用した簡単なプログラムをいくつか紹介しよう。
まず range を使って，約束の扱いに少し慣れておこう。
(defun range (m n) (cond ((< m n) (cons m ~(range (+ m 1) n)))))
(range 1 10) は Python の range(1, 10) と同じく
1 から 9 までの数のリストを作成する。ただし，遅延評価的に作成する。
> (setq a (range 1 10)) (1 . #<promise:(range (+ #0:0:m 1) #0:1:n)>)
作成当初の値は，cons 演算の結果としての
1 と #<promise:(range (+ #0:0:m 1) #0:1:n)> の cons ペアである。
容易に想像できるようにペアの cdr 値は，式
(range (+ #0:0:m 1) #0:1:n) の約束である。
#0:0:m はローカル変数 m を「コンパイル」した結果であり，
現在地からの相対フレーム番号 0, フレーム内オフセット 0, コンパイル前の名前 m
であることを意味する。
同様に #0:1:n はローカル変数 n のコンパイル結果
(フレーム内オフセット 1) である。
range の定義から分かるように，cdr の約束をかなえたとき，
整数と新たな約束の cons ペアが得られる。
cdr の約束をかなえるには，どんなつまらないものでもよいから計算結果を得るために
cdr の値を必要とするような演算をすればよい。
> (null (cdr a)) nil > a (1 2 . #<promise:(range (+ #0:0:m 1) #0:1:n)>)
L2Lisp の組込み関数はすべて，引数として与えられた約束を， 組込み関数の実行に必要なだけ果たすから，組込み関数から組み立てられた 関数も，再帰的な帰結により，引数の約束を必要なだけ果たす。
好きなようにリストの約束を果たさせるには (nth n list) が都合よい。
これは下記のように事前定義された関数であり，
Emacs Lisp や Common Lisp の同名の関数と同じく，list のゼロから数えて
n 番目の要素を返す。
これ自体はどこにも遅延評価的なところのない 普通 の関数であることに注意しよう
(
この普通さこそが他に見られない L2Lisp の特長である。
何のことを言っているかまだ分からないと思うが，
今はただありのままに起こっていることを見てほしい)。
(defun nth (n list) (while (< 0 n) (setq list (cdr list)) (setq n (- n 1))) (car list))
ゼロから数えて 4 番目，つまり 1 から数えて 5 番目の要素を見てみよう。
> (nth 4 a) 5
このとき，変数 a の値をみると 1 から 5 までかなえられている。
残りの値は (nth 4 a) の計算で必要とされなかったから，
約束のままである。
> a (1 2 3 4 5 . #<promise:(range (+ #0:0:m 1) #0:1:n)>)
mapcar でリストの全要素になにか関数を適用したときは， リストのすべての cdr 値が必要とされるから，最後の約束まで果たされる。
> (mapcar identity a) (1 2 3 4 5 6 7 8 9)
このとき，a は 1 から 9 までのリストと同値である。
> a (1 2 3 4 5 6 7 8 9)
range についていえば，その真価は，dolist マクロ
(これも Emacs Lisp 等と同様のものとして事前定義されている)
のようにリストの car 値をループごとにどんどん捨てていく場合に発揮される。
このとき，どんなに広大な値域であってもメモリ上に一度に占めるのは，
car である一つの整数と cdr である一つの約束だけであり，効率が良い。
> (dolist (i (range 0 5))
(print i))
0
1
2
3
4
nil
>
もしも Python について知っているならば，(range m n)
の振舞が Python 3.0 のジェネレータ化された range(m, n)
と似ていることに気付くはずだ。
末尾再帰ではないのに動作時にスタックをうずたかく積み上げないことを含め，
遅延評価はジェネレータと共通点がある。
しかし，range は遅延評価の最もトリビアルな応用にすぎない。
ジェネレータにない遅延評価の利点は，それがデータ構造の一部として 自然に織り込まれる点である。 もしも Python や C# のジェネレータに慣れ親しんでいるならば， 次節からのプログラムでその点によく注意しよう。
この例は簡単だから，まだ気にならないが，少し複雑な式になると，約束の文字列表現
#<promise:expression>
が煩雑に思えてくるかもしれない。下記を実行すると，L2Lisp の Ruby
プログラムが変更され，約束の文字列表現が # １文字になる。
(ruby-eval (concat "module L2Lisp\n" " class Promise\n" " def inspect; (@link == NONE) ? @exp.inspect : '#' end\n" " end\n" "end"))
これを ruby-hack.l というファイル名で保存し，
L2Lisp.rb のコマンド行引数の先頭に含めるか，
スクリプトまたは対話セッションの Lisp 式として (load "ruby-hack.l")
を実行するとよい。
> (load "ruby-hack.l") nil > (range 1 10) (1 . #)
2. フィボナッチ数列
フィボナッチ (Fibonacci) 数列
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
は文献 [1] p.191 によれば，Haskell で次のように簡潔に定義できる。
fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
L2Lisp ではこれを次のように直訳できる。 ただし，ここでは動作確認のためゼロから数えて 33 番目の値を印字する。
;; from Haskell (defun zipWith (f x y) (if (or (null x) (null y)) nil (cons (f (car x) (car y)) ~(zipWith f (cdr x) (cdr y))))) (setq fibs (cons 1 (cons 1 ~(zipWith + fibs (cdr fibs))))) (print (nth 33 fibs)) ; => 5702887
fibs.l というファイルとして保存し，実行してみよう。 繰返し的ではなく再帰的 (末尾再帰ではない)，純関数的なプログラムであり， 一見すると非常に効率が悪そうだが，実際の計算は瞬時に終わる。
$ time ./L2Lisp.rb fibs.l 5702887 real 0m0.159s user 0m0.145s sys 0m0.015s $
対話セッションでいろいろと試してみよう。
この数列は果てることがない潜在的に無限のリストであり，
nth で特定の箇所の値を問えば，
(もしまだ現実化されていなければ) 先頭からその箇所まで自動的に現実の数列としてかなえられる。
$ ./L2Lisp.rb ruby-hack.l fibs.l - 5702887 > fibs (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 570 2887 . #) > (nth 50 fibs) 20365011074 > fibs (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 570 2887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 4 33494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 125862 69025 20365011074 . #) >
他の関数も試してみよう。 mapcar のようにリストの最後まで参照しようとする関数でない限り， どれも破綻なく動作することが分かる。
Lisp でフィボナッチ数列をこのように定義したのは，これが最初の試みではない。 文献 [2] と [3] では Scheme による実装例が与えられている。 しかし，それらの例では car, cdr などの基本的なレベルから開始して 遅延評価用の関数群を一式用意している。 その Scheme 実装は，必要ならば黙って約束を果たすということをしないから， 遅延評価的なデータに対して，普通 に定義された関数の多くが役に立たない (逆に言えば，普通に定義した関数を遅延評価的なデータにそのまま適用できることが L2Lisp の特長である)。 文献 [3] の例を下記に示す。 ここで使われている force は陽に約束を果たす関数である。
(define (lcar lis) ;; lazy car
(car (force lis)))
(define (lcdr lis) ;; lazy cdr
(cdr (force lis)))
(define (ltake lis n) ;; lazy take
(if (<= n 0) '() (cons (lcar lis) (ltake (lcdr lis) (- n 1)))))
(define (lmap proc l1 l2) ;; lazy map
(if (null? l1)
'()
(cons (proc (lcar l1) (lcar l2))
(delay (lmap proc (lcdr l1) (lcdr l2))))))
;; lazy list of fibonacci numbers
(define fibs (list* 1 1 (delay (lmap + fibs (cdr fibs)))))
;; take a look
(ltake fibs 20)
いちいち基本レベルから道具立てをそろえる必要があるプログラミング技法を 日常的な問題解決の手段にしようと考える人はまずいない。 おそらく，このことが，本来，同じ関数型言語でありながら， 文献 [4] などで強力に有用性が主張されてきた「遅延評価」 が Lisp コミュニティから概ね等閑視されてきた理由だといってよいだろう。
3. ニュートン-ラプソン法による平方根
遅延評価の有用性を主張する文献 [4] から，やさしい例として 4.1 節 「ニュートン-ラプソン法による平方根 」を取り上げよう。 下記のように L2Lisp に直訳できる。
;; 「なぜ関数プログラミングは重要か」から ;; http://www.sampou.org/haskell/article/whyfp.html (defun abs (a) (if (< a 0) (- a) a)) (defun next (N x) (/ (+ x (/ N x)) 2.0)) (defun repeat (f a) (cons a ~(repeat f (f a)))) ;; (repeat f a) => (a (f a) (f(f a)) (f(f(f a))) ...) (defun within (eps x) (let ((a (car x)) (b (cadr x)) (rest (cddr x))) (if (<= (abs (- a b)) eps) b (within eps (cons b rest))))) (defun sqrt (a0 eps N) (within eps (repeat (lambda (x) (next N x)) a0))) (print (sqrt 1.0 0.001 10)) ;;; => 3.162… (defun relative (eps x) (let ((a (car x)) (b (cadr x)) (rest (cddr x))) (if (<= (abs (- a b)) (* eps (abs b))) b (relative eps (cons b rest))))) (defun relativesqrt (a0 eps N) (relative eps (repeat (lambda (x) (next N x)) a0))) (print (relativesqrt 1.0 0.001 10)) ;;; => 3.162…
ファイル newton-sqrt.l として保存し，実行してみよう。 このプログラムでは動作確認用に二つの方法で 10 の平方根を求めている。
$ ./L2Lisp.rb newton-sqrt.l 3.16227766517567 3.16227766517567 $
おそらく，多くの人にとってこのプログラムの難所は無限リストを生成する
(repeat f a)
だろう。対話セッションで試せば，どんな関数なのか勘がつかめるはずだ。
例えば，関数引数 f として値を 2 倍にする (lambda (n) (* 2 n))
を，初項の値 a として 1 を与えてみると，
> (setq s (repeat (lambda (n) (* 2 n)) 1)) (1 . #) > (nth 10 s) 1024 > s (1 2 4 8 16 32 64 128 256 512 1024 . #) >
確かに
(a (f a) (f(fa))
(f(f(f a))) …)
というリストが生成されることが分かる。
ここではこの repeat を漸化式 next
に適用して，遅延評価的なリストとして近似値の数列を生成している。
一方，within や relative
は，数列生成とは全く独立して，生成された最後の２項の値から停止条件を定めている。
最近の Python や C# のジェネレータ等により状況が改善されているとはいえ，
もしも遅延評価を利用しなければ，普通
このようなモジュール化には大掛かりなプログラム構造の変形が必要であり，しばしば非実際的である。
4. 深さ優先探索: 農夫と狼と山羊とキャベツ
パズルのような問題において，問題を解くことは，初期状態から出発して適当な操作により
状態を遷移しながらゴールに到達することとしてとらえられる。
このとき，初期状態からゴールに到達する操作の列，あるいは状態の列が問題の解となる。
初期状態から操作を適用して得られるすべての状態からなる集合は状態空間とよばれる。
したがって，問題の解決は状態空間での探索に帰着される。
状態空間を木 (tree) とするとき，ある状態 (state) と，そこから１回操作を適用して
得られる次の状態以降の部分木 (subtree) からなるリストをそれぞれ cons セルの
car と cdr で表現すれば，右図のように Lisp のリストで状態空間を表現できる。
遅延評価を利用すれば，この状態空間全体を仮想的にデータ構造として与えることができる。
クエストの開始時点では空間のほとんどは「約束」とその向こう側として実体化していないが，
ゴールを求めて探索者が足を一歩踏み入れるやいなや「約束」から実際の状態へと変化する。
このように構成したとき，もともとの問題を，状態空間の仮想的な構築と，
(探索者にとっては事実上) 完成済みの状態空間の探索という，より単純な２問題に分割できる。
ここでは農夫と狼と山羊とキャベツの問題を取り上げよう。
プログラム例を下記に示す。
ファイル farmer-and-wolf-etc.l
として保存し，実行してみよう。
これが正しい解になっていることを確かめよう。
コメントアウトしてある部分を実行して探索後の状態空間を表示すると下記が得られる。
これを Emacs の Lisp モード等で整形するとこうなる。
問題の解を求めるクエストで空間のどこに足を踏み入れたのか，
かなえられた約束があたかも足跡のように残っていることが分かる。
生産性の向上を目的とした言語はモジュール化の機能をより良くサポートする必要があるが，
手続き型言語で典型的に見られるような洗練されたスコープ規則や分割コンパイル，
実行時型に基づく動的な手続き選択などの能力は，必ずしも十分なツールではない。
プログラムを簡単な部品に分割し，そしてそれを組み立てる能力の，
より基本的な強化が必要である。
文献 [4] が主張するように，関数型言語においては高階関数と遅延評価がそのような強化を実現する。
ところが，関数型言語の一派である Lisp では，高階関数は広く活用されているが，
遅延評価については，それを標準機能とする有力な方言 (Scheme) でもサポートは多く初歩的な段階にとどまり，
事実上，熟練者がまれに見せるはなれわざや，初学者が頭の体操として取り組む奇問以上には普及していない。
ここでいくつかの例を通して紹介したように，約束の暗黙の実現 (implicit forcing) を採用した L2Lisp は，
従来の Lisp の意味論を保存しながら (そうしたければ，普通の Lisp として使うことを可能にしながら)，
日常的な課題に対し，他の関数型言語に比肩する簡単で効果的な遅延評価プログラミングを可能にしている。
もしこういってよければ，
長い Lisp の歴史のなかで概ね等閑視されてきた遅延評価プログラミングの実用性について，
現在の技術のもとで再検討する必要があると言えるかもしれない。
ある川の北岸に農夫が狼と山羊とキャベツとともにたたずんでいる。
舟が１そうあり，農夫は一度に１頭または１個を対岸に渡すことができる。
この３者と１個をすべて南岸に渡すにはどうしたらよいだろうか？
ただし，農夫がいないとき，狼と山羊を一緒にすると山羊が食われてしまうし，
山羊とキャベツを一緒にするとキャベツが食われてしまうから，
そうならないように気をつけなければならない。
(make-tree init-state)
は，与えられた初期状態 init-state からの状態空間を遅延評価的に構築する。
(search tree)
は，与えられた状態空間 tree の初期状態
(car tree) から始めて
ゴールへ至る状態のリストをどれか１個，深さ優先で探索する。
;; "農夫と狼と山羊とキャベツ"
;; 猪股・益崎「Schemeによる記号処理入門」森北出版 1994年
;; §8「状態空間の探索」からヒントを得て
;; 農夫と狼と山羊とキャベツが川の南北どちらの岸に位置するかを
;; n か s を要素とする長さ 4 のリストで表現する。
;; 初期状態はすべて北岸に位置する: (n n n n)。
;; すべて南岸に位置する状態 (s s s s) へ到達する経路を探索する。
;; binary map from Haskell
(defun map (f list)
(if (null list) nil
(cons ~(f (car list)) ~(map f (cdr list)))))
;; from Common Lisp
(defun find-if (f list)
(cond ((null list) nil)
((f (car list)) (car list))
(t (find-if f (cdr list)))))
;; (moves '(s s n n)) => ((n n n n) (n s n n))
(defun moves (state)
(let ((f (car state)) ; farmer
(w (cadr state)) ; wolf
(g (caddr state)) ; goat
(c (caddr (cdr state)))) ; cabbage
(append
(if (eq f w) `((,(opposite f) ,(opposite w) ,g ,c)))
(if (eq f g) `((,(opposite f) ,w ,(opposite g) ,c)))
(if (eq f c) `((,(opposite f) ,w ,g ,(opposite c))))
`((,(opposite f) ,w ,g ,c)))))
(defun opposite (x)
(if (eq x 'n) 's 'n))
;; (safe? '(s n s n)) => t
(defun safe? (state)
(let ((f (car state))
(w (cadr state))
(g (caddr state))
(c (caddr (cdr state))))
(not (or (and (eq w g) (not (eq f w)))
(and (eq g c) (not (eq f g)))))))
(defun goal? (state)
(equal state '(s s s s)))
(defun make-tree (init-state)
(cons init-state
~(map make-tree (moves init-state))))
;; 解となる状態の列をどれか一つ深さ優先探索する。
(defun search (tree)
(nreverse (_search tree nil)))
(defun _search (tree path)
(let ((STATE (car tree))
(SUBTREES (cdr tree)))
(let ((PATH (cons STATE path)))
(if (goal? STATE)
PATH
(find-if consp
(map (lambda (subtree)
(let ((state (car subtree)))
(and (safe? state)
(not (member state PATH))
(_search subtree PATH))))
SUBTREES))))))
(setq whole-tree (make-tree '(n n n n)))
(print (search whole-tree))
;; => ((n n n n) (s n s n) (n n s n) (s s s n) (n s n n)
;; (s s n s) (n s n s) (s s s s))
;;(load "ruby-hack.l")
;;(terpri)
;;(print whole-tree)
$ ./L2Lisp.rb farmer-and-wolf-etc.l
((n n n n) (s n s n) (n n s n) (s s s n) (n s n n) (s s n s) (n s n s) (s s s s)
)
$
((n n n n) ((s s n n) . #) ((s n s n) ((n n n n) . #) ((n n s n) ((s s s n) ((n
n s n) . #) ((n s n n) ((s s s n) . #) ((s s n s) ((n n n s) ((s s n s) . #) ((s
n s s) ((n n n s) . #) ((n n s n) . #) ((n n s s) . #)) ((s n n s) . #)) ((n s
n n) . #) ((n s n s) ((s s s s) . #) . #) . #) . #) . #) . #) . #) . #)
((n n n n)
((s s n n) . #)
((s n s n)
((n n n n) . #)
((n n s n)
((s s s n)
((n n s n) . #)
((n s n n)
((s s s n) . #)
((s s n s)
((n n n s)
((s s n s) . #)
((s n s s)
((n n n s) . #)
((n n s n) . #)
((n n s s) . #))
((s n n s) . #))
((n s n n) . #)
((n s n s)
((s s s s) . #) . #) . #) . #) . #) . #) . #) . #)
5. おわりに
参考文献