Re: proper tail calls?

[Bret Victor <bret@...>]

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