Lispでのリストは基本データ型ではありません。リストはコンスセル(cons cells)から構築されます(コンスセルとリスト型を参照)。コンスセルは順序つきペアを表現するデータオブジェクトです。つまりコンスセルは2つのスロットをもち、それぞれのスロットはLispオブジェクトを保持(holds)または参照(refers to)します。1つのスロットはCAR、もう1つはCDRです(これらの名前は歴史的なものである。コンスセルとリスト型を参照されたい)。CDRは“could-er(クダー)”と発音します。
わたしたちは、コンスセルのCARスロットに現在保持されているオブジェクトが何であれ、“このコンスセルのCARは、...”のような言い方をします。これはCDRの場合でも同様です。
リストとは互いに連なる(chained together)一連のコンスセルであり、各セルは次のセルを参照します。リストの各要素にたいして1つのコンスセルがあります。慣例によりコンスセルのCARはリストの要素を保持し、CDRはリストをチェーンするのに使用されます(CARとCDRの間の非対称性は完全に慣例的なものである。コンスセルのレベルではCARスロットとCDRスロットは同じようなプロパティーをもつ)。したがって、リスト内の各コンスセルのCDRスロットは次のコンスセルを参照します。
これも慣例的なものですがリスト内の最後のコンスセルのCDRはnilです。わたしたちはこのようなnilで終端された構造を正リスト(proper
list)と呼びます4。Emacs
Lispではシンボルnilはシンボルであり、かつ要素なしのリストでもあります。便宜上、シンボルnilはそのCDR(とCAR)にnilをもつと考えます。
したがって正リストのCDRは常に正リストです。空でない正リストのCDRは1番目の要素以外を含む正リストです。
リストの最後のコンスセルのCDRがnil以外の何らかの値の場合、このリストのプリント表現はドットペア表記(dotted pair
notation。ドットペア表記を参照のこと)を使用するので、わたしたちはこの構造をドットリスト(dotted
list)と呼びます。他の可能性もあります。あるコンスセルのCDRが、そのリストのそれより前にある要素を指すかもしれません。わたしたちは、この構造を循環リスト(circular
list)と呼びます。
ある目的においてはそのリストが正リストか循環リストなのか、あるいはドットリストなのかが問題にならない場合もあります。そのプログラムがリストを充分に辿って最後のコンスセルのCDRを確認しようとしないなら、これは問題になりません。しかしリストを処理する関数のいくつかは正リストを要求し、ドットリストの場合はエラーをシグナルします。リストの最後を探そうと試みる関数のほとんどは循環リストを与えると無限ループに突入します。
ほとんどのコンスセルはリストの一部として使用されるので、わたしたちはコンスセルで構成される任意の構造をリスト構造(list structure)と呼びます。