RE: Proper tail recursion

[Philippe Lhoste <PhiLho@...>]

> 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