Anonymous recursion

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

Anonymous recursion

Reuben Thomas-3
If you look in tests/factorial.lua, you'll find an implementation of the Y
combinator that lets you make an arbitrary function recursive. The idea is
that you take your ordinary version of the function:

f = function (...) ... f(...) ... f(...) ... end

and wrap it up:

F = function (f)
      return function (...) ... %f(...) ... %f(...) ... end
    end

replacing the recursive calls by calls to the upvariable %f, which is a
parameter to the new F.

You then say

f = Y(F)

and lo! f is now a recursive function. Of course, you can do the whole lot
in one step:

local f = Y(function ... end)

Because lua is not a proper functional language, the definition of Y is even
hairier than usual, and to be honest, I haven't quite understood it myself,
although essentially, it turns F into F(Y(F)).

-- 
http://sc3d.org/rrt/
L'art des vers est de transformer en beautés les faiblesses (Aragon)


Reply | Threaded
Open this post in threaded view
|

Re: Anonymous recursion

Daniel Silverstone
On Thu, Jan 04, 2001 at 11:57:55AM +0000, Reuben Thomas wrote:
> If you look in tests/factorial.lua, you'll find an implementation of the Y
> combinator that lets you make an arbitrary function recursive. The idea is
> that you take your ordinary version of the function:
[snip]
> Because lua is not a proper functional language, the definition of Y is even
> hairier than usual, and to be honest, I haven't quite understood it myself,
> although essentially, it turns F into F(Y(F)).

This seems a little Ikky, I suppose I could just pass the value
in explicitly, I.E.

local foo = function(fptr,param) .....end;

and just explicitly pass fptr around properly, but then it seems to me
that Lua should have this as a language feature.

Daniel.