【Common Lisp】
デフォルトのリストなのにO(n)になる
（抽象構文木）

by
  • Common Lispのリストはコンスセルの連鎖で構成されており、n番目の要素へのアクセスにO(n)のコストがかかる。
  • この非効率さはリストが木構造やグラフ向きの設計であることに由来し、Lispではコード自体をリストで表現した抽象構文木として扱う。
  • 現代のCommon Lispではベクタや型宣言で効率を引き出せるが、デフォルトは表現力優先で、効率はプログラマーが意識して補う設計になっている。

関連記事

1. ループを書くと自然とリストになる

Common Lispを書いていると、リストはあらゆる場面に顔を出します。
quoteでリテラルを書けばリストだし、loopで要素を集めるときもcollectを使えばリストが返ってくる。

;; quoteでリテラル
'(1 2 3)

;; loopのcollectも自然にリストを返す
(loop for x from 1 to 5 
      collect (* x x))
;; => (1 4 9 16 25)Code language: Lisp (lisp)

ただ、この自然さが曲者です。
単なるシーケンスが欲しいだけのときでも、無意識にリストを選んでしまいます。

1.1. コンスセルの連鎖はグラフに向いた構造

Lispのリストは内部で「コンスセル」という構造の連鎖になっています。

コンスセル表記：(A (B D E) (C F)) (A . ((B . (D . (E . nil))) . ((C . (F . nil)) . nil))) A nil car cdr car cdr car cdr B D E nil (B . (D . (E . nil))) C F nil (C . (F . nil)) 構造のポイント トップレベルは3セルの連鎖 A → (B..) → (C..) → nil 2番目のcarがサブリストを指す (B . (D . (E . nil))) 3番目のcarがサブリストを指す (C . (F . nil))

コンスセルは2つのポインタを持つ単純なペアで、
1つは値、もう1つは次のセルへの参照を指します。

[1 | *] -> [2 | *] -> [3 | nil]Code language: CSS (css)

carで先頭の値を、cdrで残りのリストを取り出すのがLispの基本操作で、これはコンスセルの2つのポインタに直接対応している1。

