【Common Lisp】
cdrは後続リストか、後続セルか？
（コンスセル）

by

関連記事

1. リストの cdr は多くの場合「後続リスト」として振る舞うが

Lispのリストはシーケンスとして扱われることが多く、car を「要素」、cdr を「後続する残りのリスト」として読むのが自然です。

cdrには、restという別名がありますし、再帰の引数名として慣用的に使われるlstも、再帰の途中では後続リストを指しています。
どちらも同じ捉え方です。

ただし、cdrを「後続リスト」と反射的に読むと、噛み合わなくなるときもあります。
cdrで受け取る値を、リストという抽象ではなく、メモリ上のコンスセルそのものを書き換えたい場面があるからです1。
そういうときはcellという名前で受け取ると、コードの意図が正直に伝わります。

2. cdrを後続リストとして受け取る

2.1. 再帰による走査

リストを扱う再帰関数では、「先頭と残り」に分解するパターンが基本で、残りのリストをcdrで取ります2。

(defun my-sum (lst)
  (if (null lst)
      0
      (+ (car lst) (my-sum (cdr lst)))))Code language: Lisp (lisp)

最初の呼び出しではlstがリスト全体を指しますが、再帰が進むにつれて後続リストを指すようになります。
(cdr lst)を渡すという行為が、「後続リストを次のステップに送る」という意図を直接表しています。

2.2. loopによる走査

loop for x onは、リストの cdr を順に受け取る構文です3。
隣接する重複要素を見つける関数も、onと分配束縛を組み合わせると自然に書けます。

(defun find-adjacent (lst)
  (loop for rest on lst
        for a = (car rest)
        for b = (cadr rest)
        when (and b (eql a b))
          return (list a b)))Code language: Lisp (lisp)

(a b)が後続リストの先頭2要素を取り出し、aとbを比較します。
一致するペアが見つかれば即座に返し、なければnilを返します。
各イテレーションで渡されるのは後続リストであり、その読み方がここでも成立しています。

3. cdrを後続セルとして受け取る

3.1. 破壊的変更

コンスセルのスロットを直接書き換えるときは、変数が「後続リスト」ではなく「今いるセル」を指しています。
特定の値を持つセルをリストから取り除く関数を例にします。

(defun delete-cell (lst value)
  (let ((dummy (cons nil lst)))
    (loop for cell on dummy
          when (eql (cadr cell) value)
            do (rplacd cell (cddr cell))
            and return (cdr dummy))
    (cdr dummy)))Code language: Lisp (lisp)

先頭にダミーセルを置くことで、先頭セルの削除も同じrplacdで扱えます。
cellは各イテレーションで「今いるセル」を指し、cadr cellで次のセルの値を確認し、一致すればrplacdで繋ぎ替えます。
後続リストのつもりで読むとrplacdで何をしているのかが読み取りにくくなります4。

後続セルを切る操作も同様です。
長さn個になるようにリストを切り詰める関数です。

(defun truncate-list! (lst n)
  (loop for cell on lst
        repeat (1- n)
        finally (rplacd cell nil)))Code language: Lisp (lisp)

repeat (1- n)でn-1回進み、finallyでそのセルのcdrをnilに切ります。
cellが「今いるセル」として一貫していることで、rplacdの操作対象が明確に読み取れます。

3.2. セルを辿る再帰

破壊的変更に限らず、セル単位で操作する再帰でもcellの方が正直です。

リストから、valueを持つコンスセルを返す関数です。

(defun find-cell (lst value)
  (cond ((null lst) nil)
        ((eql (car lst) value) lst)
        (t (find-cell (cdr lst) value))))Code language: Lisp (lisp)

しかし、この関数の戻り値はセルそのもので、呼び出し側はそのセルにrplacdなどの操作を行うことを想定しています5。

そこで、引数名をcellにすると、受け渡しているのが後続リストではなくセルだと伝わります。

(defun find-cell-from (cell value)
  (cond ((null cell) nil)
        ((eql (car cell) value) cell)
        (t (find-cell-from (cdr cell) value))))Code language: Lisp (lisp)

4. 判断の基準

変数がcdrを受け取るとき、その後のコードがリストを辿るだけなら後続リストとして読む変数名（lstやrest）が自然です。
rplacaやrplacdでスロットに触れる、あるいはセル自体を戻り値として返すならcellの方が実体に合っています。

後続リストという読み方は、リストをシーケンスとして扱うほとんどのコードで通じます。
それが噛み合わなくなったとき、変数が後続セルを指していることに気づくと、cellという名前の選択が自然に出てきます。

  1. carとcdrという名前はIBM 704のアセンブリマクロに由来します。CARは「Contents of Address part of Register」、CDRは「Contents of Decrement part of Register」の略で、レジスタの物理的な構造を反映した命名です。設計者自身が後に「firstとrestの方がよかった」と語っています。 – The origin of CAR and CDR in LISP
  2. このパターンはLispにおける再帰の基本形です。「先頭を処理し、残りに対して同じ関数を再帰的に呼び出す」という構造は、数学的帰納法と対応しており、基底ケースとしてnilを終端条件とします。 – Lisp CAR: The Essential Guide to List Processing
  3. loop for var on listは各イテレーションでvarにリストのcdrs（部分リスト）を順に束縛します。loop for var in listが要素を束縛するのに対し、onはコンスセルそのもの、つまり部分リストを束縛する点が異なります。 – Common Lisp’s Loop Macro Examples for Beginners
  4. rplacdはコンスセルのcdrスロットを破壊的に書き換える関数で、引数にconsを要求します。consでないオブジェクトを渡すとtype-errorを発します。戻り値は変更後のconsセル自体です。 – CLHS: rplaca, rplacd
  5. セルを返すfind-cell-fromのようなパターンは、リストの特定位置を直接操作するためのLispイディオムです。setfと組み合わせたり、rplacdでそのセルを繋ぎ替えたりする用途で使われます。構造共有（shared structure）が生じるため、変更が他の変数に影響することに注意が必要です。 – About Cons Cells