Let's start Scheme

2014-12-29

datum->syntaxに潜む罠

マクロ関連のバグの話(もう何度目だろう・・・)

R6RSにはdatum->syntaxという手続きがある。あるデータ(シンボル、リスト何でも可)を構文オブジェクトに変換するというものである。基本的な考え方は非常に簡単で、第一引数で受け取った構文情報を第二引数で受け取った値に付与して返すと思えばよい。これを使うことでスコープを捻じ曲げることが可能になる。

さて、本題はここから。端的なバグは以下のコード:
(import (rnrs))

(define-syntax let-it
  (lambda (x)
    (define (bind-it k binding)
      (syntax-case binding ()
        ((var . val) 
         (let ((name (syntax->datum #'var)))
           #`(#,(datum->syntax k name) val)))
        (_ (error 'let-it "invalid form"))))
    (syntax-case x ()
      ((k ((var . val) rest ...) body ...)
       (with-syntax (((var1 val1) (bind-it #'k #'(var . val))))
         #'(let ((var1 val1))
            (let-it (rest ...) body ...))))
      ((_ () body ...)
       #'(begin body ...)))))

(let-it ((name . 'name)) name)
まぁ、特に何もない単にlet*を使いにくくしただけのコードなのだが、Sagittariusではこれがエラーになる。バグは敢えてdatum->syntaxで変換している箇所にある。一言で言えば、kの構文情報では変数の参照が出来ないというものである。実はこのケースのみだけで言えば直すのは簡単なのだが、let-itが局所マクロで定義された際等がうまくいかない。

自分の頭を整理するために多少問題を詳しく書くことにする。このケースでは最初のnamelet-itが使用された際の構文情報を持つが、二つ目のnameとはeq?での比較において別の識別子となる(ちなみにdatum->syntaxを使わなかった場合においてはマクロ展開器は同一オブジェクトにする)。この場合に環境の参照が同一の環境を持つ識別子を同一識別子と見なさないのでエラーとなる。なお、この挙動は歴史的理由(主に僕の無知)によるところが多い・・・

ここで、同一環境を含む識別子を同一オブジェクトとした場合に起きる問題を見る。マクロ展開器は以下の場合において識別子の書き換えを行わない:
  • 識別子がパターン変数の場合
  • 識別子がテンプレート変数の場合
  • 識別子が既に局所的に束縛されている場合
上記二つは特に問題にならないのだが、3つ目が以下のコードにおいて問題になる:
(let ()
  (define-syntax let/scope
    (lambda(x)
      (syntax-case x ()
        ((k scope-name body ...)
         #'(let-syntax
               ((scope-name
                 (lambda(x)
                   (syntax-case x ()
                     ((_ b (... ...))
                      #`(begin
                          #,@(datum->syntax #'k
                                (syntax->datum #'(b (... ...))))))))))
             body ...)))))

  (let ((xxx 1))
    (let/scope d1
      (let ((xxx 2))
        (let/scope d2
          (let ((xxx 3))
            (list (d1 xxx) ;; *1
                  (d2 xxx)
                  xxx      ;; *2
                  ))))))
)
同一環境を持つ識別子を同一識別子とみなすと、上記の印をつけた変数が両方とも3
を返す。マクロ展開器が識別子の書き換えを行わないため、全てのxxxが同一環境を持つからである。
これだけ原因がはっきりしているのだからマクロ展開器が展開するごとに識別子を生成しなおせばいいような気がしないでもないのだが、上記の歴史的理由により環境を参照するコードが自分でも理解不能な複雑怪奇なことになっているためなかなか手が出せないでいる。ここは一発腹を決めるしかないか。

追記:
上記のletで束縛されるxxxは最初のもの以外は全て同一の環境を持つ識別子に変換される。っで、(d1 xxx)は正しく最初のxxxのみをもつ、つまり変換された識別子と同一の環境をもつ、識別子に変換されるので環境の頭にある3が束縛されたxxxにヒットする。

問題はどうこれを解決するかなんだけど、ぱっと思いつく解決方法としては、束縛が発生するたびに識別子の書き換えを行い適切な環境に変更してやるというものだろうか。それをやることのデメリットとしては:
  • 式一つコンパイルするのにO(n^2)のコストがかかる
  • コンパイラが持つ構文全てをいじる必要がある
あたりだろうか。最初のはライブラリになっていればキャッシュが効くので初回のみと割り切れなくもないのだが、二つ目のが辛い。バグを埋め込まない自信がないという話ではあるのだが、コンパイラはかなりの数(10以上)の束縛構文を知っているので全て書き換える必要がある。ものぐさな僕には辛い話である。マクロ展開器の方でやれないか考えてみたのだが、それ自体は束縛構文が何かということを知らないのでどの識別子を書き換える必要があるのかが分からないという問題がある。とりあえず直せる部分だけ直して寝かせる方針かなぁ、いつもどおり・・・

No comments:

Post a Comment