Lambda vs. function

Dave Herman dherman at ccs.neu.edu
Fri Oct 17 16:40:33 PDT 2008


No, I must have misunderstood what you meant by "wrapping the call to  
g() inside another statement" -- I thought you were referring to  
wrapping it in a context such as

     { -- ; stmt; }

which would obviously not be a tail position. But this:

> lambda f(x) {
> if (x == 0)
>  1;
> else
>  f(x - 1);
> }

would be tail recursive. Let's try to get specific without drowning in  
too much detail. Here is a taste of what defines tail position,  
written in the style of an attribute grammar:

-----

Expression <- lambda Formals Block
     Block.tail = true

Statement <- { stmt1; ... ; stmtn; stmt; }

     stmt1.tail = false
     ...
     stmtn.tail = false
     stmt.tail = Statement.tail

Statement <- if expr stmt;

     expr.tail = false
     stmt.tail = Statement.tail

Statement <- if expr stmt1 else stmt2;

     expr.tail = false
     stmt1.tail = Statement.tail
     stmt2.tail = Statement.tail

Statement <- while (expr) stmt

     expr.tail = false
     stmt.tail = false

-----

Do you see where I'm going with this? It's a pretty natural idea. The  
branches of an if-statement can be in tail position because they are  
the last thing produced by the if-statement. Some things like loop  
forms and switch won't be able to contain tail positions because  
they're too imperative. But if statements and blocks have a very  
natural notion of tail position.

Dave



More information about the Es-discuss mailing list