アルゴリズム言語Schemeに関する第五改訂報告書

RICHARD KELSEY、WILLIAM CLINGER、JONATHAN REES (編集)
H. ABELSON
N. I. ADAMS IV
D. H. BARTLEY
G. BROOKS
R. K. DYBVIG
D. P. FRIEDMAN
R. HALSTEAD
C. HANSON
C. T. HAYNES
E. KOHLBECKER
D. OXLEY
K. M. PITMAN
G. J. ROZAS
G. L. STEELE JR.
G. J. SUSSMAN
M. WAND
20 february 1998 (犬飼 大訳: 20 January 2000) (GAF05426@nifty.ne.jp)


Revised(5) Report on the Algorithmic Language Scheme

アルゴリズム言語Schemeに関する第五改訂報告書

Robert Hiebの思い出にこれを捧げる

摘要

本報告書は、プログラミング言語Schemeの定義を説明するものである。Schemeは、静的なスコープ(1)を持ち、正しく終端再帰(2)を行なうLispの一方言であり、Guy Lewis Steele Jr.とGerald Jay Sussmanによって発明された。極めて明解で単純な言語仕様を持ち、式を構成する上で例外がほとんどないことを目標として設計された。命令スタイル、関数スタイル、メッセージの引渡しスタイルを含む広範囲のプログラミングパラダイムが、Schemeによれば正確に表現できる。

「はじめに」では言語と本報告書の履歴を簡単に説明する。

最初の3章では、この言語の基本的な概念を述べ、この言語を説明し、この言語でプログラムを書く場合に使用される記法上の規約を述べる。

section とsection プログラムでは、式、プログラム、定義に関する構文と意味論を説明する。

section 標準手続きではSchemeの組み込み手続きを説明する。これにはScheme言語のデータ操作と入出力の基本手続きがすべて含まれる。

section 意味論と言語仕様には拡張BNFで書かれたSchemeの意味論と、形式記号言語を収録する。意味論と言語仕様に続いてScheme言語の使用例を示す。

最後に、参考文献をアルファベット順に収録する。

はじめに

履歴

プログラミング言語は満載した機能を特色の第一とするものではない。あとになって機能の追加が必要と判明するような弱点と制限を取り除いて設計すべきである。今日使用されるほとんどの重要なプログラミングパラダイムを取り扱うのに充分柔軟な、実用的で効率のいいプログラミング言語を作成するにあたっても、構成方法に制約がなければ極めて少数の式構成規則で充分である。それはSchemeが証明している。

Schemeはラムダ演算アルゴリズムにおけるように、手続きを第一位に(3)統合した最初のプログラミング言語のひとつであった。その結果、動的に型を生成する場合に静的スコープとブロック構造が有用であることが証明された。手続きをラムダ式とシンボルから独立させ、すべての変数に単一の静的環境を使用し、オペランドと同じ方法でオペレータの状況を評価した、初めての有力なLisp方言がSchemeであった。繰り返しを表現する場合に手続き呼び出しのみを使用することによって、終端再帰的手続き呼び出しが本質的に引数を渡すgotoであることが、Schemeでは強調されている。Schemeは、脱出手続きを第一位の状態に採用して広く使用された最初のプログラミング言語であり、以前は順次的制御構造として知られていたものがすべてそれによって統合できた。次の改定ではCommon Lispの包括的演算法に基づいて、完全数と不完全数(4)の概念が導入された。最も新しい改定版では、Schemeは名前の衝突を起こさない(5)マクロをサポートする最初のプログラミング言語となり、それによって、充分な信頼性をもってブロック構造言語の構文を拡張できるようになった。

背景

Schemeの最初の記述は1975年に書かれた[SCHEME75]。1978年にはその改定報告書が発表された[SCHEME78]。これはScheme言語の発展を説明したもので、例えばMITによる処理系は革新的なコンパイラ[RABBIT]をサポートするように更新された。1981年と1982年には、MIT、Yale、Indianaの各大学での授業のためにそれぞれ異なるSchemeを使用するという、3つの別々のプロジェクトが開始した[REES82]、[MITSCHEME]、[SCHEME311]。1984年には、Schemeを使用したコンピュータ科学入門の教科書が出版された[SICP]。

Schemeがさらに普及するにしたがって、学生も研究者も、異なる場所で書かれたコードを理解するのが困難と感ずるまでに各種方言への分岐が始まった。1984年10月には、より良く、さらに広く受け入れられるSchemeの標準へ向けた作業を行なうために、Schemeの主な処理系を代表する15人が会議を開催した。この報告書[RRRS]は1985年の夏にMITとIndianaの各大学で出版された。1986年春[R3RS]と1988年春[R4RS]に、さらなる改定が行なわれた。本報告書は、1992年のXerox PARCにおける会議で合意されたそれ以後の改定が反映されている。

本報告書はSchemeコミュニティー全体に帰属することを意図している。したがってその全部もしくは一部のいずれも、対価を支払わずに複製することを許可するものである。特にScheme処理系の実装者は本報告書を出発点に使用して、必要に応じて変更を加えてマニュアルその他の文書に利用するように奨励する。

謝辞

次の諸氏の支援に対して謝意を表したい。Alan Bawden、Michael Blair、 George Carrette、Andy Cromarty、Pavel Curtis、Jeff Dalton、Olivier Danvy、Ken Dickey、Bruce Duba、Marc Feeley、Andy Freeman、Richard Gabriel、Yekta G\"ursel、 Ken Haase、Robert Hieb、Paul Hudak、Morry Katz、Chris Lindblad、Mark Meyer、Jim Miller、Jim Philbin、John Ramsdell、 Mike Shaff、Jonathan Shapiro、Julie Sussman、Perry Wagle、 Daniel Weise、Henry Wu、Ozan Yigit。Scheme 311第4版参照マニュアルのテ キストの使用を許可して下さった、Carol Fessenden、 Daniel Friedman、 Christopher Haynesの諸氏にお礼を申し上げる。TI Scheme Language Reference Manual[TIMANUAL85]のテキストの使用を許可して下さった、 Texas Instruments, Incにお礼を申し上げる。MIT Scheme[MITSCHEME]、 Scheme 84[SCHEME84]、Common Lisp[CLTL]、Algol 60[NAUR63]のマニュアルに影響を受けたことに謝意を表するのは、我々の喜びである。

本報告書をTeXで書くために多大な労力を費したBetty Dexterと、彼女の労苦の原因となったプログラムを設計したDonald Knuthにも謝意を表するものである。

マサチューセッツ工科大学人工知能研究所、インディアナ大学コンピュータ科学学部、オレゴン大学コンピュータおよび情報科学学部、NEC学術研究所からは、本報告書の作成に支援を受けた。MITの作業については部分的に、国防総省先端研究プロジェクト機関により、海軍研究契約N00014-80-C-0505号の業務の支援を受けた。インディアナ大学の作業については、NSF助成金NCS83-04567とNCS 83-03325による支援を受けた。

Schemeの概要

意味論

この節では、Schemeの意味論の概要を説明する。section 基本概念からsection 標準手続きでは、厳密な形式にこだわらない意味論について詳しくとり扱う。Schemeの正式な意味論については、参考としてsection 形式記号言語で説明する。

Algolを継承したSchemeは、静的スコープを持つプログラミング言語である。使用する変数は一つ一つ、辞書的に明らかなその変数のバインディング(6)と連結される。Schemeは明示的な型とは逆の、暗黙の型を持っている。型は変数とではなく、(オブジェクトとも呼ばれる)値に連結されている。(著作物によっては暗黙の型を持つ言語を、弱い型生成を行なう言語、もしくは動的な型生成を行なう言語と呼ぶ場合がある。)暗黙の型を持つ言語には他にAPL、Snobol、およびSchemeとは別のLisp方言がある。明示的な型を持つ言語(強い型生成を行なう、もしくは静的な型生成を行なう言語と呼ばれる場合もある)にはAlgol 60、Pascal、Cが含まれる。

Schemeの演算過程で作成されるオブジェクトはすべて無限エクステント(7)を持つ。オブジェクトには手続きとコンティニュエーションが含まれる。Schemeのオブジェクトは廃棄されることが決してない。Schemeの実際の処理系が(通常は!)メモリ不足に陥ることがない理由は、あるオブジェクトが将来の計算に関係することがあり得ないと証明できた場合に、そのオブジェクトが占有している記憶域をSchemeが回収できるからである。ほとんどのオブジェクトが無限エクステントを持つその他の言語には、APLとScheme以外のLisp方言が含まれる。

Schemeの処理系は、正しく終端再帰を行なうものでなければならない。これにより、繰り返し計算が構文上再帰手続きで表現された場合でも、繰り返し計算を一定の空間内で行なうことができる。したがって終端再帰を実装していれば繰り返しを通常の手続き呼び出し機構で表現できるので、特別な繰り返し構造は「構文上の味付け(8)」程度の有用性でしかない。section 正しい終端再帰参照。

Scheme手続きは、それ自身がオブジェクトである(9)。手続きは動的に生成でき、データ構造に保存でき、手続きの結果として手続きを返すというようなことができる。このような特性を持つその他の言語には、Common LispとMLが含まれる。

Schemeの際だった特徴はそのコンティニュエーションにある。コンティニュエーションの動作はScheme以外の言語では隠れていて見えず、これは"第一位の"基本データ型でもある。コンティニュエーションは、大域脱出、バックトラッキング、コルーチンを含む、広範囲の先進的制御構造を実装する場合に有用である。section 制御機能参照。

Scheme手続きの引数は、必ず値で渡される。これは、手続きが評価の結果を必要とするしないにかかわらず、手続きに渡される前に実引数が評価されることを意味する。Scheme以外の言語ではML、C、APLの三言語が引数を常に値で渡す。これはHaskellの遅延評価文法や、Algol 60の名前渡し文法とは異なっている。この二つの言語では、手続きが値を必要としない限り引数の式は評価されない。

Schemeの演算モデルは、コンピュータ内部で数値が表される特定の方法に、可能な限り依存しないように設計されている。Schemeにおいてはすべての整数は有理数であり、すべての有理数は実数でありすべての実数は複素数である。したがって整数と実数の演算を区別することは、多くのプログラミング言語では重要であるが、Schemeには発生しない。それに代わってSchemeには、数学的な観念に対応する完全数の演算と、近似に基づく不完全数の演算の区別が存在する。Common Lispと同じように、完全数の演算は整数に限定されたものではない。

構文

ほとんどのLisp方言と同じくSchemeも、プログラムと(プログラム以外の)データについて、数がつりあった開き括弧と閉じ括弧を冠する記法を採用している。Schemeの文法では、データに使用された言語の下位言語が生成される。この単純で一様な表現から、Schemeのプログラムとデータは別のSchemeプログラムが同一の方法で処理できるという重要な意義が生まれる。例えばeval手続きでは、データとして表現されたSchemeプログラムが評価される。

read手続きは読み取るデータに、構文上ばかりでなく辞書を作成するようにも分解を実行する。read手続きは、入力をプログラムとしてでなくデータとして解析する(section 外部表現参照)。

Schemeの構文則はsection 意味論で説明する。

記法と用語

プリミティブ、ライブラリ、オプション機能

Schemeのすべての処理系には、オプションとして印をつけていないすべての機能をサポートすることが求められる。処理系はSchemeのオプション機能を省略することも、拡張を追加することもできる。ただし拡張は本報告書のScheme言語と矛盾しないこととする。特に、実際の処理系は可搬性のあるコードをサポートしなければならない。したがって処理形の構文構成法は、本報告書の辞書的な規約を恣意的に変更するものであってはならない。。

Schemeの理解と実装を容易にするために、機能の中にはライブラリの印をつけているものがある。ライブラリの機能は、別の機能すなわちプリミティブを使用して簡単に実装できる。これはことばの厳密な意味では冗長なものであるが良く使われるパターンを処理するものであり、適切な省略形を提供するものである。

エラー状況と不定の振舞い

エラー状況に言及する時は本報告書では"エラーが発信される"という語句を使用して、実際の処理系がエラーを検出して報告しなければならないことを示す。エラーを検討している際にこのような語句に言及しない場合は、エラーの検出と報告は望ましいものではあるが、処理系はエラーを検出して報告する必要はない。処理系が検出する必要がないエラー状況では、通常は単に"エラー"とだけ言及する。

例えば処理が明示的に指定されていない引数が手続きに渡された場合はその手続きに対するエラーであるが、このような定義域侵害エラーは本報告書ではほとんど言及していない。実際の処理系はこのような引数を含めるように、手続きの定義域を拡張することができる。

実装上加えられたある種の制限のために正しいプログラムが実行を継続できない場合に、処理系がその旨を報告することを許可されている状況を示すために、本報告書では"実装上の制限の侵害を報告する場合がある"という語句を使用する。いうまでもなく実装上の制限はない方がいいが、処理系は実装上の制限の侵害を報告することが望ましい。

例えばプログラムの実行に必要な充分な記憶域が存在しない場合、処理系は実装上の制限の侵害を報告する場合がある。

式の値が"不定である(unspecified)"と言及した場合、その式はエラーを発信せずに何らかのオブジェクトに評価されなければならない。ただしその値は処理系に依存する。このような場合に返すべき値については、本報告書は明示的には指定しない。

見出しの形式

section とsection 標準手続きは、見出し形式で構成されている。見出しの一つ一つが言語機能の一つ、でなければ複数の関連機能のグループの一つを表している。ここにいう機能は、文法構造もしくは組み込み手続きのいずれかを表す。どの見出しも、次の形式の見出し行で始まる。

[[カテゴリー]] テンプレート

上記は必要なプリミティブ機能の場合で、それ以外の場合は次のように書く。

[[修飾子つきカテゴリー]] テンプレート

ただし修飾子は、section 見出しの形式で定義したように"ライブラリ"もしくは"オプション"である。

カテゴリーが"構文"の場合、その項目は式の種類を説明するもので、見出し行は式の構文を示す。式の要素には文法上の変数が指定され、これをかぎ括弧で囲う。例えば<式>、<変数>のように書く。文法上の変数は、ソースプログラムテキストの一部を指すと考えてもらいたい。例えば<式>は、文法上有効な式となるあらゆる文字列を表す。次の記法はゼロ以上の<thing>が現れることを示す。

    <thing1> ...

また、次の記法は<thing>が一つ以上現れることを示す。

    <thing1> <thing2> ...

カテゴリーが"手続き"の場合その項目は手続きを説明するものであり、見出し行は手続きを呼び出すテンプレートを示す。テンプレート内の引数名はイタリック体で書く。したがって次の見出し行

[[手続き]] (vector-ref vector k)

は、組み込み手続きvector-refはSchemeのすべての処理系において、引数二つ、ベクタvectorと非負の完全整数k(下記参照)をとるように定義しなければならないことを示す。次の見出し行

[[手続き]] (make-vector k)
[[手続き]] (make-vector k fill)

では、手続きmake-vectorは一つもしくは二つの引数のいずれかをとるように定義しなければならないことを示す。

ある操作に処理が指定されていない引数が与えられた場合、それはエラーである。簡潔に書くために、次の規約を一貫して採用する。引数名がsection 型の非共有性に挙げた型名でもある場合、引数はその命名済みの型に属するものでなければならない。例えば上記のvector-refの見出し行では、vector-refの最初の引数がベクタでなければならないという指示を示している。以下の命名規約も、型の限定を含むものである。

評価の例

プログラム内で使用される記号"=>"は、"に評価される"と読んでもらいたい。例えば、

  (* 5 8)      =>  40

は、式(* 5 8)がオブジェクト40に評価されることを意味する。さらに詳しく言い替えれば、文字の連続"(* 5 8)"は、初期環境で、文字の連続"40"で外部的に表されるオブジェクトに評価される。オブジェクトの外部表現については、section 外部表現参照。

命名規約

規約上、常に論理値を返す手続きは。通常"?"で終る。このような手続きは述語手続きと呼ばれる。

規約上、以前に代入済みの場所(section 記憶モデル参照)に値を保管する手続きは、通常"!"で終る。このような手続きは割り当て手続きと呼ばれる。規約上、割り当て手続きが返す値は不定である。

規約上、ある型のオブジェクトを引数にとって別の型のオブジェクトを返す手続きの名前の中には、"->"が書かれる。例えばlist->vectorはリストを引数にとって、要素がもとのリストと同一のベクタを返す。

辞書的規約

本項ではSchemeプログラムを書くにあたっての辞書的規約をいくつか、形式にこだわらずに説明する。Schemeの構文則についてはsection 意味論参照。

文字定数と文字列定数の内部を除いて、大文字の文字と小文字の文字は全く区別されない。例えばfooFOOと同一の識別子であり、#x1AB#X1abは同一の数である。

識別子

他のプログラミング言語で許されている識別子のほとんどは、Schemeでも許される。識別子を形成する厳密な規則はSchemeの処理系ごとに異なるが、すべての処理系において、文字の連続、数字、それに数字の開始となることがあり得ない"拡張アルファベット文字"は、識別子である。加えて、+-、および...は識別子である。識別子の例をいくつか次に示す。

  lambda                   q
  list->vector             soup
  +                        V17a
  <=?                      a34kTMNs
  the-word-recursion-has-many-meanings

拡張アルファベット文字は、識別子の中で文字のように使用することができる。拡張アルファベット文字は次のものである。

  ! $ % & * + - . / : < = > ? @ ^ _ ~

識別子の形式構文についてはsection 辞書的構造参照。

Schemeプログラムでは、識別子は次の二つの用途に使用される。

空白とコメント

空白文字はスペース文字類と改行文字類である(実際の処理系では概して、タ ブや改ページなどの追加の空白文字が用意されている)。空白文字は可読性を 増すためと、必要に応じてトークン同士を分離するために使用されるが、それ 以外の場合は意味を持たない。トークンは識別子や数などの文法上分割できな い単位である。空白は二つのいかなるトークンの間にも挿入できるが、トーク ン内部に入れてはならない。文字列の中では必要に応じて空白を入れることが できる。

セミコロン(;)はコメントの開始を示す。セミコロンは、それが現れた行の終端まで有効である。コメントはSchemeからは見えないが、行の終りは空白として認識される。これにより、識別子や数の内部にコメントが入り込むことが防止される。

;;; FACT 手続きは
;;; 非負の整数の階乗を計算する
(define fact
  (lambda (n)
    (if (= n 0)
      1 ;終了の場合: 1が返される
      (* n (fact (- n 1))))))

その他の記法

数に使用される記法についてはsection 参照。

