【Common Lisp】コンスセルとC言語のポインタを比べる

コンスセルはcarとcdrの2本のポインタを持つ構造体で、Cの*pとp++に対応する操作をLispで表現できます。
carもcdrもどちらもデリファレンスで、Cの*p（値を読む）とp++（ポインタ算術）が異なる操作であるのと対照的です。
p++がないことで任意のアドレスに辿り着けず、メモリ安全性が上がり、cdrに次を明示的に書くことでリスト・木・グラフを同じ構造で表現できます。
コンスセルは生ポインタより重く、Cのノード構造体より言語にネイティブな、その中間の存在です。

1. コンスセルとポインタ

Common Lispのコンスセルは、C言語のポインタとノード構造体の中間にあるデータ構造と言えます。

Cのポインタを使ったことがあれば、Common Lispのコンスセルは、2本のポインタを持つ構造体と考えることができます。

struct Cell {
    void *car;
    void *cdr;
};Code language: C++ (cpp)

carとcdrはそのスロットへの参照を取り出す操作で、Cのデリファレンスに相当します¹。
まずは、このcar部分だけを使って、Cのポインタ操作を表現してみます。

1.1. `*p` を作る——`(cons nil nil)` というボックス

Cで整数への参照を持ちたいとき、こう書きます。

int *p;
p = malloc(sizeof(int));
*p = 3;
printf("%d\n", *p);
free(p);Code language: C++ (cpp)

Lispで同じことをするには、やや冗長ですが consでボックスを作ります。

(let ((cell (cons nil nil)))
  (setf (car cell) 3)
  (format t "~a~%" (car cell)))Code language: Lisp (lisp)

consでセルを確保し、(car cell)がデリファレンスに相当し、(setf (car cell) ...)で書き込みます²。

C	Common Lisp
`malloc(sizeof(T))`	`(cons nil nil)`
`*p`	`(car cell)`
`*p = x`	`(setf (car cell) x)`

ここでは、まだcdrはnilのまま放置しています。

1.2. 値コピーとポインタコピー

C言語では、ポインタコピーがあります。

int obj = 3;
int *p;
p = &obj;
*p = 5;
printf("%d\n", obj); /* => 5 */Code language: C++ (cpp)

これと同じようなことをコンスセルでするには、

(setf obj (cons 3 nil))
(setf cell obj)
(setf (car cell) 5)
(car obj)   ;=> 5Code language: Lisp (lisp)

(setf cell obj)でセルへの参照がコピーされるので、obj と cell は同じセルを指します。(setf (car p) 5)で書き換えると、objから見ても変わっています³。

1.3. 数値をオブジェクト参照する

この仕組みを使うと、数値をボックスに入れて複数の場所から共有する、ということができます。

(defparameter *threshold* (cons 0.5 nil))

(defparameter *filter-a* *threshold*)
(defparameter *filter-b* *threshold*)

(setf (car *threshold*) 0.8)

(car *filter-a*)   ;=> 0.8
(car *filter-b*)   ;=> 0.8Code language: Lisp (lisp)

Cで言えば、グローバルなdoubleへの複数のポインタです。
一箇所書き換えれば、すべてのポインタから新しい値が見えます。

ただ、コンスセルを介した共有パターンよりは、Common Lispでは通常defparameterの再束縛で済ます方が一般的です⁴。

2. `p++` を作る——`cdr` でリストを辿る

Cのポインタは、配列を走査するのに適しています。
p++で次へ進み、*pで値を読むパターンです。

int xs[] = {80, 90, 70, 85, 95, 0};
int *p = xs;
while (*p) {
    printf("%d\n", *p);
    p++;
}Code language: C++ (cpp)

これをCommon Lispに直訳するなら、

