再帰には
の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章終了。
