- Lispにはconsやcarなどの7つのプリミティブがあり、この7つだけでインタープリタを書ける。
- carとcdrという名前はIBM 704の命令フォーマットのフィールド名に由来し、実装者のラッセルがそのまま関数名にした。
- コンスセルはポインタ2本を持つ構造体で、nilで終端することでリストを形成し、map・filter・reduceなどの処理は再帰で表現できる。
1. 7つのプリミティブ
Lispには7つの基本関数があります。
cons・car・cdr・atom・eq・cond・lambda。
この7つだけで、Lispのインタープリタそのものが書けます。
「少ない概念で計算を記述できる」というLispの本質が、そこに凝縮されています。
処理系はCommon LispのSBCLを使います。
7つの関数は3つの層に分けられます。
cons / car / cdr ← リストを構築・分解する層
atom / eq ← アトムを判定・比較する層
cond / lambda ← 条件分岐と関数定義の層この7つで、任意の再帰関数を書けます。
チューリング完全です。
そして、Lispそのものに相当するのが、eval / apply。
コードをデータとして評価する層です。
一つ目の層から順に見ていきます。
cons は2つの値からコンスセルを作ります。car はセルの左側、cdr は右側を取り出します。atom はその値がアトム（リストでない単一の値）かどうかを返し、eq は2つのアトムが同じかどうかを返します。
* (cons 'a '(b c))
(A B C)
* (car '(a b c))
A
* (cdr '(a b c))
(B C)
* (atom 'x)
T
* (eq 'a 'a)
TCode language: Lisp (lisp)cond は条件分岐です。
複数の条件節を並べて、最初に真になった節の値を返します。
* (cond ((eq 'a 'b) 'no)
((eq 'a 'a) 'yes))
YESCode language: Lisp (lisp)lambda は関数を値として作ります。
Common Lispでは lambda 式を呼ぶとき funcall を使います。
* (funcall (lambda (x) (cons x '(b c))) 'a)
(A B C)Code language: Lisp (lisp)1.1. Lispとは何を解こうとした言語か
マッカーシーが1956年にLispの構想を始めたとき、AI研究に必要だと考えたのは、式そのものをデータとして扱い、変換・評価・推論できる言語でした。
当時の主流はFORTRANで、数値計算には向いていましたが、論理式や代数式のような記号を操作するには不向きでした。
その答えが「S式をリスト構造で表現し、少数のプリミティブで操作する」という設計です。
2. コンスセルとリスト
Lispのリストは、コンスセルという2つのフィールドを持つ構造体の連鎖でできています。cons で作り、左フィールドを car、右フィールドを cdr と呼びます。
* (cons 1 2)
(1 . 2)Code language: Lisp (lisp)これはドット対と呼ばれる最も基本的な形です。cdr に別のコンスセルを置くと連鎖が生まれ、末尾を nil にするとリストになります。
(cons 1 (cons 2 (cons 3 nil)))
[1 | ●]──→[2 | ●]──→[3 | nil]Code language: CSS (css)* (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)Code language: Lisp (lisp)見落としやすいのですが、このリストは左から右に読めても、内側から外側へと評価されます。
まず (cons 3 nil) が [3 | nil] を作り、次に (cons 2 ...) がその前に 2 を繋ぎ、最後に (cons 1 ...) が先頭に 1 を置く。nil から始まって後ろから前へ組み上がります。
これは再帰でリストを作るときに直接効いてきます。
先頭から順に cons で積んでいくと、できあがるリストは元の順序と逆になります。my-map や my-filter を自分で書くときに必ずぶつかる問題です。
2.1. car・cdrという名前の由来
car と cdr は、Lispを初めて見た人がほぼ必ず引っかかる名前です。
意味が読めない。
それもそのはずで、プログラミングの概念ではなく、1950年代の特定のハードウェアに由来しています。
マッカーシーは、IBM 704 を念頭に置いて、Lispを構想しました。
IBMがMITに704を設置する予定があり、マッカーシーはそのマシンで動かすつもりで設計しました。
コンピュータが届く前、ダートマスで紙の上で考えていた段階から、car・cdr・cons の概念はありました。
2.2. IBM 704 のデクリメント部
IBM 704は36ビットワードのマシンで、Type Aと呼ばれる命令フォーマットが次の構造を持っていました。
[prefix 3bit][decrement 15bit][tag 3bit][address 15bit]Code language: JSON / JSON with Comments (json)アドレス部はメモリのどこを参照するかを示します。
デクリメント部は「インデックスレジスタからいくつ引くか」を埋め込むフィールドです。
IBM 704のループは現代と逆向きで、カウンタをゼロに向かって減らしながら回します。
ゼロとの比較がハードウェアで最も安く実装できたからです。
ちょうどアセンブラで書くとこういう形になります。
LXD COUNT, 1 ; インデックスレジスタ1 にカウンタをセット
LOOP: ... ; 処理
TIX LOOP, 1, 1 ; レジスタ1 を 1 デクリメント、ゼロでなければ LOOP へこの「デクリメントする値を命令語に直接埋め込む」フィールドがデクリメント部です。
つまり、1命令でアドレス参照とカウンタ更新が同時にできる、この時代のCPU独特の最適化です。
2.3. 1ワードをコンスセルにする
マッカーシーはこの36ビットワードを見て、コンスセルの表現に使えると考えました。
アドレス部と デクリメント部に15ビットずつあり、フィールドを個別にロード・ストアする専用命令まで用意されていた。
リストのポインタ2本がちょうど収まります。
アドレス部に先頭要素へのポインタ、デクリメント部に残りのリストへのポインタを置く。
この設計は、コンピュータが届く前の紙の上での構想段階から決まっていました。
これを実装したのはラッセルです。car は “Contents of the Address part of Register”、cdr は “Contents of the Decrement part of Register” の略で、実装時にフィールド名がそのまま関数名になりました。
数ヶ月後、ラッセルとマッカーシーは first と rest の方がわかりやすいと気づいて使い替えを試みたそうです。
しかし、時すでに遅く変えられませんでした。
IBM 704は博物館の外に存在しなくなり、デクリメント部を使ったループも誰も書かなくなりました。
それでも car と cdr だけが生き残り、Common LispにもSchemeにもClojureにも引き継がれています。
2.4. consの戻り値と入れ子構造
ちなみに、当初の cons は、現在とは少し違う位置づけでした。
マッカーシーの構想段階では、cons は値を返す関数ではなく、メモリを確保して中身を詰めるサブルーチンとして定義されていました。
しかし、これをFORTRANベースのリスト処理言語FLPLを実装したゲルンターとガーベリッヒが「cons は値を返す関数であるべきだ」と気づき、関数として再定義しました。
その結果、cons の戻り値を別の cons に渡して入れ子にできるようになり、(cons 1 (cons 2 (cons 3 nil))) のように関数を合成してリストを組み立てる現在のスタイルが生まれました。
3. 再帰とリスト処理
7つのプリミティブが揃ったところで、リスト処理の基本パターンを自分で実装してみます。
いずれも「空なら底の値、そうでなければ先頭を処理して残りを再帰する」という骨格を持っています。
3.1. 変換（map）
リストの各要素に関数を適用し、新しいリストを作ります。
(defun my-map (f xs)
(if (null xs)
nil
(cons (funcall f (car xs))
(my-map f (cdr xs)))))Code language: Lisp (lisp)* (my-map #'1+ '(1 2 3 4))
(2 3 4 5)Code language: Lisp (lisp)cons で結果を積みながら再帰します。
組み込みでは mapcar が対応します。
3.2. 絞り込み（filter）
条件を満たす要素だけを残します。
(defun my-filter (pred xs)
(cond
((null xs) nil)
((funcall pred (car xs))
(cons (car xs) (my-filter pred (cdr xs))))
(t
(my-filter pred (cdr xs)))))Code language: Lisp (lisp)* (my-filter #'evenp '(1 2 3 4 5 6))
(2 4 6)Code language: Lisp (lisp)条件を満たすときだけ cons し、満たさないときは cons せずに次へ進みます。
組み込みでは remove-if-not が近いです。
3.3. 畳み込み（reduce）
リストを単一の値にまとめます。
(defun my-reduce (f init xs)
(if (null xs)
init
(my-reduce f
(funcall f init (car xs))
(cdr xs))))Code language: Lisp (lisp)* (my-reduce #'+ 0 '(1 2 3 4 5))
15Code language: Lisp (lisp)cons でリストを作らず、アキュムレータを更新しながら末尾再帰で進みます。
組み込みでは reduce が対応します。
3.4. 末尾再帰とSBCL
my-map と my-filter は末尾再帰ではありません。
再帰の外側に cons があるため、再帰のたびにスタックフレームが積まれます。
長いリストではスタックオーバーフローのリスクがあります。
アキュムレータを使って書き換えると末尾再帰になりますが、その場合は結果のリストが逆順になります。
最初に触れた「リストは後ろから組み上がる」という性質がここで顔を出します。
逆順を直すには最後に nreverse を呼ぶか、アキュムレータに積む前に反転する工夫が必要です。
Common Lisp規格は末尾再帰最適化を義務付けていませんが、SBCLは最適化宣言のあるコンパイル済みコードで実際に行います。
(defun my-reduce (f init xs)
(declare (optimize (speed 3) (debug 0)))
(if (null xs)
init
(my-reduce f (funcall f init (car xs)) (cdr xs))))Code language: Lisp (lisp)declare で最適化レベルを指定すると、SBCLはこれをループと同等のコードにコンパイルします。
REPLに直接貼り付けるだけでは適用されないこともあるので、compile 関数か .lisp ファイルへのコンパイルを経由するのが確実です。
4. evalとは何か
マッカーシーが1960年に発表した論文 “Recursive Functions of Symbolic Expressions and Their Computation by Machine” の核心は、eval という関数の定義です。
eval はLisp式を受け取り、その値を返します。
引数として式と、変数の値を保持する環境リストを取ります。
(eval 式 環境)Code language: Lisp (lisp)マッカーシーがこれを書いたのは、「Lispとはどういう言語か」を数学的に定義するためでした。
チューリングマシンより簡潔にLispを形式化できることを示す道具で、コンパイラとして実装するつもりで書いたものではありませんでした。
ところが、ラッセルがこれを読んで「機械語で動かせる」と気づき、実際にインタープリタを実装しました。
もともとLispコンパイラを作ろうとしていたマッカーシーにとって、「実行時にコードを受け取って評価する」evalの実装は困難なものでした。
しかし、インタープリタなら、S式をそのままデータとして扱いながら実行するので、evalが自然に乗ります。
マッカーシー自身も後に「インタープリタの出現が言語の形を固めた」と書いています。
4.1. プリミティブでevalを組み立てる
7つのプリミティブからevalの核心を作ります。
ここでは簡略版として、基本的な式の評価と関数適用を扱います。
まず補助関数を用意します。lookup は環境リストから変数の値を探します。
(defun lookup (var env)
(cond ((null env) (error "unbound variable: ~a" var))
((eq var (car (car env)))
(car (cdr (car env))))
(t
(lookup var (cdr env)))))Code language: Lisp (lisp)環境は ((変数 値) ...) というリストの連鎖です。car でペアを取り出し、caar でキーを、cadar で値を得ます。
* (lookup 'x '((x 1) (y 2)))
1Code language: Lisp (lisp)次が my-eval です。
(defun my-eval (expr env)
(cond
;; アトムなら変数として環境から取得
((atom expr)
(lookup expr env))
;; (quote x) ならxをそのまま返す
((eq (car expr) 'quote)
(car (cdr expr)))
;; (atom x) の評価
((eq (car expr) 'atom)
(atom (my-eval (car (cdr expr)) env)))
;; (eq x y) の評価
((eq (car expr) 'eq)
(eq (my-eval (car (cdr expr)) env)
(my-eval (car (cdr (cdr expr))) env)))
;; (car x) の評価
((eq (car expr) 'car)
(car (my-eval (car (cdr expr)) env)))
;; (cdr x) の評価
((eq (car expr) 'cdr)
(cdr (my-eval (car (cdr expr)) env)))
;; (cons x y) の評価
((eq (car expr) 'cons)
(cons (my-eval (car (cdr expr)) env)
(my-eval (car (cdr (cdr expr))) env)))
;; (cond ...) の評価
((eq (car expr) 'cond)
(my-eval-cond (cdr expr) env))
;; 関数適用
(t
(my-apply (my-eval (car expr) env)
(my-evlist (cdr expr) env)))))
(defun my-eval-cond (clauses env)
(cond ((null clauses) nil)
((my-eval (car (car clauses)) env)
(my-eval (car (cdr (car clauses))) env))
(t
(my-eval-cond (cdr clauses) env))))
(defun my-evlist (exprs env)
(cond ((null exprs) nil)
(t (cons (my-eval (car exprs) env)
(my-evlist (cdr exprs) env)))))
(defun my-apply (fn args)
(cond
;; (lambda (params) body) の適用
((eq (car fn) 'lambda)
(my-eval (car (cdr (cdr fn)))
(my-pair (car (cdr fn)) args)))
(t
(error "unknown function"))))
(defun my-pair (params args)
(cond ((null params) nil)
(t (cons (list (car params) (car args))
(my-pair (cdr params) (cdr args))))))Code language: Lisp (lisp)my-eval の中身を見ると、7つのプリミティブそれぞれに対応する節があります。cond で式の種類を判定し、再帰的に評価する仕組みになっています。
eval自体がconsとcarとcdrとcondとatomとeqで書かれています。
「Lispはlispで書ける」という性質がここに現れています。
SBCLで動かしてみましょう。
* (my-eval '(cons (quote a) (quote (b c))) '())
(A B C)
* (my-eval '(car (cons (quote a) (quote (b c)))) '())
A
* (my-eval '(cond ((eq (quote a) (quote b)) (quote no))
((eq (quote a) (quote a)) (quote yes)))
'())
YES
* (my-eval '((lambda (x) (cons x (quote (b c)))) (quote a)) '())
(A B C)Code language: Lisp (lisp)この記事で見てきたことを振り返ると、7つのプリミティブはそれぞれ独立した道具ではありません。
リストを構築・分解する層の上に関数定義の層が乗り、その頂点にevalが立つという構造です。
マッカーシーが紙の上で構想し、ラッセルが機械語で動かしたこの設計は、70年近くを経ても変わっていません。car を打つたびに、真空管が並んだIBM 704のデクリメント部が、名前の中に生きています。