How to pass a tree data structure by reference in Perl?

Question

I am writing a script to solve very basic systems of equations. I convert the equations into binary expression trees, isolate the variable that I want the value of, and then do substitutions.

This is where I have a problem, I have a function "substitution" that walks the binary expression tree of the left side of the equation I want substituted. And when I found the variable to be substituted, I replace the node with the expression tree of another equation.

But when I try to return the new tree, my susbstitution is not there. It is obviously a pass-by-reference / pass-by-value problem but I cannot find the way to solve it.

Here's a side script that shows the part which doesn't work:

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

sub inorder {
    my $expression = shift;
    my $node = $expression;
    if ($node->{type} eq "operator") {
        print "(";
        inorder($node->{left});
        print $node->{value};
        inorder($node->{right});
        print ")";
    }
    else {
        print $node->{value};
    }
}

sub substitution {
    my ($inserted_equation, $master_equation) = @_;
    my $inserted_expression = $inserted_equation->{right_side};
    my $insertion_point     = $inserted_equation->{left_side}->{value};
    my $master_expression   = $master_equation->{right_side};

    my @stack_tree_walk;
    my $node = $master_expression;
    push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};

    while(@stack_tree_walk) {
        if ($node->{type} eq "variable" and $node->{value} eq $insertion_point) {
            foreach (@stack_tree_walk) {
                
            }

#           print $node->{value};
#           print Dumper $inserted_expression;
            $node = $inserted_expression;       # WORKS
#           print Dumper $node;                 # WORKS
#           print Dumper $master_expression;    # DOES NOT WORK
            pop @stack_tree_walk;
            $node = $stack_tree_walk[-1];
        }
        elsif ($node->{type} eq "operator") {
            if (not $stack_tree_walk[-1]->{left_visited}) {
                $stack_tree_walk[-1]->{left_visited} = 1;
                $node = $node->{left};
                push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};
            }
            elsif ($node->{side} eq "left") {
                $node = $node->{right};
                $stack_tree_walk[-1]->{side} = "right";
                push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};
            }
            else {
                pop @stack_tree_walk;
                $node = $stack_tree_walk[-1];
            }
        }
        else {
            pop @stack_tree_walk;
            $node = $stack_tree_walk[-1];
        }
    }
    return {right_side=>$master_expression, left_side=>$master_equation->{left_side}};
}


my $equation = {left_side => { type=> "variable",
                            value=> "y"},

                right_side=> { type=> "operator",
                            value=> "*",
                            left=> {type=> "variable", value=> "a"},
                            right=> {type=> "variable", value=> "b"} }

                };

my $insertion = {left_side => { type=> "variable" ,
                            value=> "a" },

                right_side=> { type=> "operator",
                            value=> "+",
                            left=> {type=> "variable", value=> "x"},
                            right=> {type=> "variable", value=> "y"} }
                };
$,="";
$\="";
print "equations before substitution\n";
inorder($equation->{left_side});
print "=";
inorder($equation->{right_side});
print "\n";
inorder($insertion->{left_side});
print "=";
inorder($insertion->{right_side});
print "\n";
print "------------------\n";

$,="\n";
$\="\n\n";
my $final = substitution($insertion, $equation);

$,="";
$\="";
print "------------------\n";
print "equation substituted\n";
inorder($final->{left_side});
print "=";
inorder($final->{right_side});
print "\n";

Here is the OUPUT:

    equations before substitution
    y=(a*b)
    a=(x+y)

    equation substituted
    y=(a*b)                     <==== this is the ERROR
    y=((x+y)*b)                 <==== this should be the RIGHT result

I hope someone can show me which part is wrong. Thank you.

Answer 1

$node is a essentially a pointer into the structure. Your code simply sets $node to a different pointer, i.e. $inserted_expression. You don't change the structure this way, you only change a local variable $node to point to different things. Basically you does this:

  $struct = { foo => { bar => 1 } };
  $node = $struct->{foo}; # points at { bar => 1 } in $struct
  $node = { bar => 2 }  # points at { bar => 2 } and not longer into $struct
  print(Dumper($struct)); # unchanged

If you want to change the value you in the struct you need to take a reference to the value and not just take the value, i.e.

  $struct = { foo => { bar => 1 } };
  $node = \$struct->{foo}; # reference to value of { foo => ... }, currently { bar => 1 }
  $$node = { bar => 2 }  # changes value of { foo => ... } to { bar => 2 }
  print(Dumper($struct)); # changed