Can an anonymus function call itself? (1 Viewer)

[Herly Quijano]

I wanna add recursion to anonymus functions, is there a way to do that? like a keyword or a process or yes or yes must have a name?

 

[GavinW]

You could use a fixed-point combinator. For example

Y = function (f)
  local g = function (x) return f ( x (x)) end
  return g(g)
 end

 

[Herly Quijano]

@GavinW I don't understand, can you explain me please?

 

[GavinW]

It looks like my first suggestion does not work. I think what you are asking for is how to do a calculation like

function fact (n)
return (n<2) and n or n*fact(n-1) end
print (fact(4)) --> 24

without using a recursive function definition. What about this?

local Y = function (g)
   return (function (f)
      f = g ( function (x) return (f (x)) end)
      return f end) end
local F = function (f) return function (n)
       return (n<2) and n or n*f(n-1) end end
print (Y(F)(4)) --> 24

It works for me.
Back in the 80s there was a nice article called The care and feeding of combinators. A combinator is essentially a function whose only arguments are functions and whose return values are constructed only from applications of functions to arguments. Y is an example here. The subject of combinatory algebra will tell you more.

 

[Herly Quijano]

@GavinW At the end what you said I don't think is what I asked, because you are still naming functions, and what you suggested don't even do what you said, it printed:

function: 00000<Always a different "code">

But that thing of Combinatory algebra looks interesting but complicated.

It looks like my first suggestion does not work. I think what you are asking for is how to do a calculation like

No, I want but without naming the function.

 

[GavinW]

OK. The factorial function imay be given by

(function (g) return (
  function (f) f = g ( function (x) return (f (x)) end)
  return f end) end ) ( function (h) return function (n)
       return (n<2) and n or n*h(n-1) end end)

There are no named functions here. But naming is only a way of making expressions shorter - and of making it easier to avoid typographical errors.

 

[Herly Quijano]

If it will be to convoluted and I don't end to understand how it works, and it seems you are doing this thinking I will use that method everytime I need use that function losing the point of naming a function, I just wanna know if I can do something, like this:

-- func is a function that needs a function as parameter, what it does is irrelevant

func(function (x)
    if Cond then
        (Call this function again)(x)
    end
end)

 

[stetre]

I may be wrong, but I don't think you can. To call a function you need a reference to it (i.e. a name) even if you do it within the function itself. I'm afraid you have to define the argument function in advance, like in the code below. Is this a problem?

local function f(x)
    if Cond then f(x) end
end
func(f)

 

[GavinW]

The Y combinator as given above provides a means of doing this. Its crucial property is that Y(f) reduces to f(Y(f)) - the fixed-point property. Using it makes it possible to rewrite definitions without explicit recursion. Thus, in the remarks above, Y(F) does the same as fact. You get F from fact by replacing the repeated variable of the recursion by a new variable, and this works quite generally. However, as stetre says, why should you want to do this?

Higher order functions, as found in Lua, provide tremendous power, but how they work can be hard to comprehend. Herly has my sympathy.

NB. Should that not be

local f
function f(x) if Cond then f(x) end end

? I always use the unsugared syntax for functions so I am not quite sure how the rule about locality starting on the next line plays out here.

 

[stetre]

NB. Should that not be

local f
function f(x) if Cond then f(x) end end

? I always use the unsugared syntax for functions so I am not quite sure how the rule about locality starting on the next line plays out here.

It's equivalent, I tested it and it works. What you cannot do is this:

local f = function(x) if Cond then f(x) end end -- doesn't work: f is nil inside the body
func(f)

I'm not sure why, but I presume it's because in this case the variable f doesn't exist yet when the the right-hand expression defining the function value is evaluated.

Your version is still 'sugared', however. The 'pure' unsugared version would be this:

local f
f = function(x) if Cond then f(x) end end
func(f)

This creates a variable f, uninitialized. Then it uses that same variable in an expression that creates a function value, which it finally assigns to yet the same variable f. It works because when the function value is evaluated, the variable f is correctly initialized (even if it wasn't when the function value was created).

 

[GavinW]

Thanks. I thought it was something like that. My personal preference for the unsugared syntax is because the sugar seems to me to be unnecessarily apologetic. It is just because many Lua users come from a first-order background, rather than a higher-order one, that they should perhaps be encouraged to embrace higher-order functions by practicing with unsugared syntax. Or am I being a little bit fascist here?