末尾再帰と継続渡しスタイル

再帰には

の2種類があるそうな。
で、前者の末尾再帰なる形で書いておけば、Schemeが(規格に則って?)最適化してくれるらしい。
んで結果的に速いコードになるよ、ということらしい。

最後に呼び出した手続きの戻り値に何も行わない場合、最後の呼び出しは通常の意味の手続き呼び出しではなく、ジャンプとして扱われることになっています。

(p57)らしい。...サパーリ意味が分からん。
「通常の意味の手続き呼び出し」ってどういう意味なのよ?
ってか、もともとSchemeの手続き呼び出しって

継続を伴った引数つきgotoである

(p6の2行目)って言ってるやん?つまりジャンプのことなんじゃないの?


んで、よく分からないまま

プログラムコード上では再帰「呼び出し」として書いてあっても、実質的にはループとして実行されるということを意味します。

(p58)ということで、まぁ、よく分からんけど、速くなるんでしょうな。


んで、末尾再帰ではないlength関数を例に、末尾再帰に変換してます。
length関数は前回、練習問題として解いたMyLength関数のこと。


このMyLengthが末尾再帰ではない理由は、

(else (+ 1 (MyLength (cdr l))))

ってしてて、再帰的に呼び出したMyLengthの戻り値に1を足しているから。


ってことで、末尾再帰にするために、別のアプローチを取ってみよう、と。
そのアプローチとは、

「これまでに数えたリストの長さ」を余分の引数に渡してゆく、というものです。

(p58)


ここで、ピンと来たのが、The Little Schemerでのmultirember&co関数(id:yagiey:20071104)だった(この時点で、はやとちり)。
あー、継続渡しスタイルねぇー、と思い(込み)ながらlengthの書き換えをすっ飛ばして読んでいく。
最後らへんでreverseを末尾再帰で書いてみよう、ということなので、

(define MyReverse/cps
  (lambda (l cont)
    (cond
     ((pair? (cdr l))
      (MyReverse/cps (cdr l) (lambda (s) (cont (MyAppend s (list (car l)))))))
     (else (cont (list (car l)))))))

ってしてみた。
んで、参考までにlengthの末尾再帰版を見てみると、
継続渡しスタイルじゃないやん!
自分が勝手に想定していたコードはこんな感じ。

(define MyLength/cps
  (lambda (l cont)
    (cond
     ((null? l) (cont 0))
     (else (MyLength/cps (cdr l) (lambda (m) (cont (+ m 1))))))))


読んでみてナルホド。
本書のやり方は、「これまでに数えたリストの長さ」を表す数値そのものを渡す(さっきからそう言ってるやん...)のに対して、継続渡しスタイルの方は「評価したら『これまでに数えたリストの長さ』を返す関数」を渡しているのね。
ってことで、そのやり方で書き直したreverseがこちら(継続渡しではないので名前の「/cps」を取った)

(define MyReverse
  (lambda (l rev)
	(cond
	 ((pair? (cdr l)) (MyReverse (cdr l) (MyAppend (list (car l)) rev)))
	 (else (MyAppend (list (car l)) rev)))))

revが「これまで逆順にしてきたリスト」を表すのね。
The Little Schemerは継続をcollectorなんていう言い方もしていたけど、まさに「集めて」いく感じだな。
いい表現だな、と今更ながら思った。


末尾再帰と継続渡しスタイルって関連した話題なのかな?


ということで、末尾再帰への書き直しはできたけど、それがどんだけ速くなるのかはサパーリわからん。
実感できていない分、なんか胡散臭くも感じるけど、そういうもんだと覚えておこう。


ということで6章終了。