HN 日本語サマリー

← 一覧へ戻る
科学・技術

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

History of John Backus's functional programming project [draft] (softwarepreservation.computerhistory.org)

30 pointsby cwbuilds2 コメント

要約

この記事は、John Backusが1969年以前から1991年の退職まで取り組んだ、関数型プログラミング言語プロジェクトの歴史を記録したドラフトです。ソフトウェア危機への対応として、Backusはよりシンプルで高水準なプログラミング言語の探求を開始しました。初期のRed言語からFPプロジェクトに至るまでの開発経緯、その思想、そしてIBMリサーチにおける受容や影響について詳述しています。

全文翻訳

ジョン・バッカスによる関数型プログラミングプロジェクトの歴史

[画像: Computer History MuseumのSoftware Preservation Group]

Paul McJones
paul@mcjones.org
https://mcjones.org/dustydecks

最終更新日: 2026年10月7日

要旨

ジョン・バッカスは、1969年頃から引退する1991年まで、一連の適用型、関数型、および関数レベルの言語を探求しました。このウェブサイトの目的は、この研究から入手可能な資料をアーカイブし、文脈に入れることです。コメント、提案、および追加資料の寄贈を歓迎します。

このページを引用する方法: Paul McJones. History of John Backus's functional programming project. Webサイト、Computer History Museum、Software Preservation Group. 最終訪問日 dd mmm yyyy. https://softwarepreservation.computerhistory.org/FP/

目次

