【Lisp】
CAR と CDR に刻まれた計算機の歴史
（FortranとIBM 704）

by
  • 1958年、John McCarthyはIBM 704上でLispを設計し、そのリスト操作関数 car と cdr の名前はIBM 704のレジスタ名に由来する。
  • IBM 704はFortranの行列演算のために2つのアドレスフィールドを持つ36bitワード構造を採用しており、McCarthyはこれをコンスセルの実装に流用した。
  • FortranはLispの誕生を、ハードウェア設計と「数式を扱う言語が成立する」という前例の両面で支えた。

関連記事

1. CARとCDR、奇妙な名前

Lispを学び始めた人が最初に戸惑うのが、car と cdr という名前です。
head でも first でも value でもなく、なぜ car と cdr なのか。

CARとCDR — 名前の起源 IBM 704 1954年 真空管メインフレーム 36bit ワード構造 Address (CAR) Decrement (CDR) 15 bit 15 bit ↓ Lisp コンスセルへ流用 data (car) next (cdr) レジスタ名がそのまま関数名になった

この名前は、1950年代のコンピュータ、IBM 704のアーキテクチャに由来します。
この機械のレジスタ名が、そのまま関数名として今日まで使われています1。

その経緯を辿ると、コンピュータという機械が「何をする道具」として発展してきたのか、歴史が見えてきます。

FORTRAN, LISPは、現代の一般的なFortran, Lispで表記します。

1.1. 冷戦とIBM 704

1958年、MITのJohn McCarthyがLispの設計を始めました2。
このLispが動作するハードウェアとして、当初からIBM 704が想定されました。
McCarthyの研究室があるMITに、このIBM 704が導入される計画があったからです。

遡ること4年前の1954年、IBMは704という真空管メインフレームを発表しました。
これは、床面積は100平方メートルを超える大型コンピュータで、設置には専用に建てた部屋が必要なほど。
磁気テープ装置が複数台、カードリーダーやプリンターが並び、それらをすべて含めた「コンピュータシステム」が一つの施設を占有していました3。

この機械が生まれた背景には米ソの冷戦があります。
第二次大戦後、核開発競争と宇宙開発競争は、計算能力への国家的な需要を急激に膨らませました。
弾道ミサイルの軌道計算、核爆発のシミュレーション、航空機の流体力学解析。
これらはすべて膨大な数値計算を必要とし、当時「Computer」と呼ばれていた人間の計算担当者が行っていた仕事を機械に置き換えることが喫緊の課題でした。

IBM 704はその要請に応えた機械です。
量産機として初めて浮動小数点演算をハードウェアで実装し、36bitのワード長で高精度な数値を扱えました4。
設計を主導したのはGene AmdahlとJohn Backusで、同じチームがほぼ同時期にコンピュータ言語Fortranも開発しています5。

Fortranは、Formula Translationの略です。
数式をそのままプログラムとして書けるという発想で、行列演算やループを簡潔に記述できました。
というのも、それまでの計算機は、配線の差し替えやスイッチ制御で、基本的な演算命令を一つ一つ打ち込む必要があったからです。

1.2. 36bitワードと2アドレス構造

IBM 704の命令フォーマットは独特の構造を持っていました。

これは、IBM 704のアーキテクチャが、36bitの浮動小数点数、行列演算のための命令セット、配列操作を効率化するインデックスレジスタなど、Fortranのニーズから逆算して設計されていたこととも関係します6。

IBM 704のデータ処理単位は 1ワード 36bitです。
この36bitは、浮動小数点数の計算と行列演算をそれぞれの効率的に処理するために、違った使われ方ができるように設計されていました。

1ワードは、アドレス部15bit、デクリメント部15bit、タグ部3bit、プレフィックス部3bitに分割されていたことです7。

この設計は、Fortranの配列操作の効率化のためです。
デクリメント部は行列を逆順にたどる処理を、ハードウェアレベルで効率化するための仕組みで、インデックスレジスタに格納され、ループのたびに減算されてベースアドレスからオフセットを差し引いていきます。

1ワードに2つのアドレスが収まり、 {base_address, offset} という構造があったのです。
アドレス部とデクリメント部はそれぞれ15bitなので、2の15乗で32768、つまり32Kワードのメモリ空間を指定できます。

