9. リストはどのように実装されているか

Lisp では、アトムは直接的な方法で記録される。たとえ現実の実装方法が直接 的ではなかったとしても、理論上は直接的である。例えば `rose' という アトムは四つの隣接する文字 `r', `o', `s', `e' として 記録される。一方、リストはもっと異なる方法で記録される。メカニズムとして は同じくらい単純なのだが、そのアイディアに慣れるのにはちょっと時間がかか るかもしれない。リストは、ポインタのペアの列として記録される。この列の中 で、各々のペアの一番目のポインタは、あるアトムか、もしくは他のリストを指 している。そして、二番目のポインタは次のペアか、シンボル nil を指 している。nil の場合はリストの終わりということである。

ポインタそれ自身は、指されている対象の極めて単純な電気的な住所だと言える。 従って、リストも電気的な住所の列として記録されていると言える。例えば、 (rose violet buttercup) というリストは `rose', `violet', `buttercup' という三つの要素を持っている。計算機の中 では、`rose' の電気的な住所は、ある計算機のメモリのセグメントに `violet' というアトムの電気的な住所を示すアドレスに並んで記されてい る。そしてこっちの住所 (`violet' の場所を示すもの) は `buttercup' というアトムの電気的な住所を示すアドレスに並んで記され ている。

このように書くと何やら複雑に思えるかもしれないが、図に書いてみれば簡単に 理解出来るだろう。

___ ___ ___ ___ ___ ___ |___|___|--> |___|___|--> |___|___|--> nil | | | | | | --> rose --> violet --> buttercup

上の図の中で、各々の箱は Lisp オブジェクトを保持する計算機のメモリのワー ドを表現している。これは普通はメモリアドレスの形をしている。これらの箱、 即ち住所は、ペアになっている。各々の矢印は、そのアドレスを持つ住所を指し ている。その場所には、アトムか他のアドレスのペアがある。最初の箱は `rose' の電気的な住所であり、矢印は `rose' を指している。二番 目の箱は次の箱のペアを指しており、こっちのペアの一番目の箱は `violet' の住所、そして二番目の箱はまた次のペアのアドレス、という具 合になっている。そして最後の箱は、シンボル nil を指している。これ は、リストの最後を示している。

setq などの関数によってある変数がこのリストにセットされた場合、こ のリストの先頭の箱のアドレスがこの変数にセットされる。従って、

(setq bouquet '(rose violet buttercup))

というＳ式を評価すると、以下のような状況になる。

bouquet | | ___ ___ ___ ___ ___ ___ --> |___|___|--> |___|___|--> |___|___|--> nil | | | | | | --> rose --> violet --> buttercup

この場合、シンボル bouquet が最初のペアのアドレスを持つことになる。 実際、シンボル bouquet は幾つかのアドレスボックスから出来ている。 一つは表示される単語の `bouquet' の住所であり、二つ目はこのシンボル に定義されている関数のアドレスであり、三つ目はリスト (rose violet buttercup) というリストの最初のアドレスボックスのペアのアドレスであり、 というふうである。

同じリストをちょっと箱の書き方を変えた別のイラストで描いてみると、次のよ うになる。

bouquet | | -------------- --------------- ---------------- | | car | cdr | | car | cdr | | car | cdr | -->| rose | o------->| violet | o------->| butter- | nil | | | | | | | | cup | | -------------- --------------- ----------------

最初の方のセクションでは、シンボルを引き出しが幾つかある整理棚だと見倣す と良いと書いた。関数定義がある引き出しに入っており、値は他の引き出しに入っ ている、という説明だ。値がある引き出しの中身は他の引き出しの中身に影響を 与えずに変えることが出来るし、その逆も可能だとも書いた。実際には、各々の 引き出しに入っているのは値や関数定義のアドレスである。これは、屋根裏部屋 で古い棚を見つけて、その引き出しの一つを空けてみると宝が埋まっている場所 が描かれた地図が見つかった、ということに例えられよう。

(名前だけではなく、シンボルの定義や変数の値、また、その他の情報を取り出 すための 属性リスト (property list) の「引き出し」というもの もある。属性リストについてはここでは説明はしない。section `Property Lists' in The GNU Emacs Lisp Reference Manual, を参照のこ と。)

次は空想上の整理棚の絵である。

Chest of Drawers Contents of Drawers --------------------- | | | symbol name | bouquet | | --------------------- | | | symbol definition | [none] | | --------------------- | | | variable value | (rose violet buttercup) | | --------------------- | | | property list | [not described here] | | --------------------- |/ \|

もし、シンボルがあるリストの CDR にセットされたなら、そのリスト自身 は変化しない。そのシンボルは単にそのリストのアドレスを持つようになるだけ である。(専門用語では、CAR や CDR は 「非破壊的 (non-destructive)」 であると言う。) 従って、次のＳ式を評価す ると、

(setq flowers (cdr bouquet))

以下のような状況が生ずる。

bouquet flowers | | | ___ ___ | ___ ___ ___ ___ --> | | | --> | | | | | | |___|___|----> |___|___|--> |___|___|--> nil | | | | | | --> rose --> violet --> buttercup

flowers の値は (violet buttercup) であるが、これはシンボル flowers がアドレスボックスのペアのアドレスを持ったということである。 このペアの最初の箱には violet のアドレスがあり、二番目の箱には buttercup のアドレスが入っている。

アドレスボックスのペアはコンスセル (cons cell) もしくは ドット対 (dotted pair) と呼ばれる。section `Cons Cell and List Type' in The GNU Emacs Lisp Reference Manual, 及び section `Dotted Pair Notation' in The GNU Emacs Lisp Reference Manual, にコンスセルとドット対についてのより詳しい 情報がある。

関数 cons は、上に述べたようなアドレスの列の先頭に新しいアドレス ペアを付け加える。例えば、

(setq bouquet (cons 'lily bouquet))

を評価すると

bouquet flowers | | | ___ ___ ___ ___ | ___ ___ ___ ___ --> | | | | | | --> | | | | | | |___|___|----> |___|___|----> |___|___|---->|___|___|--> nil | | | | | | | | --> lily --> rose --> violet --> buttercup

という状況になる。この操作ではシンボル flowers の値を変更している わけではない。これは次を評価することで確かめられる。

(eq (cdr (cdr bouquet)) flowers)

これは、t を返すはずだ。再設定されない限り、flowers はずっ と (violet buttercup) という値を持ったままである。つまり、最初の アドレスが violet であるコンスセルのアドレスを持っているというこ とだ。また上の操作は、既に存在しているコンスセルを変えたりはしない。そ れらは全てそのままである。

従って、Lisp でリストの CDR を得るには、単にその列の隣りのコンスセ ルのアドレスを得ればよく、また CAR を得るには、単にそのリストの最初 の要素のアドレスを得ればよい。更に、リストに新しい要素を cons す るには、リストの先頭に新しいコンスセルを加えればよい。以上がこの話題に 関する全てである。Lisp の裏側は驚くほど明解で単純のなのだ。

では、コンスセルの列の最後のアドレスはどこに関連づけられているのか？ こ れは nil, 即ち、空リストである。

まとめると、Lisp の変数にある値にセットされる時は、その変数には、その変 数が見にいくリストのアドレスが与えられるというわけである。

9.1 練習問題

List についての練習問題

9.1 練習問題

flowers に violet と buttercup をセットしなさい。ま た、このリストに更に二つの花を consし、新しく出来たリストを more-flowers にセットしなさい。flowers の CAR に魚の 名前をセットしなさい。この時、more-flowers のリストの中身はどうな るか。