Lambda vs. function
Maciej Stachowiak
mjs at apple.com
Mon Oct 27 08:21:36 PDT 2008
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
More information about the Es-discuss
mailing list