Proper tail recursion

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Proper tail recursion

John D. Ramsdell-3
I generally do not find learning a new scripting language pleasant,
because the designs of most languages usually suggest to me that the
authors have not learned the lessons of past efforts of language
design and inflict needless confusion on their users.  My introduction
to lua was pleasant, as some fine choices were made in its design:
tables as objects, first class functions, and real garbage collection.
In many ways, lua is similar to Scheme except that tables replace
pairs as the basic gluing data structure, and the syntax is far easier
for non-specialists.

Still, lua has some ugly warts, such as the lack of real lexical
scoping as evidenced by need for upvalues.  This particular wart makes
implementing mutually recursive local functions very ugly, but this
subject has been fully discussed on this list, so I will not pursue
the topic here except to say that small Scheme implementations that
implement true lexical scoping have been available for a long time.
The issue I would like to discuss is proper tail recursion.

A properly tail recursive implementation of a programming language
allows the execution of an iterative computation in constant space,
even if the iterative computation is described by a syntactically
recursive procedure.  With a properly tail recursive implementation,
iteration can be expressed using the ordinary procedure call
mechanics, so that special iteration constructs are useful only as
abbreviations.

In the following example, the computation specified in loop.lua is
fundamentally iterative.

     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$

If you run this program in version 4.0 of the lua interpreter, you
find the interpreter runs out of stack space.  The lua interpreter is
keeping stack frames that will never be used.  Translating this
example into Scheme and running it in a system that correctly
implements the language will never result in a stack overflow.

The Scheme standard (R5RS) specifies that Scheme implementations must
be properly tail recursive here:

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

The rational from R5RS is:

     Intuitively, no space is needed for an active tail call because
     the continuation that is used in the tail call has the same
     semantics as the continuation passed to the procedure containing
     the call. Although an improper implementation might use a new
     continuation in the call, a return to this new continuation would
     be followed immediately by a return to the continuation passed to
     the procedure. A properly tail-recursive implementation returns
     to that continuation directly.

>From this discussion, one can see one of the benefits of a properly
tail recursive implementation of lua: stack frames are removed from
the stack earlier, and so the heap objects to which they refer can be
collected sooner if they are garbage.

There is another benefit that is very important.  If programmers are
allowed to assume that all lua implementations are properly tail
recursive, a new style of programming is available which relies on the
fact that implementations have this property.  For example, to
implement a program that behaves much like a finite state machine, one
can write a function for each state.  A transition in implemented by
tail call to the next state.  The tail recursiveness of the
implementation ensures that only stack frames needed to produce the
correct answer are retained, so the stack size does not limit the size
of the finite state machine.

Properly tail recursive implementations of programming languages have
served the functional programming community well.  Standard ML,
OCaml, Haskell, and Scheme programmers have a long tradition making
use of this property of an implementation.  I hope the lua community
works toward joining in this fine tradition.  Good luck.

John

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Roberto Ierusalimschy
> Still, lua has some ugly warts, such as the lack of real lexical
> scoping as evidenced by need for upvalues.  This particular wart makes
> implementing mutually recursive local functions very ugly, but this
> subject has been fully discussed on this list, so I will not pursue
> the topic here except to say that small Scheme implementations that
> implement true lexical scoping have been available for a long time.
> The issue I would like to discuss is proper tail recursion.

I would love to see real lexical scoping in Lua, too. But I don't know how 
to implement it within our requirements. As far as I know small Scheme 
implementations are not very efficient. We need an implementation that 
keeps Lua's performance, and at the same time does not increase too much 
the complexity of the compiler (Lua uses a one-pass compiler, without any 
form of intermediate representation). ET once gave an interesting 
sugestion, where "normal" local variables live in the stack, and only local 
variables that are used by inner-functions would be allocated in the heap. 
The problem is how to generate code without knowing where a variable is 
going to live (when the compiler sees the inner function it can be too 
late...) 


Proper tail recursion is not difficult to implement, but also it is not
as simple as in Scheme. In Lua, functions may be Lua functions or
C functions: C functions cannot be called using proper tail recursion,
and only at runtime we know whether a tail call calls a Lua function.
(Also we must take care of 'function' tag methods.)

Moreover, proper tail recursion spoils debug information, does it not?
(Maybe that is not a too high price to pay...).

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Thatcher Ulrich
On Thu, 26 Jul 2001, Roberto Ierusalimschy wrote:

> the complexity of the compiler (Lua uses a one-pass compiler, without any
> form of intermediate representation). ET once gave an interesting
> sugestion, where "normal" local variables live in the stack, and only local
> variables that are used by inner-functions would be allocated in the heap.
> The problem is how to generate code without knowing where a variable is
> going to live (when the compiler sees the inner function it can be too
> late...)

Interesting.  Well, how about an *optional* optimizer, which takes in Lua
bytecode, looks for optimizations like that, and outputs the optimized
bytecode.  I don't know much about Lua internals... does that sound
feasible?  It seems like it could maybe be done as an external third-party
tool.

Re: tail calls... can the decision be made at the time of the recursive
call rather than at compile time?  It's been a while since I've worked on
anything like that so forgive me if I'm being stupid :)

-Thatcher


Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Luiz Henrique de Figueiredo
In reply to this post by John D. Ramsdell-3
>Interesting.  Well, how about an *optional* optimizer, which takes in Lua
>bytecode, looks for optimizations like that, and outputs the optimized
>bytecode.  I don't know much about Lua internals... does that sound
>feasible?

The main point is that there are no such things as tail recursions, because
global names are resolved at runtime.

More precisely, in the code below

 function f(x)
  if a(x) then return b(x) end
  return f(g(x))
 end

By the time f runs and tries to call "itself", the called f might not even be
the original one because a(x) might have changed the value of the global f.
Not likely, but it just shows that the dynamic nature of Lua does make things
more complicated.

>Re: tail calls... can the decision be made at the time of the recursive
>call rather than at compile time?

Now, this could work and we actually discussed this once. We never added it
to the main code because it would ruin debugging, but would it really?
Moreover, it would not do anything for mutually recursive functions.
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Thatcher Ulrich
On Thu, 26 Jul 2001, Luiz Henrique de Figueiredo wrote:

> >Interesting.  Well, how about an *optional* optimizer, which takes in Lua
> >bytecode, looks for optimizations like that, and outputs the optimized
> >bytecode.  I don't know much about Lua internals... does that sound
> >feasible?
>
> The main point is that there are no such things as tail recursions, because
> global names are resolved at runtime.

Right, it wouldn't be able to find tail recursion.  I was thinking the
optimizer would apply to the idea you mentioned of having "true" local
variables on the stack, which isn't feasible now because the compiler uses
only one pass.  Maybe there are a whole batch of other shallow
optimizations that could be done as well?

-Thatcher



Reply | Threaded
Open this post in threaded view
|

Tag methods questions

Eric Ries
I've got a quick tag method question. If I've got the "index" tag method set
for a table (say "foo"), I can get a function called whenever someone writes

foo.member

and member is nil. I can then dispatch this call based on knowledge of the
index name (in this case the string "member").

However, for the case of foo.member(bar) (or foo:member(bar)), what is the
correct way to intercept this call? It seems to me that I lose the
information that "someone tried to call function 'member' on table 'foo'" if
I use the function tag method.

What is the 'correct' lua way to handle this case?

Eric


Reply | Threaded
Open this post in threaded view
|

RE: Proper tail recursion

Philippe Lhoste
In reply to this post by John D. Ramsdell-3
> There is another benefit that is very important.  If programmers are
> allowed to assume that all lua implementations are properly tail
> recursive, a new style of programming is available which relies on the
> fact that implementations have this property.  For example, to
> implement a program that behaves much like a finite state machine, one
> can write a function for each state.  A transition in implemented by
> tail call to the next state.  The tail recursiveness of the
> implementation ensures that only stack frames needed to produce the
> correct answer are retained, so the stack size does not limit the size
> of the finite state machine.

While I am not overly interested by recursive algorithms (useful, but
avoidable most of the time. Please, no thread on this, I know I am probably
wrong... :-), the finite state machine argument is quite valid. I don't know how to
jump from one part of code to another, in Lua (no goto). Perhaps with dofile,
but it is quite clumsy.

> In the following example, the computation specified in loop.lua is
> fundamentally iterative.
> 
>      #! /usr/bin/env lua
>      function loop(a)
>        if abs(a) < 1 then
>          return a
>        else
>          return loop(a * 0.9)
>        end
>      end

As Roberto and Luiz stated, there are some problems with a generic tail
recursions, for performance, and because of the dynamic nature of functions.

Now, perhaps we can imagine a special syntax for such use, flagging a
function or a call as needing tail recursion.
Something like:
!function loop(a)
  if abs(a) < 1 then
    return a
  else
    return loop(a * 0.9)
  end
end

or

function loop(a)
[...]
    return !loop(a * 0.9)
  end
end

This indicates that the call of this function, or this call, must not be
stacked. Of course, the ! syntax is just indicative, I choosed not to use a new
keyword.
Of course, this can provide some other problems, or strange bugs if the user
misuse this syntax...

