Hygenic macroの名前衝突回避方法達:KFFD, Lazy KFFD, syntactic-closure
マクロ展開で識別子の意図しない捕捉を防ぐための手法を紹介します。
Lisp系言語では、構文を抽象化するマクロと呼ばれる機能があります。動作としては、式を入力し、別の式を返すことを行います。マクロを適用した結果には、マクロが挿入した識別子とマクロに入力した式に含まれていた識別子が混在しています。これを区別せずに扱うと意図していない挙動を引き起こすかそれを回避するために名前空間を考えながらコーディングをしなくてはいけません。この問題を回避するためにSchemeなどの言語にはうまく識別子の衝突を回避する機構を備えたマクロシステムが存在します。この文章では、自動で識別の衝突を回避するアルゴリズムであるKFFD, Lazy KFFDと手動で識別子がどの環境で補足したいかを与えるマクロシステムであるsyntactic-closureを紹介します。
macroとhygenic macro
hygenic macroを説明するために、my-orというorと同等のことをするマクロを使います。
なお、syntax-rulesをわかっている人はこのセクションを読み飛ばしてもよいです。
(define-syntax my-or
(syntax-rules ()
((_) #f)
((_ x) x)
((_ x rests ...)
(let ((tmp x)) (if tmp tmp (my-or rests ...))))))
my-orの解説とsyntax-rules
my-orがマクロ名で、syntax-rulesの2番目のカッコ内の各要素が各展開規則になっています。
各展開規則は、((_ x) x)のように長さ2のリストで表現され、第1要素がパターンで第2要素をテンプレートです。入力とパターンの形状が同じのときに、パターン中のシンボル(パターン変数と呼ばれる)にマッチしたものを記録して、template内の同じパターン変数に代入して返します。_は例外的にパターン変数ではありませんが、任意の値とマッチします。...は前の要素の0回以上の繰り返しです。
これは展開例です。 1回目の展開は、3番めのパターンにマッチし、2回目の内部のmy-orは2番めのパターンにマッチします。
(my-or (some-proc1 x y) z)
;; => (let ((tmp (some-proc1 x y))) (if tmp tmp (my-or z)))
;; => (let ((tmp (some-proc1 x y))) (if tmp tmp z))
hygenicマクロがないとどうなるのか
hygenicマクロは、マクロが挿入した識別子とマクロに入力した式に含まれていた識別子をそれぞれの環境で評価できるようリネームしてくれるようなマクロです。
my-orでは、出力結果にlet,ifを含みますが、展開場所でletとifが別のものにおきかえられているとmy-orは正しく動かないでしょう。
ifを別のもの(#<ifでないなにか>)に置き換えた環境で、展開した例です。
(if a b)のifは#<ifでないなにか>で評価されることが期待され、my-orが挿入したifは、#<ifでないなにか>ではないことが期待されます。これは、let-syntaxで定義したifをif-renamed0など別の名前に置き換えれば良いです。
(let-syntax ((if #<ifでないなにか>))
(my-or (some-proc1 x y) (if a b)))
;;renameがもし行われないと、評価結果が意図しない挙動になる
;; => (let-syntax ((if #<ifでないなにか>))
;; (let ((tmp (some-proc1 x y))) (if tmp tmp (if a b)))
;;renameされた例
;; => (let-syntax ((if-renamed0 #<ifでないなにか>))
;; (let ((tmp (some-proc1 x y))) (if tmp tmp (if-renamed0 a b)))
syntactic-closure
syntactic-closureは、式をどの環境で評価するかを陽に与えることで名前の衝突を防ぐマクロシステムです。さきほどのmy-orをsyntactic-closureの例を示します。syntactic-closureは処理系ごとに書き方が少し異なります。これはmit-schemeでの例です。
syntactic-closureを使ったマクロを作るには、sc-macro-transformerというシンタックスを使います。これに2つの引数を持った手続きを渡します。この手続きの1つめの引数(例だとexpression)は、マクロに渡された式で、2つめの引数(例だとenv)は、マクロを呼び出した環境です。各部分式で評価したい環境を指定するには、make-syntactic-closure手続きを使います。これの第一引数は評価したい環境です。第2引数は(今回は空ですが)意図的に健全性を破る目的でenvにはないが補足したい識別子のリストです。第3引数は部分式を渡します。make-syntactic-closureによって環境をしていされていない部分は、マクロを定義した環境で評価されます。
(define-syntax my-or
(sc-macro-transformer
(lambda (expression env)
(cond
((null? (cdr expression)) #f)
((null? (cddr expression))
(make-syntactic-closure env '() (cadr expression)))
(else
`(let ((tmp ,(make-syntactic-closure env '() (cadr expression))))
(if tmp tmp (my-or ,@(map (lambda (x)
(make-syntactic-closure env '() x))
(cddr expression))))))))))
KFFD
KFFDは、とても単純なリネームアルゴリズムです。
マクロ展開ごとにユニークなタグを生成して、1回のマクロ展開する度に変換後の式の中のタグをもっていない識別子にユニークなタグを付与します。タグをもっていない識別子というのは、マクロが挿入した識別子ということです。すべてのマクロ展開後に外側から式を探索して、ローカル束縛を見つけると、そのローカル変数とそれと同じタグと変数名をもつ識別子をユニークな識別子に置き換えます(alpha renaming)。
KFFDにおける"識別子"は、シンボル(変数名)とタグの2つのフィールドを持つ構造体です。最初にプログラムを一回探索してシンボルを"識別子"に変換する必要があります。
実装にはユニークなタグは数値として表現していて、1回のマクロ展開ごとにインクリメントするようなカウンタが使われます。参考文献にあるBeautiful Codeでtime stampと読んでいるのはこのためです。
KFFDの例
lazy KFFD
lazy KFFDは、KFFDの探索する回数を少なくするように改良されたリネームアルゴリズムです。
KFFDの毎回の展開ごとのタグをつけたい識別子の探索を遅延化することで時間のオーバーヘッドを減らすようにしています。lazy KFFDでは、シンボルではなく式に対して(複数の)タグをつけることをしています。次以降のマクロ展開でcar/cdr操作でタグ付きの式を分解するときに、car部とcdr部の式にそれぞれにもとの式がもっていたタグを新たに貼ります。マクロをすべて展開しおえたあとで、式が持っているタグを中の識別子に付与していきます。こうすることで、タグを付与する探索を1回だけにすることができます。区別のために、一度もマクロ展開されていない最初の式にたいして、top-markという特別なタグをつけておきます。マクロ展開をすべて終えたあとにtop-markをもってなく、同じシンボルで同じタグの組み合わせをもつ識別子をユニークな名前のものにリネームします。
次にKFFDのように展開後にでてきた識別子だけにタグをつける方法について説明します。
毎回の展開前の式に"展開前タグ"をつけておき、その展開が終わったあとで式に"展開後タグ"をつけます。式の中には"展開前タグ"と"展開後タグ"のどちらかあるいは両方が混在するサブ式があるわけですが、次のように場合わけすることができます。
- 展開前タグだけがついている識別子 => マクロ展開で消えた識別子のため考慮しない
- 展開後タグだけがついている識別子 => 今回新しく挿入された識別子(リネーム対象)
- 展開前タグも展開後タグもついている識別子 => 前からある識別子
つまり、展開後タグがついている識別子だけが最後にリネームする対象というわけです。
実装上は、展開前タグと展開後タグの両方が式に付与された場合は打ち消して削除するようなことをします。
lazy KFFDの例
[実装上の注意] タグ付きリスト
Lazy KFFDでは式にタグを付与する必要があるため、式はタグを付けられるようなデータ構造に変更する必要があります。さらにデータ構造だけでなく、リスト操作関数もそれぞれタグ付き用のものにする必要があります。
次のコードに例を示します。
式は単純に、内容とタグのリストの2つの要素をもつ構造体で表すことができます。
リスト操作関数は、car(あるいは cdr)した結果と、自身のタグをもったタグ付き式を返すようにします。
;;タグ付きオブジェクトの表現例
(define-record-type <tagged-obj>
(tagged-obj obj tags)
tagged-obj?
(obj ref-obj)
(tags ref-tags set-tags!))
;;タグ付きリストのcarの例
(define (tags-car tagged-obj)
(let ((car-obj (car (ref-obj tagged-obj))))
(tagged-obj (ref-obj car-obj)
(merge-tags (ref-tags tagged-obj)
(ref-tags car-obj)))))
lazy KFFDで局所的な定義を補足できるようにする
lazy KFFDで局所的な定義を補足できるようにするには、単純には束縛するたびに連想リストなどに記録しておいて識別子が出てくるたびにそれを検索すれば良いです。ただ、巨大な連想リスト1つで持つよりかは、ローカル定義を先述のタグ付きオブジェクトに個別に記録していくほうが検索対象は小さくなり計算量が小さくなります。
このローカル定義を記録した連想リストなどを検索には、同じ環境かつ同じタイミングでマクロ展開された識別子かどうかが判定できる必要があります。これは2つの識別子が同じシンボルかつ付与されたタグがすべて同じであるかを確認すれば判定することができます。
参考文献
- Hygienic macro expansion (LFP'86)
- Beautiful code (2008) O'REILLY 25章 構文の抽象化: syntax-case マクロ
- Syntactic closures (LFP'88)
Discussion