Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Binary Search Tree Debug Question

by bichonfrise74 (Vicar)
on Aug 12, 2011 at 18:01 UTC ( #920057=perlquestion: print w/replies, xml ) Need Help??
bichonfrise74 has asked for the wisdom of the Perl Monks concerning the following question:

This is from the Perl Cookbook Recipe 11.17 (Program: Binary Trees).
#!/usr/bin/perl use strict; use Data::Dumper; my $root; insert( $root, 5 ); insert( $root, 3 ); print Dumper \$root; sub insert { my ($tree, $value) = @_; unless ($tree) { $tree = {}; $tree->{VALUE} = $value; $tree->{LEFT} = undef; $tree->{RIGHT} = undef; $_[0] = $tree; # $_[0] is reference param! return; } if ( $tree->{VALUE} > $value ) { insert( $tree->{LEFT}, $value ) } elsif ( $tree->{VALUE} < $value ) { insert( $tree->{RIGHT}, $value + ) }; }
I am trying to understand the relevance of this line:
$_[0] = $tree;
He mentioned that this is a reference param. And also he mentioned that "The assignment of the new node back to $_[0] alters the value in its caller."

But I still don't get it. If I removed this line, I don't get any output.

I ran the debugger but to no avail, I still could not figure out what is the relevance of that line. Why did he write it? And is there another way to write it maybe a longer version?

Can someone help understand this? Thanks.

Replies are listed 'Best First'.
Re: Binary Search Tree Debug Question
by jdporter (Canon) on Aug 12, 2011 at 18:29 UTC

    Ok, you know that arguments are passed to subs in the special array @_. It just so happens that the actual elements of @_ are not simply copies of the actual argument values, but are aliases to them. If you were to do this:

    $x = 5; @a = ( $x ); $a[0] = 7; print $x; # prints 5
    $x remains unchanged, because $a[0] is completely separate from $x. The assignment of ( $x ) to @a copies the value (5).

    It's different with @_ when it's carrying the arguments of a sub call.

    $x = 5; foo( $x ); print $x; # prints 7 sub foo { $_[0] = 7; }
    That's because $_[0] is not separate from $x; in fact, it is an alias to it. The "assignment" of ( $x ) to @_ does not copy values; it sets up aliases.

    This behavior can be used to create "OUT" parameters; that is, parameters which can alter their arguments.

    (Note that the actual argument would have to be writable for this to work. If we called foo( 5 ); with the above code, we'd get a "Modification of a read-only value attempted" error.)

    I reckon we are the only monastery ever to have a dungeon stuffed with 16,000 zombies.
Re: Binary Search Tree Debug Question
by Perlbotics (Canon) on Aug 12, 2011 at 18:19 UTC

    When called for the first time, $root is undef. insert() detects that and creates a brand new initial node. By using $_[0], insert() accesses $root as an alias - and thus assignes the inital node to $root. So, when insert() returns, $root is no longer undef but a reference to the newly created hash.
    This is (one) perlish way to realise the concept of call by reference.

    Update: Quote from perlsub:

    Any arguments passed in show up in the array @_. Therefore, if you called a function with two arguments, those would be stored in $_[0] and $_[1]. The array @_ is a local array, but its elements are aliases for the actual scalar parameters. In particular, if an element $_[0] is updated, the corresponding argument is updated (or an error occurs if it is not updatable). If an argument is an array or hash element which did not exist when the function was called, that element is created only when (and if) it is modified or a reference to it is taken. (Some earlier versions of Perl created the element whether or not the element was assigned to.) Assigning to the whole array @_ removes that aliasing, and does not update any arguments.

Re: Binary Search Tree Debug Question
by FunkyMonk (Canon) on Aug 13, 2011 at 13:56 UTC
Re: Binary Search Tree Debug Question
by Anonymous Monk on Aug 12, 2011 at 19:19 UTC
    Thanks for explaining, I sort of understand now the concept.

    But is there a way to re-write the above code without using $_[0] = $tree?

    I think that would really help in solidifying my understanding with this.

      A few possibilities. Here are two. The first is a minor change to the code:

      my $root; insert( \$root, 5 ); insert( \$root, 3 ); #... sub insert { my ($treeref, $value) = @_; my $tree = $$treeref; unless ($$treeref) { $tree = {}; #... $$treeref = $tree; } #...
      This just makes it explicit that the variable being passed in (by reference) may be modified.

      Another possibility is to have a "create tree" function for when the tree doesn't exist yet, and returns the initialised tree, possibly with the first value being required. The insert function would then need to tell if the tree is pristine and not yet populated (if the first value isn't required during create) to determine whether a new node was needed or not. The create-tree function would construct the tree - so we could call it a constructor. And we're basically at OO, all you have to do is bless the return :-)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://920057]
Approved by toolic
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2017-05-28 18:58 GMT
Find Nodes?
    Voting Booth?