コンス

コンスは，car部とcdr部の$2$つの構成要素を持つ構造体である． コンスは，基本的には次のように表記される．

(《car部》.《cdr部》)

しかし，cdr部が空リストの場合は，単に

(《car部》)

と標準的に表記される． 例えば，次のものはいずれもcar部が記号 a，cdr部が空リストのコンスを表す．

(a . ())
(a)

リストとは，コンス・データのつながったデータ構造で， cdr部を順にたどってゆくと空リストで終るものを指す． 途中の各コンスのcar部の内容を，そのリストの“要素”といい， 最初のコンスのcar部の内容をそのリストの第$1$要素， 次のコンスのcar部の内容を第$2$要素というように呼ぶ． リストは，標準的には次の形式で表記される．

(《要素$_1$》《要素$_2$》$\cdots$《要素$_n$》)

これは，以下のようにも入力できる．

(《要素$_1$》. (《要素$_2$》$\cdots$ . (《要素$_n$》)$\cdots$))
(《要素$_1$》. (《要素$_2$》$\cdots$ . (《要素$_n$》. ())$\cdots$))

cdr部を順にたどってゆくと空リスト以外のもので終わる場合は， そのデータ構造をドット・リストと呼ぶことがある． ドット・リストは標準的に次の形式で表記される． ここで， 《末尾》 はコンスと空リスト以外のデータである．

(《要素$_1$》《要素$_2$》$\cdots$《要素$_n$》.《末尾》)

これは，以下のようにも入力できる．

(《要素$_1$》. (《要素$_2$》$\cdots$ . (《要素$_n$》.《末尾》)$\cdots$))