謝辞

  • 1974年に私を雇用し、2004年に数々の歴史的な資料をくれたジョン・バッカス(アーカイブと参考文献の「From [[Backus2004]]」として注記)。
  • 図書館資料を提供してくれた米国議会図書館(アーカイブと参考文献の「From [[Backus2003]] #n」として注記)。
  • 図書館資料の調査写真を撮影してくれたEthan Ableman。
  • Baden1983bのコピーを提供してくれたScott Baden。
  • 彼のFPCのソースコードと、Gyula A. MagóのFFP Machineプロジェクトに関する情報を提供してくれたEdoardo S. Biagioni。
  • ジョン・バッカスとの仕事に関する情報を提供してくれたDines Bjørner。
  • Gyula A. Magóに関する情報を提供してくれたWill Partain。
  • Rosen1974aおよびbの掲載許可を与えてくれたBarry Rosen。
  • 思い出、写真、多くの資料を提供してくれたJohn Williams(アーカイブと参考文献の「from [[Williams2026]]」として注記)。
  • 思い出と資料掲載の許可を与えてくれたAlex Aiken。
  • Winkelmann2007、Winkelmann2009、Winkelmann201xのソースコードを提供してくれたFelix Winkelmann。
  • Hemmendinger1985を提供してくれたDavid Hemmendinger。
  • Bjørner1972の入手を助けてくれたPeter Capek。

挑戦の探求

1960年代後半までに、コンピュータははるかに安価、高速、そして大規模になりましたが、野心が大きくなるにつれて、多くのプログラミングプロジェクトがコストとスケジュールの超過、信頼性の低下に苦しみました。1968年と1969年のNATOソフトウェア工学会議は、これらの問題に注目を集め、形式手法、設計方法論、管理技術を含む解決策の議論の初期フォーラムとなりました。

ジョン・バッカスはこれらの会議にはどちらも出席しませんでしたが、プログラミングのタスクを簡素化したいという彼の長年の願望に響きました。彼はSpeedcodingとFORTRANプロジェクトで初期の成功を収めました。特にFORTRANは、数値指向プログラムの作成タスクに革命をもたらし、多くの場合、科学者やエンジニアが、バッカスがしばしば「聖職者」と呼んだプロのプログラマーによって書かれたプログラムに匹敵するかそれを超えるパフォーマンスのプログラムを書くことを可能にしました。FORTRANの後、彼はAlgolプロジェクトに参加し、1963年にはIBMフェローに任命され、自分が何をしたいかを選択できる柔軟性を得ました。その後、彼は数年間四色問題(現在は定理)に取り組みました。しかし、1969年頃、バッカスはプログラミング問題に再び取り組むことを決意しました。

「私は、Fortranほど難しくない、本当にハイレベルなプログラミングの何かを考えていました。問題は、関数型プログラミングのアイデア、「結合形式」のようなものがかなり簡単に思いついたことでした。しかし、それを、その言語では表現できない他のすべての問題を扱える実際の完全なシステムにしようとすると、非常に混乱し、厄介になりました。」 [Booch2007]

プロジェクトの開始

当初、バッカスはこの新しいアイデアに一人で取り組みました。Ted Coddは彼と短時間相談しましたが、長続きしませんでした [Booch2007]
。1969年後半、Dines Bjørnerが彼と協力し始めました。まずラムダ計算とカリーのコンビネータ論理の詳細を説明し、次にバッカスが当時RedSysと呼んでいた言語に基づいた、有限状態ツリー変換セマンティクスによるインタープリタ(PL/Iで記述)を作成しました [Bjørner1972], 2025
。

バッカスによる最初の出版物は、1972年の研究報告書「Reduction languages and variable-free programming」でした。この報告書は、Bjørnerが「この論文の一部の演算子をテストするために使用されたRedアイテムを削減するプログラムを作成した」ことに対して謝辞を述べています [Backus1972a]
。この報告書は、単純な書き換え規則によってセマンティクスが与えられる、式指向言語のファミリを導入しました。中心的な言語であるRedは、Pure Lisp [McCarthy1960]
と同程度の規模でしたが、プログラマーは関数の効果を形式パラメータで記述するのではなく、関数合成演算子と、結合形式(ここでは「モディファイア」と呼ばれる)のセットを使用して、基本関数から関数を構築しました。各関数は1つの(暗黙の)引数を取り、それはシーケンスである可能性がありました。これは、APLの「ワンライナー」を彷彿とさせるプログラミングスタイルにつながり、バッカスは後にAPLをインスピレーションとして引用しました。1972年中、Phil Summers(当時おそらくイェール大学のインターンで、後にIBMの研究者)は、LispでRedの実験的実装を行いました [Summers1972]
。

この最初の報告書は、Redに関する主張はかなり控えめなものでした。バッカスはRedを実用的なプログラミング言語というよりは形式システムとして位置づけていました。1973年、彼は最初のACMプログラミング言語原理会議で発表された論文でこれをフォローアップしました [Backus1973a], c
。この論文は言語の階層を洗練させ、中心として整理されたRedのバージョンを提示し、「希望としては、この作業が新しいクラスのプログラミング言語のセマンティック理論につながるだろう。その言語は、厳密な数学的処理に必要な単純さの公理的基盤を持つだろう」と結論づけています。

1973年中、バッカスは講演ツアーに出て、国内の大学や研究機関で14回の講演を行いました [Backus1973d]
。IBMフェローとしての彼の年次報告書は、その年の言語フレームワークとRed言語に関する作業を説明し、次に2つの主張をしました [Backus1974a]
:

  1. 「従来の複雑な、一度に1ワードのプログラミング言語とは対照的に、単純な、全体エンティティのプログラミング言語は、プログラミングコストを劇的に削減する可能性を秘めている。」
  2. 「現在の従来のプログラミング言語の概念を整理・拡張する努力には、そのような可能性はない。…実際、それらは過去15年間と同様に、ワード単位の問題に対処せずに言語に複雑さを加え続け、それによってプログラミングのコストと必要な専門知識を実際には増加させるだろう。(したがって、PL/IはFortranよりも10倍複雑で、実行効率が悪く、表現力はわずか20〜30%しか向上しないだろう。)」

彼は、「上記の2つの主張に何らかの真実があるならば、リサーチはプログラミング言語に関して快適だが誤った定説に陥っていないかどうか自問すべきである。私は、コンピュータサイエンスとプログラミングにおけるその重点と目標を再評価すべきだと信じている。少なくともIBMのコンピュータ科学者は、プログラミングコストの削減が、おそらく他のどの技術的成果よりもIBMの成長に貢献することを知っておくべきだ。」と結論づけました。これらの主張を裏付けるために、彼は、従来のコンピュータのワード単位の性質である、現在では有名な「フォン・ノイマン・ボトルネック」という言葉の、おそらく最初の書面での使用を導入し、これが従来のプログラミング言語の設計にも引き継がれ、その非効率性と複雑さにつながったと主張しました。

IBMのWatson Research Centerの自動プログラミンググループのマネージャーであるPatricia Goldbergが、バッカスに応答する責任を負いました [Goldberg1974]
。彼女は、プログラミングコスト削減の重要性、PL/Iジャンルの言語を超える必要性、APLの重要性、さまざまな分野での集約操作を発見することの重要性に同意しました。しかし彼女は、「しかし、明示的なストアと代入演算子の概念を完全に廃止すべきだとは確信していません。」と述べました。彼女は、非フォン・ノイマン型フレームワークに関するIBMでの進行中の作業と、それらを有用なプログラミングシステムに統合する試みに言及しました。バッカスは、IBMリサーチが非常に単純なフレームワークを定義することを目標に言語フレームワークを研究する必要があるという主張を、力強く繰り返して応答しました [Backus1974b]
。

私の関与

リサーチマネジメントからの反応は鈍かったものの、バッカスは persevered しました。1973年の年次報告書の「1974年の計画」セクションで、バッカスは「時間と支援が許せば、Red言語の最適化インタープリタの開発に着手したい」と述べていました。彼は一緒に働く人を募集したいと考えていることを知らせ、当時IBMサンノゼリサーチにいたJim Grayが、私が常勤の雇用を探していることを知って、私をバッカスに紹介しました。私は1972年にUCバークレーでの彼の講演の1つに出席し、彼のメーリングリストに登録していたため、彼の2つの研究報告書を受け取り、少なくとも部分的に消化していました。私はSnobol4とAPLのインタープリタで作業したことがあり、Landin、Reynolds、Evansによる関数型プログラミングの研究にも精通していました。その後約15ヶ月間、私はバッカスと共に言語を洗練させ、Lispと、W. H. Burge [Burge1968]
によって設計されたISWIMライクな言語であるMcg [McJones1975a]
でいくつかの実験的インタープリタを作成することを含む、実装アイデアを探求しました。私は参加 shortly 後に部門で短い講演を行い [McJones1974b]
、閉じた適用型言語における共鳴に関する技術報告書を作成しました [McJones1975b]
。この間、バッカスと私は、Red言語のマイナーなバリエーションのシリーズを探求しました — [Backus1974c]
から [Backus1975b]
を参照してください。プログラムの代数(最初に [Backus1974a]
で言及)と状態変換のモデリングに関する作業も始まりました。言語がまだ流動的であり、重点が実際の実際の実装よりも形式手法にあると感じたため、私はSystem Rリレーショナルデータベースプロジェクトに移りました。その後、Xeroxのオフィスシステムに移り、Poplar(遅延評価関数型言語)とMesa [McJones1978], 1980
でRedのトイ実装を作成しました。ずっと後に、私はオリジナルのFortranコンパイラを見つける探求でバッカスに連絡を取りました [McJones2007]
。

[画像: Alex Stepanov、John Backus、Paul McJones、Zazzie's、2004年]

Alex Stepanov、John Backus、Paul McJones、Zazzie's、2004年。

この期間中、大学の数人の研究者がバッカスのアイデアに基づいたプロジェクトを開始しました。Klaus Berklingは、[Backus1973c]
の影響を受けた削減ベースのマシンに関する設計作業をドイツのGMDで開始しました。これは実際に実装された最初の削減マシンであると言われています [Berkling1975], Kluge1983
。ノースカロライナ大学のGyula A. MagóはFFPMプロジェクトを開始しました [Magó1976]
。Partain1989は、これらおよびその他のグラフ削減マシンについて説明しています。

チューリング賞

講演

ジョン・バッカスは、「実用的な高水準プログラミングシステムの設計への深遠で影響力のある永続的な貢献、特にFORTRANに関する彼の業績、およびプログラミング言語の仕様のための形式的手順の先駆的な出版」により、1977年のACMチューリング賞を受賞しました。彼の受賞講演「Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs」は、すべてのACM会員に配布されたCommunications of the CACMに掲載されました [Backus1978]
。彼は次のように主張しました。

「従来のプログラミング言語はますます巨大化していますが、強くはなっていません。最も基本的なレベルでの固有の欠陥により、それらは太くて弱いものになっています。すなわち、共通の祖先であるフォン・ノイマン・コンピュータから受け継いだ、ワード単位のプログラミングスタイル、セマンティクスと状態遷移の密接な結合、プログラミングを式の世界とステートメントの世界に分割すること、既存のプログラムから新しいプログラムを構築するための強力な結合形式を効果的に使用できないこと、そしてプログラムについて推論するための有用な数学的特性の欠如。」

彼が提案した代替案は、「非形式的」関数型言語FP(関連する「形式的」バージョンFFP)と、関数型プログラムの代数、そして履歴依存システムをモデル化するための適用型状態遷移(AST)のフレームワークでした。FPは、数値、原子、シーケンスを操作するためのプリミティブ関数のセットと、より複雑な関数を単純な関数から構築するための結合形式のセットを含んでいました。行列乗算の関数例を以下に示します。

Def MM ≡ (ααIP) ○ (αdistl) ○ distr ○ [1st, trans ○ 2nd]

○は関数合成を表し、αは関数をシーケンスの各要素に適用し、[...,...]は関数のリストを値に適用して結果のシーケンスを生成します。MMは、互換性のある2つの行列をペアとして期待します。各行列は行のシーケンスとして表されます。右から左に読むと、括弧内の関数は2番目の行列を転置し、最初の行列はそのままにします。distrは、転置された2番目の行列のコピーを最初の行列の各行とペアにします。αdistlは、そのような各ペアにdistlを適用し、行ペアのシーケンスのシーケンスを生成します。ααIPは、そのような各ペアにIP(内積)を適用し、目的の行列積を生成します。

関数のみが言及されており、それらが適用されるデータ項目(変数または定数)は言及されていません。(データ値から定数値関数を作成するための結合形式がありました。)これは後にポイントフリースタイルとして知られるようになりました。バッカスは、これがFPの強力さと単純さに大きく貢献したと感じていました。

バッカスが指摘した従来の言語の問題の1つは、その複雑さと、それらを仕様化し、それらに関するプロパティを証明することの難しさでした。対照的に、バッカスはFPのためのプログラムの代数を提示しました。これは、プログラムの等価性を示すため、例えばプログラムをより効率的な形式に変換する際に使用できます。代数は、結合形式のプロパティに由来する恒等式に基づいています。例えば:

[f1, ..., fN] ○ g ≡ [f1 ○ g, ... fN ○ g]

αf ○ [g1, ..., gN] ≡ [f ○ g1, ..., f ○ gN]

/f ○ [g1, g2, ... gN-1, gN] ≡ f ○ [g1, f ○ [g2, ... f ○ [gN-1, gN]...]]

/はペア上の関数を取り、APLの還元演算子のようなシーケンス上の関数を生成します。

より複雑な変換のためのこれらの法則に基づく定理もありました。例えば、自己参照定義を(無限の)条件文に変換するためのものです。論文は何ページにもわたって、これらの定理のいくつかを説明し、証明しました。例として、行列乗算と階乗の再帰的および非再帰的なバージョンの等価性を示しました。

最後に、バッカスは適用型状態遷移システムを提示しました。このシステムでは、システムは、ユーザー定義関数またはデータ項目を含む名前付きセルのセットからなる状態を持ちます。ユーザーは一連の入力を送信し、各入力はシステム関数によって検査され、適切なハンドラにディスパッチされ、計算を実行してから、(出力、新しい状態)のペアを生成します。システム関数は新しい状態の妥当性チェックを行い、それをインストールして出力をユーザーに送信します。論文では、空の状態からのブートストラップを含む、このシステムを詳細に説明し、システムを拡張するさまざまな方法を提案しています。

反応

チューリング賞の威信と挑発的なタイトルを考えると、この論文は広く読まれ、議論されました。Dana Scott [Scott1978]
とRobin Milner [Milner1978]
からの個人的な手紙は、プログラムの証明をワーキングプログラマーにもたらすというバッカスの努力を称賛しましたが、FPとFFPに関するいくつかの技術的な問題点を指摘し、[Scott1976]
で提示されたような拡張型λ計算に基づくように彼を奨励しました。(Scottはまた、「私へのいくつかの親切な言及に感謝します。もちろん、あなたが「フォン・ノイマン」という名前を一般的な意味で使用するのと同じように、あなたも「スコット」を使用しています。私のチューリング講演 [Scott1977]
と、他の貢献者が言及されているSIAM論文 [Scott1976]
への言及を含めることを提案したでしょう。」と付け加えました。)

Edsger Dijkstraがバッカスの講演を彼の個人的なEWDシリーズの692番としてレビューしたときに、より活発なやり取りが始まりました。このシリーズは、Dijkstraの約12人の友人に直接配布されましたが、バッカスを含むより広い聴衆にも間接的に広まりました。彼の結論は比較的穏やかなものでした [Dijkstra1978b]
:

「要するに、この記事は正当な研究努力の進捗報告ですが、説得力のある結果が得られるずっと前に、その重要性を攻撃的に過大評価しているという大きな欠点があります。これは、チューリング賞講演という形で発表されたため、さらに残念です。」

しかし、彼の完全なレビューは非常に否定的であり、バッカスとDijkstraの間で手紙の交換を引き起こしました [Chen2016]
。その中でDijkstraは、彼のレビューが、バッカスのDijkstra、Hoareらによって開発されていた公理的セマンティクスへの攻撃だと感じたことに対抗するための「政治パンフレット」であったと宣言しました。

2026年8月までに、ACMのデジタルライブラリは[Backus1978]
の引用が2000件を超えたと記録しており、さらに追加されています。大部分は「フォン・ノイマン・アーキテクチャ」の参照として論文を引用しているようですが、特に最初の10年間では、バッカスのアイデアをさまざまな方法で適用または拡張しようとする真剣な試みを示す数十件の論文がありました。

代数と提唱

代数

私が1975年にSystem Rプロジェクトに移って以来、バッカスは一人で作業していました。1978年7月、John Hayden Williamsが彼に加わりました。Williamsはウィスコンシン大学マディソン校でBounded Context Parsable Grammarsというタイトルの論文で博士号を取得しました。彼はコーネル大学の教員となり、そこでプログラミング言語に関する研究を行いました。二人は1977年のデータフローおよび削減言語に関するワークショップ [Gostelow1977]
に出席し、バッカスはWilliamsを[Backus1973a]
および[Backus1978]
の謝辞で言及しました。おそらくIBMへの参加のアイデアは、バッカスがコーネル大学で講演を行った1977年12月に話し合われ、Williamsが詩 [Williams1977]
で彼を紹介しました。Williamsが到着した夏、彼はドイツのマルクトオーバードルフで開催された年次NATOサマースクールの講師の一人でした。Dijkstraは[Dijkstra1978a]
で次のように報告しました。

「最終日の最後の講演 — 削減言語について — は、参加者の一人であるJohn H. Williams(コーネル大学からIBMサンノゼへ移籍中?)によって行われました。それは、力強く行われた、素晴らしい講演でした。参加者がサマースクールで最も優れた人々であったことを考えると、これ以上適切な締めくくりの講演を望むことはできませんでした。」

[画像: ホワイトボードのJohn BackusとJohn Williams] [画像: スペイン、ペニスコラ、1981年、John BackusとJohn Williams]

John BackusとJohn Williams: IBMにて、そしてスペインにて。John Williams提供。

バッカスとWilliamsは、プログラムの代数をさらに開発するために取り組みました。初期の論文 [Backus1979]
, [Backus1981a]
および[Williams1982]
を通じて、関数、形式、極限、線形性、そして興味深いクラスの再帰関数定義を反復形式で再記述することを可能にした線形展開定理の代数の基礎が現れました。Hが「述語変換子」Htを持つ線形形式である場合、次の式の最小解は次のようになります。

f = p → q; Hf

次のようになります。

f = p → q; ...; Htnp → Hnq; ...

これにより明示的な定義が可能になります。

[Backus1981a]
は、François-Henri Raymondが独立して、そしてバッカスの知らないうちに、かなり類似した関数代数を以前に開発した1975年の論文 [Raymond1975]
に言及しました。

多くの人々が、この変数なしの関数レベルスタイルを習得するのが難しいと感じました。[Backus1979]
は2つの問題点を指摘しました。「命名」(多くの数量を追跡する必要がある場合に変数が役立つ)と「忘却」(値を計算し、データベースの更新バージョンを提供するという両方の計算が、計算を通じてデータベースをスレッドする必要がある)です。[Backus1981a]
は、名前付き形式関数変数を持つ「拡張定義」を導入しました。例えば:

xdef f ○ [x, [y, z]] = [[x, y], [x, z]]

これは次のように置き換えます。

def f = [[1, 1 ○ 2], [1, 2 ○ 2]]

この論文は、S. W. Smoliar(未発表)との共同作業が、同様の関数変数を条件式で使用される述語に拡張することを示唆していると述べています。後のFL言語は、そのパターン機能に同様のアイデアを含んでいました。

[Backus1985a]
は「Fortran構文」を導入し、MMを通常の3つのネストしたループのコードを簡単に生成できる形式に代数的に変換することを示しています。

MM' = [ [ + ○ [ * ○ [k ○ i ○ l, j ○ k ○ 2]
k=˜1, len ○ 2]
j=˜1, len ○ 1 ○ 2]
i=˜1, len ○ 1]

