次へ　前へ　目次へ　佐々木将人の個人ページへ

2　Lispの内部構造

　竹内郁雄先生の「はじめての人のためのLISP」では，Lispの御本尊として紹介されている話です。
　Lispにおいては，プログラムとデータの区別はありません。どちらも同じ形式で内部で保存されます（もしくは同じ形式で保存されているかのようにふるまいます）。この単純さが，「何か一連の文字の塊を１個読み込み、「評価」と言って一定の規則に基づいて処理をし、その結果を返します。その繰り返しです。」がLispの基本であると説明できてしまうことにつながります。その単純さを具体的に見ていきます。

　まず記憶領域を２つ組み合わせたものを１つの単位として扱います。これをcons cellもしくは単にcellと呼んでいます。
　「何か一連の文字の塊」が ( で始まると，read関数は，このcons cellを用意します。
　一般的なLispの本では，cons cellを次のように図示するのが通例です。

　┌─┬─┐　
　│　│　│
　└─┴─┘
　( の次に文字アトム a が来たとしましょう。
　アトムなので a 自体は，アトムの専用領域に収納され（そしてある種のデータベースとなって，同じアトムは複数存在しないよう仕掛ける）そこへのポインターがcons cellの前半部に収納されます。
　これを次のように図示することにします。
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　　a
　a の次に ) が来たとします。
　上のcons cellに入れるべきものがない……ということでたいていのLispの本では斜線を引きます。
　（なお，ここではできるだけASCII文字で表現するという方針で斜線を引くのではなく，斜線を示す文字を入れています。）
　┌─┬─┐
　│・│＼│
　└│┴─┘
　　↓
　　a
　ということで (a) は，内部ではこういうように格納されているのでした。

　ちなみに，内部構造を示すのに，この図を書かなければならないとなると，場所も取りますし，結構大変です。
　そこで，この内部構造に忠実な表現というのも別途存在します。
　それが
　(a . NIL)
　です。（NILはnilでもかまいません。）
　一般的には ( 前半部 . 後半部 ) という形式です。( の後や ) の前の空白は必須ではありません（＝読み飛ばされる）が，前半部と後半部を区切る . （ピリオド）の前後には空白が必須です。空白がないと意味が変わってしまいます。
　ちなみにこの表現を「ドット対（dotted pair）」による表現と呼んでいます。

　別の例です。
　「何か一連の文字の塊」が ( で始まると，read関数は，このcons cellを用意するのですが，
　┌─┬─┐　
　│　│　│
　└─┴─┘
　その次も ( だと，リストということですから，cons cellをもう１つ用意し，最初のcons cellの前半部にもう１つのcons cellへのポインターを収納します。
　これはこのような図になります。
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　┌─┬─┐
　│　│　│
　└─┴─┘
　 　( 2つの後に a が続くと
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　　a
　 その次に ) が来ると，a が前半部に入っているcons cellの後半部にNILを入れ，
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　┌─┬─┐
　│・│＼│
　└│┴─┘
　　↓
　　a
　 さらに ) が続くと，最初のcons cellの後半部にNILを入れることになります。
　┌─┬─┐
　│・│＼│
　└│┴─┘
　　↓
　┌─┬─┐
　│・│＼│
　└│┴─┘
　　↓
　　a
　ドット対による表現だと ((a . NIL) . NIL) となりますが，一般的な表現だと ((a)) になります。
（なお，ドット対による表現では . の前後の空白は省略できないとしましたが，( や ) などに続く場合には省略可能です。より正確には「区切り文字」と呼ばれる文字についてはその一文字で何らかの意味を持つため，前後に . がなくても意味が変わらないため省略可能です。）

　もう一つ別の例。
　( a と続いて，その次に b が来た場合。 
　┌─┬─┐
　│・│　│
　└│┴─┘
　　↓
　　a
　このcons cellの後半部には b へのポインターは収納できません。というのは，リストというのは長さが固定されていないので，b の後にさらにリストやアトムが続いた時に困ってしまうからです。というので，別のcons cellを用意して，そこへのポインターを後半部に収納します。その上で，新しいcons cellの前半部に b を収納します。
　┌─┬─┐　┌─┬─┐
　│・│・─→│・│　│
　└│┴─┘　└│┴─┘
　　↓　　　　　↓
　　a 　　　　　b
　( a b の次に c が来て，さらに ) が続くとこうなります。
　┌─┬─┐　┌─┬─┐　┌─┬─┐
　│・│・─→│・│・─→│・│＼│
　└│┴─┘　└│┴─┘　└│┴─┘
　　↓　　　　　↓　　　　　↓
　　a 　　　　　b 　　　　　c
　ドット対による表現だと，(a .(b .(c . NIL))) となりますが，一般的な表現では (a b c) です。

　繰り返しになりますが，Lispではプログラムとデータの区別をせず，このような形式で統一的に扱い，「何か一連の文字の塊を１個読み込み、「評価」と言って一定の規則に基づいて処理をし、その結果を返します。その繰り返しです」という単純な原理でコンピューターを動作させることを可能としているのです。

　なお，Lispの内部構造を記述できるドット対ですが，まれに，内部構造を記述しきれない場合があります。その典型例が
　　┌─────────────┐
　　↓　　　　　　　　　　　　　│
　┌─┬─┐　┌─┬─┐　┌─┬│┐
　│・│・─→│・│・─→│・│・│
　└│┴─┘　└│┴─┘　└│┴─┘
　　↓　　　　　↓　　　　　↓
　　a 　　　　　b 　　　　　c
のように，ループを形成するものです。通常はこういうことにはならないのですが，Lispではこの内部構造に手を入れることも可能になっているので，作業次第ではこういう内部構造も作られてしまいます。そしてこれをprintすると，(a b c a b c a ……) と止まらなくなってしまいます。（処理系によっては，こういうループを感知して停止させてしまうものもありますが。）このパターンはドット対でも内部構造を正確には表現できません。

cons cellの前半部を返す関数……car

　引数にとったリストのcons cellの前半部が何かを返す関数です。返す値はリストの場合もありますし，アトムの場合もあります。
　(a . (b . (c . NIL))) であれば，a を，((a . NIL) . (b . (c . NIL))) であれば，(a) を返します。
　引数にリスト以外を渡した時の扱いは定まっておらず，処理系によってエラーを返したり，何も返さなかったり，適当な値を返したりします。

lfe> (car '(a b c))
a
lfe> (car '((a) b c))
(a)

※ちなみにLFEでリスト以外を引数に渡すと，引数が適切でないという例外を返しますが，デバッグモードには入りません。

cons cellの後半部を返す関数……cdr

　引数にとったリストのcons cellの後半部が何かを返す関数です。返す値はたいていはリストですが，アトムの場合もあります。
　(a . (b . (c . NIL))) であれば，(b c) を返します。ドット対については，入力を受け付けるものの，出力としては，簡略化できるものは簡略化し，どうしても簡略化できない（cons cellの後半部にNIL以外のアトムを指すポインターが収納されている場合がその典型的な例です）時にだけ。ドット対で出力するのが通例です。簡略化できる場合というのは，例えば (b . (c . NIL)) のように後半部がリストで，かつそのリストの前半部がアトムだと， . とそれに引き続く ( と ) の組合せを外してしまい (b c . NIL) とします。さらに . の後がNILだと，リストの終端を示しているので，. NILを外して，(b c) とします。
　引数にリスト以外を渡した時の扱いは定まっておらず，処理系によってエラーを返したり，何も返さなかったり，適当な値を返したりします。

lfe> (cdr '(a b c))
(b c)

※ちなみにLFEでリスト以外を引数に渡すと，引数が適切でないという例外を返しますが，デバッグモードには入りません。

carとcdrの組合せ

　例えばリストの1番目の要素を取り出すには (car リスト) でいい訳ですが，2番目の要素を取り出す時にはリストのcdrを取って，その結果のcarを取るという手順になります。Lispで書くと (car (cdr リスト)) になります。ところで，このように「何番目の要素を取り出す」というのは結構需要があるので，多くの処理系では複数のcarやcdrを組み合わせてcxxxrの形式で一つの関数として用意していることがよくあります。（例えば (car (cdr リスト)) だと，(cadr リスト) の要領です。）どんな（どれだけ）関数があるかは，その処理系のマニュアル等を見てください。
　例えばLFEではcxxxxrのように間のx（aかd）が4つまで定義されており，5つ以上だと未定義の関数だと返されます。

carとcdrの逆に新たなリストを作る……cons

　新たなcons cellを持って来てリストを作る関数がconsです。consは必ず引数を2つ持ちます。それぞれの引数はリストでもアトムでもかまいません。（ただし第2引数はリストである場合が多いでしょう。アトムだと，ドット対でしか表現できないデータが出来上がってしまうからです。）
　ちなみに，consがcarとcdrの逆だという話なのですが……。
　一言で言ってしまうと，(cons (car x) (cdr x)) が，元のxというリストと同じになるからなのです。すなわちconsは，新たなcons cellを1つ持って来て，その前半部に第1の引数，後半部に第2の引数を収納するのですが，（car x) は元のxの最初の要素，(cdr x) は最初の要素を取り除いた残りのリストとなるため，それをconsすると元のリストに戻るという仕掛けなのです。

lfe> (cons 'a '(b c))
(a b c)

他のLispにおけるcar・cdr・cons

　Common lisp，Scheme，Emacs Lispでも，これらの基本関数については存在し，返す値も変わりません。
　carとcdrの組合せのcxxxxrの形式の関数については，これは言語というより，個々の処理系で扱いが異なっています。

（2023.5.14. 初版）
（2023.5.15. 改訂）
次へ　前へ　目次へ　佐々木将人の個人ページへ