a(nother) Reverse Polish Notation Calculator

pmichaud on 2009-03-02T19:41:55

In a Reverse Polish Notation Calculator, fREW Schmidt takes the RPN calculator example from Higher Order Perl and converts it over to Perl 6.

Very cool.

But as usual, I visually look at the Perl 6 version compared to the Perl 5 version and think "Can't we do better?" In this case, we can. Here's my version of the same code:

    my %op_dispatch_table = {
        '+'    => { .push(.pop + .pop) },
        '-'    => { my $s = .pop; .push(.pop - $s) },
        '*'    => { .push(.pop * .pop) },
        '/'    => { my $s = .pop; .push(.pop / $s) },
        'sqrt' => { .push(.pop.sqrt) },
    };

    sub evaluate (%odt, $expr) {
        my @stack;
        my @tokens = $expr.split(/\s+/);
        for @tokens {
            when /\d+/     { @stack.push($_); }
            when ?%odt{$_} { %odt{$_}(@stack); }
            default        { die "Unrecognized token '$_'; aborting"; }
        }
        @stack.pop;
    }

    say "Result: { evaluate(%op_dispatch_table, @*ARGS[0]) }";

The result:

$ ./perl6 calc.pl '5 6 +'
Result: 11

The major changes I made to fREW's code:

1. Convert the explicit subs into simple closures, assuming that the stack is the implicit topic. 2. Use 'when' statements instead of if/elsif/else in the body of the 'evaluate' sub.

And yes, as frew points out -- when we get the 'R' metaoperator in place we can get rid of the 'my $s = ...' parts of subtraction and division. Maybe I'll implement meta-R now... :-)

Thanks fREW for the very interesting example!

Pm

Update: I went ahead and implemented the R metaoperator. For those who aren't familiar with meta-R, it reverses the order of the operands to an operator. So, (5 R- 4) is the same as (4 - 5), and (2 R/ 10) is the same as (10 / 2). With this change, the RPN calculator becomes:

    my %op_dispatch_table = {
        '+'    => { .push(.pop + .pop)  },
        '-'    => { .push(.pop R- .pop) },
        '*'    => { .push(.pop * .pop)  },
        '/'    => { .push(.pop R/ .pop) },
        'sqrt' => { .push(.pop.sqrt)    },
    };

    sub evaluate (%odt, $expr) {
        my @stack;
        my @tokens = $expr.split(/\s+/);
        for @tokens {
            when /\d+/     { @stack.push($_); }
            when ?%odt{$_} { %odt{$_}(@stack); }
            default        { die "Unrecognized token '$_'; aborting"; }
        }
        @stack.pop;
    }

    say "Result: { evaluate(%op_dispatch_table, @*ARGS[0]) }";

---

Wow!

frew on 2009-03-02T20:12:05

That's much more compact! I'll try to absorb these changes so that next time I make a post about perl6 it will be closer to The Essence of Perl 6. :-)

Making it even more compact...

amahabal on 2009-03-03T04:14:09

I don't know how to do this, but I am sure Patrick or Jonathan can do this quickly...

In the code above, there is still repetition: all entries in %op_dispatch_table are nearly identical, differing only depending on the arity. We could replace that with something generic which is passed a sub, it pops as many elements as the arity of the passed sub and pushes back the value of applying the sub to the reverse of this list.

I was unable to do this myself because I could not get from the name of the sub to the callable object (I tried &($name), but got a message that it is unimplemented).

Re:Making it even more compact...

pmichaud on 2009-03-03T15:09:21

Yes, it could potentially be made slightly shorter... but I like the straightforward clarity of the above. An advantage of the above approach is that it would work for almost any stack pattern -- including things that don't fit the ".push( fn(.pop) )" model. For example, to add a 'say' operator that displays the top value of the stack (without removing it):

    'say' => { .[*-1].say }

I can also imagine functions that rotate or swap the top N operands, or the like. Trying to wedge those into a standard .push/.pop sequence seems a little less straightforward than what we have above.

I'd still be interested in seeing the solution you have in mind, even if Rakudo doesn't compile/run it yet. In fact, we'd be a bit more likely to make it do that if we had an example to work to. :-)

Thanks!

Pm

Re:Making it even more compact...

amahabal on 2009-03-03T18:58:57

I have one version here:

http://use.perl.org/user/amahabal/journal/38583

Thanks to your suggestion, I added 'say' and 'rotate3'. I will try my original idea next, for which I need to go from a name (such as 'double') to a callable object (&double). Not sure yet what I'd do with multis and such, but I will see how far I get.