I hope I am clear and not off target, I am not as aware of these problems as
you "computer science" guys :-)

Regards.

-- 
--._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.--
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
http://jove.prohosting.com/~philho/
--´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`--

Sent through GMX FreeMail - http://www.gmx.net


Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

John Belmonte-2
Philippe Lhoste wrote:
> While I am not overly interested by recursive algorithms (useful,
> but avoidable most of the time. Please, no thread on this, I know
> I am probably wrong... :-), the finite state machine argument is
> quite valid. I don't know how to jump from one part of code to
> another, in Lua (no goto). Perhaps with dofile, but it is quite
> clumsy.

Coroutines are supposed to provide a nice solution to this, although I
haven't tried them myself.

-John



Reply | Threaded
Open this post in threaded view
|

AW: Proper tail recursion

Peter Prade
Why change the language when you can already do the equivalent to tail
recursions?
just have the function return the function it would like to call as tail
call.
the only additional thing you need is a "main" function that does the actual
calling.

look at this:

function State_A()
  ...
  return State_B
end

function main()
state = State_A
  while state do state = state() end
end

if you need arguments, you can do it like that:

function State_B(arg1, arg2)
  ...
  return State_A, {"foo", "bar"}
end

function main()
state = State_A
  while state do
    state, args = call(state,args)
  end
end

-Peter


Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

John D. Ramsdell-3
In reply to this post by Philippe Lhoste
Philippe Lhoste <[hidden email]> 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

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

John D. Ramsdell-3
In reply to this post by Luiz Henrique de Figueiredo
Roberto writes:

> Proper tail recursion is not difficult to implement, but also it is
> not as simple as in Scheme. In Lua, functions may be Lua functions
> or C functions: C functions cannot be called using proper tail
> recursion, and only at runtime we know whether a tail call calls a
> Lua function.  (Also we must take care of 'function' tag methods.)

I would be interested in learning more about the issues involved and
am will to help if I can.  I looked at the source and found little
documentation in the sources.  Is there a design document describing
the Lua implementation?  Is there at least a document that describes
the semantics of each bytecode?

> Moreover, proper tail recursion spoils debug information, does it
> not?  (Maybe that is not a too high price to pay...).

When using Scheme, I found it natural not to expect to see stack
frames that could not effect the future of the computations, so I
never worried about this.

John

Reply | Threaded
Open this post in threaded view
|

Re: Tag methods questions

Jay Carlson
In reply to this post by Eric Ries
"Eric Ries" <[hidden email]>

> I've got a quick tag method question. If I've got the "index" tag method
set
> for a table (say "foo"), I can get a function called whenever someone
writes
>
> foo.member
>
> and member is nil. I can then dispatch this call based on knowledge of the
> index name (in this case the string "member").
>
> However, for the case of foo.member(bar) (or foo:member(bar)), what is the
> correct way to intercept this call? It seems to me that I lose the
> information that "someone tried to call function 'member' on table 'foo'"
if
> I use the function tag method.
>
> What is the 'correct' lua way to handle this case?

[oooh oooh I think I know this one]

Hook gettable.  You have to return a function, but it doesn't have to be a
constant function.  So:

function my_gettable(table, index)
  local v = rawget(table, index)
  if v then return v end
  -- pretend all absent values are methods to be delegated or something
  return function(self, ...)
          assert(self == %table, "tried to call method from one object on a
different object")
          print("would call", %table, "method name", %index)
  end
end

The assert is there to avoid this kind of monkey business:

  a = foo.method
  a(bar) -- self doesn't match the table where we got the method from!

BTW, I think Lua is the fastest I've ever gone from zero knowledge to
writing metaobject protocols....

Jay



Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Luiz Henrique de Figueiredo
In reply to this post by John D. Ramsdell-3
>Is there a design document describing the Lua implementation?

No.

>Is there at least a document that describes the semantics of each bytecode?

Yes, lopcodes.h.
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

Roberto Ierusalimschy
In reply to this post by John D. Ramsdell-3
> It is very easy for a compiler to identify tail calls in a Lua source.

Yes, it is. But as I said before, a tail call will not always executes as a 
"proper" tail call, because of C functions.

Again, it is easy for the interpreter to test whether the called function 
is C or Lua, and act accordingly. The real problems I see for tail calls in 
Lua are

1 - debugging. Many Lua users do not even know what is a tail call, and
expect to see them in a stack trace.

2 - subtle behaviour. "return f()" is a proper tail call (*if* f is a Lua
function), but "return x, f()" and "f(); return" are not. This can be
quite confusing for programmers assuming proper tail calls.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

John D. Ramsdell-3
Roberto,

I studied the sources carefully, and think I see the two changes
needed to make the implementation properly tail recursive.  I believe
one of the changes is important to make even if the implementation is
not modified to be properly tail recursive.  I'm sure I don't have a
deep understanding of the interpreter, so I could be on the wrong
track, but I'm sure you'll correct any misunderstanding I introduce.

As I understand it, the control stack for the interpreter is kept in
the C runtime stack, and the argument stack is in the lua_State
object.  To make the Lua bytecode interpreter properly tail recursive,
one must make sure that garbage stack frames are purged from both the
argument stack and the C runtime stack.

To eliminate garbage stack frames from the C runtime stack, the
function luaV_execute in lvm.c must be changed.  The case for a tail
call is currently:

      case OP_TAILCALL: {
        L->top = top;
        luaD_call(L, base+GETARG_A(i), LUA_MULTRET);
        return base+GETARG_B(i);
      }

or abstractly:

      case OP_TAILCALL: {
        Get the real function to be executed;
        if (executing a Lua function) {
          call the interpreter with the Lua function;
        }
        else {
          call the C function;
        }
        return args;
      }

This must be changed to become something that behaves differently when
calling a Lua function.  In particular, rather than recursively
calling the interpreter as it does now, it must restart the
interpreter in its current stack frame so that no garbage frames are
added to the C runtime stack.  Abstractly, the case for a tail call
should be:

      case OP_TAILCALL: {
        Get the real function to be executed;
        if (executing a Lua function) {
          initialize the interpreter;
          goto the interpreter start point;  /* Don't call the interpreter! */
        }
        else {
          call the C function;
          return args;
        }
      }

I strongly suspect this optimization will be beneficial even if no
other changes are made to the interpreter.  The change replaces a C
function call with a goto and eliminates garbage stack frames from the
C runtime stack.  Since the TAILCALL opcode is executed often, this
should result in a faster bytecode interpreter.

The final change needed to make the implementation tail recursive is
to remove the arguments of the function making the tail recursive call
by overwriting them with the arguments of function being called tail
recursively.

      case OP_TAILCALL: {
        Get the real function to be executed;
        Remove garbage values from the argument stack;
        if (executing a Lua function) {
          initialize the interpreter;
          goto the interpreter start point;  /* Don't call the interpreter! */
        }
        else {
          call the C function;
          return args;
        }
      }

The section that removes the garbage from the argument stack could be
added or removed via a compile time variable making it easy to select
either mode.  In this way, it would be easy for people to try Lua both
ways and decide if the debugging and subtle behavior you worry about
are real issues.

John

Roberto Ierusalimschy <[hidden email]> writes:

> > It is very easy for a compiler to identify tail calls in a Lua source.
> 
> Yes, it is. But as I said before, a tail call will not always executes as a 
> "proper" tail call, because of C functions.
> 
> Again, it is easy for the interpreter to test whether the called function 
> is C or Lua, and act accordingly. The real problems I see for tail calls in 
> Lua are
> 
> 1 - debugging. Many Lua users do not even know what is a tail call, and
> expect to see them in a stack trace.
> 
> 2 - subtle behaviour. "return f()" is a proper tail call (*if* f is a Lua
> function), but "return x, f()" and "f(); return" are not. This can be
> quite confusing for programmers assuming proper tail calls.
> 
> -- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Proper tail recursion

John D. Ramsdell-3
In reply to this post by Roberto Ierusalimschy
For this note, assume that a word surrounded by the underline
character means the word should be typeset in italics.

Roberto Ierusalimschy <[hidden email]> writes:

> Again, it is easy for the interpreter to test whether the called function 
> is C or Lua, and act accordingly. The real problems I see for tail calls in 
> Lua are
> 
> 1 - debugging. Many Lua users do not even know what is a tail call, and
> expect to see them in a stack trace.
> 
> 2 - subtle behaviour. "return f()" is a proper tail call (*if* f is a Lua
> function), but "return x, f()" and "f(); return" are not. This can be
> quite confusing for programmers assuming proper tail calls.

The subtle behavior you point out suggests to me a simple rule for the
identification of tail calls.  The rule is easy for programmers to
understand.  The rule could be:

  A call is a tail call if and only if it occurs in a statement of the
  form "return _tailcall_", _tailcall_ is a Lua function call
  expression _functioncall_, and the function part of the function
  call evaluates to a Lua function.  The syntactic category
  _functioncall_ is defined in the section of the manual titled "The
  complete Syntax of Lua".  

In other words, only statements of the form: 

  return _varorfunct_ [ ':' _name_ ] _args_

are tail calls, and only when

  _varorfunct_ [ ':' _name_ ]

evaluates to a Lua function.

John