エイダ・ラブレスのプログラムは実際に何をしたのか（2018）
(twobithistory.org)- 1843年、Ada Lovelace はまだ完成していなかった Analytical Engine を対象に Bernoulli 数を計算する手順を公開し、このため「最初のコンピュータープログラム」をめぐる論争の中心に立つことになった
- 公開された表は Bernoulli 数列全体を扱う方法のうちの一段階を示しており、Lovelace が B7 と呼んだ値は現代の表記では 8 番目の Bernoulli 数に当たる
- Note G のプログラムは 25 個の演算、入れ子のループ、変数の値の追跡表記まで含み、Menabrea の 11 演算で反復のない例よりはるかに精巧だった
- C への翻訳過程で、原文の表の 4 番目の演算
v5 / v4はv4 / v5であるべきことが判明し、これは組版ミスの可能性があるが、コンピューティング史上もっとも古いバグと見なせる - Lovelace の違いは「最初のプログラマー」という呼称よりも、カード作成を単なる代数式の翻訳ではなく、うまくも下手にもなりうる プログラミング作業 と理解していた点にある
実行されなかった1843年のプログラム
- Microsoft の創業逸話とは異なり、Ada Lovelace のプログラムは実機で実行される機会を得られなかった
- Paul Allen と Bill Gates は Altair がない状態で Intel 8080 仕様に基づくエミュレータ上で BASIC インタプリタを試験し、実際の Altair でも動作させた
- Lovelace も説明しか存在しないコンピューターを対象にプログラムを書いたが、Analytical Engine が作られなかったため実行できなかった
- Lovelace のプログラムはしばしば世界初のコンピュータープログラムと呼ばれるが、その地位には議論が残る
- Lovelace の貢献の範囲と価値をめぐる論争は、Walter Isaacson が “minor academic specialty” と呼ぶほど続いている
- ここで重要なのは人物評価より、1843 年に書かれたプログラムが どのように動作するよう設計されていたか である
- プログラムは単なる数式の列挙を超えている
- 反復可能な演算グループを構成し、ループ に相当する構造を使っている
- 変数状態の変化を追跡する表記法を導入している
- 今日のソフトウェア作成の経験と似た部分がある
Bernoulli 数と冪和の問題
- Lovelace のプログラムは Bernoulli 数 を計算するよう設計されている
- Bernoulli 数の背景には、古くからある数学の問題である冪和の計算がある
- ピタゴラス学派は
1 + 2 + 3 + ... + nを逐一足し合わせずに求める方法を探し、2 つの三角形を長方形に組み合わせる考え方からn(n+1)/2の公式を得た - Archimedes は
1² + 2² + 3² + ... + n²の形の和に関心を持ち、幾何学的に解釈できる解法を残した - Aryabhata は 499 年に三乗和の公式を含む Aryabhatiya を発表した
- ピタゴラス学派は
- より一般的な問題は
1^k + 2^k + ... + n^kの形の和をどう求めるかだった- Johann Faulhaber は 1631 年に 17 乗までの公式を計算して発表したが、一般解は示さなかった
- Blaise Pascal は 1665 年に一般的方法を作ったが、それにはまずそれより低いすべての冪和の求め方を知っている必要があった
- Jakob Bernoulli はより実用的な一般解を残した
- Pascal の三角形を用いて多項式係数のパターンを見抜いた
- 係数の一部は Pascal の三角形から、残りは係数の総和が常に 1 になる性質から導いた
- この 2 番目の係数因子が Bernoulli 数 として知られる数列になった
- Bernoulli の発見によって、任意の冪和の計算がただちに容易になったわけではない
k乗和を計算するにはk番目までの Bernoulli 数を知る必要がある- 各 Bernoulli 数は、それ以前の Bernoulli 数をもとに計算される
- それでも、各冪和の公式を順に導出するより、長い Bernoulli 数列を計算するほうがはるかに簡単だった
Babbage の2つの計算機
- Charles Babbage は 2 種類の機械式計算機を設計した
- 1 つ目は Difference Engine
- 2 つ目は、今日では機械式コンピューターとして知られる Analytical Engine
- Difference Engine はコンピューターではなく、加算と減算だけを行う機械だった
- Babbage は当時の対数表に誤りが多いことに不満を持ち、対数表を機械的に作成しようとした
- Gaspard de Prony の 有限差分法 は、対数表作成の過程を加減算だけで済む小さな段階に分解した
- 多項式は対数関数や三角関数の近似に使える
- Difference Engine は、差分表の各列を物理的な歯車の列に対応させた
- 各歯車は 10 進数 1 桁を表し、列全体で 1 つの 10 進数を表した
- 8 列を持ち、7 次多項式までを表にできた
- 人は初期値を設定した後、クランクを回して定数差分が次の列へ伝播するようにした
- Babbage は Difference Engine の一部を製作して実演したが、全体の機械を完成させることはできなかった
- 必要な数の歯車を十分な精度で作れる製作者を見つけられなかった
- 動作する Difference Engine が作られたのは、精密加工が可能になった 1990 年代になってからだった
- Analytical Engine は、はるかに強力で柔軟な機械として構想された
- Difference Engine と同様の歯車列を使うが、数百列以上を備える予定だった
- Jacquard Loom のように パンチカード でプログラムできる
- 加算・減算だけでなく乗算と除算も実行できる
- “mill” と呼ばれる部分が演算に応じて再配置され、記憶用の列から被演算子を読み出して結果を別の列に書き込む
Menabrea 論文と Lovelace の注釈
- Babbage は Turin で、イタリア人技術者で後に首相となる Luigi Menabrea と出会い、Menabrea は 1842 年に Analytical Engine の可能性を説明するフランス語論文を発表した
- Lovelace は 1843 年に Menabrea の論文を英語へ翻訳した
- Lovelace は 1833 年、17 歳のときに初めて Babbage と会い、彼の Difference Engine に魅了された
- 幼少期から数学教育を多く受け、結婚して 3 人の子どもを産んだ後も Augustus de Morgan に数学を学んだ
- Menabrea の論文は Difference Engine の動作方式と Analytical Engine の優位性を簡潔に扱っている
- Analytical Engine は 20 桁の数 2 つの積を 3 分 以内に求められる機械として紹介される
- 連立一次方程式の簡単な系と 2 つの二項式の積の展開を例に、“diagrams of development” を用いて説明している
- これらの表も Lovelace のプログラムと同じ意味ではプログラムだが、分岐や反復のない単純な例だった
- Lovelace の翻訳には原文より長い注釈が付され、そこに主要な貢献が表れている
- Note A は、Analytical Engine が任意の数学演算を実行できる機械である可能性を詳しく論じる
- 数だけでなく、相互の基本関係が演算の抽象科学として表現できる対象にも作用しうると見ていた
- たとえば、いつか音楽を作曲できるかもしれないと述べている
- Note G が有名なのは 2 つの理由による
- Analytical Engine が「考える」と言うことはできないという Lovelace の論点を、Alan Turing は後に “Lady Lovelace’s Objection” と呼んだ
- 同時に、機械が非常に複雑な問題を扱えることを示すために Bernoulli 数計算プログラムを含んでいた
Note G プログラムの実際の構造
- Lovelace の全体の表は拡張された “diagram of development” 形式で、原画像は こちら で見られる
- プログラムは、一般的な数学記号で指定された 演算リスト に近い
- Babbage や Lovelace は、Analytical Engine 用の opcode 集合のようなものを作る段階までは進んでいなかったようだ
- Lovelace は Bernoulli 数列全体をある限界まで計算する方法を説明したが、表として示したプログラムはそのうちの一段階の例である
- 計算対象は Lovelace が B7 と呼んだ値
- 現代数学の表記では 8 番目の Bernoulli 数である
- 式は
B7 = -1(A0 + B1A1 + B3A3 + B5A5)の形になる
- この式の各項は、特定の冪和多項式の係数を表している
- 対応する冪は 8 であり、8 番目の Bernoulli 数が初めて現れるのは正の整数の 8 乗和の公式である
B1からB7は Lovelace のインデックス付けによる異なる Bernoulli 数であるA0からA5は、Bernoulli が Pascal の三角形で計算できた係数因子である- Lovelace のプログラムでは
n = 4を使う
- C 言語への翻訳版は gist として提供されている
- まず
A0とB1A1を計算する - その後、2 回繰り返されるループに入り、
B3A3とB5A5を計算する - 各積を計算した後、それまでの積に加えていき、最後に全体の和を得る
- まず
ループ、変数状態、古いバグ
- C への翻訳は Lovelace のプログラムの先見性をよく示している
- 原文プログラムに厳密な
whileループがあったわけではないが、Lovelace は演算グループを作り、注釈でいつ反復すべきかを指定していた - C への翻訳には 2 つの
whileループがあり、その 1 つはもう 1 つの内側に入れ子になっている - 原文と C 翻訳の
v10は、反復ごとに減少する カウンタ変数 のように振る舞う
- 原文プログラムに厳密な
- Lovelace の表は Menabrea の表より状態変化を追いやすい
- “Indication of change in the value on any Variable” という列がある
- 各変数に上付きインデックスを付け、プログラム実行中にその変数が保持した連続する値を表している
- 上付きの 2 は、プログラム開始後にその変数へ 2 回目に代入された値を意味する
- C に移して実行すると、最初は誤った結果が出たが、原因は翻訳コードではなく原文の表にあった
- Lovelace の “diagram of development” は 4 番目の演算を
v5 / v4と記している - 正しい順序は
v4 / v5である - これは Lovelace が作ったプログラムの誤りではなく、組版ミス だった可能性が高い
- Lovelace の “diagram of development” は 4 番目の演算を
- Jim Randall も Lovelace のプログラムを Python に翻訳 し、同じ除算バグと別の 2 つの問題を指摘している
- 原文プログラムの些細なバグは、Lovelace が単なるデモンストレーションではなく、実際のプログラムにかなり近いものを書こうとしていたという解釈につながる
最初のプログラマーという呼称の境界
- Lovelace が「最初のプログラム」を書いた、あるいは発表したと言うのは完全には正確ではない
- Menabrea は Lovelace の翻訳より 1 年早く “diagrams of development” を発表していた
- Babbage も公開しなかったプログラムを 20 本以上書いていた
- 何をプログラムと見なすかによって議論の余地がある
- Lovelace の公開プログラムは、それ以前に公開されたものよりはるかに進んでいた
- Menabrea が示した最長のプログラムは 11 演算だった
- Menabrea の例にはループも分岐もなかった
- Lovelace のプログラムは 25 個の演算 と入れ子のループ、したがって分岐構造を含んでいた
- Menabrea は、機械が完成すれば困難はカード作成へと縮小し、カードは代数式の翻訳にすぎないので、簡単な表記法で作業者に実行を任せやすいと見ていた
- Babbage と Menabrea は、Analytical Engine を主として自分たちが関心を持つ数学計算の問題へ適用することに集中していた
- Lovelace は、Analytical Engine は Babbage や Menabrea が想像した以上に多くのことができると考え、「カード作成」が単なる付随作業ではなく、うまくも下手にもなりうる プログラミング作業 であることを理解していた
1件のコメント
Hacker Newsのコメント
自明ではないプログラムの本当の証は、最初の試行では動かないことだ。
Babbageが単純なエンジンを作るための精密な大量加工技術がまだ存在せず挫折した後、桁違いに複雑な新システムを設計し、さらに進んだ製造能力を求めてイタリアまで行ったという点が驚き。
何かをやろうとして行き詰まると、まず自分の道具を作り始めたし、あるときは非常に小さいポイントサイズで内蔵フォントが気に入らないと言って、自分のフォントを自作した。
私の知る限り最高のエンジニアだったが、ウサギ穴にはまらないよう常に見張っている必要があった。
Tim Robinsonも「1920年代のMeccanoが100年前に存在していたら、Babbageは完全に成功していただろう」と述べており、彼は現実的に可能な水準を先取りしすぎたアイデアのためにハードウェアに放り込まれたソフトウェアの人に近かったのだと思う。
事業・プロジェクト計画の感覚が乏しく、スコープを縮小したり10桁精度を諦めたりできなかったことに加え、より良いアイデアを次々に思いついて追いかけ、ウサギ穴にはまっていった。若い頃にDifference Engineの提案だけでいくつもの賞を受けたため、数十年後になっても諦めにくかったのだろう。
さらに、政府と関わったことも悲劇の大きな軸だった。貴族は政府・政治を見下して不信感を抱き、下層階級は政府にあまり助けられた経験がなく不信感を持っていたが、Babbageは愛国的な政府観を抱くのにちょうどよい中産階級だったため、自分の発明を「国家」に捧げ、政府が報いるべきだと考えたようだ。
彼はDifference Engineを完成できなかったが、より優れたAnalytical Engineなら追加資金で実現できるとして政府に尋ね、政府は20年にわたって優柔不断に振る舞った。政府が発明品を返すと言っても、彼は拒否した。
数々の賞の影響なのか、自分が「賢い人間」であるというアイデンティティにも固執していたようで、Faradayと一緒に賞の審査をするよう提案されたときも、自分が単独の審査員であるべきだとして断ったという逸話がある。こうした態度も、実用的な実行よりも空想的な天才型のアイデアへ流れさせた可能性が高い。
Sydney PaduaのThe Thrilling Adventures of Lovelace and Babbageは非常によく調査された本のようで、本文はあまり読めていないが、付録は詳しく読んでおり、おすすめできる。
本当に素晴らしい記事だ。導入部で、Lovelaceが演算を反復可能なグループとして組織する方法を深く考え、ループを発明し、変数が変わるときに状態を追跡することの重要性に気づいて、その変化を示す記法を作ったという点が印象的だった。
プログラマーの立場から見ると、Lovelaceがしていたことが今日のソフトウェアを書く体験にどれほど似ているかに驚かされるし、Bernoulli数を計算するために設計したという説明も、彼女が何をしたのか理解するのに十分な詳しさだった。
もし今生きていたら、廊下の向こうでRustを使って何かの問題に取り組み格闘していそうだし、静的型付け言語を強く好んだような気がする。
Analytical Engineが数だけでなく、抽象的な演算科学の関係として表現できる他の対象にも作用でき、例えば和声や作曲の基本的な関係がそのように表現されるなら、どんな複雑さや長さの精巧な音楽でも作れると見抜いた点が核心だ。
実際のプログラム可能なコンピュータが登場する1世紀前の1842年に、機械式コンピュータの原型についての説明だけでこうした考えに至ったのは、すごいハックだ。
https://en.wikipedia.org/wiki/Static_single-assignment_form#Benefits
今日でも最新の手法に近いのに、彼女は180年前にすでにそれを持っていたことになる。
Paul AllenとBill Gatesが、Altair用のBASICインタプリタを実物のAltairなしで、Harvardのコンピュータ上でIntel 8080の仕様だけを見て作ったエミュレータでテストし、実際のAltairの前で初めて実行したときに正しく動作したというくだりが興味深い。
だとすれば、ここで本当に隠れた英雄なのは、仕様だけを見て作ったエミュレータで動いたソフトウェアが実ハードウェアでも問題なく動くほど正確な仕様を書いたIntelのエンジニアたちではないかと思う。
プロッタ用の8080ファームウェアを書いていた別のプログラマーがコードをデバッグできるようにするための作業で、そのエミュレータのソースはIntelのINTERP/8 8008というものに由来していたと記憶している。オンラインの記事を見ると、AllenとGatesもそれを使っていたようだ。
一番素晴らしい部分は、彼女が翻訳に付けた「notes」に含まれている実際の作業だと思う。
参考: https://upload.wikimedia.org/wikipedia/commons/c/cf/Diagram_for_the_computation_of_Bernoulli_numbers.jpg
そして https://en.wikipedia.org/wiki/Note_G
記事では、彼女の作業をPythonに移植したこの資料も参照している: https://enigmaticcode.wordpress.com/tag/bernoulli-numbers/
Lovelace のプログラムを C に移植したものが、役に立たない名前の変数だらけという点を除けばそれほど見慣れないものではない、というくだりを見ると、著者は間違いなく私の同僚たちに会ったことがないのだと思う
私は特に保守的というわけではなかったが、彼は当然ながら “butts” が何のための変数だったのかを毎回覚えておらず、自分のコードのせいでなぜ混乱し続けるのかも最後まで理解していなかった
化学工学者だった父は FORTRAN でプログラミングを学んだのだが、当時は変数名が 1 文字と最大 2 桁の数字でなければならなかった。後に Basic を学んだものの、コードはいまだに精神的には FORTRAN のままだったので、その習慣が残っていた
最初は父だけがそうなのだと思っていたが、ずっと後に Wall St で働き、Numerical Recipes のコードをコピーして使うクオンツたちと作業してみると、C でもまったく同じ様子だった
Menabrea が Analytical Engine を主に「長く乾いた計算」を自動化し、優れた科学者たちの知的能力をより高度な思考に使えるようにする道具だと見ていた点を見ると、自動化をめぐる言説がいかに長続きするものかが面白い
今でも LLM についてまったく同じことを言っている
Babbage の命令セットで仮想マシンを作り、Ada のプログラムを動かしてみた人がいるのか気になる
ただし Ada のプログラムは例として入っていないようなので、自分で入力する必要がありそうだ
面白いことに、私のコンパイラ授業のプロジェクトは、このエミュレータをターゲットにする C コンパイラを作ることだった: https://github.com/Christopher-Chianelli/ccpa コードはひどいので注意
https://github.com/MarquisdeGeek/Ada-Origins
https://pairdebuggingwithlovelace.hashnode.dev/
この記事が投稿された当時にも議論されたことがある
What Did Ada Lovelace’s Program Actually Do? - https://news.ycombinator.com/item?id=17797003 - 2018年8月、コメント 52 件
当時のコメント 35 件の議論はこちら: https://news.ycombinator.com/item?id=10709730
少し脇道にそれるが、当時の人々が彼女を何と呼んでいたのか気になった
名前は Augusta Ada King で Lovelace 伯爵夫人だったが、当時も爵位を短くして姓のように呼ぶことが一般的だったのか、それとも最近になってそう呼ばれるようになったのか気になる
William King-Noel が Earl of Lovelace になった後は “Lovelace” と呼ばれ、彼女は社交界では “Lady Lovelace”、公式な文脈では “Countess of Lovelace” と呼ばれていたはずだ
良い記事だ。Ada がどのような意味で革新的であり、なぜ評価に値するのかについて、これまで読んだ中で最も明確な説明だった