(car '(1 2 3))  ;; => 1
(cdr '(1 2 3))  ;; => (2 3)
(car (cdr '(1 2 3)))  ;; => 2  （2番目の要素）Code language: Lisp (lisp)

1.2. フラットなシーケンスのアクセスコスト

しかし、フラットなシーケンスとして使うと、リストはえらく非効率です。

n番目の要素にアクセスするには先頭から順番にポインタをたどるしかないので、ランダムアクセスがO(n)になるからです。

(defvar lst (loop for i from 1 to 1000000 collect i))

;; 末尾近くの要素へのアクセスは100万回のポインタ追跡が必要
(nth 999999 lst)Code language: Lisp (lisp)

C言語の配列がO(1)なのとは対照的です2。

さらにコンスセルはヒープ上にバラバラに配置されるため、キャッシュ効率も悪い。
連続したメモリ上にデータが並ぶ配列と違い、CPUのキャッシュラインをうまく活用できない。

2. リストと構文木（AST）

Lispのリストの効率の問題は最初から見えていたかもしれないのですが、コードとデータを同じ構造で統一するという設計上の必然がありました。

リスト ＝ 抽象構文木（AST） S式 (+ 1 (* 2 3)) + 1 * 2 3 コード＝データ コードがリストなので そのまま操作できる マクロの仕組み コード マクロ 新コード 1958年 ジョン・マッカーシー設計 記号処理のためリストを採用 非効率さとマクロの強力さは、同じ設計から生まれている

コンスセルの連鎖構造は、もともと木構造やグラフを表現するのに適しています。
Lispでは、S式でコードそのものがリストで表現され、構文木（AST：Abstract Syntax Tree）として扱われています。

;; コードはリストなので、そのまま操作できる
(def var code '(+ 1 (* 2 3)))
(car code)    ;; => +        （演算子）
(caddr code)  ;; => (* 2 3)  （右辺のサブツリー）
(car (caddr code))  ;; => *  （サブツリーの演算子）Code language: Lisp (lisp)

(+ 1 (* 2 3))は「+ノードの子として1とノードがあり、ノードの子として2と3がある」という木構造をそのまま表現しています。

Lispは、1958年にジョン・マッカーシーがAI研究のために設計した言語で3、目的は記号処理でした。
プログラムをASTとして表現し、コード自体をデータとして操作できるようにする、それが設計の核心にあったのです。

「どうせASTが必要なら、データ構造もそれに合わせてしまえ」というのが、リストがデフォルトになった理由と言えます。

2.1. マクロはコードをリストとして受け取る

そのおかげとして、Lispのマクロは強力です。

マクロは引数としてコードをリストで受け取り、組み替えて新しいコードを返します。
マクロで言語自体を拡張できるので、「Lispで書く」というより「自分の問題に合った言語をLispの上に作って、その言語で書く」という書き方ができます。

;; マクロはコード（リスト）を受け取り、コード（リスト）を返す
(defmacro when2 (condition &body body)
  `(if ,condition (progn ,@body)))

;; マクロ展開を確認できる
(macroexpand-1 '(when2 (> x 0) (print x) (+ x 1)))
;; => (IF (> X 0) (PROGN (PRINT X) (+ X 1)))Code language: Lisp (lisp)

そのマクロが成立するのも、コードとデータが同じリスト構造だからです。
マクロは引数としてコード（リスト）を受け取り、carやcdrで分解して組み替え、新しいコード（リスト）を返す。
型のない均質な構造でなければ、コードをデータとして透過的に操作することはできません。

つまり、リストの非効率さとマクロの強力さは、同じ設計から生まれていると言えます。

3. 現代のCommon Lispでの対処

Common Lispではデフォルトの柔軟性を保ちながら、プログラマーが効率を引き出せる仕組みが用意されています。

シーケンスが必要なら、make-arrayでベクタを作り要素型を指定すれば、メモリレイアウトが連続になります。

;; 型指定ありのベクタ
(make-array 100 :element-type 'double-float)Code language: Lisp (lisp)

ランダムアクセスがO(1)になります。

SBCLではdeclareによる型宣言があるだけで、生成されるネイティブコードの品質が変わります4。

;; 型宣言なし
(defun sum-list (lst)
  (loop for x in lst sum x))

;; 型宣言あり
(defun sum-vector (vec)
  (declare (type (simple-array double-float (*)) vec)
           (optimize (speed 3) (safety 0)))
  (loop for x across vec sum x))

;; timeマクロで実測する
(let ((data (loop for i from 1 to 1000000 collect (float i 1.0d0)))
      (vec (make-array 1000000 :element-type 'double-float
                       :initial-contents (loop for i from 1 to 1000000
                                               collect (float i 1.0d0)))))
  (time (sum-list data))
  (time (sum-vector vec)))Code language: Lisp (lisp)

デフォルトは柔軟なまま、速さはプログラマーが意識して引き出す、という設計になっています。
それがCommon Lispの面白さであり、使いこなすときの注意点でもあるのです。

3.1. CとLispは「補う対象」が逆

Lispで効率よく計算するには、プログラマーが細かく指定して、その性能を引き出す必要があります。

効率を引き出す方法 ベクタを使う 連続メモリ配置 1 2 3 4 O(1) アクセス make-array キャッシュ効率◎ 型宣言を使う SBCLの最適化 declare + optimize ↓ ネイティブコード生成 speed 3 / safety 0 最大性能を引き出す コンパイル品質が変わる 設計思想 補う対象が逆 C：安全性をプログラマーが担保 デフォルト＝生のメモリ Lisp：効率をプログラマーが引き出す デフォルト＝表現力 GCで富豪的に使い捨て可 デフォルトは柔軟なまま、速さはプログラマーが意識して引き出す

Lispと同じように、プログラマーの自由と責任が大きい言語に、C言語があります。
C言語はハードウェアを直接記述するために生まれた言語で、デフォルトが生のメモリ操作、安全性はプログラマーが担保する。

対して、Lispは、いわば「思考を記述するための言語」で、デフォルトでは表現力、効率はプログラマーが引き出す。

どちらも「プログラマーが意識して補う」構造ですが、補う対象が正反対になっています。

3.2. 富豪的プログラミングと「神の言語」

Lispの設計では、効率性の問題は、ハードウェアによって解決されるだろうという、楽観的な考え方になっています。

実際、1970〜80年代にはLispマシンと呼ばれる専用ハードウェアが開発され、コンスセルの操作やGCをシリコンレベルで加速しようとしました5。

ガベージコレクション（GC）も同じ思想の表れです。
1958年の時点でLispはすでに GC を持っていて、「メモリ管理はプログラマーが考えなくていい」という設計になっていました6。
このGCを前提として、リストを気軽に使い捨てることが成立しています。

「富豪的プログラミング」とは、1997年の増井俊之さんによる言葉で7、ハードウェアリソースを惜しまず使って開発効率を上げるという考え方です。
しかし、Lispはこの言葉が生まれる前から、「問題の記述に集中する」ために、結果として「富豪的」な設計になっています。

効率はプログラマーが引き出すものとして、抽象度を極限まで高めることに振り切った設計なのです。

  1. carはContents of Address part of Register、cdrはContents of Decrement part of Registerの略。IBMの36ビットマシンIBM 704の命令フォーマットにあった2つの15ビットフィールドに由来する。最初の実装者Steve Russellは後に「ほかの名前を思いつかなかった」と述べており、firstとrestへの改名も試みられたが定着しなかった。 – CAR and CDR – Wikipedia
  2. Common LispではランダムアクセスにはO(n)のnthを使う。ベクタ（simple-array）ではO(1)のaref`が使える。HyperSpecでもリストとベクタの計算量の違いは明示されている。 – Common Lisp HyperSpec – Sequences
  3. マッカーシーは1960年に論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」を発表。S式、GC、ユニバーサルeval関数の概念を導入した、計算機科学史上の重要論文。 – McCarthy 1960 – jmc.stanford.edu
  4. SBCLは(optimize (speed 3) (safety 0))で最高速モードになり、型が確定した演算をボックス化なしで処理する。(disassemble #'関数名)で生成されたアセンブリを確認できる。 – SBCL User Manual – Efficiency
  5. LispマシンはMITのAIラボで開発され、SymbolicsとLMI（Lisp Machines Inc.）が商用化した。TexasInstrumentsのTI Explorer、XeroxのDoradoなども参入。Symbolicsの3600シリーズは1台7万ドルで販売されたが、汎用ワークステーションの台頭により1980年代末に市場から撤退した。 – Lisp machine – Wikipedia
  6. GCはマッカーニーが1958〜1959年にLispのために発明したマーク&スイープアルゴリズムが起源。現代のJava、Go、Pythonなどほぼすべての高水準言語が採用するGCの直接の祖先にあたる。 – Garbage collection – Wikipedia
  7. 増井俊之「富豪的プログラミング」bit誌1997年1月号初出。「ハードウェアは進化し続けるのだから、メモリや実行効率を気にせず気楽にソフトウェアを作る」という考え方。 – 富豪的プログラミング – 増井俊之