【Common Lisp】
入口を全体とみなす設計
（コンスセルとポインタ）

by
  • Common Lispのnreverseはリストのセル間ポインタを書き換えて反転するため、変数は末尾セルを指したままになり、反転後のリスト全体を得るにはsetfで変数を更新する必要がある。
  • Lispのリストはオブジェクトではなくコンスセルをポインタでつないだ鎖で、変数が持つのは先頭セルへの参照にすぎない点がRubyなどの言語と根本的に異なる。
  • 「先頭への参照を全体として扱う」設計はC言語の文字列や配列にも共通しており、コピーを避けて効率的に後続部分を扱える一方、関数内の変更が呼び出し元に波及する。

関連記事

1. リストが破壊される？

Common Lisp の nreverse は、「破壊的にリストを反転させる」関数です。

nreverse ─ 変数が指す先が変わる Ruby arr = [1, 2, 3] arr.reverse! arr # => [3, 2, 1] ✓ arr [3, 2, 1] オブジェクト 変数はオブジェクト全体を参照 → 反転後も全体が見える Common Lisp (nreverse lst) lst ; => (1) ← 末尾だけ！ lst 1 2 3 変数は先頭セルだけ参照 反転後 → 末尾に取り残される (setf lst (nreverse lst)) が必要

しかし、これはリストそのものが書き換わるだけではなく、変数が指している場所にも注意が必要です。
たとえば、Ruby の破壊的な反転 reverse! と同じように考えると、呼び出し後の変数の見え方がまったく違うことに戸惑います。

Ruby では arr から反転済みの全体が見えます。

arr = [1, 2, 3]
arr.reverse!
arr  # => [3, 2, 1]Code language: Ruby (ruby)

しかし、Lisp では lst から見えるのは (1) だけで、(3 2 1) ではありません1。

(let ((lst (list 1 2 3)))
  (nreverse lst)
  lst)
; 多くの実装で => (1)Code language: Lisp (lisp)

同じ「破壊的な反転」なのに、なぜ結果が違うのか。
これは「変数が指しているものが何か」という問いでもあります。

1.1. Lispのリストはオブジェクトではない

Ruby の配列は、「オブジェクト」として存在します。

そして、変数は、「そのオブジェクト全体への参照」を持ちます。
reverse! はオブジェクトの中身を書き換えますが、変数が指す先は変わりません。
呼び出し後も変数から全体が見えるのは、この言語設計のためです。

一方、Common Lisp のリストは、オブジェクトとして存在しているわけではありません。
多くの場合では、オブジェクトのように扱えるのですが、実体は、car と cdr を持つコンスセルをポインタでつないだ鎖です。
変数が持つのは、「その先頭セルへの参照」にすぎません。

1.2. コンスセル間のポインタ

nreverse の反転は、セル間のポインタを書き換えて鎖の向きを逆にします。

これが破壊的なのは、反転後の先頭はもとの末尾セルになることです。
そのため、lst はリストの末尾を指し、要素1個しか見えなくなります。

したがって、反転後のリスト全体を得るには、変数を更新しなければなりません。

(setf lst (nreverse lst))Code language: Lisp (lisp)

nreverseの返り値は、反転後のリストの先頭セルです。
Ruby では不要だった一行が、Lisp では必要になる理由がここにあります2。

2. 入口を全体として扱う慣習

Lispのコンスセル設計のメリットは、後続リストが取りやすいことです。

先頭への参照を「全体」として扱う Common Lisp ─ cdrで後続リストを得る 1 2 3 lst (cdr lst) コピーなし 別の入口を指すだけ C ─ 文字列ポインタ h e l l o \0 s s+2 s+2 → “llo” をコピーなしで参照 \0 終端で境界を表現 共通原理 先頭参照 ＝ 全体 ・コピーコスト ゼロ ・終端（nil / \0）で境界表現 ・長さ情報を外部に持たない

Lispの再帰関数では、cdrを使った後続リストへの操作が頻繁に出てきます。
cdr では、新しいリストを作っているわけではありません。
ただ、2番目のセルを入口にしただけで、後続リストとして扱えます。

