Let's start Scheme

2013-04-13

健全なマクロ

探せば山ほど解説があるので、今更というかGoogle検索の妨害するだけな気がするけど。

Twitterで健全マクロの実装をされている方がいて、そういえばコンパイラの環境を重点に置いた解説記事ってあったかなぁと思ったのがきっかけ。たぶんどこかにあるだろうけど・・・

まずは以下のコードを考える。
(import (rnrs))
;; from Ypsilon
(define-syntax define-macro
  (lambda (x)
    (syntax-case x ()
      ((_ (name . args) . body)
       #'(define-macro name (lambda args . body)))
      ((_ name body)
       #'(define-syntax name
           (let ((define-macro-transformer body))
             (lambda (x)
               (syntax-case x ()
                 ((e0 . e1)
                  (datum->syntax
                   #'e0
                   (apply define-macro-transformer
                          (syntax->datum #'e1))))))))))))

;; hygiene
(let ((x 1))
  (let-syntax ((boo (syntax-rules ()
                      ((_ expr ...)
                       (let ((x x))
                         (set! x (+ x 1))
                         expr ...)))))
    (boo (display x) (newline))))

;; non hygiene
(let ((x 1))
  (define-macro (boo . args)
    `(let ((x x))
       (set! x (+ x 1))
       ,@args))
  (boo (display x) (newline)))

;; expanded
(let ((x 1))   ;; frame 1
  (let ((x x)) ;; frame 2
    (set! x (+ x 1))
    (display x) (newline)))

;; frame 1
'(((x . 1)))

;; frame 2
'(((x . x))  ;; *1
  ((x . 1)))
話を簡単にするために、環境フレームは変数と値のペアをつないだもの(alist)とする。まぁ、多くの処理系がこの形式を使ってると思うけど。健全なマクロと非健全なマクロそれぞれの展開形はどちらも同じに(というと嘘が入るが)なる。コメントのframe 1及び2はその下にあるコンパイル時の環境フレームのイメージを示している。

ここで問題にするのは*1がそれぞれの場合で何になるかということ。

健全なマクロではマクロ内で定義された変数をマクロ外から参照することはできない。なので展開後の式とframe 2の環境イメージは実際には以下のようになる。
(let ((x 1))
  (let ((~x x))
    (set! ~x (+ ~x 1))
    (display x) (newline)))
;; frame
(((~x . x))
 ((x . 1)))
実際にどうなるかは処理系によって違うので、上記はあくまでイメージ。ここで問題になるのはletで束縛される変数のみがリネームされるということ。値の方は一つ上の環境フレームから参照されなくてはならない。(正直、これが実装者泣かせな部分の一つだと思っている。)
これの解決方法は僕が知っているだけで2つあって、1つは多くのR6RS処理系が取っている(Sagittarius以外はそうじゃないかな?)マクロ展開フェーズを持たせること。もう一つはSagittariusが取っているマクロ展開器が実行時環境とマクロ捕捉時環境の両方を参照する方法(正直お勧めではない)。

最初の方法だと、マクロ展開器は何が変数を束縛するかということを知っていなければいけない。 そうしないと上記の例のように変更してはいけないシンボルまでリネームしてしまうことになるからだ。値側のシンボルも実はリネームされるんだけど、マクロ束縛時の環境フレーム(frame 1)を参照して外側のletで束縛されたシンボルを見つけて同じ名前にするということが行われる。

2番の方法だと、マクロ展開器は両方の環境を適切に参照しつつ、コンパイラも変数の参照時に多少トリックが必要になる。正直書いててバグの温床にしかならないなぁと思ったのでお勧めではないが、この方法ならマクロ展開器は何が変数を束縛するかということを知らなくてもいいので、重複コードが多少減る。

ただ、どちらの場合もsyntax-rulesを実装するだけならたぶん必要なくて、Chibi Schemeのようにsyntactic closureを使ってer-macro-transformerを実現するとかでなんとかなる。(syntactic closure自体の実装で環境の束縛とか参照が必要にはなるけど、上記ほど複雑にはならない・・・はず。)

非健全なマクロではシンボルはリネームされないので、例で上げた展開後フォームそのままとなる。CLだと上記のようなマクロをSchemeのように動かしたいなら(gensym)とかwith-unique-namesとかを多用する必要がある。Lisp-2だったらたぶんそれでもいいだろうけど、Lisp-1だと泣けるだろうなぁと思う。

思ったとおり普通のマクロ解説記事の劣化版になってしまった。

No comments:

Post a Comment