俺様言語 Lazy を作る。

(注意: この俺様言語の日記はなにぶん学習の過程ですので、数多くの嘘が混ざっている場合があります。信用しないで下さい)

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

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

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

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

単純なパーサー

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

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

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

http://languagegame.org/dev/!svn/bc/4/trunk/lazy/Lazy.js

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) を評価して * を評価する。それじゃ全然遅延評価じゃないが、まあとりあえず。

http://languagegame.org/dev/!svn/bc/7/trunk/lazy/Lazy.js (96 行)

関数

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

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

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 を活用しました。

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 はパターンマッチを使って実現出来るので、次はパターンマッチを作ろうと思っています。か、完成するのか。。。ここまではのソースこちら。

http://languagegame.org/dev/!svn/bc/8/trunk/lazy/Lazy.js (172 行)

言語ゲーム

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

俺様言語 Lazy を作る。

単純なパーサー

REPL

シンボルなど

3 + 4

関数