http://languagegame.org/pub/lazy/Lazy.html
rewrite と compose : 項の書き換えと関数合成。
いよいよ山場。 遅延評価を実装する。遅延評価が完成した暁には次のような式が評価出来るようになる。
> ((lambda (ones) (take 5 ones)) (cons 1 ones)) (1 1 1 1 1) Haskell で書くと、take 5 ones where ones = 1 : ones のつもり
と言うわけで、今まで実行のことを eval と言ってたが、三つに分けて考える。
- rewrite : 変数を展開する。luckyNumber -> 7
- compose : 関数を展開する。( (\ (x) (+ x x) ) 3) -> (+ 3 3)
- apply : 具体的な値を基にプリミティブを評価する。(+ 3 4) -> 7
Haskell での適用はプリミティブに加えてパターンマッチでも発生すると書いてあるが、まだパターンマッチが無いので考えない。compose は関数は要素が全部プリミティブになるまで引数を適用する事だが、意味としては関数合成の事なのでこういう名前にした。例えば
いわゆる関数合成とはこういう事。 f(x) = 2 * x, g(x) = 3 * x のとき、f (g (5)) = 2 * (3 * 5) lazy で書くと (define f (\ (x) (* 2 x))) で (define g (\ (x) (* 2 x))) のとき (f (g 5)) 以下 rewrite と compose を行う (f (g 5)) ((\ (x) (* 2 x)) ((\ (x) (* 3 x)) 5)) -- rewrite ((\ (x) (* 2 x)) (* 3 5)) -- compose (* 2 (* 3 5)) -- compose
rewrite 時の具体的なアルゴリズムはこうしよう。つまり、compose は rewrite の中で呼ばれる。
- シンボルを rewrite -> 環境辞書から名前を引いて内容を返す。
- アトム (数字、Boolean、関数) を rewrite -> 自分を返す。
- リストを rewrite
- 要素を全て rewrite する
- 先頭を関数とみなして compose した結果を返す。
ラムダ式はただのリストなので、特別扱いする必要がある。リストと見分けがつくように、関数オブジェクトの文字表現の最初に # をつける。C 言語でいう所のポインタ演算子 *ptr のような物だ。
((\ (x) (+ x x)) 3) -- この式を書き換えてみます。 ((\ (x) (#+ x x)) 3) -- プリミティブの rewrite (#(\ (x) (#+ x x)) 3) -- ラムダの rewrite (#+ 3 3) -- compose
apply : 関数の適用
実装時に発見した事は、このあと apply を行う際にはもう環境辞書が必要無くなる事だ。つまり、rewrite によってデータフローを作ってしまうと名前は全部 Primitive か Lambda への参照に置き換わってしまう。効率という点でも非正格言語は凄いと分かってきた！
再帰的表現
この時点で俺言語は相当壊れてしまって、折角嫌々作った define が動かない。特に、(define ones (cons 1 ones)) -> (1 1 1...) のような再帰的な定義をしたいので注意深く作らないといけない。しかし、この式はどういう意味なんだろう。ones を定義するのに何故 ones を使えるのだ！インチキ臭い。もしかして lambda でも再帰的な定義を許さないといけないのだろうか。( (lambda ones (cons 1 ones) ) ones) これは絶対間違ってる気がする。なので、再帰的な定義はインチキ臭い define だけで許す事にする。define の処理は rewrite で行われる。
(define ones (cons 1 ones)) (define ones (#cons 1 ones)) -- リストを書き換え。ones は？ (define ones (#cons 1 (#cons 1 (#cons 1 ...)))) -- のようにしたい。
実はここまで処理系自体を Lazy で書き直すという遠い目標の為に出来るだけ副作用なしでやってきたのだが、さすがにこのオブジェクトを作るのは無理な気がして来た。というのも、副作用なしという事は全てのデータ構造を cons で作るわけだけど、cons で作るという事は新しいオブジェクトを生成してしまうという事。なので、折角環境で ones のツリーを束縛しても、rewrite すると別のオブジェクトが作られるので自分自身の参照を自分の中に取り込む事が出来ない。色々実験して、define の中だけで一度だけ許される再帰を表現する為のプロキシオブジェクトを導入する事にした。本当はどうするのが正しいのか後で調べないと。具体的には define の動作はこうなる。
(define ones (cons 1 ones)) -- Lazy の世界。自己参照 env["ones"]= new LazyProxy(); -- js の世界。環境辞書にプロキシが登録される。 (cons 1 ones) -- Lazy の世界。rewrite (#cons 1 #proxy) -- Lazy の世界。ones のところにはプロキシが入る。 env["ones"].value= (#cons 1 #proxy) -- js の世界 rewrite 後のデータを代入 (#cons 1 #proxy) -- 実際はこうだが (#cons 1 (#cons 1 (#cons 1 ... -- Lazy の世界からはこう見える。
挫折
ここまで作って実は上手く動かない事が分かった。具体的には、関数再帰を含む式を上手く評価出来ない。何がおかしいのだ！
(define factorial (lambda (x) (if (= x 0) 1 (* x (factorial (- x 1)))))) (factorial 10) (if (= 10 0) 1 (* 10 (factorial (- 10 1)))))) -- compose (if (= 10 0) 1 (* 10 ((lambda (x) (if (= x 0) 1 (* x (factorial (- x 1))))) (- 10 1)))))) -- rewrite (if (= 10 0) 1 (* 10 ((lambda (x) (if (= x 0) 1 (* x ((if (= (- 10 1) 0) 1 (* (- 10 1) (factorial (- (- 10 1) 1)))))))))) (- 10 1)))))) -- rewrite
という具合に恐ろしい勢いで式が膨張して行く。よく考えたら当たり前なのに、式が小さくなる事しか考えていなかった。あほ過ぎる！俺！
http://languagegame.org/dev/!svn/bc/12/trunk/lazy/Lazy.js 壊れてしまったバージョン (371 行)
その後。
週末が終わってしまうのでとりあえず昨日のバージョンに戻して今日の変更で有用な物をマージしてアップしました。ただのヘボい scheme になってしまった。。。まだ引数を先に評価する版です。昨日の晩に非正格 = データフローでは？と直感した時は勝ったと思ったのですが、残念ながら私の能力が足りない事が分かりました。また明日に向けて頑張ります。
http://languagegame.org/dev/!svn/bc/13/trunk/lazy/Lazy.js 正格に戻した。 (251 行)
再開する時の為に反省点を書く。S 式ではリストと関数適用を同じ方法で書くのがややこしい。特に失敗したのが、あまりにも lisp に引きずられてしまった所。後の方までプログラムとリストの区別がごちゃ混ぜになって混乱してしまった。これは記法を工夫すれば解決するかも知れない。例えば lisp の慣習では '(a b c) を評価した結果は (a b c) であるとされる。これはおかしいのではないか。'(a b c) の結果は '(a b c) であるべきだ。なぜなら '(a b c) がリストを表すのに対して、(a b c) は関数 a の呼び出し結果を表す式だ。関数型言語の評価とは、意味を変えないで表現を変える操作だから、表記法においても意味を誤解させる書き方をしてはいけない。
遅延評価については、出力機構と強く関係があるらしいと想像している。例えば無限リストを処理する場合、実際に無限リストの先頭が評価されるのはリストを表示する瞬間になるだろう。ここは面白い話になりそうだ。
