リストについて

昨日に引き続き、またまたネタを日記ブログから持ってくるパターン。 何となく読んだり見たりしている内に頭に思い浮かんだものを書き出した文章の練習みたいなもの。 データ構造としてのリストだったり、もっと抽象的な数珠繋ぎとなった何かについて書いてたり、まとめるために書き出した文章の割に話がまとまっていない。

要素が隣接している必要がない

リストと配列は様々な点で違う。 まずリストは各要素がメモリ上で隣接している必要がない。 つまりリストは配列のように連続的なメモリを取れない状況でコンテナを実現する方法でもある。 細かい要素の確保と廃棄が頻繁に起こるソフトウェアで、あまりメモリが潤沢でない組込み環境を想定する。 また廃棄と確保のサイズが同一のものだとする。 すると廃棄した後の確保が（メモリのコンパクションを行わずとも）確実に行える保証ができる。 具体的に言うと、あるクラス・構造体 A を廃棄した後、A を再び確保しようとした時に必ず確保できる。 よってコンパクションのオーバーヘッドを避ける事ができる（けど割り当てる時には空いてる場所を探すんだからコンパクションを行った方が効率が良いような気がする…）。

もちろんランダムアクセスには弱いので、そこは工夫する必要がある。 例えば循環リストにして頭と尻を繋げれば、最悪 n/2 の時間で目的の位置に辿り着ける。 ただ、輪っかの反対の位置のポインタを保存してすぐ飛べるようにしたり、要素数に比例してポインタの数を 2個、4個、8個 … と増やしていったりと工夫すれば、ほぼ対数時間で（二分探索的に）目的の位置に飛べるような気はする。

要素のようなリスト

次に、これはデータ構造としてのリストとは別だが、要素のようなリストというものが考えられる。 どういう事かというと、例えば関数のリストがあったとして、先頭の関数を呼べば後続の関数が順番に呼ばれるという関数が作れる。

それは構造的にはリストと同じなのだけど、コンテナではなくただの要素（関数）として扱える。 コールグラフから見ればリスト、データ構造としては関数。 関数とリストを組み合わせる事で、ただの要素かと思ったら入り口で何個も連なった要素の先頭ポインタだった、という事ができる。 再帰も同じ構造。

Lisp のコンスセル

今度は Lisp のコンスセルのデータ構造の話。 Lisp のセル1つは CAR 部と CDR 部に分かれていて、ポインタ2つだけで表せる。 Lisp のリストの値というのはリストの先頭のセルなので、メモリ上ではポインタ2つの構造体1つ分で表せられる。 ELIS という Lisp マシンではメモリ・レジスタと呼ばれるものでセル1つ分を表せるらしい。 セル1つはアトムかリストを（参照ではなく）保持する。 つまりアドレスによるメモリの間接参照ではなく、セル1個分の構造体をメモリ・レジスタ上に記憶する。 この構造体の大きさはマシンによって異なるが、大体の内容としては「タグ + データ部」で、タグは「アトムかセルか」「型情報」「ガベージコレクション用の情報」等の情報を保持する。 また、データの呼び出し幅を広げて CDR 部を一気に読み取ってメモリ呼び出しを減らす等、正に Lisp を効率的に実行するためのアーキテクチャといえる。