“JRM’s Syntax-rules Primer for the Merely Eccentric” メモ(その2)

SYNTAX-RULES Primer for the Merely Eccentric — https://sites.google.com/site/evalapply/eccentric.txt?attredirects=0

続き、Ellipses から。メモっていきます。

*** Ellipses must be last in a list or vector pattern. The list or vector must have at least one initial pattern.

*** Ellipses is a postfix operator that operates on the pattern before it.

*** Ellipses allows the containing list or vector pattern to match provided that the head elements of the pattern match the head elements of the list or vector up to (but not including) the pattern before the ellipses, and zero or more copies of that pattern match each and all of the remaining elements.

*** Remember that zero occurrance of the pattern can ‘match’.

この辺は直観的に解る気がします。この辺というのは、はっきり書くと、パターン部に記述する分には、ということです。これを踏まえてじゃあテンプレート部ではどうなるか、ということについてはその次です。

When a pattern has an ellipses, the pattern variables within the clause prior to the ellipses work differently from normal. When you use one of these pattern variables in the template, it must be suffixed with an ellipses, or it must be contained in a template subform that is suffixed with an ellipses. In the template, anything suffixed with an ellipses will be repeated as many times as the enclosed pattern variables matched.

これ以下のように、日本語の文章にしてみます。

パターンに略記号があった場合、略記号の前にあるパターン変数の働きが普段と違ってきます。そのような略記号の前にあるパターン変数を、テンプレート部に使う時には、パターン変数それ自体に略記号が続いている、もしくは、略記号が続いているサブフォームの中にパターン変数がある、ということが必須となります。テンプレート部で、略記号が続いているものは全て、そのパターン変数がマッチしたと同じ回数分、繰り返されるということになります。

実際に動かしてみます。

