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

プログラミング言語Schemeの歴史は、20世紀後半におけるLisp系言語の初期メンバーの開発から始まります。Schemeの設計・開発期間中、言語設計者のGuy L. SteeleとGerald Jay Sussmanは、マサチューセッツ工科大学（MIT）のAIメモシリーズ「ラムダ論文」（1975～1980年）を発表しました。この論文は、Schemeの人気を高め、1990年以降の標準化の時代へとつながりました。Schemeの歴史の多くは、開発者自身によって文書化されています。[1]

先史時代

Schemeの開発は、互いに全く異なる2つの先行言語から大きな影響を受けました。LispはSchemeの一般的な意味論と構文を提供し、ALGOLは語彙スコープとブロック構造を提供しました。SchemeはLispの方言ですが、Lispは進化を遂げてきました。Schemeの元となったLisp方言は、当時は主流でしたが、現代のLispとは全く異なります。Schemeは、Common Lisp、Scheme、ISLisp、EuLisp、XLisp、AutoLispを含む大規模なLisp言語ファミリーに属しています。

Lisp

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

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

Lispの最初の実装は、Steve RussellによってIBM 704上で行われました。彼はMcCarthyの論文を読み、彼が記述したeval関数を機械語でコーディングしました。Lispでリストの先頭要素と末尾要素を表すために使用される、馴染みのある（しかし初心者には分かりにくい） CARとCDRという名前は、 IBM 704アセンブリ言語の2つのコマンド、「アドレスレジスタの内容」と「デクリメントレジスタの内容」から派生したものです。これらのコマンドはそれぞれ、 36ビットのIBM 704命令語の各セグメントに対応する15ビットレジスタの内容を返します。

Lispで書かれた最初の完全なLispコンパイラは、1962年にMITのティム・ハートとマイク・レビンによって実装されました。[3]このコンパイラは、コンパイルされた関数と解釈された関数を自由に混在させることができる増分コンパイルのLispモデルを導入しました。

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

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

アルゴル

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

ALGOLはブロック構造とレキシカルスコープを導入しました。また、ALGOLは、手続きや関数の実行中に仮パラメータの代わりに作業パラメータを表す式をテキストで置換する必要があるように定義されていたため、その難解さで悪名高いものでした。ALGOLの実装者は、サンクと呼ばれるメカニズムを開発しました。これは作業パラメータのコンテキストを捕捉し、手続きや関数の実行中に評価できるようにしました。

俳優モデル、カール・ヒューイットとSchemeの誕生

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

1972年11月、ヒューイットと彼の学生たちは、Plannerの問題を解決するために、アクター計算モデルを発明しました。 [9] アクターの部分的な実装はPlanner-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]以降、第一級 継続をサポートした最初のプログラミング言語の一つでもありました。Schemeは、姉妹言語であるCommon Lispの開発に大きな影響を与え、Guy Steeleもその開発に貢献しました[16] 。

標準化

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

タイムライン

Lisp方言のタイムライン
1958 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2020
 LISP 1、1.5、LISP 2 （廃止）
 マックリスプ
 インターリスプ
 MDL
 Lispマシン Lisp
 スキーム  R5RS  R6RS  R7RS 小型
 ゼロ
 ZIL (Zork 実装言語)
 フランツ・リスプ
 ミューリスプ
 コモンリスプ  ANSI規格
 ル・リスプ
 MITスキーム
 XLISP
 T
 シェ・スキーム
 Emacs Lisp
 オートリスプ
 ピコリスプ
 ギャンビット
 ユーリスプ
 ISLISP
 オープンリスプ
 PLTスキーム  ラケット
 ニューリスプ
 GNUガイル
 ビジュアルLISP
 クロージュア
 アーク
 LFE
 ハイ

