| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [表紙] | [目次] | [索引] | [検索] [上端 / 下端] [?] |
Lispでは、アトムは単純な方法で記録されている。 現実の実装が単純ではないとしても、理論的には単純である。 たとえば、アトム`rose'は、`r'、`o'、`s'、 `e'の4つの連続した文字として記録されている。 一方で、リストは異なった方法で記録されている。 その機構は同様に単純であるが、その考え方に慣れるには時間がかかる。 リストは一連のポインタ対を用いて記録されている。 ポインタ対の最初のポインタはアトムやリストを指し、 ポインタ対の2番目のポインタはつぎの対やシンボル、 あるいは、リストの終わりを表すnilを指す。
ポインタ自身は、とても単純で、それが指すもののアドレスである。 したがって、リストは一連のアドレス対として記録される。
たとえば、リスト(rose violet buttercup)には3つの要素、 `rose'、`violet'、`buttercup'がある。 コンピュータ内部では、`rose'のアドレスは、 アトム`violet'の場所を示すアドレスを与えるアドレスとともに メモリに記録されている。 （`violet'の場所を示す）アドレスは、 アトム`buttercup'の場所を示すアドレスを与えるアドレスとともに 記録されている。
複雑に聞こえるであろうが、図で表せば簡単である。
___ ___ ___ ___ ___ ___
|___|___|--> |___|___|--> |___|___|--> nil
| | |
| | |
--> rose --> violet --> buttercup
|
図では、各箱は、メモリアドレス形式のLispオブジェクトを保持する コンピュータのメモリを表す。 箱、つまり、アドレスは対になっている。 各矢印は、アトムや他のアドレスの対のアドレスで表されるものを指す。 最初の箱は`rose'のアドレスであり、矢印は`rose'を指す。 2番目の箱は、つぎの箱の対のアドレスであり、 その先頭部分は`violet'のアドレスであり、 2番目の部分はつぎの対のアドレスである。 最後の箱はシンボルnilを指し、リストの終わりを表す。
setqなどの関数で変数にリストを設定すると、 変数には最初の箱のアドレスを設定する。 つぎの式
(setq bouquet '(rose violet buttercup)) |
を評価するとつぎのような状況になる。
bouquet
|
| ___ ___ ___ ___ ___ ___
--> |___|___|--> |___|___|--> |___|___|--> nil
| | |
| | |
--> rose --> violet --> buttercup
|
この場合、シンボルbouquetは、最初の箱の対のアドレスを保持する。 もちろん、シンボルbouquetもアドレスを保持する箱の組で構成され、 その1つには表示名`bouquet'のアドレスが入り、 2番目にはシンボルに結び付けられた関数定義のアドレスが入り、 3番目にはリスト(rose violet buttercup)の最初の箱の対のアドレスが入り、 のように続く。
同じリストを異なる箱表記方法で示すこともできる。
bouquet
|
| -------------- --------------- ----------------
| | car | cdr | | car | cdr | | car | cdr |
-->| rose | o------->| violet | o------->| butter- | nil |
| | | | | | | cup | |
-------------- --------------- ----------------
|
始めの節では、シンボルを箪笥と考えればよいと述べた。 関数定義はある引き出しに入れてあり、値は別の引き出しに入れてあるのである。 関数定義を収めた引き出しの中身を変えることなく、 値を収めた引き出しの中身を変更でき、その逆もそうである。 実際、各引き出しに収められているのは、値や関数定義のアドレスである。 屋根裏部屋でみつけた古い箪笥の引き出しから、宝物を埋めた場所を記した 地図をみつけるようなものである。
（シンボルには、名前、関数定義、値に加えて、その他の情報を記録するための 属性リスト（property list）を収める引き出しもある。 ここでは属性リストについては 説明しないので、節 `Property Lists' in
仮想的な表現をつぎに示す。
箪笥の引き出し 引き出しの中身
---------------------
| |
| シンボル名 | bouquet
| |
---------------------
| |
| 関数定義 | [なし]
| |
---------------------
| |
| 変数の値 | (rose violet buttercup)
| |
---------------------
| |
| 属性リスト | [本書では説明しない]
| |
---------------------
|/ \|
|
シンボルにリストのCDRを設定しても、リスト自体は変わらない。 シンボルはリストを辿ったアドレスを持つだけである （専門用語では、CARやCDRは「非破壊的」である）。 したがって、つぎの式を評価すると
(setq flowers (cdr bouquet)) |
つぎのようになる。
bouquet flowers
| |
| ___ ___ | ___ ___ ___ ___
--> | | | --> | | | | | |
|___|___|----> |___|___|--> |___|___|--> nil
| | |
| | |
--> rose --> violet --> buttercup
|
flowersの値は(violet buttercup)であり、 つまり、シンボルflowersは、violetのアドレスを最初の箱に、 buttercupのアドレスを2番目の箱に持つような箱の対のアドレスを保持する。
アドレスを収めた箱の対をコンスセル（cons cell）とか ドットペアー（dotted pair）と呼ぶ。 コンスセルやドットペアーについて 詳しくは、節 `Dotted Pair Notation' in
関数consは、上に示した一連のアドレスのまえにアドレスの新たな対を加える。 たとえば、つぎの式
(setq bouquet (cons 'lilly bouquet)) |
を評価すると、つぎのようになる。
bouquet flowers
| |
| ___ ___ ___ ___ | ___ ___ ___ ___
--> | | | | | | --> | | | | | |
|___|___|----> |___|___|----> |___|___|---->|___|___|--> nil
| | | |
| | | |
--> lilly --> rose --> violet --> buttercup
|
しかし、つぎの式を評価するとわかるように、 これによりシンボルflowersの値が変更されることはない。
(eq (cdr (cdr bouquet)) flowers) |
は、真を表すtを返す。
再設定しない限り、flowersの値は(violet buttercup)である。 つまり、flowersは、最初の部分にvioletのアドレスを 収めたコンスセルのアドレスを持つ。 さらに、すでに存在するいかなるコンスセルも変更しない。 それらはそのまま存続する。
したがって、LispでリストのCDRを取り出すと、 一連のコンスセルの中のつぎのコンスセルのアドレスを得るのである。 リストのCARを取り出すと、リストの先頭要素のアドレスを得る。 新たな要素をリストにconsすると、 リストのまえに新たなコンスセルを置くのである。 以上がすべてである。 Lispの根底にある構造は、とても単純なのである。
一連のコンスセルの最後のアドレスは何を指すのであろう？ それは空リスト、つまり、nilのアドレスである。
まとめると、Lispの変数に値を設定すると、 変数が参照するリストのアドレスが設定される。
| [ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [表紙] | [目次] | [索引] | [検索] [上端 / 下端] [?] |
flowersにvioletとbuttercupを設定せよ。 このリストにさらに2つの花をコンスし、 この新たなリストをmore-flowersに設定せよ。 flowersのCARに魚を設定せよ。 このとき、more-flowersはどんなリストを持つか？
| [ << ] | [ >> ] | [表紙] | [目次] | [索引] | [検索] [上端 / 下端] [?] |