CARとCDR
名前と語源
[編集]CAR はCDR は
この不可解な名称は、最初に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)))))
のように定義できる。
脚注
[編集]- ^ 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）