1. 言語のアウトラインをパクる(R7RS)
2. lexer/parserを書く
3. eval関数と環境を実装 (とりあえず、(+ 1 2)が評価出来る所まで実装)
4. プリミティブ(定数と関数)を実装
5. ifを実装
6. 変数を実装(letを実装)
7. ラムダ抽象と関数適用の追加実装
8. ひとまずゴール - 足りない機能はラムダ計算で補う
9. その他のTODO

最低限のLispを作るためのメモです。

言語のアウトラインをパクる(R7RS)

言語のアウトライン(特にSyntax)は一度見ておいた方がいい。 最低限のLispという点でCommon LispよりはScheme寄りになると思う。 独自のLispを作るのでR7RSの実装からは外れていくだろうが、実際の仕様書がどのように書かれているのかは一応参考にはなる。

lexer/parserを書く

最近はparser comibnatorがあるし、Lispは括弧で囲まれたリストとシンボルだけという基本的なシンタックスなので、 lexerとparserはまとめて実装できるはず。最初は代数的データ型やcase class(または普通のクラス?)も最低限の記法で間に合うかと。 動的型付け言語なら、もっとシンプルに普通にリストと(シンボルを表す)文字列というデータ型でいけてしまうかも。 後で、必要に応じて拡張していけばいい。

eval関数と環境を実装 (とりあえず、(+ 1 2)が評価出来る所まで実装)

eval関数を実装して、Lispの最も初歩的な文法である(+ 1 2)が実行可能な所まで持っていく。 ちなみにLispでは、+は演算子ではなく、関数。 ここまで行くと、モチベーションが格段に上がるので、(+ 1 2)で結果が返ってくるような形まで作っておきたい。

必要になってくるのは、(+ 1 2)を評価するための関数(evalと呼ばれるやつ)と、環境(変数名と値のペアのリスト)、 プリミティブ関数+、number型(int型?)の実装。また、この時の(+ 1 2)は、ネストさせて(+ 1 (+ 2 3))と書いても動くように しておくことが求められる。eval関数は再帰的に実装すること。 環境に関しては、環境から値を検索し取り出すための関数も必要となる。

プリミティブ(定数と関数)を実装

(+ 1 2)を評価できるeval関数が実装できたら、後はそれを引き伸ばしていくだけ。

booleanとnumberを操作する一連の関数を実装する。 booleanとnumberで計算が出来るレベルとなると、電卓っぽくなる。

ifを実装

最初の制御構文的な機能、ifを実装する。が、これは実際すごく簡単。

(if condition then-clause else-close)

に対して、conditionを評価して、その結果のtrue/falseに合わせて、 then-clauseもしくはelse-clauseのどちらかを評価し、その結果を返すだけ。

変数を実装(letを実装)

letは実際のところ、ラムダ抽象へ置換可能ので、最低限の機能を持ったLisp実装する上では、 態々実装する必要はない。しかし、letを先に実装しておくと、後のラムダ抽象の実装が楽になる。

ラムダ抽象と関数適用の追加実装

ラムダ抽象¹は大体、以下のような式。

(lambda (x) ...)

このラムダ抽象の実装は、eval関数に、ラムダ抽象が与えられた場合にクロージャを返す処理を追加し、 関数適用にクロージャが関数として与えられた場合の処理を追加する。

ひとまずゴール - 足りない機能はラムダ計算で補う

ここまでくれば、ひとまず、プログラミング言語としては完成。

ループはYコンビネータによる再帰で実現させる。

ラムダ抽象(と関数適用)を実装したことで、Yコンビネータによる再帰が可能になる。 YコンビネータとはSchemeで書くと以下のような式。

(lambda (f) ((lambda (p) (f (lambda (a) ((p p) a)))) (lambda (p) (f (lambda (a) ((p p) a))))))

このコンビネータに対して、例えば、以下の再帰的な関数fibを(引数として)与える。

(lambda (fib) (lambda (n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))))

すると、以下の式のクロージャが生成される。この時のクロージャが持つ環境の変数fibには自分自身の以下の式が束縛されている。

(lambda (n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))

このクロージャfibに(fib 10)などの関数適用を行うことで再帰呼出しが実現する。

また、データ構造も実装してないように思えるかも知れないが、これまたラムダ計算でcons/car/cdrを表現する手法がある。 したがって、ラムダ抽象を実装した時点で、すでにリスト構造の実装も終わっていた。

というわけで、最低限の機能を持ったプログラミング言語が実装できたと結論付ける。

その他のTODO

以上から、プログラミング言語を実装したも同然だが、当然、言語としては物足りない。

基本的には処理系の実装をサボった分だけ、作った言語(処理系)でプログラムを書くのが大変になる。 例えば、再帰呼出しを書くたびにYコンビネータを使うという辛みが残ってしまう。

というわけで、以下のようなTODOが残ることとなる。

1. 部分適用
2. letrecでプリミティブな再帰を実装
3. グローバル環境に変数を束縛
4. その他、文字列の実装、組み込みデータ型の実装など (あとは自由に拡張してくだけ)
5. コンパイラの実装など... etc

まあこの辺は、のんびり実装すればいいと思うが。

1. 別名、ラムダ式とか無名関数と言ったりするが、ラムダ式という言い方は、後述するラムダ計算のラムダ式と紛らわしい。したがって、ラムダ抽象と書いておくこととする。↩