Scheme:マクロ:CommonLispとの比較:意味論

Scheme:マクロ:CommonLispとの比較:意味論

前回までのあらすじ

何が問題なのか

Shiro(2007/05/16 04:43:15 PDT追記): 論点がわかりにくいという話があったので最初に整理しておきます。

R5RSにおいて、Schemeの正式な構文は 7.1節に、 基本構文(lambda、if、set!、関数呼び出し、変数参照)のセマンティクスは 7.2節に、 そして、その他の構文を基本構文に還元する規則が高レベルマクロを使って 7.3節に 定義されています。

なお、トップレベル構文とマクロのセマンティクスについては形式的な定義が あるわけではなくて、それぞれ 5章4.3節にて 自然言語による定義が与えられています。

さて、問題となっているのは7.1節の構文定義です。

ここでよーく注意して読んで欲しいのですが、R5RSから読み取れるのは次の通りです。

  1. <expression>として読める入力は<datum>としても読めなければならない。 つまり、プログラムコードをS式としてreadできることは保証されている。 (7.1.2節の最初の文)
  2. <expression>のBNFのterminalをよく見ると、quoteの中身に<datum>が 出てくる以外は、7.1.1節の字句解析のトークンが直接使われている。

しかし、<expression>が<datum>でなければならないとはどこにも書かれていない のです。

7.1.2節の最初の文が微妙なところなんですが、文字どおり取ればこれは プログラムテキストをS式としてreadすれば<datum>が得られると言っているだけで、 Scheme処理系が、プログラムテキストをreadしてから構文解析をせよとはどこにも書いていない、 言い替えれば、プログラムをS式としてではなく、readとは全く別のパーザによって 構文解析して、直接リストではない抽象構文木を作り出して実行する 処理系があっても良いということです。

この「readとは別のパーザ」、これを仮にxreadと呼ぶことにしますが、xreadは 7.1.3の文法さえパーズできればSchemeの規格を満たしていることになります。 ここで、以下のふたつのテキストがあったとします。

(if a . (b c))

(if a b c)

7.1.2節の文法では両者とも<datum>に適合し、 これらをデータとしてreadした場合は、両方ともに4要素のリストが得られます。 しかし、最初のテキストは7.1.3節の<expression>には適合しないので、 xreadが最初のテキストをエラーにしたとしても、Schemeの規格上は問題ありません。 (もしこれが「'(if a . (b c))」のようにクオートされていたら、7.1.3節の 文法でも「<quotation> → '<datum> 」 の規則にマッチするのでxreadは ちゃんと読めるはずですが)。

S式は'if', 'a', 'b', 'c'からなる4要素のリストを (if a b c) と表現しても (if a . (b c)) 表現しても良いので、 マクロがS式→S式の変換を行ったとしても、変換後のS式が<expression>の 文法定義に適合する保証が無い、つまりS式→S式のマクロはこの規格内では定義できない、 ということになります。

R5RS Schemerによる反論

Shiro: 以前、c.l.lで「SchemeはS式で意味論が定義されていないので Lispではない」という主張を読んだことは確かにあったんですが、マクロに対する implicationにまで考えが及んでいませんでした。黒田さんに指摘されてはたと 膝を打った次第です。

SchemeがCL風のマクロでなく、hygienic macroを必要と したのは、レキシカルクロージャという単一の概念で実行時のモデルを綺麗に 整理したのと同じことをマクロ(プログラム変換)の領域で再び行おうとしている、 という高邁な目標によるだけでなく、 R5RSまでの正式なセマンティクスではS式からS式へのマッピングとしての マクロを定義出来ないという現実的な要請もあったのかもしれません。

R5RSのマクロ (syntax-rules) の仕様は確かに、 適切なtokenizationさえ行われれば、文字の並びでパターンマッチをかけて 別の文字の並びへと変換するというふうに読めるので、 上記のSchemeの意味論定義とは矛盾しないことになります。 (現実的に、マクロ展開器はreadしたS式でマッチをかけるのが普通ですが、 それはtokenizationやマッチングを行うのに楽だからであって、 仕様上はS式→S式の変換を行う必要はありません。)

