CARとCDR
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/%E3%82%B3%E3%83%B3%E3%82%B9%E3%82%BB%E3%83%AB.png/220px-%E3%82%B3%E3%83%B3%E3%82%B9%E3%82%BB%E3%83%AB.png)
名前と語源
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, https://www.gnu.org/software/emacs/manual/html_node/eintr/Strange-Names.html
- ^ From the IBM 704 to the IBM 7094, How Does A Computer Work?, http://www.quadibloc.com/comp/cp0309.htm
- ^ 英: 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. https://www.scheme.com/tspl4/objects.html#./objects:h3
参考文献
- Guy L. Steele Jr.『COMMON LISP 第2版』共立出版、1992年。ISBN 4320025881。 (英語オンライン版:Guy L. Steele Jr., Common Lisp the Language, 2nd Edition, http://www.cs.cmu.edu/afs/cs/Web/Groups/AI/html/cltl/clm/clm.html )