Chia sẻ qua

TinyRPN Calculator

  • Bài viết

It’s fun dorking around with the HP 41CX emulator on the iPhone. It’s a near-perfect rendition. I forgot how much I loved RPN calculators. The 48GX looks even more interesting with Reverse Polish Lisp but I haven’t figured out how to use it yet. The 41CX, on the other hand, is an old friend. :-)

clip_image002

Until you get used to it, RPN can be pretty strange. For example, let’s try calculating:

image

Working from the inside out, pressing: [1] [Enter] [2] [+] , then [4] [×] and [2] [÷] [4] [2] [+] , we get 48. With postfix operators and doing things in the right order, very seldom must you resort to storing and recalling to memory. It takes some getting used to but it’s a nice way to work.

The "VM"

This is a simple stack machine. Arguments are pushed onto a stack and instructions are applied that pop arguments, do some work, and push the result back. For example, the binary addition operator pops two numbers and pushes their sum. More generally, instructions can be thought of as functions that take a stack and return a stack. A cons list is essentially a stack, so the signature is: ('a list -> 'a list).

A program then consist of a list of these stack functions. The machinery to execute such a sequence of operations, threading a value-stack though, is really just a fold of function application – applying each instruction to the stack and threading the results through:

let execute = Seq.fold (|>)

To construct a simple RPN calculator, first we need to define each of the basic mathematic operators (+, -, ×, ÷). These are all binary operators that pop two arguments, apply a function and push the result. So let’s first define a higher order binary operator creation function.

let binary f = function _ :: a :: b :: t -> f b a :: t

We ignore the top value, assuming it’s a zero. Now we can make operators matching the ('a list -> 'a list) signature by supplying a simple binary function:

let add = binary (+) let
subtract = binary (-) let
multiply = binary (*) let divide = binary (/)

Next we need an instruction to represent digit input:

let digit v = function x :: t -> 10 * x + v :: t

We pop the current top value (x) and push back 10x + v. Just like the real calculator, pressing multiple digits in succession builds up a decimal number; assuming that 0 is on the stack initially.

We also need to be able to press [Enter] to complete entry of a decimal number; simply pushing a 0:

let enter s = 0 :: s

Now given a “program” (such as [digit 4; digit 2 enter; digit 5; add]) this stack machine pretty much runs itself! That’s the whole machine! What is that, eight lines of code? Not bad…

The "Compiler"

Maybe we’d like to make a little textual language for driving this thing. Perhaps just mapping programs such as “42 5 +” to the sequence of operations we just did. First, let’s map characters to operations:

let codes =
    Map.of_list [
        '0', digit 0
        '1', digit 1
        '2', digit 2
        '3', digit 3
        '4', digit 4
        '5', digit 5
        '6', digit 6
        '7', digit 7
        '8', digit 8
        '9', digit 9
        '+', add
        '-', subtract
        '*', multiply
        '/', divide
        ' ', enter]

Then we can make a little one-line “compiler” that takes a string and constructs a sequence of proper operators to feed into execute:

let compile = flip Map.find codes |> Seq.map

Done! (BTW, ‘flip’ is a just let flip f a b = f b a) Now, maybe a little helper function to take a program, compile and execute it and return the answer from the stack:

let eval = compile >> execute [0] >> Seq.hd

The "IDE"

And hey, we wouldn’t be complete without a REPL:

let rec repl () = System.Console.ReadLine() |> eval |> printf "%i\n>" |> repl
printf "Welcome to TinyRPN\n>"
repl ()

Perfect. Who needs a 41CX?

Welcome to TinyRPN
>1 2 + 4 * 2 / 42 +
48

Sweet!

Comments

  • Anonymous
    March 02, 2010
    JavaScript version:   function binary(f) {       return function(s) {           s.pop();           var b = s.pop();           var a = s.pop();           s.push(f(a, b));           return s;           }   }   var add = binary(function(a, b) { return a + b; });   var subtract = binary(function(a, b) { return a - b; });   var multiply = binary(function(a, b) { return a * b; });   var divide = binary(function (a, b) { return a / b; });   function digit(v) {       return function(s) {           s.push(10 * s.pop() + v);           return s;       }   }   function enter(s) {       s.push(0);       return s;   }   var codes = {       '0': digit(0),       '1': digit(1),       '2': digit(2),       '3': digit(3),       '4': digit(4),       '5': digit(5),       '6': digit(6),       '7': digit(7),       '8': digit(8),       '9': digit(9),       '+': add,       '-': subtract,       '*': multiply,       '/': divide,       ' ': enter,   }       function compile(source) {       var code = new Array();       for (var i in source)           code.push(codes[source[i]]);       return code;   }   function exec(source) {       var stack = [0];       var program = compile(source);       for (var i in program)           stack = programi;       return stack;   }