CARとCDR

CARとCDR（カーとクダー）は、LISP言語の基本的なデータ型であるリストを操作するためのもっとも基本的な2つの関数である。LISP言語のリストはコンスセルと呼ばれる（ペアまたはドット対とも呼ばれる）二分木構造セルにより表現され、CARは二分木の片側を返しこれはリストの先頭の要素である。またCDRは二分木のもう片側を返しこれは後続する二分木セルである。

コンスセル

名前と語源

CAR は/kɑɹ/（カー）と発音され、CDR は/ˈkʊdəɹ/（クダー）と発音される^[1]。

この不可解な名称は、最初にLISPが開発されたIBM 704の命令形式に由来する。IBM 704は36ビット・ワードの機械で、タイプAの命令形式ではこれを3ビットのプレフィックス（オペコード）、15ビットのデクリメント、3ビットのタグ、15ビットのアドレスの4つの部分に分けて用いた^[2]。CAR は「レジスターのアドレス部の中身」^[3]を、CDRは「レジスターのデクリメント部の中身」^[4]を意味する略語だった。現在ではこの名称は無意味なものになっている^[1]。

Common Lispでは、より意味のあるfirst（「最初のもの」を意味する）およびrest（「残りのもの」を意味する）という関数も用意されているが、古い名称もひき続き使われている。

概要

LISPにおいて、コンス（またはペア、またはドット対）は2つの要素を持つ順序対である。1番目の要素をCAR、2番目の要素をCDRと呼ぶ。リストは「空リスト nil または CDRがリストであるところのコンスセル」であると再帰的に定義される^[5]。

具体的にいうと、要素 a と b から構成されるコンスは (a . b) と表され、リスト (e1 e2 e3) は、各要素を car 関数で取り出せるところのコンスセルと、後続のコンスセルを cdr 関数で取り出せるところの片方向リスト、すなわち (e1 . (e2 . e3 . nil)) として実現されている。したがって、リストの先頭の要素を得るのは、最後の要素を得るのに比べて効率がよい。

リスト L の2番目の要素は (car (cdr L))、3番目の要素は (car (cdr (cdr L))) のようにして得られる。

関数 car と cdr の引数が空リスト nil である場合、Common Lispでは空リストを返す^[6]。Schemeではエラーになる^[7]。

応用

carとcdrを再帰や条件分岐と組み合わせることで、リスト関係のさまざまな関数を作ることができる。

たとえば、リストの最後の要素を得る last 関数は、

(defun last (L)
  (if (consp (cdr L)) ; L のCDR部分がコンスセルである場合
    (last (cdr L))
; else
    (car L)))

リストの長さを得る関数 length は、

(defun length (L)
  (if (null L) ; L が空リストである場合
    0
; else
    (+ 1 (length (cdr L)))))

のように定義できる。