;; ((a ...) (b ...) var (c ...))
(let-syntax
    ((foo (syntax-rules ()
            ((foo var #t ((a . b) c) ...)
             '((a ...) (b ...) var (c ...))))))
  (foo 11 #t
       ((moe larry curly) stooges)
       ((carthago delendum est) cato)
       ((egad) (mild oath))))
;;=>
;; ((moe carthago egad)
;;  ((larry curly) (delendum est) ())
;;  11
;;  (stooges cato (mild oath)))

;; ((a b c) ... var)
(let-syntax
    ((foo (syntax-rules ()
            ((foo var #t ((a . b) c) ...)
             '((a b c) ... var)))))
  (foo 11 #t
       ((moe larry curly) stooges)
       ((carthago delendum est) cato)
       ((egad) (mild oath))))
;;=>
;; ((moe (larry curly) stooges)
;;  (carthago (delendum est) cato)
;;  (egad () (mild oath))
;;  11)

;; ((c . b) ... a ...)
(let-syntax
    ((foo (syntax-rules ()
            ((foo var #t ((a . b) c) ...)
             '((c . b) ... a ...)))))
  (foo 11 #t
       ((moe larry curly) stooges)
       ((carthago delendum est) cato)
       ((egad) (mild oath))))
;;=>
;; ((stooges larry curly)
;;  (cato delendum est)
;;  ((mild oath))
;;  moe carthago egad)

;; (let ((c 'b) ...) (a 'x var c) ...)
(let-syntax
    ((foo (syntax-rules ()
            ((foo var #t ((a . b) c) ...)
             '(let ((c 'b) ...) (a 'x var c) ...)))))
  (foo 11 #t
       ((moe larry curly) stooges)
       ((carthago delendum est) cato)
       ((egad) (mild oath))))
;;=>
;; (let ((stooges (quote (larry curly)))
;;       (cato (quote (delendum est)))
;;       (#0=(mild oath) (quote ())))
;;   (moe (quote x) 11 stooges)
;;   (carthago (quote x) 11 cato)
;;   (egad (quote x) 11 #0#))

実際動かしてみると、ざっくりだけれども略記号の働きをより深く再確認できたんじゃないかなと。というわけで、前回の multiple-value-set! を考えます。

;; 再掲:
;; これが
(multiple-value-set! (a b c) (values 1 2 3))

;; こう展開されるのを目指します
(call-with-values
  (lambda () (values 1 2 3))
  (lambda (tmp1 tmp2 tmp3)
    (set! a tmp1)
    (set! b tmp2)
    (set! c tmp3)))
;; 再掲おわり

;; ... を使う例
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((_ vars values-form)
     (gen-tmps-and-sets vars () () values-form))))

(define-syntax emit-cwv-form
  (syntax-rules ()
    ((_ tmps assignments values-form)
     (call-with-values
       (lambda () values-form)
       (lambda tmps . assignments)))))

(define-syntax gen-tmps-and-sets
  (syntax-rules ()
    ((_ () tmps sets values-form)
     (emit-cwv-form tmps sets values-form))
    ((_ (var . vars) (tmps ...) (sets ...) values-form)
     (gen-tmps-and-sets vars
                        (tmps ... tmp)
                        (sets ... (set! var tmp))
                        values-form))))

(let ((a #f) (b #f) (c #f))
  (multiple-value-set! (a b c) (values 1 2 3))
  (list a b c))
;;=> (1 2 3)
;;->
;; (call-with-values
;;   (lambda () (values 1 2 3))
;;   (lambda (tmp tmp tmp)
;;     (set! a tmp)
;;     (set! b tmp)
;;     (set! c tmp)))

(var . vars) の所で再帰的に gen-tmps-and-sets を呼び出すのだけれども、累積する所それぞれに略記号 ... を使い、末尾に値が追加されて貯まっていくようにしています。

コード片がもう少し込み入ったものを写経します。

(define-syntax trace-subforms
  (syntax-rules ()
    ((_ form) (trace-expand form ()))))

(define-syntax trace-expand
  (syntax-rules ()
    ((_ () traced) (trace-emit . traced))
    ((_ (form . forms) traced)
     (trace-expand forms
                   ((begin
                      (newline)
                      (display "Evaluating ")
                      (display 'form)
                      (flush)
                      (let ((result form))
                        (display " => ")
                        (display result)
                        (flush)
                        result))
                    . traced)))))

(define-syntax trace-emit
  (syntax-rules ()
    ((_ function . arguments)
     (begin
       (newline)
       (let ((f function)
             (a (list . arguments)))
         (newline)
         (display "Now applying function.")
         (flush)
         (apply f a))))))

(trace-subforms (+ 2 3))
;;=> *** ERROR: invalid application: (3 2 #<subr (+ :rest args)>)
;;>> Evaluating 3 => 3
;;>> Evaluating 2 => 2
;;>> Evaluating + => #<subr (+ :rest args)>
;;>> Now applying function.

(この例はエラーとなるのだけれども、エラーを解消したものはすぐ後に示します。)

traced にコードを蓄積していくわけだけれども、 (trace-emit . traced) でつまづいたので、自分なりに解説してみます。なぜここで、 . を使うのかな、という疑問です。

traced には ((begin ..) (begin ..) (begin ..) ..) のように、 begin にくるまれたコード片が蓄積されています。一方、 trace-emit で、 (trace-emit function . arguments) というパターンを指定しているのは恐らく、普段のSchemeコード上の関数定義に似た形であることを重視しているのかな、と考えられます。そこで、 trace-emit マクロを呼び出す箇所では、 (trace-emit traced) ではなく (trace-emit . traced) とすることで trace-emit マクロで指定しているパターンに合わせている、と考えます。

trace-emit を、 (trace-emit traced) として呼び出すとすると、 trace-emit 側で指定されているパターンは (trace-emit (function . arguments)) となっている必要があります。

自分はつまずいたので、どちらが後で眺めた時に意図したことが伝わるかな、と考えてみます。普段のSchemeの関数呼び出しでは (func a b c) の形をしているから、 trace-emit マクロ内で指定している (trace-emit function . argumets) というパターンは自然な気がします。それに合わせるように呼び出し側で工夫している、ということになるのだろうか。 N-ary マクロを取り扱うので、そこも注意点というのもあります。といったことが合わさってつまずいたのだろうと考えています。

エラーを解消するにはリストを反転するマクロを間に狭むことも考えられるけれども、略記号を使うと良い結果が得られるということで以下。

(define-syntax trace-subforms
  (syntax-rules ()
    ((_ (form ...))
     (trace-emit
      (begin
        (newline)
        (display "Evaluating ")
        (display 'form)
        (flush)
        (let ((result form))
          (display " => ")
          (display result)
          (flush)
          result)) ...))))

(define-syntax trace-emit
  (syntax-rules ()
    ((_ function . arguments)
     (begin
       (newline)
       (let ((f function)
             (a (list . arguments)))
         (newline)
         (display "Now applying function.")
         (flush)
         (apply f a))))))

(trace-subforms (+ 2 3))
;;=> 5
;;>> Evaluating + => #<subr (+ :rest args)>
;;>> Evaluating 2 => 2
;;>> Evaluating 3 => 3
;;>> Now applying function.

前の例では、 trace-expand を再帰的に呼び出してコード片を蓄積していったのだけれども（そして最後に反転すれば完成だった）、 ... 記号を使うことでやりたかったことは再帰的な呼び出し抜きにして達成できました。これ実は map 的なことをして、 trace-emit に与えているのだけれども、略記号を使うと簡潔に済ますことができました。

さてここでは上では触れなかった (list . arguments) の部分に注目します。その前の (let ((f function) ..)) は、 function にはコード片そのものがある、というか、パターン変数（の参照というか…）が表れている、と。テンプレートに表れるパターン変数は入力内の一致する部分形式に置き換えられる、ので展開系は以下のようになります。

(let ((f (begin ..)) ..) ..)

コード片を評価して f に束縛される、というコードに展開されます。 (list . arguments) も考えると、

(let ((f (begin ..))
      (a (list (begin ..) (begin ..) ..))) ..)

こうなるわけで、ある意味、実行している Scheme 処理系がどのように let や (list ..) を評価するかを見ているとも考えられます。なんで let* へ展開しなかったんだろう、とか、 (list ..) の部分の評価順を考慮していたんだろうか、とか考えてしまうけれどもここで止めておきます。

末尾再帰で書く必要があるなら、リスト等の要素を先頭から見ていく時に、コンスして蓄積して行くとすると最後には反転する必要がある、これを避けるには、蓄積する時に、略記号で要素を (append temps (list temps)) すると都合が良い、ただし、実行時のコードでは避けるイディオムだけれども、マクロ展開時には普通に使われる手法である、と。“On Lisp”か何かでも目にしたような気がする。

*** Use ellipses to extend lists while retaining the order.

*** Use ellipses to ‘flatten’ output.

flatten の例を実際に試してみます。

(let-syntax
    ((foo
      (syntax-rules ()
        ((foo (f1 ...) (f2 ...) . forms)
         '(f1 ... f2 ... . forms)))))
  (foo (a b c d) (1 2 3 4) moe larry curly))
;;=> (a b c d 1 2 3 4 moe larry curly)

最後。補助マクロをグローバルに定義するのに気が引ける場合には、 label をパターンに置いてローカルマクロっぽくするという手があります、と。

(define-syntax multiple-vaule-set!
  (syntax-rules ()
    ((_ vars values-form)
     (mvs-aux "gen-code" vars () () values-form))))

(define-syntax mvs-aux
  (syntax-rules ()
    ((_ "gen-code" () tmps sets values-form)
     (mvs-aux "emit" tmps sets values-form))
    ((_ "gen-code" (var . vars) (tmps ...) (sets ...) values-form)
     (mvs-aux "gen-code"
              vars
              (tmps ... tmp)
              (sets ... (set! var tmp))
              values-form))
    ((_ "emit" tmps sets values-form)
     (call-with-values
       (lambda () values-form)
       (lambda tmps . sets)))))

(let ((a #f) (b #f) (c #f))
  (multiple-vaule-set! (a b c) (values 1 2 3))
  (list a b c))
;;=> (1 2 3)
;;->
;; (call-with-values
;;   (lambda () (values 1 2 3))
;;   (lambda (tmp tmp tmp)
;;     (set! a tmp)
;;     (set! b tmp)
;;     (set! c tmp)))