Scheme

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
Scheme
Lambda lc.svg
パラダイム マルチパラダイム
登場時期 1975年[1]
設計者 ガイ・L・スティールジェラルド・ジェイ・サスマン
型付け 強い、動的型付け
主な処理系 GaucheRacketMIT/GNU SchemeScheme 48GuileChez Scheme
影響を受けた言語 Plasma, Conniver、Planner, ALGOL 60, Lisp

Scheme(スキーム)は構文スコープを持つ LISP の方言の一つである[2]

LISP 系統の言語としては Common Lisp と並んで現在でもよく使われている。

言語仕様の小ささとその出自からプログラミングの教育分野でもよく使われている。

概要[編集]

Scheme は、マサチューセッツ工科大学の人工知能研究所においてカール・ヒューイット の設計したアクタ言語 Plasma (Planner-73) の動作を理解するために、アロンゾ・チャーチ のλ計算を基盤に持つ LISP 方言として、カール・ヒューイットの学生であったジェラルド・ジェイ・サスマンガイ・スティール によって1975年頃に設計された。

アクタを言語に導入するにあたって採用された ALGOL 60 由来の構文スコープは、状態を持つデータであるアクタ(クロージャ[3])の実現以外にも、lambda 構文を用いたλ計算[4]末尾再帰[5]の最適化に不可欠な機構であった。

また、プログラムの制御理論から当時出てきた継続[6]及びアクタ理論におけるアクタへのメッセージ渡し[7]の概念から触発された継続渡し形式[8][9]と呼ばれるプログラミング手法は以後の継続の研究に大きな影響を与えた。

歴史[編集]

MIT人工知能研究所においては以下のとおり LISP に始まるいくつかの言語が作られた。

言語 作者
1958年 LISP マッカーシー、他
1964年 Meteor ボブロウ
1969年 Convert ガズマン
1969年 Planner ヒューイット
1970年 Muddle サスマン、ヒューイット、他
1971年 Micro-Planner サスマン、他
1972年 Conniver サスマン、他
1973年 Plasma ヒューイット、他
1975年 Schemer サスマン、スティール

この中でカール・ヒューイットが設計した規則ベースの言語 Planner はあまりに複雑な機構を持っていたため実装されなかった。サスマン等はそれを使いやすい言語 Micro-PlannerConniver として実現した。

同じくカール・ヒューイットが設計したアクタ言語 PlasmaPlanner-73)も複雑な機構を持っていたため、MacLisp による実装が存在したものの、その動作の仕組みを理解するのは困難であった。サスマン及びガイ・スティールは Plasma を理解するために、不要な機能を省いた LISP 構文を持つ小さな Plasma を設計した。

上記の Plasma からその小さな Plasma の設計に至る過程は Planner から Micro-Planner 及び Conniver へ至る過程を彷彿とさせるものであったため、その言語は Planner(計画する者)及び Conniver(策略を巡らす者)の次という意味で当初 Schemer(陰謀を企てる者)と名付けられた。しかし、当時のオペレーティングシステムのファイルシステムの制限からファイル名が6文字に切られたことから Scheme という名前が使われるようになった。

機能[編集]

構文スコープ[編集]

Scheme 以前の LISP 方言では変数束縛が実行履歴を元に決定される動的スコープが採用されていたが、Scheme では変数の意味が構文的に定まるという構文スコープLISP 方言として当時初めて採用した。構文スコープは環境 の機構により実現される。

Algol 60 からの直接の影響はこの構文スコープである[10]。構文スコープは後に Scheme からの影響を受けた形で Common Lisp にも採用されたと言われる。

継続[編集]

call/cc[編集]

Schemecall-with-current-continuation(略称:call/cc)と呼ばれる[11]ピーター・ランディンやジョン・レイノルズに始まる脱出オペレータ[12]の命令を提供する。

言語仕様[編集]

Scheme の言語仕様はIEEEによって公式に定められ[13]、その仕様は「Revisedn Report on the Algorithmic Language Scheme」(RnRS)と呼ばれている。現在広く実装されているものは改訂第五版に当たるR5RS(1998年)である。

LISP 系言語は SchemeCommon Lisp を二大潮流とするが、提案された機能を原則全て導入する Common Lisp に対して、成員の全員一致を原則とする Scheme という特徴を持っている。

