初めての人のためのLISP - 第8講 Lisp御本尊のお出まし

初めての人のためのLISP[増補改訂版]のメモです。
最初:初めての人のためのLISP (第1講-第5講) - もうカツ丼でいいよな
ボチボチ知らないことが増えてきてそんな簡単には進まなくなってきた。

Lisp御本尊

とりあえずこんな感じの箱を考える。
左側をcar部、右側をcdr部、全体をセルと呼ぶ。

そしてメモリ構造として並んだセルに0から順に番地番号が付いているようなものを想定する。
セルのcar部とcdr部は各々メモリ全体の番地を表すのに十分なだけのビットからなる。ここではメモリ全体の番地+αを扱えるだけのビットを備えているとする。

Lispポインタ

セルのcar部とcdr部は他のセルの番地を指すことが可能なので(それだけのビット数を備えると仮定したので)、Lispポインタと呼ぶことができる。
car部とcdr部はそれぞれ次のような構造を持つ。

ここでの「タグ」というのが先程の「+α」に相当している。よって番地部はそれだけでメモリ中のどの番地も指すために十分なビットを備える。
S式はLispポインタである。以下に見るように、S式はLispポインタにより表現できる。

nilを表すLispポインタ

nilはタグのビットを全て0とすることで表現する(必然性はない)。また一般的には番地部も全て0とする。nilを表すLispポインタは次のように書く。

数を表すLispポインタ

タグ部に数を表すLispポインタであることを示すビットパターンを入れる。具体的なビットパターンが何であるかは重要ではないのでここではnとする。数自体は番地部に入れる。当然だがこのような場合番地部に入る情報は番地を指していない。

シンボルを表すLispポインタ

これまで「名前」などと呼称していたものはシンボルと呼ぶ。シンボルは単なる文字列ではなく、それ自体実体を持つデータ構造であり、文字列以外の諸々の情報も付随している。そのため、番地部に全ての情報を詰め込むことはできない。シンボルを表すLispポインタは、シンボルの実体の場所を示すものである。タグ部にはシンボルを表すビットパターンsが、番地部にはシンボルの実体を指す番地が入る。

ただし簡略のため、あたかも番地部にシンボルが入っているかのような描き方をする。

リストを表すLispポインタ

リストは当然ながら一つのLispポインタには収まらないので、シンボルのように番地部でリストの実体を指すようなLispポインタを用いて表現する。

リストの実体はシンボルとは違い分かりやすい形をしている。

(S1, S2, S3, ... , Sn)

というリストの実体はn個のセルを用いて次のように表現する。

ここで各セルのcar部はS1, S2,..., Snに対応するLispポインタ表現とする。cdr部のLispポインタのタグ部にはリストを示すタグとしてlというビットパターンが入っており、番地部は次の要素が格納されているセルを指す番地が入っている。最後のセルのcdr部はnilとなる。各セルは連続している必要はない。
各セルのcdr部のタグ部にリストであることを示すタグが付いていることに注目する。この構造により、リストのcarを取ることがリストを表すLispポインタのcar部をとることに対応し、リストのcdrをとることがLispポインタのcdr部をとることに完全に対応する。

その他

タグは必要がなければ省略して描く。
リストは必要がなければ実体だけを描く。

セルでS式を表すということの意味

carやcdrという関数はセルのcar部やcdr部を取り出すということに対応する(上記リストの項で述べたように)。
null、atomはLispポインタのタグを見るだけで値を返せる。
consは新しいセルのcar部とcdr部にconsの対応する引数を入れ、そのセルを指すLispポインタをlタグつきで返す。
eqは2つの引数のLispポインタのタグと番地が両方等しいか否かを確認する。

リストの見た目が等しければtを返すequal

eqはLispポインタのタグと番地の両方が等しい時にtを返すので、リストを表すLispポインタでは見た目が同じでも番地が違うためにnilとなることがある。
アトム同士の比較ならば見た目が同じならばtになる(名前は文字が同じなら同一=見た目の同じシンボルに対応するLispポインタ表現は一つ。第4講参照)ので、アトムに分解して比較すればよい。

(defun equal (x y)
       (cond ((eq x y) t) ; eqで等しくなるなら終了
             (t (and (consp x) (consp y)) ; xとyがどちらもリストなら
                (and (equal (car x) (car y))     ; carとcdrに分解してそれぞれに
                     (equal (cdr x) (cdr y)))))) ; 再びequalを適用する(再帰)

ドット記法

consは新しいセルのcar部とcdr部にconsの2つの引数をそのまま入れ、そのセルを指すLispポインタをlタグ付きで返す。そのため、リストのLispポインタ表現との整合性を保つためには、cdr部にはリストかnilが来る必要がある。第4節でconsの第2引数はnilかリストでなければならないとしたのはこのためである。
しかし、consの第2引数にアトムを入れてもエラーにはならない。consの第2引数がアトムの場合、ドット対と呼ばれるものが返る。

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

ドット対は一つのセルに対応し、ドットがセルの仕切りに対応する。
リストはドット対により表現できる。この表現はセルによるリストの表現に対応する。

(list 'a 'b 'c) ;=> (a . (b . (c . nil)))

ただし、ドット対の右側にnilが来た時は.とnilを、開き括弧が来たときは.と括弧を省略できる。すると、ドット対によるlistの表現

(a . (b . (c . nil)))

がこれまでのlistの表現(要素を並べて括弧でくくったもの)

(a b c)

に等しくなる。

リストのトップレベルに指定した要素があるか調べる関数member

リストyのトップレベルを走査し、要素xがあればそこから後ろの要素をを返す。

(defun member (x y)
       (cond ((null y) nil) ; yを全部調べてしまったらnil
             ((eq x (car y)) y) ; carに等しい要素がでてきたらy
             (t (member (x (cdr y)))))) ; yのcdrに対し再帰

tの代わりに残ったyを返しているのはnil以外は全てtと見なされることを利用している。このようにt以外の何らかの情報を返すことで応用がきかせられるようにしている関数は多い。

連想リスト

ドット対のリストを使うとシンボルと値を対応させられる。

(setq dict '((unum . 1) (duo . 2) (tria . 3)))

このようなリストを連想リスト(association list)またはalistと呼ぶ。
alistからは次のassoc関数で要素を取り出せる。

(defun assoc (x y) ; alistのyからシンボルxを含むドット対を取り出す
       (cond ((null y) nil) ; 辞書の最後まで見てなかったらnil
             ((eq x (caar y)) (car y)) ; 先頭のドット対のcarとxが等しければドット対を返す
             (t (assoc x (cdr y))))) ; 辞書のcdrに対し再帰