Re: Proper tail recursion

[ramsdell@... (John D. Ramsdell)]

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
calls already!

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
is already to go.

For humans, you can easily identify tail calls using the notion of
tail context as was done for Scheme language definition at:

http://www.swiss.ai.mit.edu/ftpdir/scheme-reports/r5rs-html/r5rs_5.html#IDX52

It is a little more tricky for Lua because expressions are not
statements, but not much.

John