Re: Allen's lambda syntax proposal

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Allen's lambda syntax proposal

Lex Spoon-4
On Mon, Dec 1, 2008 at 3:19 PM, Allen Wirfs-Brock
<[hidden email]> wrote:
> Just to clarify some speculation, the syntax I proposed ({||}) was
> solely inspired by Smalltalk and tempered by the parsing realities
> of a C-like syntax.  Any similarities to Ruby constructs are probably
> examples of parallel evolution under similar environmental pressures.
> I suspect that designers of other languages with C-like syntax
> (C# comes to mind with its () => expr "lambda" syntax) did not
> have the experience or goal of using closures to create control
> abstractions (which often requires passing multi-statement closures)
>  and so arrived at a more function-like concise closure syntax.

I can share some history for the => form.  It's disconcerting that
everyone associates it with C#, because they are open about copying
the syntax from Scala.  Scala's designer, Martin Odersky, most
definitely had in mind that people could use functions for control
flow, and in fact he treats it as the primary way to do control flow
in Scala.  I believe Martin got this syntax most directly from ML's
"fn" expressions.  He noticed that you don't really need the keyword.

The development for ML->Scala->C# actually looks a lot like is
happening in ES discussions.  Once a function literal syntax is
available, people really want to use it, and the syntax is pressured
to get shorter and even to get its keyword dropped in favor of
symbols.

On this list, the => form has so far been dismissed due to parsing
concerns.  If that's the only reason, let me try and allay that worry
and put that horse back in the race.  Scala also has a comma operator,
but it still manages to parse the => syntax.  They way it does it is
to initially parse an expression and then, if it sees a =>,
reinterpret what it has seen so far as a parameter list.  It's an
unusual parsing strategy, but it works well and the issue is
localized.

IMHO, x => x+1 really looks like a function literal, so that's the
color I'd paint the bike shed.  I agree with Allen and others, though,
that any version that drops the keyword will make the form more useful
in practice.

-Lex
_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Allen's lambda syntax proposal

Yuh-Ruey Chen
Lex Spoon wrote:
> On this list, the => form has so far been dismissed due to parsing
> concerns.  If that's the only reason, let me try and allay that worry
> and put that horse back in the race.  Scala also has a comma operator,
> but it still manages to parse the => syntax.  They way it does it is
> to initially parse an expression and then, if it sees a =>,
> reinterpret what it has seen so far as a parameter list.  It's an
> unusual parsing strategy, but it works well and the issue is
> localized.
>  

I don't think anyone is suggesting that it would be too difficult to
parse for bottom-up parsers. It's just that it makes it difficult for a
certain common class of bottom-up parsers, namely the LALR(k) for fixed
k parser generators, to parse.

Personally, since I'm not responsible for any ES/JS implementation, I
don't care about this difficulty, but a quick search for "ecmascript
lalr" reveals that there are such existing parsers.

P.S. Take everything I say with a grain of salt, since I'm not really an
expert on parsing.
_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Allen's lambda syntax proposal

Lex Spoon-4
On Wed, Dec 17, 2008 at 9:53 PM, Yuh-Ruey Chen <[hidden email]> wrote:

> Lex Spoon wrote:
>> On this list, the => form has so far been dismissed due to parsing
>> concerns.  If that's the only reason, let me try and allay that worry
>> and put that horse back in the race.  Scala also has a comma operator,
>> but it still manages to parse the => syntax.  They way it does it is
>> to initially parse an expression and then, if it sees a =>,
>> reinterpret what it has seen so far as a parameter list.  It's an
>> unusual parsing strategy, but it works well and the issue is
>> localized.
>>
>
> I don't think anyone is suggesting that it would be too difficult to
> parse for bottom-up parsers. It's just that it makes it difficult for a
> certain common class of bottom-up parsers, namely the LALR(k) for fixed
> k parser generators, to parse.

Good point.  Actually, though, the same sort of approach should still
work.  The grammar for a => entry would be something like:

  atomic_expression "=>" atomic_expression

Then, the rule that assembles this parse tree into a real AST would
analyze the expression on the left and either convert it to a parse
tree, or emit a retroactive parse error.

I know this initially violates some design sense--it does
mine!--because normally a parser rule reuses subexpressions without
change.  However, in this case it works out well, and so I think the
rule of thumb is misleading.  This implementation technique should be
simple, localized, easy to understand, and as a result robust.


Lex
_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Allen's lambda syntax proposal

Brendan Eich-3
In reply to this post by Lex Spoon-4
On Dec 17, 2008, at 1:42 PM, Lex Spoon wrote:

I can share some history for the => form.  It's disconcerting that
everyone associates it with C#, because they are open about copying
the syntax from Scala.

It's for Ecma solidarity -- we are indirectly boosting another Ecma standard (C# is ECMA-334, IIRC), albeit at the expense of Scala :-P.

Ok, enough of that (we really do not try to align Ecma language standards, which include Eiffel!). Thanks for the precedent correction.


On this list, the => form has so far been dismissed due to parsing
concerns.  If that's the only reason, let me try and allay that worry
and put that horse back in the race.  Scala also has a comma operator,
but it still manages to parse the => syntax.  They way it does it is
to initially parse an expression and then, if it sees a =>,
reinterpret what it has seen so far as a parameter list.  It's an
unusual parsing strategy, but it works well and the issue is
localized.

I called the => syntax "no-go" for JS in


cites two general arguments.

First, parsing top-down and then revising the AST based on right context is do-able -- but the "This can get ugly" remark is meant to suggest that it's costly compared to choosing a grammar that avoids the ambiguity.

On the plus side, destructuring in JS1.7, proposed for Harmony to broad agreement, requires similar revision:

[p, q] = [q, p];

swaps p and q, but it starts like

[p, q];

(and of course could be nested anywhere an assignment expression could occur).

Let's say we can overcome this objection, by selling the benefit to the users over the cost to implementors (and users, in minor code footprint; slippery slope hazard here, otherwise it's not a big cost). I'm not confident this assumption will hold in committee -- need to get Waldemar's reaction, at least -- but for now let's just say :-).

