マクロでtarai回し

id:nozom:20060116#1137365062で載せたtarai関数版がそもそも間違っていた。

(define (tarai x y z)
  (if (< x y)
      y
      (tarai (tarai (1- x) y z)
             (tarai (1- y) z x)
             (tarai (1- z) x y))))

不等号は<ではなくて<=が正しい。このせいで、(1 1 1) (2 2 2)…などが自分自身に展開されてしまい、展開形にそれらを含むほとんどの数の組み合わせが無限ループしていた。

もう一つのバグはマクロの次の部分にあった。

    ; x >= y の場合
    ((_ (%r1 ...) () (%x1 %x2 ...) (%y1 %y2 ...) (%z1 %z2 ...))
     (tarai-mac (tarai-mac (%x2 ...) (%y1 %y2 ...) (%z1 %z2 ...))
                (tarai-mac (%y2 ...) (%z1 %z2 ...) (%x1 %x2 ...))
                (tarai-mac (%z2 ...) (%x1 %x2 ...) (%y1 %y2 ...))))

これは上手くいかない。関数の呼び出しは引数の評価が先に行われるが、マクロの場合は先頭から展開されるため、このような形の再帰呼び出しはマクロではできない。

ではどうするかというと、関数呼び出しで行われることを明示的に表せばいい。こういう場合はCPS(Continuation Passing Style)だ。

というわけで、taraiと等価なCPS関数は以下のようになる。

(define (tarai_cps x y z k)
  (if (<= x y)
      (k y)
      (tarai_cps (1- x) y z
                 (lambda (v1)
                   (tarai_cps (1- y) z x
                              (lambda (v2)
                                (tarai_cps (1- z) x y
                                           (lambda (v3)
                                             (tarai_cps v1 v2 v3 k)))))))))

(tarai_cps 12 6 1 values)
==> 12

これは次のようなコードと等価なので、

(define (tarai-cps x y z k)
  (if (<= x y)
      (k y)
      (tarai-cps-0 x y z k)))

(define (tarai-cps-0 x y z k)
  (tarai-cps (1- x) y z (cut tarai-cps-1 x y z <> k)))

(define (tarai-cps-1 x y z v1 k)
  (tarai-cps (1- y) z x (cut tarai-cps-2 x y z v1 <> k)))

(define (tarai-cps-2 x y z v1 v2 k)
  (tarai-cps (1- z) x y (cut tarai-cps-3 x y z v1 v2 <> k)))

(define (tarai-cps-3 x y z v1 v2 v3 k)
  (tarai-cps v1 v2 v3 k))

これを参考にしてマクロで書くと、

(define-syntax tarai-mac
  (syntax-rules ()
    ((_ (%x ...) (%y ...) (%z ...))
     (tarai-mac 0 (%x ...) (%y ...) (%z ...)))

    ((_ 0 %x %y %z %k ...)
     (tarai-mac "main" %x %y %x %y %z %k ...))

    ((_ 1 %x %y %z %v1 %k ...)
     (tarai-mac "sub" %y %z %x (tarai 2 %x %y %z %v1) %k ...))

    ((_ 2 %x %y %z %v1 %v2 %k ...)
     (tarai-mac "sub" %z %x %y (tarai 3 %x %y %z %v1 %v2) %k ...))

    ((_ 3 %x %y %z %v1 %v2 %v3 %k ...)
     (tarai-mac 0 %v1 %v2 %v3 %k ...))

    ((_ "sub" (%x1 %x2 ...) %y %z %k ...)
     (tarai-mac "main" (%x2 ...) %y (%x2 ...) %y %z %k ...))

    ((_ "main" (%x1 %x2 ...) (%y1 %y2 ...) %x %y %z %k ...)
     (tarai-mac "main" (%x2 ...) (%y2 ...) %x %y %z %k ...))

    ((_ "main" () (%y1 ...) %x %y %z)
     %y)

    ((_ "main" () (%y1 ...) %x %y %z (%k1 ...) %k2 ...)
     (%k1 ... %y %k2 ...))

    ((_ "main" (%x1 %x2 ...) () %x %y %z %k ...)
     (tarai-mac "sub" %x %y %z (tarai 1 %x %y %z) %k ...))

    ))

…元の形から結構変わってしまったが、一応ちゃんと動く。

(macroexpand '(tarai (() () ()) (() ()) (())))
==> (() () ())

せっかく自分で評価順を決められるのだから、引数の評価を関数呼び出しの前ではなく後で行うようにしたい（専門的には、前者を「作用順序」、後者を「正規順序」と言うらしい）。

この続きはまた今度。