So... am I crazy? This is working TCO, right? It's infinite recursion.
const getFibPromise = ( n,k ) => new Promise( resolve => queueMicrotask( () => resolve( fib(n,k) ) ) );
const fib = (n,k=0) => { if(n<=0) return 0+k; if(n===1) return 1+k; return getFibPromise( n-1,n+k ); }
const runFib = async n => {
return await fib(n);
}
Warning! Please don't overtax my example code above: queueMicrotask is dangerous. It will hang your browser. (Could fix by substituting a setTimeout() after 1000 microtasks or something.)
Other than that, feel free to drop this into your console and try it.
The method is:
- we create a promise in a new frame IFF we need to recurse
- we use await to follow those promises until we get a result
It's so simple that maybe this doesn't really count. Feel free to tell me this is not actually TCO.
If this is TCO, the dedicated TCO syntax can just be syntactical sugar around something like this setup, right?
Easy to implement in modern browsers because it already works.
In the dev console, we don't lose the call chain because await already preserves that across dropped frames.
Am I missing something here?
So yes, that will correctly implement TCO. The only issue is that you're forced to use a promise with that method, even though you're not performing an async task - a lot of functions people are wanting to optimize with TCO are not async functions, so this would not be an option for them.
A similar solution that can be done today, without promises, would be to use the trampoline method to implement TCO.
function trampoline(fn) {
return (...args) => {
let result = fn(...args)
while (result instanceof Function) {
result = result()
}
return result
}
}
const fib = trampoline(function innerFib(n, a = 0n, b = 1n) {
if(n===0) return a;
return () => innerFib(n - 1, b, a + b)
})
console.log(fib(10_000))
I'm not sure all of the reasons for why TCO was not done. I remember "difficulty of implementation" being a big issue, and perhaps it's much more difficult for them to refactor their code and implement it properly than for us to do it through things like the trampoline method. I don't know why it would have been difficult to implement it, but I also don't know what their code looks like, and knowing how much browsers try to optimize things, there could be a lot of different pieces in the engine that rely on the current call-stack behavior. I think difficulty-of-implementation wasn't the only issue though.
One reason is that error tracebacks can get pretty confusing, because they're missing frames that were optimized away, and so you may be unable to track the code path to the error.
1 Like
@lightmare Which this method solves using await's dropped frame memory.
I thought so, but not exactly!
Inside a recursive function, we can freely swap tail calls to recursive / non-recursive functions without using await | then()! 
const fib = new Recurse(
(n,k=0) => {
if(n<=0) return 0+k;
if(n===1) return 1+k;
return fib( n-1, n+k );
// ^ tail call can be any normal or recursive function
// await / then not required at all!
// (tail-normal functions can also tail-call recursives without await)
}
)
//outside a recursive, we must use await / then
fib( 5 ).then( console.log ); //15
//SAME WARNING: Do not overtax this e.g. fib(1000000000) will hang browser
Edit: Only benefit over trampoline: You don't return a function, you use recursion and it just works.
Edit2: My fib() function is not fibonacci at all. No idea what it is other than recursive / doesn't matter.
const Recurse = ( () => {
const RECURSE = Symbol();
function Recurse( f ) {
return ( ...args ) =>
new Promise( resolve => {
let schedule, shortcircuit;
//using an exposed promise because they solve everything :-P
let p = new Promise( resolve => ( schedule = setTimeout( () => resolve( f(...args) ), 1 ), shortcircuit = resolve ) );
Object.defineProperty( p, RECURSE, {value:() => ( clearTimeout( schedule ), queueMicrotask( () => shortcircuit( f( ...args ) ) ) )} );
const loop = () => {
if( typeof p[ RECURSE ] === 'function' ) {
p[ RECURSE ]();
p.then( r => ( p = r, queueMicrotask( loop ) ) );
} else resolve( p );
}
loop();
} )
}
return Recurse;
} )()
Sure you're not explicitly doing an await or .then() inside the function definition, you're just having the Recurse() function do that for you between every step.
The issue is that fib() itself is an async function when it shouldn't be. There's nothing asynchronous about the task you're doing, but you're forcing consumers of your fib() function to await the result anyways. Wouldn't you find it weird if you had to call the helper functions from lodash with await, simply because they decided to implement their algorithms using a tail-call recursion system like this?
I promise, that matters. It means infinite recursion in tail calls is already implementable in browsers.
Only if Recurse() is polyfilled. Not if it's implemented behind the scenes in JS:
recurse function fib() { ... }
Oh, actually... Why do I need Promises for Recurse() at all? It's never doing anything async.
There has to be a way to combine by Recurse() loop with your trampoline.
I'll look at this more after work.
Thanks, got it: Proper Tail Call vs. Syntactic Tail Call vs. Tail Call Optimization vs recursion.
@theScottyJam I got it working good enough for personal use:
var f = Recurse(
(n,k=0) => {
if(n<=0) return 0+k;
if(n===1) return 1+k;
return f( n-1, n+k );
// ^ tail call any recursive or normal function
}
);
f( 5 ); //returns 15, infinite recursion
Unfortunately, it has 1 major limitation:
- Inside of a recursive function, calls to recursive functions must only occur in tail-call positions
Remembering that without any clear hints in the code itself is absurd.
Personal use will have to do.
I would really like the browser version.
Functional programming is impossible without arbitrary recursion.
For example, I have a lexer written with just a little functional programming flow, so it sort-of works, but if you give it anything too nested, you'll hit too much recursion.
If browsers did implement this as syntactical sugar to the async method, you would have to require a special keyword in front of every call to a recursive function unless you were inside a recursive function.
const f = recurse x => f( ... ) //no 'recurse' qualifier inside recurser
const result = recurse f( ... ) //'recurse' qualifier outside recurser
Or something. You can't make recurse a reserved word, so I don't know exactly how it would work.
I agree, it would be nice to have syntactic tail call recursion in Javascript. Who knows, maybe in 20 years this idea will be picked up again :p
I know.
Well, it's not like I can't have it at all. And maybe I'll think of some other method eventually.
Forgot to note how flawed this reasoning is (for syntactic tail calls).
Equivalent of saying: "We're not going to implement loops because debuggers can't preserve a complete history of loop iteration states."
In functional programming, we use recursion instead of loops.
Without arbitrary recursion (requires dropped frames), functional programming is impossible in JS.