Lambda vs. function

[Maciej Stachowiak]

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 of `break' 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/Haskell `case'. 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.

Regards,
Maciej