はじめに
現存するプログラミング言語の中で2番目に古いのがLispです。生まれは古くても、いまだに使われ続け、また、Rubyなどの新しい言語にも影響を与えています。そのLispの派生であり、シンプルさが売りなのがSchemeです。
ここではSchemeの簡単なインタプリタをJavaScriptで作ってみます。
対象読者
本稿はLispやSchemeは少し触ったことはあるけど、インタプリタは書いたことがないという方を読者対象としています。また、JavaScriptの文法や、簡単なデータ構造についての知識を前提とし、説明は省きます。
必要な環境
テキストエディタと、JavaScriptが動くWebブラウザがあれば十分です。他に特に用意するものはありません。
概要
作成するインタプリタについて
インタプリタのコードはJavaScriptで書き、HTMLのフォームを使って、Schemeのプログラムの入力および、結果の表示を行います。説明の簡略化のため、マクロ、末尾再帰の最適化、継続などの実装は省きます。また、説明の上では「関数適用」などといった関数型言語独特の言葉はできるだけ避けるようにしています。
Schemeのプログラム
Schemeではプログラムはリストからなります。Schemeのリストは、
(要素1 要素2 ... 要素n)
と表されます。これをインタプリタに入力し、実行すると、「要素1を関数」、「要素2～要素nまでを引数」として関数の呼び出しが行われます。つまり数学で、sin(0)と書くものを、Schemeでは(sin 0)と表します。また、'(e1 e2 e3)といったように、頭に引用符を付けてやると、これを「リストそのもの」と見て(e1, e2, e3)というデータとして扱います。
これでは分かりにくいの実例を出してみます。
(car '(1 2 3))
これは、 car と '(1 2 3) からなるリストです。上記のルールに従うと、「carが関数」、「'(1 2 3)が引数」として扱われます。carは、第1引数のリストの先頭の要素を返す関数であり、'(1 2 3)は、引用符があるので、要素1、2、3からなるリストのデータです。したがって、このプログラムの結果は「1」となります。
プログラム自身と、データであるリストが同じ書き方であるのは一見ややこしいですが、これこそがSchemeの強みなのです。Schemeは、プログラムとデータを等価に扱えます。データをプログラムとして扱ったり、プログラムを書くプログラムなんてものも書けます。また、C言語やJavaでは書けないような「関数を引数に取る関数」や「関数を返す関数」なども簡単に記述できます。
たしかに、関数ポインタを使えば可能ですが、それはあくまでも「あらかじめ作ってある関数へのポインタ」でしかありません。
Schemeでは動的に新たな関数を作ることが可能です。本稿の最後の方にあるサンプルのクロージャにて例を載せてあります。
インタプリタの概要
Schemeインタプリタの処理は以下の3つの部分から成り立ちます。
- 入力された文字列をインタプリタの内部形式に変換する処理
- 内部形式のデータをSchemeのプログラムとして実行する処理
- プログラムの実行によって得られた結果を表示する処理
これらの処理を繰り返すことによりSchemeインタプリタは動作します。
オブジェクト
インタプリタが扱うデータ
本来Schemeは、ベクタや、文字列、複素数といったさまざまなデータを扱えますが、ここでは簡単なインタプリタを作るのが目的なので扱うデータ型は下記のものだけとします。
- シンボル
- 数値
- コンス
- 関数（後述）
シンボル
シンボルとは、「hoge」、「foo03」、「car」といった文字の集合です。ただし、同一の名前のものが2回以上作られることはなく、1度作ったシンボルを再利用します。
数値
数値とは、「0」、「123」、「-456」といった数字の集合です。こちらは同じ数を何度でも生成できます。
コンス
コンスとは、リストをなすための土台で、CARとCDRと呼ばれる2つのポインタを持ったデータです。
(1 2)というリストは2つのコンスからなり、次のように値が格納されます。
- 1つ目のコンスのCAR部には数値
1のアドレスが、CDR部には2つ目のコンスのアドレスが格納 - 2つ目のコンスのCAR部には数値
2のアドレスが、CDR部にはリストの終端を表すもの（nil）へのアドレスが格納
同様に、(a (b))というリストは、3つのコンス（X、Y、Zと呼ぶことにします）からなり、次のように値が格納されます。
XのCAR部にはシンボルaのアドレス、CDR部にはコンスYのアドレスが格納YのCAR部にはコンスZのアドレス、CDR部にはnilが格納ZのCAR部にはシンボルbのアドレス、CDR部にはnilが格納
これら3つをSchemeの「オブジェクト」と呼ぶことにします。Schemeではすべてのオブジェクトは等価であり、関数も「ただのオブジェクト」として扱えます。
オブジェクトの準備
では、上記で説明した3つのオブジェクトを実際に作ってみます。
var TAG_CONS = 0; var TAG_SYMBOL = 1; var TAG_NUM = 2; function Symbol(str) { this.tag = TAG_SYMBOL; this.name = str; } function Num(val) { this.tag = TAG_NUM; this.num = val; } var nil = /* 後述 */; function Cons() { this.tag = TAG_CONS; this.car = nil; this.cdr = nil; }
これで、hoge = new Cons();などと書くことにより、オブジェクトが生成できます。しかし、シンボルは同一の名前のものを2つ以上作ってはいけないので、工夫が必要です。
var symbol_set = new Array(); function CreateSymbol(str) { var i; for (i=0; i<symbol_set.length; i++) { if (symbol_set[i] == str) return symbol_set[i]; } symbol_set[i] = new Symbol(str); return symbol_set[i]; }
これにより、（少々強引ですが）同じ名前のシンボルを2回生成しないようになりました。また、nilは「nil」という名前のシンボルとして表すので、変数nilはvar nil = CreateSymbol("nil");と初期化します。コンスや数値はnew Cons()などでオブジェクトを作成します。シンボルだけCreateSymbol()で作成する形では統一性がないので、他のオブジェクトも同様に作れるようにします。
function CreateNum(n) { return new Num(n); } function CreateCons() { return new Cons(); }
これで一応オブジェクトは完成です。ただし、このままでは直接プロパティにアクセスする必要があります。これが個人的には嫌いなので、操作の多いものはオブジェクトの内容を設定／取得する関数を作っておきます。
function GetNum(n) { return n.num; } function CAR(x) { if (x == nil) return nil; return x.car; } function CDR(x) { if (x == nil) return nil; return x.cdr; } function SetCAR(x, val) { x.car = val; } function SetCDR(x, val) { x.cdr = val; }
内容はソースを見れば大体分かってもらえると思います。CARとCDRがnilを受け取ったときにnilを返すというのはLispの伝統です。nilというのは、実体はシンボルですが、Lisp上の意味としては空のリスト（要素のないリスト）です。リストの終端として使われたり、特別扱いされるので注意してください。
ちなみに、Schemeではnilはただの変数であり(car nil)や(cdr nil)はエラーとなりますが、Lispの伝統にあわせた方が色々と楽なので、こちらにあわせました。
対リストとクォート
リストは(b1 . b2)や(c1 . (c2 . c3))といった書き方ができます。前者は、1つのコンスからなり、CAR部にb1、CDR部にb2が入っています。後者は、2つのコンスからなり、次のように値が格納されます。
- 1つ目のCAR部には
c1、CDR部には2つ目のコンスのアドレスが格納 - 2つ目のCAR部には
c2、CDR部にはc3が格納
このようにドットを用いることにより、CDR部を自分で設定でき、nil以外が終端のリストを作れます。このようなリストを「対リスト」と言います。
リストをデータとして扱うには、'(d1 d2 d3)と頭に「'」をつけて記述すると最初に説明しましたが、これは、特殊な構文などではありません。実行する前に(quote (d1 d2 d3))に変換されます。quoteは第1引数を「触らず」にそのまま返す関数なので、結果としてリストがそのまま返ります。
