CARとCDR

コンピュータプログラミングでは、CAR（car）/ k ɑːr / ^ⓘとCDR(cdr) (/ ˈ k ʌ d ər / ^ⓘまたは/ ˈ k ʊ d ər / ^ⓘ ) は、 Lisp プログラミング言語コンスセル (または「非アトミックS 式」)に対する基本的な操作です。コンス セルは 2 つのポインタ。car操作は最初のポインタを抽出し、cdr操作は 2 番目のポインタを抽出します。

したがって、式はと評価され、 はと評価されます。 (car (cons x y))x(cdr (cons x y))y

コンス セルが、ツリーやその他のより複雑な構造ではなく、単方向リンク リストを実装するために使用される場合、car操作はリストの最初の要素を返し、 cdr はリストの残りの部分を返します。このため、操作にはfirstとrestまたはheadとtailという名前が付けられることがあります。

Lisp はもともと 1950 年代後半にIBM 704コンピュータに実装されました。

CARとCDRはそれぞれ「アドレスレジスタの内容」と「デクリメントレジスタの内容」の略であるという一般的な説明^[1]は、IBM 704のアーキテクチャと完全には一致しません。IBM 704にはプログラマがアクセスできるアドレスレジスタがなく、3つのアドレス変更レジスタはIBMによって「インデックスレジスタ」と呼ばれています。

704 とその後継機は、36 ビットの ワード長と 15 ビットのアドレス空間を備えています。これらのコンピュータには 2 つの命令形式があり、そのうちの 1 つであるタイプ A には、短い 3 ビットのオペレーション コードプレフィックスと、3 ビットのタグで区切られた2 つの 15 ビットフィールドがあります。最初の 15 ビット フィールドはオペランド アドレスで、2 番目にはデクリメントまたはカウントが格納されます。タグは 3 つのインデックス レジスタの 1 つを指定します。704 ではインデックス作成は減算プロセスであるため、インデックス レジスタにロードされる値は「デクリメント」と呼ばれていました。^{[2] : p. 8} 704 ハードウェアには、ワード内のアドレス フィールドとデクリメント フィールドにアクセスするための特別な命令がありました。^{[2] : p. 26}その結果、これら 2 つのフィールドを使用して、リストに必要な 2 つのポインタを 1 つのワード内に格納することが効率的でした。^{[3] : Intro.}

したがって、「CAR」は「レジスタのアドレス部分の内容」です。この文脈での「レジスタ」という用語は「メモリ位置」を指します。 ^{[4] [5]}

Lispの前身^{[6] [7]}には以下の関数が含まれていた:

• car（「レジスタ番号のアドレス部分の内容」）、
• cdr（「レジスタ番号の減算部分の内容」）、
• cpr（「レジスタ番号のプレフィックス部分の内容」）、および
• ctr（「レジスタ番号のタグ部分の内容」）、

それぞれの関数は、マシン アドレスを引数として受け取り、対応するワードをメモリからロードし、適切なビットを抽出します。

704アセンブラ マクロは次の通りcarです: ^{[8] [9] [10]}

LXD JLOC 4 # C ( JLOC の減分) → C( C ) # 位置 JLOC の減分をインデックス レジスタ C にロードします。CLA 0、4 # C ( 0 - C( C ) ) → C ( AC ) # AC レジスタはリストの開始アドレスを受け取ります。PAX 0、4 # C( ACのアドレス) → C( C ) # AC のアドレスをインデックス レジスタ C にロードします。PXD 0、4 # C( C ) → C( ACの減分) # AC をクリアし、インデックス レジスタ CをAC の減分にロードします。    
      
      
      

704アセンブラマクロは次の通りcdrです: ^{[8] [9] [10]}

LXD JLOC 4 # C ( JLOC の減分) → C( C ) # 位置 JLOC の減分をインデックス レジスタ C にロードします。CLA 0、4 # C ( 0 - C( C ) ) → C ( AC ) # AC レジスタはリストの開始アドレスを受け取ります。PDX 0、4 # C( ACの減分) → C( C ) # AC の減分をインデックス レジスタ C にロードします。PXD 0、4 # C( C ) → C( ACの減分) # AC をクリアし、インデックス レジスタ CをAC の減分にロードします。    
      
      
      

マシンワードは、4 つの引数 ( a、d、p、t ) を取るconsによって再構成できます。

Lispの設計の初期段階ではプレフィックスとタグの部分は削除され、CAR、CDR、および2つの引数を持つCONSが残りました。^[3]

と の合成にcarは、cdr同じ形式の短くて多少発音しやすい名前を付けることができます。Lisp では、は(cadr '(1 2 3))と同等であり(car (cdr '(1 2 3)))、その値はです。2同様に、(caar '((1 2) (3 4)))( / ˈ k eɪ ɑːr /と発音) は と同じであり(car (car '((1 2) (3 4))))、その値は です。Common LispやScheme など1のほとんどの Lisp では、との 2 つから 4 つの合成のすべてのバリエーションが体系的に定義されています。 carcdr

多くの言語 (特に関数型言語や関数型パラダイムの影響を受けた言語)は、片方向リンクリストを基本データ構造として使用し、 や に似たプリミティブまたは関数を提供しますcar。cdrこれらはfirst、restやhead、tailなど、さまざまな名前で呼ばれます。ただし、Lisp では、コンスセルはリンクリストの構築だけでなく、ペア構造やネストされたペア構造の構築にも使用されます。つまり、cdrコンスセルの はリストである必要はありません。この場合、他のほとんどの言語では、ペア構造とリスト構造を型的または意味的に区別するのが一般的であるため、異なるプリミティブを提供します。特に型付き言語では、リスト、ペア、およびツリーはすべて、異なる型シグネチャを持つ異なるアクセサ関数を持ちます。たとえば、Haskellでは、ペア型を扱う場合、carおよび はおよび にcdrなります。したがって、 との正確な類似物は他の言語でまれです。Clojureでは、の代わりにまたは の代わりにを使用します。 一方、Logoでは、の代わりにおよびを使用します。 fstsndcarcdrfirstcarnextrestcdrfirstcarbutfirstcdr

注記

• ラッセル、スティーブ。「プログラムの作成とデバッグ」(PDF)。RLE および MIT 計算センター。CSAIL出版物およびデジタル アーカイブ(メモ) 。AI メモ、第 6 号。マサチューセッツ州ケンブリッジ: MIT 人工知能研究所。OCLC 35415961。2017年 7 月 6 日の オリジナル(PDF)からアーカイブ。2017年7 月 20 日閲覧。
• Faase, Frans (2006-01-10)。「LISP における CAR と CDR の起源」。
• グレアム、ポール(1996)。ANSI Common Lisp。プレンティス ホール。ISBN 978-0-13-370875-2。
• Barski, Conrad (2010)。Land of Lisp: ゲームごとに Lisp プログラミングを学ぼう!サンフランシスコ、カリフォルニア州: No Starch Press, Inc. ISBN 978-1-59327-281-4。
• McCarthy, John (1960). 「記号式の再帰関数と機械による計算、パート I」(PDF) . Communications of the ACM . 3 (4). ACM ニューヨーク、NY、米国: 184–195. doi :10.1145/367177.367199. S2CID  1489409.