1. リストとは「チェーンへの視界」である
Lisp のリストは「値の列」ではありません。
Common Lisp の list 関数や cons が返すものを、私たちは「リスト」と呼びます。
(list 1 2 3)Code language: Lisp (lisp)しかし、メモリ上に「リスト全体」という単一のオブジェクトが存在しているわけではなく、その実体は、コンスセルと呼ばれる小さなオブジェクトが cdr でつながったチェーンです1。
[1 | *] -> [2 | *] -> [3 | nil]Code language: CSS (css)各 [値 | *] が1つのコンスセルです。
各コンスセルは car と cdr という2つの参照スロットを持っていて、car が先頭の値を、cdr が次のセルへの参照を指しています2。* が次のセルへの参照で、最後は nil で終端します。
変数 x や y を list や cdr の返り値に束縛するとき、x や y が指すのは「リストそのもの」ではなく、チェーンの先頭のセルだけです。
(setq x (list 1 2 3))
(setq y (cdr x))Code language: Lisp (lisp)そのため、x から見ると (1 2 3)、y から見ると (2 3) です。
x
↓
[1 | *] -> [2 | *] -> [3 | nil]
↑
yCode language: CSS (css)同じチェーンのどこから眺めるかで、見える「リスト」が変わります。
いわば、龍の全体像はメモリという海の中を泳いでいて、変数は、その節目にスポットを当てて見ているだけなのです。
2. 2種類の操作：作ると配線を変える
コンスセルに対する操作は、大きく2種類に分かれます。
2.1. cons：新しい節を作る
(cons 1 lst)Code language: Lisp (lisp)新しいコンスセルを1つ作り、car に 1、cdr に lst をつなぎます。
元の lst は変更されませんが、consの返り値は一つ長いリストになります。
2.2. setf で既存の配線を変える
(setf (cdr cell) other-list)Code language: Lisp (lisp)cell というコンスセルの cdr スロットが指す先を付け替えます。
この cell が既存のどこかのチェーンの一部なら、それを参照している他の変数の見え方にも影響します。
(defvar x (list 1 2 3))
(defvar cell (cdr x))
(setf (cdr cell) (list 4 5))
x ;; => (1 2 4 5)Code language: Lisp (lisp)cell の配線を変えたとき、x からもそのセルの見え方が変わります。
2.3. nreverse
nreverse は、内部でチェーンの配線を組み替える関数です。
reverse は新しいチェーンを作りますが、nreverse は既存のコンスセルの cdr を付け替えて向きを組み替えます。
(setq x (list 1 2 3))
(setq y (nreverse x))
y ;; => (3 2 1)
x ;; => (1) ; 元の先頭セルは、反転後の末尾になっているCode language: Lisp (lisp)nreverse 後、x はまだ元の先頭セルをつかんでいます。
そのため、そのセルはチェーンの末尾になって cdr が nil を指しています。
x からの視界は (1) だけになります。
つまり、「xの指すリストを反転した」のではなく、「チェーンの配線が変わり、視界が変わった」ということです3。
2.4. GC との関係：どこからもつかまれなくなった鱗
コンスセルを作り、cdr を付け替えると、以前のつながり先が到達不能になることがあります。
(setq x (list 1 2 3))
(setf (cdr x) (list 4 5))Code language: Lisp (lisp)元の (2 3) を他の変数が指していなければ、その2つのコンスセルはどこからもたどれません。
メモリという海を泳いでいた龍の胴体の一部が、どこからもつかまれなくなった状態です。
コンスセル自身は「自分を誰が指しているか」を知りません。car と cdr という外向きの参照しか持っていないからです。
あるセルがまだ必要かどうかは、ルートからたどれるかどうかを外側から調べるしかありません。
これがガベージコレクションの基本発想です。
cons で小さなオブジェクトを大量に動的生成し、cdr の付け替えで構造を組み替えていくと、到達不能なセルが自然に生まれます。
リストが共有や循環を持てるため、「このセルはもう安全に解放してよい」と人間が局所的に判断するのは困難で、GC がルートからのグラフ到達性を調べることで、初めて安全な回収が可能になります。Lisp に GC が早くから必要とされた背景は、ここにあります4。
3. コンスセルのチェーンでできる構造
コンスセルは car と cdr が任意のオブジェクトを指せるので、さまざまな形のチェーンを作れます。
3.1. proper list
いわゆる「リスト」はその一部で、これを「proper list」といいます。
(list 1 2 3) ;; => (1 2 3)Code language: Lisp (lisp)proper listは、cdr をたどると最終的に nil に到達するリストのことです。
通常の再帰関数は、proper listを前提としていて、null で判定して基底ケースとします5。
proper list を入れ子構造にすると、木構造を作ることができます。
3.2. dotted list
最後の cdr が nil でない値を指すリストは、dotted listといいます6。
(cons 'a 'b) ;; => (A . B)
(cons 'a (cons 'b 'c)) ;; => (A B . C)Code language: Lisp (lisp)(a b . c) のように「途中まではリストで、末尾だけ別の値」という形もありますが、データ構造として積極的に使われる場面は多くありません。
ほとんどは、ペア（dotted pair）として使われます。
より一般的な形式の dotted list は、パターンマッチや分配束縛の記法のとき現れます。
(destructuring-bind (x y . rest) '(1 2 3 4 5)
(list x y rest))
;; => (1 2 (3 4 5))Code language: Lisp (lisp)パターン (x y . rest) 自体が dotted list です。
ただ、(x y) と rest に分けているという意味では、これも本質的にはペア構造に近い使い方です。
4. 循環リスト
「循環リスト」は、cdr をたどっても nil に到達しない、循環したチェーンです7。
x
↓
[1|*] -> [2|*] -> [3|*]
↑ |
└──────────────────┘最後尾のcdrに、先頭セルを参照するように変更すると、循環リストができあがります。
(setq x (list 1 2 3))
(setf (cdr (last x)) x)Code language: Lisp (lisp)4.1. 循環リストでラウンドロビン処理
ターン制の処理や順番に巡回するスケジューラは、循環リストで自然に表現できます。
(defun make-circular (lst)
"リストを循環リストに変換する。
"
(let ((copy (copy-list lst)))
(setf (cdr (last copy)) copy)
copy))
(defvar players (make-circular '(alice bob charlie)))
(defun next-turn (ring)
"現在のプレイヤーを返し、次のプレイヤーへ進む。
"
(prog1 (car ring)
(setf ring (cdr ring))))Code language: Lisp (lisp)配列なら添字を剰余で回すところを、リスト構造そのものに循環を持たせることで、「次へ進む」操作が単純な cdr になります。
ただし、通常の length、map、print といった関数は循環リストで止まらない可能性があるので、終了条件を「リスト終端」ではなく「回数」や番兵にする設計が必要です8。
4.2. proper-list-p：亀と兎法で正しく判定する
このような循環リストを考慮すると、proper list かどうかの判定は単純ではありません。
cdr をたどって null を待つだけでは、循環リストで止まらないからです。
循環を検出するには Floyd の循環検出法、亀と兎法が有効です。
このアルゴリズムは、2つのセルを走査し、slow を1歩ずつ、fast を2歩ずつ進めます。
もし、循環があれば必ず同じコンスセルで出会い、なければ fast が先に終端に到達します9。
もし、訪問済みセルをリストで記録して重複を見つけようとすると O(n) のメモリが必要ですが、この方法では slow と fast という2つのポインタしか保持しないため、O(1) で済みます10。
(defun proper-list-p (object)
(labels ((step1 (x)
(cond ((null x) (values :proper nil))
((consp x)
(let ((next (cdr x)))
(cond ((null next) (values :proper nil))
((consp next) (values :continue next))
(t (values :improper nil)))))
(t (values :improper nil)))))
(cond ((null object) t)
((not (consp object)) nil)
(t
(let ((slow object)
(fast object))
(loop
(multiple-value-bind (status next) (step1 slow)
(case status
(:proper (return t))
(:improper (return nil))
(:continue (setf slow next))))
(dotimes (i 2)
(multiple-value-bind (status next) (step1 fast)
(case status
(:proper (return-from proper-list-p t))
(:improper (return-from proper-list-p nil))
(:continue (setf fast next)))))
(when (eq slow fast)
(return nil))))))))Code language: Lisp (lisp)循環を見つけるまでループしますが、必ず終端します。
「判定対象がすでにメモリ上に存在しているオブジェクト」が対象なので、コンスセル数は有限だからです。
循環があれば鳩の巣原理によりいつか同じセルに戻り、決定可能です11。
動作確認です。
(proper-list-p nil) ;; => T
(proper-list-p '(1 2 3)) ;; => T
(proper-list-p '(1 2 . 3)) ;; => NIL
(proper-list-p '((1 . 2) (3 4))) ;; => T
(let ((x (list 1 2 3)))
(setf (cdr (last x)) x)
(proper-list-p x)) ;; => NILCode language: Lisp (lisp)5. チェーンを共有する
「共有 tail」は、複数の変数やコンスセルが、同じ末尾のチェーンを指す構造です。
(defvar tail (list 3 4))
(defvar a (cons 1 (cons 2 tail)))
(defvar b (cons 9 tail))
a ;; => (1 2 3 4)
b ;; => (9 3 4)Code language: Lisp (lisp)tail の中身を変更すると、a からも b からも、両方の見え方が変わります。
a -> [1|*] -> [2|*]
\
-> [3|*] -> [4|nil]
/
b -> [9|*] ---------コピー不要で同じ末尾を共有できるため、古い版を残したまま新しい版を作る、永続データ構造的な使い方もできます。
5.1. 低コストでスタックを派生させる
たとえば、スタックに要素を「追加した版」を派生させる場面です。
(defvar v0 (list 3 2 1)) ;; 最初の版
(defvar v1 (cons 4 v0)) ;; v0 を壊さず、先頭に 4 を足した版
(defvar v2 (cons 5 v0)) ;; v0 を壊さず、先頭に 5 を足した版
v0 ;; => (3 2 1)
v1 ;; => (4 3 2 1)
v2 ;; => (5 3 2 1)Code language: Lisp (lisp)v1 -> [4|*]
\
-> [3|*] -> [2|*] -> [1|nil]
/
v2 -> [5|*]v0、v1、v2 はそれぞれ独立したリストに見えますが、(3 2 1) の部分は同じコンスセルを共有しています。cons で先頭に節を1つ加えるだけで、元のチェーンを一切コピーせずに新しい版を作れます。
破壊的変更をしない限り、どの版も安全に共存できるので、関数型のスタックや、履歴を持つデータ構造を軽量に実装するときに使える考え方です12。
5.2. 有向非循環グラフ（DAG）
有向非循環グラフ（DAG：Directed Acyclic Graph）は、辺に向きがあり、かつループを持たないグラフ構造の総称です。
共有 tail は cdr 方向だけで共有が起きるDAGの一種ですが、car 側の共有も考えることができます。
x -> [1|*] -> [leaf|*] -> [leaf|nil]
| |
v v
[9|*] -> [10|nil]car 側から同じノードを複数箇所で参照しています。
(defvar leaf (list 9 10))
(defvar x (list 1 leaf leaf))
x ;; => (1 (9 10) (9 10))Code language: Lisp (lisp)x の2番目と3番目の要素は、見た目上は同じ (9 10) ですが、実体は同じコンスセルです。
共有 tail は cdr 方向の共有であり、DAG の特殊ケースです。car 側の共有が加わると、純粋な木ではなくなり、DAG になります。循環がない点では循環リストとも異なります。
leaf を破壊的に変更すると、x の2番目と3番目の要素の両方が変わります。
(setf (car leaf) 99)
x ;; => (1 (99 10) (99 10))Code language: Lisp (lisp)コピーせずに部分構造を共有しているので、変更の影響が複数箇所に及びます。意図的に使えばメモリ効率が上がりますが、意図せず共有していた場合は予期しない挙動につながります。
6. アルゴリズム応用
6.1. cdr の付け替えで splice 削除
条件を満たすノードをリストから除くとき、前ノードの cdr を付け替えることでコピーなしに削除できます。
(defun delete-if-value (lst pred)
(let ((sentinel (cons nil lst)))
(loop for prev = sentinel then curr
for curr = lst then (cdr curr)
while curr
do (if (funcall pred (car curr))
(setf (cdr prev) (cdr curr))
(setf prev curr)))
(cdr sentinel)))Code language: Lisp (lisp)先頭に番兵ノードを置くことで、先頭要素の削除を特別扱いせずに済みます。
削除対象のコンスセルは cdr prev を飛ばすだけで、そのセルが他から参照されていなければ GC が回収します。
配列なら要素を詰め直すところを、コンスセルでは配線の付け替えだけで済むのが利点です13。
6.2. nconc で worklist を破壊的に延ばす
BFS などで候補リストを伸ばすとき、nconc を使うとコピーを避けられます。
最後のコンスセルの cdr を次のリストへ直接付け替えます。
(defvar worklist (list start-node))
(loop while worklist
do (let ((node (pop worklist)))
(let ((neighbors (find-neighbors node)))
(nconc worklist neighbors))))Code language: Lisp (lisp)nconc は元のリストを破壊します。
同じ構造を別の変数も参照している場合は影響を受けますし、同じ構造に繰り返し nconc すると循環を作ってしまう危険もあります。
自分が作ったばかりの一時リストに対してのみ使うのが安全です14。
7. pair as cursor：ノードを直接編集する走査
通常の loop for in ではリストの要素を受け取りますが、loop for on でコンスセルそのものを受け取れば、その場での splice 操作ができます15。
7.1. 要素を挿入する
たとえば、「条件を満たす要素の直後に別の要素を挿入する」処理です。
(defun insert-after! (lst pred value)
(loop for pair on lst
when (funcall pred (car pair))
do (setf (cdr pair) (cons value (cdr pair))))
lst)
(defvar ys (list 1 2 3 4))
(insert-after! ys #'evenp :even)
;; => (1 2 :even 3 4 :even)Code language: Lisp (lisp)cons で新しいノードを作り、その cdr に元の続きをつなぎ、pair の cdr を新しいノードへ向けています。
要素を受け取るだけの走査では、挿入位置のコンスセルを直接操作できません16。
7.2. 要素を取り除く
たとえば、「連続する重複を除く」処理があります。
隣り合う2つの要素を比較して、同じなら次のノードを飛ばします。
(defun remove-consecutive-duplicates! (lst &key (test #'eql))
(loop for pair on lst
when (and (cdr pair)
(funcall test (car pair) (cadr pair)))
do (setf (cdr pair) (cddr pair)))
lst)
(defvar xs (list 1 1 2 3 3 3 4))
(remove-consecutive-duplicates! xs)
;; => (1 2 3 4)Code language: Lisp (lisp)pair が現在のコンスセルを指していて、(cadr pair) が次の要素です。
重複していれば (setf (cdr pair) (cddr pair)) で次のノードを飛ばします17。
8. まとめ
コンスセルは car と cdr という2つの参照を持つだけの単純なオブジェクトです。
その組み合わせにより、proper list、dotted list、共有 tail、木、循環リスト、DAG まで表現できます。
変数が持つのはチェーンの一節への参照にすぎません。
「リスト」はその入口から cdr 方向にたどった眺めであり、cons で節を作り、setf (cdr ...) で配線を変えることで、コピーなしにチェーンを切ったり、つないだり、反転させたりできます。
- CLHS では cons を「car と cdr という2つの構成要素を持つ複合データオブジェクト」と定義し、つながった cons 群は文脈によって木、リスト、連想リストなど異なる見方ができるとしています。 – CLHS: 14.1 Cons Concepts
carとcdrという名前は、1950年代後半に Lisp が最初に実装された IBM 704 のレジスタ構造に由来します。carは “Contents of Address part of Register”、cdrは “Contents of Decrement part of Register” の略です。 – Simplified Common Lisp reference – cons- 実際には、
xは、(1)とも保証されません。Common Lisp の仕様ではnreverse` は引数のリストを破壊的に変更してよいとされており、戻り値を使わずに元の変数を参照し続けることは未定義の動作につながる可能性があるからです。 – Common Lisp the Language, 2nd Edition: Lists and Conses - ガベージコレクションは John McCarthy が 1959 年頃に Lisp のために考案したとされています。1960 年の論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine」に mark-and-sweep の原型が記述されており、プログラミング言語における GC の最初の実用例とされています。 – Wikipedia: Garbage collection (computer science)
- Common Lisp the Language では、リストを「空リスト、またはその cdr 成分がリストであるコンスの再帰的定義」としており、最後が nil で終端するものが proper list です。 – Common Lisp the Language, 2nd Edition: Lists and Conses
- Common Lisp the Language では、dotted list を「最後のコンスの cdr が nil ではなく別のデータオブジェクトであるリスト」と定義し、末尾にドットと cdr の値を書く特別な表記でこれを表します。 – Common Lisp the Language, 2nd Edition: Lists and Conses
- 循環リストをそのまま
printしようとすると無限ループに陥る可能性があります。*print-circle*をtに設定すると、循環参照を#1=(1 2 3 . #1#)のような#n=/#n#記法で出力できます。 – CLHS: Variable PRINT-CIRCLE - Common Lisp には
list-lengthという関数があり、proper list なら長さを返し、循環リストならnilを返します。通常のlengthは循環リストで終了しない可能性があるため、循環を扱う場合はlist-lengthを使うのが安全です。 – CLHS: Function LIST-LENGTH - この循環検出アルゴリズムは Robert W. Floyd が 1960 年代後半に考案したとされ、Donald Knuth によってその功績が記録されています。2つのポインタのみを使うため O(1) の追加メモリで動作します。 – Wikipedia: Cycle detection
- SRFI-1 の参照実装でも
proper-list?、circular-list?、dotted-list?が亀と兎法を用いて実装されており、循環検出が proper list 判定の前提となっています。 – srfi-1/srfi-1-reference.scm (GitHub) - 鳩の巣原理により、有限個のコンスセルを
cdrでたどり続けると、循環がある場合は必ず同じセルに再び到達します。これが「有限構造なら循環検出可能」という根拠です。 – Cycle detection – Wikipedia copy-listは外側のコンスセル列だけをコピーし、各要素（carが指すオブジェクト）は元のリストと共有されます。一方copy-treeはcar側も含めて再帰的にコピーしますが、共有構造や循環は保存しません。 – CLHS: Function COPY-LIST- Common Lisp 標準の
deleteおよびdelete-ifも同じ発想の破壊的操作で、元のリスト構造を変更することが仕様で認められています。戻り値を使わない場合の動作は未定義です。 – Common Lisp the Language, 2nd Edition - CLHS では
(nconc list-1 list-2)は概念的に(progn (rplacd (last list-1) list-2) list-1)と等価と説明されています。また、同じリストに再度nconcすると循環リストの一部が生成される可能性があると明記されています。 – CLHS: Function NCONC - SRFI-1（Scheme Requests for Implementation 1）は Scheme の標準的なリスト処理ライブラリで、
pair-for-each、pair-foldなど pair を直接操作する高階関数群を定義しています。 – SRFI 1: List Library (GitHub) - Common Lisp の
loopマクロのfor ... on構文は、リストの各コンスセルを順に束縛します。これは要素を束縛するfor ... inとは異なり、pair as cursor の発想を直接サポートする構文です。 – Common Lisp the Language, 2nd Edition - Serapeum などの Common Lisp ユーティリティライブラリでも、splice を利用したリスト操作関数が実装されており、
delqなどが前ノードのcdrを直接付け替える方式を採用しています。 – serapeum/lists.lisp (GitHub)