なお、2007年9月に「The Revised6 Report on the Algorithmic Language Scheme」 (R6RS)[14] が成立した。4部構成となり、R5RSに比べおよそ3倍の文章量となった。R5RSまでは小さな言語仕様に対してのこだわりが見られたが、UNICODEサポート等の実用的な言語として必要な要素が盛り込まれている点が特徴的である。しかし、多くの機能が盛り込まれたにもかかわらず細部の練りこみが不十分であるといった批判もあり、非公式にR5RSを拡張する形でERR5RS(Extended R5RS Scheme)という規格を検討する党派も現れている。

2009年8月、Scheme言語運営委員会は、Schemeを大規模バージョンと、大規模バージョンのサブセットとなる小さな言語仕様の2つの言語に分割することを推奨する意向を発表した[15]

2013年7月、「The Revised7 Report on the Algorithmic Language Scheme」 (R7RS)[16] (small language)が成立した。

仕様の決定[編集]

実装[編集]

Schemeの仕様書はR5RSだと50ページにも満たないため、かなりの数の実装が存在する。

  • Bigloo - 高速な実行ファイルを作るコンパイラ。
  • BiwaScheme - JavaScriptによる実装。ブラウザ上で動作する。
  • Chez Scheme - 商用の高速な実装。
  • Chicken - 可搬性の高い実用的コンパイラ。
  • Gauche - インタプリタ。多言語への対応、STklosを発展させた(メタ)オブジェクトシステムを持つ。
  • GNU Guile - GNUの公式な拡張用言語。Schemeを元にしている。
  • HScheme
  • IronScheme
  • Jscheme
  • jakld - Javaアプリケーション組み込み用のLISPドライバ
  • Kawa - GNUプロジェクトのひとつ。SchemeプログラムをJava仮想機械用にコンパイル可能。
  • Larceny - IA32/SPARCのネイティブコードを出力。IEEE/ANSI,R5RS,ERR5RS,R6RS準拠。
  • LispMe - Palm OS 用の実装。無料。
  • MIT Scheme - x86アーキテクチャ用のScheme実装。無料。
  • Mosh - R6RS準拠の高速なインタプリタFFI、ソケットなどの拡張も。
  • Ocs
  • PocketScheme - WindowsCE 用の実装。
  • Racket - 旧称 PLT Scheme。教育用の豪華な開発環境、柔軟なシステムで広く使われる。
  • QScheme
  • rhizome/pi
  • Scheme48
  • SECDR-Scheme - Lispkit Lisp拡張による(並列)Scheme。
  • SigScheme - アプリケーション組み込みを目的としたR5RS準拠の実装。uimで使用されている。
  • SISC - Second Interpreter of Scheme CodeJava仮想機械上で動作するR5RS準拠の実装。JavaオブジェクトをScheme上から利用することが可能。
  • TinyScheme - 非常に小さい実装。Zaurusなどでも走る。正規表現やソケット通信もサポート。
  • Vx-scheme - VxWorks用の実装。
  • Ypsilon - R6RSに準拠するリアルタイムアプリケーション向けの実装。

SRFI[編集]

Scheme は言語機能を必要十分の最低限まで単純化することを目指した言語である。そのため仕様書が簡素な反面、実用に際して各種のライブラリが乱立し、移植性が問題になっていた。そこで実装間の統一をとるため、コミュニティ内の議論を集約しているのが「Scheme Requests for Implementation (SRFI)」である。SRFIではライブラリ仕様、言語拡張仕様などがインデックス化されており、SRFI準拠の実装系は「Xに準拠」といった形で利用者の便宜を図ることができる。

なお、Schemeでは言語機能とライブラリ機能は分けて考えられているため、SRFIとScheme言語仕様のコミュニティは原則分離している。

出典[編集]

ラムダ論文一覧[編集]

Scheme が発表された一連の論文は、ラムダ論文と呼ばれている[17]

題名
1975年 Scheme: An Interpreter for Extended Lambda Calculus
1976年 Lambda: The Ultimate Imperative
1976年 Lambda: The Ultimate Declarative
1977年 Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO
1978年 The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two)
1978年 RABBIT: A Compiler for SCHEME
1979年 Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode
1980年 Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO
1980年 Design of a Lisp-based Processor

