俺様言語 Lazy を作る。その４。

http://languagegame.org/pub/lazy/Lazy.html

プログラムは同時にリストではない。

さて、前回の気付いた重要な点は、lisp の伝統的なリストの表現方法 '(this is a list) => (this is a list) がおかしいという事でした。数字の 7 を評価すれば 7 が返るように、リテラルなら評価しても変わらない表現を返すべきです。という事で '(list) の評価結果として '(list) を返すという方針で行こうと決めたのですが、さらにもう一点困った点があります。それは非正格の言語では部分だけ計算した結果を持つ必要があるのですが、それを上手く表現する方法がありません。つまり、'(hop <まだ実行してない> jump) のような、ヌケのあるリストを作らないといけないのです。Scheme の仕様によると、そういうリストを表現する方法としてクワジークオートというのを使えば良いと書いてあったんだけど、一見して難しいので辞めました。

で、どういう手法を採用したかと言うと、'(1 2 3 5) を表現するのに (cons 1 (cons 2 (cons 3 (cons 5 ())))) というデータを内部で持つ事にしました。これならリスパーの人にも受け入れられると思います。cons は lisp の関数で、(cons 1 '(2 3)) といえば答えは (1 2 3) です。つまり、cons を計算しないでそのままタグとして使うわけです。

分かりやすいかどうかは別として、これで大きな問題が一つ解決しました。また、リストをわざわざ cons と書く事によって、

(number 1) : データ (実装は違うが気分としては型+データ)
(cons 1 (cons 2 '(3))) : リスト
(car '(3 4 5)) : プリミティブ関数呼び出し
(lambda (x) (+ x x)) : ユーザ定義関数
(factorial 10) : ユーザ定義関数呼び出し。

のように、全てのデータが (タグ内容) という統一構造になりました。とはいえ、ここまでは単なるデータ構造の話で、実際の遅延評価の動作はまだこれからの話です。

弱い頭の非正格

Haskell では遅延評価の実装技術として、WHNF という形式を採用しているとの事でしたので http://www.sampou.org/cgi-bin/haskell.cgi?Lazy それをそのまま真似する事にしました。具体的には以下のような流れになります。

;; まず、+ はプリミティブなので引数を WHNF にする。
(+ 1 (car (cons (+ 2 3) (+ 4 'deadbeaf))))
;; car は (+ 4 'deadbeaf) を計算せずに (+ 2 3) をそのまま取り出す。
(+ 1 (+ 2 3))
;; (+ 2 3) を計算する。
(+ 1 5)
;; 結果
6

あまり良い例ではないですが、WHNF にするとは、枝がパターンマッチ出来るまで外側から適用して行く事らしいです。lazy にはパターンマッチが無いのでもっと単純です。どういう用語を選べばよいやら悩みますが、とりあえず遅延評価しないで値をとってくる事を「確定」と呼びます。(頭部引数引数...) のとき、

頭部は確定。
+ - * / = car cons : 引数を確定。
if : 条件部を確定。
cons : 評価しない。

確定と言っても、リストの場合は評価するのは一番浅い段だけでいいです。

ラムダとWHNF

ユーザ定義関数の扱いについて書きます。WHNF は日本語で書くと弱頭標準形と書けます。この弱い頭であるゆえんがユーザー定義関数の扱いにあるらしいですが、良く分からないので必要になってから考えます。とりあえずは以下のように動きます。

((lambda (x) (+ x x)) (car (cons 1 (+ 4 'deadbeaf))))
(+ (car (cons 1 (+ 4 'deadbeaf))) (car (cons 1 (+ 4 'deadbeaf))))
(+ 1 1)
2

まずまず動きそうです。

コンテキスト

さて、ここまで一見順調そうですが、新たな問題が発生しました。おなじみ factorial がこんなエラーを吐いてしまうのです。

(define factorial (lambda (x) (if (= x 0) 1 (* x (factorial (- x 1)))))) =>
  (lambda (x) (if (= x 0) 1 (* x (factorial (- x 1))))) =>
  => #(\ (x) (if (= x 0) 1 (* x (factorial (- x 1)))))
=> #(\ (x) (if (= x 0) 1 (* x (factorial (- x 1)))))
(factorial 10) =>
  (if (= x 0) 1 (* x (factorial (- x 1)))) =>
    (= x 0) =>
    => false
  => (* x (factorial (- x 1)))
=> (* x (factorial (- x 1)))
(* x (factorial (- x 1))) =>
js: "Lazy.js", line 173: exception from uncaught JavaScript throw: Undefined name: x

これは、遅延評価によって (* x (factorial (- x 1))) がそのまま返るのですが、当然 x はスコープ外なのでエラーになってしまうのです。当たり前ですが評価中のオブジェクトは環境を保存する必要があるので、リストそのままというわけには行きません。ちょっとこの先は面倒なのでまた別の日にやります。

http://languagegame.org/dev/!svn/bc/18/trunk/lazy/Lazy.js WHNF めざし中 (330 行)

途中の感想。

帰りの車のなかで、そうだ、部分リストじゃなくてラムダを作って返せば良かったんだ！と気がつきました。つまり、ラムダ式 (lambda ...) + 環境 = 関数です。関数と言うと、値を待ち受ける状態の物を考えがちですが、実行中の状態、つまり、(関数 + 引数を受け取った直後) を状態をゼロ引数の関数と考えて何の問題も無いのです。もしかして、こ、これがいわゆる継続というやつでは無いだろうか！そして、もっと一般化して、数字やリストもそれ自体を返す関数だという事にすれば、関数とは、別の関数を返す何かであると綺麗に定義出来るのです。これはすごい！

いや、別に凄くない。こういう話は大抵の関数型言語の本に書いてあります。でも凄い。何が凄いかと言うと、継続や関数を返す関数という考え方は、なんかわざとらしくて嫌だなーと思っていたんだけど、それどころか綺麗に言語を実装するには必要不可欠な事が分かった事です。何と言うか、あるべき所にあるべき物がちゃんと納まっている感じがして、とても人間が作ったアイデアとは思えないです。いやべつに私は ID 論者じゃないけど、とにかくびっくりです。

言語ゲーム

とあるエンジニアが嘘ばかり書く日記