Scheme
Scheme(スキーム)はコンピュータ・プログラミング言語 LISPの方言のひとつで、静的スコープなどが特徴である。仕様(2017年現在、改7版まで存在する)を指すこともあれば、実装を指すこともある。Schemeにより、LISP方言に静的スコープが広められた。
Schemeのロゴ | |
パラダイム | 関数型プログラミング、手続き型プログラミング、メタプログラミング、命令型プログラミング |
---|---|
登場時期 | 1975年 |
設計者 | ガイ・L・スティール・ジュニア、ジェラルド・ジェイ・サスマン |
最新リリース | R7RS-small / 2013[1] |
型付け | 強い、動的型付け |
主な処理系 | Gauche、Racket、MIT/GNU Scheme、Scheme 48、Guile、Chez Scheme |
影響を受けた言語 | LISP、ALGOL、MDL (プログラミング言語) |
影響を与えた言語 | Clojure、Common Lisp、Dylan、Egison、EuLisp、Haskell、Hop、JavaScript、Julia、Lua、MultiLisp、Python、R、Racket、Ruby、Rust[2]、S、Scala、T |
ウェブサイト |
www |
拡張子 | scm、ss |
概要
編集Schemeは、MIT AIラボにて、ジェラルド・ジェイ・サスマンとガイ・スティール・ジュニアによって1975年頃に基本的な設計がなされた。動機は、カール・ヒューイットの提案によるエレガントな並行計算モデル「アクター」と、同じくその言語のPLASMA(Planner-73)を理解するためであった。
静的スコープ(ALGOL由来とされる[注釈 1])は、状態を持つデータであるアクタ(クロージャ[注釈 2])の実現以外にも、lambda
構文を用いたλ計算[注釈 3]や末尾再帰[注釈 4]の最適化に不可欠な機構であった。
また、プログラムの制御理論から当時出てきた継続[注釈 5]及びアクタ理論におけるアクタへのメッセージ渡し[注釈 6]の概念から触発された継続渡し形式[注釈 7][注釈 8]と呼ばれるプログラミング手法は以後の継続の研究に大きな影響を与えた。
歴史
編集MIT人工知能研究所においては以下のとおりLISPに始まるいくつかの言語が作られた。
年 | 言語 | 作者 |
---|---|---|
1960年 | LISP | マッカーシー、他 |
1964年 | Meteor | ボブロウ |
1969年 | Convert | ガズマン |
1969年 | Planner | ヒューイット |
1970年 | Muddle | サスマン、ヒューイット、他 |
1971年 | Micro-Planner | サスマン、他 |
1972年 | Conniver | サスマン、他 |
1973年 | Plasma | ヒューイット、他 |
1975年 | Schemer | サスマン、スティール |
この中でカール・ヒューイットが設計した規則ベースの言語 Planner はあまりに複雑な機構を持っていたため当初設計された全機能の実装は困難であり[注釈 9]、サスマン等はそれをサブセット言語の Micro-Planner として実現し、さらには、 Planner の流れを汲んだ独自言語として Conniver を作成した。
同じくカール・ヒューイットが設計したアクタ言語 Plasma (Planner-73) も複雑な機構を持っていたため、MacLisp による実装が存在したものの、その動作の仕組みを理解するのは困難であった。サスマン及びガイ・スティール・ジュニアは Plasma を理解するために、不要な機能を省いた LISP 構文を持つ小さな Plasma を設計した。
上記の Plasma からその小さな Plasma の設計に至る過程は Planner から Micro-Planner 及び Conniver へ至る過程を彷彿とさせるものであったため、その言語は Planner(計画する者)及び Conniver(策略を巡らす者)の次という意味で当初 Schemer(陰謀を企てる者)と名付けられた。しかし、当時のオペレーティングシステムのファイルシステムの制限からファイル名が6文字に切られたことから Scheme という名前が使われるようになった。
機能
編集静的スコープ
編集マッカーシーが1979年に回顧で、1960年の最初のLISP(LISP I)に関して「In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.」と書いているように[3]、計算理論的にも静的スコープが本来は「正当」であり、動的スコープは、言ってしまえばある種の安易なインタプリタの実装手法が招く「バグ」である(有用なことも多いが)。
ガイ・スティールは、1962年の LISP 1.5 からの変更点として最初に静的スコープの採用と実装を挙げており、サスマンが静的スコープを実装したALGOL 60に関して持っていた興味からによるもので、ALGOLの直接の影響だと述べている。[4]
ただし、1962年の LISP 1.5 も1960年代後半の Maclisp もスコープの変数束縛に関しては色々と不完全だった。[5]
FUNARG問題としてLISPの初期から既に認識され議論されていたことでもあり、必ずしも1975年のSchemeから始まったとは言えないが、Scheme以後のLISP方言に静的スコープが広まったのはSchemeからの影響と言ってよく、殊にCommon Lispは特筆される。
継続
編集call-with-current-continuation
編集
Scheme はcall-with-current-continuation
(略称:call/cc
)と呼ばれる[注釈 10]ピーター・ランディンやジョン・レイノルズに始まる脱出オペレータ[注釈 11]の命令を提供する。
言語仕様
編集Scheme の言語仕様はIEEEによって公式に定められ[6]、その仕様は「Revisedn Report on the Algorithmic Language Scheme (RnRS)」と呼ばれている。2016年現在広く実装されているものは改訂第五版に当たるR5RS(1998年)である。
なお、2007年9月に「The Revised6 Report on the Algorithmic Language Scheme (R6RS)」[7]が成立した。4部構成となり、R5RSに比べおよそ3倍の文章量となった。R5RSまでは小さな言語仕様に対してのこだわりが見られたが、Unicode サポート等の実用的な言語として必要な要素が盛り込まれている点が特徴的である。しかし、多くの機能が盛り込まれたにもかかわらず細部の練りこみが不十分であるといった批判もあり、非公式にR5RSを拡張する形でERR5RS (Extended R5RS Scheme) という規格を検討する党派も現れている。
2009年8月、Scheme 言語運営委員会は、Scheme を大規模バージョンと、大規模バージョンのサブセットとなる小さな言語仕様のふたつの言語に分割することを推奨する意向を発表した[8]。
2013年7月、「The Revised7 Report on the Algorithmic Language Scheme (R7RS)」[9] (small language) が成立した。
仕様の決定
編集この節の加筆が望まれています。 |
実装
編集Scheme の仕様書はR5RSだと50ページにも満たないため、かなりの数の実装が存在する。
- Bigloo - 高速な実行ファイルを作るコンパイラ。
- BiwaScheme - JavaScript による実装。ブラウザ上で動作する。
- Chez Scheme - もと商用だったが、現在はオープンソースの高速な実装。
- Chicken - 可搬性の高い実用的コンパイラ。
- Gauche - インタプリタ。多言語への対応、STklos を発展させた(メタ)オブジェクトシステムを持つ。
- Gambit(英語版) - Schemeインタプリタ及びScheme→Cコンパイラ。
- GNU Guile - GNU の公式な拡張用言語。Scheme を元にしている。
- HScheme
- IronScheme
- Jscheme
- JAKLD - Java アプリケーション組み込み用のLISPドライバ
- Kawa - GNUプロジェクトのひとつ。Scheme プログラムを Java 仮想機械用にコンパイル可能。
- Larceny - IA-32、SPARC の機械語を出力。IEEE/ANSI、R5RS、ERR5RS, R6RS準拠。
- LispMe - Palm OS 用の実装。無料。
- MIT Scheme - x86アーキテクチャ用の Scheme 実装。無料。
- Mosh - R6RS準拠の高速なインタプリタFFI、ソケットなどの拡張も。
- Ocs
- PocketScheme - Windows CE 用の実装。
- Racket - 旧称 PLT Scheme。教育用の豪華な開発環境、柔軟なシステムで広く使われる。
- QScheme
- rhizome/pi
- Scheme48
- SECDR-Scheme - Lispkit Lisp 拡張による(並列)Scheme。
- SigScheme - アプリケーション組み込みを目的としたR5RS準拠の実装。uimで使用されている。
- SISC - Second Interpreter of Scheme Code。Java 仮想機械上で動作するR5RS準拠の実装。Java オブジェクトを Scheme 上から利用することが可能。
- TinyScheme - 非常に小さい実装。Zaurusなどでも走る。正規表現やソケット通信もサポート。
- Vx-scheme - VxWorks 用の実装。
- Ypsilon - R6RSに準拠するリアルタイムアプリケーション向けの実装。
SRFI(サーフィ)
編集Scheme は言語機能を必要十分の最低限まで単純化することを目指した言語である。そのため仕様書が簡素な反面、実用に際して各種のライブラリが乱立し、移植性が問題になっていた。そこで実装間の統一をとるため、コミュニティ内の議論を集約しているのが「Scheme Requests for Implementation (SRFI)」である。SRFI ではライブラリ仕様、言語拡張仕様などがインデックス化されており、SRFI 準拠の実装系は「◯◯に準拠」といった形で利用者の便宜を図ることができる。
なお、Scheme では言語機能とライブラリ機能は分けて考えられているため、SRFI と Scheme 言語仕様のコミュニティは原則分離している。
応用
編集Scheme はしばしば他のアプリケーションの拡張用言語として使われる。代表的なアプリケーションには以下のようなものがある。
より専門的な応用としては、映画ファイナルファンタジーのために3Dレンダリングエンジンに Scheme インタプリタを組み込んだ例[10]や、リトルウイングのピンボールコンストラクションシステムの記述に Scheme を使った例[11]がある。
Android 用の App Inventor では、Scheme コンパイラである Kawa を使ってJava仮想マシン用のバイトコードを生成している。
出典
編集ラムダ論文一覧
編集Scheme が発表された一連の論文は、ラムダ論文と呼ばれている[12]。
年 | 題名 |
---|---|
1975年 | Scheme: An Interpreter for Extended Lambda Calculus[13][14] |
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 |
参考文献
編集- ガイ・スティール・ジュニア (1996), Scheme 過去◇現在◇未来 前編・後編
- ガイ・スティール・ジュニア (2006), The History of Scheme
- ジェラルド・サスマン、ガイ・スティール・ジュニア (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
- カール・ヒューイット (1967), PLANNER A Language for Proving Theorem
- ジェラルド・サスマン、テリー・ビノグラード (1970), Micro-Planner Reference Manual
- V・マクダモット、ジェラルド・サスマン (1972), The CONNIVER Reference Manual
- アイリーン・グライフ、カール・ヒューイット (1974), Actor Semantics of PLANNER-73
- ピーター・J・ランディン (1965), A Generalization of Jumps and Labels
- ヘイヨー・シーレッケ (1998), An Introduction to Landin’s “A Generalization of Jumps and Labels”
- ジョン・C・レイノルズ (1972), Denitional Interpreters for Higher-Order Programming Languages
- ジョエル・モーゼス (1970), The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem 和訳
脚注
編集注釈
編集- ^ 元々のALGOLには関数引数等が無いためFUNARG問題なども無く、静的スコープの歴史としてALGOLをあまり強調する意味は無い。
- ^ 英: closure
- ^ 英: lambda calculus
- ^ 英: tail-recursion
- ^ 英: continuation
- ^ 英: message passing
- ^ 英: continuation passing style、CPS
- ^ 継続渡し形式は一連のλ論文において導入された。ただし、体系として確立されてはいないものの、同様の手法は「John C. Reynolds (1972), Denitional Interpreters for Higher-Order Programming Languages」にもみられる。
- ^ 後の完全な Planner の実装として、エジンバラ大学の Julian Davies が POP-2 で実装した Popler がある。
- ^ 当初は
CATCH
という名称であった。 - ^ 英: escape operator
出典
編集- ^ 出典URL: https://small.r7rs.org/
- ^ “Influences - The Rust Reference”. The Rust Reference. 2023年4月18日閲覧。
- ^ “From LISP 1 to LISP 1.5”. www-formal.stanford.edu. 8 April 2024閲覧。
- ^ 「Scheme 過去◇現在◇未来 前編」『bit』(共立出版)Vol. 28, No.4(1996年4月号) pp. 4~9
- ^ Baker, Henry G. (July 1978). “Shallow binding in Lisp 1.5”. Commun. ACM (New York, NY, USA: Association for Computing Machinery) 21 (7): 565–569. doi:10.1145/359545.359566. ISSN 0001-0782 .
- ^ 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).
- ^ Michael Sperber ほか. “The Revised6 Report on the Algorithmic Language Scheme” (英語). 2009年2月2日閲覧。
- ^ “Position statement” (英語). 2013年12月16日閲覧。
- ^ “Scheme Working Groups” (英語). 2013年12月16日閲覧。
- ^ 川合史朗 (2002年10月). “Gluing Things Together - Scheme in the Real-time CG Content Production”. 2014年6月20日閲覧。
- ^ 藤田善勝. “YPSILON”. 2014年6月20日閲覧。
- ^ Online version of the Lambda Papers (PDF)
- ^ Sussman, Gerald Jay; Steele, Guy Lewis (1975). Scheme: An Interpreter for Extended Lambda Calculus (Report). Massachusetts Institute of Technology. hdl:1721.1/5794。
- ^ Sussman, Gerald Jay; Steele Jr, Guy L (1998). “Scheme: A interpreter for extended lambda calculus”. Higher-Order and Symbolic Computation (Springer) 11 (4): 405–439. doi:10.1023/A:1010035624696 .
関連項目
編集- アクターモデル
- 継続
- 末尾再帰
- SRFI
- 計算機プログラムの構造と解釈 - Scheme を用いた計算機科学分野の古典的な教科書。