R6RSのライブラリの「レベル」指定はなぜ必要か？ - Scheme VM を書く

R6RSのライブラリにある「レベル」指定。
レベルの定義をR6RSで読んでもいまいちピンと来ない。本当に必要なの？と思ってしまう。こんな悶々とした日々を過ごしていたのですが今日やっと理解できたと思うのでまとめておきます。
R6RSは純粋に仕様書なので仕様の背景が語られることが少ないです。それが理解を妨げている一因だと思うのでここではR5RSとの比較しつつ考えます。

まずはライブラリのレベルに関連するR5RSからの大きな変化は何でしょうか？
僕が考えるのは

• ライブラリの仕組みの導入
• マクロの syntax-case の導入

の2つです。

ライブラリの仕組みの導入

R5RSでは基本的にファイルの先頭から式を順に評価するという仕組みで動いていました。
唯一の例外は (load ...) 手続きによるファイルのロードですが、これもまたロード対象のファイルを先頭から順に評価するもので大きな違いはありません。

一方R6RSではライブラリという仕組みが導入されました。
この動機はとてもよく理解できます。モダンなプログラミング言語であればライブラリを定義したり、ライブラリを使ったりといった機能は言語組み込みの機能として提供されています。これを Scheme にも導入しようというものです。
ライブラリの仕組みが組み込みで提供されていれば様々なライブラリを開発し共有することが可能になります。万歳！。

ライブラリの導入で大きく変わることの1つが、コンパイルや評価の順序が上から下へという単純なものではなくなることです。
例えば以下のようなライブラリがあるとします。

(library (greeting)
  (export (hello))
  (import)
  (define hello "hello\n"))

このライブラリ定義がファイル中に現れたときに (define hello ...) はすぐに評価されるでしょうか。
greeting ライブラリをプログラマが使いたいと思ったときに評価されるのが正しい姿なのでここではすぐには評価されません。

誤解を恐れず大雑把に言えば

(import (greeting))

というインポート式が現れたときに始めて greeting ライブラリの (define hello ...) が評価されます。

またライブラリが別のライブラリをインポートしている場合もあります。

(library (greeting)
  (export (hello))
  (import)
  (define hello "hello\n"))
(library (hello world)
  (export (say))
  (import (greeting))
  (define (say) (display hello)))

この場合 hello ライブラリの say の右辺が評価されるよりも前のタイミングで greeting ライブラリが評価されていないと hello が unbound variable になってしまうことが分かります。
つまりライブラリの導入で、ライブラリのインポート順序に依存して評価の順序を考えなければいけなくなったのです。

しかしここまでの話ならば他のプログラグラミング言語でも同じような事例はありますし、フェーズやレベルと言った概念は必要ありません。
ではなぜフェーズやレベルが必要なのでしょうか。そう Scheme にはマクロがあるからです。

マクロ

Scheme のマクロは簡単に言えば式変形です。
マクロの詳細な説明は別の場所に譲るとしてマクロは

• マクロの構文定義
• マクロの参照

の2箇所に現れます。
どちらも式をコンパイルするときに使われます。
コンパイルは

• マクロの構文定義に出会えば (マクロ名 . マクロ構文定義) というレコードをテーブルに登録する。
• (マクロ名 ...) という式に出会えば前述のテーブルからマクロ構文定義を取り出す。それを元に式変形をする。式変形の結果をコンパイルする。

という流れです。

さてライブラリ A が別のライブラリ B のマクロを参照している場合を考えましょう。
ライブラリ A をコンパイルするにはライブラリが B がコンパイルされている必要があることが分かります。
ライブラリが A が実行されるかどうか？は問題ではなくて、ライブラリ A のコンパイルはライブラリ B のコンパイルに依存していることに注意してください。
このようにコンパイルの順序にも依存関係があることが分かります。
これはマクロのせいです。

しかしまだレベルやフェーズが必要なほど複雑ではありません。インポートの依存関係の順にコンパイルをすれば良いだけです。
R5RSのマクロだけであればレベルやフェーズは必要ありません。

マクロの syntax-case の導入

実は R6RS に導入されたマクロの syntax-case が今回の犯人です。
syntax-case の全容を説明する事は僕にはまだできないので関連するところだけ説明します。
R5RS のマクロと比べて大きく変わったのが、マクロの展開にパターンマッチだけではなく式の評価も使えるようになった点です。