The second argument is that the issue may not be localized, especially in light of automatic semicolon insertion. A counter-example adapted from the "The trouble with ambiguous grammars" thread:

a => a ? f : x++
(0);

A function expression in JS today is a primary expression, e.g.

var f = function (a) { return a ? f : x++; }
(0);

so lambda users might expect the same precedence.

If the grammar is something like this:

AssignmentExpression:
     ...
|    identifier '=>' AssignmentExpression
|    '(' parameters ')' '=>' AssignmentExpression

(which AFAICT from web C# 3.0 grammars is what C# does) then we may be ok. We'd need to check carefully.

Mono C# seems to have to bend over backwards to parse C# lambdas:


but I don't see why a bottom-up parser can't decide quite late, compared to a top-down parser, that it has a lambda parameter list and not a parenthesized expression.

Perhaps we dismissed the => syntax too quickly, but we need a checked bottom-up grammar. It's not enough to assert locality, unfortunately, given the existing grammar and the complexity of automatic semicolon insertion.

/be

_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Allen's lambda syntax proposal

Dave Herman-2
In reply to this post by Lex Spoon-4
> "^" also has a slight resemblance to the greek lambda, which is the  
> reason Haskell uses "\".

As an aside, the circumflex is actually the precursor to lambda:

"We end this introduction by telling what seems to be the story how  
the letter 'λ' was chosen to denote function abstraction. In Principia  
Mathematica the notation for the function f with f(x) = 2x + 1 is

      ^
     2x + 1.

Church originally intended to use the notation

     ^
     x.2x+1.

The typesetter could not position the hat on top of the x and placed  
it in front of it, resulting in
^x.2x + 1. Then another typesetter changed it into λx.2x + 1."

-- H. Barendregt, The Impact of the Lambda Calculus In Logic and  
Computer Science [1]

Dave

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7908

_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Origins of lambda notation (was: Allen's lambda syntax proposal)

David-Sarah Hopwood
Dave Herman wrote:
> In Principia Mathematica the notation for the function f with f(x) = 2x + 1 is
>
>      ^
>     2x + 1.
[...]
> The typesetter could not position the hat on top of the x and placed it
> in front of it, resulting in ^x.2x + 1.

That's not quite right. In Principia Mathematica, x̂ was used for
class abstraction. For example x̂.x = y or x̂(x = y) would mean the
singleton class, in this case also a set, {y}. Gottlob Frege had
earlier used a half-ring or reversed-c above, e.g. x͗(x = y), for
essentially the same thing [Frege, 1902].

Since this is not the same as functional abstraction (but was similar
in the sense of being a variable-binding operator), Church deliberately
made the change to using a prefix operator; that step was not due to
typesetting considerations. As I posted before,

====
Felice Cardone, J. Roger Hindley,
History of Lambda-calculus and Combinatory Logic
2006, Swansea University Mathematics Department
Research Report No. MRRS-05-06.
<http://www-maths.swan.ac.uk/staff/jrh/papers/JRHHislamWeb.pdf>

# (By the way, why did Church choose the notation "λ"? In [Church, 1964, §2]
# he stated clearly that it came from the notation "x̂" used for
# class-abstraction by Whitehead and Russell, by first modifying "x̂" to
# "∧x" to distinguish function-abstraction from class-abstraction, and
# then changing "∧" to "λ" for ease of printing. This origin was also
# reported in [Rosser, 1984, p.338]. On the other hand, in his later years
# Church told two enquirers that the choice was more accidental: a symbol
# was needed and "λ" just happened to be chosen.)

[Church, 1964] A. Church, 7 July 1964. Unpublished letter to Harald Dickson.

[Rosser, 1984] J. B. Rosser. Highlights of the history of the lambda
calculus. Annals of the History of Computing, 6:337–349, 1984.

[Frege, 1902] G. Frege, 1902. Letter to Russell. Reproduced in
Van Heijenoort, J. From Frege to Gödel: A Source Book in Mathematical
Logic, 1879-1931. AuthorHouse, December 6, 1999. ISBN 158348597X.


[If your email client doesn't display the above correctly:
  "x̂" is an x with a hat operator (similar to a circumflex) above it.
  "x͗" is an x with a reversed 'c', or half-ring open on the left, above it.
  "∧" is an upward-pointing wedge.
  "λ" is a lowercase Greek lambda.]

--
David-Sarah Hopwood

_______________________________________________
Es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss