==

rhino で実行するには
$ CLASSPATH=".;c:/takashi/src\rhino1_6R5/js.jar"
$ rlwrap java org.mozilla.javascript.tools.shell.Main
js> load("Lazy.js")

http://blog.livedoor.jp/dankogai/archives/50662064.html



==

http://languagegame.org/dev/trunk/lazy/

* 俺様言語 Lazy を作る。

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

ふとプログラミング言語を一つ作ってみる事にした。そうすると俺に足りないものが見つかる気がする。どんな俺言語かと言うと、

- まず実装言語だが C でも良いがそれだと多分誰も試してくれないと思うので javascript。
-  あとパーサーを作るのが面倒臭いのでlisp っぽい 文法にする。
- データは javascript の物をそのまま流用。
- それだけだと面白みが無いので出来れば遅延評価にする。

こんな物かな？javascript の文法も言語の知識もあやふやだが、ここは無理して知ってる知識だけで作る事にする。

** 単純なパーサー

プログラムの構造は、ブラウザ表示用に一つと、ブラウザが無くても動くように実行エンジンだけ別に作って Rhino で動作確認しよう。で、最初はパーサーを作る。具体的には S 式の文字列をリストに変換する物と、それを文字列に戻す物を作る。リストとは、次のソースのような二つの要素を持つ構造で、配列に比べて関数型言語の実装にとても便利なのです。

>|javascript|
// Cons cell
Cons= function (head, tail) {
  this.head= head;
  this.tail= tail;
}
Cons.nil = new Cons (null, null);
||<

後で遅延評価の俺言語で書き直す壮大な計画なので、思いっきりスタック使いまくって再帰で書く。出来るだけ javascript の雰囲気を残しながら端的に書いた物がこちら(64 行)

<a href="http://languagegame.org/dev/!svn/bc/4/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/4/trunk/lazy/Lazy.js</a>

** REPL

パーサーが出来たところでブラウザ側のコードを書く。この辺は前に書いたコード http://d.hatena.ne.jp/propella/20070131/p1 を流用できるので楽。

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

** シンボルなど

よく考えたら数字とリストだけじゃ何にも出来ない！と気づいてもうちょっとパーサーをもマシにする。使える文字はこんな風。

- カッコはリスト作成に使う。
- 空白文字列は読み飛ばし。
- 数字は数字に使う。
- その他の文字列はシンボル(文字列として保存)。

** 3 + 4

ここでやっと 3 + 4 が出来る。最初は難しい事せず普通の前置式の構文にする。ややこしいのが、例えば (+ 3 4) を与えると生成されるリストが ( (+ 3 4) ) になってしまう所。なので複数の S 式が来た時は最初のやつだけ評価する事にする。

- インタプリタはきっかり一つの S 式を受け取る
- ツリーを評価。

単純に、(* (+ 3 4) 6) の場合、先に引数の (+ 3 4) を評価して * を評価する。それじゃ全然遅延評価じゃないが、まあとりあえず。

<a href="http://languagegame.org/dev/!svn/bc/7/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/7/trunk/lazy/Lazy.js</a> (96 行)

** 関数

関数の表現について考える。関数とは、実行する事の出来る物の事を言う。この言語の世界ではなんでも関数である。と言う事は基本的な動作はこんな感じ。

- 数字を実行すると -> 答えは数字
- シンボルを実行すると -> 辞書からシンボルの内容を取り出して返す
- リストを実行すると -> リストの頭を実行して関数を取り出す。リストの残りを引数として関数を呼び出す。
- 関数を実行すると -> 既存の辞書に、関数用の辞書を追加して何かする。

>|javascript|
Number.prototype.eval= function (env, tmps) { return this }
String.prototype.eval= function (env, tmps) { return env[this] }

Cons.prototype.eval= function (env, tmps) {
  var func= this.head.eval(env);
  if (!func) {
    throw Error("Undefined: " + this.head);
  }
  return func.eval(env, this.tail);
// 関数の実行は省略
}
||<

という事で、関数には辞書が必要な事がわかる。辞書の事をかっこよく環境と言ったりする。実行順序については、リストの先頭だけ最初に実行して、引数の方は関数が自分で実行する事にする。要するに Quote を作るのが面倒くさいだけ。同僚アレックスの言葉を借りると、引数を thunk で渡すと言う。辞書はあとで言語自体で書き直す予定だが、とりあえず javascript のオブジェクトを使う。関数には二種類あって、