R6RSで使われている syntax-case の例を見てみましょう。

 (define-syntax mvlet
   (lambda (stx)
     (syntax-case stx ()
       [( [(id ...) expr] body0 body ...)
        (not (find-dup (syntax (id ...))))
        (syntax
         (call-with-values
             (lambda () expr)
           (lambda (id ...) body0 body ...)))])))

一見すると R5RS の syntax-rules のようにパターンマッチングで式変形をしているように見えます。
よく見ると (not (find-dup (syntax (id ...)))) の部分も式変形の条件になっています。
これが曲者でなんと find-dup という識別子を参照して手続きを呼んでいます。
勘の良い方はもう全てを理解したかもしれません。

(mvlet ...) というマクロ参照を発見した場合、式変形をするのですがその際に別のライブラリの評価結果を参照しているのです。
ちょっと難しいかもしれませんがこういうことです。

1. コンパイルしたい (mvlet ...) という式を見つけた
2. これはマクロだから式変形をしよう
3. マクロの構文定義に従おう
4. 構文定義によれば find-dup を呼ばないと。これは別のライブラリの識別子だね
5. そのライブラリの本体が評価されていないとだめだ

つまりライブラリのコンパイル時に別のライブラリの評価が必要なことがあるのです。（伝統的マクロも同じ問題に遭遇するはずです。多分）
さらに重要なことは処理系がこの情報をソースコードから読み取るのは難しいということです。（不可能ではないと思いますが）

まとめ

ここまで分かったことを整理しましょう。

• ライブラリの導入により
  • コンパイルの順序を考える必要がある
  • 評価の順序を考える必要がある
• syntax-case の導入により
  • コンパイル時に別のライブラリの実行（評価）が必要なことがある

この「コンパイル時に別のライブラリの実行（評価）が必要なことがある」に対処するために導入されたのが「レベル」です。
例えばライブラリ A 内で

(import (for (hello) expand))

とあればレベルが expand と指定されているのでライブラリ A のコンパイル時（展開時）にライブラリ hello が必要であることを示します。

一方

(import (for (hello) run))

とあればレベルが run と指定されているのでライブラリ A の実行時（評価時）にライブラリ hello が必要であることを示します。レベルを指定しない場合はこれがデフォルトになります。（合理的ですね）

やっとレベルの存在意義が理解できました。
ここまでの説明が理解できればR6RS:翻訳:R6RS:Librariesを読み返すとすんなり理解できるようになっていると思います。

注

このあたりをよく分かっている人がいらっしゃったらぜひこのまとめが「正しい」or「間違っている」と足跡を残していただけるととても助かります。間違っているのではとビクビクしています。
僕は超人ではないのでここまで理解するのに数日間の悩みと紆余曲折がありました。
一応下に過程を残しておきます。誰かのお役に立てば幸いです。

• レベルとフェーズを正しく理解し libray body がどのタイミングで実行されるかを考える。
• 実装する。
• うまく動いたら library body のコンパイル後コードが1つで済むような仕組みを考える。

• 他の場所にタイミングについて記述がないか?

ライブラリのエクスポート/インポートレベルについて

まずライブラリが以下の展開時情報と実行時情報に分かれること理解する必要がある。

• 展開時情報
  • インポートしているライブラリ
  • エクスポートしているキーワードのリスト
  • エクスポートしている変数のリスト
  • 変換式を評価するためのコード（多分マクロのこと）
• 実行時情報
  • 変数定義の右側の式を評価するためのコード
  • body 式を評価するためのコード

展開時というのはコンパイル時におけるマクロの展開や束縛の解決などのタイミングと思えば良い。

フェーズ

さて次にフェーズという新しい用語が出てくる。以下のような定義らしい。直感的には 0 と 1 は順序が逆の方がしっくりくるのにと思う。

フェーズ	ライブラリ内にある式が評価されるタイミングのこと
フェーズ0（実行時）	body や define の右側の評価のタイミングのこと
フェーズ1（展開時）	define-syntax マクロの展開のタイミングのこと

まあフェーズの定義は分かったが次の文が分からない。

define-syntax、let-syntax、もしくは letrec-syntax フォームが フェーズ n で評価されるコードに現れた場合、そのフォームの右側は フェーズ n+1 で評価される。

分からないのはしょうがないので読み進める。
この n とか n + 1 というのは他のライブラリとの相対関係で決まるらしい。まだ分からないな。
新しい用語「インスタンス」が出てきた。
インスタンス = 別のライブラリと相対的な特定のフェーズでそのライブラリの変数定義、式が評価されること
らしい。要はライブラリの本体が評価された状態のことだろうか。

