2015-12-02

syntax-rulesで中級以上のマクロを書く手引き

この記事はLisp Advent Calendar 2015 の二日目として書かれました。

R7RS-smallでは低レベル健全マクロが定義されなかったため SchemerはR5RSから続くsyntax-rulesを使ってマクロを書くことを強いられることになった。syntax-rulesはよくできた健全マクロシステムではあるが、書き方を知らなければ複雑なマクロを書くことができない。ここでは中級程度のマクロを書くために必要な手法を紹介することとする。特に要求するレベルというものを設けることはしないが、想定する読者はここ(秘伝のタレマクロができるまで)に書かれているレベルのマクロは書けるがそれ以上のことがしたい方としている。

紹介する手法

どの程度を中級とするかというのは個人個人で違うだろうが、ここでは以下の手法を用いたマクロを中級とすることとする。
  • 識別子比較
  • CPSマクロ
上記二つを解説した後、この二つを組み合わせたマクロでできることを紹介する。

識別子比較

syntax-rulesを用いたマクロに於ける識別子の比較とは、その識別子に束縛されているものの比較と言い換えることができる。これはR7RSの4.3.2 パターン言語にあるマッチングルール第3項に定義されている。
P is a literal identifier and E is an identifier with the same binding;
(訳)Pがリテラル識別子かつEが同一束縛を持つ識別子である
R7RS 4.3.2 Pattern Language
ここでいうリテラル識別子とはsyntax-rulesに渡す第一引数(ユーザーellipsisを使用する場合は第二引数)のことである。これらの識別子はマクロ展開時に同一の束縛を指す識別子と比較した際にマッチしなければならない。ここで注意したいのは、未束縛の識別子同士の比較は単なる名前の比較になるが、束縛が同一である場合は別名でもマッチするという点である。例えばcondにおける補助構文elseを考えてみる。R7RSでは以下のように書いても正しく動くことが要求されている。
(import (rename (scheme base) (else scheme:else)))

