DEMO: recursive closures for graph traversal 
Author Message
 DEMO: recursive closures for graph traversal

I was trying to come up with a way of writing functions that work like
map{} or grep{}, so that the function would be applied to each of a
bunch of things, with $_ holding the current thing each time.

For example, suppose you had a network of nodes representing
a house, or a dungeon.  You might want to do something like
this:

    graph_walk { print $_->{VALUE}, "\n" } $kitchen;

In graph traversal, you have to keep track of nodes visited,
so you don't just keep running around the house in circles.
I wanted to do this without having an extra helper function
and a local(%seen) or an extra argument.  So I pulled something
out with recursive closures.

One thing that's interesting here is not the use of recursive
closures, but how tremendously easier it is to build fancy data
structures in Perl than in something like C, C++, or Java.
You don't need classes.  You don't need objects.  You don't
need fancy allocators.  It just all falls out.

The fact that a graph is circular means that for garbage you would
need to cloak it in a blessed non-selfreferential object box with
a destructor to sever the links if you cared not to leak.

But it's still darned easy.  Think of the pain of doing this in C.

--tom

# recursive closure demo for a graph traversal

sub graph_walk (&$)
{
    my $nodefunc = shift;
    local $_     = shift;       # nodefunc wants this here
    my %seen     = ();
    my $walker;

    $walker = sub {
        local $_     = shift;   # nodefunc wants this here
        return if $seen{$_}++;
        $nodefunc->();       # this will use $_

            $walker->($neighbor);  
        }
    };

    $walker->($_);

Quote:
}

sub add_node {



    return $newnode;

Quote:
}

sub add_value {

    my $newnode = {
        VALUE => $value,
        LINKS => [],
    };
    return add_node($oldnode, $newnode);

Quote:
}

$foyer = {
    VALUE => "Foyer",
    LINKS => [],

Quote:
};

$hall    = add_value($foyer, "Hallway");
$bedroom = add_value($hall, "Bedroom");
           add_value($bedroom, "Bathroom");
$kitchen = add_value($hall, "Kitchen");
$living  = add_value($hall, "Living Room");
           add_node($kitchen, $living);

print "Starting from foyer:\n";
graph_walk { print $_->{VALUE}, "\n" } $foyer;

print "\nStarting from kitchen:\n";
graph_walk { print $_->{VALUE}, "\n" } $kitchen;

exit;

__END__

--
Emacs is a fine operating system, but I still prefer UNIX. -me



Fri, 03 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
[A complimentary Cc of this posting was sent to Tom Christiansen


Quote:
>     my $walker;

>     $walker = sub {
>    local $_     = shift;   # nodefunc wants this here
>    return if $seen{$_}++;
>    $nodefunc->();       # this will use $_

>        $walker->($neighbor);  
>    }
>     };

I find this confusing.  I prefer the places like this explicitly
marked, as in

   my $walker;               # Should be on a separate line to scope $walker

   $walker = sub {
     local $_     = shift;   # nodefunc wants this here
   ...

Ilya



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
In comp.lang.perl.moderated, you write:

Quote:
> sub graph_walk (&$)
> {
>     my $nodefunc = shift;
>     local $_     = shift;       # nodefunc wants this here
>     my %seen     = ();
>     my $walker;

>     $walker = sub {
>        local $_     = shift;    # nodefunc wants this here
>        return if $seen{$_}++;
>        $nodefunc->();       # this will use $_

>           $walker->($neighbor);  
>        }
>    };

>    $walker->($_);
> }

Pretty Darn Cool.  I can definitely think of some places to use this
technique in my own code, thanks!

A slight optimization:  Since $seen{$_} will always be false on the first
call to walker, it's safe to do the "seen" test inside the for loop.  The
result isn't as elegant, but may be a smidgen faster:

   $walker = sub {
      local $_    = shift;       # nodefunc wants this here
      $nodefunc->();       # this will use $_

         $walker->($neighbor)
            unless $seen{$neighbor}++;
      }

BTW, is it necessary to localize $_ inside each invocation of walker?  Isn't
the localization in graph_walk sufficient?  Why does the following seem to
work just as well...?

sub graph_walk (&$)
{
   my $nodefunc = shift;
   local $_     = shift;       # nodefunc wants this here
   my %seen     = ();
   my $walker;

   $walker = sub {

   };

   $walker->($_);

Quote:
}

--Todd


Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
 [courtesy cc of this posting sent to cited author via email]

In comp.lang.perl.moderated,

