[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

2.3.6 コンスセルとリスト型

コンスセル(cons cell)とは、 CARスロットおよびCDRスロットと呼ばれる 2つのポインタから成るオブジェクトです。 各スロットは、任意のLispオブジェクトを指すことができます。 また、現在CARスロットが指しているオブジェクトがなんであれ、 『コンスセルのCARは』といったいい方をします。 CDRについても同様です。

リスト(list)はコンスセルが連なったものであり、 各コンスセルのCDRスロットは、 後続のコンスセルを指すか空リストを指します。 リストに作用する関数については、See section 5. リスト。 ほとんどのコンスセルは、リストの一部分として使われるので、 リスト構造(list structure)という用語は、 コンスセルから成る任意の構造のことを意味します。

CARやCDRという名称は、Lispの歴史に由来します。 最初のLispはIBM 704で動作していました。 この計算機では、ワードを2つの部分、『番地』(address)部分、 『減数』(decrement)部分と呼ばれるものに分けていました。 CARはレジスタの番地部分の内容(Contents of Address Register)を 取り出す命令であり、 CDRはレジスタの減数部分の内容(Contents of Decrement Register)を 取り出す命令でした。 一方、『コンスセル』という名称は、 これらを作成する関数consからきています。 この関数名は、その目的、セルを作る(construction of cells)からきています。

コンスセルはLispの核心なので、 『コンスセルではないオブジェクト』に対する名称もあります。 これらのオブジェクトをアトム(atoms)と呼びます。

リストの入力構文と表示表現は同一です。 開き括弧で始まり、任意個の要素、閉じ括弧で終えます。

読み取り時には、括弧の内側の各オブジェクトが、 リストの各要素になります。 つまり、これらの要素からなるコンスセルを作ります。 コンスセルのCARスロットで要素を指します。 同じコンスセルのCDRスロットで、 リスト上のつぎの要素を保持している、 リストのつぎのコンスセルを指します。 最後のコンスセルのCDRスロットはnilを指します。

リストは、コンスセルを1対の箱で表して図示できます。 (Lispリーダがこのような図表示を読むことはない。 人間や計算機が理解できるテキスト表記と違い、 箱を用いた図表示は人間だけが理解できる。) つぎの図は、3つの要素から成るリスト(rose violet buttercup)を表します。

 
    --- ---      --- ---      --- ---
   |   |   |--> |   |   |--> |   |   |--> nil
    --- ---      --- ---      --- ---
     |            |            |
     |            |            |
      --> rose     --> violet   --> buttercup

この図で、各箱は、任意のLispオブジェクトを指すことができるスロットを表します。 箱の対でコンスセルを表します。 各矢印は、アトムや他のコンスセルであるLispオブジェクトを指すポインタです。

この例では、最初のコンスセルのCARを表す最初の箱は、 rose(シンボル)を指しています。 あるいは、rose(シンボル)を『含んでいる』ともいいます。 最初のコンスセルのCDRを表す2番目の箱は、 つぎの1対の箱、2番目のコンスセルを指しています。 2番目のコンスセルのCARはvioletであり、 このコンスセルのCDRは3番目のコンスセルです。 3番目の(最後の)コンスセルのCDRは、nilです。

同じリスト(rose violet buttercup)を 別の方法で図表示するとつぎのようになります。

 
 ---------------       ----------------       -------------------
| car   | cdr   |     | car    | cdr   |     | car       | cdr   |
| rose  |   o-------->| violet |   o-------->| buttercup |  nil  |
|       |       |     |        |       |     |           |       |
 ---------------       ----------------       -------------------

内部に要素を持たないリストは、空リスト(empty list)です。 これはシンボルnilと同一です。 いいかえれば、nilはシンボルでもありリストでもあります。

Lispの構文で書き表したリストの例を示します。

 
(A 2 "A")            ; 3要素のリスト
()                   ; 要素を持たないリスト(空リスト)
nil                  ; 要素を持たないリスト(空リスト)
("A ()")             ; 文字列"A ()"だけの1要素のリスト
(A ())               ; Aと空リストから成る2要素のリスト
(A nil)              ; 上と同じ
((A B C))            ; 1要素のリスト
                     ;   (その要素は3要素のリスト)

リスト(A ())や、これと同じ(A nil)を 箱と矢印で書くとつぎのようになります。

 
    --- ---      --- ---
   |   |   |--> |   |   |--> nil
    --- ---      --- ---
     |            |
     |            |
      --> A        --> nil

2.3.6.1 ドット対記法  An alternative syntax for lists.
2.3.6.2 連想リスト型  A specially constructed list.



This document was generated by Takeshi Sasaoka on , 21 2002 using texi2html