Recursive anonymous functions?

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

Recursive anonymous functions?

Philip Bock
Is there any way for an anonymous function to call itself?

For example, if I'm writing a table serializer, like this one:

function serialize_table(table, outfile, tab_depth)
	outfile:write("{")

	local indent = string.rep("\t", tab_depth)

	for k, v in pairs(table) do
		if (type(v) == "number" or type(v) == "string")
			outfile:write(indent..k.." = "..v)
		elseif (type(v) == "table")
			serialize_table(table, outfile, tab_depth + 1)
		end
	end

	outfile:write("}")
end

function serialize(table, filename)
	local outfile = io.open(filename, "w")

	outfile:write("return ");
	serialize_table(table, outfile, 1)
	outfile:close()
end

Is there any way to place the serialize_table function inside the serialize function, so I don't have to pollute the global namespace, but still let it call itself? I suppose I could declare it local inside the serialize function, and then pass it as an argument to itself, but is there a less ugly way to do it?

Thanks, Philip Bock

Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Edgar Toernig
Philip Bock wrote:
>
> Is there any way for an anonymous function to call itself?

Only via the debug interface.

But your problem is easier:

> For example, if I'm writing a table serializer, like this one:
>[...] 
> Is there any way to place the serialize_table function inside the 
> serialize function, so I don't have to pollute the global namespace,
> but still let it call itself?

Make it local - either at the global scope or within serialize.

> I suppose I could declare it local inside the serialize function,
> and then pass it as an argument to itself, but is there a less ugly
> way to do it?

You don't have to pass it as an argument.  A function is able to
access outer locals and the "local function" syntax makes sure that
the name is visible within the function.

  local function foo() ...foo()... end
  function bar() ...foo()... end

or, if foo wants to access locals or parameters of bar:

  function bar(xyz)
    local function foo() ...xyz...foo()... end
    ...foo()...
  end

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Philip Bock
Thanks! That's just what I needed to know.

Philip Bock


Edgar Toernig wrote:

Philip Bock wrote:

Is there any way for an anonymous function to call itself?


Only via the debug interface.

But your problem is easier:


For example, if I'm writing a table serializer, like this one:
[...] Is there any way to place the serialize_table function inside the serialize function, so I don't have to pollute the global namespace,
but still let it call itself?


Make it local - either at the global scope or within serialize.


I suppose I could declare it local inside the serialize function,
and then pass it as an argument to itself, but is there a less ugly
way to do it?


You don't have to pass it as an argument.  A function is able to
access outer locals and the "local function" syntax makes sure that
the name is visible within the function.

  local function foo() ...foo()... end
  function bar() ...foo()... end

or, if foo wants to access locals or parameters of bar:

  function bar(xyz)
    local function foo() ...xyz...foo()... end
    ...foo()...
  end

Ciao, ET.



Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Gabor Grothendieck-2
In reply to this post by Philip Bock
Philip Bock <phil <at> flamewars.org> writes:

> Is there any way for an anonymous function to call itself?

It seems your problem can be answered without addressing the
literal question you asked but just for the sake of
completing this, we could use fixed point combinator ideas
from computer science to create anonymous recursive
functions.

Try this:

1. define this utility function:

   Y = function(f) return f(f) end

2. define an anonymous function which is a function with
   argument f, say, that returns a function that is the same as
   the factorial function except that f(f) is written in place
   of the recursive function call.  

3. pass the anonymous function in #2 to Y. Y takes #2
   as an input and outputs the desired recursive factorial
   function.

For example,

   Y = function(f) return f(f) end

   print(Y(function(f)
      return function(n) 
         if (n == 0) then
            return 1
         else
            return n * f(f)(n-1)
         end
      end
   end)(3))

will print 3 factorial which is 6.

For more on this, check out

   http://okmij.org/ftp/Computation/fixed-point-combinators.html

and google for fixed point combinator for even more.

I know of one language that has a built in Recall function that 
will recursively call the function its called in to make it
easier to write anonymous recusrive functions.  I don't think Lua 
has such a facility but if it does someone might be able to point it 
out.



Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Bennett Todd
I don't know Lua well enough to answer for Lua, but in at least
one other language (that I do know well:-) I can answer it by
creating a lexical closure; let the anonymous function capture a
lexical variable that holds a copy of the reference to the anonymous
function.

-Bennett

Attachment: pgpdFVT01Q2rr.pgp
Description: PGP signature

Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Aaron Brown-2
Bennett wrote:

> I don't know Lua well enough to answer for Lua, but in at
> least one other language (that I do know well:-) I can
> answer it by creating a lexical closure; let the anonymous
> function capture a lexical variable that holds a copy of
> the reference to the anonymous function.

