出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/11/12 08:09 UTC 版)
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（スキーム）はコンピュータ・プログラミング言語 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]、本来意図していた挙動は、静的スコープであった。動的スコープは、意図していたものではなかったため、FUNARG機構を導入して対処されたが、これは言語のスコープルールを静的にするのではなく、クロージャーを意図したように機能させるための部分的な修正であった。なお、動的スコープ自体は有用性が認められたため後のLispにも機能として残ることとなったが、これらの対処について、1962年の LISP 1.5 も1960年代後半の Maclisp もスコープの変数束縛に関しては色々と不完全だったとする意見もある。[4]
ガイ・スティールは、1962年の LISP 1.5 からの変更点として最初に静的スコープの採用と実装を挙げており、サスマンが静的スコープを実装したALGOL 60に関して持っていた興味からによるもので、ALGOLの直接の影響だと述べている。[5] なお、Scheme開発のきっかけとなったPlasmaも挙動としてはレキシカルスコープといえるが、Plasmaからの影響についての記述はない。
funarg問題としてLISPの初期から既に認識され議論されていたことでもあり、ALGOLとの融合が試みられた1964年のLISP 2でも静的スコープが採用されていたり[6]と、必ずしも1975年のSchemeから始まったとは言えないが、Scheme以後のLISP方言に静的スコープが広まったのはSchemeからの影響と言ってよく、殊にCommon Lispは特筆される。
call-with-current-continuationScheme はcall-with-current-continuation（略称：call/cc）と呼ばれる[注釈 10]ピーター・ランディンやジョン・レイノルズに始まる脱出オペレータ[注釈 11]の命令を提供する。
Scheme の言語仕様はIEEEによって公式に定められ[7]、その仕様は「Revisedn Report on the Algorithmic Language Scheme (RnRS)」と呼ばれている。2016年現在広く実装されているものは改訂第五版に当たるR5RS（1998年）である。
なお、2007年9月に「The Revised6 Report on the Algorithmic Language Scheme (R6RS)」[8]が成立した。4部構成となり、R5RSに比べおよそ3倍の文章量となった。R5RSまでは小さな言語仕様に対してのこだわりが見られたが、Unicode サポート等の実用的な言語として必要な要素が盛り込まれている点が特徴的である。しかし、多くの機能が盛り込まれたにもかかわらず細部の練りこみが不十分であるといった批判もあり、非公式にR5RSを拡張する形でERR5RS (Extended R5RS Scheme) という規格を検討する党派も現れている。
2009年8月、Scheme 言語運営委員会は、Scheme を大規模バージョンと、大規模バージョンのサブセットとなる小さな言語仕様のふたつの言語に分割することを推奨する意向を発表した[9]。
2013年7月、「The Revised7 Report on the Algorithmic Language Scheme (R7RS)」[10] (small language) が成立した。
 |
この節の加筆が望まれています。
|
Scheme の仕様書はR5RSだと50ページにも満たないため、かなりの数の実装が存在する。
Scheme は言語機能を必要十分の最低限まで単純化することを目指した言語である。そのため仕様書が簡素な反面、実用に際して各種のライブラリが乱立し、移植性が問題になっていた。そこで実装間の統一をとるため、コミュニティ内の議論を集約しているのが「Scheme Requests for Implementation (SRFI)」である。SRFI ではライブラリ仕様、言語拡張仕様などがインデックス化されており、SRFI 準拠の実装系は「◯◯に準拠」といった形で利用者の便宜を図ることができる。
なお、Scheme では言語機能とライブラリ機能は分けて考えられているため、SRFI と Scheme 言語仕様のコミュニティは原則分離している。
Scheme はしばしば他のアプリケーションの拡張用言語として使われる。代表的なアプリケーションには以下のようなものがある。
より専門的な応用としては、映画ファイナルファンタジーのために3Dレンダリングエンジンに Scheme インタプリタを組み込んだ例[11]や、リトルウイングのピンボールコンストラクションシステムの記述に Scheme を使った例[12]がある。
Android 用の App Inventor では、Scheme コンパイラである Kawa を使ってJava仮想マシン用のバイトコードを生成している。
Scheme が発表された一連の論文は、ラムダ論文と呼ばれている[13]。
| 年 | 題名 |
|---|---|
| 1975年 | Scheme: An Interpreter for Extended Lambda Calculus[14][15] |
| 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 |
CATCH という名称であった。 出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/21 01:56 UTC 版)
Scheme での実装を以下に示す。 (require-extension srfi-1) ; 実装依存。SRFI-1 と言うライブラリを用いる。(define (selection-sort ls) (let loop ((ls ls) (acc '())) (if (null? ls) (reverse acc) (let ((x (apply min ls))) (loop (remove (lambda (y) (= y x)) ls) (cons x acc)))))) 表 話 編 歴 ソート 理論計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版） 交換ソートバブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート 選択ソート選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート 挿入ソート挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート マージソートマージソート 多層マージソート ストランドソート 非比較ソート基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート 並行ソートバイトニックソート バッチャー奇偶マージソート シェアソート 混成ソートティムソート イントロソート Jソート アンシャッフルソート（英語版） その他トポロジカルソート パンケーキソート スパゲティソート 非効率的/ユーモラスソートボゴソート ストゥージソート スリープソート エラーソート
※この「Scheme」の解説は、「選択ソート」の解説の一部です。
「Scheme」を含む「選択ソート」の記事については、「選択ソート」の概要を参照ください。
