INFOSEKOLAH.NET

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) と表され、リスト (e₁ e₂ e₃) は、各要素を car 関数で取り出せるところのコンスセルと、後続のコンスセルを cdr 関数で取り出せるところの片方向リスト、すなわち (e₁ . (e₂ . (e₃ . 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)))))

のように定義できる。

脚注

^ ^a ^b “Strange Names”, An Introduction to Programming in Emacs Lisp
^ From the IBM 704 to the IBM 7094, How Does A Computer Work?
^ 英: Contents of the Address part of the Register
^ 英: Contents of the Decrement part of the Register
^ COMMON LISP 第2版 p.25。なおCommon Lispでは最後の要素のCDRが空リストでないものは「ドットリスト」と呼ばれてリストとは別扱いされる。
^ COMMON LISP 第2版 p.361
^ R. Kent Dybvig (2009). “Operations on Objects”. The Scheme Programming Language (4th ed.). The MIT Press. ISBN 978-0-262-51298-5

参考文献

Guy L. Steele Jr.『COMMON LISP 第2版』共立出版、1992年。ISBN 4320025881。（英語オンライン版：Guy L. Steele Jr., Common Lisp the Language, 2nd Edition ）

[elisp-1] “Strange Names”, An Introduction to Programming in Emacs Lisp

[2] From the IBM 704 to the IBM 7094, How Does A Computer Work?

[3] 英: Contents of the Address part of the Register

[4] 英: Contents of the Decrement part of the Register

[5] COMMON LISP 第2版 p.25。なおCommon Lispでは最後の要素のCDRが空リストでないものは「ドットリスト」と呼ばれてリストとは別扱いされる。

[6] COMMON LISP 第2版 p.361

[7] R. Kent Dybvig (2009). “Operations on Objects”. The Scheme Programming Language (4th ed.). The MIT Press. ISBN 978-0-262-51298-5

[1]

[2]

[3]

[4]

[5]

[6]

[7]

INFOSEKOLAH.NET

CARとCDR

名前と語源

概要

応用

脚注

参考文献

Content Disclaimer