Re: Recursive anonymous functions?

[Bennett Todd <bet@...>]

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: pgp36pAf6l2Ph.pgp
Description: PGP signature