syntax-rulesでfree-identifier=?, bound-identifier=? を書く

この記事は Lisp Advent Calendar 2016 17日目の記事です。

R6RS Scheme には識別子の等価性を判定する bound-identifier=? と free-identifier=? という述語がある。

詳しい説明は R6RS の本文に譲るとして、使い方で言うと、 free-identifier=? は cond の else のような構文キーワードの一致判定に使い、 bound-identifier=? は (lambda (a a) ...) の a のように変数束縛の中に重複があるケースを検出するのに使うのが代表的な使い途だ。

これらの手続きは、 R6RS では syntax-case を使った低レベルマクロを書くために提供されているが、 http://okmij.org/ftp/Scheme/macro-symbol-p.txt の方法を使うと R[567]RS の syntax-rules でこれらの手続きと同様の意味の述語を書ける。

定義は以下の通り。

(define-syntax syn-free-identifier=?
  (syntax-rules ()
    ((_ a b kt kf)
     (let-syntax ((test (syntax-rules (a)
                          ((_ a) kt)
                          ((_ x) kf))))
         (test b)))))

(define-syntax syn-bound-identifier=?
  (syntax-rules ()
    ((_ id b kt kf)
     (let-syntax ((id (syntax-rules ()
                        ((_) kf)))
                  (ok (syntax-rules ()
                        ((_) kt))))
         (let-syntax ((test (syntax-rules ()
                              ((_ b) (id)))))
             (test ok))))))

手続き版と区別するために、 syn- という接頭辞を付けている。また、 Scheme のマクロは最外簡約であるため、手続きのように値を返すことができないので、識別子 a, b が等しいときとそうでないときの継続 kt と kf を渡し、判定結果によりいずれに展開されるかを選択するようにしている（これは syntax-rules で合成可能なマクロを書くときの常套手段だ）。

syn-free-identifier=? の方は、 syntax-rules のリテラルが、ちょうど free-identifier=? の意味で一致判定をすることを利用している（syntax-rules を使った cond マクロの定義を思い出すとよい）。

syn-bound-identifier=? の方はもう少し込み入っているが、 bound-identifier=? の定義である「マクロ展開結果で一方が束縛変数になるとき、もう一方はその変数のスコープ内に現れた場合その束縛を参照する¹ならば #t を返す」というのをそのまま書き下したようになっている。

(syn-bound-identifier=? a a #t #f) で、ふたつの a が字面としては等しく、識別子として異なる場合、これを a#0 と a#1 のようにして表記することにすると、 (syn-bound-identifier=? a#0 a#1 #t #f) 展開結果は下のようになる。

(let-syntax ((a#0 (syntax-rules ()
                    ((_) kf)))
             (ok (syntax-rules ()
                   ((_) kt))))
    (let-syntax ((test (syntax-rules ()
                         ((_ a#1) (a#0)))))
        (test ok)))

a#0 と a#1 は異なる識別子なので、 test のパターン部の a#1 はテンプレート内の a#0 を捕捉しない。

この結果、 (test ok) は (a#0) に展開され、結果は kf になる。

ふたつの識別子が bound-identifier=? である場合は、ふたつを a#0 と書くと、展開結果は次のようになる

(let-syntax ((a#0 (syntax-rules ()
                    ((_) kf)))
             (ok (syntax-rules ()
                   ((_) kt))))
    (let-syntax ((test (syntax-rules ()
                         ((_ a#0) (a#0)))))
        (test ok)))

syn-bound-identifier=? の第一、第二引数が bound-identifier=? である場合、 test のパターン変数とテンプレートが同一の変数を参照し、 (test ok) の展開結果は (ok) になり、最終的に kt になる。

というような感じで、 R6RS の低レベルマクロの一部として紹介されているものでも、 syntax-rules で記述できるものがある。 syntax-rules には想像以上の表現力がある。

1. 識別子 a, b があるとき、例えば、 (lambda (a) ... b ...) に a は束縛変数として現れる。このスコープ内の b が a の束縛を参照するなら ↩