5.1 Lists and Cons Cells

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)と呼びます。