I don't know how deep you'd have to get into the language in
question to answer this, but wouldn't the function be
considered non-anonymous if a variable contained a reference
to it?

-- 
Aaron


Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Bennett Todd
2004-07-22T19:49:38 Aaron Brown:
> I don't know how deep you'd have to get into the language in
> question to answer this, [...]

I had no intent of trying to be mysterious, I'm _pretty_ sure my
answer was fairly language-neutral, and should apply to most
languages with anonymous functions and lexical closures.

But I specifically tested it with perl5 (attached).

> but wouldn't the function be considered non-anonymous if a
> variable contained a reference to it?

If there's no reference to it anywhere, it's dead code, cannot be
called. Non-anonymous functions are installed into the symbol table:

	sub foo {
		print "foo called, hooray!\n";
	}

	foo();

Anonymous functions have no entries in the language-maintained
symbol tables; instead, one or more references to them are held in
normal scalar variables; once the last such reference is lost, the
anonymous function is garbage collected.

	{
		my $fooptr = sub {
			print "this thing was called\n";
		};
		# At this point there is no named function,
		# but there is a scalar variable $fooptr containing
		# a ref to the function, which we can invoke:
		$fooptr->();
	}
	# This thing exists no more

The above construction of an anonymous function can't call itself,
which is the flavour of the problem I guessed that the OP might be
asking about. The assignment to $fooptr only completes when the
"evaluation" (construction of the anon function from a precompiled
wad o' code and a lexical frame) completes; hence, the $fooptr
created in the above assignment hasn't been created when the sub is
being constructed, so it's unable to refer to it.

To allow an anoymous function to call itself, you can use a lexical
closure to provide the ability to recurse:

	my $fooptr;
	{
		my $lexicalfooptr;

		$lexicalfooptr = sub {
			print "I am boring";
			$lexicalfooptr->();
		};

		$fooptr = $lexicalfooptr;
	}
	# $lexicalfooptr no longer exists in any symbol table, but
	# the anon function can still chase through it to recurse.
	# This call will take a while:
	$fooptr->();

$lexicalfooptr is a lexical variable in scope when the anon sub is
being constructed, so a handle to that lexical scalar is included in
the closure frame for the anon sub. The assignment only actually
completes, populating $lexicalfooptr, after the sub is constructed,
but that's Ok, since has a grip on the scalar that'll survive the
scalar going out of scope, it can collect the reference when it
actually need it to recurse.

-Bennett
#!/usr/bin/perl -w
use strict;

my $count10 = &count(10);
my $count5 = &count(5);

print for $count10->();
print for $count5->();
print for $count10->();
print for $count5->();

exit 0;

sub count ($) {
    my ($count) = @_;
    local *_;

    my $ret;
    $ret = sub {
	$_[0] = $count unless @_;
	return "\n" unless $_[0];
	return (" ", $_[0], $ret->($_[0]-1));
    };
    return $ret;
}

Attachment: pgpiAG5bJlWTp.pgp
Description: PGP signature

Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Aaron Brown-2
Bennett wrote:

> To allow an anoymous function to call itself, you can use
> a lexical closure to provide the ability to recurse:

If I understand what you're doing (maybe I don't, since I
don't know Perl) then the equivalent in Lua would be:

  local foo
  do
    lexicalfoo = function()
      print "I am boring"
      lexicalfoo()
    end -- lexicalfoo
    foo = lexicalfoo
  end -- do
  foo()

When foo is called, lexicalfoo no longer exists.

But it seems to me that the whole point of asking whether
anonymous functions can recurse is to find out whether they
can recurse without giving them names.  Of course a function
will be able to recurse if you give it a name and use that
name to make the recursive call.

-- 
Aaron



Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Rici Lake-2
In reply to this post by Aaron Brown-2

On 22-Jul-04, at 2:49 PM, Aaron Brown wrote:

I don't know how deep you'd have to get into the language in
question to answer this, but wouldn't the function be
considered non-anonymous if a variable contained a reference
to it?

I suppose we could distinguish between anonymous functions and
pronominal functions. The use case, in some hypothetical language,
would be something like this:

factorials = map(function(i)
                   if i > 1 then return i * me(i - 1)
                            else return 1
                   end
                 end,
                 myList)

where me is a pronominal reference to the enclosing function.

I'd be inclined to say that this style of programming is not particularly readable, but others may disagree :) In any event,
the Lua idiom would be:

do
  local function fact(i) ... end
  factorials = map(fact, myList)
end

<digression for="Bennett">
  This is exactly equivalent to:

  do
    local fact
    fact = function(i) ... end
    factorials = map(fact, myList)
  end
</digression>

Although some might call such a function "anonymous", this doesn't
seem to capture Lua's semantics, In some sense, all Lua objects are
anonymous (in the sense that no Lua object has an intrinsic name),
But one could say that a function was anonymous in a compilation unit if it had no named reference visible in that compilation unit, which would apply, for example, to:

  map(function(i) return i + 1 end, myList)

Clearly, if a function is going to call itself it needs to have a named reference to itself, so no recursive function could truly be anonymous in that sense; however, the "me" formulation above might be considered a halfway house -- hence "pronominal"

The infamous Y combinator is another halfway house, in the sense that the function happens to be recursive but doesn't really know that it is.

R


Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Rafael Sabbagh Armony-2
> Although some might call such a function "anonymous", this doesn't
> seem to capture Lua's semantics, In some sense, all Lua objects are
> anonymous (in the sense that no Lua object has an intrinsic name),
> But one could say that a function was anonymous in a compilation unit
> if it had no named reference visible in that compilation unit, which
> would apply, for example, to: (...)

Exactly.
In Lua, what we call the "name" of the function is actually the name of the
variable pointing to it.
Therefore, if there's a variable pointing to a function, it is not
anonymous.

----- Original Message ----- 
From: "Rici Lake" <[hidden email]>
To: "Lua list" <[hidden email]>
Sent: Thursday, July 22, 2004 5:38 PM
Subject: Re: Recursive anonymous functions?


>
> On 22-Jul-04, at 2:49 PM, Aaron Brown wrote:
>
> > I don't know how deep you'd have to get into the language in
> > question to answer this, but wouldn't the function be
> > considered non-anonymous if a variable contained a reference
> > to it?
>
> I suppose we could distinguish between anonymous functions and
> pronominal functions. The use case, in some hypothetical language,
> would be something like this:
>
> factorials = map(function(i)
>                     if i > 1 then return i * me(i - 1)
>                              else return 1
>                     end
>                   end,
>                   myList)
>
> where me is a pronominal reference to the enclosing function.
>
> I'd be inclined to say that this style of programming is not
> particularly readable, but others may disagree :) In any event,
> the Lua idiom would be:
>
> do
>    local function fact(i) ... end
>    factorials = map(fact, myList)
> end
>
> <digression for="Bennett">
>    This is exactly equivalent to:
>
>    do
>      local fact
>      fact = function(i) ... end
>      factorials = map(fact, myList)
>    end
> </digression>
>
> Although some might call such a function "anonymous", this doesn't
> seem to capture Lua's semantics, In some sense, all Lua objects are
> anonymous (in the sense that no Lua object has an intrinsic name),
> But one could say that a function was anonymous in a compilation unit
> if it had no named reference visible in that compilation unit, which
> would apply, for example, to:
>
>    map(function(i) return i + 1 end, myList)
>
> Clearly, if a function is going to call itself it needs to have a named
> reference to itself, so no recursive function could truly be anonymous
> in that sense; however, the "me" formulation above might be considered
> a halfway house -- hence "pronominal"
>
> The infamous Y combinator is another halfway house, in the sense that
> the function happens to be recursive but doesn't really know that it
> is.
>
> R
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Wim Couwenberg-4
In reply to this post by Gabor Grothendieck-2
Maybe a more Lua-friendly way to write Gabor's
proposal would be the function `reflect':

function reflect(f)
	local function me(...)
		return f(me, unpack(arg))
	end
	return me
end

With this helper you can easily express recursive
functions, but you must introduce an additional first
argument:

fac = reflect(function(me, n)
	if n == 0 then
		return 1
	else
		return n*me(n - 1)
	end
end)

for i = 0, 10 do
	print(i, fac(i))
end

Of course, in this example the first thing I do is to
give the anonymous function a name, but anyway...

--
Wim




	
		
__________________________________
Do you Yahoo!?
Vote for the stars of Yahoo!'s next ad campaign!
http://advision.webevents.yahoo.com/yahoo/votelifeengine/

Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Gabor Grothendieck-2
In reply to this post by Gabor Grothendieck-2
Gabor Grothendieck <ggrothendieck <at> myway.com> writes:

: 
: Philip Bock <phil <at> flamewars.org> writes:
: 
: > Is there any way for an anonymous function to call itself?
: 
: I know of one language that has a built in Recall function that 
: will recursively call the function its called in to make it
: easier to write anonymous recusrive functions.  I don't think Lua 
: has such a facility but if it does someone might be able to point it 
: out.

I've done a bit of reading on Lua since my first post and 
it seems it is possible to define Recall using the
facilities already present in Lua.  Note that Recall is
what some other posters referred to as me.

For example, we can invoke the anonymous factorial function 
evaluating it for the argument 3 like this:

   Recall = function(...) return debug.getinfo(2,"f").func(unpack(arg)) end

   print((function(x)
      if x == 0 then
         return 1
      else
         return x * Recall(x-1)
      end
   end)(3))




Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Rici Lake-2

On 22-Jul-04, at 9:31 PM, Gabor Grothendieck wrote:

For example, we can invoke the anonymous factorial function
evaluating it for the argument 3 like this:

   Recall = function(...)
     return debug.getinfo(2,"f").func(unpack(arg))
   end

The use of the debug library is not advisable, unless you are actually debugging. Furthermore, this will not work on the tail-recursive implementation of factorial:

print ((function(x, acc)
          if x <= 1 then return acc
                    else return Recall(x - 1, x * acc)
          end
        end) (3, 1))

stdin:1: attempt to call field `func' (a nil value)
stack traceback:
        stdin:1: in function `Recall'
        (tail call): ?
        stdin:5: in main chunk
        [C]: ?


---------- Just to confirm:
do
  local function fact(x, acc)
    if x <= 1 then return acc
              else return fact(x - 1, x * acc)
    end
  end
  for i = 1, 10 do print(fact(i, 1)) end
end
==>
1
2
6
24
120
720
5040
40320
362880
3628800


Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Gabor Grothendieck-2
Rici Lake <lua <at> ricilake.net> writes:

: 
: On 22-Jul-04, at 9:31 PM, Gabor Grothendieck wrote:
: >
: > For example, we can invoke the anonymous factorial function
: > evaluating it for the argument 3 like this:
: >
: >    Recall = function(...)
: >      return debug.getinfo(2,"f").func(unpack(arg))
: >    end
: 
: The use of the debug library is not advisable, unless you are actually 
: debugging. Furthermore, this will not work on the tail-recursive 
: implementation of factorial:
: 
: print ((function(x, acc)
:            if x <= 1 then return acc
:                      else return Recall(x - 1, x * acc)
:            end
:          end) (3, 1))
: 
: stdin:1: attempt to call field `func' (a nil value)

