ファイヤープロジェクト
コンス
2003-09-23T18:30+09:00   matsu
Lispのリストはコンスと呼ばれる一対のポインタで構成される.このことを詳しく見ていくと,Lispにおけるリストをもう少し深く理解できる.
コンスとは二つのポインタの組である.言い替えれば一対のポインタである.Lispにおけるリストはこのコンスを使用して実装されている.
> (setf alist '(a))
(A)
> (car alist)
A
> (cdr alist)
NIL
上記の一つの要素aからなるリストalistを箱表記と呼ばれる表記法で以下に示す.
真中の「仕切り」のある長方形がコンスである.仕切りによって二つの部分に分かれているが,この二つの部分がそれぞれポインタを意味している.一方はaを差し,もう一方はnilを差している.前者はcar部と呼び,後者はcdr部と呼ぶ.そしてalistがこのコンスへのポインタとなっている.次に2要素からなるリスト(a b)を箱表記で以下に示す.
一つめのコンスのcdr部が二つめのコンスを指している.
> (setf alist2 '(a b))
(A B)
> (car alist2)
A
> (cdr alist2)
(B)
> (car (cdr alist2))
B
> (cdr (cdr alist2))
NIL
出力が(B)となっている式とBとなっている式に注意する.(cdr alist2)は一つ目のコンスのcdr部が二つ目のコンスを指している事を示し,(car (cdr alist2))は二つ目のコンスのcar部がBを指していることを示している.これは要素数3のリストで試すとよりはっきりする.
> (setf alist3 '(a b c))
(A B C)
> (cdr alist3)
(B C)
> (car (cdr alist3))
B
このように(cdr alist3)はalist3のcdr部が指しているコンスから連鎖的にさらに先のコンスも調べ,リストとして返す.すなわちリストのcar値はそのリストの最初のコンスのcar部の指すオブジェクトであり,リストのcdr値はそのリストの最初のコンスのcdr部が指すコンスを最初のコンスとするリストである.
前節に示した,リストの各要素がリストでないリストをフラットリストという.リストの要素をさらにリストとする入れ子リストもある.すなわちcar部がコンスを指すことができる.
上図で示したリストalist3は(a (b1 b2) c)である.alist3の第二要素はリスト(b1 b2)である.もちろん例えばb1をリストに置き換えることもできる.
Lispにおけるデータ型はアトムかコンスのどちらかに属する.すなわちコンスでないものはアトムである.先の図で示してきたa,b,cなどの箱になっていないものがアトムである(※1).一方リストはコンスの連結である.したがって,式の上ではカッコにくくられていないものがアトムで,カッコに括られているものはリストでありコンスの連結である.nilはアトムでありコンスではない(※2).ただしnilは特殊でコンスでないにもかかわらずリストである(ややこしい).
※1 アトムにはシンボル,配列,ベクタなどがある
※2 nilは唯一のnull型のオブジェクトである
matsu(C)
Since 2002
Mail to matsu