lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]



On 17-Sep-04, at 7:54 PM, Tom Spilman wrote:

return the_page_stack:restore_device_objects()

This is a tail call; it is effectively optimised into a jump.
So the caller of the_page_stack:restore_device_objects() has
been removed from the stack before the function is called.

Tail calls make it simple to implement state machines, for example;
each state "recursively" tail calls its choice of the next state, but
this works with a constant stack

Or you can write recursive functions that run in a constant stack, such as:

  local function fib(i, r1, r2)
    if i <= 1 then return r1
              else return fib(i - 1, r1 + r2, r1)
    end
  end

  function fibonacci(i) return fib(i, 1, 0) end

Lua's attempts to "simulate" non-tail-call semantics by providing
fake stack slots actually make it harder to debug that sort of code.
But tastes vary.

As a possibly interesting side-note, I've done some experimentation
with this particular definition of fibonacci on gcc on various platforms, and it turns out that not only does gcc (in recent versions) also convert recursive call into a tail-call, on some platforms it generates faster code than the more classic iterative expression. (Interestingly, the optimiser generates the first eight or so results as a static lookup for the recursive
function but not for the iterative function; I'm assuming that this is
because the lack of assignment statements makes flow analysis easier.)