Reverse Polish Notation

This is my first blog post regarding the Perl Weekly Challenge tirelessly maintained by Mohammad Anwar. Although I’ve been doing the challenge for a while now, I haven’t maintained my blog for years. Let’s change that!

This week’s challenge #2 from the Perl Weekly Challenge is a computer science classic: create a Reverse Polish Notation (RPN) calculator. This brings back fond memories.

Basic Algorithm

My Perl 5 and Raku solutions will both use the same basic algorithm. First, we tokenize the input into numbers and operators. Then, we loop through every token. For each token, we either:

1. If the token is a number, we add it to the stack
2. Otherwise, it’s an operator:
   1. Pull zero or more items off the stack depending on the operator
   2. Perform the required operation (e.g., addition, subtraction, etc.)
   3. Push the result onto the stack

Let’s start with Perl 5. Here’s a simple way to do it:

# Perl 5
for ( map { split } @ARGV ) {
    if (looks_like_number($_)) { push @stack, $_; }

    elsif ($_ eq '+')   { push @stack, (pop @stack) + (pop @stack) }
    elsif ($_ eq '-')   { push @stack, (pop @stack) - (pop @stack) }
    elsif ($_ eq '*')   { push @stack, (pop @stack) * (pop @stack) }
    elsif ($_ eq '/')   { push @stack, (pop @stack) / (pop @stack) }
    else                { die "Unknown operator: $_"; }
}
say @stack;

That works, but we can do better. The elsifs are clumsy, and we are repeating a lot of code. So instead, we’ll use a dispatch table along with a generator function to handle the stack manipulation for us:

my %op; # Dispatch table, stores CODE refs

sub op_install {
    my ($code, $op, $arity) = @_;
    $op{$op} = sub {
        die "Stack: @{[ 0+@stack ]} < $arity" if @stack < $arity;
        my @operands;
        push @operands, pop @stack for 1..$arity;
        $code->(@operands);
    }
}

That already handles operations of any arity, but we can give ourselves a little bit of added convenience:

sub nullary(&$) { my ($code, $op) = @_; op_install($code, $op, 0) }
sub   unary(&$) { my ($code, $op) = @_; op_install($code, $op, 1) }
sub  binary(&$) { my ($code, $op) = @_; op_install($code, $op, 2) }

And now instead of the long elsif chain, our main loop can simply call $op{$_}->() (or report unknown operator if $op{$_} does not exist).

Installing operations is no longer a repetitive chore, but something that actually felt satisfying to me. Satisfying enough I went a little overboard in my solution. Here are a few examples:

binary  { $_[0] **$_[1] } '^';
unary   { 1 / pop }       'inv';
nullary { 3.14159265359 } 'π';

$op{'×'} = $op{'*'}; # Aliases are easy
$op{'÷'} = $op{'/'};

Of course I then went completely off the deep end and added user variable support with the following short snippet:

for my $var ('a'..'z') {
    unary   { $vars{$var} = $_[0]; () } "$var=";
    nullary { $vars{$var} }              $var;
}

With that, you can do things like 11 n= 2 n n 1 + * / to calculate the 11th triangle number, for instance.

Truly, I’m having too much fun with this. So I’ll leave you now with a link to my solution on Github.

Raku Solution

My Raku solution uses the same basic algorithm as the Perl5 solution, including the dispatch table and generator function, but takes advantage of some new language features. Here is the generator:

#| Generate an operator and return a Code object
sub op-gen( &code --> Code ) {
    sub () {
        die "Stack: {@stack.elems} < {&code.arity}"
            if @stack < &code.arity;
        my @operands;
        @operands.push: @stack.pop for 1..&code.arity;
        @stack.push: |code( |@operands );
    }
}

The really nice thing about this new generator function is that we no longer need to specify the arity (either explicitly or implicitly as we did with the nullary, unary, and binary subs in the Perl 5 version). Everything is an object in Raku, and subs are no different. Raku gives us the ability to introspect the sub that is passed in and determine its arity automatically. Neat, huh?

Well, it gets even better, because that even works with placeholder variables, so we don’t have to specify a signature for every single sub we want to add to the dispatch table. Here are some examples:

%op<+> = op-gen( { $^a + $^b } ); # Binary
%op<-> = op-gen( { $^a - $^b } );
%op<!> = op-gen( {[*] 1..$^a } ); # Unary
%op<π> = op-gen( { 3.1415926 } ); # Nullary

Since Raku v6.d, it has been possible to use junctions as hash keys, so this works, too:

%op{"^"|"**"}  = op-gen( { $^a ** $^b } );
%op{"%"|"mod"} = op-gen( { $^a %  $^b } );

In the above examples, the “or” (union) junction results in multiple keys being added to the hash, pointing to the same result. So if you prefer to exponentiate with 2 3 ** or 2 3 ^, it works the same.