:In comp.lang.perl.moderated, you write:
:> sub graph_walk (&$)
:> {
:A slight optimization:  Since $seen{$_} will always be false on the first
:call to walker, it's safe to do the "seen" test inside the for loop.  The
:result isn't as elegant, but may be a smidgen faster:

Yes, it should be faster without the return.

:BTW, is it necessary to localize $_ inside each invocation of walker?  Isn't
:the localization in graph_walk sufficient?  Why does the following seem to
:work just as well...?

The $_ only needs localizing for the call to the user operation,
nothing more.  Here is a version of the code slightly rearranged
based on your suggestions, and made more legible by restricting
where $_ is used, preferring real variable names elsewhere.

sub graph_walk (&$)
{
    my $_Nodefunc = shift;      # per-node user operation
    my $graph     = shift;      # starting point in network
    my %_Seen     = ();         # whether each node was visited
    my $walker;                 # IMPORTANT: leave on line by itself

    # Create recursive closure.  Enclosed variables are marked
    # with a leading under and capital.  Can't assign to $walker
    # directly when it is my()ed, because it doesn't yet exist
    # on the right-hand-side.  So keep compile-time declaration
    # and run-time assignment separate, which is usually unneeded.

    $walker = sub {             # so that this gets scoped right
        my $node = shift;       # walker gets graph-node argument
        {                       # call user func *first* on this node
            local $_ = $node;   # dynamic local here because the
            $_Nodefunc->();          #   user code uses $_, like map{}
        }

        # Each node in a network connects to N other nodes
        # where N may be 0.  Recursively visit all those
        # nodes linked to this one, but only if we haven't
        # already done so.


            $walker->($neighbor) unless $_Seen{$neighbor}++;
        }

    };

    $walker->($graph);               # begin the recursive descent

Quote:
}

--tom
--
Unix is like a toll road on which you have to stop every 50 feet to
pay another nickel.  But hey!  You only feel 5 cents poorer each time.



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal

Quote:

> local $_     = shift;   # nodefunc wants this here

That localization business makes me nervous. What if graph_walk is ever
used in multithreading context? Are $_, $a, $b and consorts
thread-local?