(元のコードにあった余分な右括弧は削除されています。)

提唱

[Dijkstra1978b]
は、チューリング講演を「説得力のある結果が得られるずっと前に、その重要性を攻撃的に過大評価している」と評しました。Dijkstraは、特にチューリング賞講演という名声にもかかわらず、これを「残念」だと感じました。しかし、バッカスは1980年代半ばまで、関数レベルプログラミングの強力な提唱と「フォン・ノイマン言語」への批判を続けました。彼と彼のグループが実際のプログラミング言語の設計と実装に没頭するにつれて、彼の議論は和らぐだけでした。

彼のチューリング講演は、従来の言語についていくつかの主張をしました。

  1. それらは機能性を得るために、より大きく、より複雑になっていた。これは、(PascalやCのような新しい言語を無視して)成長が線形以上であることを意味していました。
  2. ほとんどはワード単位であり、「全体エンティティ」ではなかった(APLを軽視し、SETLやSQLのような新しい言語を無視していた)。
  3. それらのセマンティクスは状態遷移に基づいていた。
  4. それらは式とステートメントの世界に分割されていた。
  5. それらは「結合形式」を欠いていた(APLを軽視し、Unixパイプラインや出現しつつあった適用型技術を無視していた)。
  6. それらはプログラムについて推論するための有用な数学的特性を欠いていた(公理的および指示的セマンティクスの作業を却下していた)。

[Backus1979]
は、上記のポイント3を拡張しました。彼の取り組みは形式セマンティクスに焦点を当てていました。代入と副作用のある命令型言語では、ステートメント(または副作用のある式)の意味は、ストア(メモリ状態)をストアにマッピングする関数としてモデル化されますが、関数型プログラムは値を値にマッピングします。彼は、4つの主要な結合形式(定数、合成、条件、構築)を使用した関数型プログラムは、これらの結合形式を相互に関連付けるプログラムの代数の存在により、はるかに強力であると結論づけました。彼は、Lと呼ばれるフォン・ノイマン言語を、Lと呼ばれる関数型言語に埋め込むことを実証しました。Lのセマンティック関数をLプログラムとしてモデル化しましたが、結果の関数はプログラムの代数を適用するにはあまりにも扱いにくいことを指摘しました。

[Backus1981a]
はラムダススタイル(例: LISP [McCarthy1960]
とLandinのISWIM [Landin1964]
)を取り上げました。「一般に、FPスタイルは、プログラム構造、真理、および変換を、現在ラムダスyleプログラムについて推論するために利用可能なものよりも高いレベルの一般性で認識し、推論できるフレームワークを提供すると提案します。」彼は、ラムダ抽象を使用すると、すべてのFPプログラム形成操作と「無限の他のもの」を定義できることを認めましたが、この力は無規律な使用につながると主張し、次のように結論づけました。「したがって、新しい世代の関数型言語、関数レベルの構造と関数レベルの推論を強調する言語の設計を開始する時期かもしれません。」後に、彼のFLは、ラムダ式を使用して高階関数を定義することを可能にしました。

いくつかの講演で、彼はフォン・ノイマンプログラムの「ストレージプラン」の柔軟性のなさに言及しました。2つのプログラムを合成するには、互換性のあるストレージプランが必要であり、最初のプログラムの出力が2番目のプログラムの入力と同じアドレスにある必要があります。これは、FORTRAN IIでさえ存在していたサブルーチンメカニズムの存在を無視しているように見えました。

この提唱は、業界誌 [Backus1982b]
、IBM内部 [Backus1985b]
および外部 [Backus1983]
での講演、および前述のより専門的な会議で行われました。

実装

WilliamsとBackusは比較的早い段階から実装の問題を考え始めました。[GuttagEtAl1981]
は「FPの現在の実装では、各プリミティブが引数xが正しい形式であることをチェックする必要があるため、大量の冗長なチェックが実行されます。」と述べています。その実装はPL/Iで書かれ、「FPオブジェクトのさまざまなストレージスキームを試すための手段を提供するため、非常にモジュール化されています(そして非常に非効率的です)。」Williamsはまた、FPのLisp「上」での実装を行いました。FPプリミティブ関数と結合形式の定義をLisp関数として実装しました。[BruceWilliams1982]

1983年までに、代数の基盤はかなりしっかりしており、いくつかのプログラム変換作業に適用されていました。代数をさらに検証するために、より大きなプログラムの本体が必要でした。これは、十分に表現力のあるバージョンの言語を設計し、そのセマンティクスを注意深く仕様化し、それを実装することを示唆していました。おそらくこの理由から、バッカスのチームはさらに拡大しました。1983年9月、Edward L. Wimmersが参加しました。彼は前年にウィスコンシン大学マディソン校で数理論理学の博士号を取得していました。

FP84

1984年から、WilliamsとWimmersは、FPのような言語の書き換え規則の健全性と完全性に関する調査で、IBMの研究者Joseph Halpernと協力しました。彼らはFPを一般化することから始めました。これは[WilliamsWimmers1988]
で説明されています。

「非形式的には、FP84は、無限シーケンス、プログラマー定義の結合形式、および遅延評価を含めるために[Backus1978]
のFP言語を変更した結果です。さらに、[Backus1978]
の形式言語FFPとは異なり、FP84はオブジェクトと関数の間に明確な区別を設けます。つまり、オブジェクトのシーケンスはもはや関数を表すために使用されません。これらの拡張は、FP84ではシーケンス構築が⊥でないオブジェクトにのみ適用されるというFPの制限を削除することによって達成されます。FP84では、式全体(意味が⊥であるものを含む)がシーケンス構築の下で閉じられています。」

[画像: Tim Winkler、John Williams、John Backus]

Tim Winkler、John Williams、John Backus、1984年。John Williams提供。

理論的な作業は、[HalpernEtAl1990]
と[HalpernWimmers1995]
で最高潮に達しました。

FL86

遅延評価と無限シーケンスを備えたFP84は、入出力と大規模(例: ファイルシステム)の状態変化をモデル化できました。

[画像: ファイルシステムに接続されたIFRプログラムの合成(HughesEtAl1987より)]

[HughesEtAl1987]
より

有用な作業(例: 編集、コンパイル)を行う関数を作成し、ストリーム接続をスレッドすることは煩雑であり、IFR(インタラクティブ、ファイル参照)プログラムを合成するための新しい結合形式が必要になります。そこで、以前のFPと同様の厳密な言語と暗黙の履歴コンポーネントを使用する別の方法を採用することが決定されました。

[画像: IFRプログラミングのためのFL厳密履歴アプローチを示す図(HughesEtAl1987より)]

[HughesEtAl1987]
より

これも、副作用を管理可能にするために言語の評価順序を慎重に仕様化する必要がありましたが、分析により、かなり使いやすい代数が残ることが示されました。この言語はFLと呼ばれる最初の言語でしたが、ここでは後のバージョンと区別するためにFL86と呼びます [BackusEtAl1986], 1990
。

FL86のコアは[Backus1978]
のFPに似ており、エラー値?と、プログラマー定義のデータ型を実装するために使用されるタグ付き値([GuttagEtAl1981]
の影響を受けていました)が追加されていました。このコア言語は高階でした。結合形式は関数子であり、FPの馴染みのあるプリミティブ結合形式に加えて、新しい高階関数を定義できました。コア言語は、指示的セマンティクスと操作的セマンティクスの両方(書き換え規則)によって定義され、それらは健全で完全であることが証明されました。言語には、「where」句による静的スコープのローカル関数定義、カプセル化された型定義([GuttagEtAl1981]
の影響を受けていました)、パターンマッチング、および新しい高レベル関数を定義しやすくするさまざまな表記法(カリー化、リフティング、インフィックス表記法など)を含む、追加の便利な機能が実装されていました。1987年にアンティーブで行われた講演は、型のためのスキームを示しています [BackusEtAl1987]
。

グラスゴー大学のJohn HughesとMary Sheeran [Sheeran1983], 1984
は、1987年の夏に訪問しました。Hughesは、関数レベルの書き換え規則の厳密な高階評価に関する問題の検討を支援しました。結果は、Year Of Programming Conference at U.T. Austin [HughesEtAl1987]
での講演で発表されました。WilliamsとHughesは、IFIPワーキンググループ2.8 関数型プログラミング
を共同設立しました。

FL

1988年に2人の新しいリサーチスタッフがグループに参加しました。2月にはPeter Lucasが参加しました。彼は1961年からIBMウィーン研究所、ヨークタウン、サンノゼ/アルマデンのIBMリサーチで働いていました。8月にはAlexander S. Aikenが参加しました。彼はコーネル大学で博士号を取得しました。Brian Murphyは1987年と1988年に参加したMITのコープ学生でした。Paul Tuckerは1990年初頭にIBMメンロパーク研究所から参加しました。

Backus、Williams、Wimmers、Aiken、LucasはFL言語を再設計し、詳細な新しい言語マニュアル [BackusEtAl1989b]
を作成しました。FLはFL86よりもシンプルで強力であり、いくつかの重要な新機能がありました [BackusEtAl1990]
:

  • 例外処理、signalとcatch(関数子)付き。
  • 新しい結合形式(高階関数)の便利な定義のためのラムダ式。
  • 環境操作: uses、where、union、およびrec(namelist)。