1.3. base+offset が data+next になった瞬間

このIBM 704の1ワード構造にあるアドレス部と、デクリメント部が、Lispのcar、cdrの起源になっています。

McCarthyは、Lispを設計するさい、リスト構造を表現する「コンスセル」の設計を考えていました。
そこで、Fortranの行列計算のために使われている、アドレス部とデクリメント部がうまく使って効率的に動かすアイデアを持っていました。

コンスセルは、データへのポインタと次のセルへのポインタを1つの単位にまとめたもの。
これをつないでリスト構造を作ります。
そのため、{data, next} という2つのアドレスを格納できる構造が必要でした。

IBM 704の1ワードには、アドレス部とデクリメント部という2つの15bitフィールドがすでにあったので、{base_address, offset} は {data, next} として読み替えて使うことにしたのです。

つまり、Fortranの配列操作のために設計されたデータ形式が、リスト処理のコンスセルとして流用され、car/cdrという名前を生みました。

  • car はContents of the Address Registerの略で、アドレス部に格納された値を取り出す操作です。
  • cdr はContents of the Decrement Registerの略で、デクリメント部から値を取り出します。

IBM 704の物理的なレジスタ名が、そのままLispの関数名になりました8。

まだ、計算機アーキテクチャに固有の計算システムを作る時代で、704専用の設計としてその構造に乗っかったわけです。

2. FortranがLispの母胎になった

つまり、Fortranが整えたハードウェアと予算と研究環境が、Lispの誕生を支えたのです。

FortranがLispの母胎になった Fortran / IBM 704 数値計算・行列演算 36bitワード構造 → コンスセルの物理基盤 car / cdr の誕生 Lisp (McCarthy, 1958) 記号処理・式の変換 「数式を扱う」前例 → 次の問いへ 記号処理 → AI へ ハードウェアと思想、両面でFortranがLispを支えた

ひとつは、先ほどのハードウェアの系譜です。
Fortranのために設計されたIBM 704のワードフォーマットが、car/cdrの物理的な基盤になりました。
Fortranのための機械の骨格から、Lispの最小単位が削り出されています。

もうひとつは、計算の系譜です。
Fortranが「プログラミング言語が科学計算の道具として成立する」という前例を作り、その実績の上でLispは別の問いを持って生まれました。

機械語を直接打ち込む時代から、Fortranが「数式を計算すること」を実現しました。
この有用性が広まると、次の問いが生まれました。
それが、「数式の構造そのものを扱う」ということ。

たとえば、微積分の式を数値として評価する前に、式の構造を変形し簡約する。
いわば、Fortranで数式を書く補助として式変換が必要になったのです。
Lispの解こうとする記号処理の初期の問題は、この数式の変換だったのでした9。

2.1. 計算機と知的作業の自動化

コンピュータの歴史には繰り返されるパターンがあります。
今Intelligentと呼ばれることが、数年後にAutomationになるということです。

1940年代、弾道計算は高度な知的作業でした。
熟練した人間のComputerが何日もかけて行っていた仕事を、機械が引き受けました。
それが機械化されると、弾道計算はAutomationになりました。
自動化された作業は当たり前になり、もはや「知的」とはみなされなくなります。

1950年代、次なるIntelligentなフロンティアとして、式の変換や記号処理が現れました。
Lispはその次のフロンティアを開こうとしました。
数式を記号として扱い、微分や積分を自動的に実行し、論理式を推論する。
これらは1950年代には高度な知的作業でしたが、少しずつ自動化されていきます。

2.2. 冷戦の科学技術の予算獲得

ただ、McCarthyの関心は、さらにその先にありました。

記号処理の自動化ではなく、機械が推論する汎用AIです。
1956年のダートマス会議で「人工知能（AI）」という言葉を作ったのもMcCarthyで、Lispはその夢のための言語として構想されていました10。

しかし、夢だけでは資金は来ません。
Fortranは弾道計算という自明なニーズがありましたが、Lispの実用性についてはまだ証明されていません。

そこで、McCarthyがARPAの前身から研究費を引き出した名目は「ソ連の技術文書の自動翻訳」でした。
冷戦下でロシア語の科学論文や軍事文書を英語に自動変換できれば、諜報活動に直結します。記号処理言語の研究費はその文脈で正当化されやすかった11。