(defparameter xs '(80 90 70 85 95 . nil))

(loop for cell = xs then (cdr cell)
      while cell
      do (format t "~a~%" (car p)))Code language: Lisp (lisp)

Lispのリスト走査では、(car cell)が*p、(cdr cell)がp++に対応します。
carで値を読み、次のステップではcdrが指すセルへ進みます。

もちろん、通常はもっと直感的な loop .. in で書きます。

(loop for val in xs
      do (print val))Code language: Lisp (lisp)

2.1. `p++` がないことの安全性

コンスセルとCのポインタが根本的に違う点は、cdrの有無です。

Cのp++は、配列という連続したメモリのレイアウトを前提にしています。
次のアドレスはp + sizeof(T)で計算できるので、「次」をどこかに明示的に保存する必要がありません。
ルールが次を決めているわけです。
連続したメモリを前提に、p++ だけでなく p + n で任意のオフセットへ飛ぶことができます。

ただし、確保したメモリサイズより先に進めば、配列の範囲外を指します。
この値を読み書きすると、未定義の動作になってしまい、バグの温床になります。
何より、ポインタそのものには終端を示す仕組みがなく、かんたんに範囲外になります（コード例では最後の要素に 0 を入れて終端にしていますが、 0 を入れられる配列ではうまく動作しません。結局、多くの場合長さを表すデータを別に持つ必要があります）。

一方、コンスセルには、その「次を決める計算ルール」はありません。
cdrに次のセルを明示的に書かない限り、次へは進めません。

(cons 1 (cons 2 (cons 3 nil)))Code language: Lisp (lisp)

このリストは、各セルのcdrが次のセルを指すことで繋がっています。
cdrが指す先はnilか既存のオブジェクトだけです。
参照先は計算で作る手段がなく、明示的に接続していない「どこか知らないアドレス」には辿り着けません。

この制約と利点は、同じ事実の表裏になっています。

つまり、Cのポインタは、ポインタ算術によってアクセス先を自由に変更できることが、効率性になり、一方、Common Lispのコンスセルは、生成済みのオブジェクトしか cdrで束縛できないことが、メモリ安全性を生んでいます⁵。

3. `car`と`cdr`が同じ構造

ちなみに、carとcdrは、どちらもポインタのデリファレンスです。

Cでは「値を読む（*p）」と「次へ進む（p++）」が別の操作で、p++はデリファレンスではなくポインタ算術です。

一方、(car cell)はcarポインタを辿り、(cdr cell)はcdrポインタを辿ります。
操作の種類として両者は相同です。

つまり、

Cの*pとp++は、デリファレンスとポインタ算術という異なる操作
Lispのcarとcdrは、どちらもデリファレンスで操作の種類が同じ

このため、「次」の定義をcdrが指す先で自由に決められる、という柔軟性が生まれます。

もっともよく使うシーケンス構造のリストでは、carを要素、cdrを次のセルとして使う慣例になっていますが、carに入れ子のリストを取り、木構造にしたり、cdrで自分自身を指して循環させることもできます⁶。

Cの場合は、このようなデータ構造を作るには、構造体を用意する必要があります。

struct Cell {
    void *car;
    void *cdr;
};Code language: C++ (cpp)

4. まとめ

Cのポインタ操作とコンスセルの対応をまとめます。

C	Common Lisp
`malloc(sizeof(T))`	`(cons nil nil)`
`*p`	`(car cell)`
`*p = x`	`(setf (car cell) x)`
`p++` `p = (*p).cdr`	`(setf cell (cdr cell))`

コンスセルは、ポインタ算術によるアクセスがない代わり、cdrに次を明示的にセットします。
そのため、配列のような線形構造だけでなく、木やグラフも同じセルの組み合わせで作れます。
また、範囲外を指すポインタが作れない分、メモリ安全性も上がります。

p++がないことを制約と見るか、設計の選択と見るかで、コンスセルの見え方が変わります。

carとcdrという名前は、1950年代後半にLispが最初に実装されたIBM 704コンピュータのハードウェアに由来します。carはContents of the Address part of Register、cdrはContents of the Decrement part of Registerの略です。IBM 704の36ビットワードには15ビットのAddressフィールドとDecrementフィールドがあり、コンスセルの2本のポインタをそこに収めたことが名前の起源です。 – CAR and CDR – Wikipedia
(setf (car cell) x)という書き方は、Common LispのGeneralized Reference（汎用参照）の仕組みを使っています。carはsetf可能なplaceとして定義されており、(setf (car cell) x)は内部的にrplacaと同等の操作に展開されます。cdrも同様に(setf (cdr cell) x)が使えます。 – Accessor CAR, CDR – CLHS
Common Lispでは数値（fixnum）は処理系によってタグ付きポインタとして実装されることが多く、コンスセルと同様にヒープオブジェクトへの参照として扱われます。ただし小さな整数はポインタではなく即値として表現されるため、(setf x 5)のようなコードは「参照のコピー」というよりも値そのものの代入に近い動作になります。 – 5.1 Generalized Reference – Common Lisp Language Reference
defparameterの再束縛はシンボルの値セルを差し替えるだけなので、そのシンボルを参照している変数には伝わりません。コンスセルを介した共有は、セルそのものを書き換えるため、セルへの参照を持つすべての変数に変更が波及します。これは構造の共有とも呼ばれ、memberが返すtailと元のリストが同じコンスセルを指している仕組みと同じ原理です。 – 5.1 Generalized Reference – Common Lisp Language Reference
Common Lispのメモリ管理はGC（ガベージコレクタ）が担います。consで確保したセルは、どこからも参照されなくなると自動的に回収されます。Cのようにfreeを呼ぶ必要がなく、ダングリングポインタも発生しません。これも「到達可能なオブジェクトしか指せない」という設計と合わさって、メモリ安全性を高めています。 – Garbage Collection in a Large Lisp System
コンスセルが循環構造を形成する場合、printやformatで出力しようとすると無限ループになります。Common Lispでは*print-circle*をtに設定することで、循環構造を#1=(1 2 . #1#)のような形式で安全に表示できます。 – CLHS: Variable PRINT-CIRCLE

1. コンスセルとポインタ

1.1. *p を作る——(cons nil nil) というボックス