Comments
Description
Transcript
プログラミング言語
2007年度 早稲田大学理工学部CS学科 プログラミング言語論 Part 01: プログラミング言語 小野 康一 (ONO, Kouichi) [email protected] 「プログラミング言語論」って? 「プログラミング言語」+「論」 「論」=理論/Theory 「プログラミング言語」についての理論 この場合の「理論」って何? 「プログラミング言語はどのようなモノ(概念や基盤) から成り立つのか」という話の体系 では、「プログラミング言語」って何? 2007年度 早稲田大学 CS学科 プログラミング言語論 「プログラミング言語」って? 「プログラミング」+「言語」 「言語」は何となくわかる、ような気がする 本当だろうか 「情報数学」でその基盤はやったはず オートマトン, 文脈自由文法, … 「プログラミング」って? 「プログラム」を書くこと、のはず 「プログラミング言語」=「プログラムを書くための言 語」? じゃあ、「プログラム」って? 2007年度 早稲田大学 CS学科 プログラミング言語論 「プログラム」って? とりあえず、以下のように定義してみよう: 「コンピュータに対する計算の指示」 「指示」って? 「計算」って? 「コンピュータ」って? 計算機=「計算」をする「機械」 また「計算」が出てきた… どんな性質を持つ「機械」なら「コンピュータ」なのか? 思考実験: 電卓は「コンピュータ」か? 2007年度 早稲田大学 CS学科 プログラミング言語論 電卓は「コンピュータ」か? 前提 電卓の中身に何らかのプロセッサ(CPU)が使用され ていることが多い その観点からすれば、「電卓はコンピュータ」、という ことになる(厳密には、「電卓がコンピュータでできて いる」) しかし、いま考えようとしているのは、そういうことでは なく、電卓の機能を有する機械は、コンピュータとして の要件を満たすか? ということ 言い換えると、中身ではなく、外から見た振舞や性質 が、コンピュータと呼べるものなのかどうか、というこ と 2007年度 早稲田大学 CS学科 プログラミング言語論 電卓は「コンピュータ」か? YES派の主張 電卓は「計算」をする「機械」じゃないか 電卓に数式を入力して、最後に “=” を押 すと、計算結果が出力される つまり、電卓という「コンピュータ」において、 「プログラム」は数式であり、“=”を押すこと がその実行に相当する、はずだ 2007年度 早稲田大学 CS学科 プログラミング言語論 電卓は「コンピュータ」か? NO派の主張 じゃあ、その「プログラム」をもう一度実行し たいときはどうするの? もう一度、同じ数式を入力する? 以前に入力した数式をもう一度使うことは できない? 以前の数式を少し変更したい場合は? 再入力するしかない? 2007年度 早稲田大学 CS学科 プログラミング言語論 電卓は「コンピュータ」か? 反論 YES派の反論 入力履歴を扱えるものもまれにある NO派の反論 じゃあ、入力履歴を扱えない大半の「普通の電卓」 は、「コンピュータ」ではないんだね? 2007年度 早稲田大学 CS学科 プログラミング言語論 電卓は「コンピュータ」か? 再反論 YES派の再反論 入力履歴を扱える電卓でも、過去の入力を取り出すには何 らかの指示を電卓に与える必要がある その指示を入力するのと、数式を再入力するのに、大きな 違いはないはずだ よって「普通の電卓」だってコンピュータだ NO派の再反論 「プログラム」が数式だとしたら、「データ」は何? 全部の入力が「プログラム」で、「データ」がない機械は「コ ンピュータ」じゃないはずだ あるいは逆に、入力の全部が「データ」で、「プログラム」が ない機械も「コンピュータ」じゃないはずだ 2007年度 早稲田大学 CS学科 プログラミング言語論 「コンピュータ」って? ある機械が「コンピュータ」であるためには? どんなモノを持っていればいい? どんな機能を持っていればいい? 「計算をする機械」が「コンピュータ」になるまでの歴史を 考えてみよう どこかで「コンピュータ」になったはずだ 最初の「コンピュータ」は何だ? 2007年度 早稲田大学 CS学科 プログラミング言語論 そろばん(に類するもの) 砂そろばん(BC3000∼2000頃) 古代メソポタミア文明 砂の上に線を引き、その上に石を並べて、計算に使用 線そろばん(BC500頃) 古代エジプト, 古代ギリシア, 古代ローマ 盤の上に線を引き、その上に石を並べて、計算に使用 溝そろばん(BC300∼AD400頃) 古代ローマ 盤の溝にはめ込まれた珠(石)を動かして、計算に使用 2007年度 早稲田大学 CS学科 プログラミング言語論 溝そろばん AD200頃の古代ローマの溝そろばんのレプリカ ©東京理科大学 http://www.rs.kagu.sut.ac.jp/~infoserv/museum/si/p21-2.html 2007年度 早稲田大学 CS学科 プログラミング言語論 そろばん 算盤 古代中国の「數(数)術記遺」にその原型が記載 木の枠に木製の珠を入れて動かす 後漢の徐岳の著(２世紀)/脚注者の北周の甄鸞(けんら ん)の著(6世紀)とも それ以前は、算,籌(ちゅう),策という器具を使っていた (日本では算木と呼ばれた) 日本には宋代(南宋)/室町時代に伝わったとされる 「そろばん」の語源は、「算盤」の唐音「すわんばん/そわ んぱん」という説が有力 琉球語の「スヌパン」「スルバン」が語源とする説もあり 2007年度 早稲田大学 CS学科 プログラミング言語論 そろばんは「コンピュータ」か? たぶん違う なぜだろうか 持っていたモノ/機能 計算対象の「数」の、何らかの手段による表現 珠(石)の配置 計算過程における途中の状態(数)の記憶 配置による簡単な記憶 持っていなかったモノ/機能 演算能力 加算のための珠の移動などは自分でする必要あり 演算の自動処理 桁上がりなど etc. 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機: ダ・ヴィンチの計算機 ダ・ヴィンチの歯車式計算機 スケッチのみ Leonardo di Ser Piéro da Vinci (Vinci村, イタリ ア/1452.04.15-1519.05.02) 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機: Rechenuhr (1623) Rechenuhr = Rechen(計算)+Uhr(時計) Wilhelm Schickard (ドイツ/1592-1635) Tübingen大学教授 加算・減算の他に乗算機能を有していた(除算も半機械的 に可能だったらしい) 現物は焼失し、本人を含めた家族が伝染病の腺ペストで 亡くなったため、忘れられていた Johannes Kepler宛ての書簡の中でRechenuhrにつ いて述べていた 歴史家Franz Hammerにより書簡が発見され(1935, 1956)、Rechenuhrは再現された 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機 (cont’d) Pascaline/パスカリーヌ (1642-1643) Blaise Pascal (フランス/1623.06.191662.08.19): 数学者, 哲学者 「パスカルの計算機」 加算と減算 Stepped Reckoner (1674) Gottfried Wilhelm Leibniz (ドイツ/1646.07.11716.11.14): 数学者, 哲学者 四則演算 「Leibnizの歯車」: 歯車というよりも、溝つきのドラム 2007年度 早稲田大学 CS学科 プログラミング言語論 Pascaline Pascaline © IEEE 2002 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機の系譜 Thomasの卓上計算機 (1820) Charles Xavier Thomas (フランス) Brunsviga社(ドイツ)などにより生産 Baldwinの卓上計算機 (1875) Frank Stephen Baldwin (アメリカ) Odhnerの卓上計算機 (1891) Willgodt Theophil Odhner (スウェーデン) 機械式卓上計算機として一応の完成をみる 多くのメーカにライセンス: Brunsviga社など 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機の系譜 (日本) 自動算盤 (1903) 矢頭良一 (日本) http://www.ipsj.or.jp/katsudou/museum/computer/yazu .html 日本で最初の機械式卓上計算機 独自の発想 (そろばんの機械化): 2-5進法 タイガー計算器 大本虎次郎 (日本) Brunsviga社のOdhner式卓上計算機を元に国産計算機を開 発・商品化 当初「虎印計算器」で発売したが売れず、その後「タイガー計算 器」に名称変更したら普及した 一般名詞として定着 累計販売台数(1970年頃まで) 50万台 http://www.ipsj.or.jp/katsudou/museum/computer/0010 .html 2007年度 早稲田大学 CS学科 プログラミング言語論 タイガー計算器 タイガー手廻計算機 © 株式会社タイガー http://www.tiger-inc.co.jp/temawashi/temawashi.html 2007年度 早稲田大学 CS学科 プログラミング言語論 歯車式計算機は「コンピュータ」か? 持っていたモノ/機能 計算対象の「数」の表現 歯車の角度 計算過程における状態の記憶 歯車の角度の保存 いくつかの(有限個の)基本的な演算能力 四則演算: 加算, 減算, 乗算, 除算 それらの演算の組合せで目的の計算を実現 演算にまつわる処理の機械化(自動化) 桁上がりなど 持っていなかったモノ/機能 動力 基本的に手回し式計算機 「プログラム」 他には? 2007年度 早稲田大学 CS学科 プログラミング言語論 Charles Babbage Charles Babbage, Sir (UK/1791.12.26-1871.10.18) ケンブリッジ大学ルーカス講座教授(1828∼1839年) ルーカス講座教授職にはIsaac Newton(1699年就任), Stephen William Hawking(1979年就任)など 数表(対数表など)の自動計算 数表はさまざまな用途で用いられる 航海に用いる対数表など 数表の作成は人手 (当時としては高度な知的作業だった) 計算の誤りは多かった 活字で組反して印刷する段階での誤りもよくあった だったら機械にやらせてしまえばいい 多項式の自動計算機 多項式は、何次かの階差計算で求めることができる(有限階差法) 多くの関数も、多項式で近似できる場合が多い(対数など) なお、階差計算を機械に実行させるというアイデア自体はBabbage 以前にもあったらしい 2007年度 早稲田大学 CS学科 プログラミング言語論 Difference Engine (階差機関/差分機関) Difference Engine “Computer”や“Calculator”ではなく、なぜ “Engine” ? Steam Engine (蒸気機関)からのanalogyだったと思われ る (産業革命の時代) 階差機関の動力として、蒸気機関を想定していた 1819年頃: 私財を投じて作成に着手 1823年: 英国政府の資金援助を受けて開発が本格化 1832年: 一応の試作機を作成 その後、開発は中断 完全主義者のBabbageと職人との軋轢 政府の資金援助も停止 第二階差機関の設計 (装置の簡略化、高機能化) 2007年度 早稲田大学 CS学科 プログラミング言語論 階差計算 (有限階差法) 例: f(x)=x2 となる関数f(x)の作表をしたい。 x f(x) 階差 階差 1 1 2 4 3 3 9 5 2 4 16 7 2 5 25 9 2 6 36 11 2 2次の階差(差分)を求めると定数(2)になる。 この計算を逆にすると、初期定数(2)を元に、階差の加算のみで f(x)=x2 の作表ができることになる。この場合、数列に対する階 差の加算を2回おこなえば、f(x)=x2 の作表ができる。 初期定数と階差の次数を変えれば多種の多項式が計算できる。 2007年度 早稲田大学 CS学科 プログラミング言語論 階差機関 (試作機) Difference Engine © IEEE 2002 2007年度 早稲田大学 CS学科 プログラミング言語論 階差機関は「コンピュータ」か? 持っていたモノ/機能 計算対象の「数」の表現 歯車の角度 計算過程における状態の記憶 歯車の角度の保存 階差計算の途中の数列の記憶 いくつかの(有限個の)基本的な演算能力 加算、減算: 階差計算のみ表現可能 演算にまつわる処理の機械化(自動化) 桁上がりなど 出力手段(印刷機能) 印刷も機械的におこなえば人手による誤りはなくなる 動力 蒸気機関を想定 2007年度 早稲田大学 CS学科 プログラミング言語論 階差機関は「コンピュータ」か? (cont’d) 持っていなかったモノ/機能 加減算以外の演算能力 基本的に、階差計算以外はできない 「プログラム」 他には? 2007年度 早稲田大学 CS学科 プログラミング言語論 Analytical Engine (解析機関) 階差機関: 何回かの階差計算の繰返しで、必要な作 表が達成 単独の階差計算は階差機関が自動的におこなえるが、そ れを何回か繰り返す処理は人間がおこなう必要がある その処理も機械的にできないか 以下のことが実現できれ ばいいはずだ n回目の階差計算の出力をn+1回目の階差計算の入 力に与える 階差計算の繰り返しの判断をする それらの指示および演算の手順を表現したものを解析 機関の外部から入力として与えることができれば、毎回 異なる計算ができる プログラム 2007年度 早稲田大学 CS学科 プログラミング言語論 Analytical Engine (解析機関) Analytical Engine 4つの機能ブロックから構成 入力部: データおよびプログラム 入力手段としてJacquard Loomの応用を想定 出力部 記憶部(Store) 演算部(Mill) 1833年頃にBabbageが構想 2007年度 早稲田大学 CS学科 プログラミング言語論 Jacquard Loom (ジャカール織機) Joseph Marie Jacquard (フランス/1752.07.07-1834.08.07) 1801年 パリの産業博覧会に出品 Jacquard Loom 織物の模様は、横糸をどの縦糸(経糸)の上に通すかで決定 縦糸(経糸)の上下開口の指示をパンチカードで表現 穴の有無=対応する縦糸(経糸)の上下開口の有無 縦糸(経糸)の上下開口を自動化 省力化 現在でも、Jacquard Loomで織られた織物は「ジャカール織」(また は、英語読みで「ジャカード織/ジャガード織」)と呼ぶ Analytical Engine Analytical Engineに対する処理の指示をパンチカードで与える プログラムの外部表現 2007年度 早稲田大学 CS学科 プログラミング言語論 Jacquard Loom Jacquard Loom and Punch Card, photo taken by George H. Williams 2004 at Museum of Science and Industry, Manchester, England, UK 2007年度 早稲田大学 CS学科 プログラミング言語論 Ada (エイダ) Augusta Ada (1815.12.10-1852.11.27) ロマン派詩人バイロン(George Gordon Noel Byron, Lord/1788-1824)の娘 Byron: 「ある朝、目が覚めてみると有名になっていた」 (Childe Harolde’s Pilgrimage) 母親はAnne Isabella (Annabella) Milbanke (1792-1860) Adaを出産後まもなく離婚 (1年弱の結婚生活) 1834年: William King(後にラブレイス伯爵Earl of Lovelace)と結婚しラブレイス伯爵夫人(Countess of Lovelace)となる 1833年: Babbageと出会う 2007年度 早稲田大学 CS学科 プログラミング言語論 AdaとBabbage 1833年: Babbageと出会う 母Anneは数学者William Frendに数学を教 わっていた AdaはFrendの娘婿のAugustus De Morgan （ド・モルガンの定理の発案者)に数学を教わる De Morgan夫人の紹介でBabbage宅で階差機 関の説明をBabbage本人から聞く De Morganは孤独癖があった(つまり人嫌いだった) 夫のためにDe Morgan夫人は多くの学者たちと会う 機会を設けた Babbageもそのような経緯でDe Morganと出会っ た 2007年度 早稲田大学 CS学科 プログラミング言語論 Adaと階差機関/解析機関 AdaはBabbageの階差機関/解析機関の最大の理 解者となる Babbageがイタリア・ジェノア(ジェノバ)でおこなった解析 機関に関する講演の記録(イタリア・トリノの軍事技術者 Luigi Federico Menabreaがフランス語で記述/1842 年)を、英語に翻訳し、多くの記述の誤りを訂正/補足する 注釈をつけた”Sketch of the Analytical Engine invented by Charles Babbage”を出した カード(パンチ･カード)の集まりを読み戻してもう一度実行 する方法について技術的に考察 「サブルーチン」の考え Adaは解析機関の「プログラム」をいくつも書いたことから、 「世界初のプログラマ」と一般には呼ばれる。ただし、 Babbageの考えたアルゴリズムを解析機関のプログラム としてコーディングした、というのが実際のようである 2007年度 早稲田大学 CS学科 プログラミング言語論 Adaとプログラミング言語 Adaの名はプログラミング言語の名前になっている プログラミング言語Ada アメリカ国防総省(DoD)が主に組み込みシステム向けの 言語として国際競争入札で決定 Ada83 規格番号 MIL-STD-1815 (1815はAdaの生年) Strongly Typing(強い型付け) Generic Type(総称型, 汎用型) Generic Programmingともいう Package(パッケージ) Exception Handling(例外処理) Concurrent Programming（並行プログラミング) 2007年度 早稲田大学 CS学科 プログラミング言語論 解析機関 (デモ用に製作した試作機) Analytical Engine © The Science Museum, London, England, UK 2007年度 早稲田大学 CS学科 プログラミング言語論 解析機関は「コンピュータ」か? 持っていたモノ/機能 計算対象の「数」の表現 歯車の角度 計算過程における状態の記憶 歯車の角度の保存 いくつかの(有限個の)基本的な演算能力 条件判断・繰返し 汎用性 演算にまつわる処理の機械化(自動化) 桁上がりなど 動力 蒸気機関を想定 プログラム プログラムが解析機関の動作を制御 プログラム制御方式 解析機関の外部に存在 2007年度 早稲田大学 CS学科 プログラミング言語論 解析機関は「コンピュータ」か? (cont’d) 持っていなかったモノ/機能 電気的/電子的な回路による計算機構 高速化へのbottleneck 解析機関内部におけるプログラムの記憶 他には? 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIAC ENIAC: Electronic Numerical Integrator And Calculator よく、「世界初のコンピュータ」という呼ばれ方 をする 本当なのだろうか? そもそも、何が「世界初」なのだろうか? 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIAC: 関係者 University of Pennsylvania, Moore School/ペンシルヴァニア 大学 ムーア校 John William Mauchly (1907.08.30-1980.01.08/US) 当時: Ursinus College 物理学科教授 ムーア校のチームに参加 高速な計算機があれば完璧な気象予測ができると考えられていた John Presper Eckert (1919.04.09-1995.06.05/US) 当時: 同校 大学院生 電子工学専攻, 電子工学研究室 助手 電子回路のエキスパート US Army Ballistic Research Laboratory/アメリカ陸軍 弾道研 究所 Herman Heine Goldsteine (1913.09.13-2004.06.16/US) 弾道計算表の作表のために高速かつ正確な計算機を必要としていた アナログ計算機(ex. ロックフェラー微分解析機)だと精度に難があった 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIAC: 開発プロジェクト PX Project (ENIAC開発プロジェクト) 開始: 1943年6月5日 開発費用: USD 約490,000 真空管 17,468本, ダイオード 7,200個, 抵抗器 約70,000個, キャパシタ 約10,000個 幅 24m, 高さ 2.5m, 奥行 0.9m, 総重量 30ト ン, 消費電力 150kW プログラム: ハードウェア(プログラム線)で実現 10進演算 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIAC ENIAC © U.S. Army Photo 2007年度 早稲田大学 CS学科 プログラミング言語論 真空管式計算機と実用性 1943年当時、真空管を使って実用的な汎用 計算機を作るのは無理だと考えられていた もちろん、トランジスタやICなどはまだこの時点 では存在していない したがって、真空管はこの時点では最新の電 子部品だった 当時の実用的な計算機はすべて非・真空管式 アナログ計算機 リレー式計算機 2007年度 早稲田大学 CS学科 プログラミング言語論 当時の実用的な(非・真空管式)計算機 アナログ式計算機 ロックフェラー微分解析機 (1941年12月/US) 2007年度 早稲田大学 CS学科 プログラミング言語論 当時の実用的な(非・真空管式)計算機 リレー式計算機 Bell Relay Computers (US) Model I (1940年1月) 複素数計算 Model II (1943年9月) 高射砲の照準計算 Model III (1944年6月) 弾道計算 Harvard Mark I/IBM ASCC (1944年/US) 汎用計算機 1943年時点では存在していない Enigma暗号解読機 BOMBE (1940年/UK) BOMBEは暗号解読のための機械であり、計算機とは言い がたい 2007年度 早稲田大学 CS学科 プログラミング言語論 当時の真空管式計算機 試作機レベルの真空管式計算機ならあった ABC/Atanasoff-Berry Computer (1939∼ 1942年/US) 実は、実用的な真空管式計算機はあった Colossus Lorenz SZ40/42暗号解読用 電子計算機 (1943,1944年/UK) しかし、完全な「汎用の」電子計算機ではなかった しかも軍事機密だったため、その存在は極秘にされて いた 2007年度 早稲田大学 CS学科 プログラミング言語論 真空管式計算機は実用にならない? なぜ真空管で実用的な計算機を作ることはで きないと考えられていたのか? 耐久性/信頼性に問題があった 平均寿命: 約2000時間 約18,000個の真空管を使用する計算機を稼動さ せた場合、故障の発生する頻度は? 仮定: 1個でも故障したら計算機全体が動作不能に なる 平均故障間隔(MTBF; Mean-Time Between Failure) 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIACは真空管の問題をどう解決したか? 定格電圧よりもかなり低い電圧で稼動させた もちろん真空管メーカの動作保証外 どこまで下げても動かせるかを試行錯誤 定格電圧の10%程度にまで下げたらしい 故障率: 2∼3本/週 稼働率 電源を入れたままの運用: 90% 毎晩電源を落とす運用: 50% 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIACは真空管の問題をどう解決したか? メモリを「リングカウンタ」単位で構成した 「リングカウンタ」は10進1桁の記憶ユニット ENIACの演算は10進数 10個のFlip-Flop 1個のFlip-Flopは2個の真空管から構成 20個の真空 管で1ユニット リングカウンタユニット内に故障検出回路も持つ 故障を検知したらリングカウンタユニットを丸ごと交換 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIACは「コンピュータ」か? 持っていたモノ/機能 計算対象の「数」の表現 リングカウンタによる10進数 計算過程における状態の記憶 リングカウンタのFlip-Flopの状態 いくつかの(有限個の)基本的な演算能力 条件判断・繰り返し 汎用性 演算にまつわる処理の機械化(自動化) 桁上がりなど 動力 電力 プログラム プログラム線 (ハードウェアとしてのプログラム) 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIACは「コンピュータ」か? 持っていなかったモノ/機能 内部におけるプログラムの記憶 (ソフトウェアとし てのプログラム) 他には? 2007年度 早稲田大学 CS学科 プログラミング言語論 ABC (Atanasoff-Berry Computer) 開発者 John Vincent Atanasoff (1903.10.041995.06.15/US) Iowa State University 助教授 (物理学科, 数学科) Clifford Edward Berry (1918-1963/US) 同大学院生 (学部: 電気工学/1939, 修士: 物理学 /1941, 博士: 物理学/1948) 動機: 学生たちが、物理の問題を解くための計算に時 間の大半を取られてしまい、学問の本質的なところに 時間を使うことができない 計算は機械にやらせるべ きだ 2007年度 早稲田大学 CS学科 プログラミング言語論 ABCの特徴 メモリユニット ENIACのように、メモリを真空管によるFlip-Flopで実現しようと すると、膨大な数の真空管が必要になる 高コスト 信頼性の問題 コンデンサドラム式メモリ コンデンサをドラム上に配置し、チャージした電荷でbitを表現 自然放電するので、ドラムを一定速度で回転させ、定期的に再チャー ジ(jogging) 現在のDRAMのrefresh 問題: ドラムは一定速度で定常回転しているので、読みたい位置のメ モリをアクセスするためには、最大1回転待たなければならない sequential access memory(逐次アクセスメモリ) 論理演算ユニット 演算: 2進法 2007年度 早稲田大学 CS学科 プログラミング言語論 ABCの開発 真空管: 約300本 費用: USD 約650 開発期間: 1939∼1942年 (未完成) 戦時召集によりAtanasoffたちが大学を離れ、そ の後、彼の研究室に置かれていたABCも解体され て、その存在は忘れ去られた 非・汎用計算機 ガウス消去法による連立一次方程式の解を計算す ることを目的とした 2007年度 早稲田大学 CS学科 プログラミング言語論 EnigmaとBOMBE 暗号機Enigma (エニグマ) Enigma暗号解読器BOMBE (ボンブ) 英国情報部(British Intelligence) / 英国外務省 暗号研究所 Bletchley Park (ブレッチリー・パーク) ロンドン北方約70kmにある田園地帯Bletchleyに設置さ れた暗号通信傍受・解読センター 英国中から数学者・技術者･ドイツ語研究者･暗号エキス パートを集めた Alan Mathison Turingも参加 2007年度 早稲田大学 CS学科 プログラミング言語論 暗号機Enigma (エニグマ) ドイツ語: 謎, 不可解な言葉 語源: ギリシア語 ainigma ainos (はなし) 3枚のローター(右・中央・左にそれぞれ配置) 1枚のローターは両面に26個の接点を持つ( ローマ文字と対応) 両面の各接点はローター内部で「ランダムに」接続される ローターの組み合わせは、ある文字を別の文字に変換する「転 字表」になる キーを押すたびに、右のローターが1ステップ回転する 右のローターが一回転すると、中央のローターが1ステップ回転 する 中央のローターが一回転すると、左のローターが1ステップ回転 する 左のローターが一回転すると、右のローターが1ステップ回転す る ( 263の周期) 2007年度 早稲田大学 CS学科 プログラミング言語論 Enigmaとbomba、そしてBOMBE 1920年代 商業用暗号機として販売 1933年 ナチスが政権につくと販売中止 軍用に転用 ポーランド人数学者Marian Rejewski (マーリヤーン・レ イェフスキー)によって解読 解読装置bomba（複数形bomby): ポーランド語で「爆弾」 1938年12月 ドイツ軍 Enigmaを改良 (ローターを2枚追 加) 1939年7月25日 ポーランド情報部 Enigma解読技術およ びbombaを英国/フランス情報部に開示 1940年 Enigma暗号解読機BOMBEにより解読 2007年度 早稲田大学 CS学科 プログラミング言語論 BOMBE BOMBE (ボンブ) 108個の回転ドラム Enigma 36台分の組み合わせ リレー回路でローター内部の接続の組み合わせを実現 総当りでローター内部の接続の組み合わせ(=暗号鍵)を解く 2007年度 早稲田大学 CS学科 プログラミング言語論 Colossus Lorenz SZ(Schlüsselzusatz) 40/42暗号 ヒトラー⇔SS(親衛隊)の極秘通信に使用 暗号解読機 BOMBE同様、Bletchley Parkで開発 Colossus以前 試作1号機 Peter Robinson 試作2号機 Robinson and Cleaver 試作3号機 Heath Robinson Colossus: Turingの提案で真空管式計算機として開発 (1943年開始) Colossus Mark I (1943年2月設計/1943年12月8 日完成) Colossus Mark II (1944年6月完成) 2007年度 早稲田大学 CS学科 プログラミング言語論 Colossus Mark II Colossus Mark II (1944年) 真空管: 約2400本 演算: 2進法 プログラム: ハードウェア (一部固定、一部はプロ グラム差替え可能) 暗号解読専用計算機だったが、ある程度の汎用計 算もできたらしい オーバーロード作戦(ノルマンディー上陸作戦)でも 使用されたらしい 2007年度 早稲田大学 CS学科 プログラミング言語論 ColossusとUltra Secret Winston Churchill (当時 首相)がBletchley Parkでの暗号解 読に関する情報を「私のUltra Secret (極秘情報)」と呼んだこと から、解読された情報は「ウルトラ情報」と呼ばれた Bletchley Parkでの暗号解読作業も、そこでBOMBEや Colossusが開発されていることも、すべてが極秘とされた Churchillは、BOMBEによって暗号が解読されていることをド イツ軍に知られるのを避けるために、Coventry/コヴェントリー へのドイツ空軍による爆撃の情報を事前に知りながら、それを 黙殺した、と言われている それらは、第二次大戦の終結後も1970年前半まで秘匿され続け たため、実用的な真空管式計算機であるColossusが第二次大戦 中に(ENIACに先駆けて)開発された、という事実も、それまで公に されなかった 2007年度 早稲田大学 CS学科 プログラミング言語論 EDVAC EDVAC: Electronic Discrete Variable Automatic Computer ENIACの後継プロジェクト プロジェクト開始: 1946年4月 (契約成立) 実質的には、ENIACプロジェクト進行中の1944年頃から構想・ 設計が始まっていた 関係者 ENIACプロジェクトメンバ: John William Mauchly, John Presper Echkert, Herman Heine Goldsteine John von Neumann いわゆる「フォン・ノイマン・アーキテクチャ」を採用した最初のコン ピュータになるはずだった しかし、プロジェクトは遅延することになる 2007年度 早稲田大学 CS学科 プログラミング言語論 John von Neumann 1903.12.28-1957.02.08/Budapest, Hungary 厳密に言うと誕生時点(1903年)ではオーストリア･ハンガリー二 重帝国 本名: Neumann János (ナイマン・ヤーノシュ) Neumannがsurname(姓)、Jánosがgiven name(名) マジャル(Magyar/ハンガリー人)の名前は姓-名の順に表記する。 1913年 父親Neumann Miksaがオーストリア貴族になる。 マジャル貴族は名前の前に地名をつける。父親はMargittaiを選 び(Neumann家には何の関係もない地名だが、妻の名Margit に近いので選んだと思われる)、Margittai Neumann Miksaと 名乗る。 息子のJánosにもMargittai Neumann János Lajos (マルギッタ イ・ナイマン・ヤーノシュ・ラヨシュ) あるいは、オーストリア風にした名 前のJohann Ludwig von Neumannを使わせる。 2007年度 早稲田大学 CS学科 プログラミング言語論 John von Neumann 1930年 Princeton Universityから講師として招聘 され渡米、翌年に教授に就任 1932年 “Mathematical Foundations of Quantum Mechanics” (「量子力学の数学的基 礎」) Werner Karl Heisenbergの量子理論とErwin Schrödingerの波動理論がHilbert空間において同等と 見なせることを証明 1933年 IAS/Institute for Advanced Study (いわゆる「プリンストン高等研究所」) 教授職 1936∼1938年の期間にAlan Mathison TuringがIAS にvisitorとして滞在している 2007年度 早稲田大学 CS学科 プログラミング言語論 John von Neumann 1937年 USに帰化 USでは米国風にJohn von Neumannと名乗る (ニック ネームはJohnny)。 1943年頃 マンハッタン計画(原子爆弾製造計画)に 参加 長崎型原爆(プルトニウム型原爆/Fat Man)の爆縮レンズ の設計を10ヶ月でおこなう 高速な計算機の必要性に気づく 1944年 Goldsteineと知り合い、進行中のENIAC プロジェクトにアドバイザーとして参加 後継プロジェクト (EDVAC) の構想に初期から参加 わゆる「フォン・ノイマン・アーキテクチャ」 2007年度 早稲田大学 CS学科 プログラミング言語論 い いわゆる「フォン・ノイマン･アーキテクチャ」 “von Neumann architecture” stored-program方式と同義に使われることが多いが、 厳密には区別される 例) Harvard architectureはstored-program方式の一つ だが、von Neumann architectureではない 今日のコンピュータの大部分がこのアーキテクチャ 例外: たとえば並列計算機はこのアーキテクチャの定義を満 たさない 我々が「コンピュータ」と呼ぶ場合、暗黙のうちに、あるいは無 意識に、このアーキテクチャを仮定している 2007年度 早稲田大学 CS学科 プログラミング言語論 「フォン・ノイマン･アーキテクチャ」の定義 プロセッサ(CPU)とメモリユニットの分離 バスによる結合 メモリユニットへのプログラムの格納 (stored-program) 線形メモリ メモリユニットに対する線形アドレス(番地)の割付 命令の逐次実行 プログラムカウンタ(PC)による「現在実行中の命令が置か れているアドレス」の指示 固定された(有限個の)命令セット 2007年度 早稲田大学 CS学科 プログラミング言語論 誰のアイデアなのか? 最初に思いついた人物がvon Neumannである とは言いにくい MauchlyとEckertは、ENIACプロジェクト中の 1944年に発案したと主張している 彼らはコンピュータに関する特許を取得し、会社を興そう と考えていた ( UNIVAC I) しかしながら、彼らはコンピュータの実現技術に対しての み興味があり、理論的側面に興味がなかった 2007年度 早稲田大学 CS学科 プログラミング言語論 誰のアイデアなのか? (cont’d) 数学者であるvon Neumannは理論的側面に興味があっ たので、理論的考察を論文として発表した First Draft of a Report on the EDVAC (EDVACに関する報告 第一稿) [1945年6月30日] ENIACに関係する情報は軍事技術扱いのためにほとんど公に なっておらず、この論文が注目された結果、von Neumannが このアイデアの発案者であると周囲が受け取った (そして、von Neumann自身は、その誤解を積極的に解こうとはしなかった) 軍事プロジェクトのために積極的に情報公開できなかった University of Pennsylvaniaが、名声を高めるために世界的 に著名な学者のvon Neumannに論文を書くように勧めた、と いう側面もあると思われる 2007年度 早稲田大学 CS学科 プログラミング言語論 誰のアイデアなのか? (cont’d) Konrad Zuse(ドイツ)が、1936年の特許申請で このアイデアに触れていた しかし、彼が製作した計算機(Zシリーズ)はstoredprogram方式ではなかった しかも、この申請は拒絶されて特許として成立しなかった 代替の適当な呼称がないので、括弧付きで「フォン・ノ イマン・アーキテクチャ」と呼ぶことにする 2007年度 早稲田大学 CS学科 プログラミング言語論 「フォン・ノイマン・アーキテクチャ」 命令解釈回路 論理演算回路 算術演算回路 プロセッサ (CPU) 実行制御回路 レジスタ1 レジスタ2 プログラム・カウンタ (PC) レジスタn プロセッサとメモリユニットの分離 バスによる結合 stored-program バス アドレス メインメモリ 0x010000 線形メモリ メモリユニットに対する線形アドレス(番地)の割付 命令の逐次実行 PCによる「現在実行中の命令が置かれているア ドレス」の指示 ある命令の実行が終了すると、実行制御回路 はPCの値を「その次のアドレス」に自動的に更 新する 0x010004 データ1 0x010008 データ2 0x01000c データ3 0x010010 0x010014 命令1 0x010018 命令2 0x01001c 命令3 0x100018に置かれている命令2を実行し た後、PCの値は0x10001cに更新される : : : 固定された(有限個の)命令セット 0x07fffc 2007年度 早稲田大学 CS学科 プログラミング言語論 EDVACプロジェクトの頓挫と分裂 MauchlyとEckertはEDVACプロジェクトから脱退す る ムーア校は、彼らが申請した特許の放棄を要求 von Neumannと対立の状況にあった彼らは、特許問題を 直接の動機として脱退 これに同調して、ENIACプロジェクトの頃から参加していた ムーア校のメンバの一部もEDVACプロジェクトから脱退 EDVACプロジェクトは進行不能の危機に直面 このため、EDVACプロジェクトはvon Neumannを 中心に再編されて継続したが、開発スケジュールは 遅延を余儀なくされた 2007年度 早稲田大学 CS学科 プログラミング言語論 「フォン・ノイマン・アーキテクチャ」の実現 EDVACプロジェクトが停滞する間に、von Neumannが以前に発表した論文(EDVACに関する 報告 第一稿)を読んだ多くの研究者が、「フォン・ノイ マン・アーキテクチャ」の計算機の開発に挑戦し、 EDVACよりも早く実現させることになる SSEM (The Baby) Ferranti Mark I EDSAC (ACE/Pilot ACE) Manchester Mark I MauchlyとEckertたちは会社を興し、「世界初の商 業用電子計算機」の開発に挑戦する UNIVAC I 2007年度 早稲田大学 CS学科 プログラミング言語論 ENIAC (その後) 完成: 1945年11月 すでに第二次世界大戦は終結 弾道表の作表という当初の目的には使用されず 最初に使用されたプログラム(除 テスト用プログラム) 当時開発中だった水素爆弾のための、熱核連鎖反応に関 する離散計算 図らずも、ENIACが汎用計算機であることを実証 改良 1948年: 一部stored-program方式に改良(read only) von Neumannのアイデア 1948年9月16日にデモンストレーション 2007年度 早稲田大学 CS学科 プログラミング言語論 EDSAC EDSAC: Electronic Delay Storage Automatic Computer Maurice Vincent Wilkes (1913.06.26-/UK) University of Cambridge (ケンブリッジ大学/UK) 初稼動(最初のプログラムの実行): 1949年5月6日 構成 真空管: 約3000本 消費電力: 12kW メモリ: 水銀遅延線(mercury delay line) 1024ワード(1ワード=16bit) 命令: 16個 加算、減算、乗算命令 (除算命令はなかった) 2007年度 早稲田大学 CS学科 プログラミング言語論 メモリの問題 ENIACによる、真空管を用いた電子計算機の高速性が実証 ENIAC以降の多くの計算機は真空管を使用するようになる しかし、計算機の全てを真空管で構成するには、真空管は信頼 性が低く、高価で、また、消費電力も高すぎた 特に、ENIACで真空管を大量に使っている部分はメモリだった よって、制御回路や演算回路は真空管で構成し、メモリは真空 管以外のもので構成するのが、当時としては最適だった メモリを真空管以外の何で構成するか 高速で、信頼性が高く、安価で、記憶容量が大きく、消費電力が低く、 コンパクトなもので構成したい (現代でも同様の要求) stored-program方式にすると、大きな容量のメモリが必要になる 2007年度 早稲田大学 CS学科 プログラミング言語論 各種のメモリ方式 真空管 [ENIAC] 速い。しかし、高価で信頼性も低い。消費電力も高い リレー [Konrad ZuseのZ3] 安価で信頼性が高い、が、遅い。消費電力も高いし、広いスペースも 必要 コンデンサドラム [ABC] 安価で消費電力も低い。しかし、遅い(シーケンシャルアクセス) 水銀遅延線 [EDSAC, EDVAC] 安価で消費電力も低く大容量で信頼性も高いしコンパクト。しかし、 遅い(シーケンシャルアクセス) ウイリアムズ-キルバーン管 [SSEM, Manchester Mark I] Williams-Kilburn Tube 高速(ランダムアクセス)かつ安価でコンパクト 2007年度 早稲田大学 CS学科 プログラミング言語論 伝達遅延を利用した記憶回路 情報の伝達を遅延させるモノを使うと、記憶回路を構 成できる 記憶させたい情報をそのモノに与えて、伝達に要する時間後に読 み取れば、その間、その情報を「記憶」していたことになるから 水銀遅延線 水銀中の音波は、電気信号に比べると、情報の伝達速度が遅い Eckertによる発明 2007年度 早稲田大学 CS学科 プログラミング言語論 水銀遅延線の原理 水銀を詰めた管の両端に水晶振動子(クォーツ)を付け る 電気信号を入力すると、始端の水晶振動子が振動して 水銀に音波を発生する。一定時間後に終端に音波が 到達すると、終端の水晶振動子が圧電効果で電気信 号を出力する 入力信号と同一の出力信号を一定時 間後に得られる。すなわち、記憶回路になる。 音波が終端に到達すると消えてしまう(厳密には反射が 生じる 干渉の原因になるので消す必要がある)。つま り、揮発性メモリ。よって、出力信号を増幅して始端に戻 して入力させる、いわゆるリフレッシュをする必要がある。 2007年度 早稲田大学 CS学科 プログラミング言語論 水銀遅延線によるメモリ 記憶容量 管の長さに比例 EDSACに使用された水銀遅延線は5フィート(約1.5m) 17ビット×32ワード 問題 シーケンシャルアクセス 遅い (水銀中の音速は約1,450m/sなので、EDSACのメモ リアクセス時間は約1ms) 2007年度 早稲田大学 CS学科 プログラミング言語論 EDSAC 2007年度 早稲田大学 CS学科 プログラミング言語論 SSEM(The Baby) University of Manchester Frederic (Freddie) Calland Williams (1911.06.26-1977.08.11/UK) Tom Kilburn (1921.08.11-2001.01.17/UK) SSEM: Small Scale Experimental Machine 初稼動: 1948年6月21日 (EDSACの約10ヵ月半 前) 製作目的 「フォン・ノイマン・アーキテクチャ」の計算機を作る、という目 的よりも、Williams-Kilburn tubeのアイデアがちゃんと機 能するかどうかをテストすることが目的だった 2007年度 早稲田大学 CS学科 プログラミング言語論 SSEM(The Baby)の構成 真空管式 「フォン・ノイマン・アーキテクチャ」 メモリ ウイリアムズ-キルバーン管/Williams-Kilburn tube CRTの蛍光面の前に金属の網と絶縁シートを置いて、電荷 をチャージできるようにした記憶デバイス ランダムアクセス 高速 32ワード (1ワード=32bit) 実用的な記憶容量とは いえない 2007年度 早稲田大学 CS学科 プログラミング言語論 SSEM(The Baby)とManchester Mark I 1948年10月: 英国政府はFerranti社と、SSEMの 設計にもとづく本格的な計算機の納入を契約 Manchester Mark I Intermediary Specification Version SSEMの設計を拡張 機能強化: インデックスレジ スタ, 磁気ドラムメモリ(二次記憶装置)など 完成: 1949年4月 初稼動: 1949年6月16/17日 メルセンヌ素数の計算プログラム 2007年度 早稲田大学 CS学科 プログラミング言語論 Manchester Mark IとFerranti Mark I Manchester Mark I Final Specification Version Manchester Mark I Intermediary Specification Version の設計を拡張 入出力命令など 真空管: 4,200本 Ferranti Mark I Ferranti社による製作 Manchester Mark I Final Specification Versionの設計を 拡張 乗算回路の高速化など 納入: 1951年2月 (世界で2番目の商用コンピュータ; Konrad ZuseのZ4の7ヵ月後, UNIVAC Iの2ヶ月前) 2007年度 早稲田大学 CS学科 プログラミング言語論 ACE, Pilot ACE ACE: Automatic Computing Engine 関係者 NPL/National Physical Laboratory (UK) Alan Mathison Turing (1912.06.231954.06.07/UK) 2007年度 早稲田大学 CS学科 プログラミング言語論 Alan Mathison Turing 1934∼1936年: University of Cambridge “On Computable Numbers with an application to the Entscheidungsproblem” Turing Machine 1936∼1938年: Princeton University および IAS/Institute for Advanced Study (US) von Neumannと会っている 1939∼1945年: Bletchley Park BOMBE, Colossus 1945∼1948年: NPL ACE 1948∼1951年: University of Manchester Manchester Mark I 1950年: “Computing Machinery and Intelligence” Turing Test http://loebner.net/Prizef/TuringArtichle.html 2007年度 早稲田大学 CS学科 プログラミング言語論 ACE: Automatic Computing Engine EDVACとは異なる構想でTuringが設計 1946年2月19日: NPLに提案 しかし、計画が一向に進捗しないことに失望し、 University of Cambridgeに戻ってsabbatical yearを過ごす (1947∼1948年) NPLに電子工学の研究者・技術者がいなかったた め、他の組織・プロジェクトの協力が必要だった そこで、Williams (Manchester Mark I)と Wilkes (EDSAC)と共同作業する相談をしたが、 彼らの設計方針と折り合いがつかなかった 2007年度 早稲田大学 CS学科 プログラミング言語論 Pilot ACE Turingが抜けた後、James Hardy Wilkinsonがプロジェクトを継続 ACEを製作するためのプロトタイプとして Pilot ACEを製作 初稼動: 1950年5月10日 報道機関にデモンストレーション: 1950年12月 構成 真空管: 約800本 メモリ: 水銀遅延線 128ワード (1ワード=32bit) 2007年度 早稲田大学 CS学科 プログラミング言語論 Konrad Zuse Konrad Zuse (コンラート・ツーゼ) 1910.06.22∼1995.12.18日/ドイツ Technische Hochschule BerlinCharlottenburg(現在Technische Universität Berlin/ベルリン工科大学) 土木学科 在学中、同じような計算を何度もしなければならず、 「機械による計算」ができないかと着想 卒業後、Henschel航空機製造に就職するが、1年で 退社し、両親の住宅で計算機の製作を開始 同大学 電機学科のHermut Schreier (ヘルムート・ シュライヤー)の協力を得て、計算機の製作が実現 2007年度 早稲田大学 CS学科 プログラミング言語論 Z1 (Zett erst/1936∼1938年) 当初 “V1” と呼んでいたが、ドイツ軍のミサイル兵器V1と の混同を避けて “Z1” と命名 機械式計算機 メモリ、演算ユニット、制御ユニットを金属板で構成 唯一の電気回路は、同期信号(1Hz)を出力する発振回路のみ 機械的精度が低いために信頼性が悪かった メモリ: 64words (1word=22bits) 浮動小数点 プログラム制御方式 (ただし、stored program方式ではない） ベルリン爆撃で設計図とともに破壊 1987∼1989年にZuse自身の手で再現される 2007年度 早稲田大学 CS学科 プログラミング言語論 Z2 (Zett tweit/1939年) 電機機械式計算機 (電機式計算機) メモリは機械式 (Z1の金属板式メモリを採用) 制御ユニットおよび演算ユニットをリレー回路で構成: 約 200個 16bit固定小数点 機械式計算機の信頼性の問題をリレー回路で解 決できるかどうかを検証するために製作 途中まで製作 (演算ユニットが正しく動作することを確認 し、当初の目的を果たしたため) Z1とともにベルリン爆撃で破壊 2007年度 早稲田大学 CS学科 プログラミング言語論 Z3 (Zett dritt/1939∼1941年) 電気式計算機 全部をリレー回路で構成: 約2200個 演算回路: 約600個 記憶回路: 約1600個 メモリ: 64words (1word=22bits) 浮動小数点演算 パンチカード/テープによる入出力 プログラム制御方式 (ただし、stored program方式で はない) 1941年5月12日にベルリンで公開 Z1, Z2と同様にベルリン爆撃で破壊 1960∼1961年に再現 2007年度 早稲田大学 CS学科 プログラミング言語論 Z4 (Zett viert) 電気機械式計算機 (電機式計算機) 電気式から電気機械式へ回帰 大規模な記憶容量をリレー回路で実現するには、大量のリレーが必要 Z2と同様にメモリを機械式で実現 (信頼性を高めた金属板メモリの特許を取 得していた) 演算回路はリレー回路で構成: 約2200個 メモリ: 64words (1word=32bits) [500wordsまで可能なように計画し ていた] 浮動小数点演算 パンチカード/テープによる入出力 プログラム制御方式 プロトタイプ: 1941∼1945年 爆撃を逃れてBerlinから運び出される 1950年7月11日: Eidgenössische Technische Hochschule Zürich/ETH Zürich (チューリッヒ工科大学/スイス連邦工科大学)に納 入 2007年度 早稲田大学 CS学科 プログラミング言語論 プログラミング言語 Plankalkül Plankalkül (プランカルキュール) 1942∼1945年にかけてZuseが構想 条件分岐 ループ サブプログラム 基本データ型とデータ構造 アサーション (表明) 実際にはZuseは処理系を作成せず 2007年度 早稲田大学 CS学科 プログラミング言語論 Harvard Mark I Harvard University Howard Hathaway Aiken (1900.03.09-1973.03.14/US) 製作: IBM Corporation 出荷: 1944年2月 正式納入: 1944年8月7日 名称 IBMはASCC (Automatic Sequence Controlled Calculator) と命名 Harvard UniversityとAikenはMark Iと命名 本体には”Aiken-IBM Automatic Sequence Controlled Calculator Mark I”と表示されている 2007年度 早稲田大学 CS学科 プログラミング言語論 Harvard Mark Iの計算機構 リレー式計算機 Harvard architecture データとプログラムが異なるメモリ空間に配置 異なるバスを用いてアクセス 「フォン・ノイマン・アーキテクチャ」とは厳密には異なる 「フォン・ノイマン・アーキテクチャ」は、データとプログラム を同一のメモリ空間に配置し、同一のバスを用いてアクセ スする 2007年度 早稲田大学 CS学科 プログラミング言語論 EDVAC (その後) 開発履歴 1949年8月 アメリカ陸軍 弾道研究所に納入 1951年 運用開始 開発費用 最終的に約USD 500,000 (ほぼENIACと同じ) 構成 真空管: 約6,000本 ダイオード: 約12,000個 メモリ: 水銀遅延線 1000ワード 消費電力: 56kW 設置面積: 490平方フィート (=45.5平方メートル) 重量: 17,300lb (=7,847kg) 2007年度 早稲田大学 CS学科 プログラミング言語論 MauchlyとEckert、その後 EDVACプロジェクトから脱退したMauchlyとEckert たちは、世界初の商用コンピュータを作ることを目指 して会社を設立する Electronic Control Company 1947年12月22日: 株式会社化し、EckertMauchly Computer Corporation (EMCC) 1949年9月 ノースロップ航空機会社にBINAC (Binary Automatic Computer)を納入 しかし、正しく動作せず、商用コンピュータとして失敗する 次いで、UNIVAC I (Universal Automatic Computer I)の設計を始めるが、資金難に直面 2007年度 早稲田大学 CS学科 プログラミング言語論 買収、UNIVAC I、ふたたび買収 1950年 Remington-Rand CorporationがEMCCを買収 UNIVAC開発部門としてUNIVAC Iの開発は継続 1951年3月31日 アメリカ合衆国国勢調査局にUNIVAC Iを納入 UNIVAC I 真空管: 約5,200本, ダイオード: 約10,000個, メモリ: 水銀遅延線 消費電力: 125kW 設置面積: 350平方フィート (=35.5平方メートル) 重量: 29,000lb (=13,154kg) 一台目の価格: USD 159,000 1952年 アメリカ大統領選挙の開票予想に使用、大方の予想に反 してアイゼンハワーの勝利を予想し、的中 1955年 Remington-Rand CorporationがSperry Corporationによって買収され、Sperry Rand Corporation となる (後にSperry Corporationに社名変更) 2007年度 早稲田大学 CS学科 プログラミング言語論 特許係争、Atanasoffの証言、Unisysへ 1973年 Sperry Rand Corporationが、Honeywell International Inc.を特許侵害で訴える MauchlyとEckertによるコンピュータの特許 Honeywellは、特許無効を主張 特許が主張する技術が、ENIACよりも前に存在していたことを証明 するため、ABCを作ったAtanasoffを証人として呼ぶ Atanasoffは、1941年6月に、MauchlyがAtanasoffの研究室を 訪れ、ABCについて議論したことを証言 特許申請手続きに不備があったことが判明 (技術の公開後1年以内 に特許申請する必要があったが、ENIACの公開から1年半後に申 請されていた これを理由に特許無効の判決 (よって、ABCがENIACの先行発明 であったと認定されたわけでもないし、まして、ABCが「世界初のコン ピュータ」という判決であったわけでもない) 1986年 Sperry CorporationがBurroughs Corporation によって買収され、Unisysとなる 2007年度 早稲田大学 CS学科 プログラミング言語論 EDSACとプログラミング EDSACには除算命令がなかった 除算命令をソフトウェアで実現 サブルーチンや関数ライブラリのようなもの 2007年度 早稲田大学 CS学科 プログラミング言語論 ソフトウェアによる命令の実現: 側面1 除算命令をハードウェアで実現しなくてすむので、真 空管の使用数を減らせる(除算回路は、加算・減算・ 乗算の回路全部と同程度の規模になる) 一種の RISC (Reduced Instruction Set Computer)の 思想 今日的なRISCの目的とは少し異なる。今日的なRISCは 命令セットを単純化して各命令の実行に要するクロック数を 平準化し、CPI (Clock Per Instruction)を1に近づけ、コ ンパイラによる最適化によって高速化を果たすこと「も」目 的の一つとしていた。 EDSACはそのような目的ではなく、真空管の使用数を減ら すことで、計算機全体の信頼性を向上することと、演算回 路を単純化することで計算機の開発を容易にして迅速な完 成を可能にすること、にあった。 2007年度 早稲田大学 CS学科 プログラミング言語論 ソフトウェアによる命令の実現: 側面2 ソフトウェアの再利用 汎用で品質の高いプログラム・ライブラリをどう やって作るか 必要とする命令をプログラム・ライブラリからどの ように選び、望んでいる処理を表現するためにど のように使うか 2007年度 早稲田大学 CS学科 プログラミング言語論 ソフトウェアによる命令の実現: 側面3 ソフトウェアによる命令の拡張・抽象化 プログラム・ライブラリを用いることで、コンピュータに新規の命令 を追加できる 命令の拡張 適切な命令の拡張ができると、命令セットの抽象化ができる (基本命令セットを使ってプログラムを書くと)下位の概念やその 処理を表現しなければならないが、(拡張命令セットを使うと)上 位の概念とその処理を表現するだけでよい (あくまで、うまく拡張 命令セットが定義できるならば、だが) 例: 印刷機能 基本命令セットだと「レジスタCに印刷する文字数 を与え、レジスタDに文字列データの格納開始アドレスを与え、レ ジスタBにバッファ領域の開始アドレスを与え、レジスタAに印刷 用デバイスのI/Oポート番号を与えて、A9FF00番地を呼び出 す」という手順を表現する必要があるが、拡張命令セットだと 「PRT 文字列データ格納開始アドレス」という命令だけで表現で きる 2007年度 早稲田大学 CS学科 プログラミング言語論 「計算」の抽象化 プログラミング言語は、「計算」をいかに抽象 化して表現できるか、という問題意識によって 設計される、と言ってもよい ここで言う「計算」とは、それを実行するのに用い る「計算する機械(=コンピュータ)」の動作・振舞 2007年度 早稲田大学 CS学科 プログラミング言語論 「計算」の抽象化 (cont’d) したがって、対象の「計算する機械」が「フォン・ノイマン・アーキテ クチャ」型計算機であるのなら、そのアーキテクチャが持つ制御機 構や計算機構を抽象化するように言語が設計される ということは、「フォン・ノイマン・アーキテクチャ」と異なる計算機の ためのプログラミング言語には、異なる発展がある、ということで もある それはそれで面白いテーマではあるし、実際、データフローマシ ンなどの「非・フォン・ノイマン・アーキテクチャ」型計算機のための プログラミング言語は数多く提案されている しかし、まずは基本として、「フォン・ノイマン・アーキテクチャ」型計 算機における「計算」とは何か、それを抽象化するとはどういうこ とか、を理解すべきだろう EDSACにおけるプログラム・ライブラリによる命令の拡張は、抽象 化の一つではあるが、すべてではない 「手続の抽象化」に相当する 2007年度 早稲田大学 CS学科 プログラミング言語論 次回予告 「計算」の抽象化 プログラミング言語の設計において「計算」の表現 を抽象化することがなぜ重要なのか 「フォン・ノイマン・アーキテクチャ」における「計算」 とは何なのか その抽象化とは何なのか 2007年度 早稲田大学 CS学科 プログラミング言語論