Basic Lambdas and Explicit Tail Calls Repackaged

Michael Day mikeday at
Sun Dec 7 01:10:49 PST 2008


I thought it might be good to package these two proposals together, as 
they are interrelated.

It would be very much appreciated if anyone could point out major use 
cases that these proposals don't cover, or any other important issues 
that they might currently neglect.


Lambdas are similar to functions, but use the "lambda" keyword instead 
of "function", always have a "this" value of "undefined", and do not 
have an "arguments" object in scope.


var x = lambda(n) { return n + 1 }

var x = lambda fact(n) {
     if (n <= 1)
         return 1;
         return n * fact(n-1);


The JavaScript specification should require implementations to
treat any ReturnStatement containing a CallExpression as a tail call, 
except in cases when the ReturnStatement is within a WithStatement or 
within a TryStatement.


function f()
     return g(); // <-- tail call!

function f()
     g(); // <-- not a tail call, no "return" keyword

function f(x)
     with (x)
         return g(); // <-- not a tail call, inside with

ADVANTAGE: Very easy to specify and very easy to implement.

It does not require tail calls for CallExpressions which occur outside
of a ReturnStatement, eliminating a big chunk of specification devoted
to figuring out exactly what is or isn't a tail call position.

It does not require scanning through a function to identify tail
positions, so even the most basic interpreter operating directly on
abstract syntax trees could still implement them easily.

ADVANTAGE: It makes tail calls explicit.

Using "return f()" is as close as you can get to introducing a new
keyword, without introducing a new keyword. It makes it immediately
obvious whether a call is a tail call or not. EIBTI.

ADVANTAGE: Explicit tail calls preserve correctness.

The only point of requiring tail call optimisation rather than leaving
it optional is because the correctness of some code depends upon it.
However, implicit tail calls are easily lost as code changes. Consider a
tail call within a deeply nested block:

function f()
     if (cond)
         if (cond)
             g(); // <-- supposed to be a tail call, but is it?

     minorCleanup(); // <-- oh no! someone added this!

If tail calls use an explicit return, it is much harder to accidentally
break them, or overlook them. If tail calls are essential to ensure the
correctness of some code, they should be explicit in that code.

NOTE: Does not preclude fancier optimisations.

Implementations would be required to treat return calls as tail calls.
However, they would be free to treat other calls as tail calls as well,
or perform more complex optimisations such as introducing accumulator
arguments to transform code into tail-recursive form.

Best regards,


Print XML with Prince!

More information about the Es-discuss mailing list