Discuss
  • Basic Lambdas and Explicit Tail Calls Repackaged

Basic Lambdas and Explicit Tail Calls Repackaged

# Michael Day (17 years ago)

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.

BASIC LAMBDAS

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.

LAMBDA EXAMPLES:

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

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

EXPLICIT TAIL CALLS

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.

TAIL CALL EXAMPLES:

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 ,

Michael

# Eugene Lazutkin (17 years ago)

Is your lambda proposal competing with strawman:lambdas (gave me by Brendon)?

Another question: the only difference between lambda and function is:

// pseudo code this = undefined; delete arguments;

Why would anybody want to use a lambda instead of a function? 2 characters less to type? What is the compelling reason, the super idea behind the lambda besides confusing programmers, and more things to implement by compiler writers?

Thanks,

Eugene

# Michael Day (17 years ago)

Is your lambda proposal competing with strawman:lambdas (gave me by Brendon)?

It is a different proposal, I think it helps to have more than one proposal, in order to clearly see the different trade offs involved.

Why would anybody want to use a lambda instead of a function? 2 characters less to type? What is the compelling reason, the super idea behind the lambda besides confusing programmers, and more things to implement by compiler writers?

Well, that's a really good question, as lambdas don't sound sufficiently different to regular functions in this proposal to be worth doing.

The lambda proposal on the wiki gives the following "Why" reasons:

"A simpler primitive underlying the language’s first-class functions."

Removing 'this' and 'arguments' also gives a simpler primitive, but is it enough to bother with?

"Supports defining other features via desugaring without breaking equivalence with implicit features (arguments, this, return) — this is sometimes described as Tennent’s Correspondence Principle [ 1, 2 ]."

Not clear what this means, or what benefit it brings to either JavaScript programmers or implementors.

"A well-tested feature of programming languages since time immemorial."

JavaScript already has higher-order functions, and much fewer languages have lambdas where a return returns from the enclosing function.

"Supports tail calls more naturally than function."

I don't see what's unnatural about explicit tail calls in functions.

"Simple, composable features like lambda are useful for other language features defined via desugaring/compiling other languages to ES/macros"

What do lambdas in the wiki have that lambdas-as-functions-without-this do not have? They seem to have more complexity, but I can't see how they are significantly more useful.

Best ,

Michael

# Eugene Lazutkin (17 years ago)

I agree with you: lambdas in strawman:lambdas look useless too. They don't have a clearly articulated vision nor compelling use cases (at least not in the document).

I am for the lambda facility as a short notation for small functional snippets, but both proposals do nothing for this use case. So far it all looks like "lambdas are cool --- we can do lambdas too!" kind of exercise.

Thanks,

Eugene

# Michael Day (17 years ago)

I agree with you: lambdas in strawman:lambdas look useless too. They don't have a clearly articulated vision nor compelling use cases (at least not in the document).

Right, can anyone clarify this? Is there a summary anywhere stating exactly why lambdas are needed in JavaScript and which use cases they are intended to satisfy?

# Brendan Eich (17 years ago)

On Dec 7, 2008, at 9:55 PM, Michael Day wrote:

I agree with you: lambdas in strawman:lambdas look useless too. They don't have a clearly articulated vision nor
compelling use cases (at least not in the document).

Right, can anyone clarify this? Is there a summary anywhere stating
exactly why lambdas are needed in JavaScript and which use cases
they are intended to satisfy?

We started with lambdas as better functions. They evolved due to a
combination of TCP idolatry (sorry, I call it as I see it :-P) and
some preference for Scheme-ish modeling of statements as if they were
part of an expression language (based on completion value precedent
used by eval).

We should back up and reconsider the goals. It seems to me that these
two main goals are in conflict:

  1. Better functions, better meaning no |this| parameter and no
    arguments object, possibly no var. For this item alone, TCP for var,
    return, etc. seems undesirable. We could ban var, and make return
    apply to the immediately enclosing lambda, which would thus not be
    anything comparable to a Smalltalk block.

  2. The ability to desugar existing and future syntax into kernel
    semantics primarily using lambda coding and lexical bindings. As the
    for loop desugarings Mark and David-Sarah worked out demonstrate, this
    item wants var TCP at least, probably the full monty: |this|, return,
    break, continue all apply to the lexically enclosing function, loop,
    switch, etc.

About return, break, and continue, I think Michael Day is onto
something in arguing that TCP loses when it comes to block-bodied
lambdas (if we have such, and we think we should, because the JS
expression language is too weak as Jon Zeppieri colorfully asserts).
What motivates aggressive TCP application is the second goal.

