Lambda vs. function

Dave Herman dherman at ccs.neu.edu
Mon Oct 20 14:23:22 PDT 2008


> 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 the 
`lambda' proposal nicely avoids this complication by eliminating `return'.

Dave


More information about the Es-discuss mailing list