CARCDRカーとクダーは、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]

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

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

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

応用編集

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

たとえば、リストの最後の要素を得る 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)))))

のように定義できる。

脚注編集

  1. ^ a b “Strange Names”, An Introduction to Programming in Emacs Lisp, https://www.gnu.org/software/emacs/manual/html_node/eintr/Strange-Names.html 
  2. ^ From the IBM 704 to the IBM 7094, How Does A Computer Work?, http://www.quadibloc.com/comp/cp0309.htm 
  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. https://www.scheme.com/tspl4/objects.html#./objects:h3 

参考文献編集