Ggtkuk

Scheme
	; Schemeのロゴ;
パラダイム	; マルチパラダイム;
登場時期	; 1975年;
設計者	; ガイ・L・スティール・ジュニア、ジェラルド・ジェイ・サスマン;
最新リリース	; R7RS /
型付け	; 強い、動的型付け;
主な処理系	; Gauche、Racket、MIT/GNU Scheme、Scheme 48、Guile、Chez Scheme;
影響を受けた言語	; Plasma、Conniver、Planner、ALGOL 60、LISP;
	テンプレートを表示

この項目では、プログラミング言語について説明しています。その他の語句については「スキーム (曖昧さ回避)」、「スキーマ (曖昧さ回避)」をご覧ください。

Scheme（スキーム）はコンピュータ・プログラミング言語 Lispの方言のひとつで、静的スコープなどが特徴である。仕様（2017年現在、改7版まで存在する）を指すこともあれば、実装を指すこともある。Schemeにより、Lisp方言に静的スコープが広められた。

概要

Schemeは、MIT AIラボにて、ジェラルド・ジェイ・サスマンとガイ・スティール・ジュニアによって1975年頃に基本的な設計がなされた。動機は、カール・ヒューイットの提案によるエレガントな並行計算モデル「アクター」と、同じくその言語のPLASMA（Planner-73）を理解するためであった。