Jean-Louis Leroy
http://ourworld.compuserve.com/homepages/jl_leroy



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
[A complimentary Cc of this posting was sent to Tom Christiansen


Quote:
>     $walker = sub {                # so that this gets scoped right
>    my $node = shift;       # walker gets graph-node argument
>    {                       # call user func *first* on this node
>        local $_ = $node;   # dynamic local here because the
>        $_Nodefunc->();          #   user code uses $_, like map{}
>    }

...
>     $walker->($graph);          # begin the recursive descent

I still do not see why localization is needed in the loop.  Per Todd's
suggestion, why not

    $walker = sub {             # so that this gets scoped right
        my $node = shift;       # walker gets graph-node argument
        $_ = $node;             # user code uses $_, like map{}
        $_Nodefunc->();         # call user func *first* on this node
...

    local $_;
    $walker->($graph);          # begin the recursive descent

Ilya



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal

writes:

Quote:
> I still do not see why localization is needed in the loop.  Per Todd's
> suggestion, why not

>     $walker = sub {             # so that this gets scoped right
>         my $node = shift;       # walker gets graph-node argument
>    $_ = $node;             # user code uses $_, like map{}
>         $_Nodefunc->();         # call user func *first* on this node
> ...
>     local $_;
>     $walker->($graph);          # begin the recursive descent

I think that's right -- after all, $_ is just any old global scalar for
purposes here...so it only needs saving once.  Here's a revised and version
taking this into account and also taking a second callback function
returning a list of links for a given node (to make it more generic):

sub graph_walk (&&$)
{

   my %seen = ();  # Tracks visited nodes.
   my $walk;       # Recursive function (keep declaration on separate line).
   local $_;       # Save $_ because we overwrite it below.


   $walk->($start);

Quote:
}


(no real need to set it explicitly).  To call this version, use "sub"
keywords and commas because there are two &'s in the prototype:

print "Starting from foyer:\n";
graph_walk sub { print $_->{VALUE}, "\n" },

           $foyer;

print "\nStarting from kitchen:\n";
graph_walk sub { print $_->{VALUE}, "\n" },

           $kitchen;

But I don't like having to put the "sub" and the comma there.  Tom's
original version with plain grep-like blocking was really cool.  So here's
an even simpler version which does all of that:

sub graph_walk (&$)
{

   my %seen = ();  # Tracks visited nodes.
   my $walk;       # Recursive function (keep declaration on separate line).
   local $_;       # Save $_ because we overwrite it below.


   $walk->($start);

Quote:
}

To call it:

print "Starting from foyer:\n";

print "\nStarting from kitchen:\n";

Damn, is that terse.  All praise Perl, amen.

--Todd



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal


Quote:

>> local $_     = shift;   # nodefunc wants this here

>That localization business makes me nervous. What if graph_walk is ever
>used in multithreading context? Are $_, $a, $b and consorts
>thread-local?

$_ is automatically per-thread.
$a and $b are if and only if they are "my" variables, as usual.
(You can't help the symtable $a and $b used by sort() though so
you'd have to serialise sorting by choosing something to lock().)

--Malcolm

--

Oxford University Computing Services
"I permitted that as a demonstration of futility" --Grey Roger



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal

Quote:

> Then there is no need to localize $_ explicitly.

Well I'll be darned!  yes, that's right! -- because the call to graph_walk
automatically preserves the old value.  Excellent -- once again Perl lives up
to its well-deserved reputation of doing the right thing when you need it to.

Quote:
> And since walk takes a list of things, there is no need to restrict
> graph_walk to one argument.
> [...code snipped...]
> (Not tested.)

Much cool.  Code looks correct to me, and seems to run OK too.  One last turn
of the crank then:  fold in the other callback paradigm in which the callback
function "does its thing" for the node passed to it and then returns a list of
links from that node all in one shot:

sub graph_walk (&$)
{
   my ($exec, %seen) = (shift);  # %seen tracks visited nodes.
   my $walk;  # Recursive function (keep declaration on separate line).


   &$walk;

Quote:
}


Quote:
> And you do not need one of the trailing semicolons on $walk line.

(hee) nor those wasteful spaces, comments, and long variable names.


--Todd



Sat, 04 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
[A complimentary Cc of this posting was sent to Todd Lehman


Quote:
> sub graph_walk (&&$)
> {

>    my %seen = ();  # Tracks visited nodes.
>    my $walk;       # Recursive function (keep declaration on separate line).
>    local $_;       # Save $_ because we overwrite it below.


>    $walk->($start);
> }


> (no real need to set it explicitly).

Then there is no need to localize $_ explicitly.  And since walk takes
a list of things, there is no need to restrict graph_walk to one argument.


    my ($exec, $links, %seen) = (shift, shift);  # %seen tracks visited nodes.
    my $walk;       # Recursive function (keep declaration on separate line).


    &$walk;
 }

(Not tested.)  And you do not need one of the trailing semicolons on
$walk line.

Ilya



Sun, 05 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal

Quote:
> Well I'll be darned!  yes, that's right! -- because the call to graph_walk
> automatically preserves the old value.  [...]


Quote:
> [...]

>    &$walk;

Hey!  That assignment and that call can even be mrfled together!--


Thus maketh that this:


Creepy.

--Todd



Sun, 05 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal
Wait a minute? sort is not thread safe? I can't have two threads sorting
at the same time? What am I missing here?

<snip>

Quote:
> $_ is automatically per-thread.
> $a and $b are if and only if they are "my" variables, as usual.
> (You can't help the symtable $a and $b used by sort() though so
> you'd have to serialise sorting by choosing something to lock().)

> --Malcolm

--
Matthew O. Persico
http://www.erols.com/mpersico
http://www.digistar.com/bzip2


Sun, 05 Aug 2001 03:00:00 GMT  
 DEMO: recursive closures for graph traversal

Quote:

> $_ is automatically per-thread.

On second thought, not many scripts would work if $_ were not per-thread...

Quote:
> $a and $b are if and only if they are "my" variables, as usual.
> (You can't help the symtable $a and $b used by sort() though so
> you'd have to serialise sorting by choosing something to lock().)

That's scary. It makes it difficult to write a module that uses sort() and
is works (safely) in both threaded and non-threaded Perl.

Perhaps sort() could automatically serialize itself in threaded Perl? Or
better, could $a and $b become thread-local for the duration of the sort?

Jean-Louis Leroy
http://ourworld.compuserve.com/homepages/jl_leroy



Mon, 06 Aug 2001 03:00:00 GMT  
 
 [ 17 post ]  Go to page: [1] [2]

 Relevant Pages 

1. DEMO: recursive closures for graph traversal

2. Advice need on recursive traversal of complex data structures

3. Advice need on recursive traversal of complex data structures

4. Graph::Traversal Problems

5. Recursive call in closure prevents Filehandle release

6. Newbie: Recursive data structure with recursive subroutine.

7. Recursive subroutine output to recursive subroutine problem

8. 3D Graphs for GD::Graph

9. ANNOUNCE: Graph.pm v0.9 graphing module

10. using Graph::Base to get graph components

11. Problem with the position of Y-axis in graphs plotted using GD::graph

12. GD::Graph (line graph visibility question)

 

 
Powered by phpBB® Forum Software