syntax-rulesの中間表現を考え直す会
実装まで落とし込むまで行けなかったのでもうちょっと真面目に考える。
パタン / テンプレート要素表現 の改善
とりあえず、
- パタン要素が空リストで終端されるケースを特別扱いする
- テンプレート要素は複数のellipsisを内包できるようにしてsplice要素を廃止
"パタン要素が空リストで終端されるケース"は頻出なので最適化する。空リストで終端されないケースをMNLISTとして分割、MLISTは常に空リストで終端されるケースにだけ使う。
;; MNLIST (a b ... c d) ;; MLIST (a b ...)
これは、MLISTケースではb ...にマッチした部分を元ソースから切り出す必要が無い(テンプレートのリスト中にb ...が表われたら単に接続すれば良い)ため。(ただし2回以上表われた場合は結局コピーが必要になる)
- パタン要素クラス (改)
pattern: 1 : (p0 . p1) => PAIR[ p0 p1 ] 2 : (p0 p1 p2) => LIST[ p0 p1 p2 ] 3 : (p0 p1 p2 . p) => DLIST[ p0 p1 p2 p ] 4 : (p0 p1 p2 ...) => MLIST[ p0 p1 p2 ] 5 : (p0 p1 ... p2 p3) => MNLIST[ p0 : p1 : p2 p3 ] 6 : (p0 p1 ... p2 p3 . p) => MDLIST[ p0 : p1 : p2 p3 p ] 7 : #(p0 p1 p2) => VEC[ p0 p1 p2 ] 8 : #(p0 p1 ... p2 p3) => MVEC[ p0 : p1 : p2 p3 ]
- テンプレート要素クラス (改)
template: 1 : (a0 . a1) => PAIR[ a0 a1 ] 2 : (a0 a1) => LIST[ a0 a1 ] 3 : (a0 a1 . a2) => DLIST[ a0 a1 a2 ] 4 : (a0 ... a1) => MLIST[ SPPOS : a0 a1 ] 5 : (a0 a1 ... . a2) => MDLIST[ SPPOS : a0 a1 a2 ] 6 : #(a0 a1) => VEC[ a0 a1 ] ;; Fixed length 7 : #(a0 a1 ... a2 a3) => MVEC[ SPPOS : a0 a1 a2 a3 ] ;; Variable length
SPPOSのエンコードは{ellipsisの数, {インデックス}*}。図中では黄色で表記する。
(※ 図がDLISTになっているがMDLISTの間違い)
VEC(固定長)とMVEC(可変長)は別々のクラスにしている。VECの場合はテンプレートが生成するvectorの長さは静的に決定できる。(listのlength取得はO(N)になるので可能な限り避ける)
キャプチャと展開
syntax-rulesマクロの展開処理は
- パタンにマッチするかどうかの検査
- テンプレートの出力
の2フェーズに分けることができる。 ...Scheme処理系によってはこの2つを同時に行うものも有るかもしれないが、余計なconsを避けるという意味では可能な限りギリギリまで実際の出力は行わない方が良いんじゃないかと思う。
ここでは、パタン変数の内容を"Capture"、テンプレートからの出力を"Output"と呼ぶことにする。
Captureを構築するには、Pattern-IRに従って入力をスキャンすることになる。このときCaptureに含めなくても良いパタン要素が存在する(_ とか リテラル類)ため、Pattern-IRとCapture中の内容のレイアウトは一致しない。このため、事前にCapture中のデータレイアウトを表現するlocとidxを生成しておく必要がある。
図の例では、パタン変数 code はloc = (-13 -14)、idx = (0 1)がアサインされている。idxを用いて、出力されたcaptureの0番目→1番目と見れば実際のcodeの内容にアクセスできることがわかる。
locが必要なのは、Captureの内容がどのPattern-IRから生成されたのかを知る必要があるため。CaptureにはInputの参照のみを含め、Outputの際にはPattern-IRの記述を元に"切り出し"を行うことにより余計なコピーを減らすことができる。切り出しを行うためには、Pattern-IRが参照している要素の素性を知る必要がある。(例えば、このとき、↑のMNLISTとMLISTの分割が生きる - MLISTなら単にリスト終端まで走査すれば良いが、MNLISTの場合は末尾の要素をいくつか除く必要がある)
実際のOutputは、Template-IRを順に処理していけば得ることができる。... といっても、このアルゴリズムもあまり自明でない(現在考え中)。
