John Backusの関数型プログラミングプロジェクトの歴史 [ドラフト]

John Backusの関数型プログラミングプロジェクトの歴史 ***** ドラフト ***** Paul McJones paul@mcjones.org https://mcjones.org/dustydecks 最終更新日 2026年7月18日 要旨 John Backusは、1969年以前から始まり1991年に退職するまで続いた、アプリカティブ、関数型、および関数レベルの言語のシーケンスを探求しました。このプロジェクトの目標は、この研究から生き残った資料を保存し、文脈に入れることです。コメント、提案、および追加資料の寄付を歓迎します。 目次 謝辞 ソフトウェア危機 プロジェクトの開始 もう一人のアシスタント チューリング講演 代数の洗練 FLチーム 他者による実装 評価 参考文献 関連リソース 謝辞 1974年に私を雇用し、2004年に多くの歴史的資料を与えてくれたJohn Backus。 「DFT → FFT変換」のコピーを提供してくれたScott Baden。 彼のFPCのソースコードとGyula A. MagóのFFPマシンプロジェクトに関する情報を提供してくれたEdoardo S. Biagioni。 John Backusとの仕事に関する情報を提供してくれたDines Bjørner。 Gyula A. Magóに関する情報を提供してくれたWill Partain。 [Rosen1974a, b]を投稿する許可を与えてくれたBarry Rosen。 ソフトウェア危機 1960年代後半、「ソフトウェア危機」は頻繁な話題となりました。コンピュータは速度、メモリサイズ、価格において大幅に能力を向上させましたが、野心が増大するにつれて、多くのプログラミングプロジェクトがコストとスケジュールの超過、および信頼性の低さに悩まされました。 1968年と1969年の2回のNATO後援によるソフトウェア工学会議は、問題に注目を集め、正式な手法、設計方法論、および管理技術を含む解決策を議論するための初期のフォーラムとなりました。 John Backusはこれらの会議のどちらにも出席しませんでしたが、それらはプログラミングタスクを単純化したいという彼の長年の願望に共鳴しました。彼はSpeedcodingとFORTRANプロジェクトで初期の成功を収めていました。特にFORTRANは、数値指向プログラムの作成タスクに革命をもたらし、多くの場合、科学者やエンジニアが、Backusが時折「聖職者」と呼んでいたプロのプログラマーによって書かれたプログラムに匹敵するか、それを超えるパフォーマンスのプログラムを書くことを可能にしました。 FORTRANの後、彼はAlgolプロジェクトに参加し、1963年にはIBMフェローに任命され、任意の問題を選択して取り組む柔軟性を得ました。その後、彼は四色問題（現在の定理）に数年間取り組みました。しかし、1967年から1969年頃、Backusはプログラミング問題に再び取り組むことを決意しました：「私はFortranよりも難しくない、本当に高水準なプログラミングの何かを考えていました。問題は、関数型プログラミングのアイデア、「組み合わせ形式」などがかなり簡単に思いついたことでした。しかし、それを、その言語では表現できない他のすべての問題を扱える実際の完全なシステムにすることになると、非常に混乱して厄介になりました。」[Booch2007] プロジェクトの開始 数年間、Backusはこの新しいアイデアにほとんど一人で取り組みました。Ted Coddが短期間コンサルティングしましたが、それは長続きしませんでした[Booch2007]。 1969年後半、Dines Bjørnerが彼と協力し始めました。まず、ラムダ計算とCurryの組み合わせ論理の詳細を説明し、次にBackusの言語（当時はRedSysと呼ばれていました）の「有限状態ツリー変換子」セマンティックに基づいたインタープリター（PL/Iで書かれた）を作成しました[Bjørner2025, 1972]。Bjørnerは1972年までBackusと協力していましたが、その後別々の道を歩みました。BjørnerはTed Coddと協力することになりました[Bjørner2025]、[BjørnerEtAl1973]。 Backusの最初の出版物は、1972年の研究報告書「Reduction languages and variable-free programming」でした。この報告書は、この論文の演算子の一部をテストするために使用されたRedアイテムを削減するプログラムを書いてくれたBjørnerに感謝の意を表しています。[Backus1972a] この報告書は、単純な書き換えルールによってセマンティックが与えられる一連の式指向言語を導入しました。 特徴的な言語であるRedは、Pure Lisp[McCarthy1960]と同程度のサイズでしたが、プログラマーは、形式パラメータに対する効果を記述することによって関数を定義するのではなく、関数の合成演算子と一連の組み合わせ形式（ここでは「モディファイア」として知られる）を使用して、ベース関数のセットから関数を構築しました。 各関数は1つの（暗黙の）引数を取り、それはシーケンスである可能性がありました。これは、APLの「ワンライナー」にいくぶん似たプログラミングスタイルにつながり、Backusは後にAPLをインスピレーションとして引用しました。 1972年中、Phil Summers（当時おそらくイェール大学の大学院生インターン、後にIBMの研究者）は、LispでRedの実験的な実装を行いました[Summers1972]。この最初の報告書は、Redに関する主張としてはかなり穏やかなもので、彼はそれを実用的なプログラミング言語というよりは形式システムとして位置づけていました。 1973年、彼は最初のACM Principles of Programming Languages会議で発表された論文でこれをフォローアップしました[Backus1973a, c]。それは言語の階層を洗練させ、中心として整理されたRedのバージョンを提示し、次のように結論付けました：「この作業が、厳密な数学的処理に必要な単純さを持つ新しいクラスのプログラミング言語のセマンティック理論につながることを願っています。」 1973年中、Backusは講演ツアーに出て、全国の大学や研究機関で14回の講演を行いました[Backus1973d]。IBMフェローとしての彼の年次報告書は、その年の言語フレームワークとRed言語に関する作業を説明し、2つの主張をしました[Backus1974a]：「単純で、全体的なプログラミング言語は、従来の複雑な、単語ごとのプログラミング言語とは対照的に、プログラミングのコストを劇的に削減する可能性を秘めています。従来のプログラミング言語の概念をクリーンアップして拡張する現在の取り組みには、そのような可能性はありません。実際、それらは過去15年間のように言語に複雑さを加え続け、それによってプログラミングのコストと実践に必要な専門知識を実際に増加させるでしょう。（したがって、PL/IはFortranよりも10倍複雑で、実行効率が悪く、表現力は20〜30％しか向上していません。）」 彼は次のように結論付けました。「上記の2つの主張に真実があるとすれば、リサーチ部門は、プログラミング言語に関して快適だが誤った伝統に陥っているかどうかを自問すべきです。私は、コンピュータサイエンスとプログラミングにおけるその重点と目標を再評価すべきだと信じています。少なくともIBMのコンピュータ科学者は、プログラミングのコストを削減することが、おそらく他のどの技術的成果よりもIBMの成長に貢献することに気づくべきです。」 これらの主張を裏付けるために、彼は「フォン・ノイマン・ボトルネック」という言葉、つまり従来のコンピュータの単語ごとの性質を導入し、これが従来のプログラミング言語の設計にも引き継がれ、その非効率性と複雑さにつながっていると主張しました。 IBMワトソンリサーチセンターの自動プログラミンググループのマネージャーであるPatricia GoldbergがBackusに応答する番でした[Goldberg1974]。彼女は、プログラミングコスト削減の重要性、PL/Iジャンルの言語を超える必要性、APLの重要性、さまざまな分野での集計演算の発見の重要性に同意しました。しかし、彼女は次のように述べました。「しかし、明示的なストアと代入演算子の概念を完全に放棄すべきだとは確信していません。」彼女は、IBMにおける非フォン・ノイマンフレームワークに関する進行中の作業と、それらを有用なプログラミングシステムに統合する試みに言及しました。 Backusは、IBMリサーチが非常に単純なフレームワークをサポートする言語フレームワークの研究を行う必要性を力強く再確認して応答しました[Backus1974b]。 もう一人のアシスタント リサーチマネジメントからの反応は lukewarm でしたが、Backusは persevered しました。彼の1973年の年次報告書の「1974年の計画」セクションで、Backusは次のように述べていました。「時間と支援があれば、私は作業を開始することを望んでいます。