戻って例に出てくるライブラリAとライブラリBの話を考える。ライブラリAがエクスポートしている変数をライブラリBが参照している場合の話。

• ライブラリBのトップレベル式が A を参照している場合 => フェーズ0というタイミングで A のインスタンスを参照
• ライブラリBのフェーズ1の式（マクロ）が A を参照している場合 => フェーズ1というタイミングで A のインスタンスを参照

これは上に出てきたフェーズの定義そのままだから理解できる。

新しい用語「訪問(visit)」が出てきた。
訪問 = 別のライブラリと相対的な特定のフェーズでそのライブラリの構文定義が評価されること
らしい。要はライブラリのマクロ定義が評価されることかな。

インスタンスの時と同じような例が出てきた。

• ライブラリBのトップレベル式が A のマクロを参照している場合 => フェーズ0というタイミングで A の訪問を参照

うんまあ分かる。しかし用語多すぎ。吐きそう。。

先ほど飛ばした

define-syntax、let-syntax、もしくは letrec-syntax フォームが フェーズ n で評価されるコードに現れた場合、そのフォームの右側は フェーズ n+1 で評価される。

はまだいまいち理解できていない。先に進む。

レベル

レベルとは識別子の字句特性でその識別子がどのフェーズで参照されるかを決定するものである。

ライブラリ内で定義された識別子はレベル 0 らしい。なので上の定義によりライブラリ内ではそれらの識別子はフェーズ 0 で参照される。
そのライブラリ内で定義されたものではなくインポートされたもののレベルはどう決まるのだろう？
これはユーザーが において指定するようだ。

例えば

(import (for (my-library) (meta 1)))

こんな感じ。レベルの指定は (meta レベル) の方式で指定する。
ちなみにレベルの指定を省略すると (meta 0) と解釈される。

ここで指定したレベルにエクスポート先の識別子のレベルを足し合わせたものがインポートされた識別子のレベルになる。
頭がわかめになってきた。

そもそもこのごちゃごちゃと長い仕組みは何のためにあるのだろうか？その背景を考えてみよう。
たぶん一番大きな動機は、Scheme には普通の式とは別にマクロがあることだと思う。
マクロには

• マクロの定義
• マクロを使う（参照）

がありそれらの評価タイミングと方法が違うのが問題。

R5RSではどうだっただろうか？
R5RSは基本的にファイルの先頭から順序よく式をコンパイルしていけば良かった。

• 通常の式に出会ったらコンパイルする
• マクロ定義に出会ったら（マクロ名 . マクロ定義本体）を登録
• マクロ参照に出会ったら登録されたマクロ定義を取り出し式変形を実行する。そして変形後の式をコンパイルする
• コンパイルが終わったら先頭から評価

という動き。

ここで例えばマクロ展開後の式に、まだ評価されていない識別子が現れたらどうなるか？
当然エラーになるし、それはその識別子を参照される前に評価されるようにコードを書かなかったプログラマの責任となる。

R6RSでは何が変わった？
ライブラリの概念が新たに追加された。ライブラリは定義されただけでは実行されない。これによりファイルの先頭から順序よく式を評価するという形が崩れた。
ライブラリはトップレベル式からのインポートをきっかけに実行される。トップレベルからインポートされたライブラリがまた別のライブラリをインポートする場合もあるだろう。
つまりライブラリに依存関係がある。例えばライブラリ A はライブラリ B をインポートしていれば A は B に依存している。
A が B に依存しているということは A の本体が評価される前に B が評価されている必要があることを意味する。

例：

;; ライブラリ A 内で B の変数を参照する
(define a-var1 (+ b-var1 3))

a-var1 の定義式が評価される前に b-var1 の定義が評価されている必要がある。
コンパイルの順序はどうだろうか？基本的には依存順にコンパイルする必要はないと思う。（インポートしているライブラリが何をエクスポートしているかは知る必要があるけど本体のコンパイルは別に後でも良い。）
この例だけを考えればインポート元を辿り、順にライブラリ本体を評価していくだけで良さそう。レベルとかフェーズとか要らない。

ではマクロがからんだ場合はどうか。

;; ライブラリ A 内で B のマクロを参照する
(define a-var1 (b-macro1 3))

マクロはコンパイル時に展開されるべきであるから A のコンパイルの前に B のコンパイルがされている必要がある。ここがまず変数の場合と違う。
あとの違いは b-macro1 の定義によるよね。
うーん。R5RS のマクロと R6RSのマクロに何か違いがあるんだっけか？うあか。。
これで大体理解できたぞ。まとめ直そうλ...。