. + - これは数に使用され、最初の文字以外であれば識別子のどの場所にも使用できる。区切り文字をともなったプラス記号とマイナス記号自体も識別子である。区切り文字をともなったピリオド(数や識別子の中で使用されたピリオド以外のもの)はペア(10)
( ) 小括弧は、リストのグループ化とリストの表記に使用される(section ペアとリスト)。
' 一重引用符(11)
` バッククォート文字(12)
, ,@ 文字コンマと文字列コンマアットマークは、バッククォートとともに使用される (section バッククォート式)。
" 二重引用符は文字列の区切りとして使用される(section 文字列)。
\ バックスラッシュは構文中では文字定数として(section 文字型)、文字列定数(section 文字列)内ではエスケープ文字として使用される 。
[ ] { } | 左右大括弧と左右中括弧は、将来生じ得る言語の拡張のために予約されている。
# シャープサインはその直後に続く文字に応じて、さまざまな用途に使用される。
#t #f これらは論理定数である(section 論理式)。
#\ 文字定数の始まりを示す(section 文字型)。
#( ベクタ定数の始まりを示す(section ベクタ)。ベクタ定数は")"で終る。
#e #i #b #o #d #x 以上は数の表記に使用される(section 数値定数の構文)。

基本概念

変数、構文キーワード、領域

識別子は構文の型に名前をつけたり、値が保管される場所に名前をつけたりすることができる。構文の型に名前をつける識別子を構文キーワードと呼び、構文キーワードは構文にバインドされているといういい方をする。プログラムのある箇所で有効な可視のバインディングすべての集合は、その箇所で有効な環境と考えられる。値が保管される記憶域内のある場所(13)に名前をつける識別子を変数と呼び、そのとき変数は、その記憶域にバインドされるという。変数がバインドされている記憶域に保管される値を、変数の値と呼ぶ。用語が乱用されたために、変数が値に命名する、もしくは変数が値にバインドされると表現される場合がある。これはあまり正確ではないが、この習慣によって混乱が生ずることは滅多にない。

式の中には新種の構文を作成して、その構文に構文キーワードをバインドするのに使用されるものがある。一方で新しい記憶域を生成して、生成した記憶域に変数をバインドする式もある。このような式をバインディング構成手続きという。構文キーワードをバインドするバインディング構成手続きについてはsection マクロで説明する。

変数バインディングを構成するもっとも基本的なものはlambda式である。その他すべての変数バインディング構成手続きは、lambda式に置き換えて説明できるからである。lambda式以外のバインディング構成手続きには、let式、let*式、letrec式、do式がある(section 手続き、 section バインディング構成手続き、section 繰り返し参照)。

AlgolとPascalに同じく、しかしCommon Lispを除くその他のほとんどのLisp方言とは異なり、Schemeはブロック構造化された静的スコープを持っている。プログラム内で変数がバインドされた記憶域の一つ一つに、プログラムテキストのそのバインディングが見える内部領域の一つが対応する。この領域は、バインディングを作成した特定のバインディング構成手続きによって定まる。例えばバインディングがlambda式で作成されたとすれば、領域はそのラムダ式全体である。識別子を呼び出すとそのたびに、その変数が使用された領域のもっとも内側を構成する、変数バインディングへの参照が行なわれる。

識別子が使用された領域にその変数のバインディングが存在しない場合、トップレベル環境に変数のバインディングが存在すれば(section 参照)、識別子の呼び出しによってトップレベル環境のバインディングが参照される。識別子のバインディングがどこにも存在しない場合は、識別子はアンバウンド(14)であるという。

型の非共有性

いかなるオブジェクトも、次に述べる述語手続きの二つ以上を同時に満足することはない。

boolean?          pair?
symbol?           number?
char?             string?
vector?           port?
procedure?%

上記述語手続きは、論理型、ペア型、シンボル型、数値型、char型(もしくは文字型)、文字列型、ベクタ型、ポート型、手続き型をそれぞれ定義するものである。

論理型を独立させてはいるが、Schemeのあらゆる値は条件テストのための論理値として使用できる。section 論理式で説明する通り、条件テストにおいては#fを除くすべての値が真に評価される。section 論理式に説明する通り、本報告書では、語句"真"を使用した場合は#fを除くあらゆるSchemeの値を表し、語句"偽"を使用した場合は#fを表す。

外部表現

Scheme(およびLisp)の重要な概念の一つは、一連の文字としてのオブジェクトの外部表現である。例えば整数28の外部表現は文字列"28"であり、整数8と13からなるリストの外部表現は、文字列"(8 13)"である。

オブジェクトの外部表現は必ずしもただ一つだけとは限らない。整数28は"#e28.000"とも"#x1c"とも表現され、前段のリストは"( 08 13 )"とも"(8 . (13 . ()))"とも表現される(section ペアとリスト参照)。

オブジェクトには標準の外部表現が存在するものが多いが、中には手続きのように標準の外部表現が存在しないものもある(ただし特別な処理系の場合はその外部表現を定義してもよい)。

プログラム内に外部表現を書けば、対応するオブジェクトを手に入れることができる(quote、section リテラル式参照)。

外部表現は入出力にも使用できる。手続きread(section 入力)は外部表現を解析し、手続きwrite(section 出力)は外部表現を生成する。この二つが相俟って、優雅で強力な入出力機能が提供される。

一連の文字"(+ 2 6)"は、整数8に評価される式ではあるが、整数8の外部表現ではないことに注意しなければならない。これは整数8の外部表現ではなく、要素が三つのリストの外部表現であり、その要素はそれぞれシンボル+と、整数2と6である。Schemeの構文は、式であるいかなる文字列も、同時に何らかのオブジェクトの外部表現であることを特徴とする。これにより、ある文字列がデータを示すのかプログラムを示すのかが文脈から明らかでないために一種の混乱が生まれる可能性があるが、インタープリタとコンパイラのようなプログラムをデータとして処理する(もしくはその逆を行なう)プログラムを書くことが容易になる以上、これはSchemeが強力である理由ともなる。

section 標準手続きの該当する節では、各種オブジェクトの外部表現の構文で、そのオブジェクトを処理するプリミティブ(15)を説明している。

記憶モデル

ペア、ベクタ、文字列のような変数とオブジェクトは、記憶域内の位置もしくは連続した場所を暗黙に指し示すものである。例えば文字列は、文字列内に存在する文字と同数の記憶域内の場所を指し示している(この場所はマシンの完全1ワードに対応する必要はない)。string-set!手続きを使用すれば、そのうちの一箇所に新しい値を保管することができるが、文字列が指し示す記憶域は以前と同じ場所である。

変数の参照や、carvector-refstring-refなどの手続きによって取り出されたオブジェクトは、取り出す前に最後に保管された記憶域内のオブジェクトと、eqv?(section 同値を調べる述語手続き)の意味で等しい。

記憶域内のすべての場所には、それが使用されているかどうかを示す印が一つ一つに付けられている。いかなる変数もオブジェクトも、未使用の記憶域を参照することはない。本報告書で変数もしくはオブジェクトに記憶域が割り当てられていると言及する時は、未使用の記憶域から適当な数の場所が選択され、ついで変数やオブジェクトがそれを指し示す前に、選択された場所に使用中を示す印が付けられたことを意味している。

定数(リテラル式の値)を読み取り専用メモリに置いておくのが望ましい処理系は多い。これを表現するにあたっては、記憶域を指し示すすべてのオブジェクトに、そのオブジェクトが変更可能か変更不可かを示すフラグが連結されていると想像してみるのが適当である。定数と、symbol->string手続きから返される文字列はしたがって変更不可のオブジェクトであり、一方本報告書に挙げるその他の手続きで生成されるすべてのオブジェクトは変更可能である。変更不可のオブジェクトが指し示す記憶域に新しい値を保管しようとした場合はエラーである。

正しい終端再帰

Schemeの処理系は正しく終端再帰を行なうものでなければならない。下記に定義するような構文脈で発生する手続き呼び出しは、「終端呼び出し」である。アクティブな終端呼び出しの数に制限がないScheme処理系は、正しい終端再帰を行なっている。呼び出された手続きがともかく返ることができる場合、その手続きはアクティブである。これには、現在のコンティニュエーションにしたがって返ることができる手続き呼び出しと、後で呼び出されるcall-with-current-continuationによって捕獲された、以前のコンティニュエーションにしたがって返ることができる手続き呼び出しが含まれる。コンティニュエーションを捕獲できなかった場合手続きは一回だけは返ることができ、その場合にアクティブな手続き呼び出しはまだ返ってきていない手続き呼び出しということになる。形式文法による正しい終端再帰の定義は、[PROPERTAILRECURSION]で説明されている。

理論的根拠:

終端呼び出しで使用されるコンティニュエーションの構文が、その 呼び出しを含む手続きに渡されるコンティニュエーションの構文と 同一であることから、アクティブな終端呼び出しに余分な空間が 不要であることが直観的に理解できる。実装が正しくない処理系では 手続き呼び出しの際に新しいコンティニュエーションを利用する 場合があるが、その新しいコンティニュエーションに返った直後に、 手続きに渡されたコンティニュエーションに返ることになる。 正しい終端再帰を行なう処理系では、直接もとのコンティニュエー ションに返る。

正しい終端再帰は、SteelとSussmanによるSchemeの当初のバージョン における中心概念の1つであった。2人の最初のSchemeインタープリタ には、関数とアクタの2つが実装された。制御の流れはアクタを 使用して表現され、アクタと関数とは、アクタが呼び出し元に返る のではなく別のアクタに結果を渡すという意味で、異なるもので あった。この終端再帰語法においてはアクタの1つ1つが、別のアクタ への終端呼び出しで終了していた。

後にSteelとSussmanは、この当初のインタープリタにおいてアクタを 処理するコードが関数を処理するコードと同一であり、したがって 言語にアクタと関数の2つを含める必要がないことに気がついた。

終端呼び出しは、終端文脈で発生する手続き呼び出しである。終端文脈は帰納的に定義される。終端呼び出しは、必ず特定のラムダ式に関して定義される点に注意しなければならない。

ある種の組み込み手続きも終端呼び出しを実行する必要がある。applycall-with-current-continuationに渡される第1引数と、call-with-valuesに渡される第2引数は、終端呼び出し経由で呼び出さなければならない。同様にeval手続きでは、引数がeval手続き内部の終端位置にあるかのように評価しなければならない。

以下の例で、唯一の終端呼び出しはfの呼び出しである。gへの呼び出しもhの呼び出しも終端呼び出しではない。xへの参照は終端文脈にあるがこれは呼び出しではなく、したがって終端呼び出しではない。

  (lambda ()
    (if (g)
        (let ((x (h)))
          x)
        (and (g) (f))))

注: 処理系には上記hの呼び出しのようなある種の非終端呼び出しについて、終端呼び出しであるかのように評価できると認識することが許される。ただしこれは必須ではない。上記の例の場合、let式をhへの終端呼び出しとしてコンパイルしてもよい。(hが予期せぬ数の値を返す可能性は無視できる。この場合letの結果は明示的に不定であり、処理系に依存するからである。)

式の型はプリミティブか、あるいはそれから導出されたものとして分類される。プリミティブ式の種類には、変数と手続き呼び出しが含まれる。導出式型は文法的にはプリミティブではないが、マクロとして定義することができる。マクロ定義が複雑となるバッククォート式を除いて、導出式型はライブラリ機能に分類される。この適切な定義については、section 導出式型に示す。

プリミティブ式型

変数の参照

[[構文]] <変数>

変数(section 変数、構文キーワード、領域)で構成される式は変数を参照する。変数の値は、変数がバインドされた記憶域に保管された値である。バインドされていない変数を参照した場合はエラーである。

  (define x 28)
  x  => 28

リテラル式

[[構文] (quote <データ>)
[[構文] '<データ>
[[構文] <定数>

(quote <データ>)は<データ>に評価される。<データ>は、Schemeオブジェクトのいかなる外部表現であってもよい(section 外部表現参照)。この記法は、書かれた通りの定数をSchemeコードに含めるのに使用される。

  (quote a)                     =>  a
  (quote #(a b c))              =>  #(a b c)
  (quote (+ 1 2))               =>  (+ 1 2)

(quote <データ>)は、'<データ>と略記してもよい。この二つの記法はすべての点で等価である。

  'a                   =>  a
  '#(a b c)            =>  #(a b c)
  '()                  =>  ()
  '(+ 1 2)             =>  (+ 1 2)
  '(quote a)           =>  (quote a)
  ''a                  =>  (quote a)

数値定数、文字列定数、文字定数、論理定数はそれ自身に評価されるので、クォートをつける必要はない。

  '"abc"     =>  "abc"
  "abc"      =>  "abc"
  '145932    =>  145932
  145932     =>  145932
  '#t        =>  #t
  #t         =>  #t

section 記憶モデルで言及したように、set-car!string-set!のような書き換え手続きを使用して、定数(リテラル式の値)を変更することはエラーである。

手続き呼び出し

[[構文]] (<オペレータ> <オペランド1> ...)

手続きの呼び出しは、呼び出す手続きの式とそれに渡す引数を小括弧で括って表記される。オペレータの式とオペランドの式は(不定の順序で)評価され、評価結果の手続きに評価結果の引数が渡される。

  (+ 3 4)                   =>  7
  ((if #f + *) 3 4)         =>  12

初期環境では、変数の値として一定数の手続きが利用できる。例えば上記の例の加算手続きと乗算手続きは、それぞれ変数+*の値である。新しい手続きは、ラムダ式(section 手続き参照)を評価して生成される。

手続き呼び出しはいかなる値でも返すことができる(section 制御機能values参照)。valuesの場合を除いて初期環境で利用できる手続き呼び出しは1つの値を返すか、さもなければapplyのような手続きの場合には、引数の一つの呼び出しから返される値を次の手続きに渡す。

手続きの呼び出しはコンビネーションとも呼ばれる。

注: その他のLisp方言とは対照的に評価の順序は不定であり、オペレータ式とオペランド式は、必ず同一評価規則で評価される。

注: 一般には評価の順序は不定であるが、オペレータ式とオペランド式のいかなる同時並行的評価の結果も、一定の順次的評価と一致しなければならない。評価の順序は手続きの呼び出しごとに選択できる。

注: 多くのLisp方言では空のコンビネーション()は有効な式である。Schemeにおいてはコンビネーションは少くとも一つの下位の式を持っていなければならず、したがって()は文法上有効な式ではない。

手続き

[[構文]] (lambda <仮引数> <ボディ>)

構文: <仮引数>は下記に示す通りの仮引数のリスト(16)でなければならず、<ボディ>には一つ以上の式が連続しなければならない。

意味: ラムダ式は手続きに評価される。ラムダ式が評価された時に有効な環境が、手続きの一部として記憶される。後で手続きが何らかの実引数とともに呼び出された時には、仮引数リスト内の変数が新しい記憶域にバインドされてラムダ式が評価された環境が拡張され、対応する実引数の値がその記憶域に保管される。ラムダ式のボディの中の式は、その拡張された環境で順次的に評価される。手続き呼び出しの結果として、ボディの最後の式の結果が返される。

  (lambda (x) (+ x x))     =>   ;手続き
   ((lambda (x) (+ x x))4) => 8 ;(17)
   (define reverse-subtract 
    (lambda (x y) (- y x)))
   (reverse-subtract 7 10) => 3 ;(18)
   (define add4
    (let ((x 4))
      (lambda (y) (+ x y))))
  (add4 6) => 10

<仮引数群>は次の形式でなければならない。

<仮引数群>の中に<変数>が二度以上現れた場合はエラーである。

  ((lambda x x) 3 4 5 6) => (3 4 5 6);(19)
  ((lambda(x y . z) z) 
    3 4 5 6)         => (5 6);(20)

ラムダ式の評価の結果生成された手続き一つ一つには、eqv?eq?が手続きに対して有効になるように(section 同値を調べる述語手続き参照)、(概念的には)保管場所を示す標識が付けられる。

条件式

[[構文]] (if <テスト> <帰結> <代わりの帰結>)
[[構文]] (if <テスト> <帰結>)

構文: <テスト>、<帰結>、<代わりの帰結>は、任意の式であってよい。

意味: if式は次のように評価される。最初に<テスト>が評価される。その結果の値が真であれば(section 論理式参照)、<帰結>が評価されてその値が返される。さもなければ<代わりの帰結>が評価されてその値が返される。<テスト>の結果の値が偽で<代わりの帰結>が指定されていない場合は、式の結果は不定である。

  (if (> 3 2) 'yes 'no) => yes
  (if (> 2 3) 'yes 'no) => no
  (if (> 3 2)
      (- 3 2)
      (+ 3 2)) => 1

割り当て

[[構文]] (set! <変数> <式>)

<式>が評価されて、<変数>がバインドされている記憶位置に結果の値が保管される。<変数>は、set!式を取り囲む領域内かトップレベルの、いずれかにバインドしなければならない。set!式の結果は不定である。

  (define x 2)
  (+ x 1)     => 3
  (set! x 4)  => unspecified
  (+ x 1)     => 5

導出式型

section マクロに説明する通り、本節の構成手続きは名前の衝突を起こさないものである(ハイジーニック)。参考のために、本節に説明する構成手続きのほとんどを前節に説明したプリミティブ構成手続きに変換するマクロ定義を、section 導出式型に示す。

条件節

[[ライブラリ構文]] (cond <節1> <節2> ...)

構文: <節>の一つ一つは、

  (<テスト> <式1> ...)

の形式でなければならない。ここに <テスト>はあらゆる式である。

もう1つの書法として、<節>を次のように書くこともできる。

  (<テスト> => <式>)

最後の <節>はelse節であってもよく、これは

  (else <式1> <式2> ...)

の形式である。

意味: cond式は、連続する<節>の<テスト>式を順に評価しながら、そのうちの一つが真値(section 論理式参照)に評価されるまで評価が継続される。<テスト>が真値に評価されると、その<節>の残りの<式>が順次評価される。その<節>の最後の<式>の結果がcond式全体の結果として返される。選択した<節>に<テスト>のみが存在して<式>が存在しない場合、<テスト>の値が結果として返される。選択した<節>がもう1つの書法=>形式を使用している場合、続く<式>が評価される。<式>の値は引数を1つとる手続きでなければならない。この場合、<テスト>の値に基づいてこの手続きが呼び出され、手続きの返す値がcond式の返す値になる。すべての<テスト>が偽値に評価されかつelse節が存在しなかった場合、その条件式の結果は不定である。else節が存在する場合はその <式>が評価されて、最後の式の値が返される。

  (cond ((> 3 2) 'greater)
        ((< 3 2) 'less))                    =>  greater

  (cond ((> 3 3) 'greater)
        ((< 3 3) 'less)
        (else 'equal))                      =>  equal

  (cond ((assv 'b '((a 1) (b 2))) => cadr)
        (else #f))                          =>  2

[[ライブラリ構文]] (case <キー> <節1> <節2> ...)

<キー>はどんな式でもよい。<節>の一つ一つは次の形式でなければならない。

    ((<データ1> ...) <式1> <式2> ...) 

ここに、<データ>の一つ一つはオブジェクトの外部表現である。<データ>はすべて、異なるものでなければならない。最後の<節>は"else節"であってもよくこれは次の形式をとる。

  (else <式1> <式2> ...).

意味: case式は次のように評価される。<キー>が評価されて、その結果が<データ>の一つ一つと比較される。評価中の<キー>が(eqv?の意味で、section 同値を調べる述語手続き参照)<データ>に等しい場合、対応する<節>の式が左から右へと評価され、<節>の最後の式の結果がcase式の結果として返される。評価中の<キー>の結果がすべての<データ>と異なる場合、else節が存在すればその式群が評価されて、その最後の式の結果がcase式の結果となる。else節が存在しない場合は、case式の結果は不定である。

  (case (* 2 3)
    ((2 3 5 7) 'prime)
    ((1 4 6 8 9) 'composite))     =>  composite
  (case (car '(c d))
    ((a) 'a)
    ((b) 'b))                     =>  unspecified
  (case (car '(c d))
    ((a e i o u) 'vowel)
    ((w y) 'semivowel)
    (else 'consonant))            =>  consonant
[[ライブラリ構文]] (and <テスト1> ...)

<テスト>は左から右へと評価され、偽値(section 論理式参照)に評価された最初の式の値が返される。残りの式は全く評価されない。すべての式が真値に評価された場合は、最後の式の値が返される。式が存在しない場合は#tが返される。

  (and (= 2 2) (> 2 1))           =>  #t
  (and (= 2 2) (< 2 1))           =>  #f
  (and 1 2 'c '(f g))             =>  (f g)
  (and)                           =>  #t
[[ライブラリ構文]] (or <テスト1> ...)

<テスト>式が左から右へと評価され、真値(section 論理式参照)に評価された最初の式の値が返される。残りの式は一切評価されない。すべての式が偽値に評価された場合は、最後の式の値が返される。式が存在しない場合は、#fが返される。

  (or (= 2 2) (> 2 1))            =>  #t
  (or (= 2 2) (< 2 1))            =>  #t
  (or #f #f #f)                   =>  #f
  (or (memq 'b '(a b c))
      (/ 3 0))                    =>  (b c)

バインディング構成手続き

letlet*letrecの三つのバインディング構成手続きを使用すれば、Algol 60同様のブロック構造をSchemeで実現できる。この三つの構成手続きの構文は同一であるが、変数バインディングを作成する領域が異なっている。let式では、変数のバインディングが行なわれる以前に、初期値が計算される。let*式では、バインディングと評価が順次的に行なわれる。一方letrec式では、初期値が計算されている間にもバインディングが有効であり、したがって相互に再帰的な定義が可能である。

[[ライブラリ構文]] (let <バインディング> <ボディ>)

構文: <バインディング>は次の形式でなければならない

    ((<変数1> <初期値1>) ...)

ここに<初期値>は式である。さらに<ボディ>には一つ以上の式が連続しなければならない。バインドしている変数リスト内に<変数>が二度以上現れた場合はエラーである。

意味: 初期値は現行の環境で(不定の順序で)評価される。<変数>は結果を保持する新しい記憶域にバインドされる。<ボディ>はその拡張された環境で評価され、<ボディ>の最後の式の値が返される。<変数>のバインディング一つ一つは、ボディをその領域とする。

  (let ((x 2) (y 3))
    (* x y))                      =>  6

  (let ((x 2) (y 3))
    (let ((x 7)
          (z (+ x y)))
      (* z x)))                   =>  35

名前付let、section 繰り返しも参照。

[[ライブラリ構文]] (let* <バインディング> <ボディ>)

構文: <バインディング>は次の形式でなければならない。

    ((<変数1> <初期値1>) ...)

さらに、<ボディ>には一つ以上の式が連続しなければならない。

意味: let*letに似ているが、バインディングは左から右に順次行なわれ、(<変数> <初期値>)が示すバインディングの領域は、let*式からバインディングの右側へ向かう領域である。したがって第2のバインディングが行なわれる環境では最初のバインディングが見え、以後のバインディングでも同様である。

  (let ((x 2) (y 3))
    (let* ((x 7)
           (z (+ x y)))
      (* z x)))             =>  70
[[ライブラリ構文]] (letrec <バインディング> <ボディ>)

構文: <バインディング>は次の形式でなければならない。

    ((<変数1> <初期値1>) ...)

<ボディ>には一つ以上の式が連続しなければならない。バインドしている変数リスト内に<変数>が二度以上現れた場合はエラーである。

意味: <変数>は、未定義の値を保持する新しい記憶域にバインドされる。その結果の環境で(不定の順序で)<初期値>が評価される。<変数>は一つ一つ対応する<初期値>の結果に割り当てられ、その結果の環境で<ボディ>が評価される。<ボディ>の最後の式の結果が返される。<変数>のバインディング一つ一つの領域はletrec式全体であり、したがって再帰手続きを相互に定義することが可能である。

  (letrec ((even?
            (lambda (n)
              (if (zero? n)
                  #t
                  (odd? (- n 1)))))
           (odd?
            (lambda (n)
              (if (zero? n)
                  #f
                  (even? (- n 1))))))
    (even? 88))
                  =>  #t

letrecに関する次の制限は非常に重要である。一つ一つの<初期値>は、いかなる<変数>への割り当ても参照も行なわずに評価できなければならない。この制限を侵害した場合はエラーである。この制限が必要な理由は、Schemeが引数を名前でなく値で渡すためである。letrecの一般的な使用法では<初期値>がすべてラムダ式である場合がもっとも多く、その場合この制限は自動的に満足される。

順次処理式

[[ライブラリ構文]] (begin <式1> <式2> ...)

<式>は左から右へ順次的に評価され、最後の<式>の値が返される。この型の式は、入出力などの副作用(21)を順次的に処理するために使用される。

  (define x 0)

  (begin (set! x 5)
         (+ x 1))           => 6

  (begin (display "4 plus 1 equals ")
         (display (+ 4 1))) => unspecified
  [さらに次のように印字される]  4 plus 1 equals 5  (22)

繰り返し

[[ライブラリ構文]](do ((<変数1> <初期値1> <ステップ1>)
                        ...)
                      (<テスト> <式> ...)
                      <コマンド> ...)

doは、繰り返しを構成する手続きである。バインドすべき変数の組、開始時に変数を初期化する方法、および繰り返しごとに変数を更新する方法を指定する。終了条件が満足されると<式> ...が評価されてループが終了する。

do式は次のように評価される。<初期値>の式が(不定の順序で)評価される。<変数>が新しい記憶域にバインドされ、初期値の式の評価結果が<変数>のバインディングに保管される。その上で繰り返し手順が開始する。

一回の繰り返しは<テスト>の評価で始まる。結果が偽であれば(section 論理式参照)<コマンド>の式が順次評価されて有効になる。<ステップ>の式が不定の順序で評価され、<変数>が新しい記憶域にバインドされる。<ステップ>の評価結果がその<変数>のバインディングに保管される。ついで次の繰り返しが開始する。

<テスト>が真値に評価されると<式>が左から右へ評価され、最後の<式>の値が返される。<式>が存在しない場合、do式の評価値は不定である。

変数のバインディング領域は、<初期値>を除くdo式全体で構成される。do式の変数リストに<変数>が二度以上現れた場合はエラーである。

<ステップ>は省略でき、その場合は(<変数> <初期値>)の代わりに、(<変数> <初期値> <変数>)と書いたものと同じ効果である。

  (do ((vec (make-vector 5))
       (i 0 (+ i 1))) 
      ((= i 5) vec) 
    (vector-set! vec i i)) => #(0 1 2 3 4)

  (let ((x '(1 3 5 7 9)))
    (do ((x x (cdr x))
         (sum 0 (+ sum (car x)))) 
      ((null? x) sum)))    => 25
[[ライブラリ構文]] (let <変数> <バインディング> <ボディ>)

Schemeの処理系によっては、"名前付let(named let)"と呼ばれるもう一つのlet構文が使用できる。これはdoよりもさらに一般的なループ構造が可能であり、再帰の表現にも使用できる。

名前付letの構文と意味は通常のletと同じであるが、<変数>が<ボディ>内部で手続きにバインドされる点が異なっている。この時、手続きの仮引数はバインドされた変数群であり、手続きの本体が<ボディ>である。したがって<変数>で命名された手続きを呼び出せば、<ボディ>の実行を繰り返すことができる。

  (let loop ((numbers '(3 -2 1 6 -5))
             (nonneg '())
             (neg '()))
    (cond ((null? numbers) (list nonneg neg))
          ((>= (car numbers) 0)
           (loop (cdr numbers)
                 (cons (car numbers) nonneg)
                 neg))
          ((< (car numbers) 0)
           (loop (cdr numbers)
                 nonneg
                 (cons (car numbers) neg)))))
    =>  ((6 1 3) (-5 -2))

遅延評価

[[ライブラリ構文]] (delay <式>)

delay構成手続きはforce手続きと組み合わせて使用して、その場で行なわない評価もしくは必要が生じた時の呼び出しを実装するものである。(delay <式>)は、プロミスと呼ばれるオブジェクトを返す。プロミスは将来のある時点で(force手続きによって)呼び出すことができ、その時点で<式>が評価されて結果が返される。複数の値を返す<式>の結果は不定である。

delayのさらに詳しい説明についてはforce(section 制御機能)参照。

バッククォート式

[[構文]] (quasiquote <qqテンプレート>)
[[構文]] `<qqテンプレート>

