ちまたでは言語開発合宿というのをやってたそうです。http://wiki.fdiary.net/ldev/ 無茶苦茶楽しそう！この日記も思いっきり影響されてますが、ヘタレなのでこそこそ隠れてマイペースに行きます。
http://languagegame.org/pub/lazy/Lazy.html
factorial
先に進む前に define を実装する。これは破壊的な関数で現在の環境に名前を追加する。define は lambda を使って定義出来る、とどこかで聞いたけど、やり方が良く分からないのでプリミティブとして環境辞書に突っ込む。現在のパーサは read (文字列) という風に文字列を受け取ると、一つのリストを生成する。例えば read("42") は 42 では無く (42) を生成する。で、なぜか最初の最初の要素だけを実行するのだが、これを変更して全部実行して最後の要素だけを返すという風する。これをトップレベルと言う。しかしこれで副作用を導入してしまった！
で、あとやっぱり代入の前には引数を評価しておく必要がある事が分かった。なぜなら、例えば (define negated (lambda (x) (- 0 x))) とやった後で (negated 10) を評価すると、答えは -10 じゃなくて ( (lambda (x) (- 0 x) ) 10) になってしまう。() の中の先頭は一度しか評価されないから、negated -> (lambda (x) (- 0 x)) までは変換されるけど、そこで止まってしまう。もしかして、ここが遅延評価の勘所なのかな？
なんかまったく lazy じゃないし、だんだん面白みのない言語になって来た。lisp には重力が働いているというのは本当なのだろうか。とりあえず動くものを作ってからぶっ壊すという方針で、定番の factorial が作れるまでは我慢しよう。というわけで嫌々実装した版です。factorial は普通に書けます。
(define factorial (\ (x) (if (= x 0) 1 (* x (factorial (- x 1))))))
http://languagegame.org/dev/!svn/bc/10/trunk/lazy/Lazy.js (222 行)
遅延評価について考える。
この言語の開発動機は、遅延評価についての理解を深めたいという事だったので、遅延評価を作らないと意味が無い。そこで、どういう動きをすれば良いのか考える。例えば次の式を考える。
(define double (\ (x) (+ x x))) (double (+ 3 4))
正格な評価順序だと、(+ 3 4) を実行してから double が呼ばれる。ところが非正格だと、先に double が展開されるらしい。こんな感じか。
-- 正格 (double (+ 3 4)) ((\ (x) (+ x x)) 7) -- カッコの中を全部評価する。 (+ 7 7) -- 関数を適用する。 14 -- (+ 7 7) を評価する。 -- 非正格 (double (+ 3 4)) ((\ (x) (+ x x)) (+ 3 4)) -- double を評価する。 (+ (+ 3 4) (+ 3 4)) -- (+ 3 4) を適用する。 (+ 7 7) -- (+ 3 4) を評価する。 14 -- (+ 7 7) を評価する。
どうやったらこんな事が可能になるのだろうか。そこでじっくり非正格の式を眺めているとある一つの事に気がつく。それは、(+ (+ 3 4) (+ 3 4)) の前と後では式の雰囲気が明らかに異なるのだ。
- (double ?) -> ( (\ (x) (+ x x) ) ?) : 変換の仕方が一つしか無い。
- (+ ? ?) -> ? : 数字の値によって結果が異なる。
つまり、double の評価結果は、引数に関係ないのに比べて、プリミティブである + の評価は引数によって変わる。つまり、+ をこれ以上変換したい場合は先に引数を変換しないといけない。つまり、一言で評価と言っても二種類あるのだ。もしかして、非正格な評価とは、まずはプリミティブや条件式を含まない静的な変換を行ったツリーを最後に深さ優先探索で結果を求める事を言うのではないか。しかも、よく見ると。
(+ (+ 3 4) (+ 3 4))
こ、これは！データフローである！！解説しよう。ここでデータフローとは、俺定義では、変数を含まないプログラムの解析木の事を言う。データフローは本質的にデータの流れをそのまま表現し、S式で表現する事は出来ない。例えば上の式では、二つの (+ 3 4) は同じノードを表すが、S 式上では別々に表記される。データフローはスタック言語を用いて効率的に表現する事が出来るが、それはまた別の話題である。
非正格の評価は、データフローの作成とその評価と言う二段構えで行けそうな事が分かった。でも眠いので続く！
