末尾呼び出しの最適化


Tags: R6RS, 手続き

Scheme では末尾文脈での手続き呼び出しが最適化されるので、

(import (rnrs))

(define (my-gcd a b)
  (if (zero? b)
      a
      (my-gcd b (mod a b))))

のような手続き定義は、ほかの言語で言うところのループ構造と等価なものに展開されスタックを消費しない。

def gcd(a, b)
   until b == 0 do
      a, b = b, a % b
   end

   return a
end

これは末尾文脈での呼び出しが自身に対する呼び出しかどうかにかかわらないため、より柔軟に、複数の手続き間で相互に末尾文脈で呼び出し合う場合でもこの最適化が働く。

(import (rnrs))

(define (my-even? n)
  (or (zero? n)
      (my-odd? (- (abs n) 1))))

(define (my-odd? n)
  (and (not (zero? n))
       (my-even? (- (abs n) 1))))

末尾文脈の定義は R6RS 11.20 にある。まとめると次の通りである。

よって、次の $ で始まる名前の手続きはすべて末尾呼び出しされる。

(lambda (x y)
  ($a y x))

(lambda (x)
  (b x)
  ($a x))

(lambda (x)
  (if (p? x) ($a x) x))

(lambda (x)
  (and (b x) ($a x)))

(lambda (x)
  (case (b x)
    ((c) ($a x))
    (else ($d x))))

(lambda (x)
  (cond
   ((b x) => $a)
   ((c x) => (d))))

(lambda (x)
  (let ()
    (b x)
    ($a x)))

マクロ展開によって最終的にこれらの式に展開される式の各部分も末尾文脈になる。

ここで、 dynamic-wind は末尾文脈に含まれないことに注意。

(define (f n)
  (if (zero? n)
      1
      (dynamic-wind
        (lambda () (display #f))
        (lambda () (f (- n 1)))
        (lambda () (display #f)))))

このとき、 dynamic-wind の呼び出し自体と f の呼び出し自体は末尾文脈にあるが、 dynamic-wind に渡された thunk は末尾文脈にないため、この手続きは末尾再帰的でない。