That's too bad; however, one can still do it in a consistent,
but uglier, way for both examples by using 

   debug.getinfo(1,"f").func

inline like this:

   print ((function(x)
           if x == 0 then return 1
                     else return x * debug.getinfo(1,"f").func(x - 1)
           end
         end) (3, 1))
  
   print ((function(x, acc)
           if x <= 1 then return acc
                     else return debug.getinfo(1,"f").func(x - 1, x * acc)
           end
         end) (3, 1))





Reply | Threaded
Open this post in threaded view
|

Re: Recursive anonymous functions?

Gabor Grothendieck-2
Gabor Grothendieck <ggrothendieck <at> myway.com> writes:

: 
: Rici Lake <lua <at> ricilake.net> writes:
: 
: : 
: : On 22-Jul-04, at 9:31 PM, Gabor Grothendieck wrote:
: : >
: : > For example, we can invoke the anonymous factorial function
: : > evaluating it for the argument 3 like this:
: : >
: : >    Recall = function(...)
: : >      return debug.getinfo(2,"f").func(unpack(arg))
: : >    end
: : 
: : The use of the debug library is not advisable, unless you are actually 
: : debugging. Furthermore, this will not work on the tail-recursive 
: : implementation of factorial:
: : 
: : print ((function(x, acc)
: :            if x <= 1 then return acc
: :                      else return Recall(x - 1, x * acc)
: :            end
: :          end) (3, 1))
: : 
: : stdin:1: attempt to call field `func' (a nil value)
: 
: That's too bad; however, one can still do it in a consistent,
: but uglier, way for both examples by using 
: 
:    debug.getinfo(1,"f").func
: 
: inline like this:
: 
:    print ((function(x)
:            if x == 0 then return 1
:                      else return x * debug.getinfo(1,"f").func(x - 1)
:            end
:          end) (3, 1))
: 
:    print ((function(x, acc)
:            if x <= 1 then return acc
:                      else return debug.getinfo(1,"f").func(x - 1, x * acc)
:            end
:          end) (3, 1))

Here is a slight improvement.  If one defines Recall to return the 
function, itself, rather than the function evaluated, then Recall can
still be used in both the non-tail recursion and tail recursion cases
like this:

   Recall = function() return debug.getinfo(2,"f").func end

   print ((function(x)  -- non-tail recursion example
      if x == 0 then return 1
         else return x * Recall()(x-1)
      end
   end) (3))
  
   print((function(x, acc) -- tail recursion example
           if x <= 1 then return acc
              else 
                 local Recall = Recall()
                 return Recall(x - 1, x * acc)
           end
       end)(3,1))


We could have made this entirely symmetric by writing the
non-tail recursion case using the local redefinition of
Recall, as well, like this:

   print ((function(x)  -- non-tail recursion version 2
      if x == 0 then return 1
         else
            local Recall = Recall() 
            return x * Recall(x-1)
      end
   end) (3))