• Subject: Re: Proper tail recursion
• From: ramsdell@... (John D. Ramsdell)
• Date: 27 Jul 2001 08:27:09 -0400

```Philippe Lhoste <PhiLho@gmx.net> writes:

> Now, perhaps we can imagine a special syntax for such use, flagging a
> function or a call as needing tail recursion.
> Something like:
....

It is very easy for a compiler to identify tail calls in a Lua
source.  If that last thing a function does is call another function,
that call is a tail call.  There is no need for any special
annotations.  Furthermore, the current compiler seems to identify tail

bash-2.01\$ luac -v
Lua 4.0  Copyright (C) 1994-2000 TeCGraf, PUC-Rio
bash-2.01\$ cat loop.lua
#! /usr/bin/env lua
function loop(a)
if abs(a) < 1 then
return a
else
return loop(a * 0.9)
end
end

print(loop(3))

print(loop(3e30))
bash-2.01\$ luac -l loop.lua

main <0:@loop.lua> (13 instructions/52 bytes at 0x8052898)
0 params, 3 stacks, 0 locals, 2 strings, 1 number, 1 function, 7 lines
1	[8]	CLOSURE    	0 0	; 0x8052990
2	[8]	SETGLOBAL  	0	; loop
3	[10]	GETGLOBAL  	1	; print
4	[10]	GETGLOBAL  	0	; loop
5	[10]	PUSHINT    	3
6	[10]	CALL       	1 255
7	[10]	CALL       	0 0
8	[12]	GETGLOBAL  	1	; print
9	[12]	GETGLOBAL  	0	; loop
10	[12]	PUSHNUM    	0	; 3e+30
11	[12]	CALL       	1 255
12	[12]	CALL       	0 0
13	[12]	END

function <2:@loop.lua> (14 instructions/56 bytes at 0x8052990)
1 param, 4 stacks, 1 local, 2 strings, 1 number, 0 functions, 8 lines
1	[3]	GETGLOBAL  	0	; abs
2	[3]	GETLOCAL   	0	; a
3	[3]	CALL       	1 1
4	[3]	PUSHINT    	1
5	[3]	JMPGE      	3	; to 9
6	[4]	GETLOCAL   	0	; a
7	[4]	RETURN     	1
8	[4]	JMP        	5	; to 14
9	[6]	GETGLOBAL  	1	; loop
10	[6]	GETLOCAL   	0	; a
11	[6]	PUSHNUM    	0	; 0.9
12	[6]	MULT
13	[6]	TAILCALL   	1 1
14	[8]	END
bash-2.01\$

The compiler appears to merge any CALL followed by a RETURN into a
TAILCALL.  It seems that a properly tail recursive implementation of
Lua requires only changes to the bytecode interpreter, as the compiler