参考文献[編集]

  1. ガイ・スティール・ジュニア (1996), Scheme 過去◇現在◇未来 前編・後編, http://www010.upp.so-net.ne.jp/okshirai/scheme-20070402222203.txt 
  2. ガイ・スティール・ジュニア (2006), The History of Scheme, http://deptinfo.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf 
  3. ジェラルド・サスマン、ガイ・スティール・ジュニア (1975), Scheme: An Interpreter for Extended Lambda Calculus, ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-349.pdf 
  4. ジェラルド・サスマン、ガイ・スティール・ジュニア (1976), Lambda: The Ultimate Imperative, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-353.pdf 
  5. ガイ・スティール・ジュニア (1976), Lambda: The Ultimate Declarative, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf 
  6. ガイ・スティール・ジュニア (1977), Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf 
  7. ジェラルド・サスマン、ガイ・スティール・ジュニア (1978), The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two), http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf 
  8. ガイ・スティール・ジュニア (1978), Rabbit: A Compiler for Scheme, ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf 
  9. ジェラルド・サスマン、ガイ・スティール・ジュニア (1979), Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-514.pdf 
  10. カール・ヒューイット (1967), PLANNER A Language for Proving Theorem, http://dspace.mit.edu/bitstream/handle/1721.1/6144/AIM-137.pdf 
  11. ジェラルド・サスマン、テリー・ビノグラード (1970), Micro-Planner Reference Manual, http://dspace.mit.edu/bitstream/handle/1721.1/5833/AIM-203.pdf 
  12. V. マクダモット、ジェラルド・サスマン (1972), The CONNIVER Reference Manual, http://dspace.mit.edu/bitstream/handle/1721.1/6204/AIM-259a.pdf 
  13. アイリーン・グライフ、カール・ヒューイット (1974), Actor Semantics of PLANNER-73, http://dspace.mit.edu/bitstream/handle/1721.1/41116/AI_WP_081.pdf 
  14. ピーター・J・ランディン (1965), A Generalization of Jumps and Labels, http://mirrors.csl.sri.com/www.brics.dk/%257Ehosc/local/HOSC-11-2-pp125-143.pdf 
  15. ヘイヨー・シーレッケ (1998), An Introduction to Landin’s “A Generalization of Jumps and Labels”, http://cs.au.dk/~hosc/local/HOSC-11-2-pp117-123.pdf 
  16. ジョン・C・レイノルズ (1972), Denitional Interpreters for Higher-Order Programming Languages, http://cs.au.dk/~hosc/local/HOSC-11-4-pp363-397.pdf 
  17. ジョエル・モーゼス (1970), The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem, http://dspace.mit.edu/bitstream/handle/1721.1/5854/AIM-199.pdf  和訳

脚注[編集]

  1. ^ Gerald J. SussmanGuy L. Steele Jr. (December 1975). “Scheme: An interpreter for extended lambda calculus”. MIT AI Memo 349 (Massachusetts Institute of Technology). 
  2. ^ Scheme は構文スコープを持つ初めての LISP 方言である。
  3. ^ : closure
  4. ^ : lambda calculus
  5. ^ : tail-recursion
  6. ^ : continuation
  7. ^ : message passing
  8. ^ : continuation passing style、CPS
  9. ^ 継続渡し形式は一連のλ論文において導入された。ただし、体系として確立されてはいないものの、同様の手法は「John C. Reynolds (1972), Denitional Interpreters for Higher-Order Programming Languages, http://cs.au.dk/~hosc/local/HOSC-11-4-pp363-397.pdf 」にもみられる。
  10. ^ Scheme 過去◇現在◇未来 前編」より
  11. ^ 当初は CATCH という名称であった。
  12. ^ : escape operator
  13. ^ 1178-1990 (Reaff 2008) IEEE Standard for the Scheme Programming Language. IEEE part number STDPD14209, unanimously reaffirmed at a meeting of the IEEE-SA Standards Board Standards Review Committee (RevCom), March 26, 2008 (item 6.3 on minutes), reaffirmation minutes accessed October 2009. NOTE: this document is only available for purchase from IEEE and is not available online at the time of writing (2009).
  14. ^ Michael Sperber ほか. “The Revised6 Report on the Algorithmic Language Scheme” (英語). 2009年2月2日閲覧。
  15. ^ Position statement” (英語). 2013年12月16日閲覧。
  16. ^ Scheme Working Groups” (英語). 2013年12月16日閲覧。
  17. ^ Online version of the Lambda Papers(PDF文書)

関連項目[編集]

外部リンク[編集]