(defun my-sum (lst)
  (if (null lst)
      0
      (+ (car lst) (my-sum (cdr lst)))))

(my-sum (list 1 2 3 4))
; => 10Code language: Lisp (lisp)

(cdr lst) が指すリストは独立した構造ではなく、lst の途中への別の入口になっています。

2.1. C 言語の文字列

「先頭セルへの参照をリストとみなす」という慣習は、計算機のアーキテクチャに根ざしています。
要は、「計算機に優しい設計」で、たとえば C言語 にも同じような構造があります。

C の文字列変数の正体は、先頭文字へのポインタです。
文字列全体というオブジェクトは存在せず、入口となるポインタと終端文字の慣習だけで成立しています。

char *s = "hello";
printf("%s\n", s);     // hello
printf("%s\n", s + 2); // lloCode language: Arduino (arduino)

そのため、s + 2 を渡せば、'l' から '\0' までを、コピーなしで別の文字列として扱えます。

終端による境界表現も同じ発想です。
Lispのリストは終端を nil で、C言語の文字列は終端を '\0' で表すことで、「長さ」という付加情報を構造の外に置かずに済みます。

また、C言語の配列も同様で、多くの式文脈で先頭要素へのポインタに暗黙変換されます。
これを array-to-pointer decay と言います3。

int sum(int a[], int n) {
    int total = 0;
    for (int* p = a; p < a + n; p++) {
        total += *p;
    }
    return total;
}

int arr[] = {1, 2, 3, 4};Code language: Arduino (arduino)

arr を渡すとき配列のコピーは起きません。
先頭要素へのポインタが渡されるだけです。そのため関数側は長さを別に受け取る必要があります。

つまり、Common Lisp のコンスセル鎖と C のポインタは、内部構造が連結リストと連続メモリで異なりますが、「先頭への参照を全体として扱う」という点において共通しています。

3. 効率性の代償としてのメモリ管理

効率性の裏側として、関数が受け取ったリストや配列を操作すると、呼び出し元でも書き換わることがあります。
たとえば、累積和を求める関数で見てみましょう。

効率 と 副作用 は同じ設計の表裏 コピーなし = 効率的 新しいリストを生成しない メモリ・速度コストがゼロ 大きなデータに有効 同じ 設計 呼び出し元が変わる 関数内の変更が外部に波及 意図しないデータ破壊のリスク 元データを残す場合は要コピー 元データを守る場合 Lisp: (copy-list data) してから渡す C: memcpy で複製してから渡す 言語での対応 C / Lisp：手動で管理 Go スライス：長さ明示 Rust：コンパイル時に防止 「コピーを避ける」と「呼び出し元が変わる」は 同じ設計から生まれる 
(defun cumsum! (lst)
  (let ((acc 0))
    (do ((cur lst (cdr cur)))
        ((null cur) lst)
      (incf acc (car cur))
      (setf (car cur) acc))))

(let ((data (list 1 2 3 4)))
  (cumsum! data)
  data)
; => (1 3 6 10)Code language: Lisp (lisp)

cumsum! は新しいリストを作らず、渡された先頭セルから cdr をたどりながら、各セルの car をその場で書き換えています。

そのため、呼び出し後に data を見ると中身が変わっています。
元のデータが不要なら、新しいリストを生成するコストがゼロになるため効率的ですし、元のデータを残したいなら、呼び出し前にコピーすればよいわけです4。

(let* ((data (list 1 2 3 4))
       (result (cumsum! (copy-list data))))
  (values data result))
; => (1 2 3 4)
;    (1 3 6 10)Code language: Lisp (lisp)

C でも構造は同じです。
受け取った配列に直接計算結果を書き込んでいくと、呼び出し元の配列が変更されます。

void cumsum(int a[], int n) {
    for (int i = 1; i < n; i++)
        a[i] += a[i-1];
}

int arr[] = {1, 2, 3, 4};
cumsum(arr, 4);
// arr は {1, 3, 6, 10}Code language: Arduino (arduino)

