マクロでtarai回し 5回目

引数に0が含まれるときにも動くように修正した。

• tarai-mac.scm

#! /usr/bin/env gosh

(define-syntax tarai
  (syntax-rules ()
    ((_ (%x ...) (%y ...) (%z ...))
     (tarai "loop" (%x ...) (%y ...) (%x ...) (%y ...) (%z ...)))

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

    ((_ "loop" () (%y1 ...) %x-value %y-value %z %k ...)
     (tarai "return" %y-value %k ...))

    ((_ "loop" (%x1 %x2 ...) () %x-value %y-value %z %k ...)
     (tarai 0
                ("delay" (tarai 3 %x-value %y-value %z))
                ("delay" (tarai 3 %y-value %z %x-value))
                ("delay" (tarai 3 %z %x-value %y-value))
                %k ...))

    ((_ 0 %x %y %z %k ...)
     (tarai "force" %x (tarai 1 %y %z) %k ...))

    ((_ 1 %y %z %x-value %k ...)
     (tarai "force" %y (tarai 2 %z %x-value) %k ...))

    ((_ 2 %z %x-value %y-value %k ...)
     (tarai "loop" %x-value %y-value %x-value %y-value %z %k ...))

    ((_ 3 %x %y %z %k ...)
     (tarai "force" %x (tarai 4 %y %z) %k ...))

    ((_ 4 %y %z () %k ...)
     (tarai "force" %y %k ...))

    ((_ 4 %y %z (%x1 %x2 ...) %k ...)
     (tarai 1 %y %z (%x2 ...) %k ...))

    ((_ "force" ("delay" (%f ...)) %k ...)
     (%f ... %k ...))

    ((_ "force" %val %k ...)
     (tarai "return" %val %k ...))

    ((_ "return" %val)
     %val)

    ((_ "return" %val (%k1 ...) %k2 ...)
     (%k1 ... %val %k2 ...))

    ))

(define (main args)
  (display (macroexpand '(tarai (12 11 10 9 8 7 6 5 4 3 2 1) (6 5 4 3 2 1) ())))
  (newline))

% time ./tarai-mac.scm
(12 11 10 9 8 7 6 5 4 3 2 1)

real    0m0.038s
user    0m0.025s
sys     0m0.001s

ちなみに、実行時間の比較をすると、

• tarai.scm

#! /usr/bin/env gosh

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

(define (main args)
  (display (tarai 12 6 0))
  (newline))

% time ./tarai.scm
12

real    0m2.537s
user    0m2.458s
sys     0m0.006s

• tarai-delay.scm

#! /usr/bin/env gosh

(define (tarai x y z)
  (if (<= (force x) (force y))
      (force y)
      (tarai (delay (tarai (- (force x) 1) y z))
             (delay (tarai (- (force y) 1) z x))
             (delay (tarai (- (force z) 1) x y)))))

(define (main args)
  (display (tarai 12 6 0))
  (newline))

% time ./tarai-delay.scm
12

real    0m0.028s
user    0m0.012s
sys     0m0.006s

さすがにpromiseを使ったものよりは落ちるが、マクロ版も意外と効率は良いようだ。