1988年のレビューおよび計画文書によると、VM/370上のIBM LISPで動作するブートストラップコンパイラがあり、FLをLISPにコンパイルできました。これはその後VM/370システムでコンパイルして実行でき、言語を試すために使用でき、またプロトタイプおよび最適化コンパイラがFLで書かれると予想されていたため、ブートストラップにも使用できました。[Backus1988a], b
。Backusの1990年12月の年次フェロー報告書は次のように発表しました [Backus1990]
:

「FLで書かれるプログラムが増えるにつれて、この言語はさまざまなタスクに対して強力で便利であることがわかっています。言語全体が現在のコンパイラに実装されています。私たちが開発している最適化技術が、例で現在行われているように、全体的にうまく機能するようになれば、これまでのFLプログラミング経験は、FL言語が非常に高レベルの「高速プロトタイピング」言語として機能できることを示しています(強力な型チェックによってその精度と堅牢性が向上します)。そして同時に、コンパイラから直接高速な、プロダクションレベルのオブジェクトコードが得られます。したがって、FLは、現在プロトタイピングに使用されている言語よりも強力で拡張性の高い言語を提供しながら、Cで「高速プロトタイププログラム」を再コーディングする必要性を排除するはずです。」

報告書は、コンパイラの多くのコンポーネントの進捗状況を説明しました。

Backusは1991年に引退し [Backus1991]
、プロジェクトは約3年後に終了しました。

[画像: Ed Wimmers、Alex Aiken、John Backus、John Williams]

Ed Wimmers、Alex Aiken、John Backus、John Williams。John Williams提供。

[画像: ネクタイをしたJohn Backus]

John Backus(ネクタイ着用!)、妻のBarbara Stannard、John Williams、1999年11月。
John Williams提供。

[画像: John WilliamsとJohn Backus、2003年]

John WilliamsとJohn Backus、2003年。John Williams提供。

[画像: John WilliamsとJohn Backus、2003年]

John WilliamsとPaul McJones、2026年。Raquel McJones提供。

他者による実装
  • Scott BadenのBerkeley FPは、Franz Lispで書かれたインタープリタです。 [BadenPatel1983]
    , [Baden1983a]–c
    を参照してください。
  • John HughesのmuFPは、Mary Steeranのストリーム指向FP方言のためのLispKit Lispで書かれたインタープリタです。 [Sheeran1983], 1984
    および[HendersonEtAl1983]
    を参照してください。
  • Arch RobisonのIllinois FPは、Cで書かれたインタープリタです。 [Robison1987a]–e
    を参照してください。
  • Edoardo S. BiagioniのFPCはCで書かれており、FPをCに翻訳し、それをCコンパイラでコンパイルします。 [Biagioni1988]
    を参照してください。
  • Andy ValenciaのStanford FPは、Cで書かれたインタープリタです。 [Valencia1986]
    を参照してください。
  • Sean O'RourkeのLanguage:FPは、Perlで書かれたインタープリタです。 [O'Rourke2002]
    を参照してください。
  • Christophe Deleuzeのoc-FPは、OCamlで書かれたインタープリタです。 [Deleuze2003]
    を参照してください。
  • Felix L. Winkelmann、CHICKEN Schemeの作者は、3つの実装を設計しました。
    • fpはChicken Schemeで書かれています。FPをSchemeに翻訳し、FPとSchemeコードの相互運用を可能にします。 [Winkelmann2007]
      を参照してください。
    • Furry Paws: 「John BackusのFP言語の方言のための最適化全体プログラムコンパイラとランタイムシステム。コンパイラはFPで書かれており、完全に自己コンパイルします。FPコードはCに翻訳され、その後バイナリ実行可能ファイルにコンパイルできます。」 [Winkelmann2009]
      を参照してください。
    • muFPはSheeranのmuFP [Sheeran1983], 1984
      からVerilogへのコンパイラです。CHICKEN Schemeで書かれています。 [Winkelmann201x]
      を参照してください。
  • Juan Facorroのfpは、Lispで書かれたインタープリタです。 [Facorro2011]
    を参照してください。
  • Kwang Yul Seoのfpは、Haskellで書かれたインタープリタです。 [Seo2016]
    を参照してください。
  • Alessandro Di Giorgioのfparは、C++17に埋め込まれたDSL(ドメイン固有言語)としてのFPのデータ並列実装です。 [DiGiorgio2019]
    を参照してください。
  • Benjamín Bucciantiのfpは、Clojureで書かれたインタラクティブなFP実装です。 [Buccianti2020]
    を参照してください。Webベースのデモはこちら: https://fp.buccianti.dev

評価

Backusのチューリング講演 [Backus1978]
は、当時のコンピュータアーキテクチャとプログラミング言語に対する論争であり、適用型、関数レベルの言語とプログラムの代数を支持するものでした。彼は「フォン・ノイマン・ボトルネック」がパフォーマンスを制限し、プログラミング言語の設計を制約する傾向があると感じていました。従来のプログラミング言語に対する彼の反対意見には、次のものが含まれます。

  1. それらは、新しい種類の問題に適応するにつれて、サイズと複雑さが増加した。
  2. それらは「ワード単位」であり、「全体エンティティ」ではなかった。
  3. それらのセマンティクスは、還元(書き換え)ではなく、状態遷移に基づいていた。
  4. それらは式とステートメントの世界に分割されていた。
  5. それらは、より小さなプログラムをより大きなプログラムに直接結合する方法を欠いていた。
  6. それらは、プログラムについて推論するための有用な数学的特性を欠いていた。

Backusは絶対的な言葉で話しましたが、おそらくそれが彼をすでに進行中のトレンドから盲目にしていました。

彼が予測したハードウェアの停滞の代わりに、ムーアの法則は集積回路のトランジスタ密度を6桁増加させ、コンピュータアーキテクトは、キャッシュ
, パイプライン
, マルチプルイシュー
, SIMD
、そしてGPU
やTPU
のような特殊プロセッサを含む、パフォーマンス向上技術の長いリストを発明しました。

言語設計者はすでに「全体エンティティ」プログラミングを実験していました。例えば、APLの配列操作、SETL
のセット操作、SQLのリレーション操作などです。

Unix
のパイプ
は、別々に書かれたプログラムを接続して新しいプログラムを構築することをすでに可能にしており、ラムダスタイルの関数型言語は、コンビネータを含むさまざまなスタイルでの実験を可能にしていました。ラムダ計算のパイオニアであるJ. Barkley Rosserは後に、「Backus(1978)はこの活動の主流にはいないようだが、彼は非常に新しいコンビネータ関数を持っており、彼の作品から興味深いものが進化する可能性がある。」と述べています [Rosser1984]
。

他の人々は、モジュール、インターフェース
, 抽象データ型、およびオブジェクトなどの抽象化技術を実験しており、これらはプログラマーが各アプリケーション領域の個別の拡張機能で言語コアを拡張することを可能にするでしょう。

パーソナルコンピュータはオフィスや家庭に普及し、若い人々はプログラミングに惹かれ、あらゆる種類のソフトウェアが繁栄しました。

操作的、指示的、公理的セマンティクスに関する作業は、遅いが着実な進歩を遂げました。プログラマーは、事前条件と事後条件、ループ不変条件、終了証明に慣れました。証明およびモデルチェッカーが開発されました。LLM支援プログラミングのこの時代において、そのような形式手法は「幻覚」を回避するための鍵となる可能性があります。

関数レベルプログラミングは、多くのプログラマーにとって習得が難しいことが判明しました。拡張定義、述語、パターンマッチングのFL技術は役立ちましたが、高階関数の定義を容易にするために、最終的にラムダ束縛がFLに追加されました。いわゆるポイントフリープログラミングは、Haskell
のような言語でサポートされているスタイルですが、必須ではなくオプションです。

Backusと同僚は、代数に関して限定的な進歩しか遂げませんでした。FLのクリーンな操作的セマンティクスは、最適化に役立つ書き換えベースの変換をサポートしましたが、そのような最適化の複雑さを排除するまでには至りませんでした。Richard BirdとLambert Meertensが並行して、仕様から等式推論を使用してプログラムを導出する広範な作業を行ったことは興味深い [BirdEtAl2021]
。 [KapurEtAl1981]
が指摘したように、「…演算子は、演算子の動作が依存する代数構造に関連付けられるべきです。」(この思考の流れは最終的にC++ Standard Template Library [Stepanov2007]
につながりました。)

Backusの提唱は、一般的に関数型プログラミングの研究を普及させるのに役立ちました。そして今では、関数スタイルはほとんどの現代のプログラミング言語に浸透しています。効果(ミュータブルなストレージと非同期I/O)の処理は、関数レベルであろうと値レベルであろうと、すべての適用型フレームワークにとって依然として課題です。

アーカイブと参考文献

パート1: バッカスと同僚によるもの

[Aiken1988]

Alex Aiken. Optimization Strategies for FL. 1988年10月5日. [Backus2004]
より. PDF

[AikenEtAl1989]

Alexander Aiken, Edward L. Wimmers, and John H. Williams. 1989. Program transformation in the presence of errors. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '90). Association for Computing Machinery, New York, pages 210–217. https://doi.org/10.1145/96709.96730

[AikenEtAl1990]

Alexander Aiken, John H. Williams, and Edward L. Wimmers. The Program Feature in FL. IBM Almaden Research Center, 1990年10月16日. [Backus2004]
より. PDF

[Aiken1991]

AA [Alex Aiken]. Another Stab at Monads. 1991年4月29日. [Backus2004]
より. PDF

[AikenEtAl1991]

Alex Aiken, Brennan Gaunce, Brian Murphy. Implementing FL in C. 1991年6月22日. [Backus2004]
より. PDF

[AikenMurphy1991a]

Alexander Aiken and Brian R. Murphy. Implementing Regular Tree Expressions. In Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture. Springer-Verlag, Berlin, Heidelberg, 427–447. https://theory.stanford.edu/~aiken/publications/papers/fpca91.pdf

[AikenMurphy1991b]

Alexander Aiken and Brian R. Murphy. Static type inference in a dynamically typed language. In Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '91). Association for Computing Machinery, New York, NY, USA, 279–290. https://doi.org/10.1145/99583.99621

