健全なマクロ展開 - reversed syntactic closures (その1)

明示的リネーミング・マクロの元になった Clinger-Rees (1991) の記載によると、 R4RS Scheme (1991) を目指して 1988 年から始まった議論の中で、 Bawden-Rees の syntax-closures (1988) を改良することで syntax-rules の実装に利用する方法を C. Hanson が発見していました。

⇒ W. Clinger, J. Rees, Macros That Works, 1991

Chris Hanson implemented a prototype and discovered that an implementation based on syntactic closures must determine the syntactic roles of some identifiers before macro expansion based on textual pattern matching can make those roles apparent [6].

[6] Chris Hanson. Personal communication.

その手法は C. Hanson による syntactic closures (1991) の改訂版で知られるようになりました。さらに、 Hanson によると、 syntax-rules の実装のためにこの技巧を使うのは発明したのは Bawden だそうです。 その後、 この手法が reversed syntactic closures と呼ばれるようになりました。

⇒ C. Hanson, A Syntactic Closures Macro Facility, 1991

Previous syntactic closure proposals did not have an identifier data type - they just used symbols.

As discussed earlier, an identifier is either a symbol or an alias. An alias is implemented as a syntactic closure whose form is an identifier:

The use of aliases to implement syntax-rules was invented by Alan Bawden (who prefers to call them synthetic names).

識別子 (identifier) は、 上記のように、 定義時構文環境と識別子を閉じ込めた構文クロージャか、 シンボルのいずれかのバリアント型です。 識別子扱いの構文クロージャを別名と呼び、 他の構文クロージャより特別扱いします。 どういう特別扱いかというと、 構文環境の束縛対の左側に現れることを許します。 他の構文クロージャは、 このような使い方を禁止します。 構文環境の束縛対の左にある識別子は、 別名もシンボル同様に eq? で比較します。

識別子 : シンボル | #<SC 定義時構文環境 () 識別子>
構文環境 : (((識別子 . 意味) ...) ...)
意味 : (subst . シンボル)
     | (macro 手続き . 定義時構文環境)
     | (special . キーワード)

Hanson-Bawden の reversed syntactic closures は、 明示リネーミング・マクロよりさらに低レベルな機構であり、 これを作法に従って利用することで、 明示リネーミング・マクロと等価な使い方ができます。 この作法によって、 新しく挿入されたシンボルを世代ごとに区別すると同時に、 構文キーワードとして定義時構文環境から意味を得るようになります。

  1. 変換世代ごとに定義時構文環境とシンボルを閉じ込めた別名を構文クロージャとして作ること。
  2. 変換世代内で 1 つのシンボルにつき 1 つの別名を使いまわし、 eq? で同一判定できるようにしておくこと。
  3. identifer=? を使い、 展開時構文環境下の展開対象式の識別子の意味と、 定義時構文環境下のシンボルの意味が同じかどうか調べること。
  4. 変換が終わった展開対象式は、 展開時構文環境で展開を続けること。

簡易 cond 構文を書くと、 この作法が明示リネーミング・マクロの書き方であることを納得できます。