例えば、次の2つのマクロはGaucheでは現実的にほとんど同じように 動作しますが、Schemeの仕様上、foo2は「不正なプログラム」を 生成するとして弾く処理系があってもおかしくはありません:

(define-syntax foo1
  (syntax-rules ()
    ((foo1 x ...) (list x ...))))

(define-syntax foo2
  (syntax-rules ()
    ((foo2 . x) (list . x))))

「(foo2 1 2 3)」は「(list . (1 2 3))」へと展開されますが、 R5RS Schemeの定義によれば手続き呼び出し構文は「(<op> <arg> ...)」 であり、上の展開結果は正しい手続き呼び出し構文とは言えないからです。

一方、上の仕様から「(foo1 1 2 3)」を「(list 1 2 3)」へと置き換える S式を経由しないマクロ展開器を生成することは可能です (例えば全てを文字列で扱って、xへのマッチを部分文字列で扱う)。

GaucheNightで私は「マクロの健全性とパターンマッチは直交する 概念」と発言しました。確かに実装側から見るとパターンマッチは syntactic closureを分解するための便利な機能のひとつにすぎず、 健全性はsyntactic closureそのもので担保されるので、 両者は直交するのですが、 R5RS Schemeのセマンティクスを保つためには、マクロが パターンマッチで定義されることが(したがって文字の並びから 文字の並びへの変換器という実装も許されることが) 必要であった、とも言えそうです。

R6RS Schemerによる反論

でも、確かに上の説明は苦しい。Schemerにもその自覚がある何よりの証拠は、 R6RSで意味論の定義方法が変えられていることです。 正確には、現在のドラフトであるR5.92RSでは、ですが、 おそらくここは大きく変更されることは無いと思われるので、 R5.92RSを基準に見てゆきましょう。(ちなみにたぶん来週あたりに 次のドラフトR5.93RSが出る予定なんで、リンクは変わっちゃうかもしれません)

R6RSでは、言語の定義は明確に2段構えになります。 Chapter 3. Lexical Syntax and Read Syntaxにおいてまず外部表現から 内部表現へのマッピングが定められ、 プログラムの意味は内部表現の組み合わせで決定されることが明記されています。

R6RSマクロではパターンマッチ以外の方法でのマクロ (具体的にはsyntax-case) が 入るはずですから、この変更はどうしても必要なものだったわけですが、 これでCLerからみてもSchemeはまともなLispの仲間入りが出来るかもしれません。

(R6RSが成立すれば、ですが…)

名前空間?

もうひとつGaucheNightで黒田さんからツッコミが入ったのが、 「R6RSではモジュールシステムが入るそうだけど、そしたらモジュール名と 変数名で名前空間が分かれるってことじゃない?」って点でした。

まあショートアンサーはyesなんですが、 R6RS Schemeではモジュール/マクロの展開とプログラムの実行は別のレイヤで 行われることになっています。つまり、 プログラムとそこから参照されている全てのモジュールを一度読み込んで マクロ展開を含むグローバルなプログラム変換を行い、得られたプログラムを改めて 実行する、という実装も許されるということです。

syntax-case等の低レベルマクロを使った場合、グローバルプログラム変換の 段階でSchemeコードが走ることになりますが、その環境と、 実行時に走るSchemeコードの環境は完全に別個です。

なので、名前空間が分かれると言っても、CommonLispのように 実行時に複数の名前空間が存在するわけではなくて、プログラム変換の 各フェーズに対応する名前空間が存在する、という解釈になります。 実行時に見える名前空間はひとつだけで、そこにはモジュール名というものは 既に存在しないことになっているわけです。

ちなみに低レベルマクロの実行中に他のマクロを必要とする場合などは、 プログラム変換が何段階かに渡って行われることになります。 この場合も各変換フェーズの環境は独立している、はずです(私が議論にちゃんと ついてってるなら)。


Tag: gauche.night

More ...