翻訳という現世利益を前面に出しながら、その奥でMcCarthyはAIを構想していました。
ただ、機械翻訳は実際には難しく、1966年のALPACレポートで「機械翻訳は役に立たない」と結論づけられ、AIへの予算が大幅に削られました。
最初の「AIの冬」の一因です12。

ただ、名目が崩れても、Lispという言語はMITに根付いていました。

3. ハッカー文化とLisp

Lispが生き延びたのは、MITのAI研究所というコミュニティがあったからです13。

ハッカー文化とLispの生存 なぜ生き残ったか コード＝データ (S式) 言語自体を拡張できる 最小の公理系 car / cdr / cons / lambda … MIT AI研究室コミュニティ Lispマシンまで製作 知的作業の自動化サイクル 弾道計算 → 自動化 記号処理 → Lisp 推論・AI へ Intelligentな作業は やがてAutomationになる car/cdrという名前に、計算機の問いの変遷が刻まれている

MITのハッカー文化は、1960年代に育ち始めました。
「システムを深く理解して、設計者が想定しなかった使い方を見つける」という姿勢がその核にあります。

Lispがハッカー文化と相性が良かったのは、プログラムが自分自身を書き換えたり生成したりできたことです。
コードとデータが同じS式という構造で表現されているため、言語自体を拡張する余地が大きかったのです。
面白いことに、計算機が考えるための柔軟な言語設計が、もっとも計算機を深く理解しようとする人間（ハッカー）に好まれたわけです。

ちなみに、McCarthyはその後スタンフォードに移り、ロボティクスと論理推論の形式化に向かいました。
彼のテーマは、自ら思考する機械でした。
一方、言語としてのLispは、MITのAI研究室を中心としたコミュニティで研究され、LispマシンというLisp専用ハードウェアまで作りました14。

3.1. 最小の公理が残った理由

Lispが数十年後も参照される理由は、car/cdrという操作の抽象が今も有効だからです。

FortranがDO文もIF文もサブルーチンも最初から個別の部品として持っていたのに対して、Lispは最小の要素から組み上げる方向で設計されていました。

Lispのコアは驚くほど小さいです。
公理系に近い構造で、car、cdr、cons、atom、eq、lambda、cond、といった基本操作から言語のほぼすべてが導けます。15。

チューリング完全な体系は無数にありますが、実用的で最小に近いものはほとんどありません。
これは、McCarthyがチャーチのラムダ計算に影響を受け、計算の数学的なモデルを実装可能な形に落としたことによります。
それゆえ、時代に依存しない普遍性があるのかもしれません16。

ラムダ計算もチューリング完全ですが、実用にはほど遠いです。
Lispはそこに実際のメモリ管理とS式を乗せて、辛うじて実用側に着地させました。

4. ビットに刻まれた歴史

car/cdrという名前は、今日のLispやClojureやSchemeの実装では文字通りの意味を持ちません。
現代の処理系はIBM 704のワードフォーマットを使っておらず、アドレス部もデクリメント部も存在しません。

それでもcarとcdrという名前は残っています。

名前の下には1954年の真空管メインフレームがあり、冷戦の国防予算があり、Fortranの行列演算のために設計されたワードフォーマットがあります。
Fortranが地ならしした土地に、Lispが別の問いを持って芽吹いた。
その瞬間に生まれた名前が、ハードウェアの制約がとっくに消えた後も生き続けています。