- Primitive オブジェクト: 言語が用意する関数をラップしたもの。とりあえず四則演算と lambda 関数
- Lambda オブジェクト: lambda 関数でユーザが作る関数。

Primitive オブジェクトには javascript の関数オブジェクトをそのまま使っても良いのだけど、関数オブジェクトに eval という名前のメソッドを作るのが精神衛生上良くなかったのでラップオブジェクトを作った。あと、lambda のつづりが苦手なのでバックスラッシュでも書けるようにした。

- (\ (x y) (+ x y))

javascript の世界で、read("( (\ (x y) (+ x y) ) 3 4)").eval(Env) とした時の動作について考える。

- javascript の世界
-- Env はグローバル辞書で、+ 等の関数が入っている。
-- read() は S 式からリスト(Cons オブジェクト)を作る。
-- Cons.prototype.eval(env) が呼ばれる。
- Lazy の世界
-- リストの先頭を実行する。
--- lambda 関数を実行する
--- 今の Env を覚えておく(レキシカルスコープ)
--- ラムダオブジェクトを返す
-- 3, 4 を引数にラムダが呼ばれる。
-- x <-3, y <-4 を代入した環境を作る。
-- Env より + が足し算だと分かる。
-- 3 + 4 の結果を返す。

ラムダによる内環境を作るのに、http://blog.livedoor.jp/dankogai/archives/50662064.html を参考に javascript の prototype を活用しました。

>|javascript|
Lambda.prototype.eval= function (env, tmps) {
  var child= function() {};
  child.prototype= env;
  var innerEnv= new child();
  innerEnv.prototype= this.env;
  this.tmpNames.pairsDo(tmps,
                        function (key, value) { innerEnv[key]= value; });
  return this.body.eval(innerEnv, Cons.nil);
}
||<

で、ラムダがつくとなんとなく言語っぽくなってきたわけだけど、まだ CAR も CDR も無いのでろくな事が出来ません。CAR や CDR はパターンマッチを使って実現出来るので、次はパターンマッチを作ろうと思っています。か、完成するのか。。。ここまではのソースこちら。

<a href="http://languagegame.org/dev/!svn/bc/8/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/8/trunk/lazy/Lazy.js</a> (172 行)

* 俺様言語 Lazy を作る。その２。

ちまたでは言語開発合宿というのをやってたそうです。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 は普通に書けます。

>|scheme|
(define factorial (\ (x) (if (= x 0) 1 (* x (factorial (- x 1))))))
||<

<a href="http://languagegame.org/dev/!svn/bc/10/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/10/trunk/lazy/Lazy.js</a> (222 行)

** 遅延評価について考える。

