Gauche:MultiPhaseMacro
Shiro(2009/02/24 13:51:19 PST):
現在のSchemeマクロのセマンティクスは、 メタプログラミングとして可能な領域の一部しかカバーしてないんじゃないかと もやもや思っているのでアイディアをメモしておく。
Schemeマクロの限界
マクロはトップダウン、あるいは「外から内へ」、あるいはpreorderで 展開が進むことになっている。
(foo (bar x) (baz x))
この式でfooがマクロであった場合、内側のサブフォーム(bar x), (baz x)は手つかずのままfooの 展開ルーチンに渡される。fooの展開ルーチンは(bar x)や(baz x)をそのまま 出力フォームに埋め込むかもしれないし、bar, baz xなどに分解して処理するかもしれない。 (bar x), (baz x)がそのまま出力フォームに埋め込まれた場合、それはfooの展開後に 処理されることになる。
preorderは、サブフォームの構造を変えるマクロ(例:let)を書くのに必要だ。 しかし、preorderはサブフォームを、ソースに与えられた「生の」形でしか見ることができない。 これには次のような欠点がある。
- サブフォームをトラバースして定数畳み込みみたいな最適化をマクロで書きたいと 思っても、マクロはリテラルで書かれた定数しか扱えない。コンパイラは後で 不変な束縛を定数に置き換えることが出来るのに、それをマクロで最適化する チャンスがない。(これは、コンパイラマクロで最適化かけたいという時も 障害になる)。
- R6RSでidentifier macroが導入されたことにより、マクロがサブフォーム だけを見てそれが単なる変数参照か適用形式かを見分けることが出来なくなった。 これは、マクロの能力が専らソース上に明示されている構造を触ることのみに 制限されるということだ。common subexpression eliminationをやりたい、 といった意味を触ろうとすると壁に当たることになる(全く出来ないわけじゃないが、 完全には出来ない)
- 究極のメタプログラミングツールとしてマクロを考えるなら、引数のメタ情報、 例えば推論された型とか束縛の変更可能性なども展開ルーチンの中で参照したい。 しかしそのようなメタ情報は、一度ツリーを全部トラバースしないと判明しない。
pre-post orderの可能性
preorderで起動される展開ルーチンと、postorderで展開されるルーチンを くっつけておいたら、これらの欠点はカバーできるだろうか。
- ソースの構文上の意味を変える展開はpreorderでのみ許される。 この時に、identifier macroや定数置換も行われる。
- 末端まで展開したら、コンパイラはメタ情報を付与する。
- postorderではメタ情報を参照した最適化などを行う。意味は変えられない。
あーでもメタ情報は一旦木全体を見ないとつけられないのか。 サブツリーを見終わった時点でもまだ訪れてないsibilngがあると メタ情報は確定しないなあ。
結局マルチパス?
そうなると複数パスが必要になるかな。pass1を2つに分ける:
- pass1.1: 構文的マクロ展開パス。S式を入力とし、出力はannotated S-expr、つまり hygieneを確保するためのsyntactic bindingな情報とか、推論された型などの メタ情報が付与された形。
- pass1.2 意味的マクロ展開パス。展開ルーチン内でメタ情報を参照できる。 意味を変える展開 (既に付与されたメタ情報と矛盾するような変更) はできない。 メタ情報を特殊化するのは可能 (collectionを返すはずの式を、listを返す式に 特殊化するとか)。
うーん、pass1.2と現在のpass2がやってるのは概念的には同じことかなあ。 しかし、現在のpass2は入力時点で既にソースがコンパイラの内部形式(IForm)に 変換されちゃってるから、マクロのような形で簡単にフックをかけるのは難しい。
pass1.2はpreorderであるべきか、postorderであるべきか。preorderなら 1.2のpostorderでIFormへと変換できる。でも何となく意味的マクロ展開は postorderの方がいろいろできそうな気がする。だがそうなると1.2の出力を さらにIFormへと変換する必要がある。
いっそのことIFormをannotated S-exprの形にしちゃったら、 1.2と2を融合してpass3まで持ってける? むむむ。
資料
Typed Schemeの実装ではlocal-expandでマクロ展開ルーチンがサブフォームの 展開を部分的にキックしているようだ: http://www.ccs.neu.edu/scheme/pubs/scheme2007-ctf.pdf