CARとCDR

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

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

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

 概要 
LISPにおいて、コンス（またはペア、またはドット対）は2つの要素を持つ順序対である。1番目の要素をCAR、2番目の要素をCDRと呼ぶ。リストは「空リスト nil または CDRがリストであるところのコンスセル」であると再帰的に定義されるCOMMON LISP 第2版 p.25。なおCommon Lispでは最後の要素のCDRが空リストでないものは「ドットリスト」と呼ばれてリストとは別扱いされる。。

具体的にいうと、要素 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では空リストを返すCOMMON LISP 第2版 p.361。Schemeではエラーになる。

 応用 
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)))))
のように定義できる。

 脚注 

 参考文献 
 （英語オンライン版：）

Category:LISP