この言語の開発動機は、遅延評価についての理解を深めたいという事だったので、遅延評価を作らないと意味が無い。そこで、どういう動きをすれば良いのか考える。例えば次の式を考える。
>|scheme|
(define double (\ (x) (+ x x)))
(double (+ 3 4))
||<
正格な評価順序だと、(+ 3 4) を実行してから double が呼ばれる。ところが非正格だと、先に double が展開されるらしい。こんな感じか。
>|scheme|
-- 正格
(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 の評価結果は、引数に関係ないのに比べて、プリミティブである + の評価は引数によって変わる。つまり、+ をこれ以上変換したい場合は先に引数を変換しないといけない。つまり、一言で評価と言っても二種類あるのだ。もしかして、非正格な評価とは、まずはプリミティブや条件式を含まない静的な変換を行ったツリーを最後に深さ優先探索で結果を求める事を言うのではないか。しかも、よく見ると。
>|scheme|
(+ (+ 3 4) (+ 3 4))
||<
こ、これは！データフローである！！解説しよう。ここでデータフローとは、俺定義では、変数を含まないプログラムの解析木の事を言う。データフローは本質的にデータの流れをそのまま表現し、S式で表現する事は出来ない。例えば上の式では、二つの (+ 3 4) は同じノードを表すが、S 式上では別々に表記される。データフローはスタック言語を用いて効率的に表現する事が出来るが、それはまた別の話題である。

非正格の評価は、データフローの作成とその評価と言う二段構えで行けそうな事が分かった。でも眠いので続く！

* 俺様言語 Lazy を作る。その３。

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 のような物だ。

>|scheme|
((\ (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 で行われる。
>|scheme|
(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 の世界からはこう見える。
||<
** 挫折

ここまで作って実は上手く動かない事が分かった。具体的には、関数再帰を含む式を上手く評価出来ない。何がおかしいのだ！
>|scheme|
(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
||<

という具合に恐ろしい勢いで式が膨張して行く。よく考えたら当たり前なのに、式が小さくなる事しか考えていなかった。あほ過ぎる！俺！

<a href="http://languagegame.org/dev/!svn/bc/12/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/12/trunk/lazy/Lazy.js</a> 壊れてしまったバージョン (371 行)

** その後。

週末が終わってしまうのでとりあえず昨日のバージョンに戻して今日の変更で有用な物をマージしてアップしました。ただのヘボい scheme になってしまった。。。まだ引数を先に評価する版です。昨日の晩に非正格 = データフローでは？と直感した時は勝ったと思ったのですが、残念ながら私の能力が足りない事が分かりました。また明日に向けて頑張ります。

<a href="http://languagegame.org/dev/!svn/bc/13/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/13/trunk/lazy/Lazy.js</a> 正格に戻した。 (251 行)

再開する時の為に反省点を書く。S 式ではリストと関数適用を同じ方法で書くのがややこしい。特に失敗したのが、あまりにも lisp に引きずられてしまった所。後の方までプログラムとリストの区別がごちゃ混ぜになって混乱してしまった。これは記法を工夫すれば解決するかも知れない。例えば lisp の慣習では '(a b c) を評価した結果は (a b c) であるとされる。これはおかしいのではないか。'(a b c) の結果は '(a b c) であるべきだ。なぜなら '(a b c) がリストを表すのに対して、(a b c) は関数 a の呼び出し結果を表す式だ。関数型言語の評価とは、意味を変えないで表現を変える操作だから、表記法においても意味を誤解させる書き方をしてはいけない。

遅延評価については、出力機構と強く関係があるらしいと想像している。例えば無限リストを処理する場合、実際に無限リストの先頭が評価されるのはリストを表示する瞬間になるだろう。ここは面白い話になりそうだ。

* 俺様言語 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 それをそのまま真似する事にしました。具体的には以下のような流れになります。
>|scheme|
;; まず、+ はプリミティブなので引数を 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 は日本語で書くと弱頭標準形と書けます。この弱い頭であるゆえんがユーザー定義関数の扱いにあるらしいですが、良く分からないので必要になってから考えます。とりあえずは以下のように動きます。
>|scheme|
((lambda (x) (+ x x)) (car (cons 1 (+ 4 'deadbeaf))))
(+ (car (cons 1 (+ 4 'deadbeaf))) (car (cons 1 (+ 4 'deadbeaf))))
(+ 1 1)
2
||<
まずまず動きそうです。

** コンテキスト

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

>|scheme|
(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 はスコープ外なのでエラーになってしまうのです。当たり前ですが評価中のオブジェクトは環境を保存する必要があるので、リストそのままというわけには行きません。ちょっとこの先は面倒なのでまた別の日にやります。

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

** 途中の感想。

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

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

* 俺様言語 Lazy を作る。その５。(進展なし)

ここ数日体調を思いっきり崩したのと、仕事で手一杯になってしまったので進展はありません。なので自分でもどこまでやったか忘れないように現在の状況を書きます。実は進展が無いと言いつつ数日前から何度もコードを書いては消し書いては消しという事を繰り返して、あまりの自分の能力の無さにあきれてしまいます。という愚痴は置いといて。

- 遅延評価の理屈は何となく分かったと思う。
- ようするに副作用が無いので、リストが答えとして返るとき、リスト特定の位置の答えは他の部分に関係なく求まるという点が画期的で、無限リストもこの手で難なく扱う事が出来る。
- 大島さんに教えてもらった scheme で言うと何でも delay と force だと思えば良い。
- 部分リストを評価しないで返すという事は、レキシカルスコープが必要。

れ、レキシカルスコープ！こんな二、三百行のプログラムでそんな大それた事をするつもりは無かったのだけど、遅延評価にレキシカルスコープが必要とは意外に大仕事だ、こういうトイ言語の場合、実行スタックがそのまま変数のスコープになるダイナミックスコープでやると楽勝なのだが、そもそも非正格な言語では実行スタックという物が無いのでこの手が使えない。

このレキシカルスコープ。単に少しルールが変わるだけだと考えていたら大間違いで、えらく面倒臭くて、半分やる気を失っている状態です。

ちなみに体調はどういう具合かと言うと、膀胱(？)はマシになってきましたが頭痛が酷くて、アレックスに聞くとクランベリーを食べると良いらしい(根拠不明) なので、甘酸っぱい物が嫌いなのにも関わらず大量のクランベリーの干物と水をがぶ飲みしています。来週もっと酷くなったら病院も考慮する予定です。

== *[lazy] 俺様言語 Lazy を作る。その６。祝！遅延評価完成！

- 実行環境: http://languagegame.org/pub/lazy/Lazy.html
- ソースコード: <a href="http://languagegame.org/dev/!svn/bc/32/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/32/trunk/lazy/Lazy.js</a> (343 行)

屈折四ヶ月。やりました！ようやく最初の目的だった遅延評価が完成しました！しんどいのでメモだけ。ほとんど <a href="http://mitpress.mit.edu/sicp/full-text/sicp/book/node84.html">SICP 4.1 章</a>と同じやり方です。

- 関数を適用する際に、引数を評価せず Thunk という物で包む。サンク = 式 + 環境
- Thunk は force と言うメソッドで再帰的に中を force し値を取り出す。
- 関数を適用する際に、関数自体は force する。
- 関数を適用する際に、プリミティブなら引数も force する。

たったこれだけで遅延評価できます。Haskell の本に書いてある、パターンマッチの時だけ force するというのとはちょっと違いますが、プリミティブをパターンマッチだと思えば良いです。これだけなら簡単なのですが。。。

落とし穴はデータ構造です。Lazy はコンスセルしかデータ構造がありませんが、それでもここ数ヶ月データ構造の遅延評価をどうすれば良いのだろうと悩み続けていました。<a href="http://mitpress.mit.edu/sicp/full-text/sicp/book/node87.html">SICP 4.2.3</a> のように関数としてコンスセルを定義すれば簡単ですが、なんか納得行きませんでした。答えは簡単で、コンスセルの中にアクセスするには必ず car か cdr を通す事にすればよかっただけでした。一見コンスセルを force すればコンスセルの中身まで force されてしまいそうな気がするのですが、間違い。コンスセルもまた関数の一種だという事を念じながら考えると分かります。中を force するのは必ず car か cdr を通してからです。オブジェクト指向的に言うと、硬くカプセル化されているのです。結果を表示する為に、今はサボって forceAll というのでコンスセルの中まで force する関数を作ってありますが、ちゃんと文字列も Lazy の中で実装すれば要らなくなるはずです。

最近なぜか遅延評価やら Haskell やらに興味がある人が増えたらしく、焦ってしまいます。ずっとやってるのに分からないのはヤバイ！！！と思ってたので出来て良かったです。

- これまでの努力: http://d.hatena.ne.jp/propella/searchdiary?word=%2a%5blazy%5d

* 俺様言語 Lazy を作る。その７。カリー化、Thunk を関数で。

ちまちま細かい修正をしている。まず一度 Thunk を専用のオブジェクトとして作ったのを関数で表現する事にした。意味的には Thunk は引数の無い関数と同じ物ではないかと思ったから。これは後でまた戻すかも知れない。カリー化は、今の所、ユーザ定義関数(lambda)だけ出来る。プリミティブは引数の数をどうやって保存するか考え中。

式を実行するとこんなトレースが表示される。

>|scheme|
>>> (((lambda (x y) (+ x y)) 1) 2)
(((lambda (x y) (+ x y)) 1) 2) =>
  ((lambda (x y) (+ x y)) 1) =>
    (lambda (x y) (+ x y)) =>
    => [ x y|((+ x y))]
    x := [|1]
  => [ y|((+ x y))]
  y := [|2]
  (+ x y) =>
  => 3
=> 3
3
||<

関数式は評価されると [] で囲まれる。| の左が一時変数。リストとしての関数式と、環境を含んだオブジェクトとしての関数を見分けたかったので、表記を変えてみた。:= は関数適用で束縛される値。引数は Thunk 化されて関数になる。

次は無限リストの例

>|scheme|
>>> (define ones (cons 1 ones)) (car ones)
(define ones (cons 1 ones)) =>
=> [|(cons 1 ones)]
(car ones) =>
  (cons 1 ones) =>
  => ([|1].[|ones])
=> [|1]
1
||<

ones は (1 1 1 1...) のように無限に続くリストだけど、car に出会うまでは [|ones] のように Thunk 化されているので評価されない。

まだトレース式が醜いのでそこが課題。また、よく Haskell のデバッグしにくさは実行順序が読めないからという説があるが、遅延評価でも出鱈目の順番な訳では無くてちゃんとルール通り実行されているわけで、Lazy のデバッガを作って遅延評価を快適にデバッグする方法を研究しようと思う。もしかしたらデバッガはスクイークで作るかも知れない。大島さんがスクイークをもっと使おう！と言ってるので。

- 実行環境: http://languagegame.org/pub/lazy/Lazy.html
- ソースコード: <a href="http://languagegame.org/dev/!svn/bc/37/trunk/lazy/Lazy.js">http://languagegame.org/dev/!svn/bc/37/trunk/lazy/Lazy.js</a> (365 行)







== 以下ゴミ

*[lazy] 俺様言語 Lazy を作る。その６。

散々週末を潰して悩み続けてきましたその答えが、あっさり SICP の 4 章に
書いてありました。ガックリ。しかしこの本マニアックだなー。情報科の学生
というのはこんな教科書で育つのか。恐ろしい。十年早く出会ってたらなあ。
随分間が開いてしまったので、方向転換して SICP に書いてある通り進める事
にします。つまり、とりあえず scheme (っぽいもの) を Javascript で実装
して、後から遅延評価に変更する事にします。SICP では簡単に書いてあるの
で、きっと簡単なのでしょう。

まず 4.1.1 章にある eval の実装。eval は式と環境を受け取る関数ですが、
Javascript の方がすっきり書けます。

>|javascript|
Number.prototype.eval= function (env) { return this }
Boolean.prototype.eval= function (env) { return this }
|<

次に変数参照です。変数名は文字列で表現しているので、こんな感じ。

String.prototype.eval= function (env) { 
  var value= env[this];
  if (value == undefined) {
    throw("Undefined name: " + this);
    return this;
  }
  return value;
}

todo: scheme 実装中








====

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

** 関数は関数を返す。

さすがにそろそろ先が見えてきたと思うんだけど、どうかな。次の定義を考え
ます。

(define factorial
  (lambda (x) (if (= x 0)
                  1
                (* x (factorial (- x 1))))))

(factorial 10) という風に呼んだ時、x が 0 の時は 1 を返し、そうでなけ
れば (* x (factorial (- x 1))) を返します。この場合 x が 10 なので、(*
x (factorial (- x 1))) が返ります。普通の言語ではそのまま式の中も評価
されますが、遅延評価なのでとりあえずこのまま返し、呼んだ人がこれをどう
するか決めます。

さて、この式には x という変数があり、この式を返されても呼んだ人はどう
しようもありません。環境を含めた式を返さないといけないのです。環境を含めた式とはすなわち関数です。この場合は、

#(lambda () (* x (factorial (- x 1))))

を返す事になります。# はこれが式(リスト)では無く、環境を覚えている関数
だという事を示す印という事にします。

** コンパイル

実は今まであやふやだった事実が、ここでやっと明らかになりました。変数の
スコープについて曖昧に考えていたのです。どうやら知らない間にダイナミッ
クスコープに作っていたようでした。ハズカシー。という事で、レキシカルス
コープにするにはどうすれば良いのか一から出直して考えます。レキシカルス
コープというのはどういう意味かと言うと(以下省略)という事で、プログラム
を実行する以前に変数の意味を確定する。つまりコンパイルという作業が必要
になってきました。コンパイルという用語はプログラムを機械語に変換する時
に使う用語なので適当では無いですが、良い言葉が見つからなかったのでコン
パイルと呼びます。

具体的にはどうするかと言うと、次の式を見てください。

(+ 3 4)

何の変哲も無い式ですが、コンピュータはこれを見ても何も分かりません。+,
3, 4 と言った単語の意味を確定する必要があります。確定には辞書を使いま
す。これは例えば Env という名前で、Env["+"] = 足し算のような形式になっ
ています。理屈の上では数字の意味も Env に記述するべきですが、実装上は
省略します。(+ 3 4) に Env という辞書がついて意味が確定します。少しや
やこしい例です。

((lambda (double) (double 3)) (lambda (x) (+ x x)))

これは haskell 風に書くと

double 3 where double x = x + x

です。ポイントは、二倍に束縛される double と、実行時まで束縛されない x 
です。このような構造を実現するため、lambda を次のように定義します。

lambda.env = 辞書
lambda.formal = 引数名のリスト
lambda.body = 定義本体のリスト

例えば最初の lambda は次のようになります。

lambda.env = Env
lambda.formal = (double)
lambda.body = (double 3)

このように環境を持ったオブジェクトを、ただのリストと区別して頭に # を
付けます(後で廃止予定) 例えばコンパイル後の式は 

(#(lambda (double) (double 3)) #(lambda (x) (+ x x)))

になります。ここで最後に Env を含む大きな関数を作成して

#(lambda () (#(lambda (double) (double 3)) #(lambda (x) (+ x x))))

最後に実行すれば OK という具合です。失敗談を言いますと、作っているうち
に頭が混乱して、lambda.body も lambda なのでは無いだろうかと言う気持ち
になって来ますが、lambda.body は自体はリストです。




 の先頭は * なのでさらに掛け算をする必要がありま
すが、それは呼んだ人が決める事で、とりあえずこの途中の式を返さなくては
なりません。ところが式をそのまま返しても駄目で、ちゃんと



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







todo: if の定義を変更
ラムダの rewrite について考える。




諦めきれず、今の lisp もどきの言語を無理やり非正格にしたらどうなるかやっ
てみた。つまり、四則演算以外の関数で引数を評価するのをやめてみたのだ。
まずは軽く cons から。

(cons (+ 3 4) '(5)
((+ 3 4) quote (5))

むむ。確かにヘンだ。でもヘンじゃないかも知れない。cons は頑張って (+ 3
4) と '(5) でリストを作ろうとしている。まだ結果が ((+ 3 4) . '(5)) だったら
許せるかも知れない。なぜなら、まだそこに何かをやり遂げようとする意思を
感じるからだ。ここで、lisp の呪縛から逃れて、思い切って '(list) の結果
は '(list) であると書く事にすると評価前 -> 評価後はこんな形になるだろ
う。

- (+ (+ 1 2) 4) -> (+ 3 4) -> 7 -- 変化する。意思を感じる形。
- 42 -> 42 -- もう一仕事終えて何もやらなくて良い感じ。
- '(+ 3 4) -> '(+ 3 4) -- もう何もやらなくて良い感じ。
- (cdr '(3 4)) -> '(4) -- 変化する。意思を感じる形。
- (cons (+ 3 4) ()) -> ((+ 3 4) . ())




** 頭の弱いふつうの形式

http://codezine.jp/a/article/aid/739.aspx
http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4-05w/text/eopl014.html#toc18
http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4-05w/text/eopl010.html
http://www.sampou.org/cgi-bin/haskell.cgi?Lazy
http://en.wikibooks.org/wiki/Haskell/Laziness
http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/?ST=ittrend&P=2

(define foldl (lambda (f z xs) (if (null? xs) z (foldl f (f z (car xs)) (cdr xs)))))








とりあえず factorial が壊れたままだと気持ちが悪いので、兎にも角にも動
く形に纏めたからこの週末を終えたいと思う。再び再帰関数の動作に注目する。

(define factorial (lambda (x) (if (= x 0) 1 (* x (factorial (- x 1))))))

ここで問題は、プリミティブである if が出てきたのに飛び越えて factorial 
を rewrite してしまったからだろう。アルゴリズムを見直す。

- rewrite プリミティブが現れるまで変数を書き換える。
- apply 

(define ones (cons 1 ones)))
(take 5 ones)
(take 5 ones)

((lambda (n xs) (if (= n 0) () (cons (car xs) (take (- n 1) (cdr xs))))) 5 ones)
(if (= 5 0) () (cons (car ones) (take (- 5 1) (cdr ones))))) 5 ones)
(cons (car ones) (take (- 5 1) (cdr ones)))
(cons 1 (take 4 (cdr ones)))






(define take (lambda (n xs) (if (= n 0) () (cons (car xs) (take (- n 1) (cdr xs)))))


(define three 3) -- three = 3 と定義する。
((\ (x) (+ x x)) (+ three 4) -- リストの rewrite
(#(\ (x) (+ x x)) (+ 3 4)) -- 要素を全部 rewrite する。
(+ (+ 3 4) (+ 3 4)) -- (+ 3 4) を x に compose


-- 非正格
(double (+ 3 4))
(#(\ (x) (+ x x)) (+ 3 4)) -- double を評価する。
(+ (+ 3 4) (+ 3 4)) -- (+ 3 4) を適用する。
(+ 7 7) -- (+ 3 4) を評価する。
14 -- (+ 7 7) を評価する。
||<




プログラムの意味に変更を及ぼさないのに比べて、
+ の変換は



パターンマッチをどのように実現するのか考えている。パターンマッチという
と、普通は一つの関数にパターンが幾つもあって、当てはまった関数を実行す
るという事になるのだが、

(define if (\ (true then _)  then
              (false _ else) else))


で、最初は (+ 3 4) が Rhino で動くまで。いきなり 3 + 4 は難しいの
Lazy.eval("42") == "42"
Lazy.eval("(+ 3 4)") == "7"