Lambda vs. function

[Dave Herman]

> What is your point?  To write a recursive factorial I'd write either:
>
> lambda f(x) {
> if (x == 0)
>   1;
> else
>   f(x - 1);
> }
>
> or:
>
> function f(x) {
> if (x == 0)
>   return 1;
> else
>   return f(x - 1);
> }

Right, good, so far we're on the same page.

> Either one is subject to having to jump out of try-catch blocks if  
> you have them.  You still have all the same issues of whether f is  
> in the tail position or not.

Yes and no. Try-catch does need to be kept in the continuation  
regardless of whether we're talking about a tail-recursive function/ 
return form or a tail-recursive lambda form. But the point is that, if  
you want function/return to be properly tail-calling, then in these  
two functions:

     function f() {
         try {
             if (test())
                 return g();
         }
         catch (e) { }
     }

     function f() {
         if (test())
             return g();
     }

return has different behavior. In the first one, you first evaluate  
g() and then return. In the second one, you first return and then  
evaluate g(). By contrast, if you write these in lambda-style, you get:

     lambda f() {
         try {
             if (test())
                 g()
         }
         catch (e) { }
     }

     lambda f() {
         if (test())
             g()
     }

Now there's no question about any control effect. And just to drive  
home the point that `return' is indeed a control effect, imagine the  
same function where the try-block isn't even the last statement in the  
block:

     function f() {
         try {
             if (test())
                 return g();
         }
         catch (e) { }
         h();
     }

There isn't even a straightforward translation to lambda style[*]  
without some kind of jumps! This is where return-to-label comes in:

     lambda f() {
         abort: {
             try {
                 if (test())
                     return :abort g();
             }
             catch (e) { }
             h();
         }
     }

Now, because return :exit g() first evaluates g() before returning,  
this is not a tail call to g(). So when you use return, you don't get  
tail calls. But it means you have *one* consistent semantics for  
return: it always evaluates its argument before performing its control  
effect. That means function/return isn't properly tail calling, but by  
default `lambda' is.

> They all first evaluate the subexpression and then jump to the caller.

No, they don't. Not if you are trying to implement properly tail- 
calling `return'. That's the point.

Dave

[*] Short of CPS, which is precisely a lambda-encoding of jumps. But  
it's a non-local transformation, which is both anti-modular and bad  
for readability.