[AikenWimmers1992a]

[Alexander Aiken and Edward L. Wimmers. Solving systems of set constraints. In Symposium on Logic in Computer Science, June 1992, pages 329-340. (Extended Abstract) https://theory.stanford.edu/~aiken/publications/papers/lics92.pdf

[AikenWimmers1993]

Alexander Aiken and Edward L. Wimmers. Type inclusion constraints and type inference. In Proceedings of the Conference on Functional programming languages and Computer architecture (FPCA '93). Association for Computing Machinery, New York, NY, USA, 1993, pages 31–41. https://doi.org/10.1145/165180.165188

[AikenEtAl1993a]

Alexander Aiken, John H. Williams, and Edward L. Wimmers. The FL Project: The design of a Functional Language. IBM Almaden Research Center, 1993年9月. https://theory.stanford.edu/~aiken/publications/trs/FLProject.pdf / PDF

[AikenEtAl1993b]

Alexander Aiken, John H Williams, Edward L Wimmers. Programming a Language. RJ 9877, IBM Almaden Reseearch Center, 1994年8月17日. PDF

[AikenEtAl1994]

Alexander Aiken, Edward L. Wimmers, and T. K. Lakshman. Soft typing with conditional types. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '94). Association for Computing Machinery, New York, NY, USA, 1994 pages 163–173. https://doi.org/10.1145/174675.177847

[AikenEtAl1995]

Alexander Aiken, John H. Williams, and Edward L. Wimmers. Safe: a semantic technique for transforming programs in the presence of errors. ACM Trans. Program. Lang. Syst. 17, 1 (Jan. 1995), 63–84. https://doi.org/10.1145/200994.201002

[Aiken2007]

Alex Aiken. John Backus 1924–2007: A memorial given at the 2007 Conference on Programming Language Design and Implementation. http://theory.stanford.edu/~aiken/other/backus.pdf

[Backus1972a]

John Backus. Reduction languages and variable-free programming. RJ 1010, IBM Research Laboratory, San Jose, California, 1972年4月7日. PDF

[Backus1972b]

John Backus. Re: "Reduction languages and variable-free programming." Cover letter for RJ 1010. IBM Research Laboratory, San Jose, California, 1972年4月19日. PDF

[Backus1973a]

John Backus. Programming language semantics and closed applicative languages. RJ 1245, IBM Research Laboratory, San Jose, California, 1973年7月5日. See [Backus1973c]
. PDF

[Backus1973b]

John Backus. To Recipients of "Reduction languages and variable-free programming." Cover letter for RJ 1245. IBM Research Laboratory, San Jose, California, 1973年7月17日. Paul McJones's copy, with errata applied. PDF

[Backus1973c]

John Backus. Programming language semantics and closed applicative languages. In Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages (POPL '73). Association for Computing Machinery, New York, NY, USA, 71–86. https://doi.org/10.1145/512927.512934

[Backus1973d]

John Backus. Class notes -- Red languages. Probably for two one-hour lectures at the University of California, Santa Cruz? See [Backus1974a]
. 1973年11月14日, 6 pages: PDF / 1973年11月21日, 7 pages: PDF

[Backus1974a]

John Backus. Memorandum for R. E. Gomory. Annual report and Research goals in programming. 1974年1月21日, 7+1 pages. PDF

[Backus1974b]

John Backus. Memorandum for P. S. Dauber and P. C. Goldberg. Pat Goldberg's memo of 2/15/74. IBM San Jose Research Laboratory, 1974年3月19日, 3 pages. PDF

[Backus1974c]

John Backus. Definition of Red with "items" and "rows". As transcribed by Paul McJones, 1974年5月10日. PDF

[Backus1974d]

John Backus. Proposal for a quote-like feature: pseudo-applications. As transcribed by Paul McJones, 1974年5月20日. PDF

[Backus1974e]

John Backus. Semantic definitions, top down and bottom up. As transcribed by Paul McJones, 1974年5月23日. PDF

[Backus1974f]

John Backus. John's definitions: Red with "instruction", "world pair" {i.e, environment}. As transcribed by Paul McJones, 1974年10月30日. PDF

[Backus1974g]

John Backus. Red with Rows and Contexts. Includes quoted expressions per [McJones1974a]. As transcribed by Paul McJones, circa 1974年12月10日. PDF

[Backus1974h]

John Backus. Red with Contexts (but no general rows). As transcribed by Paul McJones, 1974年12月20日. PDF

[Backus1974i]

John Backus. "Proper expressions." As transcribed by Paul McJones, 1974年12月30日. PDF

[Backus1975a]

John Backus. Syntax and semantics. 1975年1月29日. PDF

[Backus1975b]

John Backus. Class notes -- A variable-free functional programming system, FP. 1975年2月19日, 9 pages: PDF / 1975年3月5日, 3 pages: PDF / 1975年4月30日, 7 pages: PDF / 1975年5月7日, 5 pages: PDF

[Backus1978]

John Backus. Can Programming be liberated from the von Neumann Style? A functional style and its algebra of programs. 1977 ACM Turing Award Lecture.

  • RJ 2234, IBM Research Laboratory, San Jose, California 95193, 1978年4月25日, 98 pages. Paul McJones's autographed copy. PDF
  • Commun. ACM 21, 8 (August 1978), pages 613–641. https://doi.org/10.1145/359576.359579

[Backus1979]

J. W. Backus. On extending the concept of program and solving linear functional equations. Draft paper distributed at Summer Workshop on Programming Methodology, Univ. of Calif. at Santa Cruz, Santa Cruz, Calif., August 1979. Backus's correction copy. A revised version was published as [Backus1981a]
. From [Backus2004]
. PDF

[Backus1980]

J. W. Backus. Programming in the 1950's - some personal impressions.

  • In: N. Metropolis et al. (eds.), A History of Computing in the Twentieth Century, Academic Press, New York, 1980, pages 125-135. PDF
  • Video from The First International Research Conference on the History of Computing, Los Alamos, 1976. https://www.youtube.com/watch?v=EylBknGtkqA

[Backus1981a]

John Backus. The algebra of functional programs: Function level reasoning, linear equations, and extended definitions. In: J. Diaz, I. Ramos (eds.), Formalization of Programming Concepts. International Colloquium, Peñíscola, Spain, April 19-25, 1981. Lecture Notes in Computer Science 107, Berlin-Heidelberg-New York: Springer 1981, 1-43. Derived from [Backus1979]
; reprinted as [Backus1982a]
. https://doi.org/10.1007/3-540-10699-5_91 / PDF

[Backus1981b]

John Backus. Function level programs as mathematical objects. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1–10, 1981年10月18日. https://doi.org/10.1145/800223.806757

[Backus1981c]

John Backus. Is Computer Science Based on the Wrong Fundamental Concept of 'Program'? An Extended Concept. In Algorithmic Languages, de Backker and van Vliet (eds). International Symposium on Algorithmic Languages Amsterdam, The Netherlands, 26-29 October 1981. IFIP, North-Holland Publishing Company, 1981, pages 133-165. https://ir.cwi.nl/pub/34328/34328D.pdf#page=158 / Preprint from [Backus2004]
: PDF

[Backus1982a]

John Backus. The algebra of functional programs: Function level reasoning, linear equations, and extended definitions. RJ 3555, IBM Research Laboratory, San Jose, California, 1982年7月23日. Reprint of [Backus1981a]
. PDF / Backus's correction copy from [Backus2004]
: PDF

[Backus1982b]

John Backus. Function-level computing. IEEE Spectrum 19:8, August 1982, 22-27. https://doi.org/10.1109/MSPEC.1982.6366967 / From [Backus2004]
: PDF

[Backus1983]

John Backus. The Coming Revolution. RJ 3994, IBM Research Laboratory, San Jose, California, 1983年8月23日. This paper is the text of a lecture given at MIT on May 5, 1983. From [Backus2004]
. PDF

[Backus1984]

John Backus. The "Program" Approach to FP Programming. 1984年4月17日. From [Williams2026]
. PDF

[Backus1985a]

John Backus. From Function Level Semantics to Program Transformation and Optimization.

  • RJ 4567, IBM Research Laboratory, San Jose, California, 1985年1月8日. From [Backus2004]
    . PDF + slides *** To be scanned
  • In: Ehrig, H., Floyd, C., Nivat, M., Thatcher, J. (eds) Mathematical Foundations of Software Development. CAAP 1985. Lecture Notes in Computer Science, vol 185. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15198-2_5 (open access)

[Backus1985b]

John Backus. The Programming Problem. Text and slides for "Future Computing" series of talks, IBM Yorktown, 1985年7月26日. From [Backus2004]
. PDF

[BackusEtAl1986]

John Backus, John H. Williams, and Edward L. Wimmers. The FL language manual (Preliminary Version). RJ 5339, IBM Research Laboratory, San Jose, California, November 1986. Replaced by [BackusEtAl1989b]
. [Backus2003] #75 observes: "On re-reading this, it looks like we lost our way & got pretty complicated trying to provide 'conveniences'". From [Williams2026]
. PDF

[BackusEtAl1987]

John Backus, John H. Williams, and Edward L. Wimmers. Data Types in FL: An alternative to strong typing? Slides for talk given at IFIP WG 2.2, Antibes, 1987年6月4日. From [Backus2003] #27 PDF

[Backus1987a]

John Backus. Notes on Optimizing FL Programs.

  • 1987年2月24日. PDF
  • 1987年3月2日. PDF

[Backus1987b]

John Backus. Function Level Programming and the FL Language. Video, 1987年10月27日, University Video Communications. https://archive.org/details/JohnBack1987

[Backus1988a]

Programming Languages. Review slides for Juri Matisoo (lab director), 1988年4月26日? ( [Backus2003 #147] claims 1989). From [Backus2004]
. PDF

[Backus1988b]

John Backus. Plan for implementing an FL system. 1988年9月29日. From [Backus2004]
. PDF

[BackusEtAl1988]

John Backus, Peter Lucas, John H. Williams, and Edward L. Wimmers. FL Reference Manual. 1988年11月23日. Abstract: This is the (unreadable) reference manual for FL. From [Backus2003] #194. PDF

[BackusEtAl1989a]

John Backus Group Meeting. Video recording at IBM Almaden Laboratory, 1989年7月5日. Mary Van Deusen, videographer: "Raw footage from B-roll I shot at Almaden, the Calfornia IBM Reseach lab for a video on their computer science department. John allowed me to crawl around the floor through the meeting, then I shot his group's video segments. The videos were part of my multimedia research project for Abe Peled, back in NY's IBM Research."
https://www.youtube.com/watch?v=KzBkb-bvNK4

  • 00:00. 1. John Williams leads a group meeting on the bootstrap compiler's current status. *John Williams notes: "The participants around John's desk are (L to R) Thom Linden, Ed Wimmers, JW, Brian Murphy (Stanford student working w/ Alex), Peter Lucas, and Paul Tucker."
  • 24:40. 2. John Backus discusses the goals of the FL project.
  • 30:13. 3. Ed Wimmer discusses the choice of a function-level language.
  • 31:56. 4. Paul Tucker discusses rewriting.

[BackusEtAl1989b]

John Backus, John H. Williams, Edward L. Wimmers, Peter Lucas, and Alexander Aiken. FL language manual, Parts 1 and 2. RJ 7100, IBM Almaden Research Center, San Jose, California, 1989年10月26日. Part 3, to be a formal description of the denotational semantics and the primitive functions of FL, was never published. From [Backus2004]
. PDF

[Backus1990]

John Backus. Annual Fellow report for 1990: The Functional Programming Project. IBM Corporation. 1990年12月17日. From [Backus2004]
. PDF

[BackusEtAl1990]

John Backus, John H. Williams, and Edward L. Wimmers. An Introduction to the FL Language. In Research Topics in Functional Programming, D.A. Turner (Ed.), Addison-Wesley, Reading, MA, 1990. Revised excerpt from [BackusEtAl1986]
. PDF

[Backus1991]

John Backus. FL Project Status. 1991年4月4日. "Last review, for McGroddy. I was very saddened and disgusted by IBM’s failure to support this really exciting project that was doing great, had wonderful people, great prospects." From [Backus2004]
. PDF

[Backus2003]

John W. Backus papers, 1951-2001 (bulk 1953-1991). Library of Congress, Manuscript Division. https://lccn.loc.gov/mm2003084968

[Backus2004]

John W. Backus. Collection of papers given to Paul McJones, 2004年11月7日. These will be offered to the Computer History Museum, along with documents acquired during 1974-1975 while working with Backus.

[Bjørner1972]

Dines Bjørner. Finite State Tree Computations (Part I). RJ 1053, IBM Research Division, San Jose, Calf., 1972年6月13日. PDF

[BjørnerEtAl1973]

D. Bjørner, E. F. Codd, K. L. Deckert, and I. L. Traiger. The Gamma-0 n-ary Relational Data Base Interface Specifications of Objects and Operations. RJ 1200, IBM San Jose Research Laboratory, 1973年4月11日. PDF

[Bjørner2025]

Dines Bjørner. Reflections. 2025年12月30日. https://www.imm.dtu.dk/~dibj/2025/reflections/reflektioner.pdf

[Booch2007]

Grady Booch, interviewer. Oral History of John Backus, recorded 2006年9月5日. X3715.2007, Computer History Museum, 2007.

[BruceWilliams1982]

Kim B. Bruce and John H. Williams. Letters concerning FP implementations. 1982年4月. From [Williams2026]
. PDF

[Chen2016]

Jiahao Chen. "This guy’s arrogance takes your breath away”: Letters between John W. Backus and Edsger W. Dijkstra, 1979. Medium, 2016年5月29日. https://medium.com/@acidflask/this-guys-arrogance-takes-your-breath-away-5b903624ca5f

[Dijkstra1978a]

Edsger W. Dijkstra. Trip report, Marktoberdorf 1978年7月24日–8月6日. https://www.cs.utexas.edu/~EWD/ewd06xx/EWD676.PDF / https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD676.html

[Dijkstra1978b]

Edsger W. Dijkstra. A review of the 1977 Turing Award Lecture by John Backus. EWD692, undated (late 1978). http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD692.PDF / https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD692.html

[Goldberg1974]

P. C. Goldberg. John Backus's Remarks on Red Languages and Reducing the Cost of Programming. Memo to P. S. Dauber, IBM Research Yorktown Heights, 1974年2月15日. PDF

[Gostelow1977]

Kim P. Gostelow. Letter to John Williams re 1977 Dataflow and Reduction Languages Workshop, 1977年4月4日. From [Williams2026]
. PDF

[GuttagEtAl1981]

John Guttag, James Horning, and John Williams. FP with data abstraction and strong typing. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, pages 11–24. https://doi.org/10.1145/800223.806758

[HalpernEtAl1985]

Joseph Y. Halpern, John H. Williams, Edward L. Wimmers, and Timothy C. Winkler. Denotational Semantics and Rewrite Rules for FP. In Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '85). Association for Computing Machinery, New York, pages 108–120. https://doi.org/10.1145/318593.318623

[HalpernEtAl1986]

Joseph Y. Halpern, John H. Williams, Edward L. Wimmers: Good Rewrite Strategies for FP. Proceedings of the 1st IEEE Symposium on Logic in Computer Science (Boston, Mass.), IEEE, New York, 1986, pages 149–162.

[HalpernEtAl1990]

Joseph Y. Halpern, John H. Williams, and Edward L. Wimmers. Completeness of rewrite rules and rewrite strategies for FP. J. ACM 37, 1 (Jan. 1990), pages 86–143. Subsumes [HalpernEtAl1985], HalpernEtAl1986
. https://doi.org/10.1145/78935.78939

[HalpernWimmers1995]

J. Y. Halpern and E. L. Wimmers. Full Abstraction and Expressive Completeness for FP. Information and Computation Volume 118, Number 22, 1995, pages 246-271. Preprint https://www.cs.cornell.edu/home/halpern/papers/FP_abstraction.pdf Earlier version in Proceedings of the Symposium on Logic in Computer Science (1987), pages 257-271.

[HughesEtAl1987]

John Hughes, John Williams, Ed Wimmers, John Backus. Higher Order Functions and I/O in Strict Functional Languages. Slides for talk at Year Of Programming Conf., Univ of Texas, 1987年8月28日. PDF

[McJones1974a]

Paul McJones. Proposal for Quoted Expressions in Red. 1974年5月15日. PDF

[McJones1974b]

Paul McJones. [Slides for Red talk for Department K55], 1974年6月20日. PDF

[McJones1975a]

Paul McJones. Mcg source code for Red combining forms and primitives. Circa 1975年2月. PDF

[McJones1975b]

Paul McJones. A Church-Rosser Property of Closed Applicative Languages. RJ 1589, IBM Research Laboratory, San Jose, California 95193, 1975年5月23日. PDF

[McJones1978]

Paul McJones. Poplar FP. Poplar source code for FP combining forms and primitive functions, 1978年10月16日. PDF

[McJones1980]

Paul McJones. Alto Mesa Red. Mesa source code, definitions in Red, and test run. 1979-1980. PDF

[McJones2007]

Paul McJones. Remembering John Backus. Dusty Decks blog, 2007年4月1日. https://mcjones.org/dustydecks/remembering-john-backus

[Milner1978]

Robin Milner. Letters to John Backus. 1978年9月29日および10月11日. From [Backus2004]
.

[Murphy1990]

Brian R. Murphy. A type inference system for FL. Master's thesis, MIT, 1990年9月. PDF (from http://suif.stanford.edu/~brm/papers/msthesis.ps.gz)

[Rosen1974a]

Barry K. Rosen. Notes on application of complete posets to RED languages. Computer Science Department, IBM Watson Research Center, 1974年8月1日. PDF

[Rosen1974b]

Barry K. Rosen. More notes on application of complete posets to RED languages. Computer Science Department, IBM Watson Research Center, 1974年10月28日. PDF

[Scott1978]

Dana Scott. Letters to John Backus. From [Backus2004]
. 1978年9月14日および23日.

[Stegman1979]

Claire Stegmann. Pathfinder. THINK, IBM Corporation, July/August 1979, pages 18-27. PDF

[Summers1972]

P. D. Summers. Documentation and source code of RED systems based on [Backus1972a]
, T. J. Watson Research Center, 1972年8月.

  • Sign on and use of the RED system. 1972年8月11日. PDF
  • Three algorithms to convert lambda expressions inlo RED language expressions. 1972年8月15日. PDF
  • Summary of RED primitives and their definitions as lambda notations. 1972年8月29日. PDF
  • Adding primitives to the RED systems. 1972年8月29日. PDF
  • Annotated listings of the RED systems. 1972年8月29日. PDF

[Williams1977]

John Williams. "Red 1, Red 1, shining bright" [Poem in honor of John Backus.] Cornell University, 1977年12月. PDF

[Williams1978]

John H. Williams. Reduction Languages. Slides presented at the NATO Summer School in Marktoberdorf, August 1978. See Dijkstra's remarks in [Dijkstra1978a]
. PDF

[Williams1981a]

John H. Williams. Formal Representations for Recursively Defined Functional Programs. J. Diaz, I. Ramos (eds.). Formalization of Programming Concepts. International Colloquium, Peñíscola, Spain, April 19-25, 1981. Lecture Notes in Computer Science 107, Berlin-Heidelberg-New York: Springer 1981, pages 460-470. https://doi.org/10.1007/3-540-10699-5_119 / PDF

[Williams1981b]

John H. Williams. Notes on the FP Style of Functional Programming. In: Functional Programming and its Applications: An Advanced Course, J. Darlington, P. Henderson, and D. A. Turner (eds.), Cambridge University Press, March 1982. Proceedings of an advanced course held at Newcastle University, 20-31 July 1981. PDF

[Williams1982]

John H. Williams. On the Development of the Algebra of Functional Programs.

[Williams2026]

John Williams. Collection of papers and photographs given to Paul McJones, 2026年8月.

[WilliamsWimmers1988]

J. H. Williams and E. L. Wimmers. Sacrificing simplicity for convenience: Where do you draw the line? In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '88). Association for Computing Machinery, New York, NY, USA, 169–179. https://doi.org/10.1145/73560.73575

[WilliamsWimmers1990a]

John H. Williams and Edward L. Wimmers. The New Simplification Algorithm. 1990年2月8日. "I include this item to show the difficulties in accurately transforming FL programs, even though it would require a lot of study of the FL manual and many other papers to understand this." From [Backus2003] #201. PDF

[WilliamsWimmers1990b]

John H. Williams and Edward L. Wimmers. An optimizing compiler based on program transformation. IBM Almaden Research Center, 1990年12月3日. From [Backus2004]
. PDF

[Wimmers1988]

Ed Wimmers. Some Basic FL Laws. 1988年9月23日. "Shows the richness of the algebra of the higher order functions of FL." From [Backus2003] #198. PDF

パート2: 関連研究

[BackusHerrick1954]

J. W. Backus and H. Herrick. IBM 701 Speedcoding and other automatic programming systems. In Proc. Symp. on Automatic Programming for Digital Computer, Washington DC, The Office of Naval Research, May 1954, pages 106-113. PDF

[BeebeMcJones2026]

Nelson H. F. Beebe and Paul McJones. A bibliography of publications of John Warner Backus. Report, University of Utah, Department of Mathematics, Salt Lake City, UT 84112-0090, USA, 2026年6月16日. 35 pages https://ftp.math.utah.edu/pub/bibnet/authors/b/backus-john-w.html

[BirdEtAl2021]

Richard Bird, Jeremy Gibbons, Ralf Hinze, Peter Höfner, Johan Jeuring, et al. Algorithmics. Advancing Research in Information and Communication Technology, AICT-600, pages 59-98, 2021. https://inria.hal.science/hal-03325977/document

[Burge1968]

W. H. Burge. Mcg—A Functional Programming System. RC-2189, IBM Research, Yorktown Heights, New York, 1968年8月29日. PDF

[Landin1964]

P. J. Landin. The mechanical evaluation of expressions. Computer J. 6, 4, 1964, pages 308-320. https://doi.org/10.1093/comjnl/6.4.308

[McCarthy1960]

John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Commun. ACM 3, 4 (April 1960), pages 184–195. https://doi.org/10.1145/367177.367199

[Raymond1975]

François-Henri Raymond. Note sur l’algèbre des fonctions. Revue française d’automatique informatique recherche opérationnelle. Informatique théorique, tome 9, no R3 (1975), pages 25–49. (French) http://www.numdam.org/item?id=ITA_1975__9_3_25_0 / English translation by Claude.ai PDF

[Raymond1977]

François-Henri Raymond. Note sur la suppression des étiquettes en programmation. RAIRO – Informatique théorique, tome 11, no 1 (1977), pages 3–16. https://www.numdam.org/item/?id=ITA_1977__11_1_3_0 / English translation by Claude.ai PDF

[Rosser1984]

J. Barkley Rosser. Highlights of the History of the Lambda-Calculus, IEEE Annals of the History of Computing, Volume 6, Number 4, Oct.–Dec. 1984, pages 337–349. https://doi.org/10.1109/MAHC.1984.10040 / https://lawrencecpaulson.github.io/papers/Rosser-Lambda-Calculus.pdf

[Scott1976]

Dana Scott. Data Types as Lattices. SIAM Journal on Computing, Volume 5, Number 3, September 1976, pages 522–587. https://doi.org/10.1137/0205037 / https://www.cs.ox.ac.uk/files/3287/PRG05.pdf

[Scott1977]

Dana Scott. Logic and Programming Languages. 1976 ACM Turing Award lecture. Comm. ACM, Vol. 20, 1975, pages 634–641. https://doi.org/10.1145/359810.359826

パート3: バッカスに影響を受けたもの

[BadenPatel1983]

S. B. Baden and D. R. Patel. Berkeley FP — Experiences with a Functional Programming Language. Conference Record of COMPCON ’83, San Francisco, California, pages 274–277, March 1983.

[Baden1983a]

Scott Baden. Berkeley FP User's Manual, Version 41. UNIX Programmer’s Manual Supplementary Documents

[Baden1983b]

Scott Baden. DFT → FFT transformation in FP. University of California, Berkeley, 1983年5月3日. PDF

[Baden1983c]

Scott Baden. Berkeley FP source code. 1983–1985. .zip

[Banerjee1992]

Debasish Banerjee. A technique for solving a class of quadratic FP equations. Science of Computer Programming, Volume 19, Issue 1, 1992, pages 61–85, ISSN 0167–6423. https://doi.org/10.1016/0167-6423(92)90004-U

[Bellegarde1986]

Françoise Bellegarde. Rewriting systems on FP expressions to reduce the number of sequences yielded. Science of Computer Programming, Volume 6, 1986, Pages 11–34, ISSN 0167–6423. https://doi.org/10.1016/0167-6423(86)90017-1

[Bellot1984]

Patrick Bellot. Semantiques comparees des systemes de programmation fonctionnelle FP et FFP de J.W. Backus ["Comparative Semantics of J.W. Backus's Functional Programming Systems FP and FFP"]. In: Paul, M., Robinet, B. (eds) International Symposium on Programming. Programming 1984. Lecture Notes in Computer Science, vol 167. Springer, Berlin, Heidelberg, 1984. https://doi.org/10.1007/3-540-12925-1_25

[Bellot1985]

Patrick Bellot. 1985. High order programming in extended FP. High order programming in extended FP. In: Jouannaud, JP. (eds) Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science, vol 201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15975-4_30

[Ben-AsherEtAl1993]

Y. Ben-Asher, G. Rünger, A. Schuster, and R. Wilhelm. 2DT-FP: An FP based programming language for efficient parallel programming of multiprocessor networks. In: Bode, A., Reeve, M., Wolf, G. (eds) PARLE '93 Parallel Architectures and Languages Europe. PARLE 1993. Lecture Notes in Computer Science, vol 694. Springer, Berlin, Heidelberg, 1993. https://doi.org/10.1007/3-540-56891-3_4

[Berkling1975]

Klaus J. Berkling. Reduction Languages for Reduction Machines. 2nd Annual Symposium on Computer Architecture, Houston, Texas, 1975年1月20–22日. PDF

[Biagioni1988]

Edoardo S. Biagioni. FPC: A Translator for FP. Report R88-027, University of North Carolina, 1988年5月. PDF / https://www.cs.unc.edu/techreports/88–027.pdf

[Böhm1982]

Corrado Böhm. Combinatory foundation of functional programming. In Proceedings of the 1982 ACM Symposium on LISP and Functional Programming (LFP '82). Association for Computing Machinery, New York, 1982, pages 29–36. https://doi.org/10.1145/800068.802132

[BossiGhezzi1984]

Annalisa Bossi, Carlo Ghezzi. Using FP as a query language for relational data-bases. Computer Languages, Volume 9, Issue 1, 1984, Pages 25–37, ISSN 0096-0551. https://doi.org/10.1016/0096-0551(84)90010-9

[Buccianti2020]

Benjamín Buccianti. Interactive FP interpreter written in Clojure. 2020. .zip / https://github.com/bbuccianti/fp

[BunemanFrankel1979]

Peter Buneman and Robert E. Frankel. FQL: a functional query language. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data (SIGMOD '79). Association for Computing Machinery, New York, NY, USA, 1979, pages 52–58. https://doi.org/10.1145/582095.582104

[Chiarini1980]

A. Chiarini. 1980. On FP languages combining forms. SIGPLAN Not. 15, 9 (September 1980), 25–27. https://doi.org/10.1145/947706.947709

[ChoppyEtAl1983]

C. Choppy, G. Guiho, and S. Kaplan. Algebraic semantics for FP languages, a lisp compiler and its proof, Rapport LRI N° 133, Orsay, 1983.

[ChoppyEtAl1985]

C. Choppy, G. Guiho, and S. Kaplan. A LISP compiler for FP language and its proof via algebraic semantics. In: Ehrig, H., Floyd, C., Nivat, M., Thatcher, J. (eds) Mathematical Foundations of Software Development, CAAP 1985. Lecture Notes in Computer Science, vol 185. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15198-2_26 (open access)

[ChristopherAmeiss1990]

T. Christopher and D. Ameiss. Functional programming in a parallel environment: the implementation of FP in MDC. SIGPLAN Not. 25, 11 (Nov. 1990), 85–94. https://doi.org/10.1145/101356.101362

[CremersHibbard1983]

A. B. Cremers and T. N. Hibbard. Applicative State Transition Systems in LISP-Like Notation. In: Kupka, I. (eds) GI - 13. Jahrestagung. Informatik-Fachberichte, vol 73. Springer, Berlin, Heidelberg, 1983. https://doi.org/10.1007/978-3-642-69298-7_6

[Deleuze2003]

Christophe Deleuze. oc-FP: An OCAML implementation of John Backus' FP system. Version 0.21, 2003.

[DiGiorgio2019]

Alessandro Di Giorgio. fpar: a data parallel implementation of Backus's FP programming language as an embedded DSL in C++17. 2019. .zip / https://github.com/alessandrodgr/fpar

[DoschMöller1984]

Walter Dosch and Bernhard Möller. Busy and lazy FP with infinite objects. In Proceedings of the 1984 ACM Symposium on LISP and functional programming (LFP '84). Association for Computing Machinery, New York, NY, USA, 1984, pp282–292. https://doi.org/10.1145/800055.802045

[Ei-Affendi1994]

M.A. Ei-Affendi. Imposing an FP Layer on a Risc Machine. Journal of King Saud University—Engineering Sciences, Volume 6, Issue 2, 1994, Pages 167–183, ISSN 1018-3639. https://doi.org/10.1016/S1018-3639(18)30606-8

[Facorro2011]

Juan Facorro. fp interpreter written in Lisp. Common Lisp source code, 2011. .zip / https://github.com/jfacorro/fp-interpreter-in-lisp

[FickertSudkamp1992]

Chris Fickert and Thomas Sudkamp. Unification based FP interpreters. SIGPLAN Not. 27, 11 (Nov. 1992), 49–58. https://doi.org/10.1145/141018.141042

[Frank1981]

Geoffrey A. Frank. Specification of data structures for FP programs. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 221–228. https://doi.org/10.1145/800223.806782

[Gabriëls2007]

René Gabriëls, Dirk Gerrits, and Peter Kooijmans. John W. Backus : 3 December 1924–17 March 2007. Report for class 2R930 Geschiedenis van Informatica (History of Computing), Faculteit Wiskunde & Informatica, Technische Universiteit Eindhoven, 2007年5月29日. https://dirkgerrits.com/publications/john-backus.pdf

[George1988]

K. M. George. Objects and data structures in the FP paradigm. Seventh Annual International Phoenix Conference on Computers an Communications. 1988 Conference Proceedings, Scottsdale, AZ, USA, 1988, pages 256–260. https://doi.org/10.1109/PCCC.1988.10081

[HalpernEtAl1988]

Brent Hailpern, T. Huynh, and G. Revesz. Comparing two functional programming systems. IEEE Transactions on Software Engineering, 15(5):532–542. http://doi.ieeecomputersociety.org/10.1109/32.24702 Also RJ–12598, IBM Research Division, 1988年3月17日. https://brent.hailpern.com/wp-content/uploads/2019/12/rc12598.pdf

[Hemmendinger1985]

David Hemmendinger. Lazy Evaluation and Cancellation of Computations. Proceedings of the 1985 International Conference on Parallel Processing. 1985年8月20–23日. PDF

[HendersonEtAl1983]

Peter Henderson‚ Geraint A. Jones and Simon B. Jones. The LispKit Manual. Oxford University Computer Laboratory Programming Research Group, 1983. Technical Monographs PRG-32(1) and PRG-32(2). Includes an implementation of muFP written in LispKit. mirror

[HongLingzi1989]

Z. Hong and J. Lingzi. A knowledge-based system to synthesize FP programs from examples. In: Martins, J.P., Morgado, E.M. (eds) EPIA 89. EPIA 1989. Lecture Notes in Computer Science, vol 390. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51665-4_89

[HuynhEtAl1985]

Tien Huynh, Brent Hailpern Lee W. Hoevel. An execution architecture for FP. IBM J. Res. Development, Vol. 30, No. 6, November 1986, pages 609–616. https://brent.hailpern.com/wp-content/uploads/2017/03/IJRD_30_6_1986.pdf / https://doi.org/10.1147/rd.306.0609

[HuynhHailpern1986]

Tien Huynh and Brent Hailpern. An Improved DEL-Style Execution Architecture for FP. RC-12202, IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598, 1986年10月2日. https://brent.hailpern.com/wp-content/uploads/2017/03/rc12202.pdf Also published in Proc. Twentieth Hawaii Int. Conf. System Sciences, vol. 1, Kona, HI, Jan. 1987, pages 369–376.

[Ida1982]

T. Ida. A manual of IPCR-FP. Information Science Laboratory, Institute of Physical and Chemical Research. 1982.

[Ida1983]

Tetsuo Ida. Some FP algebra with Currying operation. Information Processing Letters, Volume 17, Issue 5, 1983, Pages 259–261, ISSN 0020–0190. https://doi.org/10.1016/0020-0190(83)90110-2

[IdaTanaka1983]

Tetsuo Ida and Jiro Tanaka. Functional Programming with Streams. Information Processing '83: Proceedings of the IFIP Ninth World Computer Congress, Sept 19–23, 1983, pp 265–270.

[IdaTanaka1984]

T. Ida and J. Tanaka. Functional programming with streams —Part II—. New Generation Computing 2, pages 261–275 (1984). https://doi.org/10.1007/BF03037060

[IslamEtAl1981]

N. Islam, T. J. Myers, and P. Broome. A simple optimizer for FP-like languages. In Proceedings of the 1981 conference on Functional Programming Languages and Computer Architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1981, pp33–40. https://doi.org/10.1145/800223.806760

[JonesMuchnick1982]

Neil D. Jones and Steven S. Muchnick. A fixed-program machine for combinator expression evaluation. In Proceedings of the 1982 ACM symposium on LISP and functional programming (LFP '82). Association for Computing Machinery, New York, NY, USA, 1982, 11–20. https://doi.org/10.1145/800068.802130

[KapurEtAl1981]

D. Kapur, D. R. Musser, and A. A. Stepanov. Operators and algebraic structures. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, pages 59–64. https://doi.org/10.1145/800223.806763

[KieburtzShultis1981]

Richard B. Kieburtz and Jonathan Shultis. Transformations of FP program schemes. In Proceedings of the 1981 conference on Functional Programming Languages and Computer Architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1981, pages 41–48. Cited in [Backus1985a]
. https://doi.org/10.1145/800223.806761

[Kluge1983]

Werner E. Kluge. Cooperating reduction machines. IEEE Transactions on Computers, C-32(11):1002-1012, November 1983. https://doi.org/10.1109/TC.1983.1676151

[Koster1980]

A. Koster. An algorithm for translating LISP programs into reduction language programs. In: Robinet, B. (eds) International Symposium on Programming. Programming 1980. Lecture Notes in Computer Science, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09981-6_14

[Koster1985]

Alexis Koster. Compiling APL for parallel execution on an FFP machine. In Proceedings of the International Conference on APL: APL and the Future (APL '85). Association for Computing Machinery, New York, NY, USA, 1985, pp29–37. https://doi.org/10.1145/17701.255327

[Leszczyłowski1980]

J. Leszczyłowski. On Proving Laws of the Algebra of FP-Systems in Edinburgh LCF. In Proceedings of AAAI-80, 1980, pages 84–86. https://cdn.aaai.org/AAAI/1980/AAAI80-024.pdf

[Leszczyłowski1981]

J. Leszczyłowski. FP systems in Edinburgh LCF. In: Díaz, J., Ramos, I. (eds) Formalization of Programming Concepts. ICFPC 1981. Lecture Notes in Computer Science, vol 107. Springer, Berlin, Heidelberg, 1981. https://doi.org/10.1007/3-540-10699-5_112

[LinLin1988]

Yen-Chun Lin and Ferng-Ching Lin. The use of aFP to design regular array algorithms. Proceedings. 1988 International Conference on Computer Languages, Miami Beach, FL, USA, 1988, pages 388-395. https://doi.org/10.1109/ICCL.1988.13088

[LuoKatayama1990]

Junhui Luo, Takuya Katayama. A Type Inference System for FP Programs. Advances in Software Science and Technology, Elsevier, Volume 1, 1990, Pages 105–131. https://doi.org/10.1016/B978-0-12-037101-3.50012-0

[LichtensteinKaplan1990]

N. Lichtenstein and S. Kaplan. FPL : Functional plus logic programming: an integration of the FP and Prolog languages. In: Kaplan, S., Okada, M. (eds) Conditional and Typed Rewriting Systems. CTRS 1990. Lecture Notes in Computer Science, vol 516. Springer, Berlin, Heidelberg, 1991. https://doi.org/10.1007/3-540-54317-1_98

[Magó1976]

Gyula A. Magó. A network of microprocessors to execute reduction languages. Department fo Computer Science, University of North Carolina, 1976年6月. PDF

[Magó1981]

Gyula Magó. Copying operands versus copying results: A solution to the problem of large operands in FFP'S. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 93–98. https://doi.org/10.1145/800223.806767

[NguyenEtAl1986]

Van Nguyen, Alan Demers, and Brent Hailpern. FPL: A Functional Parallel Language. RC 11858, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, 1986年5月5日. https://brent.hailpern.com/wp-content/uploads/2017/03/rc11858.pdf

[Norman1986]

Eric Norman. Tracking the Elusive Eureka. Technical Report TR636, Computer Sciences Department, University of Wisconsin, 1986年3月. https://minds.wisconsin.edu/handle/1793/58710

[OngEtAl1990]

E. Teng Ong, K. M. George and K. A. Teague. BT-Server FP Interpreter. Proceedings of the Fifth Distributed Memory Computing Conference, 1990, Charleston, SC, USA, 1990, pages 1147-1152. https://doi.org/10.1109/DMCC.1990.556329

[O'Rourke2002]

Sean O'Rourke. Language-FP-0.03, 2002年6月1日. https://metacpan.org/release/SEANO/Language-FP-0.03

[Pagan1986]

Frank G. Pagan. On the feasibility of teaching Backus-type functional programming (FP) as a first language. SIGCSE Bull. 18, 3 (Sep 1 1986), 31–35. https://doi.org/10.1145/378905.378929

[Pagan1987]

Frank G. Pagan. A graphical FP language. SIGPLAN Notices. 22, 3 (March 1987), 21–39. https://doi.org/10.1145/24697.24699

[Partain1989]

William Partain. Graph Reduction Without Pointers. Ph.D. Thesis, TR89-045, Department of Computer Science, University of North Carolina at Chapel Hill, 1989年12月. https://www.cs.unc.edu/techreports/89-045.pdf

[PresnellPargas1981]

H. A. Presnell and R. P. Pargas. Communication along shortest paths in a tree machine. In Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture (FPCA '81). Association for Computing Machinery, New York, pages 107–114. https://doi.org/10.1145/800223.806769

[Radensky1987]

A Radensky. Lazy evaluation and nondeterminism make Backus' FP-systems more practical. SIGPLAN Not. 22, 4 (April 1987), pages 33–40. https://doi.org/10.1145/24714.24718

[Robison1987a]

Arch D. Robison. A Functional Programming Interpreter. M.S. Thesis, University of Illinois, Urbana-Champaign, 1987年1月.

[Robison1987b]

Arch D. Robison. Illinois Functional Programming: A Tutorial. BYTE, Volume 12, Number 2, February 1987, page 115–125. PDF

[Robison1987c]

Arch D. Robison. IFP User's Manual. Professional Workstation Research Group Technical Report #7, University of Illinois, Urbana-Champaign, 1987年2月9日. ASCII

[Robison1987d]

Arch D. Robison. The Illinois functional programming interpreter. In Papers of the Symposium on Interpreters and interpretive techniques (SIGPLAN '87). Association for Computing Machinery, New York, pages 64–73. https://doi.org/10.1145/29650.29657

[Robison1987e]

Arch D. Robison. IFP source code. 1987年7月7日. .zip / https://sources.vsta.org/comp.sources.unix/volume10/ifp/

[RyderPendergrast1988]

B. G. Ryder and J. S. Pendergrast. Experiments in optimizing FP. IEEE Transactions on Software Engineering, vol. 14, no. 4, pages 444–454, April 1988. https://doi.org/10.1109/32.4668

[Seo2016]

Kwang Yul Seo. A Haskell implementation of John Backus's FP (Functional Programming) system. .zip / https://github.com/kseo/fp