二桁！
1.2 手続きとその生成するプロセス
前文を読んだ限りでは、手続きの再帰(?)呼び出しを視覚化して、理解を深めよう、という段落に思えます。
1.2.1 線形再帰と反復
nの階乗を求める際の考え方として「再帰的プロセス(recursive process)」と「反復的プロセス(iterative process)」の2つが出てくる。
再帰的プロセスは
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
のような実装である。この際、計算を途中で中断し、再開するためには各変数の状態の他に、呼び出し履歴をスタックと呼ばれるデータ構造で持たなければならない。
反復的プロセスは
(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
のような実装である。こちらの場合は、3つの変数の状態を保持するだけで、計算を中断・再開出来る。
二つの計算プロセスの違いは別の見方も出来る。反復の方ではどの時点においてもプログラム変数がプロセスの状態の完全な記述を持っている。計算をステップの途中で止めたら、計算再開に必要なのは三つのプログラム変数だけだ。再帰的プロセスではそうはならない。こちらでは解釈系が保持し、プログラム変数に含まれない「隠れた」情報があり、それが遅延演算の列での「プロセスのいる場所」を示している。列が長くなると多くの情報を保持しなければならなくなる。
反復と再帰を比べる場合、再帰的プロセス(process)と再帰的手続き(procedure)を混同しないよう注意しなければならない。手続きが再帰的という時、手続き定義が(直接にしろ間接にしろ)その手続き自身を指す高分譲の事実をいう。しかしプロセスが、例えば線形再帰のパターンに従うという時、プロセスがどう進化するかをいうので、手続きが書いてある構文をいうのではない。。fact-iterのような再帰的手続きが反復的プロセスを生成するというのは紛らわしい。しかしプロセスは実に反復的だ：その状態は三つの変数で完全に維持され、解釈系はプロセスを実行するのに、三つの変数を覚えておくだけでよい。
最後に「末尾再帰(tail recursive)」という単語が初めて出てきたので、ちょっとだけ引用。
プロセスと手続きの区別が紛らわしい理由の一つは、(Ada, Pascal, Cを含む)通常の言語の実装が、再帰手続きの実行で消費する記憶量が、プロセスは原理的に反復的であっても、手続き呼び出し数とともに増加するように設計してあるからである。(中略)５章で検討するSchemeの実装にはこの欠点はない。反復的プロセスは再帰的手続きとして記述してあっても、固定スペースで実行できる。この性質の実装を末尾再帰(tail recursive)という。
C言語的発想だと、スタックを消費するのは「しょうがない」と思っていただけに「すげー」と思える。構文の末尾に再帰呼び出しが合ったら、特殊な動作をするのかしら。5章が楽しみです。