(define-syntax cond
 (sc-macro-transformer
  (lambda (form expanding-env)
   (capture-syntactic-environment (lambda (defined-env)
    (make-syntactic-closure expanding-env '()
     (let ((alias_if (make-syntactic-closure defined-env '() 'if))
           (alias_let (make-syntactic-closure defined-env '() 'let))
           (alias_temp (make-syntactic-closure defined-env '() 'temp))
           (alias_begin (make-syntactic-closure defined-env '() 'begin))
           (alias_cond (make-syntactic-closure defined-env '() 'cond)))
      (match form
       ((_ (pred) clauses ...)
        `(,alias_let ((,alias_temp ,pred))
          (,alias_if ,alias_temp ,alias_temp (,alias_cond ,@clauses))))
       ((_ (pred form1 ..1) clauses ...)
        (if (identifier=? expanding-env pred defined-env 'else)
         `(,alias_begin ,@form1)
         `(,alias_if ,pred (,alias_begin ,@form1) (,alias_cond ,@clauses))))
       ((_) ''unspecified)))))))))

作法があるなら、 それを組み込んだ er-macro-transformer に頼る方が良いでしょう。 rename 手続きで変換世代ごと別名を作り、 世代内で同じシンボルに同じ別名を使いまわします。 compare には identifer=? を内部で使います。 さらに、変換後の置換対象式を展開時構文環境で展開を続けるように展開器を作っておくことで、 変換後の式を展開時構文環境の構文クロージャにする操作がいらなくなります。

(define (er-macro-transformer proc)
 (lambda (form expanding-env defined-env)
  (let ((table '()))
   (let ((rename (lambda (x)
          (cond
           ((assq x table) => cdr)
           (else
            (let ((alias_x (make-syntactic-closure defined-env '() x)))
             (set! table (cons (cons x alias_x) table))
             alias_x)))))
         (compare (lambda (x y)
          (identifier=? expanding-env x expanding-env y))))
    (proc rename compare)))))

それでは、 いつもの式を手動で展開してみましょう。

【((lambda (x) (let ((if list) (temp x)) (or 1 temp))) 2) E0】
E0 (((or macro or-proc . E0)
     (let macro let-proc . E0)
     (lambda special lambda . E0)
     (if special if . E0)))

let 構文を変換します。 マクロ変換後の展開時環境はそのままで、 syntactic closures のように定義時構文環境に変わることはありません。 変換によって展開対象式に lambda シンボルの別名が入ります。 この際、 シンボルと定義時構文環境の結びつきを構文オブジェクトで表すため、 Clinger-Rees のように展開時構文環境へリネームされたシンボルを置く必要がなくなります。 以下では、 別名の eq? 同一性を表すために、 コロンと識別番号を構文クロージャにつけることにします。

((lambda (x.1)【(let ((if list) (temp x)) (or 1 temp)) E1】) 2)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1)【((#<SC:1 E0 () lambda> (if temp) (or 1 temp)) list x) E1】) 2)
E1 (((x subst . x.1)) . E0)
E0

識別子の意味を求めるときは、 最初に展開時構文環境から意味を探します。 見つからなかったとき、 識別子がシンボルのときは、 シンボル自身への置換規則とします。 識別子が構文クロージャのときは、 続けて構文クロージャに記録済みの定義時環境下で、 構文クロージャに記録してあるシンボルを使って意味を探します。 このふるまいは Clinger-Rees と等価です。 上の 1 番の構文クロージャは展開時構文環境に eq? になる束縛対は含まれていないので見つからなかったことになり、 今度は E0 から lambda シンボルを探して意味を求めます。 特殊形式 lambda として登録済みなので、 λ構文の展開をおこないます。 置換規則で展開時構文環境を拡張し、 本体を or マクロで変換します。 変換後を展開してλ構文にします。

((lambda (x.1) ((lambda (if.2 temp.2)【(or 1 temp) E2】) list x.1)) 2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1) ((lambda (if.2 temp.2)
 【(#<SC:2 E0 () let> ((#<SC:3 E0 () temp> 1))
    (#<SC:4 E0 () if> #<SC:3 E0 () temp>
     #<SC:3 E0 () temp> (#<SC:5 E0 () or> temp))) E2】) list x.1)) 2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1) ((lambda (if.2 temp.2)
 【((#<SC:6 E0 () lambda> (#<SC:3 E0 () temp>)
     (#<SC:4 E0 () if> #<SC:3 E0 () temp>
      #<SC:3 E0 () temp> (#<SC:5 E0 () or> temp))) 1) E2】) list x.1)) 2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

このλ構文の束縛変数は構文クロージャなので、 左側が構文クロージャになる置換規則との束縛対を展開時構文環境に加えます。

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3)
  【(#<SC:4 E0 () if> #<SC:3 E0 () temp>
     #<SC:3 E0 () temp> (#<SC:5 E0 () or> temp)) E3】) 1)) list x.1)) 2)
E3 (((#<SC:3 E0 () temp> . subst temp.3)) . E2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

if 構文を展開します。 if 構文の最初の 2 つの式は構文クロージャであり、 しかもこの構文クロージャと eq? である束縛対が展開時環境に存在します。 この束縛対で置換規則に結びついているので、 構文クロージャを束縛変数シンボルへ展開します。

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3)
   (if【#<SC:3 E0 () temp> E3】
   【#<SC:3 E0 () temp> E3】【(#<SC:5 E0 () or> temp) E3】)) 1)) list x.1)) 2)
E3 (((#<SC:3 E0 () temp> . subst temp.3)) . E2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3)
   (if temp.3 temp.3【(#<SC:5 E0 () or> temp) E3】)) 1)) list x.1)) 2)
E3 (((#<SC:3 E0 () temp> . subst temp.3)) . E2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

続いて or を変換すると、 すぐに構文環境 E3 で temp シンボルを展開します。 するとm E3 中に、 temp.2 シンボルへの置換規則が見つかります。

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3)
   (if temp.3 temp.3【(#<SC:5 E0 () or> temp) E3】)) 1)) list x.1)) 2)
E3 (((#<SC:3 E0 () temp> . subst temp.3)) . E2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3) (if temp.3 temp.3【temp E3】)) 1)) list x.1)) 2)
E3 (((#<SC:3 E0 () temp> . subst temp.3)) . E2)
E2 (((if subst . if.2) (temp subst . temp.2)) . E1)
E1 (((x subst . x.1)) . E0)
E0

((lambda (x.1) ((lambda (if.2 temp.2)
 ((lambda (temp.3) (if temp.3 temp.3 temp.2)) 1)) list x.1)) 2)

このように Hanson-Bawden を作法に従って使うことで Clinger-Rees と同等の働きをします。 Hanson-Bawden 展開器のリファレンス実装は、 MIT Scheme の runtime/syntax.scm とそれの補助モジュールで、 Bawden-Rees 展開器を元に識別子を扱えるようにしてあります。