先頭要素へのポインタが渡されるだけなので、関数内で書き込めば呼び出し元の配列が変わります。
元のデータを残したいなら、呼び出し前に memcpy でコピーするのが C での慣用です。

つまり、「コピーを避ける」という効率性と、「呼び出し元が変わる」という注意点は、同じ設計の表裏です5。
関数の呼び出し側がメモリ効率を管理できるということは、どのようにメモリが管理されているか意識して使わなければならない、ということでもあるのです。

3.1. 計算機の論理が見える場所

Common Lisp と C には歴史があり、まだ人間ではなく「計算機の論理」が直接見えます。

変数とはアドレスであり、終端を確認することでリストや文字列を扱っていました。
nreverse の奇妙な挙動は、こうした論理によって成り立っています。

この設計はオブジェクトがまだ「高価」だった時代の名残りでもあります。

ヒープにオブジェクトを確保し、長さや型情報を付加して管理する。
それ自体がコストだった時代には、先頭への参照を全体として扱う慣習は実用的な解でした。
抽象の下で何が起きているかを理解する手がかりとして、この種の設計を読む価値は今も残っています。

3.2. GoやRustでの継承

Ruby のような言語がオブジェクトモデルを徹底できたのは、そのコストを許容できるだけのハードウェアの進化と寛容さができたからです。

同じような設計思想は、さらに形を変えて続いています。

たとえば、Go のスライスは内部的に「先頭ポインタ、長さ、容量」の三つ組で、配列の一部を指します6。
cdr や C の配列ポインタと同じ原理ですが、長さを明示的に持つ点で C より安全な設計になっています。

Rust のスライス &[T] はさらに進んで、借用チェッカーが共有と変更の競合をコンパイル時に封じます。
C や Lisp で実行時に露出していた問題を、静的に防ぐ設計になっています。

  1. nreverse の副作用の範囲は Common Lisp の仕様で厳密に規定されておらず、処理系によって結果が異なる場合があります。SBCL では lst が (1) になりますが、CLISP では実装の都合でその場で反転されるため lst が (3 2 1) になることがあります。いずれにせよ、戻り値を必ず使う形で書くのが安全です。 – Function REVERSE, NREVERSE – Common Lisp HyperSpec
  2. nreverse の n は non-consing の略で、新たにコンスセルを確保しないことを意味します。Common Lisp では破壊的操作の多くがこの n プレフィックスを持ちます（nconc、nsubst など）。戻り値を変数に戻す慣用として (setf lst (nreverse lst)) が標準的です。 – Practical Common Lisp – List Processing
  3. C99 規格（6.3.2.1 節）では、配列型の式は sizeof 演算子・単項 & 演算子・文字列リテラルによる配列初期化の3つの例外を除いて、先頭要素へのポインタに変換されると規定されています。この変換によって配列の長さ情報は失われます。 – C99 Standard and Array Decay – Dmitry Kabanov
  4. copy-list はリストの「浅いコピー（shallow copy）」を作ります。トップレベルのコンスセルは新しく作られますが、要素として含まれるネストしたリストなどのオブジェクトは元のリストと共有されます。要素ごと独立させたい場合は copy-tree の使用を検討してください。 – Function COPY-LIST – Common Lisp HyperSpec
  5. Common Lisp では (push item list) でリストを逆順に積み上げ、最後に (nreverse list) で反転するイディオムが広く使われています。このとき nreverse に渡すリストへの参照は1つだけなので、破壊的操作が安全に使えます。CLOCC（Common Lisp Open Code Collection）の調査では、破壊的操作の用途の約半数がこのパターンだったとされています。 – Practical Common Lisp – List Processing
  6. Go のスライスヘッダは、データへのポインタ・長さ（len）・容量（cap）の3フィールドで構成されます。スライスを関数に渡す際にはこのヘッダがコピーされますが、参照先の配列データはコピーされません。そのため関数内でスライス要素を変更すると呼び出し元にも影響します。 – Go Blog: Go Slices – usage and internals