Lambda vs. function
Dave Herman
dherman at ccs.neu.edu
Fri Oct 17 05:10:16 PDT 2008
> 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.
More information about the Es-discuss
mailing list