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
_______________________________________________
Es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
