はじめに
今回は、NuでLisp風プログラミングを学んでみましょう。LispはFORTRANにつぐ古い言語ですが、Rubyをはじめ現在使われているたくさんの言語に大きな影響を与えています。Lispの特徴としてよく言われるものは、
- S式
- 再帰呼び出し
- 高位関数
- 動的言語
- Garbage Collection
- マクロ
などがあげられます。「再帰呼び出し」「高位関数」「動的言語」「Garbage Collection」はLispが生まれた時点では極めて特徴的でしたが、現在の言語では当たり前になってきています。そこで、今回はS式を中心にLispプログラミングについて説明していきます。
前回の記事
S式（リスト）
S式の概要は前回説明しましたが、S式は定数やシンボル、S式自体を並べ、()で括ったものです。ここで重要なのは、S式はS式を要素として持てるということです。従って、S式ではプログラムをはじめ、いろいろなデータ構造を表す事ができます。
例えばHTMLはHTML要素を並べることで構成され、HTML要素は開始タグ、内容、終了タグでできていますが、内容にはさらにHTML要素（子要素）を含む事ができます。このHTMLもS式で表せます。
<html>
<body>
<h1> Lisp </h1>
<table>
<tr><td>1</td> <td>lisp</td></tr>
<tr><td>2</td> <td>scheme</td></tr>
</table>
</body>
</html>
(html (body
(h1 “Lisp”)
(table
(tr (td 1) (td “lisp”))
(tr (td 2) (td “scheme”)))))
S式の内部構造
S式は配列のようにメモリーエリアの連続したデータ構造ではなく、下の図のように要素と要素をポインターでつないでいるので、新しい要素の挿入や削除が効率的に行えます（JavaのLinkedListクラスにあたります）。さらに、ポインターが同じ場所を指す事で簡単にデータを共有することもできます。
また、下の図のようにLispでは2つのポインターが入るセル（Cell）単位でメモリーを管理しています。NuではNuCellというクラスがこのS式（セル）に対応しています。
慣れないうちは、S式を操作する際はこの図を紙に書いたり、頭に浮かべたりしながらプログラムすると良いと思います。また、()で括られたS式のことをリストと呼ぶ事もあります。
ちなみにLispという名前は「List Processor」から来ています。
S式を扱う関数
リスト（S式）の最初の要素を取り出すのが car関数（オペレータ）です、また最初の要素を除いたリストを戻すのが cdr関数（オペレータ）です。これらの関数はセルの左側、右側の値を取り出しているだけです。
$ nush % (car '(a b c)) a % (cdr '(a b c)) (b c)
新たにセルを作るには cons関数を使います、
% (cons 'a ()) (a) % (cons 'a '(b)) (a b)
またリストを作成する事は多いので、リストを作る list関数も用意されています。
% (list 'a 'b) (a b) % (list 'a '(b)) (a (b))
(list a b) は (cons a (cons b ())) と等価です。
