Schemeプログラミング言語の歴史

プログラミング言語Schemeの歴史は、20 世紀後半のLispファミリー言語の初期メンバーの開発から始まります。Scheme の設計と開発期間中、言語設計者のGuy L. SteeleとGerald Jay Sussman は、Lambda 論文(1975-1980)として知られるマサチューセッツ工科大学(MIT) AI メモの影響力のあるシリーズを発表しました。これにより、言語の人気が高まり、1990 年以降は標準化の時代が到来しました。Scheme の歴史の多くは、開発者自身によって文書化されています。^[1]

Scheme の開発は、互いに大きく異なる 2 つの先行言語の影響を強く受けました。Lispは Schemeの一般的な意味と構文を提供し、ALGOL はScheme の語彙範囲とブロック構造を提供しました。Scheme は Lisp の方言ですが、Lisp は進化してきました。Scheme の元となった Lisp の方言は、当時は主流でしたが、現代の Lisp とはまったく異なります。

Lisp は、1958 年にマサチューセッツ工科大学(MIT)在学中のジョン マッカーシーによって発明されました。マッカーシーは 1960 年にCommunications of the ACM 誌に「記号式の再帰関数と機械による計算、パート I」^{[2] と}題する論文で Lisp の設計を発表しました (パート II は出版されませんでした)。彼は、いくつかの単純な演算子と関数の表記法を使用して、アルゴリズム用の チューリング完全な言語を構築できることを示しました。

Lisp の構文を特徴付けるS 式の使用は、当初は McCarthy が「 m 式」と呼んだものを採用した言語が開発されるまでの暫定的な措置として意図されていました。たとえば、 m 式はcar[cons[A,B]]S 式と同等です(car (cons A B))。しかし、 S 式は人気があり、 m 式を実装する多くの試みは普及しませんでした。

Lisp の最初の実装は、 Steve RussellによるIBM 704上での実装でした。Russell は McCarthy の論文を読み、その論文で説明されている eval 関数をマシン コードでコーディングしました。Lispでリストの先頭要素と末尾を記述するために使用される、おなじみの (しかし初心者には不可解な) CAR と CDRという名前は、2 つのIBM 704アセンブリ言語コマンド、Contents of Address Register と Contents of Decrement Register から派生したものです。これらのコマンドはそれぞれ、36 ビットのIBM 704 命令語のセグメントに対応する 15 ビットのレジスタの内容を返しました。

Lispで書かれた最初の完全なLispコンパイラは、1962年にMITのTim HartとMike Levinによって実装されました。^[3]このコンパイラは、コンパイルされた関数と解釈された関数を自由に混在させることができる増分コンパイルのLispモデルを導入しました。

Schemeの開発において最も重要な2つのLispの変種は、どちらもMITで開発されました。McCarthyらによって開発されたLISP 1.5 ^[4]と、 MITのProject MAC向けに開発されたMaclisp ^{[5]です。MaclispはLISP 1.5の直接の後継であり、PDP-10および}Multicsシステムで実行されました。

Lispは誕生以来、特にPDP-10において人工知能（AI）研究コミュニティと密接な関係がありました。PDP -6とPDP-10の36ビットワードサイズは、 1ワードに2つのLisp 18ビットポインタを持つことの有用性に影響されました。^[6]

ALGOL 58 は、もともと「国際アルゴリズム言語」の略称であるIALと呼ばれていましたが、1958年にチューリッヒ工科大学で開催された会議で、ヨーロッパとアメリカのコンピュータ科学者の委員会によって共同で開発されました。 パリで開催されたALGOL 60会議で開発された後の改訂版であるALGOL 60は、現在ではALGOLと呼ばれていますが、商業的な成功がなく限界があったにもかかわらず、アルゴリズムの公開の標準となり、その後の言語開発に大きな影響を与えました。 トニー・ホーアは次のように述べています。「これは時代をはるかに先取りした言語であり、その前身だけでなく、ほぼすべての後継言語よりも改善されています。」^[7]

ALGOL はブロック構造と語彙スコープの使用を導入しました。また、ALGOL は、名前による呼び出しによるデフォルト パラメータ渡しメカニズムが難しいことでも有名でした。このメカニズムは、プロシージャまたは関数の実行中に、仮パラメータの代わりに作業パラメータを表す式のテキスト置換を要求するように定義されており、実行中に参照されるたびに再評価されます。ALGOL 実装者は、作業パラメータのコンテキストをキャプチャしてプロシージャまたは関数の実行中に評価できるようにする、 サンクと呼ばれるメカニズムを開発しました。

