Schemeで展開順序の問題を回避してマクロを組み合わせる方法(CKマクロ)
Scheme標準のマクロ(Syntax-rules)は、単純な変換を楽に書けます。
ただ、複雑なマクロは書きにくく、可読性も悪くなりがちです。
これは、展開が外側から行われるため、マクロを単純には組み合わせることができないことと
パターンマッチを用いた変換であることから複雑なことが記述できないことが理由です。マクロの記述も通常のプログラミングのように小さな部品として切り出し、それを組み合わせて大きなマクロを作ることができるようになることが理想です。
今回紹介するCKマクロは、マクロを用いて内側から展開されるように制御することで、マクロを組み合わせやすくする方法です。それから、同様にマクロをうまく組み合わせる目的で使われるCPSマクロも簡単に紹介します。CPSマクロは、syntax-rulesの自動的なリネームと相性が悪かったり、可読性が良くなかったりしますが、CKマクロではこのような問題はありません。
syntax-rulesを使ったマクロを組み合わせることの問題点
マクロは外側から展開されるため、単純に埋め込むと意図しない展開結果になる場合があることを説明します。
reverse-lambdaという例
例として、reverse-lambda
というマクロを考えます。
reverse-lambda
は、lambdaとよく似た記述をしますが、引数と本体が逆の順序になります。
つまり、次のような挙動をします。(実用的なマクロではないですが..)
(reverse-lambda (a b) (display (list a b)) (newline) 'result)
;=> (lambda (b a) 'result (newline) (display (list a b)))
reverse-lambdaの部品macro-reverse
このreverse-lambda
での2箇所の反転操作のために、要素を反転させるマクロmacro-reverse
を作ります。macro-reverse
はこのようになります。これを利用してreverse-lambda
を作れることを期待します。
(define-syntax macro-reverse
(syntax-rules ()
((_ (x ...)) (macro-reverse "progress" (x ...) ()))
((_ "progress" () (res ...)) (res ...))
((_ "progress" (x rest ...) (res ...))
(macro-reverse "progress" (rest ...) (x res ...)))))
;(macro-reverse (2 1 cons)) => (cons 1 2) => (1 . 2)
reverse-lambdaの記述
そして、reverse-lambda
をmacro-reverse
を使ってこのように記述してみます。
(define-syntax reverse-lambda
(syntax-rules ()
((_ (args ...) bodies ...)
(lambda (macro-reverse (args ...)) . (macro-reverse (bodies ...))))))
reverse-lambda、失敗
(reverse-lambda (a b) (display (list a b)) (newline) 'result)
を1回展開すると、このようになります。
(lambda (macro-reverse (a b))
macro-reverse
(display (list a b))
approve/approve/(newline)
'result)
この結果は期待したものと異なっています。
そして、この式はこれ以上展開することができません。lambdaの引数部は展開の対象外ですし、body部のmacro-reverse
は、マクロ展開の形式ではなくなっているためです。実行すると、lambda式の引数が不正であるなどのエラーが生じるという結果になるでしょう。
うまく展開できるようにするには、macro-reverse
を何らかの手段で、先に展開するようにすることが必要です。CPSマクロやCKマクロが主な解決方法です。
CPSマクロ
展開順序を考慮してマクロを組み合わせる方法である、CPSマクロを(簡単に)紹介します。
CPSマクロは、先に展開したい式を外側に置き、後で展開したい式を追加で渡すというものです。
この説明では、後で展開したい式を継続マクロ
と呼ぶことにします。
CPSとは、Continuation-passing styleの略です。CPSでは、関数(手続き)は、陽に記述した継続を追加で受け取り、もともと返すはずの値を受け取った継続に渡す記述スタイルです。CPSマクロでは、継続マクロ
を追加で受け取り、展開結果を継続マクロ
に渡します。
継続マクロ
継続マクロ
は、別のマクロの展開結果を受けとり、次に展開したい式に埋め込みます。
この説明では、(syntax-lambda (<結果>) <次に展開したい式>)
という記法を使います。
そして、継続マクロ
に結果を適用するためにもマクロが必要で、今回はapply-continuation-macro
という名前で次のように定義します。
(define-syntax apply-continuation-macro
(syntax-rules (syntax-lambda)
((_ (syntax-lambda (cont-args) cont-body) args ...)
(let-syntax ((cont-syntax
(syntax-rules ()
((_ cont-args) cont-body))))
(cont-syntax args ...)))))
このapply-continuation-macro
は、<継続マクロ>
と渡したい値を受け取ります。
そして、継続マクロ
の<次に展開したい式>
内の<結果>
を渡したい値で置き換えることをします。
簡単な例を示します。
(apply-continuation-macro
(syntax-lambda (x) (lambda x 'x))
(a b))
; => (lambda (a b) '(a b))
apply-continuation-macro
に、継続マクロ(syntax-lambda (x) (lambda x 'x))
と渡したい値(a b)
を与えます。(lambda x
x)の
xを
(a b)で置き換えた結果、
(lambda (a b) (a b))
となります。
macro-reverseの書き換え
CPSマクロでは、式を返す代わりに継続マクロ
に渡す必要があります。macro-reverse-cps
の結果を返す部分である(res ...)
を(apply-continuation-macro cont-macro (res ...))
のように、継続マクロに渡すように置き換えます。それから、macro-reverse-cps
は継続マクロ
を受け取る必要があるので、受け取る口を追加します。
(define-syntax macro-reverse-cps
(syntax-rules ()
((_ cont-macro (x ...))
(macro-reverse-cps cont-macro "progress" (x ...) ()))
((_ cont-macro "progress" () (res ...))
(apply-continuation-macro cont-macro (res ...)))
((_ cont-macro "progress" (x rest ...) (res ...))
(macro-reverse-cps cont-macro "progress" (rest ...) (x res ...)))))
reverse-lambdaの書き換え
reverse-lambda
をmacro-reverse-cps
を使って書き換えます。
reverse-lambda
は、(reverse-lambda <引数> <本体>...)
という表記です。
まず、
(1) <引数>をmacro-revere-cps
で反転する
(2)、次に<本体>をmacro-revere-cps
で反転する
(3)、lambda式に(1)と(2)を埋め込みます。
(define-syntax reverse-lambda
(syntax-rules ()
((_ (args ...) bodies ...)
(macro-reverse-cps;(1)引数の反転
(syntax-lambda (reverse-result1)
(macro-reverse-cps;(2)本体の反転
(syntax-lambda (reverse-result2)
;(3)lambda式に結果を埋め込む
(lambda reverse-result1 . reverse-result2))
(bodies ...)))
(args ...)))))
変換は機械的に行えばよいですが(すべてのマクロ適用を変換するのは大変ですが)、通常のLispでの式と内側と外側が反転しているため、読むのは慣れないと難しいです。
CPSマクロでのreverse-lambdaの結果
展開はうまくいきます。
(reverse-lambda (a b) (display (list a b)) (newline) 'result)
;=> (lambda (b a) 'result (newline) (dislay (list a b)))
しかし、実際にreverse-lambdaで作った手続きに値を渡すと失敗します。(結果は処理系による。これは、Gauche 0.9.10の結果)
((reverse-lambda (a b) (display (list a b)) (newline) 'result) 1 2)
;ERROR: unbound variable :a
これは、apply-continuation-macro
内でsyntax-rulesに適用しているのが問題で、syntax-rulesの名前の衝突を避ける機構(hygenic-macro)によって、もともと同じものを参照している名前も別のものに置き換えられることがあります。CPSマクロでlambda式の引数を処理するようなことは避けたほうが良いです。
CKマクロ
CKマクロは、展開順序を考慮してマクロを組み合わせる方法です。
また、CPSマクロのように参照が衛生的マクロによって壊れたり、記述順序を逆転させなくてもよいです。衛生的マクロの問題が起こらないのは、結果の挿入に内部的なsyntax-rulesを使わないためです。CKマクロは、Oleg先生によって普及しました。
各マクロは、継続の代わりにどこまでマクロを展開したかを管理するスタックを受け取り、apply-continuation-macro
の代わりにCKマシンに値を渡します。[1]
CKマシンはスタックを使って深さ優先探索のように、内側の未展開の式を見つけて展開していきます。CKマシンが入力した式を展開しても良い部分か判定するためのマーカーとして、展開しない部分にquoteを使います。また、展開した部分を再展開しないように、展開済み結果にもquoteを適用します。
CKマクロ版reverse-lambda
CKマクロ版のreverse-lambdaを作る部品として、macro-reverse
のCKマクロ版の他に、cons*(最後の引数が末尾のセルのcdr部になるような(非)リストを作る手続き)のようなmacro-cons*-ck
を使います。展開したい式を空のスタック(空リストで表現される)と共にCKマシンに渡します。シンボルlambdaは展開する式ではないため、CK機械がそうであると解釈させるために、quoteを適用し'lambda
とします。
(ck ())
内の記述は、普通のSchemeのコードと大差ないことが分かります。
(define-syntax reverse-lambda
(syntax-rules ()
((_ (args ...) bodies ...)
(ck () (macro-cons*-ck 'lambda
(macro-reverse-ck '(args ...))
(macro-reverse-ck '(bodies ...)))))))
CKマシン
CKマシンはスタックを使って内側の未展開の式を展開していきます。
スタックには、外側の式の展開済みの式のリストと未展開の式のリストの組が入っています。CKマシンには、スタックと展開したい式を渡します。CKマシンはこのような挙動をします。CKマシンは、<展開済み>と<未展開>の2つの式のリストを持ちます。
<展開済み>を展開
が完了すると、CK機械を再度呼び出し外側の式の展開を再開します。
ck機械はマクロで記述します。このコードはoleg先生のCKマクロのページにかかれているものです。http://okmij.org/ftp/Scheme/macros.html#ck-macros
(define-syntax ck
(syntax-rules (quote)
((ck () 'v) v) ; yield the value on empty stack
((ck (((op ...) ea ...) . s) 'v) ; re-focus on the other argument, ea
(ck s "arg" (op ... 'v) ea ...))
((ck s "arg" (op va ...)) ; all arguments are evaluated,
(op s va ...)) ; do the redexthe
((ck s "arg" (op ...) 'v ea1 ...) ; optimization when the first ea
(ck s "arg" (op ... 'v) ea1 ...)) ; was already a value
((ck s "arg" (op ...) ea ea1 ...) ; focus on ea, to evaluate it
(ck (((op ...) ea1 ...) . s) ea))
((ck s (op ea ...)) ; Focus: handle an application;
(ck s "arg" (op) ea ...)) ; check if args are values
))
macro-reverse-ckやmacro-cons*-ckの記述
CKマクロ内ですべてのマクロは、スタックを追加で受け取り、展開結果とスタックをCK機械に渡します。この展開結果は展開済みなので再展開しないようにquoteを適用します。
macro-reverse
のCKマクロ版はこのように記述できます。ほとんど、macro-reverse-cps
と同じです。reverseを適用する対象は展開済みなのでquoteで囲われていることと、渡す結果をquoteで囲うことが違う点です。
(define-syntax macro-reverse-ck
(syntax-rules (quote)
((_ s '(x ...)) (macro-reverse-ck s "progress" (x ...) ()))
((_ s "progress" () (res ...)) (ck s '(res ...)))
((_ s "progress" (x rest ...) (res ...))
(macro-reverse-ck s "progress" (rest ...) (x res ...)))))
macro-cons*-ck
は次のように記述できます。
(define-syntax macro-cons*-ck
(syntax-rules (quote)
((_ s 'args ...)
(macro-cons*-ck s "progress" (args ...) ()))
((_ s "progress" (arg) (res ...))
(ck s '(res ... . arg)))
((_ s "progress" (arg1 args2 ...) (res ...))
(macro-cons*-ck s "progress" (args2 ...) (res ... arg1)))))
CKマクロのライブラリ
SRFI 148: Eager syntax-rulesでは、CK機械といくつかのリスト操作のマクロ版が提供されています。
まとめ
- CKマクロは評価順序の問題を回避してマクロを組み合わせる方法
- CPSマクロのように記述順序の問題や衛生的マクロによる参照先の破壊が起こらない
ソースコード
- CKマクロの例で使ったコードのリンク
https://gist.github.com/niyarin/4db3fdff3c4cc02e65978a1a33f23c00
-
このスタックと継続マクロは表現は違うが、指しているものは同じな気がします ↩︎
Discussion
教えてください。
フローチャートのいくつかの箇所で、文字が消えているように見えます。
・先頭の「が空」の、がの前は何でしょうか?
・左に行った3個目の「をpop」のをの前は何でしょうか?
・右下の箱の上の箱で、「に『展開済み』と先頭を取り出した」のにの前は何でしょうか?
お手数ですが、お教えいただけると幸いです。
よろしくお願いいたします。
報告ありがとうございます!
消えた文字は見えるようにしました。
zennのMermaid (markdownでグラフを書けるツール)のバージョンが変わったのかレンダリングがうまくいっていませんでした。
早速のご対応、誠にありがとうございました。勉強させていただきます。