「計算する機械」から「記号を処理する機械」へ、さらに「推論する機械」へ。
その問いの変遷を、carとcdrという2つの関数名が静かに記録しています。

  1. car はContents of the Address Register、cdr はContents of the Decrement Registerの略。ただし厳密には、IBM 704にはプログラマが直接アクセスできる「アドレスレジスタ」は存在せず、インデックスレジスタと呼ばれる3本のレジスタがあった。「Register」という語はメモリ上のフィールドを指す意味で使われている。 – IBM 704 – Wikipedia
  2. McCarthyがLispの設計を始めた直接の動機は、微分計算を行うプログラムを設計しようとした際に、条件式と再帰関数の扱いにFortranが不十分だと感じたことだった。Lispの設計論文は1960年にCommunications of the ACMに「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」として発表された。 – How Lisp Became God’s Own Programming Language – twobithistory.org
  3. IBM 704には真空管が約4000本使われており、冷却のために32トン分のエアコンが必要だった。1955年から1960年の間に123台が出荷されている。 – IBM 704 Scientific Computer – ZL2AL
  4. 704は毎秒最大12,000回の浮動小数点加算を実行できた。当時「複雑な数学を扱える事実上唯一のコンピュータ」と見なされていた。 – IBM 704 – Wikipedia
  5. John BackusはFortranの主設計者であり、同時に704のアーキテクト。Gene Amdahlはのちに IBM System/360 の主任設計者となり、1970年にはIBM競合のAmdahl Corporationを設立している。 – The IBM 704 – Columbia University
  6. Fortranの識別子が6文字に制限されているのも、704の6ビットBCD文字セットと36ビットワードに由来する。 – The IBM 704 – Columbia University
  7. 704はさらに38bitのアキュムレータと36bitの乗算・商レジスタを持ち、3本の15bitインデックスレジスタがあった。インデックスレジスタの内容はベースアドレスから減算されるため「デクリメントレジスタ」とも呼ばれた。 – IBM 704 – Wikipedia
  8. 最初のLispインタープリタは、McCarthyの学生であるSteve Russellが704向けに実装した。McCarthyはeval関数が実際に機械語として動くとは思っていなかったため、Russellの実装に驚いたと後に語っている。 – LISP: John McCarthy’s Language for AI (1958-1960)
  9. McCarthyがLispの構想を始めたのは1956年のダートマス会議の場でだったと自ら記している。その際にNewell、Shaw、SimonがIPL 2というリスト処理言語を紹介したことも影響を与えたが、FortranのようなAlgebraicな記法の方が魅力的だと感じてLispを独自に設計した。 – History of Lisp – jmc.stanford.edu
  10. ダートマス会議の正式名称は「Dartmouth Summer Research Project on Artificial Intelligence」。1955年8月31日にMcCarthy、Minsky、Rochester、Shannonの4名が提案書を作成し、ロックフェラー財団に資金を申請した。提案書の中で初めて「artificial intelligence」という言葉が使われた。 – Dartmouth workshop – Wikipedia
  11. McCarthyのLisp研究はMIT Research Laboratory of ElectronicsとARPAの資金で支援されていた。資金提供者にはUS Army Signal Corps、US Air Force、US Navyが含まれている。これはMcCarthyの1960年論文の謝辞に明記されている。 – Recursive Functions of Symbolic Expressions… – Stanford
  12. ALPACはAutomatic Language Processing Advisory Committeeの略。1964年にJohn R. Pierceを委員長とする7名の科学者で構成され、米国政府が機械翻訳研究の進捗を評価するために設置した。1966年11月の報告書は機械翻訳を「人間の翻訳より遅く、精度が低く、コストが高い」と結論し、約20年にわたり機械翻訳研究への政府資金が途絶えた。 – ALPAC – Wikipedia
  13. MIT AI LabはMcCarthyとMinskyが1959年に共同設立した。正式名称はArtificial Intelligence Projectで、2003年にLaboratory for Computer ScienceとCSAIL（MIT Computer Science and Artificial Intelligence Laboratory）として統合されるまで存続した。 – Marvin Minsky – Computer History Museum
  14. LispマシンはMIT AI LabでRichard GreenblattとTom Knightらが1970年代に開発した。1979年にGreenblattがLisp Machines Inc.（LMI）を、同年にSymbolicsが設立されて商用化されたが、1980年代後半に汎用ワークステーションの性能向上により市場から撤退した。 – MIT Computer Science and Artificial Intelligence Laboratory – Wikipedia
  15. Paul GrahamはMcCarthyの1960年論文について「計算を公理化しようとした試み」と評し、Lispの設計がほぼ7つの基本演算から導出できることを示した。 – How Lisp Became God’s Own Programming Language – twobithistory.org
  16. McCarthyの1960年論文はChurchのラムダ計算（1941年）を直接引用しており、匿名関数の記法をChurchから借用したと明記している。 – Recursive Functions of Symbolic Expressions… – Stanford