1971 年、サスマン、ドリュー・マクダーモット、ユージン・チャーニアックは、カール・ヒューイットの野心的なPlannerプロジェクトの部分的で、いくぶん不十分な実装であるMicro-Plannerというシステムを開発しました。サスマンとヒューイットは他の人たちと共同で Muddle (後にMDLと改名) に取り組みました。これはヒューイットのプロジェクトの構成要素となる拡張 Lisp です。ドリュー・マクダーモットとサスマンは 1972 年に Lisp ベースの言語Conniver を開発し、非生産的だと彼らが考えていた Planner の自動バックトラックの使用法を改訂しました。ヒューイットは、Conniver の「複雑な制御構造」が Planner の問題の解決策であるかどうか疑問に思いました。パット・ヘイズは次のように述べている。「しかしながら、彼ら（サスマンとマクダーモット）の解決策は、ユーザーにプランナーの実装プリミティブへのアクセスを与えるというものだが、これはある意味では後退的なステップである（コニバーのセマンティクスとは何なのか？）」^[8]

1972年11月、ヒューイットと彼の学生は、プランナーの問題の解決策として、アクター計算モデルを発明しました。 ^[9] アクターの部分的な実装は、プランナー73（後にPLASMAと呼ばれる）と呼ばれました。当時MITの大学院生だったスティールはこれらの開発を追跡しており、彼とサスマンは、モデルをよりよく理解するために、 Maclispで開発された独自の「小さなLisp」でアクターモデルのバージョンを実装することを決定しました。これを基に、彼らはアクターを作成し、メッセージを送信するメカニズムの開発を開始しました。^[10]

PLASMA の語彙スコープの使用は、ラムダ計算に似ていた。サスマン氏とスティール氏は、ラムダ計算でアクターをモデル化しようと決めた。彼らはモデリング システムを Schemer と名付けたが、最終的にはDEC PDP-10のITSファイル システムの 6 文字制限に合わせるために Scheme に変更した。彼らはすぐに、アクターは本質的には決して戻らずに継続を呼び出すクロージャであると結論付け、クロージャとアクターは、調査の目的上、本質的に同一の概念であると判断した。彼らは冗長とみなしたコードを削除し、その時点で、非常に小さくて高性能な Lisp 方言を記述していたことを発見した。ヒューイット氏は Scheme ^{[11] [12]}の「扱いにくい制御構造」に批判的であり続け、Scheme 実装で使用されているプリミティブ (、、など)は後退であると考えた。 START!PROCESSSTOP!PROCESSEVALUATE!UNINTERRUPTIBLY

25年後の1998年、サスマン氏とスティール氏は、Schemeのミニマリズムは意識的な設計目標ではなく、むしろ設計プロセスの意図しない結果であったと振り返っています。「私たちは実際に複雑なものを作ろうとしていましたが、偶然にも、私たちの目標をすべて満たすが、意図していたよりもはるかに単純なものを設計してしまったことに気付きました...ラムダ計算、つまり小さくて単純な形式主義が、強力で表現力豊かなプログラミング言語の核として機能できることに気付きました。」^[10]

一方、ヒューイットは計算の基礎としてのラムダ計算に対して批判的であり、「実際のところ、ラムダ計算はある種の逐次的および並列的な制御構造を表現できるが、一般的にアクターモデルで表現される並行性は表現できない。一方、アクターモデルはラムダ計算のすべてとそれ以上のことを表現できる」と書いている。彼はまた、継続関数への依存や例外の欠如など、ラムダ計算から派生したSchemeの側面に対しても批判的である。^[13]

1975年から1980年にかけて、サスマン氏とスティール氏はラムダ計算、継続、末尾再帰の最適化などの高度なプログラミング概念の使用に関するアイデアの開発に取り組み、それらを一連のAIメモとして公開しました。これらのメモは総称してラムダ論文と呼ばれています。^[14]

• 1975: Scheme: 拡張ラムダ計算のインタプリタ
• 1976年: ラムダ: 究極の命令
• 1976年: ラムダ: 究極の宣言
• 1977: 「高価な手続き呼び出し」という神話の暴露、または、手続き呼び出しの実装は有害であると考えられる、または、ラムダ: 究極の GOTO
• 1978: 通訳の芸術、あるいはモジュール性複合体（第 0 部、第 1 部、第 2 部）
• 1978: RABBIT: SCHEME 用コンパイラ
• 1979: LISP ベースのプロセッサの設計、または SCHEME: LISP の方言、または有限メモリの有害性、または LAMBDA: 究極のオペコード
• 1980: LAMBDA を RENAME + GOTO として捉えるコンパイラの最適化
• 1980年: Lispベースのプロセッサの設計

Schemeは、語彙スコープを選択した最初のLisp方言でした。また、レイノルドの定義言語^{[15]以降、}第一級 継続をサポートした最初のプログラミング言語の1つでもありました。Schemeは、ガイ・スティールが貢献した姉妹言語であるCommon Lispの開発に大きな影響を与えました。 ^[16]

Scheme言語は、電気電子技術者協会（IEEE）の公式標準^[17]と、アルゴリズム言語Schemeの改訂版^報告書（RnRS ）と呼ばれる事実上の標準で標準化されています。最も広く実装されている標準はR5RS（1998）^[18]であり、新しい標準であるR6RS ^[19]は2007年に批准されました。^[20] RnRS標準の他に、Scheme実装によって追加される可能性のある追加のライブラリを含むScheme実装要求文書もあります 。