You can regard trampolines as compiler optimizations reified in the program. So what is stopping us from adapting more general optimization techniques in exactly the same manner.
Here is a sketch of tail recursion modulo cons
:
const loop = f => {
let step = f();
while (step && step[step.length - 1] && step[step.length - 1].type === recur) {
let step_ = step.pop();
step.push(...f(...step_.args));
}
return step;
};
const recur = (...args) =>
({type: recur, args});
const push = (xs, x) => (xs.push(x), xs);
const map = f => xs =>
loop((i = 0) =>
i === xs.length
? []
: push([f(xs[i])], recur(i + 1)));
const xs =
map(x => x * 2) (Array(1e6).fill(0).map((x, i) => i))
.slice(0,5);
console.log(xs); // [0, 2, 4, 6, 8]
This kind of optimization depends on the associativity property of an expression. Multiplication is associative too and hence there is tail recursion modulo multiplication. However, I have to cheat to implement it in Javascript:
const loop = f => {
let step = f();
const acc = [];
while (step && step[1] && step[1].type === recur) {
acc.push(step[0]);
step = f(...step[1].args);
}
return acc.reduce((acc, f) => f(acc), step);
};
const recur = (...args) =>
({type: recur, args});
const mul = x => step => [y => x * y, step];
const pow = (x_, n_) =>
loop((x = x_, n = n_) =>
n === 0 ? 1
: n === 1 ? x
: mul(x) (recur(x, n - 1)));
console.log(
pow(2, 1e6)); // Infinity, no stack overflow
As you can see I cannot use a regular mul
, which isn't particular satisfying. Is this connected with Javascript beeing a strict language? Is there a better way to achieve tail recursion modulo multiplication in JS without having to introduce awkward binary operators?
Instead of using
loop
/recur
(which I consider an ugly and unnecessary hack), consider using folds:Almost every recursive function can be defined using folds (a.k.a. structural recursion, a.k.a. induction). For example, even the Ackermann function can be defined using folds:
The above code snippet takes about 18 seconds to compute the answer on my laptop.
Now, you might ask why I implemented
recNat
using iteration instead of natural recursion:I used iteration for the same reason you used iteration to implement
loop
. Trampolining. By implementing a different trampoline for every data type you're going to fold, you can write functional code without having to worry about stack overflows.Bottom line: Use folds instead of explicit recursion. They are a lot more powerful than you think.