learning lisp: list (appendix)

[TAKAHASHI Naoto <ntakahas@m17n.org>]

実はリストというのは dotted pair のネストされたものに過ぎません。
(a) は (a . nil) , (a b) は (a . (b . nil)) , (a b c) は 
(a . (b . (c . nil))) とそれぞれ同等です。

(equal '(a b c) '(a . (b . (c . nil)))) => t

別の例を出します。ちょっとややこしくなります。

(equal '((a b) (c d)) '((a . (b . nil)) . ((c . (d . nil))))) => t

ここまで来ると、実はこれまで説明してきた car, cdr, cons の動作に首尾一
貫性が見えてきます。セミコロンの後にコメントを付けます。

(car '(a)) ; イコール (car '(a . nil))
=> a ; ピリオドの左側

(cdr '(a)) ; イコール (cdr '(a . nil))
=> nil ; ピリオドの右側

(car '(a b)) ; イコール (car '(a . (b . nil))) 
=> a ; 外側のピリオドの左側

(cdr '(a b)) ; イコール (cdr '(a . (b . nil)))
=> (b) ; イコール (b . nil) すなわち外側のピリオドの右側

(cons 'x nil) ; イコール (cons 'x '())
=> (x) ; イコール (x . nil) すなわち第1引数と第2引数の dotted pair

(cons 'x '(a)) ; イコール (cons 'x '(a . nil))
=> (x a) ; イコール (x . (a . nil)) すなわち第1、第2引数の dotted pair

car も cdr も cons も、引数が何であろうと結局やっていることは首尾一貫
しているということがおわかりでしょうか。

以下は余談です。

余談その1

ちょっとうろ覚えですが、car は content of address part の略で、cdr 
は content of data part の略だったはずです。これは昔の IBM のハードウェ
アで、レジスタの address part と data part にそれぞれ別のデータを入れ
て一つの dotted pair としていたことに由来します。

余談その2

普通 dotted pair というと、car 部分も cdr 部分もアトムのものを指します。
ですから (a . b) は dotted pair ですが、 (a . nil) は一般には (a) と書
くので dotted pair とはあまり言いません。同様に ((a b) (c d)) も普通は 
dotted pair とは言いません。一方、dotted pair よりもうちょっと意味の広
い言葉として cons cell (コンス・セル) というのがあります。car 部分と 
cdr 部分を持つものはすべて cons cell です。(a . b) はもちろん、(a) も
((a b) (c d)) も cons cell です。

余談その3

普通、リストの最後は nil になっています。たとえば (a b c) を詳しく書く
と (a . (b . (c . nil))) のようになります。が、最後が nil でないリスト
も作れます。

(cons 'a (cons 'b 'c)) => (a b . c)

以前守岡さんが書いてくれたように、このようなリストは malformed list と
呼ばれているようですが、差別的なにおいがして好きではありません。むしろ
「最終要素が nil でないリストの方々」と呼ぶべきでしょう。

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/