(define else #f)

(cond (else 'ng)
      (scheme:else 'ok))
;; -> ok

(cond (scheme:else 'ng)
      (else 'ng))
;; syntax error
R6RSにはfree-identifier=?と呼ばれる識別子同士が同一の束縛を指すかどうかを調べる手続きがあるが、この性質を使うとR7RS-smallでも同様の機能を持つマクロを書くことができる。例えば以下のように:
(import (scheme base))

(define-syntax free-identifier=??
  (syntax-rules ()
    ((_ a b)
     (let-syntax ((foo (syntax-rules (a)
                         ((_ a) #t)
                         ((_ _) #f))))
       (foo b)))))

(free-identifier=?? a a)
;; -> #t

(free-identifier=?? a b)
;; -> #f
R7RS-smallでは識別子を直接扱うこと、ここでは手続き等の引数にするという意味、はできないのでマクロで書いてやる必要がある点に注意されたい。このようにリテラルに比較したい識別子を与え、それにマッチするかどうかをチェックすることで識別子の比較が可能である。ちなみに、fooという名前に特に意味はない。単にこのマクロ内で使われていない識別子を取っているに過ぎない。意味がないことに意味があるともいえるのかも知れないが、哲学的になるので深くは掘り下げないことにする。

ここで識別子の比較は束縛の比較と書いたがそれが端的に現れている例を提示しよう。
(import (scheme base) (rename (only (scheme base) car) (car scheme:car)))

;; definition of free-identifier=??

(free-identifier=?? car scheme:car)
;; -> #t
上記のスクリプトに於いてcarscheme:carも同一の手続きを指すのでfree-identifier=??#tを返す。

注意:このケースではライブラリのインポートがたかだか一回であることが保障されているはずだが、この解釈は多少自信がない部分がある。解釈が揺れていることに関してはこちらの記事を参照されたい:
Defined or undefined?(英語)
R7RSのライブラリに関する疑問


識別子の比較で注意したいのは一時変数として生成された同名のテンプレート変数の比較は常に真になるということだろう。
(import (scheme base))

(define-syntax foo
  (syntax-rules ()
    ((_ a b)
     (let-syntax ((bar (syntax-rules (a)
                         ((_ a) #t)
                         ((_ _) #f))))
       (bar b)))
    ((_ t* ...)
     (foo t t* ...))))
(foo)
;; -> #t
一時識別子を、マクロ展開器がテンプレート変数をリネームするという性質を用いて、生成するというのはしばしば用いられるテクニックなのだが、これで生成された識別子は同一ではないが同一の束縛を持つ(ここでは未束縛)同名の識別子になるため、syntax-rulesのリテラルと必ずマッチする。こういったケースの識別子を比較した場合はR6RSで定義されているbound-identifier=?を使用する以外にはなく、R7RS-smallの範囲では行えないはずである。(少なくとも筆者が知る限りでは。)

CPSマクロ

CPSマクロとはCPS(Continuation Passing Style)で書かれたマクロのことである。この名称が一般的かどうかというのはここでは議論しないこととする。

Schemeに於いてマクロは必ず式の先頭から評価される。手続きでは引数が評価された後に手続き自体が評価されるが、マクロにおいてはこれが逆になる。これは、あるマクロの展開結果を別のマクロで使いたい場合に手続きのように書くことができない、ということを意味する。例えば以下:
(define-syntax foo
  (syntax-rules ()
    ((_ (a b)) 'ok)))

(define-syntax bar
  (syntax-rules ()
    ((_) (a b))))

(foo (bar))
;; -> syntax error
これは多少例が極端すぎるかもしれないが、いくつかのマクロを組み合わせたい場合というのは少なからずある。その際にあるマクロを展開結果を意図して別のマクロの引数に渡すというミスはままある(体験談)。これを解決する唯一の方法がCPSマクロである。

CPSという名が示すとおり、CPSマクロは次に展開されるマクロをマクロの引数として渡してやる。上記の例であれば、foobarが先に展開されることを期待しているので、以下のようにbarfooを渡すように書き換える。
(define-syntax foo
  (syntax-rules ()
    ((_ (a b)) 'ok)))

(define-syntax bar
  (syntax-rules ()
    ((_ k) (k (a b)))))

(bar foo)
;; -> ok
次に展開するマクロが期待する式をあらかじめ知っておく必要があることと、それに合わせて式を展開する必要がある以外は何も難しいことはない。

組み合わせる

これら二つのテクニック、特に識別子の比較、は単体ではあまり意味を持たせて使うことはないが組み合わせるととても強力なマクロを書くことができる。ここでは極単純だがある程度汎用性のある例を紹介しよう。

マクロは、とりあえずベクタのことは忘れるとして、言ってしまえばリスト操作である。リスト操作といえばassq、ということでassqのマクロ版を作ってみる(強引)。

注意:このネタは既に書いてるので、これを読んだ方には退屈かもしれない。新しいネタを考えてると期日に間に合わなさそうだったので焼き増しである。正直スマン

assocなので、取り出した式を使えるようにしたい。そのためにはCPSマクロを使う必要がある。そうすると一番上の定義は以下のようになるだろう。
(define-syntax massq
  (syntax-rules ()
    ((_ k id alist)
     ...)))
kは次に展開されるマクロの識別子である。後はassqと一緒だ。次にidalistの中にあるかを調べる必要がある。idは識別子であることを期待するので、syntax-rulesのリテラルを使って以下のように書ける。
(letrec-syntax ((foo (syntax-rules (id)
                       ((_ ((id . d) rest ...)) (k (id . d))
                       ((_ ((a . d) rest ...))  (foo (rest ...))))))
  (foo alist))
後はこれを組み合わせてやればよい。
(define-syntax massq
  (syntax-rules ()
    ((_ k id (alist ...))
     (letrec-syntax ((foo (syntax-rules (id)
                            ((_ ((id . d) rest (... ...))) (k (id . d))
                            ((_ ((a . d) rest (... ...)))  (foo (rest (... ...)))))))
       (foo alist)))))
実はこのマクロには少なくとも一つ問題がある。多くの場合では問題にならないことの方が多いのだが、このマクロは入力式をそのまま返さない。具体的にはidがリネームされてしまうのである。これを回避するためには、マッチさせる式と出力する式を分ける必要がある。こんな感じでalistを2回渡してやるだけなので難しい話ではない。
(define-syntax massq
  (syntax-rules ()
    ((_ k id alist)
     (letrec-syntax ((foo (syntax-rules (id)
                            ((_ ((id . d1) rest (... ...)) 
                                ((a . d2) rest2 (... ...)))
                             (k (a . d2)))
                            ((_ ((a1 . d1) rest (... ...))
                                ((a2 . d2) rest2 (... ...)))
                             (foo (rest (... ...)) (rest2 (... ...)))))))
       (foo alist alist)))))
kに渡しているのがaというのが肝である。これによって入力式の識別子が展開された式で使用されることを保障している。ここまでやる必要のあるマクロを書く機会は少ないかも知れないが、識別子のリネームによる予期しない動作を回避するための一つの方法として覚えておいても損はないだろう。

まとめ

中級以上のマクロを書くために必要になる手法を紹介した。識別子の比較を用いればsyntax-rulesのリテラルに依存しないマクロキーワードを作ることができ、CPSマクロを用いればマクロの展開結果を受け取るマクロを作ることができる。どちらも複雑なマクロを書く際の強力なツールとなる。

なおこの記事はこれらの手法を使って複雑怪奇なマクロを書くことを推奨するものではないが、言語を拡張するレベルのマクロを書く際には必要になる(かもしれない)ものではある。更なるマクロの深淵を覗きたい方はOleg氏のLow- and high-level macro programming in Schemeがいろいろまとまっているので参照するとよいだろう。

No comments:

Post a Comment