健全なマクロ展開 - 構文オブジェクト (その2)

構文オブジェクトを採用すると、 KFFD のようにマクロ変換子が新しく挿入したシンボルを自動認識させることができるようになりました。 前回の例は、 マクロは大域だけで局所マクロを使わなかったので、 構文オブジェクトを使って展開対称式をマークしておくだけで展開ができました。 今度は、 局所マクロを利用できるようにします。

まず、 前回と同じやりかたで、 局所マクロに書き換えてみます。

【(letrec-syntax
   ((or (syntax-rules () ((_) #f) ((_ a) a) ((_ a b ...) (let ((t a)) (if t t (or b ...)))))))
   ((lambda (x) (let ((if list) (t x)) (or 1 t))) 2)):M1 E0】
M1 (() . E0)
E0 (((let macro <proc> . E0) (letrec-syntax special letrec-syntax . E0)
     (if special if . E0) (lambda special lambda . E0)))

letrec-syntax が構文環境に or マクロを追加して、 本体の展開に入る直前を考えてみます。 考慮するべきは、 構文環境の or マクロに束縛する識別子は構文オブジェクトなのか、 それともシンボルなのでしょうか。 識別子はシンボルの変換世代を表しているので、 健全性を保つには構文オブジェクトであるべきしょう。 展開環境を拡張して、 展開前を表す or:M1 とマクロ or を結びつけることにします。 なお、 以下では KFFD 流にシンボルにマークをすることにします。

【((lambda:M1 (x:M1) (let:M1 ((if:M1 list:M1) (t:M1 x:M1)) (or:M1 1 t:M1))) 2) E2】
E2 (((or:M1 macro <proc> . E2)) . E0)
M1 (() . E0)
E0

途中を飛ばして、 1 回目の or マクロの展開直前まで進めます。 展開時構文環境 E3 中で識別子 or:M1 を探すと、 E2 まで潜って or マクロを見つけます。

((lambda (x.1) ((lambda (if.2 t.2) 【(or:M1 1 t:M1) E3】) list x.1)) 2)
E3 (((if:M1 subst . if.2) (t:M1 subst . t.2))
    ((x:M1 subst . x.1)) . E2)
E2 (((or:M1 macro <proc> . E2)) . E0)
M1 (() . E0)
E0

or マクロで展開します。 or マクロの定義時構文環境 E2 を空リストで拡張した構文環境 M4 をマークとし、 変換で挿入されたシンボルにマークします。

((lambda (x.1) ((lambda (if.2 t.2) 
 【(let:M4 ((t:M4 1)) (if:M4 t:M4 t:M4 (or:M4 t:M1))) E3】) list x.1)) 2)
M4 (() . E2)
E3 (((if:M1 subst . if.2) (t:M1 subst . t.2))
    ((x:M1 subst . x.1)) . E2)
E2 (((or:M1 macro <proc> . E2)) . E0)
M1 (() . E0)
E0

なお、 syntax-rules テンプレートが挿入するものはクォートされたシンボルなので、 syntax-rules で変換をおこなうとテンプレート定義時の識別子と等価な意味をもつシンボルへと変換され、 変換後に新しく変換世代を表すマークが付きます。 このことは syntax-rules を等価な低レベル・マクロ変換手続きに変換するとわかります。

; (syntax-rules () ((_) #f) ((_ a) a) ((_ a b ...) (let ((t a)) (if t t (or b ...)))))
(lambda (x)
 (if (if (pair? (so-unwrap-syntax x))
         (null? (so-unwrap-syntax (cdr (so-unwrap-syntax x)))) #f)
  #f
 (if (if (pair? (so-unwrap-syntax x))
     (if (pair? (so-unwrap-syntax (cdr (so-unwrap-syntax x))))
         (null? (so-unwrap-syntax (cdr (so-unwrap-syntax (cdr (so-unwrap-syntax x)))))) #f))
  ((lambda (a) a) (car (so-unwrap-syntax (cdr (so-unwrap-syntax x)))))
 (if (if (pair? (so-unwrap-syntax x))
         (pair? (so-unwrap-syntax (cdr (so-unwrap-syntax x)))) #f)
  ((lambda (a b)
    (list 'let (list (list 't a)) (list 'if 't 't (cons 'or b))))
   (car (so-unwrap-syntax (cdr (so-unwrap-syntax x))))
   (cdr (so-unwrap-syntax (cdr (so-unwrap-syntax x)))))
  (error "no matching" (so-syntax->datum x))))))

ちなみに、 unwrap-syntax は、 ペアをマークしている構文オブジェクトから、 構文オブジェクトのペアへと作り直す手続きです。 さらに、 識別子のときは、 入れ子の識別子から、 最も深い識別子をとりだします。 so-extend-wrap は、 逆に構文オブジェクトを被せます。

(define (so-unwrap-syntax form)
 (if (so-syntax-object? form)
  (let ((env (so-syntax-object-env form)) (expr (so-syntax-object-expr form)))
   (cond
    ((symbol? expr) form)
    ((pair? expr) (cons (so-extend-wrap env (car expr)) (so-extend-wrap env (cdr expr))))
    (else (so-unwrap-syntax expr))))
  form))

(define (so-extend-wrap env form)
 (cond
  ((so-syntax-object? form) form)
  ((symbol? form) (make-so-syntax-object env form))
  ((pair? form) (make-so-syntax-object env form))
  (else form)))

またもや途中を飛ばして、 2 回目の or マクロの展開直前まで進めます。 展開時構文環境 E5 中に or:M4 そのものは存在しません。 続いて or をマークしている構文環境 M4 から定義時構文環境 E2 中でシンボル or を探してみるのですが、 やっぱり見つかりません。 E2 には or を M1 でマークした識別子しかないためです。 そこで、 定義時構文環境から or を探すとき、 or と or:M1 のどちらでも良いとしましょう。 これで、 or:M1 を選択して or マクロを見つけることができます。

((lambda (x.1) ((lambda (if.2 t.2) 
  ((lambda (t.3) (if t.3 t.3【(or:M4 t:M1) E5】)) 1)) list x.1)) 2)
E5 (((t:M4 subst t.3)) . E3)
M4 (() . E2)
E3 (((if:M1 subst . if.2) (t:M1 subst . t.2))
    ((x:M1 subst . x.1)) . E2)
E2 (((or:M1 macro <proc> . E2)) . E0)
M1 (() . E0)
E0

奇妙なことをしているように読めますが、 この挙動は、 構文環境に次のように Clinger-Rees のような rename denotation を登録するのに相当します。 例えば、 E2 での or:M1 は、 E2 の or へのシンボリック・リンクで、 E2 で or:M1 に一致したときは、 同じ E2 の or の denotation を代わりに利用せよという意味です。

E5 (((t:M4 rename t . E5) (t subst t.3)) . E3)
M4 (() . E2)
E3 (((if:M1 rename if . E3) (if subst . if.2) (t:M1 rename t E3) (t subst . t.2))
    ((x:M1 rename x . E3) (x subst . x.1)) . E2)
E2 (((or:M1 rename or . E2) (or macro <proc> . E2)) . E0)
M1 (() . E0)
E0

lookup 手続きで識別子の意味を求めることにします。 assoc-env は判定手続きを指定して環境から識別子を探します。 最初は展開時構文環境からなので、 同じ識別子かどうかで判定します。 2 度目は定義時構文環境からなので、 同じシンボルを含む識別子なら一致するように緩めた判定を使います。

(define (so-lookup env id)
 (cond
  ((so-assoc-env id env so-bound-identifier=?) => cdr)
  ((symbol? id) (make-so-subst id))
  ((so-syntax-object? id)
   (let ((env (so-syntax-object-env id)) (id (so-syntax-object-expr id)))
    (cond
     ((so-assoc-env id env so-rename-identifier=?) => cdr)
     (else (make-so-subst id)))))
  (else (error "so-lookup cannot happen"))))

(define (so-bound-identifier=? id1 id2)
 (and (so-identifier? id1) (so-identifier? id2)
  (or (eq? id1 id2)
   (and (so-syntax-object? id1) (so-syntax-object? id2)
    (eq? (so-syntax-object-env id1) (so-syntax-object-env id2))
    (eq? (so-syntax-object-expr id1) (so-syntax-object-expr id2))))))

(define (so-rename-identifier=? id1 id2)
 (or (so-bound-identifier=? id1 id2)
  (and (symbol? id1) (so-syntax-object? id2) (eq? id1 (so-syntax-object-expr id2)))))

この定義時構文環境からシンボルを見つけるやりかたは、 マクロだけでなく、 λ構文の束縛変数にも有効です。 SRFI 93 R6RS Syntax-Case Macros から例をとってみます。

【((lambda:M1 (f:M1)
    (let-syntax:M1 ((f:M1 (syntax-rules () ((_ x) x):M1))
                    (g:M1 (syntax-rules () ((_ x) (f x)):M1)
     (list:M1 (f:M1 1) (g:M1 1)))) (lambda (x) (+ x 1)):M1) E0】
M1 (() . E0)

let-syntax の本体中のマクロの展開直前まで進めると、 展開時構文環境 E3 に、 λ構文の束縛変数 f の置換規則と、 2 つの局所マクロが積み上がっています。

((lambda (f.1)
  (let-syntax ((f:M1 (syntax-rules () ((_ x) x):M1))
               (g:M1 (syntax-rules () ((_ x) (f x)):M1)
   (list【(f:M1 1) E3】【(g:M1 1) E3】))) (lambda (x.4) (+ x.4 1)))
E3 (((f:M1 macro <proc> . E2) (g:M1 macro <proc> . E2)) . E2)
E2 (((f:M1 subst . f.1)) . E0)
M1 (() . E0)
E0

E3 中で、 識別子 f:M1 はマクロ・キーワード、 識別子 g:M1 もマクロ・キーワードなので、 それぞれの変換をおこないます。 前者は定数 1 に展開され、 後者は (f:M4 1) に展開されます。 マーク M4 はマクロ g:M1 の定義構文環境 E2 を空フレームで拡張したものです。 展開時構文環境 E3 から識別子 f:M4 を探しても見つかりません。 今度はシンボル f を定義時構文環境 E2 から探すと、 E2 に f:M1 が見つかります。 そして、 E2 の f:M1 は変数 f.1 への置換規則です。 展開を終えた式を評価すると、 SRFI-93 の説明のようにリスト (1 2) が得られます。

((lambda (f.1)
  (let-syntax ((f:M1 (syntax-rules () ((_ x) x):M1))
               (g:M1 (syntax-rules () ((_ x) (f x)):M1)
   (list 1【(f:M4 1) E3】))) (lambda (x.4) (+ x.4 1)))
M4 (() . E2)
E3 (((f:M1 macro <proc> . E2) (g:M1 macro <proc> . E2)) . E2)
E2 (((f:M1 subst . f.1)) . E0)
M1 (() . E0)
E0

((lambda (f.1) (list 1 (f.1 1))) (lambda (x.4) (+ x.4 1))) ; => (1 2)

ついでに、 let-syntax ではなく letrec-syntax のときは、 両方のマクロの定義時構文環境が E3 に変わります。 そのため、 識別子 f:M4 から定義時構文環境 E3 のマクロ・キーワード f:M1 を見つけて、 マクロ変換して定数 1 にします。

((lambda (f.1)
  (letrec-syntax ((f:M1 (syntax-rules () ((_ x) x):M1))
                  (g:M1 (syntax-rules () ((_ x) (f x)):M1)
   (list 1【(f:M4 1) E3】))) (lambda (x.4) (+ x.4 1)))
M4 (() . E3)
E3 (((f:M1 macro <proc> . E3) (g:M1 macro <proc> . E3)) . E2)
E2 (((f:M1 subst . f.1)) . E0)
M1 (() . E0)
E0

((lambda (f.1) (list 1 1)) (lambda (x.4) (+ x.4 1))) ; => (1 1)

識別子を展開時構文環境から識別子そのものに一致する意味を探し、 見つからなかったら今度は定義時構文環境からシンボルそのものかシンボルにマークしてある識別子を探すことで、 局所マクロを扱えるようになります。