参考文献

  1. ^ Steele, Guy (2006). 「Schemeの歴史」(PDF) .サン・マイクロシステムズ研究所. 2023年3月2日時点のオリジナルよりアーカイブ。 2023年4月5日閲覧。{{cite web}}: CS1 maint: bot: 元のURLステータス不明（リンク）
  2. ^ マッカーシー、ジョン. 「記号式の再帰関数と機械による計算、パートI」. 2013年10月4日時点のオリジナルよりアーカイブ。 2006年10月13日閲覧。
  3. ^ ハート、ティム、レビン、マイク。「AIメモ39、新しいコンパイラ」（PDF） 。 2017年7月6日時点のオリジナル（PDF）からアーカイブ。 2006年10月13日閲覧。
  4. ^ マッカーシー, ジョン; エイブラハムズ, ポール W.; エドワーズ, ダニエル J.; ハート, ティモシー P.; レビン, マイケル I. (1985). LISP 1.5 プログラマーズ・マニュアル. MIT プレス. ISBN 978-0-262-13011-0。
  5. ^ "Maclisp Reference Manual". 1979年3月3日. 2007年12月14日時点のオリジナルよりアーカイブ。
  6. ^ Hurley, Peter J. (1990年10月18日). 「TOPSの歴史、あるいは高速ACにおける人生」.ニュースグループ: alt.folklore.computers. Usenet:  84950@tut.cis.ohio-state.edu. PDP-6プロジェクトは1963年初頭に24ビットマシンとして開始されました。LISPに対応するために、設計目標である36ビットマシンへと拡張されました。
  7. ^ Hoare, Tony (1973年12月). プログラミング言語設計のヒント(PDF) . p. 27.(この発言は、最初の ALGOL 60コンパイラの実装にも関わったEdsger W. Dijkstra の 発言だと誤って解釈されることがあります。)
  8. ^ ヘイズ、パット (1974). 「表現理論におけるいくつかの問題と非問題」.人工知能と行動シミュレーション研究協会.
  9. ^ Hewitt, Carl ; Bishop, Peter ; Steiger, Richard (1973). 「人工知能のための普遍的なモジュラーアクター形式論」 IJCAI. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  10. ^ ab Sussman, Gerald Jay ; Steele Jr., Guy L. (1998年12月). 「Scheme再考に関する最初の報告書」(PDF) . Higher-Order and Symbolic Computation . 11 (4): 399– 404. doi :10.1023/A:1010079421970. ISSN  1388-3690. S2CID 7704398. 2006年6月15日時点の オリジナル(PDF)からアーカイブ。 2006年6月19日閲覧。
  11. ^ Hewitt, Carl (1976年12月). 「制御構造をメッセージ伝達のパターンとして見る」. AIメモ410 .
  12. ^ Hewitt, Carl (1977年6月). 「制御構造をメッセージ伝達のパターンとして捉える」. Journal of Artificial Intelligence . 8 (3): 323– 364. doi :10.1016/0004-3702(77)90033-9. hdl : 1721.1/6272 .
  13. ^ Hewitt, Carl (2009). 「ActorScript: クライアントクラウドコンピューティングにおけるローカルおよび非ローカル同時実行性の産業用統合」. arXiv : 0907.3330 [cs.PL].
  14. ^ 「Lambda Papersのオンライン版」. scheme.org . 2025年. 2025年12月4日閲覧。
  15. ^ レイノルズ、ジョン (1972). 「高階プログラミング言語のための定義インタープリタ」ACM カンファレンスプロシーディングス. Association for Computing Machinery.
  16. ^ 「Common Lisp Hyperspec – 1.1.2 History」LispWorks . 2005年. 2018年12月2日閲覧。
  17. ^ 1178-1990 (R1995) Schemeプログラミング言語のIEEE標準
  18. ^ リチャード・ケルシー、ウィリアム・クリンガー、ジョナサン・リース他 (1998年8月). 「アルゴリズム言語Schemeに関する改訂報告書」 .高階および記号計算. 11 (1): 7– 105. doi :10.1023/A:1010051815785.
  19. ^ Sperber, Michael; Dybvig, R. Kent; Flatt, Matthew; Van Straaten, Anton; Findler, Robby; Matthews, Jacob (2009年8月). 「アルゴリズム言語Schemeに関する改訂報告書」. Journal of Functional Programming . 19 (S1): 1– 301. CiteSeerX 10.1.1.154.5197 . doi :10.1017/S0956796809990074. S2CID  62724224. 
  20. ^ 「R6RS批准投票結果」。
「https://en.wikipedia.org/w/index.php?title=History_of_the_Scheme_programming_language&oldid=1325692085」より取得