JavaScript版SICP（計算機プログラムの構造と解釈）のニュートン法の末尾再帰関数を見た目を保ったままスタックセーフにする
JavaScript版SICP（計算機プログラムの構造と解釈）をちょこっと覗いてみた。そしたら最初に出てきた繰り返しの例がニュートン法で、しかも末尾再帰で実装されていた。JavaScriptの前はSchemeが使われていたらしいから、再帰で当然なのかもしれない。それにしたって、「JavaScriptで入門しようねー」という雰囲気なのに、しょっぱなからループが再帰で書かれていたらビビる。とても楽しい。
注釈では、再帰関数で反復を実装する際の効率が気になるなら1.2.1を読んでねと書いてあった。
[4] Readers who are worried about the efficiency issues involved in using function calls to implement iteration should note the remarks on "tail recursion" in section 1.2.1.
そんな注釈はガン無視して、while文を使ったスタックセーフな実装に書き換えてみる。
末尾再帰なオリジナル関数
書き換える関数は sqrt と sqrt_iter だけなので、そこだけ先に引用しておこう。他の関数はTypeScriptで型を付けた上で、最後にまとめて記載する。
function sqrt(x) {
return sqrt_iter(1, x);
}
function sqrt_iter(guess, x) {
return is_good_enough(guess, x)
? guess
: sqrt_iter(improve(guess, x), x);
}スタックセーフな関数への書き換え
書き換えたものは次のようになる。新たに追加された starts関数, returns関数, restarts関数はTypeScriptで型を付けた上で、最後にまとめて記載する。
function sqrt_s(x) {
return sqrt_iter_s(1, x);
}
const sqrt_iter_s = starts(function (guess, x) {
return is_good_enough(guess, x)
? returns(guess)
: restarts(improve(guess, x), x);
});オリジナルの sqrt と書き換えた sqrt_s の違いはほとんどない。これに異論はないだろう。
一方で、オリジナルの sqrt_iter と書き換えた sqrt_iter_s についは、それなりに書き換わったと感じるかもしれない。sqrt_iter_s は、sqrt_iter を次の手順で書き換えている。
「function sqrt_iter」を「const sqrt_iter_s = starts(function 」に書き換える
最終結果の「guess」を「returns(guess)」に書き換える
再帰呼び出しの「sqrt_iter」を「restarts」に書き換える
関数の終わり「}」を「});」に書き換える
上記の通り、書き換えは行ごとに行われている。複数の行にまたがった書き換えはない。部分部分を少し書き換えているだけだ。この程度の書き換えなら、見た目のほとんどが保たれると言えるのではないだろうか。いや、言える。私は見た目が保たれていると思う（ごり押し）。
他の末尾再帰にも使える
同様に、他の末尾再帰な関数もスタックセーフな関数へ機械的に書き換えられる。具体的には次のように書き換えればいい。
「function 関数名」を「const 関数名 = starts(function 」に書き換える
「最終結果」を「returns(最終結果)」に書き換える
再帰呼び出しの「関数名」を「restarts」に書き換える
関数の終わり「}」を「});」に書き換える
例えば、JS版SICPの1.2.1節に載っている末尾再帰な階乗関数も機械的に書き換えられる。
末尾再帰なオリジナル関数
function factorial(n) {
return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
return counter > max_count
? product
: fact_iter(counter * product, counter + 1, max_count);
}スタックセーフな関数への書き換え
function factorial_s(n) {
return fact_iter_s(1, 1, n);
}
const fact_iter_s = starts(function (product, counter, max_count) {
return counter > max_count
? returns(product)
: restarts(counter * product, counter + 1, max_count);
});このように、末尾再帰な関数はスタックセーフな関数に機械的に書き換えられる。だから、スタックオーバーフローが気になったらサクッと書き換えたらいい。
まあ、SICPは学習目的のコードだし、注釈やら別のページやらで、再帰関数に関する注意点はきちんと説明しているのだから、書き換える必要があるとも思えないが。
説明になっていない仕組みの説明
スタックセーフな実装への書き換えで登場するのは starts と restarts、returns だ。このうち、starts は run の構文糖衣（ちょっと書きやすくしたもの）で、restarts は continues の構文糖衣になっている。run を含めた各実装は次のとおりだ。
const starts = (next) => (...state) => run(state, state => next(...state));
const restarts = (...state) => continues(state);
const run = (state, next) => {
let step = next(state);
while (step.tag === 'continues') {
step = next(step.state);
}
return step.value;
};
const continues = (state) => ({
tag: 'continues',
state
});
const returns = (value) => ({
tag: 'returns',
value
});starts とrestartsは「...」と書かれる残余構文とスプレッド構文のせいで複雑に見える。だが、逆に言えば「...」を使っているくらいで他には何もしていない。書き換えに伴う書き味をよくするための構文糖衣であって、本質的には何もしていない。書き味と言っても、スタックセーフな関数に機械的に書き換える際、「(引数)」を「([引数])」と書き換えずに済むようになるぐらいだ。かなり微妙な違いで、ぶっちゃけ無くても問題ない。
continues と returns は値構築子（単純なオブジェクトを作るためだけの関数）になっている。値構築子なので本質的な仕組みは持っていない。
つまり、本質的な仕組みのすべては run が持っている。
では、末尾再帰における本質的な仕組みとは何だろうか。それは引数の状態遷移だ。f が末尾再帰関数だったとすると、f(いくつかの引数) を実行すれば、どこかで f(別のいくつかの引数) が実行される。あるいは最終結果が得られるかもしれない。例えば、fact_iter(2, 3, 6) は fact_iter(6, 4, 6) を呼び出す。fact_iter(720, 7, 6) からは 720 が得られる。
末尾再帰関数の要点は２点だけだ。①引数がどのように変化するかという点。②引数の変化がなくなったときに、どのような最終結果が得られるかという点。この２点だけだ。
run 関数は引数で受け取った next 関数を使い、①引数（step.state）の変化を再現する。②引数の変化が終了したら、得られた結果（step.value）を返す。run 関数は末尾再帰関数の要点をおさえて、末尾再帰関数の仕組みを模倣している。そして、run 関数自体は while 文によって書かれているのだから、明らかにスタックセーフな実装である。めでたし、めでたし。
末尾再帰になっていない再帰はめでたくない問題
何もめでたくない。末尾再帰でない再帰関数はスタックセーフにならないじゃないか。
この問題を解決するのに、直接スタイル（DS）を継続渡しスタイル（CPS）に書き換える方法がある。継続渡しスタイルで書くと、すべてが末尾呼び出しに変わる。末尾呼び出し最適化が効く言語であれば、あら不思議。スタックセーフになるのだ。めでたし。めでたし。
めでたくない。proper tail calls (tail call optimisation)の対応状況からして、JavaScriptの末尾呼び出し最適化は期待しずらい。そもそも、while文を使ったスタックセーフな実装に書き換えることを目的にSICPの注釈を無視したのだ。末尾呼び出し最適化を頼ったら、末尾再帰関数をwhile文で書き換えた意味がなくなってしまう。そんな本末転倒は避けなければならない（注釈を無視する方が本末転倒だろうという正論はわきに置いておく）。
しょうがない。継続渡しスタイルと末尾呼び出し最適化を手で書くしかない。力技だ。実用性も理論的な美しさもかなぐり捨てて、それっぽい物をでっち上げるしかない。
そんな気合と筋肉で、JS版SICPの1.2.1節に載っている末尾再帰でない再帰関数を次のように書き換えてみた。
階乗：末尾再帰でないオリジナル再帰関数
function factorial_ds(n) {
return n === 1
? 1
: n * factorial_ds(n - 1);
}階乗：スタックセーフな関数への書き換え
const factorial_r1 = (n) => run1(n, n => n === 1
? returns(1)
: winding(n, continues(n - 1)), (n, prev_fact) => returns(n * prev_fact));アッカーマン関数：末尾再帰でないオリジナル再帰関数
よく知られた定義と違う気もするが、SICPとしては、これがアッカーマン関数らしい。
function ack_ds(x, y) {
return y === 0
? 0
: x === 0
? 2 * y
: y === 1
? 2
: ack_ds(x - 1, ack_ds(x, y - 1));
}アッカーマン関数：スタックセーフな関数への書き換え
const ack_r1 = (x, y) => run1([x, y], ([x, y]) => y === 0
? returns(0)
: x === 0
? returns(2 * y)
: y === 1
? returns(2)
: winding(x, continues([x, y - 1])), (x, a) => continues([x - 1, a]));このように、継続を１つ使えば末尾呼び出しにできる再帰関数は、run1 によってスタックセーフな関数へ書き換えられる。新たに追加された run1関数や winding関数はTypeScriptで型を付けた上で、最後にまとめて記載する。
run1の仕組みはともかく、変換の方針は明快だ。継続渡しスタイルで書いたときに現れる継続を run1 の第三引数に取り出す。factrial_r1 で言えば「(n, prev_fact) => returns(n * prev_fact)」が取り出した継続にあたる。
ただ、そのまま外に出してしまうと、継続がクロージャーだった場合に困ることがある。と言うのも、外に出した時に参照できる環境が変わってしまうからだ。元いたスコープでしかキャプチャできない変数なんかもある。そこで、キャプチャしたい変数を明示的にwindingでキャプチャさせることにした。そして、キャプチャした環境を第一引数、再帰の結果を第二引数として取り出した継続に渡すことで、直接スタイルの再帰関数を継続渡しスタイルに書き換えた時と同じ効果を実現している。そして裏側では、末尾呼び出し最適化なしでスタックセーフになるように実装している（まあ、スタック領域の代わりにヒープ領域を食い尽くす可能性はあるが）。
では、継続を２つ使わないと末尾呼び出しにならない再帰関数はどのように書き換えられるだろうか。簡単だ。外に出す継続を２つに増やせばいい。しからば、JS版SICPの1.2.2節に載っている末尾再帰でない再帰関数は次のように書き換えられる。
フィボナッチ数：末尾再帰でないオリジナル再帰関数
function fib_ds(n) {
return n === 0
? 0
: n === 1
? 1
: fib_ds(n - 1) + fib_ds(n - 2);
}フィボナッチ数：スタックセーフな関数への書き換え
const fib_r2 = (n) => run2(n, n => n === 0
? returns(0)
: n === 1
? returns(1)
: winding(n, continues(n - 1)),
(n, fib1) => winding(fib1, continues(n - 2)),
(fib1, fib2) => returns(fib1 + fib2));最小コイン数：末尾再帰でないオリジナル再帰関数
function count_change(amount) {
return cc(amount, 5);
}
function cc(amount, kinds_of_coins) {
return amount === 0
? 1
: amount < 0 || kinds_of_coins === 0
? 0
: cc(amount, kinds_of_coins - 1)
+
cc(amount - first_denomination(kinds_of_coins), kinds_of_coins);
}
function first_denomination(kinds_of_coins) {
return kinds_of_coins === 1 ? 1
: kinds_of_coins === 2 ? 5
: kinds_of_coins === 3 ? 10
: kinds_of_coins === 4 ? 25
: kinds_of_coins === 5 ? 50
: 0;
}最小コイン数：スタックセーフな関数への書き換え
const count_change_r2 = (amount) => run2([amount, 5], ([amount, kinds_of_coins]) => amount === 0
? returns(1)
: amount < 0 || kinds_of_coins === 0
? returns(0)
: winding([amount, kinds_of_coins], continues([amount, kinds_of_coins - 1])),
([amount, kinds_of_coins], cc1) => winding(cc1, continues([amount - first_denomination(kinds_of_coins), kinds_of_coins])),
(cc1, cc2) => returns(cc1 + cc2));と言うわけで、N個の継続で末尾呼び出しになる再帰関数は runN でスタックセーフに書き換えられる。ところで、0個の継続で末尾呼びだしになる再帰関数とは末尾再帰関数に他ならない。ゆえに run は run0 に他ならない。
説明になっていない仕組みの説明：runN編
runNは下記の通り機械的に定義できる。runNのNが増えるたびに引数のnextNが増え、if(go.to === N-1)の条件分岐が増えていく。だいたいそんな感じ。
runNがやっていることは$${\text{next}_{k}}$$を呼び出したら、goto_index関数を使って、次に呼び出すべき関数が$${\text{next}_{k + 1}}$$であることをタグ付けしているだけだ。驚くべきトリックはどこにもない。
const goto_index = (index, step) => step.tag !== 'winding'
? step
: winding(goes(index, step.state), step.step);
const run1 = (state, next0, next1) => run_stack(state, step => {
if (step.tag === 'continues')
return goto_index(1, next0(step.state));
const [go, value] = step.value;
return next1(go.state, value);
});
const run2 = (state, next0, next1, next2) => run_stack(state, step => {
if (step.tag === 'continues')
return goto_index(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index(2, next1(go.state, value));
return next2(go.state, value);
});
const run3 = (state, next0, next1, next2, next3) => run_stack(state, step => {
if (step.tag === 'continues')
return goto_index(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index(2, next1(go.state, value));
if (go.to === 2)
return goto_index(3, next2(go.state, value));
return next3(go.state, value);
});
const run4 = (state, next0, next1, next2, next3, next4) => run_stack(state, step => {
if (step.tag === 'continues')
return goto_index(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index(2, next1(go.state, value));
if (go.to === 2)
return goto_index(3, next2(go.state, value));
if (go.to === 3)
return goto_index(4, next3(go.state, value));
return next4(go.state, value);
});しかし、runNは末尾再帰でない再帰関数を再現するのだから、コールスタックを代替するデータ構造が何かしら必要なはずじゃないか。それはどこにあるのだろう。名前から察しが付くかもしれない。それは run_stack関数が担っている。
コールスタックは値構築子である nil と cons と使った片方向連結リストで代替する。winding関数はスタック（片方向連結リスト）に積むべき環境を指定するための関数になる。winding(env, continues(arg)) と書かれた場合、env がスタックに積まれる。積んだ後に、continues(arg) に応じた再帰処理が実行される。
const nil = ({
tag: 'nil'
});
const cons = (head, tail) => ({
tag: 'cons',
head,
tail
});
const winding = (state, step) => ({
tag: 'winding',
state,
step
});
const run_stack = (state, next) => run([continues(state), nil], ([step, stack]) => {
if (step.tag === 'winding')
return continues([step.step, cons(step.state, stack)]);
if (step.tag === 'continues')
return continues([next(step), stack]);
if (stack.tag === 'cons')
return continues([next(returns([stack.head, step.value])), stack.tail]);
return step;
});run_stack関数は環境をスタックに積んだり、取り出したりしてnext関数を呼び出す。そしてスタックが空であれば最終結果を返す。うまいことnext関数が組めれば、うまいこと動くわけだ。runN関数はそのような、うまいnext関数を作り出す糖衣構文に過ぎない。そして、run_stack関数はうまく定義されたnext関数を条件によって呼び分けているだけで、ここにも驚くべきトリックはない。
では、どこに驚くべき仕組みがあるのだろうか。run_stack は run で実装されている。run関数だけが while文によるループを持っている。runN も run_stack も、その他の値構築子にもループはない。どこにもない。run関数だけにループがある。そして run関数は末尾再帰関数を模倣するものであった。
結局、末尾再帰が驚くべき仕組みってこと。
型付きのすべてのコード
TypeScriptで次のように型が付けられる。一応、プレイグラウンドへのリンクも載せておこう。
function sqrt(x: number): number {
return sqrt_iter(1, x);
}
function sqrt_iter(guess: number, x: number): number {
return is_good_enough(guess, x)
? guess
: sqrt_iter(improve(guess, x), x);
}
function is_good_enough(guess: number, x: number): boolean {
return abs(square(guess) - x) < 0.001;
}
function abs(x: number): number {
return x >= 0 ? x : - x;
}
function square(x: number): number {
return x * x;
}
function improve(guess: number, x: number): number {
return average(guess, x / guess);
}
function average(x: number, y: number): number {
return (x + y) / 2;
}
const starts = <S extends any[], T>(next: (...state: S) => Step<S, T>) => (...state: S): T => run<S, T>(state, state => next(...state));
const restarts = <S extends any[]>(...state: S): Continues<S> => continues(state);
function sqrt_s(x: number): number {
return sqrt_iter_s(1, x);
}
const sqrt_iter_s = starts<[guess: number, x: number], number>(function (guess, x) {
return is_good_enough(guess, x)
? returns(guess)
: restarts(improve(guess, x), x);
});
const run = <S, T>(state: S, next: (state: S) => Step<S, T>): T => {
let step = next(state);
while (step.tag === 'continues') {
step = next(step.state);
}
return step.value;
};
type Step<S, T> = Continues<S> | Returns<T>;
type Continues<out S> = Readonly<{
tag: 'continues',
state: S
}>;
const continues = <S,>(state: S): Continues<S> => ({
tag: 'continues',
state
});
type Returns<out T> = Readonly<{
tag: 'returns',
value: T
}>;
const returns = <T,>(value: T): Returns<T> => ({
tag: 'returns',
value
});
function factorial(n: number): number {
return fact_iter(1, 1, n);
}
function fact_iter(product: number, counter: number, max_count: number): number {
return counter > max_count
? product
: fact_iter(counter * product, counter + 1, max_count);
}
function factorial_s(n: number): number {
return fact_iter_s(1, 1, n);
}
const fact_iter_s = starts<[product: number, counter: number, max_count: number], number>(function (product, counter, max_count) {
return counter > max_count
? returns(product)
: restarts(counter * product, counter + 1, max_count);
});
function factorial_ds(n: number): number {
return n === 1
? 1
: n * factorial_ds(n - 1);
}
const factorial_r1 = (n: number): number => run1<number, number, number>(
n,
n => n === 1
? returns(1)
: winding(n, continues(n - 1)),
(n, prev_fact) => returns(n * prev_fact)
);
function ack_ds(x: number, y: number): number {
return y === 0
? 0
: x === 0
? 2 * y
: y === 1
? 2
: ack_ds(x - 1, ack_ds(x, y - 1));
}
const ack_r1 = (x: number, y: number): number => run1<[x: number, y: number], number, number>(
[x, y],
([x, y]) => y === 0
? returns(0)
: x === 0
? returns(2 * y)
: y === 1
? returns(2)
: winding(x, continues([x, y - 1])),
(x, a) => continues([x - 1, a])
);
function fib_ds(n: number): number {
return n === 0
? 0
: n === 1
? 1
: fib_ds(n - 1) + fib_ds(n - 2);
}
const fib_r2 = (n: number): number => run2<number, number, number, number>(
n,
n => n === 0
? returns(0)
: n === 1
? returns(1)
: winding(n, continues(n - 1)),
(n, fib1) => winding(fib1, continues(n - 2)),
(fib1, fib2) => returns(fib1 + fib2)
);
function count_change(amount: number): number {
return cc(amount, 5);
}
function cc(amount: number, kinds_of_coins: number): number {
return amount === 0
? 1
: amount < 0 || kinds_of_coins === 0
? 0
: cc(amount, kinds_of_coins - 1)
+
cc(amount - first_denomination(kinds_of_coins),
kinds_of_coins);
}
function first_denomination(kinds_of_coins: number): number {
return kinds_of_coins === 1 ? 1
: kinds_of_coins === 2 ? 5
: kinds_of_coins === 3 ? 10
: kinds_of_coins === 4 ? 25
: kinds_of_coins === 5 ? 50
: 0;
}
const count_change_r2 = (amount: number): number => run2<[amount: number, kinds_of_coins: number], [amount: number, kinds_of_coins: number], number, number>(
[amount, 5],
([amount, kinds_of_coins]) => amount === 0
? returns(1)
: amount < 0 || kinds_of_coins === 0
? returns(0)
: winding([amount, kinds_of_coins], continues([amount, kinds_of_coins - 1])),
([amount, kinds_of_coins], cc1) => winding(cc1, continues([amount - first_denomination(kinds_of_coins), kinds_of_coins])),
(cc1, cc2) => returns(cc1 + cc2)
);
type List<T> = Nil | Cons<T>;
type Nil = Readonly<{
tag: 'nil'
}>;
const nil: Nil = ({
tag: 'nil'
});
type Cons<out T> = Readonly<{
tag: 'cons',
head: T,
tail: List<T>
}>;
const cons = <T,>(head: T, tail: List<T>): Cons<T> => ({
tag: 'cons',
head,
tail
});
type Winding<R, S, T> = Readonly<{
tag: 'winding',
state: R,
step: Step<S, T>
}>;
const winding = <R, S, T>(state: R, step: Step<S, T>): Winding<R, S, T> => ({
tag: 'winding',
state,
step
});
const run_stack = <R, S, T>(state: S, next: (step: Step<S, [state: R, value: T]>) => Winding<R, S, T> | Step<S, T>): T => run<[Winding<R, S, T> | Step<S, T>, List<R>], T>([continues(state), nil], ([step, stack]) => {
if (step.tag === 'winding')
return continues([step.step, cons(step.state, stack)]);
if (step.tag === 'continues')
return continues([next(step), stack]);
if (stack.tag === 'cons')
return continues([next(returns([stack.head, step.value])), stack.tail]);
return step;
});
type Goes<S, T> = Readonly<{
tag: 'goes',
to: S,
state: T
}>;
const goes = <S, T>(to: S, state: T): Goes<S, T> => ({
tag: 'goes',
to,
state
});
const goto_index = <U extends number, R, S, T>(index: U, step: Winding<R, S, T> | Step<S, T>): Winding<Goes<U, R>, S, T> | Step<S, T> =>
step.tag !== 'winding'
? step
: winding(goes(index, step.state), step.step);
const run1 = <S0, S1, T>(
state: S0,
next0: (state: S0) => Winding<S1, S0, T> | Step<S0, T>,
next1: (state: S1, value: T) => Step<S0, T>
): T => run_stack<Goes<1, S1>
, S0, T>(state, step => {
if (step.tag === 'continues')
return goto_index<1, S1, S0, T>(1, next0(step.state));
const [go, value] = step.value;
return next1(go.state, value);
});
const run2 = <S0, S1, S2, T>(
state: S0,
next0: (state: S0) => Winding<S1, S0, T> | Step<S0, T>,
next1: (state: S1, value: T) => Winding<S2, S0, T> | Step<S0, T>,
next2: (state: S2, value: T) => Step<S0, T>
): T => run_stack<Goes<1, S1>
| Goes<2, S2>
, S0, T>(state, step => {
if (step.tag === 'continues')
return goto_index<1, S1, S0, T>(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index<2, S2, S0, T>(2, next1(go.state, value));
return next2(go.state, value);
});
const run3 = <S0, S1, S2, S3, T>(
state: S0,
next0: (state: S0) => Winding<S1, S0, T> | Step<S0, T>,
next1: (state: S1, value: T) => Winding<S2, S0, T> | Step<S0, T>,
next2: (state: S2, value: T) => Winding<S3, S0, T> | Step<S0, T>,
next3: (state: S3, value: T) => Step<S0, T>
): T => run_stack<Goes<1, S1>
| Goes<2, S2>
| Goes<3, S3>
, S0, T>(state, step => {
if (step.tag === 'continues')
return goto_index<1, S1, S0, T>(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index<2, S2, S0, T>(2, next1(go.state, value));
if (go.to === 2)
return goto_index<3, S3, S0, T>(3, next2(go.state, value));
return next3(go.state, value);
});
const run4 = <S0, S1, S2, S3, S4, T>(
state: S0,
next0: (state: S0) => Winding<S1, S0, T> | Step<S0, T>,
next1: (state: S1, value: T) => Winding<S2, S0, T> | Step<S0, T>,
next2: (state: S2, value: T) => Winding<S3, S0, T> | Step<S0, T>,
next3: (state: S3, value: T) => Winding<S4, S0, T> | Step<S0, T>,
next4: (state: S4, value: T) => Step<S0, T>
): T => run_stack<Goes<1, S1>
| Goes<2, S2>
| Goes<3, S3>
| Goes<4, S4>
, S0, T>(state, step => {
if (step.tag === 'continues')
return goto_index<1, S1, S0, T>(1, next0(step.state));
const [go, value] = step.value;
if (go.to === 1)
return goto_index<2, S2, S0, T>(2, next1(go.state, value));
if (go.to === 2)
return goto_index<3, S3, S0, T>(3, next2(go.state, value));
if (go.to === 3)
return goto_index<4, S4, S0, T>(4, next3(go.state, value));
return next4(go.state, value);
});