syntax-caseを実装したいの0 - .mjtの日記復帰計画

諸般の事情でsyntax-caseを実装したい。

地味に複雑なことができるsyntax-case

syntax-caseは一面的には高レベルなマクロで、パタンマッチに従っていろいろと書くことができる。特にellipsisによるパタンの繰り返し表現が強力。。
2つの値のリストを混ぜ合わせるマクロtransを考える。

(define-syntax trans
  (lambda (p)
    (syntax-case p ()
      ((_ (a b) ...) ;; <= パターン
       (syntax
         '((a ...) (b ...)))))))

これは、次のように使える。

(trans (a A) (b B) (c C) (d D) (e E)) => ((a b c d e) (A B C D E))

微妙に理解しづらいが、パターンとパターン変数が別物であることに注意する必要が有る。
上の例では、

パターン変数 : a, b
パターン : a, b, (a b), _, (_ (a b) ...)

がとなる。
ellipsis ... は、直前のパターン(パターン変数でない)の繰り返しを表現する。ここでは、(a b)の繰り返しということになる。
実装するときにやらないといけないのは、

分解: 入力を分解し、適当なリストやベクタに格納する
出力: リストやベクタに分解された入力を、指示に従って再構築する

の2つに分割できる。

フェーズ1 : 分解

上のtransの例で言えば、入力を次のように分解することを考える。

(trans (a A) (b B) (c C) (d D) (e E)) => #((#(a A) #(b B) #(c C) #(d D) #(e E)))

(transが省略されていることに注意する。パターン _ は何にでもマッチするがパターン変数にならない。)
ベクタのリストのベクタとなる。要するに、パターンが(x y z)のような形式であればベクタ#(X Y Z)のように分解し、x ...のようなellipsis形式であれば(x0 x1 x2 x3)のようなリストに分解する。
今回は、このような分解を行うプログラム自体を生成する、つまりsyntax-case節を伝統的なマクロに変換する。(nmoshがそういう実装になっている。)
実際のsyntax-case→define-macro変換器を作る前に、手でtransマクロの分解部分を書いてみる。

(define (trans-decompose input)
  (define (match-ab input success fail)
    (if (pair? input)
      (let ((a (car input))
            (input.0 (cdr input)))
        (if (pair? input.0)
          (let ((b (car input.0))
                (input.1 (cdr input.0)))
            (if (null? input.1)
              (success (vector a b))
              (fail))) ;; != ()
          (fail))) ;; != (b)
      (fail))) ;; != (a b)
  (define (match-root input fail)
    (if (pair? input) ;; (_ AB ...)
      (let ((input.0 (cdr input))) ;; (AB ...)
        (let ((map-result (map/fail match-ab input.0)))
          (if map-result
            (vector map-result) ;; (A B) ...
            (fail))))
      (fail)))
  (match-root input (lambda () (syntax-violation 'trans "invalid form" input))))

この手の処理はCPS(継続渡しスタイル)で書くことがある。なぜなら、マッチが失敗したときに、残りの処理をキャンセル、つまり大域脱出をしたくなるため。いわゆるcall/ccとか例外を使って普通に書くこともできるが、call/ccや例外は遅いことが有る。もっとも、クロージャの生成も遅いことがあるのでなんとも言えない。。
処理の段階を全て手続きに分解し、それぞれに、successとfailの2つの継続(単なるクロージャ)を渡す。successには"次"の処理を入れておき、failには失敗して抜ける処理(ここでは、syntax-violationの発行)を入れる。例外的に、match-rootにはsuccessが無い。なぜならmatch-rootのsuccessに相当する継続はtrans-decompose自体の継続であるため。(通常のプログラミング言語で考えるなら、successをreturnと読みかえると良いかもしれない)
もちろん通常のmapは今回の書き方に合わないので、今回のためのmap/failを特別に定義する必要がある。

(define (map/fail proc lis)
  (define (itr cur fail-k proc lis)
    (define (success x)
        (itr (cons x cur) fail-k proc (cdr lis)))
    (if (pair? lis)
      (proc (car lis) success fail-k)
      (reverse cur)))
  (itr '() (lambda () #f) proc lis))

map/failは自身の継続をprocに渡すが、map/fail自体の呼び出しを末尾呼び出しにするのは面倒なので手を抜いている。。