Concise functions, Nonexistent lambdas, Explicit tail calls
On Tue, Dec 9, 2008 at 2:19 AM, Michael Day <mikeday at yeslogic.com> wrote:
Hi,
This proposal consists of three ideas for concise functions, nonexistent lambdas, and explicit tail calls that go well together. It supersedes any previous proposals I may have made on these subjects :)
CONCISE FUNCTIONS
(1) Treat "fun" as a keyword that is exactly equivalent to the existing "function" keyword used in function expressions and declarations.
This will break existing code: www.google.com/codesearch?q=lang%3Ajavascript+"var+fun"&hl=en&btnG=Search+Code
ADVANTAGES OF CONCISE FUNCTIONS
Both changes are very easy to implement and should be compatible with top-down parsers. The two changes combine to allow very concise function declarations, while still preserving the syntactic feel of JavaScript.
As a bonus, any future additions to expressions, such as comprehension expressions or other control structures, will be immediately usable in expression function bodies.
The benefit seems vanishingly small. I don't think it's enough to cover the (admittedly minor) cost in language complexity.
One of the claimed advantages of the lambda proposal is that it would reduce complexity (of one kind) by allowing most of the language to be understood in terms of a small kernel language. Then again, complexity comes in many flavors, and some users will be confused by unfamiliar additions. Lambda could be introduced only as a specification fiction (like the reviled "activation object"). But it's useful.
NONEXISTENT LAMBDAS [...]
Refraining from adding a new lambda construct will make JavaScript easier to specify...
If you're right about this, I'd consider it a powerful argument against the lambda proposal. It's not obvious, however.
This will break existing code: www.google.com/codesearch?q=lang%3Ajavascript+"var+fun"&hl=en&btnG=Search+Code
As will "lambda": www.google.com/codesearch?hl=en&lr=&q=lang%3Ajavascript+"var+lambda"&sbtn=Search
Or practically any other keyword we can think of. So this problem exists for many of the proposed syntactic extensions to JavaScript. Is there any way other than opt-in to introduce to new keywords without breaking existing code?
The benefit seems vanishingly small. I don't think it's enough to cover the (admittedly minor) cost in language complexity.
Mozilla already has expression comprehensions, albeit without the parentheses, so this aspect can be evaluated now.
Refraining from adding a new lambda construct will make JavaScript easier to specify...
If you're right about this, I'd consider it a powerful argument against the lambda proposal. It's not obvious, however.
Everything currently in the specification describing functions will still need to be there, even if some of it is rewritten to be expressed in terms of lambdas. On top of that, lambdas will need to be described. This will make the spec longer, and have more constructs that need to be understood. And I'm not convinced that describing functions in terms of lambdas makes them easier for implementors to understand than just describing their behaviour directly.
Best ,
Michael
On Tue, Dec 9, 2008 at 5:42 PM, Michael Day <mikeday at yeslogic.com> wrote:
Hi Jon,
This will break existing code:
www.google.com/codesearch?q=lang%3Ajavascript+"var+fun"&hl=en&btnG=Search+Code
As will "lambda": www.google.com/codesearch?hl=en&lr=&q=lang%3Ajavascript+"var+lambda"&sbtn=Search
Or practically any other keyword we can think of. So this problem exists for many of the proposed syntactic extensions to JavaScript. Is there any way other than opt-in to introduce to new keywords without breaking existing code?
Aside from picking really odd keywords? I don't think so. That's why people have been discussing the use of non-identifier ASCII punctuation.
The benefit seems vanishingly small. I don't think it's enough to cover the (admittedly minor) cost in language complexity.
Mozilla already has expression comprehensions, albeit without the parentheses, so this aspect can be evaluated now.
JS also has a more powerful expression language than ES, so it wouldn't be an entirely accurate evaluation. It could be that Harmony will adopt many of the JS additions, though.
Refraining from adding a new lambda construct will make JavaScript easier to specify...
If you're right about this, I'd consider it a powerful argument against the lambda proposal. It's not obvious, however.
Everything currently in the specification describing functions will still need to be there, even if some of it is rewritten to be expressed in terms of lambdas. On top of that, lambdas will need to be described. This will make the spec longer, and have more constructs that need to be understood.
Harmony almost certainly won't use the pseudocode specification style of current ES specs. So, I have no idea how long the spec will be. I do know, however, that having more things to describe does not necessarily entail a longer text, and I also know that length and complexity don't have as simple a relation to one another as you seem to imply.
And I'm not convinced that describing functions in terms of lambdas makes them easier for implementors to understand than just describing their behaviour directly.
What does it mean to describe their behavior "directly"? The current ES specifications use a certain style of pseudo-assembly, along with a host of fictional entities, attributes, &c. That is to say, they use a certain ad-hoc language that may or may not reflect the structure of an actual implementation. How is a description in this language any more direct than a description in an extended lambda calculus? They're both specification languages, only the latter is far better understood.
On Dec 9, 2008, at 4:15 PM, Jon Zeppieri wrote:
On Tue, Dec 9, 2008 at 5:42 PM, Michael Day <mikeday at yeslogic.com>
wrote:Or practically any other keyword we can think of. So this problem
exists for many of the proposed syntactic extensions to JavaScript. Is there
any way other than opt-in to introduce to new keywords without breaking
existing code?Aside from picking really odd keywords? I don't think so. That's why people have been discussing the use of non-identifier ASCII punctuation.
Opt-in versioning was required for let and yield in JS1.7 -- it's a
fait accompli.
The benefit seems vanishingly small. I don't think it's enough to cover the (admittedly minor) cost in language complexity.
Mozilla already has expression comprehensions, albeit without the parentheses, so this aspect can be evaluated now.
JS also has a more powerful expression language than ES, so it wouldn't be an entirely accurate evaluation. It could be that Harmony will adopt many of the JS additions, though.
I wasn't sure whether "expression comprehensions" meant expression
closures:
function hi() "there";
or array comprehensions:
return [i*i for (i in nat(N))];
Everything currently in the specification describing functions will
still need to be there, even if some of it is rewritten to be expressed
in terms of lambdas. On top of that, lambdas will need to be described. This
will make the spec longer, and have more constructs that need to be
understood.Harmony almost certainly won't use the pseudocode specification style of current ES specs. So, I have no idea how long the spec will be. I do know, however, that having more things to describe does not necessarily entail a longer text, and I also know that length and complexity don't have as simple a relation to one another as you seem to imply.
The relations are not simple. But I have to say that the lambda-coded
for loop examples:
were not what I would call clear specifications -- at least not to the
audience of JS implementors working in C++ or a similar language, and
not experienced lambda-coders.
I wasn't sure whether "expression comprehensions" meant expression closures:
function hi() "there";
Oops, yes, I meant expression closures, although array comprehensions are also cool :)
were not what I would call clear specifications -- at least not to the audience of JS implementors working in C++ or a similar language, and not experienced lambda-coders.
Perhaps we can separate these two proposals:
- using the lambda calculus to specify JavaScript
and
- adding a new "lambda" construct to the language
My proposal was not to add a new lambda construct to the language, but that wouldn't prevent the use of the lambda calculus as a specification tool if it was felt to be desirable.
Other proposals have suggested adding lambda constructs to the language with various syntactic choices, but do not require the use of the lambda calculus in the specification; the existing pseudo-code approach would still work to specify their behaviour.
Since the two uses of lambda are quite different and independent we need to be clear which one we mean when we talk about "lambda in JavaScript".
On Tue, Dec 9, 2008 at 7:25 PM, Brendan Eich <brendan at mozilla.com> wrote:
The relations are not simple. But I have to say that the lambda-coded for loop examples: esdiscuss/2008-October/007822 were not what I would call clear specifications -- at least not to the audience of JS implementors working in C++ or a similar language, and not experienced lambda-coders.
Those were encodings of a for loop that binds the variables in its initialization expression on every iteration. It's not surprising that it would be complicated to take a user's "i++" and, essentially, turn it into "rebind i with i + 1." It's also not polite. Desugaring a normal 'for' loop is straightforward. (Well, getting the completion value right introduces a bit of oddness, but not much.)
for (initExpr; condExpr, updateExpr) body; ==>
{ initExpr;
let $loop = lambda($v) { if (condExpr) { let $v0 = (lambda() { body; })(); // get the completion value of body updateExpr; $loop($v0); } else { $v; } };
$loop(<emptyCompletionValue>); }
On Dec 9, 2008, at 5:54 PM, Jon Zeppieri wrote:
On Tue, Dec 9, 2008 at 7:25 PM, Brendan Eich <brendan at mozilla.com>
wrote:The relations are not simple. But I have to say that the lambda- coded for loop examples: esdiscuss/2008-October 007822.html were not what I would call clear specifications -- at least not to
the audience of JS implementors working in C++ or a similar language,
and not experienced lambda-coders.Those were encodings of a for loop that binds the variables in its initialization expression on every iteration. It's not surprising that it would be complicated to take a user's "i++" and, essentially, turn it into "rebind i with i + 1."
You're right, that was an extra complication. But something like it
will come up with for (let x in o), even if we leave the for(let x
= ...;;) loop binding semantics var-like. There's strong demand for a
fresh let binding each time through a for-in or for-each-in loop.
for (initExpr; condExpr, updateExpr) body; ==>
{ initExpr;
let $loop = lambda($v) { if (condExpr) { let $v0 = (lambda() { body; })(); // get the completion value
of body updateExpr; $loop($v0); } else { $v; } };$loop(<emptyCompletionValue>); }
That's not bad, but is it the best spec to actual and likely JS
implementors? I don't know, I'm asking. Obviously I'm game, since the
ES4 Reference Implementation was in SML, and so used tail recursion
for looping. But it did not exhibit the aggressive TCP application
that's supported by Dave's lambdas proposal.
We never got every TC39 browser-based JS implementor on board with the
use of SML in the ES4 RI. We should discuss this again before going
too far down any road.
On Tue, Dec 9, 2008 at 10:22 PM, Brendan Eich <brendan at mozilla.com> wrote:
On Dec 9, 2008, at 5:54 PM, Jon Zeppieri wrote:
Those were encodings of a for loop that binds the variables in its initialization expression on every iteration. It's not surprising that it would be complicated to take a user's "i++" and, essentially, turn it into "rebind i with i + 1."
You're right, that was an extra complication. But something like it will come up with for (let x in o), even if we leave the for(let x = ...;;) loop binding semantics var-like. There's strong demand for a fresh let binding each time through a for-in or for-each-in loop.
Since there is no updateExpr to worry about, that isn't a problem. The real problem with for/in is that the set of property names can change under you as the loop executes. Since the language doesn't define a way to get a 'cursor' into an object's keys, I'm making it up:
for (let x in o) body; ==>(with fresh x per iteration)
$_FOR_IN: { let $loop = lambda(x, $v) { if (x) { let $v0 = (lambda() { $_FOR_IN_BODY: { body; } })(); $loop(Object.getNextKey(0, x), $v0); } else { $v; } };
$loop(Object.getNextKey(o, null), <empty>); }
... where the fictional Object.getNextKey(o, null) returns the first key in o.
Something I omitted from the previous example: 'break' and 'continue' in body need to be rewritten. break; ==> return : $_FOR_IN $v; continue; ==> return : $_FOR_IN_BODY $v;
Obviously, that's not the whole story. There could be labeled breaks or continues already there, and 'body' can contain its own nested loops, functions, &c. I'm still a bit fuzzy on the 'break' and 'continue' rewriting rules. Dave?
On Dec 9, 2008, at 8:59 PM, Jon Zeppieri wrote:
Since there is no updateExpr to worry about, that isn't a problem. The real problem with for/in is that the set of property names can change under you as the loop executes.
You're guaranteed not to see ids deleted after the loop started. The
spec leaves undefined whether you see added names. Real
implementations that I know do not show added names.
Enumeration order is also unspecified. The big issue among
implementors I talk to is whether only Arrays, or all objects with
indexed properties, use index order rather than insertion order. I'm
increasingly in favor of index order, which almost always matches
insertion order. Where there's no agreement among browsers (e.g., for
an array with named and indexed properties), we could hope to
standardize on a specific total order.
For JS1.7+ and (I hope) Harmony, for-in constructs are built on a
Pythonic iteration protocol, likewise for-each-in (just using a
different iterator). Everything, arrays, DOM nodelists, objects
representing various kinds of collections, could have an iterator
hook (name TBD, iter is the Python name). Calling it gets you the
iterator for that object (iterators return themselves). An iterator
has only a .next() method and throws StopIteration (a singleton
exception object) to stop iteration.
Generators (functions that yield, as in Python) are factories for
iterators that resume the function at the entry point or after the
last yield when .next() is called. It's actually easier to model for-
in and for-each-in as generator-based, and then specify generators
using primitives. The ES4 RI used delimited continuations in SML-NJ,
thanks to Dave Herman.
This was detailed in a couple of ways for ES4, most successfully by
Jason Orendorff (with a patch to the RI), but the fundamental design
doesn't depend on ES4-isms.
I'd like to take a fresh run at strawman:iteration over the holidays.
Thoughts welcome,
This proposal consists of three ideas for concise functions, nonexistent lambdas, and explicit tail calls that go well together. It supersedes any previous proposals I may have made on these subjects :)
CONCISE FUNCTIONS
(1) Treat "fun" as a keyword that is exactly equivalent to the existing "function" keyword used in function expressions and declarations.
(2) A function body may consist of an expression wrapped in parentheses, which is evaluated as the return value of the function.
EXAMPLES OF CONCISE FUNCTIONS
fun()(false) fun(elem) (elem.type == "text") fun(x, y) (x + y) fun(g, h) { g(); return h(); }
ADVANTAGES OF CONCISE FUNCTIONS
Both changes are very easy to implement and should be compatible with top-down parsers. The two changes combine to allow very concise function declarations, while still preserving the syntactic feel of JavaScript.
As a bonus, any future additions to expressions, such as comprehension expressions or other control structures, will be immediately usable in expression function bodies.
NONEXISTENT LAMBDAS
(1) Do not add "lambda" as a keyword and do not add any new lambda construct to the language.
EXAMPLES OF NONEXISTENT LAMBDAS
None, as they do not exist.
ADVANTAGES OF NONEXISTENT LAMBDAS
Nonexistent lambdas are already implemented in all the major JavaScript implementations, and have been in JavaScript since forever and do not require any further changes to the ECMA specifications.
Refraining from adding a new lambda construct will make JavaScript easier to specify, easier to implement, easier to teach and learn.
JavaScript already has functions as first-class values, and concise functions greatly reduce the syntactic overhead of using them, to the point where there is nothing to gain by introducing a new construct.
EXPLICIT TAIL CALLS
(1) Implementations should treat any ReturnStatement whose expression is a CallExpression as a tail call, except when the ReturnStatement is within a WithStatement or within a TryStatement.
Note: This does not cover tail calls in expressions, but implementations could at their option treat certain calls as tail calls within the body of function expressions. For example:
fun() (f(), g()) // <-- g could be a tail call
fun(f, g) (f() || g()) // <-- g could be a tail call
fun(x, f, g) (x ? f() : g()) // <-- f and g could be tail calls
EXAMPLES OF EXPLICIT TAIL CALLS:
fun f() { return g(); // <-- tail call! }
fun f() { g(); // <-- not a tail call, no "return" keyword }
fun f(x) { with (x) { return g(); // <-- not a tail call, inside 'with' } }
ADVANTAGES OF EXPLICIT TAIL CALLS
Very easy to specify and very easy to implement.
It makes tail calls explicit, and explicit tail calls help preserve correctness of code that depends upon them.
Best ,
Michael
Hi, This proposal consists of three ideas for concise functions, nonexistent lambdas, and explicit tail calls that go well together. It supersedes any previous proposals I may have made on these subjects :) CONCISE FUNCTIONS (1) Treat "fun" as a keyword that is exactly equivalent to the existing "function" keyword used in function expressions and declarations. (2) A function body may consist of an expression wrapped in parentheses, which is evaluated as the return value of the function. EXAMPLES OF CONCISE FUNCTIONS fun()(false) fun(elem) (elem.type == "text") fun(x, y) (x + y) fun(g, h) { g(); return h(); } ADVANTAGES OF CONCISE FUNCTIONS Both changes are very easy to implement and should be compatible with top-down parsers. The two changes combine to allow very concise function declarations, while still preserving the syntactic feel of JavaScript. As a bonus, any future additions to expressions, such as comprehension expressions or other control structures, will be immediately usable in expression function bodies. NONEXISTENT LAMBDAS (1) Do not add "lambda" as a keyword and do not add any new lambda construct to the language. EXAMPLES OF NONEXISTENT LAMBDAS None, as they do not exist. ADVANTAGES OF NONEXISTENT LAMBDAS Nonexistent lambdas are already implemented in all the major JavaScript implementations, and have been in JavaScript since forever and do not require any further changes to the ECMA specifications. Refraining from adding a new lambda construct will make JavaScript easier to specify, easier to implement, easier to teach and learn. JavaScript already has functions as first-class values, and concise functions greatly reduce the syntactic overhead of using them, to the point where there is nothing to gain by introducing a new construct. EXPLICIT TAIL CALLS (1) Implementations should treat any ReturnStatement whose expression is a CallExpression as a tail call, except when the ReturnStatement is within a WithStatement or within a TryStatement. Note: This does not cover tail calls in expressions, but implementations could at their option treat certain calls as tail calls within the body of function expressions. For example: fun() (f(), g()) // <-- g could be a tail call fun(f, g) (f() || g()) // <-- g could be a tail call fun(x, f, g) (x ? f() : g()) // <-- f and g could be tail calls EXAMPLES OF EXPLICIT TAIL CALLS: fun f() { return g(); // <-- tail call! } fun f() { g(); // <-- not a tail call, no "return" keyword } fun f(x) { with (x) { return g(); // <-- not a tail call, inside 'with' } } ADVANTAGES OF EXPLICIT TAIL CALLS Very easy to specify and very easy to implement. It makes tail calls explicit, and explicit tail calls help preserve correctness of code that depends upon them. Best regards, Michael -- Print XML with Prince! http://www.princexml.com