Part4では，Lisp（リスプ：List Processor）インタプリタをJava言語を使って作っていきます。Lispは非常に歴史が古く，様々な分野で利用されている言語です。しかし，皆さんの中にはLisp自体をよく知らないという方もいらっしゃるかもしれません。どんなものを作るかわからないままでは面白みも半減してしまいますから，まずはLispのごく基本的な動作を紹介しましょう。

まずは簡単Lisp講座

　Lispの本質は，すべてがリスト（正確にはS式，詳細は後述）で表現されることにあります。リストは要素を順序付きで並べたもので，“(1 2 3 4)”のように要素の並びをカッコでくくって表記します。このリストの要素は1，2，3，4の四つです。

　「すべてがリストで表現される」という言葉の通り，Lispではプログラムもこのようなリストとして表現します。Lisp処理系は，与えられたリストの一つ目の要素を関数名として解釈し，二つ目以降の要素を引数としてその関数を実行します。また，Lispでプログラム（リスト）を実行することを「評価する（evaluate）」と言います。例えば，

　(+ 10 20)

というリストを評価（実行）する際には，“＋”という関数に二つの引数10と20が与えられることになります。関数“＋”はすべての引数を加算する関数で，このリストの評価結果は30です。評価結果のことを「値」と呼びます。

　関数定義もやはりリストの形をしたプログラムで，defun関数を使います。例えば，fooという名前の関数を定義するには，

　(defun foo (x y) (+ x y))

のように記述します。2番目の要素が関数名，3番目の要素が仮引数のリスト，4番目の要素が関数の本体です（図1）。関数“＋”はすでに見たようにすべての引数を足し合わせる関数ですから，fooは二つの引数の和を求める関数になります。つまり，“(foo 10 20)”の値は30です。

図1●関数定義もリストで記述する

　表記は独特ですが，何か既存のプログラミング言語を知っていれば，基本的な動作はなんとなく理解できると思います。ただ，独特な用語がこの先でいくつか出てきますので紹介しておきましょう。“(foo 10 20)”を評価する際，関数fooの仮引数xに10が格納され，yに20が格納されます。Lispではこれを「束縛」と言い，束縛された変数の値の組（ここでは“((x 10) (y 20))”）を「環境」と呼びます。関数定義の本体の“(+ x y)”はこの環境の下で評価されることになります。つまり，この時点でx，yに束縛されている値が使われて，“(+ 10 20)”として評価されます。

　リストの要素としては数値，関数名，変数名，リストなどどれでも入れることができます。変数はタイプ（型）を持ちません。つまり変数にはどんなものでも入れることができます。これを「タイプレス変数」などと呼んでいます。

　リストの要素になりうるもののうち，リスト以外のもの，具体的には変数や関数など名前を持つものや，1，2などのデータを「アトム」と呼びます。また，空のリスト“( )”は例外的にアトムとしても扱います。さらに，Lispには空っぽであることを表す特別な値「NIL」があり，空のリストはNILと同じものとして扱われます。

　アトムのうち名前を持つものを「シンボル」と呼びます＊1。上の例ではdefun，foo，x，y，＋がシンボルです。NILも特別なシンボルです。これらアトム（シンボルも含む）とリストからなるLispで扱うすべてのものをまとめて「S式」（Symbolic Expression）と呼びます（図2）。つまり，冒頭で述べたようにLispではすべてをS式で表すわけです。

図2●Lispのタイプ・システム（一部）。アトムもリストもS式である

Lispの関数，初歩の初歩

　少しだけLispの基本的な関数も紹介しておきましょう。上の例ですでに二つの値を加算する関数“＋”が出てきました。同様に“−”（減算），“＊”（乗算），“／”（除算）もあります。さらに“＝”や“＜”のように比較関数もあります。比較関数の値は偽であればNILになり，真であればNIL以外になります。

　quoteという関数は，引数のS式を評価せずに値として返します。例えば，“(quote (1 2 3))”の値は“(1 2 3)”です。quote関数は頻繁に用いられる（多くの場合，リストが数や文字列から成るデータであることを示す）ため，シングルクォート（’）を用いた簡略記法があり，上の例は“'(1 2 3)”と書いても同じです。

　リストに対する基本的な操作も関数として用意されています。リストの先頭の要素を取り出す関数は「car」（「カー」と発音します）です。例えば，

　(car '(1 2 3))

を評価すると1が返ってきます。

　また，先頭以外の残りの部分を取り出す関数は，「cdr」（「クダー」と発音します）です。例えば，

　(cdr '(1 2 3))

を評価すると“(2 3)”が返ります。

　carとcdrを組み合わせれば，リストの何番目の要素でも簡単に取り出すことができます。例えば，2番目の要素を取り出すには

　(car (cdr '(1 2 3)))

と書くことができます。

Javaを活用して
コンパクトに仕上げる

　このように「データとプログラムが同じデータ構造で表現され，それらを同等に扱える」という点で，Lispはほかの多くの言語と大きく異なります。プログラムをデータと同じように扱えるということは，プログラム内のある場所でデータとして生成したリストを，同じプログラム内でプログラムとして動かすこともできるということです。この特徴を生かして，Lispは新しい言語を作成するときの実験場としてもよく使われます。

　以上，Lispのごく基本的な部分を紹介しました。少しはイメージがつかめたでしょうか。あとは必要に応じて補足していくことにして早速作り始めましょう。プログラミング言語を深く知るのに一番いい方法は，その処理系を作成してみることだからです。それによって，そのプログラミング言語の本質や言語仕様の背景にある考え方も見えてきます。

　Lisp処理系の機能は大きく三つの要素――(1)リストをキーボードやファイルから読み込み，メモリー上の表現に変更する「リーダー」部，(2)メモリー上に表現されたリストを評価（つまり実行）する「エバル」部，(3)評価した結果を画面に表示したりファイルに書き込んだりする「プリンタ」部――に分けることができます。

　例えば，“(+ 2 3)”というリストをリーダー部がキーボードから読み込んでメモリー上に展開し，それをエバル部が評価して5という値を得て，プリンタ部がその5を画面に印字します。図3では，“(+ 2 3)”を評価した後，関数定義“(defun add1 (x) (+ x 1))”を読み込み，評価することによって関数add1を定義，さらに“(add1 3)”を読み込み，評価することで4が印字されています(1)。

図3●Lisp処理系の動作イメージ。1行のS式を入力すると直ちに評価して結果が出力される

　言語処理系を一度も作ったことがない人には，どれくらいの長さのプログラムでこのようなものを作れるのかが実感しづらいかも知れません。Lisp処理系は機能をどれくらい作り込むかによって大きくも小さくも作ることができます。今回は，Lisp処理系のベンチマーク用関数として知られる関数takが動作する最低限の構成を，Javaで500ステートメント以内で作成することを目標としました（カコミ記事「Lispのベンチマーク関数tak」を参照）。他の機能を追加していくうちに残念ながら500ステートメントは超えてしまいましたが，1000ステートメントには達していません＊2。

　Lispの開発にJavaを使うメリットはいくつかあります。一つは，メモリー管理部を一切作成せずにJava VMに任せられることです。これにより，面倒なGC（Garbage Collection）＊3の機構を作成する必要がなくなります。またタイプレスなオブジェクトも，Javaのクラスをそのまま使用することで比較的容易に実装できます。