Re: proper tail calls?
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: proper tail calls?
- From: Bret Victor <bret@...>
- Date: 2006年3月11日 11:03:10 -0800 (PST)
Hi Nathan,
I don't think Matt or David read your code carefully enough. ;)
"return {car=x,cdr=const(x)}" and "listing(const('.'))" are both
fine as is. The problem is here:
function listing(x)
io.write(thunk.force(x).car)
listing(thunk.force(x).cdr)
end
Change that to:
function listing(x)
io.write(thunk.force(x).car)
return listing(thunk.force(x).cdr)
end
and you're all good. Unlike Scheme (and Perl, and etc.), Lua doesn't
automatically return the last expression evaluated. Without the
"return" on the end there, it's not a tail-call because the caller
has to clean up the stack (throw away what the callee returned).
Incidentally, here's another approach to thunking. It's somewhat more
efficient because closures are smaller than tables, and you can also
get rid of force() and just call the thunk directly:
function thunk.delay (f)
local value
return function ()
if f then value = f(); f = nil end
return value
end
end
function thunk.force (x)
return x()
end
Also incidentally, if you're looking to do a "memoized lazy list"
sort of thing, a more Lua-like way is to use a metatable. For example,
here is an "infinite table" that contains all the Fibonacci numbers:
local fibs = { 1, 1 }
setmetatable(fibs, { __index = function (fibs, i)
fibs[i] = fibs[i-2] + fibs[i-1]
return fibs[i]
end })
-- fibs[i] is the ith Fibonacci number.
assert(fibs[8] == 21)
assert(fibs[9] == 34)
assert(fibs[10] == 55)
Metatables and laziness go hand-in-hand. That's a big part of what
makes Lua so awesome.
-Bret