Discuss
  • Lambda vs. function

Lambda vs. function

# Waldemar Horwat (17 years ago)

Dave Herman wrote:

I don't see enough of a benefit to warrant inclusion of a new lambda concept. It's just another way of doing what local functions can do.

As I see it, the major benefits of `lambda' are

a) introducing a low-level and compositional primitive that is useful for code generation (as a target language for compilers, macros, or other language features defined by desugaring), and

b) creating a clearer place in the language syntax to enforce tail calling by eliminating `return'

I don't understand what you mean in point b.

These needs aren't addressed by `function' and almost certainly can't be.

If there is a bug with local functions, then fix that one instead instead of sowing confusion by having two concepts.

Recall that lambda' does not includereturn', this',var', or arguments'. We're not about to eliminate those fromfunction'! (Nor would I advocate doing so-- even if we could somehow rewrite the entire web.)

Maybe you don't feel that the issues addressed by lambda' are important enough to warrant the new feature, but "just changefunction'" is a not a realistic argument.

Why isn't function a realistic alternative? You cited four differences:

return: Return from within a function returns from that function instead of doing a longjmp. I'd consider that to be a feature.

this: You have a point there.

var: Not an issue if you're not using var inside the lambda. Code generation that wants to use lambda would use var why?

arguments: Again, not an issue if you're not using the arguments array. If a code generator is updated for lambda, then presumably it will be updated not to use the arguments array.

Waldemar
# Dave Herman (17 years ago)

b) creating a clearer place in the language syntax to enforce tail calling by eliminating `return'

I don't understand what you mean in point b.

Consider two different syntaxes for a function performing a tail call:

 lambda(x) { f(x) }
 function(x) { return f(x) }

The traditional semantics of return' is 1) evaluate the argument to get a value and 2) jump to the caller (i.e., pop the stack frame) with that value. If we try to graft tail calls on top ofreturn', we reverse the semantics: 1) jump to the caller with an unevaluated expression and 2) evaluate the subexpression.

But what if the return' occurs in a try-block? Then popping the whole activation frame would be incorrect (it would unwind the exception handler too soon). So now we have to say the semantics ofreturn' depends on its context:

 1) if the `return' is in tail position, then
    1.1) jump to the caller and
    1.2) evaluate the subexpression
 2) if the `return' is not in tail position, then
    1.1) evaluate the subexpression and
    1.2) jump to the caller

You could certainly argue that this is just a syntactic difference for the same behavior as the return'-less form. Butreturn' suggests a control effect, and imperative behavior, and we're messing with its interpretation.

I claim that return' suggests that a function call corresponds to an activation frame (which is in fact the way ES3 is explicitly specified), which is popped after evaluating the argument of areturn' statement. By contrast, a procedure form that does not use `return' simply avoids any suggestion of control effect, and tail calling is a natural interpretation.

To some degree, you could wedge proper tail calling on top of the semantics of function/return. But the notion of what constitutes a tail position is much clearer with lambda.

Why isn't function a realistic alternative? You cited four differences:

return: Return from within a function returns from that function instead of doing a longjmp. I'd consider that to be a feature.

There is no longjmp in ES, nor is longjmp being proposed. Maybe you're mixing semantics with implementation. Or maybe you're making fun of the return-to-label proposal. I don't see what you're driving at. But `return' is a transfer of control; it is a jump. It just happens to be a jump that you don't have to implement in C with longjmp.

this: You have a point there.

var: Not an issue if you're not using var inside the lambda. Code generation that wants to use lambda would use var why?

arguments: Again, not an issue if you're not using the arguments array. If a code generator is updated for lambda, then presumably it will be updated not to use the arguments array.

If you're writing a compiler that targets ES, you can have conventions that avoid using those features. But for defining ES language features by desugaring, we don't have that luxury; for example:

 let (x = e) { s } !== (function(x) { s })(e)

because `s' may contain any of those four features (this, var, arguments, return). This would be a problem for macros, too.

# Brendan Eich (17 years ago)

On Oct 16, 2008, at 1:55 PM, Waldemar Horwat wrote:

var: Not an issue if you're not using var inside the lambda. Code
generation that wants to use lambda would use var why?

arguments: Again, not an issue if you're not using the arguments
array. If a code generator is updated for lambda, then presumably
it will be updated not to use the arguments array.

Why assume that lambda is only for code generators?

# Peter Michaux (17 years ago)

On Thu, Oct 16, 2008 at 3:04 PM, Brendan Eich <brendan at mozilla.com> wrote:

On Oct 16, 2008, at 1:55 PM, Waldemar Horwat wrote:

var: Not an issue if you're not using var inside the lambda. Code generation that wants to use lambda would use var why?

arguments: Again, not an issue if you're not using the arguments array. If a code generator is updated for lambda, then presumably it will be updated not to use the arguments array.

Why assume that lambda is only for code generators?

For hand-written code, I think the combination of "lambda" and "class" have the potential to (almost?) eliminate the need for "function" and its relatively confusing semantics. I've been looking through my code; lambda and even the simplest class (instance private, zero inheritance) would cover almost everything as drop in replacements. A few situations would need very little reworking to use lambda and class and as a result would be better.

