I'm concerned about looping. It looks like you're implementing function calls in terms of JavaScript function calls, so there's no tail call elimination, and a recursive loop will soon exhaust the JS stack. A while loop could be a practical alternative.
Thanks to your advices. The runtime is based on Node.js, so there is no tail recursion elimination, I'm finding a method to transform recursion code to iteration code automatically, do you have some advice?
If you want to have full tail recursion elimination, I recommend changing everything to work in continuation-passing style. That will overflow the JS stack even sooner, so I recommend using a trampoline.
// before
function plus( a, b ) {
return a + b;
}
// after
function plus( a, b, then ) {
// We call `then()` only after we've unwound the stack.
return trampolineBounce( function () {
return then( a + b );
} );
}
// the trampoline system
function trampolineBounce( func ) {
return { type: "bounce", func: func };
}
function runTrampoline( func ) {
var step = func( function ( result ) {
return { type: "result", result: result };
} );
while ( step.type === "bounce" )
step = step.func();
return step.result;
}
// example usage
var onePlusTwoPlusThree = runTrampoline( function ( then ) {
return plus( 1, 2, function ( onePlusTwo ) {
return plus( onePlusTwo, 3, function ( result ) {
return then( result );
} );
} );
} );
This part is a bit redundant:
function ( result ) {
return then( result );
}
It's equivalent to `then` but uses one more JS stack frame. We can just reuse the `then` continuation directly. In general, the places we can do this are tail calls.
// example usage with a tail call
var onePlusTwoPlusThree = runTrampoline( function ( then ) {
return plus( 1, 2, function ( onePlusTwo ) {
return plus( onePlusTwo, 3, then );
} );
} );
---
"I'm finding a method to transform recursion code to iteration code automatically"
I don't think it's possible to get full tail recursion elimination that way unless you statically analyze the whole program, or you transform the code so it uses the CPS-and-trampolining technique above.
Maybe you can get something somewhat less powerful than full tail recursion, but I don't have advice on that. If you do want to work on that, here's an example of a tail-recursive while loop you can test with:
; Evaluate an expression repeatedly until it returns something falsy.
( (lambda (f body) (f f body))
(lambda (f body)
(if (body)
(f f body)
#f))
(lambda () ___)) ; insert expression here