Is it possible to reconcile these goals? I don't think so. If not,
then 1 trumps 2 for a language catering to humans rather than, or
primarily over against, code generator programs or a relatively few
specifications that want to desugar, no matter the loss of clarity or
usability to most hand-coding users of the language. 2 trumps 1 if
it's all about Schemers and GWT or Volta or OpenLaszlo or Skynet :-P.

I say 1 trumps 2 for the reason given in the last paragraph: human
programmers first, meaning the fat bell curve (sorry, Schemers).

# Michael Day (17 years ago)

I say 1 trumps 2 for the reason given in the last paragraph: human programmers first, meaning the fat bell curve (sorry, Schemers).

I agree with this; there are all sorts of clever things that implementors can do that don't necessarily need to be exposed as features in the language standard.

However, as Eugene Lazutkin pointed out, is omitting 'this' and 'arguments' a sufficiently compelling improvement to justify introducing a whole new language construct?

In some cases in strict mode 'this' will be undefined instead of being the global object, does this come close enough to omitting 'this' for functions which are not methods?

Best ,

Michael

# Brendan Eich (17 years ago)

On Dec 7, 2008, at 1:10 AM, Michael Day wrote:

Hi,

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.

BASIC LAMBDAS

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.

If the lambda is enclosing in a function, is that function's arguments
binding visible in the lambda body? Probably you meant to allow outer
arguments to be unshadowed, not somehow censored, but I thought I'd ask.

Same question for |this| could be asked (never mind an enclosing
function, since |this| is bound in global code), although Mark had an
argument against lexical |this| for classes as sugar -- but that
argument may not bear on lambdas.

LAMBDA EXAMPLES:

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

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

How about var in lambda? Allowed, or banned in favor of let or const?

EXPLICIT TAIL CALLS

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.

The ReturnStatement's Expression (if present) must be a
CallExpression, not just contain one, of course. Just picking nits ;-).

I like your thinking here, on both lambdas and tail calls.

# Brendan Eich (17 years ago)

On Dec 7, 2008, at 11:43 PM, Michael Day wrote:

Hi Brendan,

I say 1 trumps 2 for the reason given in the last paragraph: human
programmers first, meaning the fat bell curve (sorry, Schemers).

I agree with this; there are all sorts of clever things that
implementors can do that don't necessarily need to be exposed as
features in the language standard.

However, as Eugene Lazutkin pointed out, is omitting 'this' and
'arguments' a sufficiently compelling improvement to justify
introducing a whole new language construct?

I believe this is Waldemar's view too, which along with his objection
to the completion-value hazard leads to the "improve functions through
strict mode or a new version" approach.

There's a lesser goal I didn't list: make function syntax thinner.
'function' is eight whole letters, plus four chars of parens and
braces, plus 'return'. Wherefore expression closures in JS1.8 -- they
save the braces and 'return' overhead. But to fix expression closures
to be bottom-up unambiguous we would require at least parens around
the body-expression.

More concise function syntax is not a goal solely, or even
exclusively, to support user-defined control abstractions. It's a good
in its own right unless you consider every use of a function
expression in JS today to be a control abstraction in the Smalltalk
block sense (I do not).

In some cases in strict mode 'this' will be undefined instead of
being the global object, does this come close enough to omitting
'this' for functions which are not methods?

Not really -- strict mode does not change the ability of |this| to be
rebound in the absence of Function.prototype.bind usage, which has its
costs, and which apart from overhead in implementation terms, takes
too long to say in the language to be likely as a default practice.
Sure, Ajax libraries use it well, but it's still observed more in the
breach looking at the whole of "web JS".

# Brendan Eich (17 years ago)

On Dec 7, 2008, at 11:51 PM, Brendan Eich wrote:

More concise function syntax is not a goal solely, or even
exclusively,

Er, I meant non-exclusively.

to support user-defined control abstractions. It's a good in its own
right unless you consider every use of a function expression in JS
today to be a control abstraction in the Smalltalk block sense (I do
not).

In some cases in strict mode 'this' will be undefined instead of
being the global object, does this come close enough to omitting
'this' for functions which are not methods?

Not really -- strict mode does not change the ability of |this| to
be rebound in the absence of Function.prototype.bind usage, which
has its costs, and which apart from overhead in implementation
terms, takes too long to say in the language to be likely as a
default practice. Sure, Ajax libraries use it well, but it's still
observed more in the breach looking at the whole of "web JS".

IOW, without a sugared syntax for bound methods (instance methods in a
class, say), |this| is still dynamically bound depending on call
expression. Passing undefined for some cases does not get rid of the
"which this?" confusion.

I would be surprised if we ever evolved a version that lost the
default this binding whereby

var o = {m: function(){print(this.x);}, x: 42}; o.m();

worked as it does today, without requiring heavy analysis or any
incompatibility. We might someday hope, in the default version, to
censor the global object, if we are lucky. Mark wrote about this
recently in raising the prospect of Harmony being a successor to 3.1- strict, not 3.1.

One mountain at a time...

# Michael Day (17 years ago)

If the lambda is enclosing in a function, is that function's arguments binding visible in the lambda body? Probably you meant to allow outer arguments to be unshadowed, not somehow censored, but I thought I'd ask.

Yes, I meant that activation object for a lambda execution context would not contain an arguments object, such that 10.1.6 and 10.1.8 would only apply to execution contexts for function objects.

Same question for |this| could be asked (never mind an enclosing function, since |this| is bound in global code), although Mark had an argument against lexical |this| for classes as sugar -- but that argument may not bear on lambdas.

Every execution context has a this value, and I assumed that it would be set to 'undefined' when entering a lambda.

How about var in lambda? Allowed, or banned in favor of let or const?

Well, without thinking about it very deeply, I would say that if it's not banned then lambdas are too similar to functions, and not worth introducing at all. So I guess I would say banned :)

The ReturnStatement's Expression (if present) must be a CallExpression, not just contain one, of course. Just picking nits ;-).

Right, that's what I meant :)

(It technically means that one could disable tail calls by wrapping the call in parentheses, but this is a fairly minor issue either way).

# Michael Day (17 years ago)

There's a lesser goal I didn't list: make function syntax thinner. 'function' is eight whole letters, plus four chars of parens and braces, plus 'return'. Wherefore expression closures in JS1.8 -- they save the braces and 'return' overhead. But to fix expression closures to be bottom-up unambiguous we would require at least parens around the body-expression.

Allow "fun" as a shorthand for "function" similar to "var" being a shorthand for "variable", and you can add back the parentheses and still make a saving:

 fun(n) (n + 1)

Actually I think it's a great idea to allow function bodies to be expressions when wrapped in parentheses and blocks when wrapped in braces. It's obvious and consistent with other syntax.

More concise function syntax is not a goal solely, or even exclusively, to support user-defined control abstractions. It's a good in its own right unless you consider every use of a function expression in JS today to be a control abstraction in the Smalltalk block sense (I do not).

Concise syntax is good. When I look at these:

 function ident(args) { body ; return }
 function ident(args) ( expression )

the only way it can be made more concise is by shrinking the "function" keyword. The ident is already optional, as are the args, the return is no burden given that the body is already there, and functions with no body can use expression form instead.

I don't think that you can get much more concise than this without fundamentally changing the nature of JavaScript and its syntax:

 fun(x) {x(1)}
 fun(x) (x + 1)

Adding "fun" to millions of scripts all over the world could also have a powerful subliminal effect on JavaScript programmers, as compared with the way that the "die" command ushered in the extinction of Perl :)

# Michael Day (17 years ago)

I would be surprised if we ever evolved a version that lost the default this binding whereby

var o = {m: function(){print(this.x);}, x: 42}; o.m();

Right, but if it was a lambda instead:

var o = {m: lambda(){print(this.x);}, x: 42}; o.m();

the options are:

  • Capture the 'this' value in scope when the lambda is defined, and use that when the lambda is called.

  • Always return 'undefined' when 'this' is evaluated within a lambda.

  • Any others?

Do either of these policies make lambdas useful language constructs as compared with normal functions?

Michael

# Breton Slivka (17 years ago)

On Mon, Dec 8, 2008 at 6:35 PM, Brendan Eich <brendan at mozilla.com> wrote:

(if we have such, and we think we should, because the JS expression language is too weak as Jon Zeppieri colorfully asserts).

What would it take to make javascript's expressions rich enough to be suitable for use as a lambda body, in opposition to blocks?

# Brendan Eich (17 years ago)

On Dec 8, 2008, at 3:21 AM, Breton Slivka wrote:

On Mon, Dec 8, 2008 at 6:35 PM, Brendan Eich <brendan at mozilla.com>
wrote:

(if we have such, and we think we should, because the JS expression language is
too weak as Jon Zeppieri colorfully asserts).

What would it take to make javascript's expressions rich enough to be suitable for use as a lambda body, in opposition to blocks?

Pretty much what Yuh-Ruey Chen just posted: make loop and if
constructs expressions, a la Algol 68.

We talked about this at the Oslo meeting but more as a funny thought
experiment. No one was seriously proposing it then. It might be
possible to extend the grammar without much trouble, or "rotate" most
statement productions down into the top of the expression grammar.

But is it really worth the trouble? The C heritage, specifically most
JS hackers' training, militates against JS ever being used in the
large as an expression language.

# Brendan Eich (17 years ago)

On Dec 8, 2008, at 12:38 AM, Michael Day wrote:

Hi Brendan,

I would be surprised if we ever evolved a version that lost the
default this binding whereby var o = {m: function(){print(this.x);}, x: 42}; o.m();

Right, but if it was a lambda instead:

var o = {m: lambda(){print(this.x);}, x: 42}; o.m();

the options are:

  • Capture the 'this' value in scope when the lambda is defined, and
    use that when the lambda is called.

This would break the pattern:

C.prototype = { m1: function(){return this.x1}, m2: function(){return this.x2}, ... };

where (new C) is evaluated repeatedly and each instance delegates to
C.prototype but of course |this| in the proto-methods binds to the
directly-referenced instance.

  • Always return 'undefined' when 'this' is evaluated within a lambda.

Would frustrate any use of lambda (fun!) patterned on today's
prototype method templates.

Why shadow an outer |this|?

It would be better to make |this| in a lambda body a static error.

  • Any others?

Do either of these policies make lambdas useful language constructs
as compared with normal functions?

Compared with, or contrasted to?

|this| as a calling-expression-bound leading parameter is an odd duck.
But it's part of the way object oriented JS is written.

Lambda as better function could lose it along with the arguments
object, and people who prefer it would use lexical 'self' variable
binding to make higher-integrity methods (no this jihacking; Mark's
"Look Ma, no this!" post).

If lambdas are too different (TCP to the max) they are probably
hazardous -- attractive nuisances for too many users of the language.

If lambdas are too much like functions, what's the point? We can work
on briefer function syntax.

I think lambdas should not bind |this| in order to avoid dynamic | this| binding hazards without guessing at a single (and likely wrong,
in light of standard JS OOP practices) object to bind unconditionally.

This does not mean an outer |this| would be visible in a lambda's
body, however -- but it could. The choices seem to be:

  1. Let outer |this| be visible in the lambda's body -- "lexical this".

  2. Make |this| in a lambda body a static error.

# P T Withington (17 years ago)

On 2008-12-08, at 12:19EST, Brendan Eich wrote:

But is it really worth the trouble? The C heritage, specifically
most JS hackers' training, militates against JS ever being used in
the large as an expression language.

Are you saying these new dogs are incapable of learning the tricks us
old dogs already know? Sucks to be them. :P

# Brendan Eich (17 years ago)

On Dec 8, 2008, at 9:35 AM, P T Withington wrote:

On 2008-12-08, at 12:19EST, Brendan Eich wrote:

But is it really worth the trouble? The C heritage, specifically
most JS hackers' training, militates against JS ever being used in
the large as an expression language.

Are you saying these new dogs are incapable of learning the tricks
us old dogs already know? Sucks to be them. :P

I said "militates against". We'd be swimming against a tide.

There could be a new tide coming, who knows? We know the JavaSchools
waxed during the last bubble, and after; will they wane now in favor
of SchemeSchools (Matthias Felleisen's curriculum at Northeastern)?

# Yuh-Ruey Chen (17 years ago)

I was also under the impression that since lambdas were lighter functions that would be more efficient in time and/or space.

# Michael Day (17 years ago)

Ruey,

I was also under the impression that since lambdas were lighter functions that would be more efficient in time and/or space.

Is there any optimisation that could be performed for lambdas, but couldn't be performed for normal functions?

For example, it is easy to statically check that a function does not refer to 'this', or 'arguments' (right?) so in theory a function that does not use these features should not have to pay for them.

Functions are mutable objects and could perhaps gain a potential speed boost in some circumstances by being immutable. But that could be achieved by a generic mechanism for making immutable objects, and does not require introducing a new type of function.

Best ,

Michael

# Brendan Eich (17 years ago)

On Dec 9, 2008, at 3:23 AM, Michael Day wrote:

Functions are mutable objects and could perhaps gain a potential
speed boost in some circumstances by being immutable. But that could
be achieved by a generic mechanism for making immutable objects, and
does not require introducing a new type of function.

ES3.1 has Object.freeze, but you have to call it. This is ineffecient
and slightly hazardous, compared to a declarative form that makes an
immutable function from the start. The other advantage, of course, is
better syntactic UI -- sweet sugar. Opinions vary on what's sweet, but

function dontMessWithMe() { ... } Object.freeze(dontMessWithMe);

is not, especially if you do it hundreds of times (because you want
almost all your functions to be immutable).

# Michael Day (17 years ago)

ES3.1 has Object.freeze, but you have to call it. This is ineffecient and slightly hazardous, compared to a declarative form that makes an immutable function from the start. The other advantage, of course, is better syntactic UI -- sweet sugar. Opinions vary on what's sweet, but

I was thinking a new keyword that applied to any declaration would do the trick in a more generic and syntactically sweet way.