Peter

# Waldemar Horwat (17 years ago)

Brendan Eich wrote:

On Oct 16, 2008, at 1:55 PM, Waldemar Horwat wrote:

var: Not an issue if you're not using var inside the lambda. Code generation that wants to use lambda would use var why?

arguments: Again, not an issue if you're not using the arguments array. If a code generator is updated for lambda, then presumably it will be updated not to use the arguments array.

Why assume that lambda is only for code generators?

Just trying to follow Dave Herman's line of reasoning.

Waldemar
# Waldemar Horwat (17 years ago)

Dave Herman wrote:

b) creating a clearer place in the language syntax to enforce tail calling by eliminating `return'

I don't understand what you mean in point b.

Consider two different syntaxes for a function performing a tail call:

lambda(x) { f(x) }
function(x) { return f(x) }

What is your point? To write a recursive factorial I'd write either:

lambda f(x) { if (x == 0) 1; else f(x - 1); }

or:

function f(x) { if (x == 0) return 1; else return f(x - 1); }

Either one is subject to having to jump out of try-catch blocks if you have them. You still have all the same issues of whether f is in the tail position or not.

The traditional semantics of return' is 1) evaluate the argument to get a value and 2) jump to the caller (i.e., pop the stack frame) with that value. If we try to graft tail calls on top ofreturn', we reverse the semantics: 1) jump to the caller with an unevaluated expression and 2) evaluate the subexpression.

But what if the return' occurs in a try-block? Then popping the whole activation frame would be incorrect (it would unwind the exception handler too soon). So now we have to say the semantics ofreturn' depends on its context:

1) if the `return' is in tail position, then
   1.1) jump to the caller and
   1.2) evaluate the subexpression
2) if the `return' is not in tail position, then
   1.1) evaluate the subexpression and
   1.2) jump to the caller

Maybe you're mixing semantics with implementation. They all first evaluate the subexpression and then jump to the caller.

Waldemar
# Dave Herman (17 years ago)

What is your point? To write a recursive factorial I'd write either:

lambda f(x) { if (x == 0) 1; else f(x - 1); }

or:

function f(x) { if (x == 0) return 1; else return f(x - 1); }

Right, good, so far we're on the same page.

Either one is subject to having to jump out of try-catch blocks if
you have them. You still have all the same issues of whether f is
in the tail position or not.

Yes and no. Try-catch does need to be kept in the continuation
regardless of whether we're talking about a tail-recursive function/ return form or a tail-recursive lambda form. But the point is that, if
you want function/return to be properly tail-calling, then in these
two functions:

 function f() {
     try {
         if (test())
             return g();
     }
     catch (e) { }
 }

 function f() {
     if (test())
         return g();
 }

return has different behavior. In the first one, you first evaluate
g() and then return. In the second one, you first return and then
evaluate g(). By contrast, if you write these in lambda-style, you get:

 lambda f() {
     try {
         if (test())
             g()
     }
     catch (e) { }
 }

 lambda f() {
     if (test())
         g()
 }

Now there's no question about any control effect. And just to drive
home the point that `return' is indeed a control effect, imagine the
same function where the try-block isn't even the last statement in the
block:

 function f() {
     try {
         if (test())
             return g();
     }
     catch (e) { }
     h();
 }

There isn't even a straightforward translation to lambda style[*]
without some kind of jumps! This is where return-to-label comes in:

 lambda f() {
     abort: {
         try {
             if (test())
                 return :abort g();
         }
         catch (e) { }
         h();
     }
 }

Now, because return :exit g() first evaluates g() before returning,
this is not a tail call to g(). So when you use return, you don't get
tail calls. But it means you have one consistent semantics for
return: it always evaluates its argument before performing its control
effect. That means function/return isn't properly tail calling, but by
default `lambda' is.

They all first evaluate the subexpression and then jump to the caller.

No, they don't. Not if you are trying to implement properly tail- calling `return'. That's the point.

Dave

[*] Short of CPS, which is precisely a lambda-encoding of jumps. But
it's a non-local transformation, which is both anti-modular and bad
for readability.

# Waldemar Horwat (17 years ago)

Dave Herman wrote:

What is your point? To write a recursive factorial I'd write either:

lambda f(x) { if (x == 0) 1; else f(x - 1); }

or:

function f(x) { if (x == 0) return 1; else return f(x - 1); }

Right, good, so far we're on the same page.

Either one is subject to having to jump out of try-catch blocks if you have them. You still have all the same issues of whether f is in the tail position or not.

Yes and no. Try-catch does need to be kept in the continuation regardless of whether we're talking about a tail-recursive function/return form or a tail-recursive lambda form. But the point is that, if you want function/return to be properly tail-calling, then in these two functions:

function f() {
    try {
        if (test())
            return g();
    }
    catch (e) { }
}

function f() {
    if (test())
        return g();
}

return has different behavior. In the first one, you first evaluate g() and then return. In the second one, you first return and then evaluate g(). By contrast, if you write these in lambda-style, you get:

lambda f() {
    try {
        if (test())
            g()
    }
    catch (e) { }
}

lambda f() {
    if (test())
        g()
}

Now there's no question about any control effect.

Again, what is your point? The first function f behaves the same way as the first lambda f, so what is the advantage you're claiming for lambda? What you appear to be saying is that wrapping the call to g() inside another statement indicates that it will not be tail-recursive. In that case what will things like the following do?

lambda h(x) { switch (x) { case 1: g(); break; case 2: ... } }

lambda k(x) { with (x) { g(); } }

lambda i(x) { if (x) { g(); } else { ... } }

lambda l():type1 { g(); // Produces type2 }

All of these wrap the call to g in another statement.

Waldemar
# Dave Herman (17 years ago)

What you appear to be saying is that wrapping the call to g() inside another statement indicates that it will not be tail-recursive.

No, that's not what I'm saying-- that's a given and not relevant.

What I'm trying to say is that trying to make "return" into a tail-calling form is clunky because it makes the control behavior of "return" different in different contexts. A tail return does jump-then-evaluate; a non-tail return does evaluate-then-jump.

By contrast, with a lambda, there's no control effect involved in returning. A function simply returns the result of any expression in tail position-- no jumps in sight. No return, no jump.

# Waldemar Horwat (17 years ago)

Dave Herman wrote:

What you appear to be saying is that wrapping the call to g() inside another statement indicates that it will not be tail-recursive.

No, that's not what I'm saying-- that's a given and not relevant.

OK. You just stated that it's "a given and not relevant" that the factorial lambda example I gave earlier is not tail-recursive:

lambda f(x) { if (x == 0) 1; else f(x - 1); }

That clears things up.

Waldemar
# Dave Herman (17 years ago)

No, I must have misunderstood what you meant by "wrapping the call to
g() inside another statement" -- I thought you were referring to
wrapping it in a context such as

 { -- ; stmt; }

which would obviously not be a tail position. But this:

lambda f(x) { if (x == 0) 1; else f(x - 1); }

would be tail recursive. Let's try to get specific without drowning in
too much detail. Here is a taste of what defines tail position,
written in the style of an attribute grammar:

Expression <- lambda Formals Block Block.tail = true

Statement <- { stmt1; ... ; stmtn; stmt; }

 stmt1.tail = false
 ...
 stmtn.tail = false
 stmt.tail = Statement.tail

Statement <- if expr stmt;

 expr.tail = false
 stmt.tail = Statement.tail

Statement <- if expr stmt1 else stmt2;

 expr.tail = false
 stmt1.tail = Statement.tail
 stmt2.tail = Statement.tail

Statement <- while (expr) stmt

 expr.tail = false
 stmt.tail = false

Do you see where I'm going with this? It's a pretty natural idea. The
branches of an if-statement can be in tail position because they are
the last thing produced by the if-statement. Some things like loop
forms and switch won't be able to contain tail positions because
they're too imperative. But if statements and blocks have a very
natural notion of tail position.

# Waldemar Horwat (17 years ago)

Dave Herman wrote:

Do you see where I'm going with this? It's a pretty natural idea. The branches of an if-statement can be in tail position because they are the last thing produced by the if-statement. Some things like loop forms and switch won't be able to contain tail positions because they're too imperative. But if statements and blocks have a very natural notion of tail position.

Dave

Yes, that's what I was referring to earlier. Do you now understand my mail from 10/17/2008 12:39? There are contexts where things are black and white and there are more gray ones -- switch statements, try/catch, return, type annotated functions, etc.

Waldemar
# Dave Herman (17 years ago)

Yes, that's what I was referring to earlier. Do you now understand my mail from 10/17/2008 12:39?

You mean these examples?

lambda h(x) { switch (x) { case 1: g(); break; case 2: ... } }

I doubt there's any clean way to fit tail positions into a switch statement, since it works by jumping out of the statement. I'll have to look closer at the semantics of the completion value of a switch statement; there might be some reasonably straightforward notion of a tail position. But I doubt it.

Continuing the attribute grammar I described in my 10/17/2008 7:40PM email, the `switch' production would look something like this:

 Statement <- switch (expr) block

     expr.tail = false
     block.tail = false

 CaseClause <- case expr: stmt

     expr.tail = false
     stmt.tail = false

lambda k(x) { with (x) { g(); } }

lambda i(x) { if (x) { g(); } else { ... } }

I overlooked these two examples last time. I believe there's no problem with considering both calls to g tail calls. So we have:

 Statement <- with (expr) stmt

     expr.tail = false
     stmt.tail = Statement.tail

 Statement <- if expr stmt1 else stmt2

     stmt1.tail = Statement.tail
     stmt2.tail = Statement.tail

lambda l():type1 { g(); // Produces type2 }

We haven't nailed down the semantics of type annotations, but if they simply represent dynamic assertions, then the most straightforward semantics is just to say that return-type annotations destroy tail-position. So in this example the call to g would not be in tail position. So the attribute grammar would differentiate lambda expressions depending on whether they were type-annotated:

 Expression <- lambda formals block

     block.tail = true

 Expression <- lambda formals : type block

     block.tail = false

There are contexts where things are black and white and there are more gray ones -- switch statements, try/catch, return, type annotated functions, etc.

It doesn't need to be gray; it just requires that we enumerate the tail positions explicitly and completely. IOW, mandating proper tail calls requires two things from a spec:

  1. Precisely specifying what the tail positions are. This is a syntactic property, not a semantic one (e.g., there's no control flow or dataflow analysis required). A nice way to specify this is with an attribute grammar.

  2. Mandating that subexpressions in tail position be evaluated in exactly the same control context as their parent expression.

Since switch statements, try/catch statements, and type-annotated functions have no tail subexpressions, they are completely exempt from (2). Return statements make the notion of tail position messier, and proper tail calls complicates the semantics of return'. But thelambda' proposal nicely avoids this complication by eliminating `return'.

# Maciej Stachowiak (17 years ago)

On Oct 20, 2008, at 2:23 PM, Dave Herman wrote:

Yes, that's what I was referring to earlier. Do you now understand
my mail from 10/17/2008 12:39?

You mean these examples?

lambda h(x) { switch (x) { case 1: g(); break; case 2: ... } }

I doubt there's any clean way to fit tail positions into a switch statement, since it works by jumping out of the statement. I'll have
to look closer at the semantics of the completion value of a switch statement; there might be some reasonably straightforward notion of a tail position. But I doubt it.

I don't think you can represent tail position in a switch statement
with your "attribute grammar" notion, but it's clear to me that the
statement immediately before a break statement, or else the last
statement in the last case or default clause, is in tail position.
There is no reason this should be any different than the if/else case.

, Maciej

# Waldemar Horwat (17 years ago)

Maciej Stachowiak wrote:

On Oct 20, 2008, at 2:23 PM, Dave Herman wrote:

Yes, that's what I was referring to earlier. Do you now understand my mail from 10/17/2008 12:39?

You mean these examples?

lambda h(x) { switch (x) { case 1: g(); break; case 2: ... } }

I doubt there's any clean way to fit tail positions into a switch statement, since it works by jumping out of the statement. I'll have to look closer at the semantics of the completion value of a switch statement; there might be some reasonably straightforward notion of a tail position. But I doubt it.

I don't think you can represent tail position in a switch statement with your "attribute grammar" notion, but it's clear to me that the statement immediately before a break statement, or else the last statement in the last case or default clause, is in tail position. There is no reason this should be any different than the if/else case.

, Maciej

Of course, if you do that then you're back to what Dave was complaining about: break becomes like return in that it can jump out of various kinds of places. For example:

switch (x) { case 1: { if (x) { g(); break; } h(); break; } case 2: try { h(); break; } finally ... case 3: ... }

Waldemar
# Maciej Stachowiak (17 years ago)

On Oct 21, 2008, at 6:14 PM, Waldemar Horwat wrote:

Maciej Stachowiak wrote:

I don't think you can represent tail position in a switch statement
with your "attribute grammar" notion, but it's clear to me that the
statement immediately before a break statement, or else the last
statement in the last case or default clause, is in tail position.
There is no reason this should be any different than the if/else
case. , Maciej

Of course, if you do that then you're back to what Dave was
complaining about: break becomes like return in that it can jump
out of various kinds of places. For example:

switch (x) { case 1: { if (x) { g(); break; } h(); break; } case 2: try { h(); break; } finally ... case 3: ... }

Breaking out of an if seems non-problematic to me, you could imagine
rewriting all such if statements where everything after it is in an
else clause, and then it would be clear that in case 1 both g() and
h() are in tail position (assuming the switch statement itself is).
However nothing inside a "try" block can be in tail potion since there
is implied control context. That's a problem with "try", though, not
with "switch". Obviously wrapping with "switch" cannot turn a non-tail
position into a tail position.

You could probably define a rigorous transform to apply to a swtich()
statement that turns it into a series of if / else clauses (possibly
duplicating later cases if there is no break) and apply the usual if
rule to that transform to get case statements into the attribute
grammar more formally. For example the above could transform as
something like:

if (x == 1) { if (x) { g(); } else { h(); } } else if (x == 2) { try { h(); finally ... ... // duplicate case 3 assuming there was no break } else if (x == 3) { ... }

Then it's clear that the first two calls can be in tail position but
the third cannot by the usual rules for if(). It doesn't make sense to
treat switch differently just because the syntax is different.

, Maciej

# David-Sarah Hopwood (17 years ago)

Maciej Stachowiak wrote:

On Oct 20, 2008, at 2:23 PM, Dave Herman wrote:

I doubt there's any clean way to fit tail positions into a switch statement, since it works by jumping out of the statement. I'll have
to look closer at the semantics of the completion value of a switch statement; there might be some reasonably straightforward notion of a tail position. But I doubt it.

I don't think you can represent tail position in a switch statement
with your "attribute grammar" notion, but it's clear to me that the
statement immediately before a break statement, or else the last
statement in the last case or default clause, is in tail position.

You mean that these are in tail position iff the switch statement is.

(This is possible to express directly with an attribute grammar, but it is a bit tedious, so I will only work out the details if asked.)

# Dave Herman (17 years ago)

Maciej Stachowiak wrote:

You could probably define a rigorous transform to apply to a swtich() statement that turns it into a series of if / else clauses (possibly duplicating later cases if there is no break) and apply the usual if rule to that transform to get case statements into the attribute grammar more formally.

I've been thinking about this for a few days. I think it wouldn't be wise. The transformation gets complicated by conditional breaks:

 if (p()) break;

or worse, breaks inside of loops:

 L: switch (x) {
     case 1:
         while (p()) {
             ...
             if (q()) break L;
             ...
         }
     ...
 }

This idea of a "break-elimination transformation" is analogous to a CPS-transformation. To implement conditional breaks, you're either going to have to explicitly represent an "escape continuation" as an extra functional argument, or you're going to have to encode some instances of break' with an exception or return-to-label. Even if it works out, it's going to be an awfully complex way to specify the behavior ofswitch'.

To specify tail position, only unconditional breaks would introduce tail positions (otherwise, tail position becomes not a syntactic property but a runtime property). IOW, a statement immediately preceding an unconditional break from a switch block would be in tail position.

But as Waldemar said, this creates an incongruity similar to tail-recursive return': some instances ofbreak' would introduce tail positions, and some wouldn't, leading to different control behavior. Specifically, in the tail-calling cases:

 g(); break;

has the unintuitive behavior of first breaking out of the switch-block and then evaluating g().

Maciej Stachowiak wrote:

I don't think you can represent tail position in a switch statement
with your "attribute grammar" notion, but it's clear to me that the
statement immediately before a break statement, or else the last
statement in the last case or default clause, is in tail position.

You should always be able to express tail position in an attribute grammar; it's an inherited attribute based on the syntactic structure of a program.

David Sarah-Hopwood wrote:

You mean that these are in tail position iff the switch statement is.

(This is possible to express directly with an attribute grammar, but it is a bit tedious, so I will only work out the details if asked.)

What the heck, I gave it a go. :)

 // case clauses inherit information about the switch block
 Statement ::= L: switch (expr) { CaseClause1 ... CaseClausen }
     CaseClause1.insideSwitch = { tail: Statement.tail,
                                  label: L.label }
     ...
     CaseClausen.insideSwitch = { tail: Statement.tail,
                                  label: L.label }

 // unlabelled switch block
 Statement ::= switch (expr) { CaseClause1 ... CaseClausen }
     CaseClause1.insideSwitch = { tail: Statement.tail, label: null }
     ...
     CaseClausen.insideSwitch = { tail: Statement.tail, label: null }

 // case clause bodies inherit information about the switch block
 // a statement immediately preceding an unconditional break is tail
 CaseClause ::= case expr: stmt1 ... stmtn
     stmt1.insideSwitch = CaseClause.insideSwitch
     ...
     stmtn.insideSwitch = CaseClause.insideSwitch
     stmtn-1.tail = CaseClause.insideSwitch.tail &&
                      stmtn.isUnconditionalBreak

 // if it matches the switch label it's an unconditional break
 Statement ::= break L
     Statement.isUnconditionalBreak =
         Statement.insideSwitch &&
           Statement.insideSwitch.tail &&
             L.label == Statement.insideSwitch.label

 // or if it's the default label it's an unconditional break
 Statement ::= break
     Statement.isUnconditionalBreak = true

 // a statement immediately preceding an unconditional break is tail
 Statement ::= { stmt1 ... stmtn }
     stmtn-1.tail = Statement.insideSwitch &&
                      Statement.insideSwitch.tail &&
                        stmtn.isUnconditionalBreak

As I say, I'm not really in favor of this semantics. I think it's too complicated and bifurcates the meaning of `break'. The fact is if you write:

 case 1:
     if (p()) {
         f();
         g();
         break;
     }
     // fall through
 case 2:

then the call to g() is in tail position, but the break' is inarguably a jump. Put differently, theswitch' construct is inherently imperative (just ask Tom Duff!). A more functional multiple-case dispatch form would be like Scheme's cond' or ML/Haskellcase'. God, we need macros.

# Maciej Stachowiak (17 years ago)

On Oct 27, 2008, at 6:46 AM, Dave Herman wrote:

Maciej Stachowiak wrote:

You could probably define a rigorous transform to apply to a
swtich() statement that turns it into a series of if / else clauses
(possibly duplicating later cases if there is no break) and apply
the usual if rule to that transform to get case statements into the
attribute grammar more formally.

I've been thinking about this for a few days. I think it wouldn't be
wise. The transformation gets complicated by conditional breaks:

if (p()) break;

I don't see why that is complicated. In this literal example, nothing
is in tail position. There is no statement immediately before the
break. In the case of:

if (p()) { q(); break; }

It's equally clear that q() is in tail position.

or worse, breaks inside of loops:

L: switch (x) { case 1: while (p()) { ... if (q()) break L; ... } ... }

This idea of a "break-elimination transformation" is analogous to a
CPS-transformation. To implement conditional breaks, you're either
going to have to explicitly represent an "escape continuation" as an
extra functional argument, or you're going to have to encode some
instances of `break' with an exception or return-to-label.

I was thinking only of the simple case of breaks directly from the
switch statement (not from a nested loop or a loop more generally)

Even if it works out, it's going to be an awfully complex way to
specify the behavior of `switch'.

To specify tail position, only unconditional breaks would introduce
tail positions (otherwise, tail position becomes not a syntactic
property but a runtime property). IOW, a statement immediately
preceding an unconditional break from a switch block would be in
tail position.

I'd say a break statement that's the sole statement in the "then" or
"else" clause of an if statement should not be thought of as a
"conditional break" but rather as equivalent to a "then" clause that's
a block containing only a break statement; no statement precedes the
break in the same block in that case, so the break does not create any
tail positions.

But as Waldemar said, this creates an incongruity similar to tail- recursive return': some instances ofbreak' would introduce tail
positions, and some wouldn't, leading to different control behavior.

Some instances of an if statement introduce tail positions and others
do not. Some instances of a function call expression statement
introduce tail positions and others do not. Why is this more
problematic in the case of "return" or "break"? In any of these cases,
a seeming tail position may fail to be one because it is followed by
an exit from observable control context.

Specifically, in the tail-calling cases:

g(); break;

has the unintuitive behavior of first breaking out of the switch- block and then evaluating g().

Since the difference cannot be observed (other than through growth of
the control stack), I don't see that it really matters which is done
first. Otherwise, many common compiler optimizations (instruction
scheduling, common subexpression elimination, load/store hoisting...)
are uninituitive by the same standard.

Maciej Stachowiak wrote:

I don't think you can represent tail position in a switch
statement > with your "attribute grammar" notion, but it's clear
to me that the > statement immediately before a break statement,
or else the last > statement in the last case or default clause,
is in tail position.

You should always be able to express tail position in an attribute
grammar; it's an inherited attribute based on the syntactic
structure of a program.

David Sarah-Hopwood wrote:

You mean that these are in tail position iff the switch statement is. (This is possible to express directly with an attribute grammar, but it is a bit tedious, so I will only work out the details if
asked.)

What the heck, I gave it a go. :)

// case clauses inherit information about the switch block Statement ::= L: switch (expr) { CaseClause1 ... CaseClausen } CaseClause1.insideSwitch = { tail: Statement.tail, label: L.label } ... CaseClausen.insideSwitch = { tail: Statement.tail, label: L.label }

// unlabelled switch block Statement ::= switch (expr) { CaseClause1 ... CaseClausen } CaseClause1.insideSwitch = { tail: Statement.tail, label:
null } ... CaseClausen.insideSwitch = { tail: Statement.tail, label:
null }

// case clause bodies inherit information about the switch block // a statement immediately preceding an unconditional break is tail CaseClause ::= case expr: stmt1 ... stmtn stmt1.insideSwitch = CaseClause.insideSwitch ... stmtn.insideSwitch = CaseClause.insideSwitch stmtn-1.tail = CaseClause.insideSwitch.tail && stmtn.isUnconditionalBreak

// if it matches the switch label it's an unconditional break Statement ::= break L Statement.isUnconditionalBreak = Statement.insideSwitch && Statement.insideSwitch.tail && L.label == Statement.insideSwitch.label

// or if it's the default label it's an unconditional break Statement ::= break Statement.isUnconditionalBreak = true

// a statement immediately preceding an unconditional break is tail Statement ::= { stmt1 ... stmtn } stmtn-1.tail = Statement.insideSwitch && Statement.insideSwitch.tail && stmtn.isUnconditionalBreak

As I say, I'm not really in favor of this semantics. I think it's
too complicated and bifurcates the meaning of `break'. The fact is
if you write:

case 1: if (p()) { f(); g(); break; } // fall through case 2:

then the call to g() is in tail position, but the `break' is
inarguably a jump.

I would argue it. You can either equivalently consider the fall
through to be a jump, or say it behaves as if the code of case 2

Put differently, the `switch' construct is inherently imperative
(just ask Tom Duff!).

Correct me if I'm wrong but I don't believe Duff's device works in
ECMAScript, because case labels can't appear in arbitrarily deep
substatements of the switch statement.

A more functional multiple-case dispatch form would be like Scheme's
cond' or ML/Haskellcase'. God, we need macros.

ECMAScript's switch is sort of halfway between Scheme cond and C
switch. Personally I think fall through and explicit break were
unnecessary concessions to C-likeness but I don't think they create
insurmountable problems. Case labels at arbitrary points in the code
would be much worse because it's hard to describe them in any way but
a controlled goto.

, Maciej

# Brendan Eich (17 years ago)

On Oct 27, 2008, at 8:21 AM, Maciej Stachowiak wrote:

A more functional multiple-case dispatch form would be like
Scheme's cond' or ML/Haskellcase'. God, we need macros.

ECMAScript's switch is sort of halfway between Scheme cond and C
switch. Personally I think fall through and explicit break were
unnecessary concessions to C-likeness but I don't think they create
insurmountable problems. Case labels at arbitrary points in the code
would be much worse because it's hard to describe them in any way
but a controlled goto.

Netscape management said that JS had to "look like Java", which
follows C in having fall-through from an upper case to a lower one.
Same as C++. That's a big head-wind to tack against, and I was not
prepared to explain yet another switch statement to Java-heads circa
1995.

As you say, at least we don't have the C/C++ arbitrary case label in
switch body fun. Useful for low-level hacking a la Duff's Device, but
hazardous scaled over a large distribution of programmer ability
(IIRC, comp.risks had an item on an AT&T telephony switch crash in the
late '80s or early '90s that was blamed on a missing break. I can't
find it atm via Google search, which makes me sad; anyone with a
pointer, please mail me).

FWIW, I agree switch can have tail position calls in its cases. That
it is messy to specify, that fall-through makes it irregular, doesn't
seem like enough of a reason to specify no tail call positions in
switch statements.

# Maciej Stachowiak (17 years ago)

On Oct 27, 2008, at 8:21 AM, Maciej Stachowiak wrote:

As I say, I'm not really in favor of this semantics. I think it's
too complicated and bifurcates the meaning of `break'. The fact is
if you write:

case 1: if (p()) { f(); g(); break; } // fall through case 2:

then the call to g() is in tail position, but the `break' is
inarguably a jump.

I would argue it. You can either equivalently consider the fall
through to be a jump, or say it behaves as if the code of case 2

"as if the code of case 2 were duplicated into case 1"

# Breton Slivka (17 years ago)

I don't know if anyone will find this relevant or useful, but in my personal code, I have changed over to completely avoiding the switch statement altogether, in favor of primarily using objects with subscript notation.

instead of

switch(type) { case "big": //do something big break; case "small" //do something small break; }

I would instead

var cases = { big: function (arg) { /* do something big / }, small: function (arg) { / do something small */ } }

var result = (cases[type] ? casestype:"default result";

or, if each case has a lot of repeating code, I simply make an object factoring out the parameters that are different, and use the case as a look up for parameters, and feed them into the boiler plate code once.

The result can be a little less readable unfortunately, but I find it's a bit tidier and succinct- and can also be much more readable if I manage to do it right. Plus, it completely avoids the fall through problem by making it impossible. Tail position might be a bit more clear with this approach as well.

# Breton Slivka (17 years ago)

I would argue it. You can either equivalently consider the fall through to be a jump, or say it behaves as if the code of case 2

"as if the code of case 2 were duplicated into case 1"

  • Maciej

I had a go at combining that concept with my object dispatcher concept, to try and come up with an example of a reasonable transform of a switch statement to a structure with equivalent function that uses (mostly) only lambdas and expressions. The idea here, I hope, may make tail positions more obvious when it comes to switch statements.

so we're transforming this switch statement with fall throughs

switch (switcher) {

case 1: if (p()) { f(); g(); break; } // fall through case 2: while(x) { if(x==y) { break; } } case 3: x += y; break; default: y = x; break; }

to this object dispatcher:

var dispatch = { 1: lambda () { p() ? f(), g() : dispatch2; }, 2: lambda () { while(x) { x==y ? undefined : dispatch3; } }, 3: lambda () { x += y; } } //Implementing default case with a tertiary operator var result = dispatch[switcher] ? dispatchswitcher : y=x;

I've used tertiary operators to replace if/else, since the tertiary operator is an expression form where the tail position is rather obvious and defined. (i think). If there's a lambdified version of the if/else statement, or "while", I would be fascinated.

# David-Sarah Hopwood (17 years ago)

Breton Slivka wrote: [...]

var dispatch = { 1: lambda () { p() ? f(), g() : dispatch2; },

I'm nitpicking, but this is invalid syntax -- due to the relative precedence of comma and ?:, it will be parsed as:

(p() ? f()), (g() : dispatch2);

You want something like

p() ? lambda {f(); g();}() : dispatch2;

(I'm using Mark Miller's proposed syntax for lambda.)

I've used tertiary operators to replace if/else, since the tertiary operator is an expression form where the tail position is rather obvious and defined. (i think). If there's a lambdified version of the if/else statement, or "while", I would be fascinated.

if/else can be desugared to ?: like this:

if (cond) { thenClause } else { elseClause } ==> (cond) ? lambda { thenClause }() : lambda { elseClause }()

if (cond) { thenClause } ==> (cond) ? lambda { thenClause }() : undefined

Note that the tail statement in the selected arm automatically gives the result of the 'if', i.e. this turns the whole 'if/else' into an expression, which is what we want in the case where it is the tail statement of a lambda. In your example, if switcher is 1 and p() is true, then this expansion will make the whole 'switch' evaluate to g().

Ignoring 'break' and 'continue', 'while' can be desugared using tail recursion like this:

while (cond) { body } ==> lambda $loop { if (cond) { { body } $loop(); }();

Here the 'while' statement always evaluates to 'undefined' (when it terminates), which is probably a good idea since there may be zero iterations.

# Dave Herman (17 years ago)

Specifically, in the tail-calling cases:

g(); break;

has the unintuitive behavior of first breaking out of the switch-block and then evaluating g().

Since the difference cannot be observed (other than through growth of the control stack), I don't see that it really matters which is done first. Otherwise, many common compiler optimizations (instruction scheduling, common subexpression elimination, load/store hoisting...) are uninituitive by the same standard.

That's a fair point. I guess I'll stand down on this.

I do want to stress that we're not talking about tail calls as an optimization, but as a requirement of the language. The programmer needs to be able to rely on them, and so it needs to be well-specified exactly where the tail positions are. If that specification is complicated, it could lead to refactoring hazards, and the resulting stack growth (or overflow) could be hard to debug.

I guess my feeling is that the notion of tail position is just cleaner when it doesn't involve control operators like break' andreturn', and that's one of the reasons I like the idea of a lambda' form that doesn't usereturn'.

But I won't argue against having more tail positions in forms like `switch'. So much the better, even if it's messy.

# Maciej Stachowiak (17 years ago)

On Oct 27, 2008, at 11:28 PM, Breton Slivka wrote:

I would argue it. You can either equivalently consider the fall
through to be a jump, or say it behaves as if the code of case 2

"as if the code of case 2 were duplicated into case 1"

  • Maciej

I had a go at combining that concept with my object dispatcher concept, to try and come up with an example of a reasonable transform of a switch statement to a structure with equivalent function that uses (mostly) only lambdas and expressions.

The object dispatcher is a neat trick but not a correct transform of
switch, since switch compares with == rather than by converting to
string like property lookup does.

# Brendan Eich (17 years ago)

On Oct 28, 2008, at 12:18 PM, Maciej Stachowiak wrote:

On Oct 27, 2008, at 11:28 PM, Breton Slivka wrote:

I had a go at combining that concept with my object dispatcher concept, to try and come up with an example of a reasonable transform of a switch statement to a structure with equivalent function that uses (mostly) only lambdas and expressions.

The object dispatcher is a neat trick but not a correct transform of
switch, since switch compares with == rather than by converting to
string like property lookup does.

===, actually.

Another use for Map.

# Peter Michaux (17 years ago)

On Mon, Oct 27, 2008 at 2:34 PM, Breton Slivka <zen at zenpsycho.com> wrote:

I don't know if anyone will find this relevant or useful, but in my personal code, I have changed over to completely avoiding the switch statement altogether, in favor of primarily using objects with subscript notation.

instead of

switch(type) { case "big": //do something big break; case "small" //do something small break; }

I would instead

var cases = { big: function (arg) { /* do something big / }, small: function (arg) { / do something small */ } }

var result = (cases[type] ? casestype:"default result";

or, if each case has a lot of repeating code, I simply make an object factoring out the parameters that are different, and use the case as a look up for parameters, and feed them into the boiler plate code once.

The result can be a little less readable unfortunately, but I find it's a bit tidier and succinct- and can also be much more readable if I manage to do it right. Plus, it completely avoids the fall through problem by making it impossible. Tail position might be a bit more clear with this approach as well.

I do roughly the same thing. Using an object is faster than "switch" also, as far as I recall doing some tests. The speed of switch seems to be the same speed as if-else if-else if-...-else.

I don't think I've ever used "switch" in JavaScript. I do like the semantics of "cond" in Scheme.

Peter

# Maciej Stachowiak (17 years ago)

On Oct 28, 2008, at 12:46 PM, Peter Michaux wrote:

I do roughly the same thing. Using an object is faster than "switch" also, as far as I recall doing some tests. The speed of switch seems to be the same speed as if-else if-else if-...-else.

It really depends on what you are doing. At least some modern
implementations use a jump table for common cases such as all simple
integer values in the case blocks.

, Maciej

# Mark S. Miller (17 years ago)

On Tue, Oct 28, 2008 at 12:39 PM, Brendan Eich <brendan at mozilla.com> wrote:

On Oct 28, 2008, at 12:18 PM, Maciej Stachowiak wrote:

On Oct 27, 2008, at 11:28 PM, Breton Slivka wrote:

I had a go at combining that concept with my object dispatcher concept, to try and come up with an example of a reasonable transform of a switch statement to a structure with equivalent function that uses (mostly) only lambdas and expressions.

The object dispatcher is a neat trick but not a correct transform of switch, since switch compares with == rather than by converting to string like property lookup does.

===, actually.

Another use for Map.

function foo(n) { switch (n) { case NaN: return 'x'; case -0: return 'y'; default: return 'z'; } } foo(NaN) // must yield z foo(0) // must yield y

Hopefully Map will not reproduce this insanity, and so be too well behaved to use directly in a desugaring of switch.

# Brendan Eich (17 years ago)

On Oct 28, 2008, at 2:00 PM, Mark S. Miller wrote:

Hopefully Map will not reproduce this insanity, and so be too well behaved to use directly in a desugaring of switch.

I don't propose to desugar switch, but yes: default Map should use
identity ("eq"), not ===.