5.1 リストとコンスセル

Lispでのリストは基本データ型ではありません。リストはコンスセル(cons cells)から構築されます(Cons Cell Typeを参照)。コンスセルは順序つきペアを表現するデータオブジェクトです。つまりコンスセルは2つのスロットをもち、それぞれのスロットはLispオブジェクトを保持(holds)または参照(refers to)します。1つのスロットはCAR、もう1つはCDRです(これらの名前は歴史的なものである。Cons Cell Typeを参照されたい)。CDRは“could-er(クダー)”と発音します。

わたしたちは、コンスセルのCARスロットに現在保持されているオブジェクトが何であれ、“このコンスセルのCARは、...”のような言い方をします。これはCDRの場合でも同様です。

リストとは互いに連なる(chained together)一連のコンスセルであり、各セルは次のセルを参照します。リストの各要素にたいして1つのコンスセルがあります。慣例によりコンスセルのCARはリストの要素を保持し、CDRはリストをチェーンするのに使用されます(CARとCDRの間の非対称性は完全に慣例的なものである。コンスセルのレベルではCARスロットとCDRスロットは同じようなプロパティーをもつ)。したがって、リスト内の各コンスセルのCDRスロットは次のコンスセルを参照します。

これも慣例的なものですが、リスト内の最後のコンスセルのCDRはnilです。わたしたちはこのようなnilで終端された構造を、真リスト(true list)と呼びます。Emacs Lispではシンボルnilはシンボルであり、かつ要素なしのリストでもあります。便宜上、シンボルnilはそのCDR(とCAR)にnilをもつと考えます。

したがって真リストのCDRは、常に真リストです。空でない真リストのCDRは、1番目の要素以外を含む真リストです。

リストの最後のコンスセルのCDRがnil以外の何らかの値の場合、このリストのプリント表現はドットペア表記(dotted pair notation。Dotted Pair Notationを参照のこと)を使用するので、わたしたちはこの構造をドットリスト(dotted list)と呼びます。他の可能性もあります。あるコンスセルのCDRが、そのリストのそれより前にある要素を指すかもしれません。わたしたちは、この構造を循環リスト(circular list)と呼びます。

ある目的においてはそのリストが真リストか、循環リストなのか、ドットリストなのかが問題にならない場合もあります。そのプログラムがリストを充分に辿って最後のコンスセルのCDRを確認しようとしないなら、これは問題になりません。しかしリストを処理する関数のいくつかは真リストを要求し、ドットリストの場合はエラーをシグナルします。リストの最後を探そうと試みる関数のほとんどは、循環リストを与えると無限ループに突入します。

ほとんどのコンスセルはリストの一部として使用されるので、わたしたちはコンスセルで構成される任意の構造をリスト構造(list structure)と呼びます。