[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: RE: Proper tail recursion
- From: Philippe Lhoste <PhiLho@...>
- Date: Fri, 27 Jul 2001 11:41:20 +0200 (MEST)
> 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
> return loop(a * 0.9)
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.
if abs(a) < 1 then
return loop(a * 0.9)
return !loop(a * 0.9)
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
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 :-)
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
Sent through GMX FreeMail - http://www.gmx.net