Scheme

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

Scheme
Schemeのロゴ
パラダイム	関数型プログラミング、手続き型プログラミング、メタプログラミング、命令型プログラミング
登場時期	1975年 (49年前) (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.scheme-reports.org
拡張子	scm、ss
テンプレートを表示

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

概要

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]、その仕様は「Revisedⁿ Report on the Algorithmic Language Scheme (RnRS)」と呼ばれている。2016年現在広く実装されているものは改訂第五版に当たるR5RS（1998年）である。

なお、2007年9月に「The Revised⁶ 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 Revised⁷ 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 はしばしば他のアプリケーションの拡張用言語として使われる。代表的なアプリケーションには以下のようなものがある。

GIMP の Script-Fu
uim
LilyPond

より専門的な応用としては、映画ファイナルファンタジーのために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 過去◇現在◇未来前編・後編, 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, https://hdl.handle.net/1721.1/6144
ジェラルド・サスマン、テリー・ビノグラード (1970), Micro-Planner Reference Manual, https://hdl.handle.net/1721.1/5833
V・マクダモット、ジェラルド・サスマン (1972), The CONNIVER Reference Manual, https://hdl.handle.net/1721.1/6204
アイリーン・グライフ、カール・ヒューイット (1974), Actor Semantics of PLANNER-73, https://hdl.handle.net/1721.1/41116
ピーター・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, https://hdl.handle.net/1721.1/5854 和訳

脚注

注釈

^ 元々の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 がある。
^ 当初は 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. 2024年4月8日閲覧。
^ 「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. https://doi.org/10.1145/359545.359566.
^ 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)
^ 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. https://www.researchgate.net/publication/227098423_Scheme_A_Interpreter_for_Extended_Lambda_Calculus.

外部リンク

ウィキブックスにScheme関連の解説書・教科書があります。

schemers.org
R6RS.org
Scheme Requests for Implementation
プログラミング言語 Scheme
R5RS
R5RS日本語版
SchemePunks
独習 Scheme 三週間
Practical Scheme
もうひとつの Scheme 入門

表話編歴 LISP系言語
言語（処理系）	AutoLISP（英語版） Clojure Common Lisp Emacs Lisp Interlisp ISLISP（英語版） LFE（英語版） LISP LISPマシン Lush Maclisp Scheme GNU Guile MIT/GNU Scheme Gauche Chicken Kawa Racket SKILL Steel Bank Common Lisp
関連項目	S式 SRFI ラムダ計算

コンピュータ・プログラミング言語

低水準言語

高水準言語

1950年代	FORTRAN ALGOL RPG COBOL
1960年代	LISP CPL BASIC PL/I APL BCPL Simula LOGO B
1970年代	Forth Pascal C Prolog Smalltalk Scheme ML AWK Ada
1980年代	C++ Objective-C Common Lisp Eiffel Erlang Perl Mathematica J
1990年代	Python Tcl Haskell Visual Basic Ruby Lua Delphi Java ECMAScript (JavaScript) PHP OCaml SuperCollider R
2000年代	C# VB.NET Scala Clojure D F# Go Nim
2010年代	Dart Ceylon Elixir Crystal Hack Swift Rust Raku Elm Julia Kotlin Zig