静的スコープ（ALGOL由来とされる^[2]）は、状態を持つデータであるアクタ（クロージャ^[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 はあまりに複雑な機構を持っていたため当初設計された全機能の実装は困難であり^[10]、サスマン等はそれをサブセット言語の Micro-Planner として実現し、さらには、 Planner の流れを汲んだ独自言語として Conniver を作成した。

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

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

機能

静的スコープ

詳細は「静的スコープ」を参照

「動的スコープ」も参照

マッカーシーが後に回顧で、初期のLisp（LISP 1 および LISP 1.5）に関して「In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.」と書いているように^[11]、計算理論的にも静的スコープが本来は「正当」であり、動的スコープは、言ってしまえばある種の安易なインタプリタの実装手法が招く「バグ」である（有用なことも多いが）。

ガイ・スティールは、LISP 1.5 からの変更点として最初に静的スコープの採用と実装を挙げており、サスマンがAlgolに関して持っていた興味からによるもので、Algolの直接の影響だと述べている。^[12]

「FUNARG問題」（en:Funarg problem）としてLISPの初期から既に認識され議論されていたことでもあり、必ずしもSchemeから始まったとは言えないが、Scheme以後のLisp方言に静的スコープが広まったのはSchemeからの影響と言ってよく、殊にCommon Lispは特筆される。

継続

`call-with-current-continuation`

Scheme はcall-with-current-continuation（英語版）（略称：call/cc）と呼ばれる^[13]ピーター・ランディンやジョン・レイノルズに始まる脱出オペレータ^[14]の命令を提供する。

言語仕様

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

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

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

2013年7月、「The Revised⁷ Report on the Algorithmic Language Scheme (R7RS)」^[18] (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 - 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 はしばしば他のアプリケーションの拡張用言語として使われる。代表的なアプリケーションには以下のようなものがある。

GIMP の Script-Fu

uim

LilyPond

より専門的な応用としては、映画ファイナルファンタジーのために3Dレンダリングエンジンに Scheme インタプリタを組み込んだ例^[19]や、リトルウイングのピンボールコンストラクションシステムの記述に Scheme を使った例^[20]がある。

Android 用の App Inventor では、Scheme コンパイラである Kawa を使ってJava仮想マシン用のバイトコードを生成している。

出典

ラムダ論文一覧

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

年	題名
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

参考文献

ガイ・スティール・ジュニア (1996), Scheme 過去◇現在◇未来前編・後編, http://www010.upp.so-net.ne.jp/okshirai/scheme-20070402222203.txt

ガイ・スティール・ジュニア (2006), The History of Scheme, http://deptinfo.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf

ジェラルド・サスマン、ガイ・スティール・ジュニア (1975), Scheme: An Interpreter for Extended Lambda Calculus, ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-349.pdf

ジェラルド・サスマン、ガイ・スティール・ジュニア (1976), Lambda: The Ultimate Imperative, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-353.pdf

ガイ・スティール・ジュニア (1976), Lambda: The Ultimate Declarative, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf

ガイ・スティール・ジュニア (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

ジェラルド・サスマン、ガイ・スティール・ジュニア (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

ガイ・スティール・ジュニア (1978), Rabbit: A Compiler for Scheme, ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf

ジェラルド・サスマン、ガイ・スティール・ジュニア (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

カール・ヒューイット (1967), PLANNER A Language for Proving Theorem, http://dspace.mit.edu/bitstream/handle/1721.1/6144/AIM-137.pdf

ジェラルド・サスマン、テリー・ビノグラード (1970), Micro-Planner Reference Manual, http://dspace.mit.edu/bitstream/handle/1721.1/5833/AIM-203.pdf

V・マクダモット、ジェラルド・サスマン (1972), The CONNIVER Reference Manual, http://dspace.mit.edu/bitstream/handle/1721.1/6204/AIM-259a.pdf

アイリーン・グライフ、カール・ヒューイット (1974), Actor Semantics of PLANNER-73, http://dspace.mit.edu/bitstream/handle/1721.1/41116/AI_WP_081.pdf

ピーター・J・ランディン (1965), A Generalization of Jumps and Labels, http://mirrors.csl.sri.com/www.brics.dk/%257Ehosc/local/HOSC-11-2-pp125-143.pdf

ヘイヨー・シーレッケ (1998), An Introduction to Landin’s “A Generalization of Jumps and Labels”, http://cs.au.dk/~hosc/local/HOSC-11-2-pp117-123.pdf

ジョン・C・レイノルズ (1972), Denitional Interpreters for Higher-Order Programming Languages, http://cs.au.dk/~hosc/local/HOSC-11-4-pp363-397.pdf

ジョエル・モーゼス (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 和訳

脚注

^ Gerald J. Sussman、Guy L. Steele Jr. (December 1975). “Scheme: An interpreter for extended lambda calculus”. MIT AI Memo 349 (Massachusetts Institute of Technology).

^ 元々の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, http://cs.au.dk/~hosc/local/HOSC-11-4-pp363-397.pdf 」にもみられる。

^ 後の完全な Planner の実装として、エジンバラ大学の Julian Davies が POP-2 で実装した Popler がある

^ http://www-formal.stanford.edu/jmc/history/lisp/node4.html

^ 「Scheme 過去◇現在◇未来前編」『bit』（共立出版）Vol. 28, No.4（1996年4月号） pp. 4～9

^ 当初は CATCH という名称であった。

^ 英: escape operator

^ 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 Revised⁶ 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)

外部リンク

schemers.org

R6RS.org

Scheme Requests for Implementation

プログラミング言語 Scheme

R5RS

R5RS日本語版

SchemePunks

独習 Scheme 三週間

Practical Scheme

もうひとつの Scheme 入門

[1] Gerald J. Sussman、Guy L. Steele Jr. (December 1975). “Scheme: An interpreter for extended lambda calculus”. MIT AI Memo 349 (Massachusetts Institute of Technology).

[2] 元々のALGOLには関数引数等が無いためFUNARG問題なども無く、静的スコープの歴史としてALGOLをあまり強調する意味は無い。

[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] 後の完全な Planner の実装として、エジンバラ大学の Julian Davies が POP-2 で実装した Popler がある

[11] ttp://www-formal.stanford.edu/jmc/history/lisp/node4.html

[12] 「Scheme 過去◇現在◇未来前編」『bit』（共立出版）Vol. 28, No.4（1996年4月号） pp. 4～9

[13] 当初は CATCH という名称であった。

[14] 英: escape operator

[ieee1178-15] 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).

[16] Michael Sperber ほか. “The Revised⁶ Report on the Algorithmic Language Scheme” (英語). 2009年2月2日閲覧。

[17] “Position statement” (英語). 2013年12月16日閲覧。

[18] “Scheme Working Groups” (英語). 2013年12月16日閲覧。

[19] 川合史朗 (2002年10月). “Gluing Things Together - Scheme in the Real-time CG Content Production”. 2014年6月20日閲覧。

[20] 藤田善勝. “YPSILON”. 2014年6月20日閲覧。

[readscheme_lambda-21] Online version of the Lambda Papers (PDF)

搜尋此網誌

Ggtkuk

Scheme

目次

概要

歴史

機能