See Mastering Algorithms with Perl, p.47 to p.71.

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

The interpreter mentioned in Lisp-In-Perl implements them as two arrays. One for all the 'car|down' nodes, and one for all the 'cdr|right' nodes. But then the nodes don't free themselves when they are no longer being referenced. A garbage collector has to periodically compact the arrays.

Update: I did a rough benchmark of memory used by the two methods, and using array refs used ~3-4 times more memory. Is this because perl over-allocates whenever it allocates an array? Since you can pre-extend an array you know will be large, would it help if it were possible to pre-de-extend an array you know will be small? Here's the code I used (for comments on the fairness of the comparisons):

my @arr;
my @arr1;
my @arr2;
my $i=0;
for (1..1_000_000) {
 # This
 #push @arr, [undef, undef];
 # Or this
 push @arr, [++$i, ++$i];

 # Vs. this:
 #push @arr1, undef;
 #push @arr2, undef;
 # Or this:
 #push @arr1, ++$i;
 #push @arr2, ++$i;
}

print "Done\n";
# Then just do a 'ps -lu runrig' at another command prompt when I get 
+here
my $str=<STDIN>;
[download]

Jeff

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
F--F--F--F--F--F--F--F--
(the triplet paradiddle)