"バッククォート"式あるいは"疑似クォート"式は、あらかじめほとんどわかっているけれども一部不明なリスト構造やベクタ構造が欲しい時に、その構造を作成するのに有用である。<qqテンプレート>内にコンマがない場合、`<qqテンプレート>の評価結果は'<テンプレート>に等しい。ただし<qqテンプレート>内にコンマがあると、コンマに続く式は("クォートを取り払って(アンクォート)")評価され、コンマとそれに続く式の代わりにその評価結果が構造内に挿入される。コンマの直後にアットマーク(@)が書かれている場合は、それに続く式はリストに評価されなければならない。この時リストの開き括弧と閉じ括弧は"取り除かれ"、コンマアットマーク式に代わってそのリストの要素がそのあとに挿入される。コンマアットマークは、リストかベクタの<qqテンプレート>内部に書かなければならない。

  `(list ,(+ 1 2) 4)  =>  (list 3 4)
  (let ((name 'a)) `(list ,name ',name))
                      =>  (list a (quote a))
  `(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b)
                      =>  (a 3 4 5 6 b)
  `((foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons)))
                      =>  ((foo 7) . cons)
  `#(10 5 ,(sqrt 4) ,@(map sqrt '(16 9)) 8)
                      =>  #(10 5 2 4 3 8)

バッククォート形式はネストできる。もっとも外側のバッククォートと同一のネストレベルで書かれたアンクォート要素に対してだけ置換が行なわれる。ネストレベルは、バッククォートが現れるたびにバッククォートの内側で1つ増加し、アンクォートが現れるたびにその内側で1つ減少する。

  `(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)
            =>  (a `(b ,(+ 1 2) ,(foo 4 d) e) f)
  (let ((name1 'x)
        (name2 'y))
    `(a `(b ,,name1 ,',name2 d) e))
            =>  (a `(b ,x ,'y d) e)

2つの記法`<qqテンプレート>と(quasiquote <qqテンプレート>)はすべての点で等しい。,<式>(unquote <式>)に等しく、,@<式>(unquote-splicing <式>)に等しい。リストのcarが以上のシンボルの一つである2要素リストの場合、それに対してwriteが生成する外部表現による構文は、処理系によって異なる場合がある。

  (quasiquote (list (unquote (+ 1 2)) 4))
             =>  (list 3 4)
  '(quasiquote (list (unquote (+ 1 2)) 4))
             =>  `(list ,(+ 1 2) 4)
       i.e., (quasiquote (list (unquote (+ 1 2)) 4))

ただしこれは等しい構文(quasiquote (list (unquote (+ 1 2)) 4))と表現される場合がある。

シンボルquasiquoteunquoteunquote-splicingのいずれも、<qqテンプレート>内の上に述べた以外の場所に書かれた場合は生ずる動作は予測できない。

マクロ

Schemeプログラムでは、マクロと呼ばれる新しい導出式型を定義して使用することができる。プログラムで定義される導出式型の構文は次の通りである。

(<キーワード> <データ> ...)

ただし<キーワード>は、式の型を一意に定める識別子である。この識別子は構文キーワード、もしくは単にキーワードと呼ばれる。<データ>の数とその構文は、式の型に応じて異なる。

一つのマクロの具体化をそのマクロの使用と呼ぶ。マクロの使用をよりプリミティブな式に翻訳する方法を指定する規則の集合は、変換手続きと呼ばれる。

マクロ定義は次の2つの部分からなる。

マクロの構文キーワードは変数バインディングを隠す(23)場合があり、局所変数はキーワードバインディングを隠す場合がある。このパターン言語を使用して定義されたすべてのマクロは、次のように"名前の衝突"(24)がなく(ハイジーニック)、"参照上透過的"であり、したがってSchemeの辞書的スコープが保持される[KOHLBECKER86]、[HYGIENIC]、[BAWDEN88]、[MACROSTHATWORK]、[SYNTACTICABSTRACTION]。

構文キーワードのバインディング構成手続き

let-syntaxletrec-syntaxはそれぞれletletrecに似ているが、値が入る記憶域に変数をバインドするのではなく、構文キーワードをマクロ変換手続きにバインドする。構文キーワードをトップレベルで作成することもできる。section 構文定義参照。

[[構文]] (let-syntax <バインディング> <ボディ>)

構文: <バインディング>は次の形式でなければならない。

    ((<キーワード> <変換手続き仕様>) ...) 

<キーワード>の一つ一つは識別子である。<変換手続き仕様>の一つ一つはsyntax-rulesの発動である。<ボディ>には一つ以上の式が連続しなければならない。バインディングを実行中のキーワードのリストの中に、<キーワード>が二度以上現れた場合はエラーである。

意味: 指定変換手続きにバインドした<キーワード>をキーワードととするマクロを使用して、let-syntax式の構文環境を拡張した構文環境が得られる。その構文環境で<ボディ>が展開される。一つ一つの<キーワード>のバインディング領域は<ボディ>である。

  (let-syntax ((when (syntax-rules ()
                       ((when test stmt1 stmt2 ...)
                        (if test
                            (begin stmt1
                                   stmt2 ...))))))
    (let ((if #t))
      (when if (set! if 'now))
      if))                           =>  now

  (let ((x 'outer))
    (let-syntax ((m (syntax-rules () ((m) x))))
      (let ((x 'inner))
        (m))))                       =>  outer
[[構文]] (letrec-syntax <バインディング><ボディ>)

構文: let-syntaxに同じ。

意味: 指定変換手続きにバインドされた<キーワード>をキーワードとするマクロを使用して、letrec-syntax式の構文環境を拡張した構文環境が得られる。その構文環境で<ボディ>が展開される。<キーワード>のバインディング1つ1つの領域内に<バインディング>と<ボディ>が配置され、変換手続きはそれによってletrec-syntax式が導入するマクロの使用に式を翻訳できる。

  (letrec-syntax
    ((my-or (syntax-rules ()
              ((my-or) #f)
              ((my-or e) e)
              ((my-or e1 e2 ...)
               (let ((temp e1))
                 (if temp
                     temp
                     (my-or e2 ...)))))))
    (let ((x #f)
          (y 7)
          (temp 8)
          (let odd?)
          (if even?))
      (my-or x
             (let temp)
             (if y)
             y)))        =>  7

パターン言語

<変換手続き仕様>は次の形式である。

  (syntax-rules <リテラル> <構文規則> ...)

構文: <リテラル>は識別子のリストで、<構文規則>の一つ一つは次の形式でなければならない。

    (<パターン> <テンプレート>)

<構文規則>内の<パターン>は、マクロキーワードで始まるリスト<パターン>である。

<パターン>は識別子か定数であるか、でなければ下記のいずれかである。

    (<パターン> ...)
    (<パターン> <パターン> ... . <パターン>)
    (<パターン> ... <パターン> <略記号>)
    #(<パターン> ...)
    #(<パターン> ... <パターン> <略記号>)

<テンプレート>は識別子か定数であるか、でなければ下記のいずれかである。

    (<要素> ...)
    (<要素> <要素> ... . <テンプレート>)
    #(<要素> ...)

ただし<要素>は<テンプレート>であり、オプションで<略記号>を続ける場合がある。<略記号>は識別子"..."である(略記号識別子は、テンプレート内でもパターン内でもこの意味の識別子としてしか使用することはできない)。

意味: syntax-rulesが現れるごとに一連の名前の衝突を起こさない---ハイジーニックな---書き換え規則が指定され、新しいマクロ変換手続きがひとつ生成される。syntax-rulesが指定するマクロ変換手続きにキーワードが連結されたマクロの使用が、<構文規則>に含まれるパターンに一致するかどうかが<構文規則>の左端から比較される。一致するものが発見されると、テンプレートにしたがってマクロの使用がハイジーニックな方法で翻訳される。

<構文規則>のパターン内に現れる識別子は、パターンを開始するキーワードであるか、<リテラル>内にリストされるか、でなければ識別子"..."でない限り、パターン変数である。パターン変数は任意の入力要素に一致するもので、テンプレート内の入力要素の参照に使用される。<パターン>内に同一のパターン変数が二度以上現れた場合はエラーである。

<構文規則>のパターンの開始位置のキーワードは比較の対象には含まれず、パターン変数ともリテラル識別子とも見なされない。

理論的根拠:

キーワードのスコープは、キーワードとそれに結合するマクロ 変換手続きとをバインドする式もしくは構文定義によって定まる。 キーワードがパターン変数かリテラル識別子ならば、キーワードが let-syntaxによってバインドされたか、letrec-syntax によってバインドされたかにかかわらず、パターンに続くテンプレー トはキーワードのスコープ内にあることになる。

<リテラル>内に現れる識別子はリテラル識別子と解釈され、入力の対応する部分形式との一致が比較される。入力内の部分形式は、それが識別子であり、かつマクロ式内に出現する識別子とマクロ定義内に出現する識別子の両方が同一の辞書的バインディングを持っているか、二つの識別子が等しく両方とも辞書的バインディングを持っていないかのいずれかの場合に限ってリテラル識別子に一致する。

...が後続する部分パターンは、ゼロ個以上の入力要素に一致することができる。...が<リテラル>内に現れた場合はエラーである。パターンの内部では、識別子...は連続する空でない部分パターンの最後の要素の後ろに続けなければならない。

より形式的にいえば、次のいずれかの場合に限って入力形式FはパターンPに一致する。

マクロキーワードのバインディングスコープの内部で、いずれのパターンとも一致しない式にマクロキーワードを使用した場合はエラーである。

一致する<構文規則>のテンプレートにしたがってマクロの使用が翻訳されると、テンプレート内に現れるパターン変数は入力内の一致する部分形式で置き換えられる。一つ以上の識別子...が後続する部分パターン内に現れるパターン変数は、同一の数の識別子...が後続する部分テンプレート内でのみ使用することができる。パターン変数は指定通りに配分されて、入力内のすべての一致する部分形式で置き換えられて出力される。出力を指定通りに構築できない場合はエラーである。

テンプレート内に書かれていてもパターン変数でも識別子...でもない識別子は、リテラル識別子として出力に挿入される。リテラル識別子が自由な識別子として挿入された場合は、syntax-rulesのインスタンスが書かれているスコープ内の識別子のバインディングが参照される。リテラル識別子がバインド済み識別子として挿入された場合、リテラル識別子が自由な識別子に不用意に連結されるのを防止するために、リテラル識別子は実質的に名前が変更される。

例えばletcondがsection 導出式型の通りに定義されていたとすれば、この2つの識別子は(仕様通り)ハイジーニックであり、次はエラーではない。

  (let ((=> #f))
    (cond (#t => 'ok)))           => ok

condのマクロ変換手続きは=>を局所変数として、したがって式の1つとして認識し、マクロ変換手続きが構文キーワードとして処理するトップレベル識別子としては認識しない。したがって上の例は次のように展開される。

  (let ((=> #f))
    (if #t (begin => 'ok)))

次のように展開されるのではない。

  (let ((=> #f))
    (let ((temp #t))
      (if temp ('ok temp))))

これは無効な手続き呼び出しになる。

Program structure

プログラム

Schemeプログラムは一連の式、定義、構文定義で構成される。式はsection で説明する。この章では定義と構文定義を説明する。

プログラムは概してファイルに保管されるか、実行中のScheme処理系で対話的に入力される。無論これ以外の方法も考えられる。ユーザインタフェースは本報告書の取り扱い範囲外である。(実際Schemeは、機械的な処理系がない場合でも計算法を表現する記法として有効である。)

プログラムのトップレベルで生成される定義と構文定義は、宣言と解釈できる。宣言により、トップレベル環境にバインディングが作成される。あるいはトップレベルの既存のバインディングが変更される。プログラムのトップレベルに書かれた式は必ず解釈され、プログラムが呼び出されるかロードされた時に順次実行される。これは一般に一定の初期化を行なうものである。

プログラムのトップレベルでの(begin <表現形式1> ...)は、beginのボディを形成する連続する式、定義、構文定義に等しい。

定義

定義は、必ずというわけではないが、式が許される一定の文脈で有効である。定義は、<プログラム>のトップレベルと<ボディ>の開始点でのみ有効である。

定義は以下の形式の一つで行なわなければならない。

トップレベルの定義

プログラムのトップレベルにおいて、次の定義

  (define <変数> <式>)

は本質的に、<変数>がバインド済みの場合の次の割り当て式と同じ効果がある。

  (set! <変数> <式>)

ただし<変数>がバインドされていない場合は、割り当てを実行する前に定義を行なうことによって、<変数>が新しい記憶域にバインドされる。バインドされていない変数にset!を実行した場合はエラーになる。

  (define add3
    (lambda (x) (+ x 3)))
  (add3 3)                            =>  6
  (define first car)
  (first '(1 2))                      =>  1

処理系によっては、考えられる変数をすべて記憶域にバインドした初期環境を使用するものがある。その記憶域の大部分に含まれる値は未定義である。そのような処理系の場合、トップレベルの定義はまさしく割り当てに等しい。

内部での定義

<ボディ>の冒頭(すなわちlambda式、let式、let*式、letrec式、let-syntax式、letrec-syntax式のボディ、もしくは適切な形式の定義のボディ)に定義を配置してもよい。このような定義は先に述べたトップレベルの定義に対して、内部での定義と考えられる。内部での定義で定義された変数は、<ボディ>に対して局所的である。すなわち<変数>は割り当てられるのではなくバインドされる。したがってバインディング領域は<ボディ>全体である。次に例を挙げる。

    (let ((x 5))
      (define foo (lambda (y) (bar x y)))
      (define bar (lambda (a b) (+ (* a b) a)))
      (foo (+ x 3)))  =>   45

内部での定義を含む<ボディ>は、完全に等価なletrec式に必ず変換できる。例えば上記のlet式は次の式に等価である。

    (let ((x 5))
      (letrec ((foo (lambda (y) (bar x y)))
        (bar (lambda (a b) (+ (* a b) a)))) 
        (foo (+ x 3))))

まさに等価なletrec式の場合と同じく<ボディ>内部での定義の<式>は、定義中のいかなる<変数>への割り当ても参照も行なわずに、一つ一つ評価できなければならない。

内部での定義ができる場所では(begin <定義1> ...)は常に、begin式のボディを構成する一連の定義に等価である。

構文定義

構文定義は、<プログラム>のトップレベルでのみ有効である。構文定義の形式 は次の通りである。

  (define-syntax <キーワード> <変換手続き仕様>)

<キーワード>は識別子である。<変換手続き仕様>はsyntax-rulesの発動でなければならない。<キーワード>を指定変換手続きにバインドして、トップレベルの構文環境が拡張される。

内部での定義には、define-syntaxに類似したものは存在しない。

文脈で許される限りはマクロを定義と構文定義に展開できるが、定義や構文定義によるシャドウイングで次のような構文キーワードが隠される場合はエラーである。トップレベルグループでの定義もしくは内部での定義において、シャドウイングを行なう定義を含む定義が事実上定義の一つであるかどうかを判別するのに意味が必要となる構文キーワード。もしくはグループとそれに続く式の境界を判別するのに意味が必要となる構文キーワード。例えば以下はエラーである。

  (define define 3)

  (begin (define begin list))

  (let-syntax
    ((foo (syntax-rules ()
            ((foo (proc args ...) body ...)
             (define proc
               (lambda (args ...)
                 body ...))))))
    (let ((x 3))
      (foo (plus x y) (+ x y))
      (define foo x)
      (plus foo x)))

標準手続き

本章ではSchemeの組み込み手続きを説明する。Schemeの初期環境(もしくは"トップレベル")は、有用な値を含む記憶域に一定数の変数をバインドして開始する。変数の大部分はデータを処理するプリミティブ手続きである。例えば変数 absは、引数を一つ取って数の絶対値を計算する手続き(が入るように初期化された記憶域)にバインドされている。変数+は和を計算する手続きにバインドされている。別の組み込み手続きに置き換えて容易に書くことができる組み込み手続きは、"ライブラリ手続き"と呼んで区別している。

プログラムは、トップレベルの定義を使用してあらゆる変数をバインドできる。ついで割り当てによって(section 割り当て参照)、そのバインディングを変更できる。Schemeの組み込み手続きの動作は、このような操作によっては変更されない。定義によって導入されなかったトップレベルバインディングを変更した場合、それによる組み込み手続きへの影響は不定である。

同値を調べる述語手続き

述語手続きは、必ず論理値(#tか#f)を返す手続きである。同値を調べる述語手続きは、(対称的、反射的、推移的な)数学的同値関係の演算上の類同語である。本項で説明する同値述語手続きの内で、eq?がもっとも緻密もしくは差別が厳しくequal?がもっともきめが粗い。eqv?eq?と比べるとやや差別がゆるい。

[[手続き]] (eqv? obj1 obj2)

eqv?手続きは、オブジェクトに関して利用価値の高い同値関係を定義するものである。簡単にいえばこの手続きは、obj1とobj2が通常は当然同一オブジェクトと見なされる場合に、#tを返す。この関係は多少解釈の余地を残してはいるが、以下に述べるeqv?の部分的仕様は、Schemeのすべての処理系に共通する。

eqv?手続きは次の場合に#tを返す。

eqv?手続きは次の場合に#fを返す。

次の例は、上記の規則ではeqv?の動作を充分には指定しきれない場合を示すものである。このような場合にいえることは、eqv?の返す値が論理値でなければならないということだけである。

  (eqv? "" "")             =>  unspecified
  (eqv? '#() '#())         =>  unspecified
  (eqv? (lambda (x) x)
        (lambda (x) x))    =>  unspecified
  (eqv? (lambda (x) x)
        (lambda (y) y))    =>  unspecified

局所状態を持つ手続きにeqv?を使用した場合を次の例に示す。gen-counterは、呼び出されるごとに異なる手続きを必ず返す。呼び出された手続きはそれぞれ固有の内部カウンタを持っているからである。一方gen-loserは、何度呼び出されてもすべて同値の手続きを返す。手続きの値もしくは副作用が、局所状態によって変化しないからである。(26)

  (define gen-counter
    (lambda ()
      (let ((n 0))
        (lambda () (set! n (+ n 1)) n))))
  (let ((g (gen-counter)))
    (eqv? g g))           =>  #t
  (eqv? (gen-counter) (gen-counter))
                          =>  #f
  (define gen-loser
    (lambda ()
      (let ((n 0))
        (lambda () (set! n (+ n 1)) 27))))
  (let ((g (gen-loser)))
    (eqv? g g))           =>  #t
  (eqv? (gen-loser) (gen-loser))
                          =>  unspecified

  (letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
           (g (lambda () (if (eqv? f g) 'both 'g))))
    (eqv? f g))
                          =>  unspecified

  (letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
           (g (lambda () (if (eqv? f g) 'g 'both))))
    (eqv? f g))
                          =>  #f

定数オブジェクト(リテラル式が返すもの)を変更した場合はエラーなので、必要ならば定数間で構造を共有することが処理系には許可されている。ただしこれは必須事項ではない。したがって定数に関するeqv?の値は、処理系によって異なる場合がある。

  (eqv? '(a) '(a))                 =>  unspecified
  (eqv? "a" "a")                   =>  unspecified
  (eqv? '(b) (cdr '(a b)))         =>  unspecified
  (let ((x '(a)))
    (eqv? x x))                    =>  #t

理論的根拠:

eqv?の上記の定義により、次のように処理系ごとに手続きと リテラル式を取り扱う自由度が生まれる。処理系は二つの手続きや 二つのリテラル式が互いに等しいかどうかを検出することも検出し ないこともできる。したがって二つのオブジェクトを表す同一の ポインタもしくは同一のビットパターンを使用して、等価なオブ ジェクトの表現を一つに統合するかしないかを決定できる。

[[手続き]] (eq? obj1 obj2)

eq?eqv?に似ているが、場合によってeqv?が行なう検出よりも微妙な違いを区別できる点が異なる。

シンボル、論理値、空リスト、ペア、空でない文字列とベクタについて、eq?eqv?は同一の動作をすることが保証されている。数と文字に関するeq?の動作は処理系によって異なるが、必ず真か偽を返すことになっており、eq?が真を返す時にはeqv?も真を返す。空のベクタと空の文字列についても、eq?eqv?は異なる動作をする場合がある。

  (eq? 'a 'a)                     =>  #t
  (eq? '(a) '(a))                 =>  unspecified
  (eq? (list 'a) (list 'a))       =>  #f
  (eq? "a" "a")                   =>  unspecified
  (eq? "" "")                     =>  unspecified
  (eq? '() '())                   =>  #t
  (eq? 2 2)                       =>  unspecified
  (eq? #\A #\A)                   =>  unspecified
  (eq? car car)                   =>  #t
  (let ((n (+ 2 3)))
    (eq? n n))                    =>  unspecified
  (let ((x '(a)))
    (eq? x x))                    =>  #t
  (let ((x '#()))
    (eq? x x))                    =>  #t
  (let ((p (lambda (x) x)))
    (eq? p p))                    =>  #t

理論的根拠:

例えば決まり切った複雑な操作でなく単純にポインタを比較する ことによって、eq?eqv?よりも通常ははるかに 効率的に実装できる。その理由の一つとしては、二つの数の eqv?を一定の時間内に計算することが不可能な場合が あることが挙げられる。一方eq?をポインタの比較として 実装した場合、比較は必ず一定時間内に終了する。状態を持つ オブジェクトを実装する手続きを使用するアプリケーションでは、 eq?eqv?と同じように使用できる。この時 eq?にはeqv?と同じ制限が課せられるからである。

[[ライブラリ手続き]] (equal? obj1 obj2)

equal?は、数とシンボルのような異なるオブジェクトにeqv?を適用して、ペア、ベクタ、文字列の内容を再帰的に比較する。経験的に、表示が同一であればオブジェクトは一般にequal?である。引数が循環的データ構造の場合、equal?は終了できないことがある。

  (equal? 'a 'a)                  =>  #t
  (equal? '(a) '(a))              =>  #t
  (equal? '(a (b) c)
          '(a (b) c))             =>  #t
  (equal? "abc" "abc")            =>  #t
  (equal? 2 2)                    =>  #t
  (equal? (make-vector 5 'a)
          (make-vector 5 'a))     =>  #t
  (equal? (lambda (x) x)
          (lambda (y) y))  =>  unspecified

Lispコミュニティーは、伝統的に数値計算をないがしろにしてきた。Common Lispが現れるまで、MacLisp系以外には充分に考え尽くされた数値計算の構成戦略は存在せず、数値コードを効率的に実行する努力は払われていなかった。本報告書はCommon Lispコミュニティーが行なった優れた業績を認識し、その勧告の多くを受け入れている。本報告書はある意味で、Schemeの目的に沿うように、Common Lispの提案の単純化と一般化を行なっている。

数学的な数、そのモデル化を試みたSchemeの数、Schemeに数を実装するために使用された計算装置に適した数の表現、数を書き出すために使用された記法の、それぞれを区別することは重要である。本報告書では数学的な数とSchemeの数の両方を示す数の種類として複素数実数有理数整数を使用する。固定小数点と浮動小数点のような計算装置に適した表現は、fixnumflonumのような名前を使用して参照する。

数の種類

数は数学的に、下位の層が上位の層の部分集合であるような、複数の層を持つ 階層として組織できる。

例えば3は整数である。したがって3は有理数でもあり、実数でもあり、複素数でもある。3をモデルとしたSchemeの数についても同じことがいえる。Schemeの数の場合、以上の種類は述語手続きnumber?complex?real?rational?integer?で定義される。

数の種類とコンピュータ内部の数の表現との間に、単純な関係は存在しない。Schemeのほとんどの処理系では、3の表現について少くとも二種類の異なる方法が用意されているが、いずれの表現も同一の整数を指し示すものである。

Schemeの数値処理では、数は可能な限りその内部表現から独立した、抽象データとしてとり扱われる。数はSchemeの処理系ごとにfixnum、flonum、場合によってはそれ以外の表現を使用できるが、単純なプログラムを書く不注意なプログラマにこれが見えるようであってはならない。

ただし完全に表現される数とそうではない数を区別する必要がある。例えばデータ構造の指標は完全にわかっているものでなければならない。これはある種の記号代数学系の多項式の係数がわかっていなければならないのに似ている。一方測定結果というものはその性質上不完全であって無理数を有理数で近似する場合があり、したがってこれは不完全な近似である。完全数が必要な場所で不完全数が使用されていることを明らかにするために、Schemeでは完全数と不完全数を明示的に区別している。この区別は数の種類の次元に直交する。

完全性

Schemeの数は完全であるか、不完全であるかのいずれかである。完全な定数として書かれたか、完全な演算のみを使用して完全数から導かれた場合、数は完全である。不完全な定数として書かれたか、不完全な成分を使用して導かれたか、もしくは不完全な演算を使用して導かれた場合、数は不完全である。したがって数の不完全性という特徴は伝染する。

不完全な中間結果を含まない計算によって二つの処理系が完全な結果を生成した場合、最終的に二つの計算結果は数学的に等価になる。不完全数を含む計算については浮動小数点演算などの近似法が使用される場合があるために、二つの計算結果が等価であるということは一般に正しくない。ただし処理系はその結果を、実用上数学的に限りなく等価に近付けなければならない。

引数が完全数の時は、+のような有理演算は結果として必ず完全数を生成しなければならない。演算の結果が完全数を生成できない場合、処理系は実装上の制限の侵害を報告するか、でなければ侵害を報告せずに強制的に不完全な値を計算して生成できる。section 実装上の制限参照。

引数に不完全数が与えられた時は、inexact->exactを除いて本節に述べる演算の結果は、一般に不完全数を生成しなければならない。ただし演算結果の値が引数の不完全性に影響されないことが証明できる場合は、演算は完全数を結果として返してもよい。例えばその他の引数が不完全数であったとしても、完全なゼロを乗じたあらゆる数は、結果として完全なゼロを生成することができる。

実装上の制限

Schemeの処理系がsection 数の種類に述べるすべての階層を実装する必要はないが、処理系の目的とScheme言語の精神の両方に沿って、一貫性のある階層を実装しなければならない。例えば処理系の数をすべて実数にしたとしても、それはそれで利用価値が高い。

処理系には本節の要件にしたがう限り、いかなる種類の数であってもその一部の範囲だけをサポートすることが許される。いかなる種類の完全数についても、サポートされる完全数の範囲は、同一種類の不完全数についてサポートされる範囲と異なってよい。例えばflonumを使用してすべての不完全実数を表現する処理系は、不完全実数の範囲をflonum形式の動的な範囲に限定して(したがって不完全整数と不完全有理数の範囲を限定して)、実用上無制限の範囲の完全整数と完全有理数をサポートすることができる。そのような処理系においては以上の限定に加えて、範囲の上限と下限に近付くにしたがって、表現可能な不完全整数と不完全有理数との間の空隙が非常に大きくなる場合がある。

Schemeの処理系は、リスト、ベクタ、文字列の指標に使用される可能性がある数、もしくはリスト、ベクタ、文字列の長さの計算から生ずる可能性がある数の全範囲に渡って、完全整数をサポートしなければならない。lengthvector-lengthstring-length手続きは完全整数を返さなければならない。指標として完全整数以外を使用した場合はエラーである。さらに指標範囲外でいかなる実装上の制限が適用されるとしても、完全整数構文で表現された指標範囲内のあらゆる整数定数は、実際に完全整数として読み込まれる。最後に、すべての引数が完全整数で、数学的に予期される結果が処理系内部で完全整数として表現できる場合は、次に挙げる手続きは必ず完全整数の結果を返す。

  +              -               *
  quotient       remainder       modulo
  max            min             abs
  numerator      denominator     gcd
  lcm            floor           ceiling
  truncate       round           rationalize
  expt

処理系には実用上無制限の大きさと精度の完全整数完全有理数のサポートと上記の手続き、および完全な引数が与えられた場合に必ず完全な結果を返す手続きの実装が望ましい。ただしこれは必須ではない。完全な引数が与えられた場合に上記手続きの一つが完全な結果を返すことができない場合は、処理系は実装上の制限の侵害を報告するか、侵害を報告せずに強制的に結果を不完全数に変換することができる。この強制変換により、後で誤差が生ずる場合がある。

不完全数については、処理系は浮動小数点とその他の近似表現戦略を使用することができる。本報告書ではflonum表現を使用する処理系に、IEEEの32ビットと64ビットの浮動小数点規格にしたがうように推奨する。またその他の表現を使用する処理系は、この浮動小数点規格[IEEE]を使用した場合に実現可能な精度に合致するか、その精度を越える必要がある。ただしこれらは必須ではない。

flonum表現を使用する処理系は特に、以下の規則にしたがわなければならない。flonumの結果は、演算に与えられたあらゆる不完全引数の表現に使用された精度と、少くとも同等の精度で表現しなければならない。sqrtのような潜在的に不完全な演算が完全な引数に適用された場合は、可能な限り必ず完全な答を生成することが望ましい(例えば完全な4の自乗根は完全な2である必要がある)。ただしこれは必須ではない。しかし(sqrtのような)不完全な結果を生成する演算が完全数に行なわれ、かつその結果がflonumで表現される場合は、利用できる最も精度の高いflonumを使用しなければならない。ただし結果がflonum以外の方法で表現される場合はその表現精度は、利用できる最も精度の高いflonum形式と少くとも同等でなければならない。

数についてSchemeでは広範囲の記法が許されているが、特定の処理系はその一部だけをサポートしてもよい。例えばすべての数が実数である処理系では複素数について、直交座標記法と極座標記法をサポートする必要はない。処理系が完全数として表現できない完全な数値定数に遭遇した場合は、実装上の制限の侵害を報告するか、侵害を報告せずにその定数を不完全数で表現することができる。

数値定数の構文

数に関する記法上の表現の構文則は、section 辞書的構造で説明する。数値定数においては、大文字と小文字は区別されない点に注意する必要がある。

数は基数接頭辞を使用して、二進数、八進数、十進数、十六進数で書くことができる。基数接頭辞は、#b(二進)、#o(八進)、#d(十進)(十進)、#x(十六進)である。基数が存在しない場合、数は十進表現であると仮定される。

数値定数は接頭辞を使用して、完全数か不完全数のいずれかを指定できる。この接頭辞は完全数については#e不完全数については#iである。完全性接頭辞は、使用する基数接頭辞の前に書いても後ろに書いてもよい。数の記法上の表現に完全性接頭辞が存在しない場合、数値定数は不完全数である場合と完全数である場合がある。小数点、指数もしくは数字の代わりに"#"が表現に含まれる場合、数は不完全数である。それ以外の場合、数は完全数である。

さまざまな精度の不完全数を使用する処理系においては、定数の精度の指定が有用な場合がある。精度を指定する場合は、不完全数の表現に関する精度を示す指数標識を、数値定数に書くことができる。文字sfdlで、それぞれshort(短精度)、single(単精度)、double(倍精度)、long(長精度)を指定する。(不完全数の内部表現が四種に満たない場合、この指定は利用できる精度にマップされる。例えば内部表現が二種類の処理系では、短精度と単精度、および長精度と倍精度をそれぞれ一つの表現にマップできる。)加えて指数標識eは、処理系のデフォルトの精度を指定する。デフォルトの精度は少くとも倍精度と同等のものとするが、処理系がユーザにデフォルトを設定させてもよい。

  3.14159265358979F0
         Round to single -- 3.141593
  0.6L0
         Extend to long -- .600000000000000

数値演算

数値ルーチンに渡す引数の型に関する制限の指定に使用される命名規約については、section 見出しの形式に要約を載せている。本節に使用する例では、完全数の記法を使用して書かれたあらゆる数値定数は、完全数として表現されると仮定している。例によっては、不完全数の記法を使用して書かれた数値定数は、精度を失わずに表現できると仮定しているものもある。不完全数値定数は、不完全数の表現にflonumを使用する処理系でおそらく正しくなるように選択された。

[[手続き]] (number? obj)
[[手続き]] (complex? obj)
[[手続き]] (real? obj)
[[手続き]] (rational? obj)
[[手続き]] (integer? obj)

上記の数値型述語手続きは、数値以外のものを含むあらゆる種類の引数に適用できる。オブジェクトが名前を指定された型であれば#tを返し、それ以外の場合は#fを返す。一般に数についてのある型の述語手続きが真であれば、その数についての上位の述語手続きも真である。

したがって数についてのある型の述語手続きが偽であれば、その数についての下位の述語手続きも偽である。

zを不完全な複素数とすれば、(zero? (imag-part z))が真の場合にのみ(real? z)は真である。zが不完全な実数の場合は、(= x (round x))が真ならばその場合にのみ(integer? x)は真である。

  (complex? 3+4i)         =>  #t
  (complex? 3)            =>  #t
  (real? 3)               =>  #t
  (real? -2.5+0.0i)       =>  #t
  (real? #e1e10)          =>  #t
  (rational? 6/10)        =>  #t
  (rational? 6/3)         =>  #t
  (integer? 3+0i)         =>  #t
  (integer? 3.0)          =>  #t
  (integer? 8/4)          =>  #t

注: 不完全数に関しては誤差によって結果が変わる場合があるために、上記の型述語手続きの振舞いは信頼できない。

注: 多くの処理系ではrational?手続きはreal?手続きと、complex?手続きはnumber?手続きと等しくなる。ただし特殊な処理系ではある種の無理数を正確に表現できたり、複素数以外のある種の数をサポートするように数体系を拡張する場合がある。

[[手続き]] (exact? z)
[[手続き]] inexact? z)

以上の数値述語手続きは、量の完全性をテストするものである。Schemeのいかなる数も、この述語手続きのいずれか一つが正確に真になる。

[[手続き]] (= z1 z2 z3 ...)
[[手続き]] (< x1 x2 x3 ...)
[[手続き]] (> x1 x2 x3 ...)
[[手続き]] (<= x1 x2 x3 ...)
[[手続き]] (>= x1 x2 x3 ...)

以上の手続きは引数がそれぞれ、等しいか、単調に増加するか、単調に減少するか、単調に減少しないか、単調に増加しない場合に#tを返す。

これらは推移的(27)でなければならない。

注: 従来のLispライクな言語に実装された上記の述語手続きは、推移的ではない。

注: 上記述語手続きを使用して不完全数を比較することはエラーではないが、小さな誤差で結果が変わる場合があるために、その結果は信頼できない。疑いがある時は数値アナリストに相談してほしい。

[[ライブラリ手続き]] (zero? z)
[[ライブラリ手続き]] (positive? x)
[[ライブラリ手続き]] (negative? x)
[[ライブラリ手続き]] (odd? n)
[[ライブラリ手続き]] (even? n)

以上の数値述語手続きは、数が特定の属性を持つかどうかをテストして#tか#fを返す。上記の注参照。

[[ライブラリ手続き]] (max x1 x2 ...)
[[ライブラリ手続き]] (min x1 x2 ...)

以上の手続きは引数の中の最大値か最小値を返す。

    (max 3 4) => 4 ; 完全数
    (max 3.9 4) => 4.0 ; 不完全数%

注: 引数の中に不完全数が存在する場合は、(誤差が結果を変えるほど大きくないことを手続きが証明できない限り---これは特殊な処理系でのみ可能である)結果も不完全数になる。完全性が混在する数の比較にminもしくはmaxを使用して、かつ精度を失わずに不完全数として結果の値を表現することができない場合は、手続きは実装上の制限の侵害を報告することができる。

[[手続き]] (+ z1 ...)
[[手続き]] (* z1 ...)

上記手続きは引数の和もしくは積を返す。

  (+ 3 4)                 =>  7
  (+ 3)                   =>  3
  (+)                     =>  0
  (* 4)                   =>  4
  (*)                     =>  1
[[手続き]] (- z1 z2)
[[手続き]] (- z)
[[オプション手続き]] (- z1 z2 ...)
[[手続き]] (/ z1 z2)
[[手続き]] (/  z)
[[オプション手続き]] (/ z1 z2 ...)
  (- 3 4)                 =>  -1
  (- 3 4 5)               =>  -6
  (- 3)                   =>  -3
  (/ 3 4 5)               =>  3/20
  (/ 3)                   =>  1/3
[[ライブラリ手続き]] (abs x)

absは引数の大きさを返す。

  (abs -7)                =>  7
[[手続き]] (quotient n1 n2)
[[手続き]] (remainder n1 n2)
[[手続き]] (modulo n1 n2)

以上の手続きは整数論的な(もしくは整数の)除算を実装するものである。n2はゼロであってはならない。手続きは3つとも整数を返す。n1/n2が整数ならば次が成立する。

  (quotient n1 n2)   => n1/n2
  (remainder n1 n2)  => 0
  (modulo n1 n2)     => 0

n1/n2が整数でないならば次が成立する。

  (quotient n1 n2)   => n_q
  (remainder n1 n2)  => n_r
  (modulo n1 n2)     => n_m

ただしn_qはゼロ側に丸めたn1/n2。0 < |n_r| < |n2|、0 < |n_m| < |n2|とする。n_rとn_mはn1からn2の倍数だけ異なり、n_rの符号はn1に同じく、n_mの符号はn2に同じとする。

以上から整数n1とn2について、n2がゼロに等しくないとすれば、以下を導くことができる。

     (= n1 (+ (* n2 (quotient n1 n2))
           (remainder n1 n2)))
                                 =>  #t

ただし演算に関係するすべての数は完全数とする。

  (modulo 13 4)           =>  1
  (remainder 13 4)        =>  1

  (modulo -13 4)          =>  3
  (remainder -13 4)       =>  -1

  (modulo 13 -4)          =>  -3
  (remainder 13 -4)       =>  1

  (modulo -13 -4)         =>  -1
  (remainder -13 -4)      =>  -1

  (remainder -13 -4.0)    =>  -1.0  ; 不完全数
[[ライブラリ手続き]] (gcd n1 ...)
[[ライブラリ手続き]] (lcm n1 ...)

以上の手続きは、引数の最大公約数と最小公倍数を返す。結果は必ず非負の数である。

  (gcd 32 -36)            =>  4
  (gcd)                   =>  0
  (lcm 32 -36)            =>  288
  (lcm 32.0 -36)          =>  288.0  ; 不完全数
  (lcm)                   =>  1
[[手続き]] (numerator q)
[[手続き]] (denominator q)

以上の手続きは引数の分子もしくは分母を返す。結果は引数が規約分数であるかのように計算される。分母は常に正である。0の分母は1に定義される。

  (numerator (/ 6 4))         =>  3
  (denominator (/ 6 4))       =>  2
  (denominator
    (exact->inexact (/ 6 4))) => 2.0
[[手続き]] (floor x)
[[手続き]] (ceiling x)
[[手続き]] (truncate x)
[[手続き]] (round x)

以上の手続きは整数を返す。floorはxよりも大きくない最大の整数を返す。celingはxよりも小さくない最小の整数を返す。 truncateは絶対値がxの絶対値よりも大きくない、xに最も近い整数を返す。roundはxが二つの整数の中間にある場合でもそれを丸めて、xに最も近い整数を返す。

理論的根拠:

roundは、IEEE浮動小数点規格に指定されるデフォルトの 丸めモードと一貫性を保つように、数値を丸める。

注: 以上の手続きの引数が不完全数の場合は結果も不完全数である。完全数が必要な場合は、結果をinexact->exact手続きにかける必要がある。

  (floor -4.3)          =>  -5.0
  (ceiling -4.3)        =>  -4.0
  (truncate -4.3)       =>  -4.0
  (round -4.3)          =>  -4.0

  (floor 3.5)           =>  3.0
  (ceiling 3.5)         =>  4.0
  (truncate 3.5)        =>  3.0
  (round 3.5)           =>  4.0  ; 不完全数

  (round 7/2)           =>  4    ; 完全数
  (round 7)             =>  7
[[ライブラリ手続き]] (rationalize x y)

rationalizeは、y以上にはxと異ならない最も単純な有理数を返す。r1 = p1/q1かつr2 = p2/q2(規約分数)で、|p1| <= |p2|かつ|q1| <= |q2|ならば、有理数r1はもう一つの有理数r2よりも単純である。したがって3/5は4/7よりも単純である。すべての有理数がこの順にしたがうとは限らないが(2/7と3/5参照)、すべての区間には、その区間のその他すべての有理数よりも単純な有理数が一つ含まれる(2/7と3/5の間にはより単純な2/5が存在する)。0 = 0/1は、すべての有理数の中で最も単純であることに注意する必要がある。

  (rationalize
    (inexact->exact .3) 1/10)  => 1/3   ;完全数
  (rationalize .3 1/10)        => #i1/3 ;不完全数
[[手続き]] (exp z)
[[手続き]] (log z)
[[手続き]] (sin z)
[[手続き]] (cos z)
[[手続き]] (tan z)
[[手続き]] (asin z)
[[手続き]] (acos z)
[[手続き]] (atan z)
[[手続き]] (atan y x))

以上の手続きは、実数全般をサポートするすべての処理系に実装され、通常の超越関数を計算する。logは、zの(常用対数ではなく)自然対数を計算する。asinacosatanはそれぞれ、arcsine(sin^-1)、acrcosine(cos^-1)、arctangent(tan^-1)を計算する。引数を二つ取るatanの別形は、複素数全般をサポートしない処理系においても、(angle (make-rectangular x y))(下記参照)を計算する。

一般に数学関数log、arcsine、arccosine、arctangentは、多重定義である。log(z)の値は、虚部が-pi(-piを除く)からpi(piを含む)の範囲にあるものとして定義される。log(0)は無定義である。logをこのように定義した場合、sin^-1(z)、cos^-1(z)、tan^-1(z)の値は次の式の通りとなる。

  sin^-1(z) = -i*log(i*z + sqrt(1 - z^2))
  cos^-1(z) = pi/2 - sin^-1(z)
  tan^-1(z) = (log(1 + i*z) - log(1 - i*z)) / (2*i)

以上の仕様は[CLTL]にしたがうものであり、[CLTL]はさらに[PENFIELD81]を引用している。分岐線法、境界条件、および上記関数の実装の詳細な検討については、原典にあたっていただきたい。上記手続きは、可能な時は実数引数から実数の結果を生成する。

[[手続き]] (sqrt z)

zの主平方根を返す。結果は正の実部か、実部がゼロの非負の虚部になる。

[[手続き]] (expt z1 z2)

z1のz2乗を返す。z1 =/= 0ならば、

  z1^z2 = e^(z2*log(z1))

である。

0^zはz = 0ならば1、さもなければ0である。

[[手続き]] (make-rectangular x1 x2)
[[手続き]] (make-polar x3 x4)
[[手続き]] (real-part z)
[[手続き]] (imag-part z)
[[手続き]] (magnitude z)
[[手続き]] (angle z)

以上の手続きは、複素数全般をサポートするすべての処理系に実装される。x1、x2、x3、x4が実数、zが複素数で次を満足するとすれば、

  z = x1 + x2*i = x3 * e^(i*x4)
  (make-rectangular x1 x2) => z
  (make-polar x3 x4)     => z
  (real-part z)                  => x1
  (imag-part z)                  => x2
  (magnitude z)                  => |x3|
  (angle z)                      => x_angle

が返される。ただしある整数nに対してx_angle = x4 + 2*pi*nとして、-pi < x_angle <= piである。

理論的根拠:

magnitudeは実数引数に対してはabsと同じもの である。ただしabsはすべての処理系が実装しなければ ならないが、magnitudeは複素数全般をサポートする 処理系にのみ実装される。

[[手続き]] (exact->inexact z)
[[手続き]] (inexact->exact z)

exact->inexactはzの不完全数表現を返す。返される値は数値的に引数に最も近い不完全数である。完全数引数にに近い適当な等価な不完全数が存在しない場合は、実装上の制限の侵害を報告することができる。

inexact->exactはzの完全数表現を返す。返される値は数値的に引数に最も近い完全数である。不完全数引数にに近い適当な等価な完全数が存在しない場合は、実装上の制限の侵害を報告することができる。

以上の手続きは、処理系に応じた全領域にわたって、完全整数と不完全整数の自然な一対一対応を実装するものである。section 実装上の制限参照。

数値の入出力

[[手続き]] (number->string number)
[[手続き]] (number->string number radix)

radix(基数)は完全整数で、2、8、10、もしくは16でなければならない。省略した場合、基数はデフォルトの10に設定される。手続きnumber->stringは数と基数の引数をそれぞれ一つづつ取って。その数とその基数による外部表現を、次の式が真となるような文字列として返す。

  (let ((number number)
        (radix radix))
    (eqv? number
          (string->number (number->string number
                                          radix)
                          radix)))

上の式が真となる結果が存在しない場合はエラーである。

zが不完全数、基数が10で小数点を含む結果が上記の式を満足すれば、結果には小数点が含まれ、上記の式が真になる[HOWTOPRINT]、[HOWTOREAD]ために必要な最小の桁数を使用して結果が表現される(指数と後続する0を除く)。さもなければ結果の形式は不定である。

number->stringが返す結果に明示的に基数接頭辞が含まれること はない。

注: エラー状況はzが複素数でないか、複素数であってもその実部か虚部が有理数でない場合にだけ、発生できる。

理論的根拠:

zがflonumを使用して表現される不完全数で基数が10であれば、 結果に小数点を含めることによって上記の式は通常満足される。 無限大Nanと flonum表現については、結果を不定とする状況が 用意されている。

[[手続き]] (string->number string)
[[手続き]] (string->number string radix)

渡された文字列が表す数を、最大精度の表現で返す。基数radixは2、8、10、16のいずれかの完全数でなければならない。基数が与えられた場合はそれがデフォルトの基数となり、これは文字列内の基数接頭辞(例えば"#o177")で明示的に上書きすることができる。基数が与えられていない場合のデフォルトの基数は10である。数について文字列が文法的に有効な記法でない場合は、 string->numberは#fを返す。

  (string->number "100")        =>  100
  (string->number "100" 16)     =>  256
  (string->number "1e2")        =>  100.0
  (string->number "15##")       =>  1500.0

注: 処理系は次のように、string->numberの定義域を制限する場合がある。文字列に明示的な基数が含まれる時は、string->numberは常に#fを返すことができる。サポートするすべての数が実数である処理系では、複素数の記法として文字列に極形式記法か矩形形式記法が使用された時は、string->numberは常に#fを返すことができる。すべての数が整数の処理系では、記法に分数が使用された時は、string->numberは常に#fを返すことができる。すべての数が完全数の処理系では、指数標識もしくは明示的な完全性接頭辞が使用された時、もしくは数字の代わりに#が書かれた場合でも、 string->numberは常に#fを返すことができる。すべての不完全数が整数の処理系では、小数点が使用された時は、string->numberは常に#fを返すことができる。

その他のデータ型

本節ではSchemeの数値以外のデータ型、すなわち論理型、ペア型、リスト型、シンボル型、文字型、文字列型、ベクタ型のあるものについての演算を説明する。

論理式

真と偽に対する論理オブジェクトは#tと#fと書く。ただし実際に重要なものは、Schemeの条件式(ifcondandordo)が真または偽として処理するオブジェクトである。語句"真値"(単に"真"という場合もある)は、条件式が真として処理するあらゆるオブジェクトを意味する。語句"偽値"(単に"偽"という場合もある)は、条件式が偽として処理するあらゆるオブジェクトを意味する。

Schemeのすべての標準の値の内で、#fだけが条件式の中で偽と判断される。#fを除くSchemeのすべての標準の値は真と判断される。これには#t、ペア、空リスト、シンボル、数、文字列、ベクタ、手続きが含まれる。

注: Scheme以外のLisp方言に慣れているプログラマは、Schemeでは#fと空リストの両方とも、シンボルnilとは異なっていることに注意しなければならない。

論理定数はそれ自身に評価される。したがってプログラム内でクォートをつける必要はない。

  #t        =>  #t
  #f        =>  #f
  '#f       =>  #f
[[ライブラリ手続き]] (not  obj)

notはobjが偽であれば#tを返し、それ以外では#f を返す。

  (not #t)         =>  #f
  (not 3)          =>  #f
  (not (list 3))   =>  #f
  (not #f)         =>  #t
  (not '())        =>  #f
  (not (list))     =>  #f
  (not 'nil)       =>  #f
[[ライブラリ手続き]] (boolean?  obj)

boolean?はobjが#tか#fのいずれかであれば#tを返し、それ以外の場合は#fを返す。

  (boolean? #f)         =>  #t
  (boolean? 0)          =>  #f
  (boolean? '())        =>  #f

ペアとリスト

ペア(ドットペアと呼ばれることもある)は、car(カー)とcdr(クダー)と呼ばれる二つのフィールドを持つレコード構造である。carとcdrは歴史的にそう呼び慣わされている。ペアはcons手続きで作成される。carフィールドとcdrフィールドは、それぞれ手続きcarcdrで取り出される。carフィールドとcdrフィールドには、それぞれ手続きset-car!set-cdr!で代入が行なわれる。

ペアは主としてリストを表現するのに使用される。リストは空リストであるか、cdrがリストであるペアとして再帰的に定義できる。さらに厳密にいえば、リストの集合は次のような最小の集合Xとして定義される。

リストは連続するペアで構成され、各ペアのcarフィールドに含まれるオブジェクトがそのリストの要素である。例えば要素が二つのリストとは、リストの最初の要素であるcarとペアcdrで構成されるペアである。そのcdrは、carがリストの第2の要素であり、cdrのcdrが空のリストである。リストの長さは要素の数で、これはペアの数に等しい。

空のリストはこの型の中の特別のオブジェクトである(これはペアではない)。空のリストに要素はなく、その長さはゼロである。

注: 上記の定義は、リストがすべて有限の長さで、空のリストで終ることを意味している。

Schemeのペアのもっとも一般的な記法(外部表現)は"ドット付"記法(c1 . c2)である。ここにc1はcarフィールドの値、c2はcdrフィールドの値である。例えば(4 . 5)は、carが4でcdrが5のペアである。(4 . 5)はペアの外部表現であって、ペアに評価される式ではないことに注意しなければならない。

リストにはもっと簡素な記法が使用できる。リストの要素を単に空白で区切って小括弧で囲む。空のリストは()と書く。次に例を示す。

  (a b c d e)と
  (a . (b . (c . (d . (e . ())))))

はシンボルのリストについての等価な記法である。最後が空のリストでない一連のペアは、変則リストと呼ばれる。変則リストはリストではないことに注意しなければならない。リストとドット記法を組み合わせて、変則リストを書くことができる。

  (a b c . d)と
  (a . (b . (c . d))) 

とは等価である。

ペアがリストであるかどうかは、cdrフィールドに何が保管されているかによる。set-cdr!手続きを使用した時は、その瞬間リストであったものが次の瞬間にはリストでなくなる場合がある。

  (define x (list 'a 'b 'c))
  (define y x)
  y                       =>  (a b c)
  (list? y)               =>  #t
  (set-cdr! x 4)          =>  unspecified
  x                       =>  (a . 4)
  (eqv? x y)              =>  #t
  y                       =>  (a . 4)
  (list? y)               =>  #f
  (set-cdr! x x)          =>  unspecified
  (list? x)               =>  #f

read手続きが読み込むリテラル式とオブジェクトの外部表現の内部では、'<データ>、`<データ>、,<データ>、,@<データ>は2要素リストを指す。その第一要素はそれぞれシンボル quotequasiquoteunquoteunquote-splicingであり、いずれの場合もその第二要素は<データ>である。この規約は、任意のSchemeプログラムをリストで表現できるように用意したものである。Schemeの文法では、すべての<式>は<データ>でもある(section 外部表現参照)。数ある特徴の中でもこれによって、read手続きを使用してSchemeプログラムを解析することができる。section 外部表現参照。

[[手続き]] (pair? obj)

pair?はobjがペアであれば#tを返し、それ以外の場合は#fを返す。

  (pair? '(a . b))        =>  #t
  (pair? '(a b c))        =>  #t
  (pair? '())             =>  #f
  (pair? '#(a b))         =>  #f
[[手続き]] (cons obj1 obj2)

この手続きはペアを新しく割り当てて返し、そのcarはobj1、cdrはobj2である。このペアは、既存のすべてのオブジェクトとは(eqv?の意味で)異なることが保証されている。

  (cons 'a '())           =>  (a)
  (cons '(a) '(b c d))    =>  ((a) b c d)
  (cons "a" '(b c))       =>  ("a" b c)
  (cons 'a 3)             =>  (a . 3)
  (cons '(a b) 'c)        =>  ((a b) . c)
[[手続き]] (car pair)

この手続きはpairのcarフィールドの内容を返す。空リストのcarを取った場合はエラーであることに注意しなければならない。

  (car '(a b c))          =>  a
  (car '((a) b c d))      =>  (a)
  (car '(1 . 2))          =>  1
  (car '())               =>  error
[[手続き]] (cdr pair)

この手続きはpairのcdrフィールドの内容を返す。空リストのcdrを取った場合はエラーであることに注意しなければならない。

  (cdr '((a) b c d))      =>  (b c d)
  (cdr '(1 . 2))          =>  2
  (cdr '())               =>  error
[[手続き]] (set-car! pair obj)

この手続きはpairのcarフィールドにobjを保管する。set-car!が返す値は不定である。

  (define (f) (list 'not-a-constant-list))(28)
  (set-car! (f) 3) => unspecified
  (29)
  (set-car! (g) 3) => error
  (30)
[[手続き]] (set-cdr! pair obj)

この手続きはpairのcdrフィールドにobjを保管する。set-cdr!が返す値は不定である。

[[ライブラリ手続き]] (caar pair)
[[ライブラリ手続き]] (cadr pair)
    ...                   ...
[[ライブラリ手続き]] (cdddar pair)
[[ライブラリ手続き]] (cddddr pair)

以上の手続きはcarcdrの組合せである。例えばcaddrは次のように定義される。

  (define caddr (lambda (x) (car (cdr (cdr x)))))

深さ4までの任意の組合せが用意されており、このような手続きは合計28ある。

[[ライブラリ手続き]] (null? obj)

objが空リストの時に#tを返し、それ以外の場合は#fを返す。

[[ライブラリ手続き]] (list? obj)

objがリストの場合は#tを返し、それ以外の場合は#fを返す。定義上すべてのリストは長さが有限で、終端は空リストである。

 (list? '(a b c))     =>  #t
 (list? '())          =>  #t
 (list? '(a . b))     =>  #f
 (let ((x (list 'a)))
   (set-cdr! x x)
   (list? x))         =>  #f
[[ライブラリ手続き]] (list obj ...)

引数を新しく割り当てたリストにして返す。

  (list 'a (+ 3 4) 'c)            =>  (a 7 c)
  (list)                          =>  ()
[[ライブラリ手続き]] (length list)

リストlistの長さを返す。

  (length '(a b c))               =>  3
  (length '(a (b) (c d e)))       =>  3
  (length '())                    =>  0
[[ライブラリ手続き]] (append list ...)

最初のリストlistの要素にその他のリストの要素を続けたものを要素とするリストを返す。

  (append '(x) '(y))              =>  (x y)
  (append '(a) '(b c d))          =>  (a b c d)
  (append '(a (b)) '((c)))        =>  (a (b) (c))

結果のリストは、最後のリスト引数と構造を共有する場合を除いて、必ず新しく割り当てられる。最後のリストは実際にはいかなるオブジェクトでもよい。最後のリストが正しいリストでない場合は、変則リストが生成される。

  (append '(a b) '(c . d))        =>  (a b c . d)
  (append '() 'a)                 =>  a
[[ライブラリ手続き]] (reverse list)

listの要素を逆順にしたリストを新しく割り当てて返す。

  (reverse '(a b c))              =>  (c b a)
  (reverse '(a (b c) d (e (f))))  =>  ((e (f)) d (b c) a)
[[ライブラリ手続き]]  (list-tail list k)

listから最初のk個の要素を取り除いた部分リストを返す。listの要素数がk個より少い場合はエラーである。list-tailは次のように定義できる。

(define list-tail
  (lambda (x k)
    (if (zero? k)
        x 
        (list-tail (cdr x) (- k 1)))))
[[ライブラリ手続き]] (list-ref list k)

listのk番目の要素を返す。(これは(list-tail list k)のcarに等しい)。listの要素数がk個より少かった場合はエラーである。

  (list-ref '(a b c d) 2)                 =>  c
  (list-ref '(a b c d)
            (inexact->exact (round 1.8))) =>  c
[[ライブラリ手続き]] (memq obj list)
[[ライブラリ手続き]] (memv obj list)
[[ライブラリ手続き]] (member obj list)

以上の手続きは、carがobjであるlistの部分リストを返す。ただしこの部分リストは、kがlistの長さ未満の場合に(list-tail list k)が返す空でないリストとする。objがlistに存在しなかった場合は、(空リストでなく)#fが返される。objとlistとの比較にmemqeq?を使用するが、memveqv?を、memberequal?を使用する。

  (memq 'a '(a b c))              =>  (a b c)
  (memq 'b '(a b c))              =>  (b c)
  (memq 'a '(b c d))              =>  #f
  (memq (list 'a) '(b (a) c))     =>  #f
  (member (list 'a)
          '(b (a) c))             =>  ((a) c)
  (memq 101 '(100 101 102))       =>  unspecified
  (memv 101 '(100 101 102))       =>  (101 102)
[[ライブラリ手続き]] (assq obj alist)
[[ライブラリ手続き]] (assv obj alist)
[[ライブラリ手続き]] (assoc obj alist)

alist("association list" = 連想リスト)はペアのリストでなければならない。上記手続きはcarフィールドがobjである最初のペアを検索して、そのペアを返す。alistにcarがobjであるようなペアが存在しない場合は、(空リストではなく)#fが返される。各ペアのcarフィールドとobjとを比較するにあたって、assqeq?を使用する。一方 assveqv? を、assoceequal?を使用する。

  (define e '((a 1) (b 2) (c 3)))
  (assq 'a e)                =>  (a 1)
  (assq 'b e)                =>  (b 2)
  (assq 'd e)                =>  #f
  (assq (list 'a) '(((a)) ((b)) ((c))))
                             =>  #f
  (assoc (list 'a) '(((a)) ((b)) ((c))))
                             =>  ((a))
  (assq 5 '((2 3) (5 7) (11 13)))
                             =>  unspecified
  (assv 5 '((2 3) (5 7) (11 13)))
                             =>  (5 7)

理論的根拠:

memqmemvmemberassqassvassocは通常述語手続きとして使用される ものであるが、名前に疑問符が含まれていない。これらは単に #tか#fを返すのではなく、利用価値のある値を返すからである。

シンボル

シンボルは、二つのシンボルの名前と綴が同一の場合にのみ、(eqv?の意味で)その二つのシンボルが同一である点に利用価値があるオブジェクトである。これはプログラム内で識別子を表すのに必要な特徴である。したがってSchemeのほとんどの処理系では、その目的のために内部的にシンボルを使用している。シンボルはこれ以外の多くの応用にも利用価値が高い。例えばPascalで使用される列挙型の値のように使用することができる。

シンボルの表現規則は、識別子の表現規則と正確に等しい。section 識別子とsection 辞書的構造参照。

リテラル式の一部として返されるか、もしくはread手続きを使用して読み込まれ、その後write手続きを使用して書き込まれたいかなるシンボルも、(eqv?の意味で)同一シンボルとしてもう一度読み込まれることが保証されている。ただしstring->symbol手続きでは、write/readのこの不変性が維持されないシンボルが作成される場合がある。この手続きで標準以外の文字を使用して作成された名前には、特殊文字が含まれるからである。

注: Schemeの処理系によっては、すべてのシンボルにwrite/readの不変性を保証するために、"スラッシュ化"(slashification)(31)として知られる機能を備えているものがある。ただし歴史的にはこの機能の重要な利用法の大部分は、文字列データ型の不備を補うことであった。

処理系によっては"未登録のシンボル"(32)を使用するものがあり、これはスラッシュ化を使用する処理系においてもwrite/readの不変性を破壊するものである。二つのシンボルの名前と綴が同一の場合にのみシンボルは等しいという規則にも例外が発生する。

[[手続き]] (symbol? obj)

objがシンボルの場合に#tを返し、それ以外の場合は#fを返す。

  (symbol? 'foo)          =>  #t
  (symbol? (car '(a b)))  =>  #t
  (symbol? "bar")         =>  #f
  (symbol? 'nil)          =>  #t
  (symbol? '())           =>  #f
  (symbol? #f)            =>  #f
[[手続き]] (symbol->string symbol)

シンボルsymbolの名前を文字列として返す。シンボルがリテラル式(section リテラル式参照)の値として返されるオブジェクトの一部もしくはread手続きの呼び出しで返されるオブジェクトで、かつ名前にアルファベット文字が含まれる場合、この文字列には標準の文字が入る。標準の文字が大文字であるか小文字であるかは、処理系が決定する。処理系によって、小文字に統一される場合と大文字に統一される場合がある。シンボルがstring->symbolによって返される場合は、string->symbolに渡される文字が大文字であれば大文字が、小文字であれば小文字が返される。この手続きが返す文字列に、string-set!などの変更手続きを使用した場合はエラーである。

以下の例は、処理系の標準文字が小文字であると仮定した場合である。

  (symbol->string 'flying-fish)
                                    =>  "flying-fish"
  (symbol->string 'Martin)          =>  "martin"
  (symbol->string
     (string->symbol "Malvina"))
                                    =>  "Malvina"
[[手続き]] (string->symbol string)

名前が文字列stringであるシンボルを返す。この手続きは標準以外の文字集合の場合に名前に特殊文字が含まれるシンボルを作成できるが、そのようなシンボルを作成することは通常好ましい発想ではない。処理系によってはそのようなシンボルを読み込めないものがあるからである。symbol->string参照。

以下の例では標準文字が小文字であることを仮定している。

  (eq? 'mISSISSIppi 'mississippi)     =>  #t
  (string->symbol "mISSISSIppi")      =>  the symbol with name "mISSISSIppi"
  (eq? 'bitBlt (string->symbol "bitBlt"))
                                      =>  #f
  (eq? 'JollyWog
       (string->symbol
         (symbol->string 'JollyWog))) =>  #t
  (string=? "K. Harper, M.D."
            (symbol->string
              (string->symbol "K. Harper, M.D.")))
                                      =>  #t

文字型

文字型は、文字と数字などの印字文字を表すオブジェクトである。文字型は記法#\<文字もしくは#\<文字名>を使用して書かれる。例えば次の通りである。

  #\a       ; 小文字
  #\A       ; 大文字
  #\(       ; 左小括弧
  #\        ; スペース
  #\space   ; スペースを書く望ましい方法
  #\newline ; newline文字

大文字と小文字の別は#\<文字>の場合は意味を持つが、#\<文字名>では意味を持たない。#\<文字名>内の<文字>がアルファベットの場合は、<文字>に続く文字列はスペースや括弧などの区切り文字でなければならない。この規則により例えば文字列"#\space"が、スペース文字を表すのか、それとも文字を表す"#\s"にシンボル"pace"が後続したものか、いずれにも解釈できるといった曖昧さが避けられる。

#\記法で書かれた文字はそれ自身に評価されるので、プログラム内でクォート(')をつける必要はない。

文字を扱う手続きの中には大文字と小文字を区別しないものがある。大文字と小文字を無視する手続きは、名称の中に"-ci"("case insensitive")が入っている。

[[手続き]] (char? obj)

objが文字の場合には#tを返し、それ以外の場合には#fを返す。

[[手続き]] (char=? char1 char2)
[[手続き]] (char<? char1 char2)
[[手続き]] char>? char1 char2)
[[手続き]] (char<=? char1 char2)
[[手続き]] (char>=? char1 char2)

以上の手続きのためには文字集合に関する完全な順序付けが必要である。順序づけが完全に行なわれていれば以下が保証される。

処理系によっては以上の手続きを一般化して、対応する数値述語手続きのように三つ以上の引数を取るようにしているものがある。

[[ライブラリ手続き]] (char-ci=? char1 char2)
[[ライブラリ手続き]] (char-ci<? char1 char2)
[[ライブラリ手続き]] (char-ci>? char1 char2)
[[ライブラリ手続き]] (char-ci<=? char1 char2)
[[ライブラリ手続き]] (char-ci>=? char1 char2)

以上の手続きはchar=?その他に似ているが、大文字と小文字を同一のものとして処理するものである。例えば(char-ci=? #\A #\a)は#tを返す。処理系によっては手続きを一般化して、対応する数値述語手続きのように三つ以上の引数を取るようにしているものがある。

[[ライブラリ手続き]] (char-alphabetic? char)
[[ライブラリ手続き]] (char-numeric? char)
[[ライブラリ手続き]] (char-whitespace? char)
[[ライブラリ手続き]] (char-upper-case? letter)
[[ライブラリ手続き]] (char-lower-case? letter)

以上の手続きはそれぞれ、引数がアルファベット、数字、空白文字、大文字、小文字の場合に#tを返し、それ以外の場合は#fを返す。ASCII文字集合に固有の以下の注は、参考指針として述べるものである。アルファベット文字は大文字と小文字を合わせて52ある。数字は十進数で10ある。空白文字はスペース文字、タブ文字、改行文字、改ページ文字、キャリッジリターンである。

[[手続き]] (char->integer char)
[[手続き]] (integer->char n)

文字を渡されると、char->integerはその文字の完全数による整数表現を返す。char->integerのもとでの文字イメージである完全整数を渡されると、integer->charは該当する文字を返す。以上の手続きはchar<=?による順序づけのもとで文字集合間に、<=による順序づけのもとで整数の部分集合の一部に、それぞれ順序を保存した同型写像(33)を実装するものである。すなわち

  (char<=? a b) => #t  かつ  (<= x y) => #t

であり、かつxとyがinteger->charの定義 域内にあれば、

(<= (char->integer a)
    (char->integer b))              =>  #t

(char<=? (integer->char x)
         (integer->char y))         =>  #t

である。

[[ライブラリ手続き]] (char-upcase char)
[[ライブラリ手続き]] (char-downcase char)

以上の手続きは、(char-ci=? char char2)である文字char2を返す。さらにcharがアルファベット文字である場合は、char-upcaseの結果は大文字、char-downcaseの結果は小文字である。

文字列

文字列は、文字が連続したものである。文字列は、文字の連続を二重引用符(")で括って書く。文字列内部の二重引用符は、エスケープ文字バックスラッシュ(\)を使用した場合にのみ書くことができる。例えば次のようになる。

  "The word \"recursion\" has many meanings."

文字列内部のバックスラッシュは、バックスラッシュをもう一つ使用してエスケープした場合にのみ書くことができる。文字列内部で二重引用符やバックスラッシュが後続しない単独のバックスラッシュの効果については、Schemeは指定していない。

文字列定数は二行に跨って連続することができるが、そのような文字列の正確な内容は不定である。

文字列の長さは、その中に入っている文字の数である。この数は非負の整数で、文字列が作成された時に確定する。文字列の有効な指標は、文字列の長さ未満の非負の完全整数である。文字列の最初の文字の指標は0で始まり、二番目の文字の指標は1、以下同様である。

"指標startで始まり指標endで終る<文字列>"のような語句による表現をした場合は、指標startは指標に含まれ、指標endは指標に含まれない。したがってstartとendが同一の指標である場合は長さゼロの部分文字列が参照され、startがゼロでendが文字列の長さである場合は文字列全体が参照される。

文字列に作用する手続きの中には、大文字と小文字の違いを無視するものがある。大文字と小文字を無視する手続きの名前には"-ci"("case insensitive")が入る。

[[手続き]] (string? obj)

objが文字列の場合に#tを返し、それ以外の場合は#fを返す。

[[手続き]] (make-string k)
[[手続き]] (make-string k  char)

make-stringは、長さkの文字列を新しく割り当てて返す。charが与えられた時は、文字列の要素がすべてそのcharで初期化される。それ以外の場合は文字列の内容は不定である。

[[ライブラリ手続き]] (string char ...)

引数で構成される文字列を新しく割り当てて返す。

[[手続き]] (string-length string)

渡された文字列stringの長さを返す。

[[手続き]] (string-ref string k)

kは、有効な<文字列>指標でなければならない。string-refは、開始値をゼロとする指標を使用して指標kの文字を返す。

[[手続き]] (string-set! string k  char)

kは有効な文字列指標でなければならない。string-set!は文字列stringの指標kの要素に文字charを格納して、不定の値を返す。

  (define (f) (make-string 3 #\*))
  (define (g) "***")
  (string-set! (f) 0 #\?)  =>  unspecified
  (string-set! (g) 0 #\?)  =>  error
  (string-set! (symbol->string 'immutable)
               0
               #\?)  =>  error
[[ライブラリ手続き]] (string=? string1 string2)
[[ライブラリ手続き]] (string-ci=? string1 string2)

二つの文字列が同一の長さで、かつ同一の文字が同一の場所に入っている場合に#tを返す。それ以外の場合は#fを返す。string-ci=?は大文字と小文字を同一文字であるかのように処理するが、string=?では大文字と小文字が異なる文字として処理される。

[[ライブラリ手続き]] (string<? string1 string2)
[[ライブラリ手続き]] (string>? string1 string2)
[[ライブラリ手続き]] (string<=? string1 string2)
[[ライブラリ手続き]] (string>=? string1 string2)
[[ライブラリ手続き]] (string-ci<? string1 string2)
[[ライブラリ手続き]] (string-ci>? string1 string2)
[[ライブラリ手続き]] (string-ci<=? string1 string2)
[[ライブラリ手続き]] (string-ci>=? string1 string2)

以上の手続きは、文字の順序付手続きに対応して、手続きを辞書的な意味で文字列に拡張したものである。例えばstring<?では、文字に関する順序付け手続きchar<?から帰納して、文字列を辞書的に順序付けている。二つの文字列の長さが異なっており、短い方の文字列の長さまで文字列が同一である場合は、短い方の文字列は長い方の文字列よりも辞書的に小さいと見なされる。

対応する数値述語手続きと同じように、処理系は上記の手続きとstring=?およびstring-ci=?手続きを、三つ以上の引数をとるように拡張してもよい。

[[ライブラリ手続き]] (substring string start end)

stringは文字列でなければならず、startとendは

  0 <= start <= end <= (string-length string).

を満足しなければならない。substringは、指標startを含むstartから始まり指標endを除くendで終る文字で構成される文字列を、新しく割り当てて返す。

[[ライブラリ手続き]] (string-append string ...)

渡された文字列引数を連結した文字で構成される文字列を、新しく割り当てて返す。

[[ライブラリ手続き]] (string->list string)
[[ライブラリ手続き]] (list->string list)

string->listは、渡された文字列を構成する文字のリストを新しく割り当てて返す。list->stringは、文字のリストlist(34)の文字で構成される文字列を、新しく割り当てて返す。string->listlist->stringは、equal?の意味で逆関数である。

[[ライブラリ手続き]] (string-copy string)

渡された文字列stringのコピーを新しく割り当てて返す。

[[ライブラリ手続き]] (string-fill! string char)

渡された文字列stringのすべての要素にcharを格納する。返す値は不定である。

ベクタ

ベクタは、整数で指標付を行なった要素で構成される、異成分からなる構造である。ベクタは通常同じ長さのリストよりも占有するメモリが少く、任意に選択した要素のアクセスに必要な平均時間も、通常はリストよりも少い。

ベクタの長さは、ベクタに含まれる要素の数である。この数は非負の整数で、ベクタが作成された時に確定する。ベクタの有効な指標は、ベクタの長さよりも短い非負の完全整数である。ベクタの最初の要素には指標ゼロがつき、最後の要素にはベクタの長さよりも1少い指標がつく。

ベクタは、記法\#(obj ...)を使用して書かれる。例えば指標0の要素に数値ゼロ、指標1の要素にリスト(2 2 2 2)、指標2の要素に文字列"Anna"を含む長さ3のベクタは、次のように書く。

  #(0 (2 2 2 2) "Anna")

これがベクタの外部表現であって、ベクタに評価される式ではないことに注意する必要がある。リスト定数同様、ベクタ定数は次のようにクォートしなければならない(引用符をつける、もしくはquoteをつける)。

  '#(0 (2 2 2 2) "Anna")  =>  #(0 (2 2 2 2) "Anna")
[[手続き]] (vector? obj)

objがベクタの場合に#tを返し、それ以外の場合は#fを返す。

[[手続き]] (make-vector k)
[[手続き]] (make-vector k fill)

k個の要素を持つベクタを新しく割り当てて返す。二番目の引数が渡された場合は、要素の一つ一つがfillで初期化される。それ以外の場合は要素一つ一つの内容は不定である。

[[ライブラリ手続き]] (vector obj ...)

渡された引数を要素の内容とするベクタを、新しく割り当てて返す。listに相似の手続きである。

  (vector 'a 'b 'c)               =>  #(a b c)
[[手続き]] (vector-length vector)

ベクタvector内の要素数を完全整数で返す。

[[手続き]] (vector-ref vector k)

kはベクタvectorの有効な指標でなければならない。vector-refは、ベクタvectorの指標kの要素の内容を返す。

  (vector-ref '#(1 1 2 3 5 8 13 21)
              5)         =>  8
  (vector-ref '#(1 1 2 3 5 8 13 21)
              (let ((i (round (* 2 (acos -1)))))
                (if (inexact? i)
                    (inexact->exact i)
                    i))) => 13
[[手続き]] (vector-set! vector k obj)

kはベクタvectorの有効な指標でなければならない。vector-set!は、オブジェクトobjをベクタvectorの指標kの要素に格納する。vector-set!が返す値は不定である。

  (let ((vec (vector 0 '(2 2 2 2) "Anna")))
    (vector-set! vec 1 '("Sue" "Sue"))
    vec)      =>  #(0 ("Sue" "Sue") "Anna")

  (vector-set! '#(0 1 2) 1 "doe")  =>  error  ; constant vector
[[ライブラリ手続き]] (vector->list vector)
[[ライブラリ手続き]] (list->vector list)

vector->listは、ベクタvectorの要素に含まれるオブジェクトをリストにして、新しく割り当てて返す。list->vectorはベクタを新に作成し、その要素をリストlistの要素に初期化して返す。

  (vector->list '#(dah dah didah))  =>  (dah dah didah)
  (list->vector '(dididit dah))     =>  #(dididit dah)
[[ライブラリ手続き]] (vector-fill! vector fill)

ベクタvectorの一つ一つの要素すべてにfillを格納する。 vector-fill!が返す値は不定である。

制御機能

本章では、プログラムを実行する流れを特別な方法で制御する、各種のプリミティブ手続きを説明する。述語手続きprocedure?についても本章で説明する。

[[手続き]] (procedure? obj)

objが手続きであれば#tを返し、それ以外の場合は#fを返す。

  (procedure? car)            =>  #t
  (procedure? 'car)           =>  #f
  (procedure? (lambda (x) (* x x)))
                              =>  #t
  (procedure? '(lambda (x) (* x x)))
                              =>  #f
  (call-with-current-continuation procedure?)
                              =>  #t
[[手続き]] (apply proc arg1 ... args)

procは手続き、argsはリストでなければならない。リスト(append (list arg1 ...) args)の要素を実引数に使用してprocを呼び出す。

  (apply + (list 3 4))              =>  7

  (define compose
    (lambda (f g)
      (lambda args
        (f (apply g args)))))

  ((compose sqrt *) 12 75)          =>  30
[[ライブラリ手続き]] (map proc list1 list2 ...)

一連のlistはリストでなければならず、procは存在する限りのlistを引数にとって単一の値を返す手続きでなければならない。二つ以上のlistを渡す場合、リストはすべて同じ長さでなければならない。mapはlistの要素一つ一つにprocを適用して、もとの順序を変えずに結果をリストにして返す。listの要素にprocが適用される動的な順序は不定である。

  (map cadr '((a b) (d e) (g h)))   =>  (b e h)

  (map (lambda (n) (expt n n))
       '(1 2 3 4 5))                =>  (1 4 27 256 3125)

  (map + '(1 2 3) '(4 5 6))         =>  (5 7 9)

  (let ((count 0))
    (map (lambda (ignored)
           (set! count (+ count 1))
           count)
         '(a b)))                   =>  (1 2) or (2 1)
[[ライブラリ手続き]] (for-each proc list1 list2 ...)

for-eachの引数はmapのものに似ているが、値ではなく副作用を目的にして手続きを呼び出す点が違っている。mapとは異なりfor-eachは、最初から最後に向かう順序でリストの要素に対して手続きを呼び出すことが保証されている。for-eachが返す値は不定である。

  (let ((v (make-vector 5)))
    (for-each (lambda (i)
                (vector-set! v i (* i i)))
              '(0 1 2 3 4))
    v)                                =>  #(0 1 4 9 16)
[[ライブラリ手続き]] (force promise)

プロミスpromiseの値を強制的に引き出す(delay、section 遅延評価参照)。プロミスの値が以前に計算されていない場合は、この時に値を計算して返す。プロミスの値はキャッシュされる(memoizeされる)(35)ので、二度目にforceで呼び出された時には以前に計算した値が返される。

  (force (delay (+ 1 2)))        => 3
  (let ((p (delay (+ 1 2))))
    (list (force p) (force p)))  => (3 3)

  (define a--stream
    (letrec ((next
              (lambda (n)
                (cons n (delay (next (+ n 1)))))))
      (next 0))) 
  (36)

  (define head car) 
  (define tail
    (lambda (stream) (force (cdr stream))))

  (head (tail (tail a--stream))) => 2

forcedelayは、関数型プログラムでプログラミングを行なう場合を主として想定している。以下の例は、いいプログラミングスタイルを示すためのものではない。これはforce手続きが何度呼び出された場合でも、一つのプロミスについてただ一つの値だけが計算されるという特徴を説明するものである。

  (define count 0) 
  (define p
    (delay (begin (set! count (+ count 1))
                  (if (> count x)
                      count 
                      (force p)))))
  (37)

  (define x 5) 
  p                 => *プロミス*
  (force p)         => 6 
  p                 => *やはりプロミス*
  (begin (set! x 10)
         (force p)) => 6

delayforceの可能な実装例を次に示す。この例ではプロミスは引数を持たない手続きとして実装されており、forceは単にforce自体の引数を(手続きとして--訳者注)呼び出しているだけである。

  (define force
    (lambda (object)
      (object)))(38)

次の式

  (delay <式>) 

は、次の手続き呼び出しと同じ意味を持つように定義される。

  (make-promise (lambda () <式>))

例えば次の通りである。

  (define-syntax delay
    (syntax-rules ()
      ((delay expression)
       (make-promise (lambda () expression))))),%

ただしmake-promiseは次のように定義される。

  (define make-promise
    (lambda (proc)
      (let ((result-ready? #f)
            (result #f))
        (lambda ()
          (if result-ready?
              result
              (let ((x (proc)))
                (if result-ready?
                    result
                    (begin (set! result-ready? #t)
                           (set! result x)
                           result))))))))

理論的根拠:

上記の最後の例に示すように、プロミスはプロミス自体の固有の 値を参照することができる。この様なプロミスをforceで呼び出 した場合、最初のforceが計算される前にプロミスに対する二度 目のforceが発生することがあり、そのためにmake-promise の定義が複雑になる。

処理系によっては次のように、このdelayforceの構文の拡張をサポートするものがある。

[[手続き]] (call-with-current-continuation proc)

procは、引数を一つとる手続きでなければならない。call-with-current-continuationは現在のコンティニュエーション(下記の理論的根拠参照)を"エスケープ手続き"として一つの環境にまとめ、それを引数としてprocに渡す。Scheme手続きであるこのエスケープ手続きが後で呼び出されると、その時に有効なあらゆるコンティニュエーションが放棄され、かわりにエスケープ手続きが作成された時に有効であったコンティニュエーションが使用されるようになる。このエスケープ手続きを呼び出すと、dynamic-windを使用してインストールされたbeforeとafterの手続きが呼び出される場合がある。

このエスケープ手続きはコンティニュエーションとして、もともとのcall-with-current-continuation呼び出しと同数の引数を受け付ける。call-with-values手続きで作成されたコンティニュエーションを除いて、すべてのコンティニュエーションは正確に1つの値をとる。call-with-valuesが作成した以外のコンティニュエーションに値を渡さなかった場合、もしくは2つ以上の値を渡した場合、その結果は不定である。

procに渡されるエスケープ手続きは、Schemeのその他のあらゆる手続きと同じく無限エクステントを持つ。この手続きは変数やデータ構造に保管して、必要な回数だけ呼び出すことができる。

次の例はcall-with-current-continuationの最も一般的な利用法を示すためだけにあげるものである。現実のプログラムがこの例のように単純であるならば、call-with-current-continuationのように強力な手続きは不要であろう。

  (call-with-current-continuation
    (lambda (exit)
      (for-each (lambda (x)
                  (if (negative? x)
                      (exit x)))
                '(54 0 37 -3 245 19))
      #t))                        =>  -3

  (define list-length
    (lambda (obj)
      (call-with-current-continuation
        (lambda (return)
          (letrec ((r
                    (lambda (obj)
                      (cond ((null? obj) 0)
                            ((pair? obj)
                             (+ (r (cdr obj)) 1))
                            (else (return #f))))))
            (r obj))))))
(39)

  (list-length '(1 2 3 4))            =>  4

  (list-length '(a b . c))            =>  #f

理論的根拠:

call-with-current-continuationの一般的な利用法は ループや手続き本体からの構造化された大域脱出であるが、 広範囲にわたる先進的な制御構造を実装する場合には、 call-with-current-continuationは極めて有用である。

Schemeの式が評価される時は、式の結果を待っているコンティ ニュエーションが必ず存在する。このコンティニュエーションは、 計算に対応する未来の全体(デフォルト)を表すものである。 例えば式がトップレベルで評価される場合、結果を受け取り、 画面に表示し、次の入力を求めてそれを評価しという具合に、 これを無限に繰り返すのがコンティニュエーションと言える。 結果を受け取って局所変数に保管された値を乗じ、7を加えて 答をトップレベルコンティニュエーションに渡して画面に表示 するといった局所コンティニュエーションの場合のように、 ほとんどの場合このコンティニュエーションにはユーザのコー ドで指定される動作が含まれる。このように至るところに 存在するコンティニュエーションは通常その時々の状況の影に 隠れており、プログラマがそれについて深く考えることはない。 ただし稀には、各種のコンティニュエーションを明示的に操作 する必要がプログラマに生ずることがある。 call-with-current-continuationによって現在のコン ティニュエーションであるかのように動作する手続きを作成 すれば、Schemeプログラマはコンティニュエーションを明示的に 操作できる。

ほとんどのプログラミング言語には、exitreturn、あるいはさらにgotoの様な名前の、 特別な目的のエスケープ構造が一つ以上組み込まれている。 しかしながら1965年にはPeter Landin[LANDIN65]が J--operatorと呼ばれる汎用目的のエスケープ操作を発明した。 1972年にはJohn Reynolds[REYNOLDS72]が、より 単純ながら同じように強力な構造を発表した。1975年の Schemeに関する報告書でSussmanとSteeleが発表した catch特殊形式は、まさにReynoldsの構造と同じもの であったが、その名前はさほど一般的でないMaclispの構造 から取られたものであった。catch構造の強力さの 全貌は、特殊構文の構造ではなく手続きによって得られること に気がついたScheme処理系の複数の実装者が、1982年に call-with-current-continuationの名前を考案 した。この名前は手続きをよく表しているが、この様な 長い名前を使うメリットについては異論もあって、代わりに call/ccという名前を使用する人々も存在する。

[[手続き]] (values obj ...)

渡されたすべての引数を自分のコンティニュエーションに渡す。call-with-values手続きで作成されたコンティニュエーションの場合を除いて、すべてのコンティニュエーションは正確に1つの値をとる。valuesは次のように定義することができる。

  (define (values . things)
    (call-with-current-continuation 
      (lambda (cont) (apply cont things))))
[[手続き]] (call-with-values producer consumer)

値を渡さずにproducer引数を呼び出し、ついで何らかの値を渡されたときはその値を引数としてconsumer手続きを呼び出すコンティニュエーションを呼び出す。consumerを呼び出す際のコンティニュエーションは、call-with-valuesを呼び出すコンティニュエーションである。

  (call-with-values (lambda () (values 4 5))
                    (lambda (a b) b))                =>  5
(40)

  (call-with-values * -)                             =>  -1
(41)
[[手続き]] (dynamic-wind before thunk after)

引数なしでthunkを呼び出し、その呼び出しの結果を返す。下記の規則の指定にしたがって、beforeとafterがやはり引数なしで呼び出される(call-with-current-continuationを使用して捕獲したコンティニュエーションへの呼び出しがない場合、3つの引数が順序通りに各々一回だけ呼び出される点に注意する必要がある)。実行がthunkの呼び出しの動的エクステントに入ったときはbeforeが必ず呼び出され、その動的エクステントが終了したときは必ずafterが呼び出される。手続き呼び出しの動的エクステントは、呼び出しが開始した時点と呼び出しが返った時点との間の期間である。Schemeではcall-with-current-continuationがあるために、呼び出しの動的エクステントが単一の連続した期間でない場合がある。これは次のように定義される。

thunkの呼び出しの動的エクステント内部で2番目のdynamic-windの呼び出しが発生し、2度のdynamic-windの起動による2つのafterを両方とも呼び出す必要が生ずるようなコンティニュエーションが呼び出された場合は、2番目の(内側の)dynamic-wind呼び出しに連結されたafterが最初に呼び出される。

thunkの呼び出しの動的エクステント内部で2番目のdynamic-windの呼び出しが発生し、2度のdynamic-windの起動による2つのbeforeを両方とも呼び出す必要が生ずるようなコンティニュエーションが呼び出された場合は、最初の(外側の)dynamic-wind呼び出しに連結されたbeforeが最初に呼び出される。

1つのdynamic-wind呼び出しのbeforeと別のdynamic-wind呼び出しのafterがコンティニュエーションの起動に必要な場合は、afterが最初に呼び出される。

捕獲したコンティニュエーションを使用してbeforeやafterの動的エクステントを開始、もしくは終了した場合の結果は未定義である。

  (let ((path '())
        (c #f))
    (let ((add (lambda (s)
                 (set! path (cons s path)))))
      (dynamic-wind
        (lambda () (add 'connect))
        (lambda ()
          (add (call-with-current-continuation
                 (lambda (c0)
                   (set! c c0)
                   'talk1))))
        (lambda () (add 'disconnect)))
      (if (< (length path) 4)
          (c 'talk2)
          (reverse path))))
      => (connect talk1 disconnect
                   connect talk2 disconnect)

Eval

[[手続き]] (eval expression environment-specifier)

指定環境でexpressionを評価し、expressionの値を返す。expressionはデータとして表現された有効なSchemeの式でなければならず、environment-specifierは下記に示す3つの手続きの1つが返す値でなければならない。処理系はevalを拡張して式以外のプログラム(定義)を第1引数に許可し、その他の値を環境として許可してもよい。ただしnull-environmentscheme-report-environmentに連結された環境に、evalによる新しいバインディングの作成が許可されないような制限が必要である。

  (eval '(* 7 3) (scheme-report-environment 5))      =>  21

  (let ((f (eval '(lambda (f x) (f x x))
                 (null-environment 5))))
    (f + 10))                                        =>  20
[[手続き]] (scheme-report-environment version)
[[手続き]] (null-environment version)

versionは、Scheme報告書(the Revised^5 Report on Scheme)の今回の改定版に対応する完全整数5でなければならない。scheme-report-environmentは必須、もしくはオプションであっても処理系がサポートするとして本報告書に定義するすべてのバインディング以外は空の、環境を指定する手続きを返す。null-environmentは必須、もしくはオプションであっても処理系がサポートするとして本報告書に定義するすべての構文キーワードの(構文)バインディング以外は空の、環境を指定する手続きを返す。

その他のversionの値を使用して、本報告書の過去の改定に一致する環境を指定することもできるが、この機能のサポートは必須ではない。versionが5でもなく処理系がサポートするもう1つの値でもない場合、処理系はエラーを発信する。

scheme-report-environmentでバインドされている変数に(evalを使用して)割り当てを行なった場合の結果は不定である。したがって scheme-report-environmentで指定された環境は、変更できない場合がある。

[[オプション手続き]] (interaction-environment)

この手続きは処理系定義のバインディング、標準的には本報告書にあげたバインディングの上位集合を含む環境を指定する手続きを返す。目的はこの手続きによって、ユーザが動的に型を定義した式を処理系が評価する環境を返すことである。

入出力

ポート

ポートは入出力装置を表す。Schemeにとっての入力ポートはコマンドに応じて文字を送出できるSchemeオブジェクトである。対する出力ポートは、文字を受け付けるSchemeオブジェクトである。

[[ライブラリ手続き]] (call-with-input-file string proc)
[[ライブラリ手続き]] (call-with-output-file string proc)

stringはファイルの名前を指定する文字列、procは引数を一つ受け入れる手続きである。call-with-input-fileの場合、ファイルはすでに存在しているものでなければならない。call-with-output-fileについてファイルがすでに存在している場合、呼び出しの結果は不定である。この二つの手続きは入力もしくは出力用に名前を指定したファイルを開いて、得られたボートを引数に一つ取る手続きprocを呼び出す。ファイルを開けなかった場合はエラー信号が発せられる。手続きが戻る場合はポートが自動的に閉じられて、手続きが生成した値が返される。手続きが戻らない場合、readもしくはwrite操作でポートが二度と使用されないことが証明できない限り、ポートが自動的に閉じられることはない。

理論的根拠:

Schemeのエスケープ手続きは無限エクステントを持つことから、 現在のコンティニュエーションからエスケープで脱出して後で エスケープで戻ることができる。現在のコンティニュエーション からエスケープ脱出した時にポートを閉じることを処理系に 許した場合、call-with-current-continuationcall-with-input-file、もしくは call-with-current-continuationcall-with-output-fileを使用して移植可能な コードを書くことができなくなるであろう。

[[手続き]] (input-port? obj)
[[手続き]] (output-port? obj)

objが入力ポートか出力ポートであれば#tを返し、それ以外の場合は#fを返す。

[[手続き]] (current-input-port)
[[手続き]] (current-output-port)

現在のデフォルトの入力ポートか出力ポートを返す。

[[オプション手続き]] (with-input-from-file string thunk)
[[オプション手続き]] (with-output-to-file string thunk)

stringはファイルを指す文字列、proc(42)は引数を取らない手続きでなければならない。with-input-from-fileの場合、ファイルはすでに存在しているものでなければならない。with-output-to-fileについては、ファイルがすでに存在している場合の結果は不定である。ファイルは入力もしくは出力用に開かれ、ファイルに連結された入力ポートもしくは出力ポートが、current-input-portもしくはcurrent-output-portのデフォルトの値になる(このポートを(read)(write obj)などが使用する)。その上で引数をとらない手続きthunkが呼び出される。thunkが返るとポートが閉じられ、以前のデフォルト値が回復する。with-input-from-filewith-output-to-fileは、thunkが生成した値を返す。このコンティニュエーションからの脱出にエスケープ手続きが使用された場合、二つの手続きの振舞いは処理系に依存する。

[[手続き]] (open-input-file filename)

既存のファイルを指定する文字列を引数にとって、そのファイルの文字を送出できる入力ポートを返す。ファイルを開くことができなかった場合はエラー信号が発せられる。

[[手続き]] (open-output-file filename)

作成する出力ファイルを指定する文字列を引数にとって、その名前で新しいファイルに文字を書き出すことができる出力ポートを返す。渡された名前のファイルがすでに存在する場合、結果は不定である。

[[手続き]] (close-input-port port)
[[手続き]] (close-output-port port)

ポートportに連結したファイルを閉じて、文字を送出したり受け入れたりしていたportを使用禁止にする。ファイルがすでに閉じられていた場合はこの二つのルーチンは何も行なわない。返される値は不定である。

入力

[[ライブラリ手続き]] (read)
[[ライブラリ手続き]] (read port)

readはSchemeオブジェクトの外部表現をオブジェクト自体に変換する。すなわちreadは、非終端<データ>(section 意味論とsection ペアとリスト参照)のパーサ(構文解析手続き)である。readはオブジェクトの外部表現の終端の次の、最初の文字を指すようにポートportを更新して、与えられた入力ポートから構文解析可能な次のオブジェクトを返す。

オブジェクトの開始となり得る文字を発見する前に入力中にファイル終りが検出された場合は、ファイル終りオブジェクトが返される。portは開いたままであり、さらに読み取りを試みた場合にもファイル終りオブジェクトが返される。オブジェクトの外部表現が開始した後にその外部表現が不完全であるために構文解析できず、ファイル終りが検出された場合は、エラーが発信される。

port引数は省略できる。この場合のデフォルトはcurrent-input-portが返す値である。閉じたポートから読み取りを行なった場合はエラーである。

[[手続き]] (read-char)
[[手続き]] (read-char port)

入力ポートportから取り出すことができる次の文字を返し、その次の文字を指すようにポートを更新する(ポートを一つ進める)。取り出す文字が存在しなかった場合はファイル終りオブジェクトが返される。port引数は省略でき、その場合のデフォルトはcurrent-input-portが返す値である。

[[手続き]] (peek-char)
[[手続き]] (peek-char port)

入力ポートportから取り出すことができる次の文字を返すが、次の文字を指し示す様なポートの更新は行なわれない(ポート内の位置は変わらない)。取り出す文字が存在しなかった場合はファイル終りオブジェクトが返される。port引数は省略でき、その場合のデフォルトはcurrent-input-portが返す値である。

注: peek-charの呼び出しで返される値は、同じポートに対するread-charの呼び出しで返される値と同じものである。唯一の違いは、ポートに対する直後のread-char呼び出しもしくはpeek-char呼び出しで、直前のpeek-char呼び出しで返された値が返されるという点である。特に対話型ポートに対してpeek-charを呼び出した場合、入力を待ち続けてread-charがハングする時には、peek-charも必ずハングすることになる。

[[手続き]] (eof-object? obj)

objがファイル終りオブジェクトの場合に#tを返し、それ以外の場合は#fを返す。ファイル終りオブジェクトの正確な集合は処理系ごとに異なるが、いかなる場合にも、ファイル終りオブジェクトがreadを使用して読み取ることができるオブジェクトになることはない。

[[手続き]] (char-ready?)
[[手続き]] (char-ready? port)

入力ポートportに文字の準備ができている場合に#tを返し、それ以外の場合は#fを返す。char-ready?が#tを返した場合、与えられたポートに対する次のread-char操作はハングしないことが保証される。ポートがファイル終りにある場合、char-ready?は#tを返す。port引数は省略でき、その場合のデフォルトはcurrent-input-portが返す値である。

理論的根拠:

char-ready?は、入力を待ち続けてスタックすること なく、対話型ポートからプログラムが文字を受け入れることが できるようにするために存在する。この様なポートに接続 されたあらゆる入力エディターは、char-ready?が 存在を肯定した文字を削除できないことを保証しなければ ならない。ファイル終りでchar-ready?が#fを返す 様なことがあるならば、ファイル終りにあるポートを文字 の準備ができていない対話型ポートから区別することがで きなくなるであろう。

出力

[[ライブラリ手続き]] (write obj)
[[ライブラリ手続き]] (write obj port)

objの文字による表現を与えられたポートportに書き出す。文字表現内に現れる文字列は二重引用符で括られ、その文字列内のバックスラッシュ文字と二重引用符文字にはエスケープ文字バックスラッシュが付けられる。writeが返す値は不定である。port引数は省略でき、その場合のデフォルトはcurrent-output-portが返す値である。

[[ライブラリ手続き]] (display obj)
[[ライブラリ手続き]] (display obj port)

objの文字による表現を与えられたポートportに書き出す。文字表現内に現れる文字列は二重引用符で括られず、その文字列内のいかなる文字にもエスケープ文字は付かない。この表現内の文字オブジェクトは、writeではなくwrite-charで書かれたかのように表示される。displayが返す値は不定である。port引数は省略でき、その場合のデフォルトはcurrent-output-portが返す値である。

理論的根拠:

writeは機械が読みやすい出力を生成し、displayは 人間が読みやすい出力を生成することを目的としている。シンボル 内に"スラッシュ化"(slashification)を許す処理系では、 シンボルの特殊文字を"スラッシュ化"するにはdisplay ではなくwriteの方がおそらく好ましいであろう。

[[ライブラリ手続き]] (newline)
[[ライブラリ手続き]] (newline port)

行の終りをポートportに書き出す。これが正確にどのように行なわれるかは、オペレーティングシステムごとに異なる。不定の値が返される。port引数は省略でき、その場合のデフォルトはcurrent-input-portが返す値である。

[[手続き]] (write-char char)
[[手続き]] (write-char char port)

文字char(文字の外部表現ではない)を与えられたポートportに書き出し、不定の値を返す。port引数は省略でき、その場合のデフォルトはcurrent-output-portが返す値である。

システムインタフェース

一般的には、システムインタフェースの問題は本報告書の領域外に属す。ただし以下の操作は非常に重要であり、本節で説明するに値する。

[[オプション手続き]] (load filename)

filenameは、Schemeのソースコードが入っている既存のファイルを指定する文字列でなければならない。load手続きはファイルから式と定義を読み込んで、それを順次的に評価する。式の結果が表示されるかどうかは指定されていない。current-input-portcurrent-output-portが返す値は、load手続きによっては変更されない。loadは不定の値を返す。

理論的根拠:

移植性を確保するためには、loadはソースファイルに 対して動作しなければならない。その他のファイルに対する 動作が処理系ごとに異なることはやむを得ない。

[[オプション手続き]] (transcript-on filename)
[[オプション手続き]] (transcript-off)

filenameは、作成する出力ファイルを指定する文字列でなければならない。transcript-onの結果指定されたファイルが出力用に開かれて、以後のユーザとSchemeシステムとの対話の記録がそのファイルに書き出されるようになる。記録の出力はtranscript-offの呼び出しで終了し、それによって記録ファイルが閉じられる。いつの時点でも、開いている記録ファイルはただ一つだけである。ただし処理系によってはこの制限を緩める場合がある。この二つの手続きが返す値は不定である。

意味論と言語仕様

本章では、報告書のこれまでの章で形式にこだわらずに説明してきたところを意味論にしたがって説明する。

意味論

本節では、拡張BNFで書かれたSchemeの構文則を述べる。

語法内にはいっているすべての空白は、読みやすさのために入れたものである。大文字と小文字の区別は意味がなく、例えば#x1A#X1aとは等価である。<空>は空の文字列を表す。

BNFへの次の拡張は、説明をさらに簡約にするために使用している。<thing>*は、<thipng>がゼロ回以上発生することを意味する。<thing>+は、<thing>が少くとも一回発生することを意味する。

辞書的構造

この項では、一つ一つのトークン(識別子、数、その他)が文字の連続からどのように生成されるかを説明する。続く項では、式とプログラムがトークンの連続からどのように生成されるかを説明する。

<トークン間の空白>はあらゆるトークンのいずれの側にもつけることができるが、トークン内部に入れることはできない。

暗黙の終了を必要とするトークン(識別子、数、文字、ドット)はいかなる<区切り文字>で終了することもできるが、必ずしもそれ以外の何で終了してもいいというわけではない。

以下の五文字は言語の将来の拡張のために予約されている: "[" "]" "{" "}" "|"。

<トークン> ---> <識別子> | <論理値> | <数>  | <文字> | <文字列>
              | ( | ) | #( | ' | ` | , | ,@ | .
<区切り文字> ---> <空白> | ( | ) | " | ;
<空白> ---> <空白もしくは改行>
<コメント> ---> ; <改行まで後続するすべての文字>
<空白圏> ---> <空白> | <コメント>
<トークン間の空白> ---> <空白圏>*
<識別子> ---> <頭字> <後続文字>*
     | <特殊な識別子>
<頭字> ---> <文字> | <特殊な頭字>
<文字> ---> a | b | c | ... | z

<特殊な頭字> ---> ! | $ | % | & | * | / | : | < | =
                | > | ? | ~ | _ | ~
<後続文字> ---> <頭字> | <数字>  | <特殊な後続文字>
<数字> ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<特殊な後続文字> ---> + | - | . | @
<特殊な識別子> ---> + | - | ...
<構文キーワード> ---> <式のキーワード>
                    | else | => | define 
                    | unquote | unquote-splicing
<式のキーワード> ---> quote | lambda | if
                    | set! | begin | cond | and | or | case
                    | let | let* | letrec | do | delay
                    | quasiquote

<変数> --->  <同時に<構文キーワード>でないあらゆる<識別子>>

<論理値> ---> #t | #f
<文字> ---> #\ <あらゆる文字>  | #\ <文字名>
<文字名> ---> space | newline
<文字列> ---> " <文字列要素>* "
<文字列要素> ---> <"か\以外のあらゆる文字> | \" | \\ 
<数> ---> <基数2>
        | <基数8>
        | <基数10>
        | <基数16>

<数R>、<複素数R>、<実数R>、<符号なし実数R>、<符号なし整数R>、<接頭辞R>に対する以下の規則は、R = 2, 8, 10, 16のすべての場合に適用される。<2進小数>、<8進小数>、<16進小数>に関する規則は存在しない。これは、小数点もしくは指数を含む数の基数が10でなければならないことを意味する。

<数R> ---> <接頭辞R> <複素数R>
<複素数R> ---> <実数R> 
             | <実数R> @ <実数R>
             | <実数R> + <符号なし実数R> i 
             | <実数R> - <符号なし実数R> i
             | <実数R> + i 
             | <実数R> - i
             | + <符号なし実数R> i 
             | - <符号なし実数R> i
             | + i  | - i
<実数R> ---> <符号> <符号なし実数R>
<符号なし実数R> ---> <符号なし整数R>
             | <符号なし整数R> / <符号なし整数R>
             | <小数R>
<10進小数> ---> <符号なし10進整数> <接尾辞>
             | . <10進数字>+ #* <接尾辞>
             | <10進数字>+ . <10進数字>* #* <接尾辞>
             | <10進数字>+ #+ . #* <接尾辞>
<符号なし整数R> ---> <数字R>+ #*
<接頭辞R> ---> <基数R> <完全性>
             | <完全性> <基数R>
<接頭辞> ---> <空> | <指数標識> <符号> <10進数字>+
<指数標識> ---> e | s | f | d | l
<符号> ---> <空>  | + |  -
<完全性> ---> <空> | #i | #e
<基数2> ---> #b
<基数8> ---> #o
<基数10> ---> <空> | #d
<基数16> ---> #x
<2進数字> ---> 0 | 1
<8進数字> ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
<10進数字> ---> <数字>
<16進数字> ---> <10進数字> | a | b | c | d | e | f 

外部表現

<データ>は、read手続き(section 入力参照)が構文解析できたものである。<式>として構文解析されるあらゆる文字列は<データ>としても構文解析される。

<データ> ---> <単純データ> | <複合データ>
<単純データ> ---> <論理値> | <数>
                  | <文字> | <文字列> |  <シンボル>
<シンボル> ---> <識別子>
<複合データ> ---> <リスト> | <ベクタ>
<リスト> ---> (<データ>*) | (<データ>+ . <データ>)
              | <略記>
<略記> ---> <略記接頭辞> <データ>
<略記接頭辞> ---> ' | ` | , | ,@
<ベクタ> ---> #(<データ>*)

<式> ---> <変数>
        | <リテラル>
        | <手続き呼び出し>
        | <ラムダ式>
        | <条件式>
        | <割り当て>
        | <導出式>
        | <マクロの使用>
        | <マクロブロック>

<リテラル> ---> <クォート式> | <自己評価式>
<自己評価式> ---> <論理値> | <数>
               | <文字> | <文字列>
<クォート式>  '<データ> | (quote <データ>)
<手続き呼び出し> ---> (<演算子> <被演算子>*)
<演算子> ---> <式>
<被演算子> ---> <式>

<ラムダ式> ---> (lambda <仮引数> <ボディ>)
<仮引数> ---> (<変数>*) | <変数>
            | (<変数>+ . <変数>)
<ボディ> ---> <定義>* <シーケンス>
<シーケンス> ---> <コマンド>* <式>
<コマンド> ---> <式>

<条件式> ---> (if <テスト> <帰結> <代わりの帰結>)
<テスト> ---> <式>
<帰結> ---> <式>
<代わりの帰結> ---> <式> | <空>

<割り当て> ---> (set! <変数> <式>)

<導出式> --->
       (cond <cond節>+)
     | (cond <cond節>* (else <シーケンス>))
     | (case <式> <case節>+)
     | (case <式> <case節>* (else <シーケンス>))
     | (and <テスト>*)
     | (or <テスト>*)
     | (let (<バインディング仕様>*) <ボディ>)
     | (let <変数> (<バインディング仕様>*) <ボディ>)
     | (let* (<バインディング仕様>*) <ボディ>)
     | (letrec (<バインディング仕様>*) <ボディ>)
     | (begin <シーケンス>)
     | (do (<繰り返し仕様>)
               (<テスト> <do式の結果>)
           <コマンド>*)
     | (delay <式>)
     | <バッククォート式>

<cond節> ---> (<テスト> <シーケンス>)
            | (<テスト>)
            | (<テスト> => <受け入れ手続き>)
<受け入れ手続き> ---> <式>
<case節> ---> ((<データ>*) <シーケンス>)
<バインディング仕様> ---> (<変数> <式>)
<繰り返し仕様> ---> (<変数> <初期値> <ステップ>)
                  | (<変数> <初期値>)
<初期値> ---> <式>
<ステップ> ---> <式>
<do式の結果> ---> <シーケンス> | <空>

<マクロの使用> ---> (<キーワード> <データ>*)
<キーワード> ---> <識別子>

<マクロブロック> ---> (let-syntax (<構文仕様>*) <ボディ>)
                    | (letrec-syntax (<構文仕様>*) <ボディ>)
<構文仕様> ---> (<キーワード> <変換手続き仕様>)

Quasiquotations

バッククォート式に関する以下の文法は文脈自由ではない。これは無限数の生成規則を生成するための方法として示すものである。D = 1、2、3 ...の場合の以下の規則を想像してみればよい。Dはネストレベルの深さを示す。

<バッククォート式> ---> <バッククォート式1>
<qqテンプレート0> ---> <式>
<バッククォート式D> ---> `<qqテンプレートD>
                       | (quasiquote <qqテンプレートD>)
<qqテンプレートD> ---> <単純データ>
                     | <リストqqテンプレートD>
                     | <ベクタqqテンプレートD>
                     | <アンクォートD>
<リストqqテンプレートD> ---> 
       (<qqテンプレートもしくは挿入D>*)
      | (<qqテンプレートもしくは挿入D>+ . <qqテンプレートD>)
      | '<qqテンプレートD> | <バッククォート式D+1>
<ベクタqqテンプレートD> --->
       #(<qqテンプレートもしくは挿入D>*)
<アンクォートD> ---> ,<qqテンプレートD-1>
                   | (unquote <qqテンプレートD-1>)
<qqテンプレートもしくは挿入D> ---> <qqテンプレートD>
                                 | <挿入アンクォートD>
<挿入アンクォートD> ---> ,@<qqテンプレートD-1>
                       | (unquote-splicing <qqテンプレートD-1>) 

<バッククォート式>においては、<リストqqテンプレートD>が<アンクォートD>や<挿入アンクォートD>と混同されやすい場合がある。<アンクォートD>か<挿入アンクォートD>としての解釈の方が優先される。

変換手続き

<変換手続き仕様> ---> (syntax-rules (<識別子>*) <構文規則>*)
<構文規則> ---> (<パターン> <テンプレート>)
<パターン> ---> <パターン識別子>
              | (<パターン>*)
              | (<パターン>+ . <パターン>)
              | (<パターン>* <パターン> <略記号>)
              | #(<パターン>*)
              | #(<パターン>* <パターン> <略記号>)
              | <パターンデータ>
<パターンデータ> ---> <文字列> | <文字> | <論理値> | <数>
<テンプレート> ---> <パターン識別子>
                  | (<テンプレート要素>*)
                  | (<テンプレート要素>+ . <テンプレート>)
                  | #(<テンプレート要素>*)
                  | <テンプレートデータ>
<テンプレート要素> ---> <テンプレート> | <テンプレート> <略記号>
<テンプレートデータ> ---> <パターンデータ>
<パターン識別子> ---> <... を除くあらゆる識別子>
<略記号> ---> <識別子 ...>

プログラムと定義

<プログラム> ---> <コマンドもしくは定義>*
<コマンドもしくは定義> ---> <コマンド> | <定義>
                          | <構文定義>
                          | (begin <コマンドもしくは定義>+)
<定義> ---> (define <変数> <式>)
          | (define (<変数> <仮引数定義>) <ボディ>)
          | (begin <定義>*)
<仮引数定義> ---> <変数>* | <変数>* . <変数>
<構文定義> 
    (define-syntax 
             <キーワード> <変換手続き仕様>)

形式記号言語

... Texinfo版にては省略 ...。

導出式型

本節では、導出式型をプリミティブ式型(リテラル、変数、手続き呼び出し、lambdaifset!)に置き換えるマクロ定義を示す。delayに関して可能な定義についてはsection 制御機能参照。

(define-syntax cond
  (syntax-rules (else =>)
    ((cond (else result1 result2 ...))
     (begin result1 result2 ...))
    ((cond (test => result))
     (let ((temp test))
       (if temp (result temp))))
    ((cond (test => result) clause1 clause2 ...)
     (let ((temp test))
       (if temp
           (result temp)
           (cond clause1 clause2 ...))))
    ((cond (test)) test)
    ((cond (test) clause1 clause2 ...)
     (let ((temp test))
       (if temp
           temp
           (cond clause1 clause2 ...))))
    ((cond (test result1 result2 ...))
     (if test (begin result1 result2 ...)))
    ((cond (test result1 result2 ...)
           clause1 clause2 ...)
     (if test
         (begin result1 result2 ...)
         (cond clause1 clause2 ...)))))
(define-syntax case
  (syntax-rules (else)
    ((case (key ...)
       clauses ...)
     (let ((atom-key (key ...)))
       (case atom-key clauses ...)))
    ((case key
       (else result1 result2 ...))
     (begin result1 result2 ...))
    ((case key
       ((atoms ...) result1 result2 ...))
     (if (memv key '(atoms ...))
         (begin result1 result2 ...)))
    ((case key
       ((atoms ...) result1 result2 ...)
       clause clauses ...)
     (if (memv key '(atoms ...))
         (begin result1 result2 ...)
         (case key clause clauses ...)))))
(define-syntax and
  (syntax-rules ()
    ((and) #t)
    ((and test) test)
    ((and test1 test2 ...)
     (if test1 (and test2 ...) #f))))
(define-syntax or
  (syntax-rules ()
    ((or) #f)
    ((or test) test)
    ((or test1 test2 ...)
     (let ((x test1))
       (if x x (or test2 ...))))))
(define-syntax let
  (syntax-rules ()
    ((let ((name val) ...) body1 body2 ...)
     ((lambda (name ...) body1 body2 ...)
      val ...))
    ((let tag ((name val) ...) body1 body2 ...)
     ((letrec ((tag (lambda (name ...)
                      body1 body2 ...)))
        tag)
      val ...))))
(define-syntax let*
  (syntax-rules ()
    ((let* () body1 body2 ...)
     (let () body1 body2 ...))
    ((let* ((name1 val1) (name2 val2) ...)
       body1 body2 ...)
     (let ((name1 val1))
       (let* ((name2 val2) ...)
         body1 body2 ...)))))

次のletrecマクロでは、記憶域内に格納されたときに、格納場所から格納された値を取り出そうとするとエラーになるようなオブジェクトを返す式に代えて、シンボル<undefined>を使用している(このような式はSchemeでは定義されていない)。値を評価する順序の指定を避けるために必要な一時名を生成するために、一種の手品を使用している。これは補助的なマクロを使用して行なうこともできる。

(define-syntax letrec
  (syntax-rules ()
    ((letrec ((var1 init1) ...) body ...)
     (letrec "generate\_temp\_names"
       (var1 ...)
       ()
       ((var1 init1) ...)
       body ...))
    ((letrec "generate\_temp\_names"
       ()
       (temp1 ...)
       ((var1 init1) ...)
       body ...)
     (let ((var1 <undefined>) ...)
       (let ((temp1 init1) ...)
         (set! var1 temp1)
         ...
         body ...)))
    ((letrec "generate\_temp\_names"
       (x y ...)
       (temp ...)
       ((var1 init1) ...)
       body ...)
     (letrec "generate\_temp\_names"
       (y ...)
       (newtemp temp ...)
       ((var1 init1) ...)
       body ...))))
(define-syntax begin
  (syntax-rules ()
    ((begin exp ...)
     ((lambda () exp ...)))))

次のもう1つのbegin式の展開では、ラムダ式のボディ内に2つ以上の式を書く機能を使用していない。いずれの場合にも構文規則は、begin式のボディに定義が含まれない場合にのみ適用される点に注意する必要がある。

(define-syntax begin
  (syntax-rules ()
    ((begin exp)
     exp)
    ((begin exp1 exp2 ...)
     (let ((x exp1))
       (begin exp2 ...)))))

次のdo式の定義では、変数節の展開に一種の手品を使用している。前のletrec式の場合と同じく補助的なマクロを使うこともできる。不定の値を求めるために、式(if #f #f)が使用されている。

(define-syntax do
  (syntax-rules ()
    ((do ((var init step ...) ...)
         (test expr ...)
         command ...)
     (letrec
       ((loop
         (lambda (var ...)
           (if test
               (begin
                 (if #f #f)
                 expr ...)
               (begin
                 command
                 ...
                 (loop (do "step" var step ...)
                       ...))))))
       (loop init ...)))
    ((do "step" x)
     x)
    ((do "step" x y)
     y)))

この節では、"Revised^4 report" [R4RS]の刊行以後に行なわれたSchemeへの変更点をあげる。

integrate-system : 次の微文方程式系

  y'_k = f_k(y_1, y_2, ..., y_n), k = 1, ..., n

を、ルンゲ・クッタ(Runge-Kutta)法を使用して積分する。

パラメータsystem-derivativeは、系の状態(状態変数y_1, ...,y_nについての値のベクタ)を引数に取って、系の導関数(値y'_1, ...,y'_n)を生成する。パラメータinitial-stateは、系の初期状態を与える。hは積分刻みの長さに対する初期推測値である。

integrate-systemが返す値は、系の状態の無限ストリームである。

(define integrate-system
  (lambda (system-derivative initial-state h)
    (let 
      ((next (runge-kutta-4 system-derivative h)))
        (letrec ((states
                 (cons initial-state
                       (delay (map-streams next
                                        states))))) 
        states))))

Runge-Kutta-4は、系の状態から系の導関数を生成する関数fを引数にとる。Runge-Kutta-4は、系の状態を引数にとって系の新しい状態を生成する関数を生成する。

(define runge-kutta-4
  (lambda (f h)
    (let ((*h (scale-vector h))
          (*2 (scale-vector 2))
          (*1/2 (scale-vector (/ 1 2)))
          (*1/6 (scale-vector (/ 1 6))))
      (lambda) (y) ;; yは系の状態
        (let* 
          ((k0 (*h (f y)))
           (k1 (*h (f (add-vectors y (*1/2 k0)))))
           (k2 (*h (f (add-vectors y (*1/2 k1)))))
           (k3 (*h (f (add-vectors y k2)))))
          (add-vectors y
            (*1/6 (add-vectors k0
                               (*2 k1)
                               (*2 k2) 
                               k3))))))))
(define elementwise
  (lambda (f)
    (lambda vectors
      (generate-vector
        (vector-length (car vectors))
        (lambda (i)
          (apply f
                 (map (lambda (v) (vector-ref v i))
                      vectors)))))))
(define generate-vector
  (lambda (size proc)
    (let ((ans (make-vector size)))
      (letrec ((loop
                  (lambda (i)
                    (cond ((= i size) ans)
                          (else
                            (vector-set! ans i (proc i))
                            (loop (+ i 1)))))))
        (loop 0)))))
(define add-vectors (elementwise +))
(define scale-vector
  (lambda (s)
    (elementwise (lambda (x) (* x s)))))

map-streamsmapに似ており、第1引数(手続き)を第2引数(ストリーム)のすべての要素に適用する。

(define map-streams
  (lambda (f s)
    (cons (f (head s))
          (delay (map-streams f (tail s))))))

無限ストリームはペアとして実装され、そのcarにはストリームの最初の要素が、cdrにはストリームの残りを生成するプロミスが保持される。

(define head car) 
(define tail
  (lambda (stream) (force (cdr stream))))

integrate-systemの利用法を下記に示す。これは減衰発信器をモデル化した次の系の積分を行なうものである。

  C * (dv_C / dt) = -i_L - (v_C / R)
  L * (di_L / dt) = v_C
(define damped-oscillator
  (lambda (R L C)
    (lambda (state)
      (let ((Vc (vector-ref state 0))
            (Il (vector-ref state 1)))
        (vector (- 0 (+ (/ Vc (* R C)) (/ Il C)))
                (/ Vc L))))))
(define the-states
  (integrate-system
      (damped-oscillator 10000 1000 .001) 
      '#(1 0) 
      .01)

References

  1. Harold Abelson and Gerald Jay Sussman with Julie Sussman.
    Structure and Interpretation of Computer Programs, second edition.
    MIT Press, Cambridge, 1996.
  2. Alan Bawden and Jonathan Rees.
    Syntactic closures.
    In Proceedings of the 1988 ACM Symposium on Lisp and Functional Programming, pages 86-95.
  3. Robert G. Burger and R. Kent Dybvig.
    Printing floating-point numbers quickly and accurately.
    In Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 108-116.
  4. William Clinger, editor.
    The revised revised report on Scheme, or an uncommon Lisp.
    MIT Artificial Intelligence Memo 848, August 1985.
    Also published as Computer Science Department Technical Report 174, Indiana University, June 1985.
  5. William Clinger.
    How to read floating point numbers accurately.
    In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 92-101.
    Proceedings published as SIGPLAN Notices 25(6), June 1990.
  6. William Clinger and Jonathan Rees, editors.
    The revised^4 report on the algorithmic language Scheme.
    In ACM Lisp Pointers 4(3), pages 1-55, 1991.
  7. William Clinger and Jonathan Rees.
    Macros that work.
    In Proceedings of the 1991 ACM Conference on Principles of Programming Languages, pages 155-162.
  8. William Clinger.
    Proper Tail Recursion and Space Efficiency.
    To appear in Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, June 1998.
  9. R. Kent Dybvig, Robert Hieb, and Carl Bruggeman.
    Syntactic abstraction in Scheme.
    Lisp and Symbolic Computation 5(4):295-326, 1993.
  10. Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes.
    Scheme 311 version 4 reference manual.
    Indiana University Computer Science Technical Report 137, February 1983.
    Superseded by [11].
  11. D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand.
    Scheme 84 interim reference manual.
    Indiana University Computer Science Technical Report 153, January 1985.
  12. IEEE Standard 754-1985.
    IEEE Standard for Binary Floating-Point Arithmetic.
    IEEE, New York, 1985.
  13. IEEE Standard 1178-1990.
    IEEE Standard for the Scheme Programming Language.
    IEEE, New York, 1991.
  14. Eugene E. Kohlbecker Jr.
    Syntactic Extensions in the Programming Language Lisp.
    PhD thesis, Indiana University, August 1986.
  15. Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias Felleisen, and Bruce Duba.
    Hygienic macro expansion.
    In Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, pages 151-161.
  16. Peter Landin.
    A correspondence between Algol 60 and Church's lambda notation: Part I.
    Communications of the ACM 8(2):89-101, February 1965.
  17. MIT Department of Electrical Engineering and Computer Science.
    Scheme manual, seventh edition.
    September 1984.
  18. Peter Naur et al.
    Revised report on the algorithmic language Algol 60.
    Communications of the ACM 6(1):1-17, January 1963.
  19. Paul Penfield, Jr.
    Principal values and branch cuts in complex APL.
    In APL '81 Conference Proceedings, pages 248-256.
    ACM SIGAPL, San Francisco, September 1981.
    Proceedings published as APL Quote Quad 12(1), ACM, September 1981.
  20. Kent M. Pitman.
    The revised MacLisp manual (Saturday evening edition).
    MIT Laboratory for Computer Science Technical Report 295, May 1983.
  21. Jonathan A. Rees and Norman I. Adams IV.
    T: A dialect of Lisp or, lambda: The ultimate software tool.
    In Conference Record of the 1982 ACM Symposium on Lisp and Functional Programming, pages 114-122.
  22. Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan.
    The T manual, fourth edition.
    Yale University Computer Science Department, January 1984.
  23. Jonathan Rees and William Clinger, editors.
    The revised^3 report on the algorithmic language Scheme.
    In ACM SIGPLAN Notices 21(12), pages 37-79, December 1986.
  24. John Reynolds.
    Definitional interpreters for higher order programming languages.
    In ACM Conference Proceedings, pages 717-740.
    ACM, 1972.
  25. Guy Lewis Steele Jr. and Gerald Jay Sussman.
    The revised report on Scheme, a dialect of Lisp.
    MIT Artificial Intelligence Memo 452, January 1978.
  26. Guy Lewis Steele Jr.
    Rabbit: a compiler for Scheme.
    MIT Artificial Intelligence Laboratory Technical Report 474, May 1978.
  27. Guy Lewis Steele Jr.
    Common Lisp: The Language, second edition.
    Digital Press, Burlington MA, 1990.
  28. Gerald Jay Sussman and Guy Lewis Steele Jr.
    Scheme: an interpreter for extended lambda calculus.
    MIT Artificial Intelligence Memo 349, December 1975.
  29. Joseph E. Stoy.
    Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory.
    MIT Press, Cambridge, 1977.
  30. Texas Instruments, Inc.
    TI Scheme Language Reference Manual.
    Preliminary version 1.0, November 1985.


This document was generated on January, 22 2000 using texi2html 1.57.