CODEWITHSUNDEEP
luatail-recursiontail-call-optimization
Baiyan Huang
Baiyan Huang

Reputation: 6771

tail call optimization in lua

Lua claims that it implement tail call properly thus no stack needs to be maintained for each call thus allow infinite recursion, I tried to write a sum function, one is not tail call, and one is tail call:

non tailcall version

function sum(n)
    if n > 0 then
        return n + sum(n-1)
    end
end

print(sum(1000000))

stackoverflow as expected.

tailcall version

function sum2(accu, n)
    if n > 0 then
        accu.value = accu.value + n
        sum2(accu, n-1)
    end
end
local accu = {value = 0}
sum2(accu, 1000000)
print(accu.value)

I suppose there would be no stackoverflow in this case as it is a tailcall, but it still failed due to stackoverflow:

/bin/lua/5.1.4/bin/lua: tailcall.lua:13: stack overflow
stack traceback:
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        ...
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:13: in function 'sum2'
        tailcall.lua:17: in main chunk
        [C]: ?

So is lua really support tail call optimization, or my function is actually not tail call here?

I am using lua 5.1.4 on redhat 5

Upvotes: 15

Views: 5682

Answers (2)

DLatchX
DLatchX

Reputation: 63

As has already been said, the only correct tail call syntax is return f(...)

That's because f() ; return is not the same as return f(): the former requires a final operation after calling f : drop its results to ensure nothing is returned.

but how could lua can't figure out this is actually a tail call

Because lua is a very "dynamic" language: in

function sum2(accu, n)
    if n > 0 then
        accu.value = accu.value + n
        sum2(accu, n-1)
    end
end

sum2 is not calling itself, it's calling the global variable "sum2" (or equivalent upvalue if declared local)

And this variable could become a function returning values, in which case emitting a tail call bytecode would be incorrect.

In other words: whether f makes a tail call is knowledge that is inaccessible to the compiler, and will only be confirmed at runtime, unless you use the unbreakable syntax return f(...)

Upvotes: 1

prapin
prapin

Reputation: 6858

Tail call in Lua must have the following form

return fct(args)

So your tail call version must be rewritten as:

function sum2(accu, n)
  if n > 0 then
    accu.value = accu.value + n
    return sum2(accu, n-1) --< note the return here
  end
end

Upvotes: 23

Related Questions