健全なマクロ展開 - 構文オブジェクト (その 1)

最初の健全なマクロ展開手法 KFFD (1986) では、変換世代ごとに挿入されるシンボルを自動認識して、 それらを別物として区別します。 あらかじめ変数に変換世代番号がつけてあり、 変換するごとに世代番号なしの変数を探して、 新しい変数を認識していました。

展開前:
((lambda (t:0) (or #f t:0)) 2)

変換世代 1 の変換直後:
((lambda (t:0) ((lambda (t) (if t t t:0)) #f)) 2)

変換世代 1 の番号付け:
((lambda (t:0) ((lambda (t:1) (if t:1 t:1 t:0)) #f)) 2)

α変換: t:0 => t.0、t:1 => t.1
((lambda (t.0) ((lambda (t.1) (if t.1 t.1 t.0)) #f)) 2)

一方、 Bawden-Rees (1988) と Clinger-Rees (1991) および Hanson-Bawden (1991) は異なるアプローチを採用し、 変換子に一手間かけてもらい、 世代ごとにシンボルを区別できるように変換してもらっていました。 自動認識はしていませんでした。 これらに続いて健全なマクロ展開の萌芽期の最後を飾った B. Hieb、 K. Dybvig、 C. Bruggerman、 Syntactic Abstraction in Scheme (1992) は、 KFFD の変数自動認識をとりいれつつ、 O(n) の処理時間・局所マクロの利用を両立できることを示しました。 Hieb-Bybvig は、 ポータブル syntax-case (1992) に使われているものの、 構文オブジェクト・構文環境・局所マクロの表現が独自なので、 ここでは深追いしません。 その代わり、 Hieb-Bybvig のエッセンスを Hanson-Bawden の別名にとりいれることにします。

Hieb-Bybvig のエッセンスとは、 リストに世代番号をつけておくことで、 その中に含まれている世代番号なしのシンボルへの番号付けの代用とすることです。 これで、 マクロ変換後にいちいちシンボルに世代番号をつけなくても良くなります。 もちろん構文環境を使って、 マクロ変換とα変換を同時に進めます。 例として、 上の KFFD の例の展開をこの流儀で書き直してみます。

展開前:
【((lambda (t) (or #f t)) 2):0 E0】

λ構文の展開後:
((lambda (t.1)【(or #f t):0 E1】) 2)
E1 (((t:0 subst t.1)) . E0)

or 構文の展開後:
((lambda (t.1)【((lambda (t) (if t t t:0)) #f):1 E1】) 2)

if 構文の展開後:
((lambda (t.1) ((lambda (t.2) (if【t:1 E2】【t:1 E2】【t:0 E2】)) #f)) 2)
E2 (((t:1 subst t.2)) ((t:0 subst t.1)) . E0)

Hanson-Bawden にこれを応用するには、 変換世代を表す方法を考えないといけません。 そこには Clinger-Rees にならって変換ごとにフレームを拡張した定義時構文環境を使えば良いでしょう。 これで変換世代の区別がつきますし、 識別子の意味を定義時構文環境から得ることができます。 フレームは空で良いでしょう。 つまり、 定義時構文環境を空フレームで拡張したものと展開対象式を閉じ込めることにします。

さて、 この閉じ込めたもののスロット構成は構文クロージャと同じですけど、 展開器での扱い方が異なるので別のクラスとします。 名称は Hieb-Bybvig から借りて構文オブジェクトと呼ぶことにしましょう。 構文クロージャを展開すると展開時構文環境が構文クロージャのものへと、 同時に展開対象式が構文クロージャのものへと変化しました。 一方、 構文オブジェクトを展開しても展開時構文環境は変わりません。 展開対象式は構文オブジェクトのものになるのですが、 それが構文オブジェクトでないときはくっついていた構文環境を受け継ぐ構文オブジェクトに変更します。

いつもの式を手動展開します。 式の後にコロンと環境をつけて構文オブジェクトを表すことにしましょう。 展開前世代を表すのに、 念のため、 E0 を空フレームで拡張した構文環境 M1 をつけることにします。

【((lambda (x) (let ((if list) (temp x)) (or 1 temp))) 2):M1 E0】
M1 (() . E0)
E0 (((let macro E0 let-proc) (or macro E0 or-proc) (if special E0) (lambda special E0)))

2 は定数なので、 そのままとします。 摘要の関数の最初の識別子は lambda:M1 です。 lambda:M1 自身が展開時環境 E0 に含まれていないので、 lambda の意味を M1 下から探すと、 λ構文のキーワードであることがわかります。 λ構文を展開して、 識別子 x:M1 からシンボル x.1 への置換規則で拡張した構文環境 E2 を展開時構文環境とします。

(【(lambda:M1 (x:M1) (let ((if list) (temp x)) (or 1 temp)):M1) E0】2)
M1 (() . E0)

((lambda (x.1)【(let ((if list) (temp x)) (or 1 temp)):M1 E2】) 2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

続いて、 別名 let:M1 自体の意味を展開時構文環境 E2 下で探しますが、 これも見つからず、 let を M1 下で探して、 let マクロのキーワードの意味であることがわかります。 let の変換結果に、 let マクロの定義時構文環境 E0 を空フレームで拡張した M3 をくっつけます。

((lambda (x.1)【(let:M1 ((if:M1 list:M1) (temp:M1 x:M1)) (or 1 temp):M1) E2】) 2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

((lambda (x.1)【((lambda (if:M1 temp:M1) (or 1 temp):M1) list:M1 x:M1):M3 E2】) 2)
M3 (() . E0)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

識別子 list:M1 は展開時構文環境 E2 下になく、 シンボル list も M1 下にないので、 シンボル list 自体へ展開します。 識別子 x:M1 は E2 下にシンボル x.1 への置換規則があるので x.1 へ展開します。 関数は、 またもやλ構文の展開で、 今度は、 別名 if:M1 と temp:M1 の置換規則で展開時構文環境 E2 を拡張した E4 を新しい展開時構文環境にします。

((lambda (x.1) ((lambda (if.2 temp.2) 【(or 1 temp):M1 E4】) list x.1)) 2)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

別名 or:M1 を展開時構文環境 E4 下、 シンボル or を 下で探し、 意味がマクロ or のキーワードであることがわかります。 or 変換手続きの変換結果の展開対象式に or マクロの定義時構文環境 E0 を空フレームで拡張した M5 をくっつけます。 さらに、 let マクロを変換して、 let マクロの定義構文環境を空フレームで拡張した M6 をくっつけます。

((lambda (x.1) ((lambda (if.2 temp.2) 【(or:M1 1 temp:M1) E4】) list x.1)) 2)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

((lambda (x.1)
  ((lambda (if.2 temp.2)
   【(let ((temp 1)) (if temp temp temp:M1)):M5 E4】) list x.1)) 2)
M5 (() . E0)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

((lambda (x.1)
  ((lambda (if.2 temp.2)
   【((lambda (temp:M5) (if temp temp temp:E1):M5) 1):M6 E4】) list x.1)) 2)
M6 (() . E0)
M5 (() . E0)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

λ構文を展開して、 別名 temp:M5 の置換規則で展開時構文環境 E4 を拡張した E7 を新しい展開時構文環境にします。

((lambda (x.1)
  ((lambda (if.2 temp.2)
    ((lambda (temp.3) 【(if temp temp temp:M1):M5 E7】) 1)) list x.1)) 2)
E7 (((temp:M5 subst temp.3)) . E4)
M5 (() . E0)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

if 構文を展開します。 そのとき、 temp:M1 は既に構文オブジェクトなので、 そのまま残します。 そして、 識別子 temp:M5 を展開時構文環境 E7 下で探すと、 シンボル temp.3 への変換規則が見つかります。 また、 識別子 temp:M1 もシンボル temp.2 への置換規則が見つかります。 両方を展開して、 すべての展開が終わります。

((lambda (x.1)
  ((lambda (if.2 temp.2)
    ((lambda (temp.3) (if【temp:M5 E7】【temp:M5 E7】【temp:M1 E7】)) 1)) list x.1)) 2)
E7 (((temp:M5 subst temp.3)) . E4)
M5 (() . E0)
E4 (((if.M1 subst if.2) (temp:M1 subst temp.2)) . E2)
E2 (((x:M1 subst x.1)) . E0)
M1 (() . E0)

((lambda (x.1)
  ((lambda (if.2 temp.2)
    ((lambda (temp.3) (if temp.3 temp.3 temp.2)) 1)) list x.1)) 2)

以上のように、 Hanson-Bawden の別名を Hieb-Bybvig にならってリストへ環境をつけられるように使い方を変更し、 展開前と変換後に変換世代として新しい構文環境をくっつけていきます。 これで、 KFFD のようにマクロが変換ごとに挿入していくシンボルを自動認識できるようになりました。