Let's start Scheme

2015-01-08

識別子を識別するために

SRFI-72を確認した結果
  • 識別子の比較は、名前とその識別子の色で行われる
  • 識別子が含む色はリストである(colors)
  • 色はマクロが呼ばれる度に生成される
  • 色は一意のシンボル(eq?でのみ比較される何か)である
  • ソースの式に含まれるシンボルは全て識別子に変換される
    • その際の色は空(nil)
  • 識別子が含む環境は、リネームされるたびに追加されている
  • 束縛は識別子の名前と色をキーとして作られる
  • 全ての束縛には一意の名前が付けられる
    • ライブラリからエクスポートされる際にはそれに対して別名がつく
上記はまぁ前から分かっていたことなので単なる覚書でしかない。本当に知りたいことはリネームのタイミングと識別子の識別方法だったりする。ポータブルなR6RSマクロ展開器であるPsyntaxやこのSRFI-72はどちらもライブラリ機構も提供していて、少なくともSRFI-72はマクロ展開器自体がその機構と密接に関連している。なので一部だけを取り除いて使うということはなかなか難しい。例えば、テンプレート変数が展開されるたびに一意のシンボルになるというのとか。(色付け機能だけを取り除いて実装してみた結果分かったこと。手を動かさないと理解できない程度には頭が悪いので・・・)

とりあえずそれは忘れて現状のリネームの粒度を見直してさらに変数参照の見直しをした結果もう一つわかったこと。おそらく見直し後のリネームの粒度は正しい(syntax-caseのコンパイル時とsyntaxテンプレートの展開時の2回。以前は合計で3~4回やってたorz)。識別子の比較には別の要因がいる。現状識別子が持っている環境を比較をeq?で比較しているのだが、これではまずい場合がでてきている。マクロ展開器を起動した際に環境フレームのみをコピーして一意にしているのだが、これだと同一であるはずのもが非同一になる。これは困る。ここでSRFI-72で行われている色づけが使えそうな気がしないでもない。上記に書いたように、これだけに絞るとまずいので、現状の仕組みの上につける必要がある。(アホみたいな識別子のスロットを排除したいところなのだが、無理っぽいな。)

問題は、どのタイミングで色を変えるかということ。一つはマクロ展開器を起動したタイミングなのだが、そこだけでいいのかが不安。なんとなくもう一息な感じのところまでは来ている気がするので、MPが残っているうちに片付けてしまいたいところではある。走り書き過ぎて自分でも何言ってるのか分からなくなった。

2 comments:

Shiro Kawai said...

一番の基本は、「一回のマクロ展開呼び出しにおいて、その展開で新たに挿入された識別子と、元フォームにあった識別子を区別すればよい」というだけのはずです。一番素直なのは、マクロ展開器の呼び出しごとに、その入力のS式内の全識別子にマークをつけちゃう。展開器が帰ってきたらまたS式を調べれば、マークのついてないやつは新しく挿入されたとわかるのでリネームする。(ただし、挿入された識別子が自由変数の場合はマクロ定義環境のトップレベルを参照することになるので処理系依存の工夫が必要)。

で、それを下層として作ってその上にパターンマッチを入れれば、パターン変数をどうするかとかテンプレートをどうするかという話は自然に解決されるはず、なんですが、この素直な方法だとマクロ展開毎に全フォームを2回づつwalkするのでとても重い。そいつを何とかしようといろいろやりはじめるとごちゃごちゃしちゃう、っていうことだと思います。

パターン変数を考慮したマークづけについては、Dybvig, Hieb & Bruggeman: Syntactic Abstraction in Scheme ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/iucstr355.ps.gz に詳しく載っていますが、私自身実装したことはないので実装のしやすさについては何ともわからんです。


kei said...

とりあえず素直に展開コストをO(n^2)にすることにして、基本的な考え方で片付けることにしました。複雑怪奇なコードをばっさり捨てることができたのでとりあえずは満足してます。

http://www.cs.indiana.edu/~dyb/pubs/bc-syntax-case.pdf で言われてるKFFDってこの論文にあったんですか。今度眺めてみよう。

Post a Comment