Zenn
🚛

Schemeで展開順序の問題を回避してマクロを組み合わせる方法(CKマクロ)

2021/08/28に公開
#
macro
scheme
#
lisp
tech

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マクロのように記述順序の問題や衛生的マクロによる参照先の破壊が起こらない

ソースコード

脚注

  1. このスタックと継続マクロは表現は違うが、指しているものは同じな気がします ↩︎

Discussion