Lambda vs. function

Dave Herman dherman at ccs.neu.edu
Mon Oct 27 06:46:46 PDT 2008


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 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.

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. 
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, the `switch' construct is inherently imperative 
(just ask Tom Duff!). A more functional multiple-case dispatch form 
would be like Scheme's `cond' or ML/Haskell `case'. God, we need macros.

Dave



More information about the Es-discuss mailing list