Skip to content

RPN calculator

Jump to bottom Edit New page
wangp edited this page May 21, 2017 · 1 revision

Let's use what we have covered so far in a somewhat realistic program, a calculator. For simplicity, we will implement an RPN-style calculator (Reverse Polish Notation) so we don't have to worry about parsing infix mathematical expressions.

The calculator has a working memory consisting of a stack of numbers. At each step, the calculator will display the stack then prompt the user for input. The user can enter a number to be pushed on top of the stack, or an arithmetic operation that pops arguments off the stack and pushes the result of the operation.

A sample run looks like this:

Current stack (top to bottom): empty
> 3
Current stack (top to bottom): 3
> 17
Current stack (top to bottom): 17 3
> *
Current stack (top to bottom): 51
> 12
Current stack (top to bottom): 12 51
> -
Current stack (top to bottom): 39
>

Data representation

First, we need to decide how to represent the stack of numbers. There is a stack module in the standard library but, for the purposes of this tutorial, we won't use it.

The other obvious choice is to use the list(T) type. Since all the action will happen near the top of the stack, it makes sense to consider the front of the list to be the top of the stack.

Let's define a type alias for the stack. We will use int for the numbers.

:- type stack == list(int).

push

We'll need a predicate to push a number on top of the stack. The new stack will be the old stack with another number in front (i.e. on top). We can write it directly:

:- pred push(int::in, stack::in, stack::out) is det.

push(Top, Stack, [Top | Stack]).

Or, if you prefer:

push(Top, Stack0, Stack) :-
    Stack = [Top | Stack0].

pop

We'll also need a predicate to take the number off the top of the stack. The predicate can fail when the stack is empty, so its determinism must be semidet. If the stack is not empty, then the new stack is just the old stack without the topmost number.

:- pred pop(int::out, stack::in, stack::out) is semidet.

pop(Top, [Top | Stack], Stack).

It is a common convention in Mercury to keep state-like arguments together as it allows the use of state variable notation. It is also a convention to keep state-like parameters at the end of the argument list.

add

The "+" operation will pop the top two numbers off the stack, add them, then push the result onto the stack. One attempt at this predicate might look like:

:- pred add(stack::in, stack::out) is det.

add(Stack0, Stack) :-
    pop(X, Stack0, Stack1),
    pop(Y, Stack1, Stack2),
    push(X + Y, Stack2, Stack).

If you try to compile that, you will find that the compiler spits out error messages:

In `add'(in, in):
  error: determinism declaration not satisfied.
  Declared `det', inferred `semidet'.
  Call to `rpn.pop'(out, in, out) can fail.
  Call to `rpn.pop'(out, in, out) can fail.

Ah, there might be too few operands on the stack. Perhaps we should allow add to fail as well, by declaring its determinism to be semidet? The caller of add would need to do something sensible in case of failure, such as printing an error message.

Though, if we added a division operation, there could be two different reasons for a "divide" predicate to fail. The stack could have too few operands or the divisor could be zero. If the predicate fails in both cases, the caller could not tell why.

For now, we'll silently ignore invalid operations and leave the stack unchanged.

add(Stack0, Stack) :-
    ( if
        pop(X, Stack0, Stack1),
        pop(Y, Stack1, Stack2)
    then
        push(X + Y, Stack2, Stack)
    else
        % Not enough values on the stack.
        Stack = Stack0
    ).

Numbering the stack states is a bit tedious so we'll switch to state variable notation.

add(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(X + Y, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

subtract and multiply

As you would expect, subtract and multiply are similar to add. We just have to be a bit careful as subtraction is not commutative.

:- pred subtract(stack::in, stack::out) is det.

subtract(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(Y - X, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

:- pred multiply(stack::in, stack::out) is det.

multiply(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(X * Y, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

Printing the stack

To print the stack from top to bottom, we just need to print the value at the top of the stack before printing the rest of the stack, recursively.

:- pred write_stack(stack::in, io::di, io::uo) is det.

write_stack([], !IO).
write_stack([Head | Tail], !IO) :-
    write_int(Head, !IO),
    write_stack(Tail, !IO).

Oops! Actually, we'll need some sort of separator so numbers don't run into each other.

write_stack([], !IO).
write_stack([Head | Tail], !IO) :-
    write_int(Head, !IO),
    (
        Tail = []
    ;
        Tail = [_ | _],
        write_string(" ", !IO),
        write_stack(Tail, !IO)
    ).

Asking for input

We'll need a way to ask the user for input. Here's how to do that:

:- pred prompt(io.result(string)::out, io::di, io::uo) is det.

prompt(PromptRes, !IO) :-
    write_string("> ", !IO),
    flush_output(!IO),
    read_line_as_string(ReadRes, !IO),
    (
        ReadRes = ok(Line),
        PromptRes = ok(strip(Line))
    ;
        ReadRes = eof,
        PromptRes = eof
    ;
        ReadRes = error(Error),
        PromptRes = error(Error)
    ).

First we print something to let the user know the program is expecting input. Output streams are buffered. write_string adds its string argument to the output buffer of the current output stream. The buffer will be flushed whenever a newline occurs, but we want the user see the prompt and type input on the same line as the prompt, so we don't want to write a newline. Instead, we can manually flush the buffer using flush_output.

Next, read_line_as_string reads a line from the current input stream. The result has type io.result(string) with three possible cases:

  • On success, the result will be ok(Line) where Line is a string, including the newline that terminated the line (if any).

  • The result may be eof (end-of-file) indicating that the end of the input stream was reached.

  • If some error occurs, the result will be error(Error) where Error has type io.error.

In the ok(Line) case, Line includes the newline at the end of the line just read. The newline is irrelevant in this program. In fact, we don't mind if the user types any extra white space characters at the start or end of the line. prompt removes white space characters from either end of the line using the strip function, then the rest of the program doesn't need to deal with them.

eval

Having got input from the user, it is time to do something with it. If the input is a number (rather, the string representation of a number) then we convert the string to an int, then push the number on top of the stack. If the input names an operation, then call the predicate that implements it. Otherwise, we don't know what to do with the input so just do nothing for now.

The code is straightforward:

:- pred eval(string::in, stack::in, stack::out) is det.

eval(Input, !Stack) :-
    ( if string.to_int(Input, Number) then
        push(Number, !Stack)
    else if Input = "+" then
        add(!Stack)
    else if Input = "-" then
        subtract(!Stack)
    else if Input = "*" then
        multiply(!Stack)
    else
        % Don't know what to do, just leave the stack alone.
        true
    ).

The main loop

Now to put the pieces together. As always, the program starts in main. main just kicks off the main loop with an empty initial stack:

main(!IO) :-
    main_loop([], !IO).

In main_loop we show the user the current stack (with a few niceties) before prompting for input. If we manage to get some input, then we have eval perform the action according to the input, then repeat main_loop starting from the new stack. If, instead, we reached the end of the input stream then it is time to quit; simply do not enter main_loop again. Finally, if an error occurs while trying to get some input (unlikely) then print out an error message and let the program end.

:- pred main_loop(stack::in, io::di, io::uo) is det.

main_loop(Stack0, !IO) :-
    write_string("Current stack (top to bottom): ", !IO),
    (
        Stack0 = [],
        write_string("empty", !IO)
    ;
        Stack0 = [_ | _],
        write_stack(Stack0, !IO)
    ),
    nl(!IO),
    prompt(PromptRes, !IO),
    (
        PromptRes = ok(Line),
        eval(Line, Stack0, Stack),
        main_loop(Stack, !IO)
    ;
        PromptRes = eof
        % Quit program.
    ;
        PromptRes = error(Error),
        write_string("Error: ", !IO),
        write_string(error_message(Error), !IO),
        nl(!IO)
        % Quit program.
    ).

That's it!

The full program

:- module rpn.
:- interface.

:- import_module io.

:- pred main(io::di, io::uo) is det.

:- implementation.

:- import_module int.
:- import_module list.
:- import_module string.

:- type stack == list(int).

:- pred push(int::in, stack::in, stack::out) is det.

push(Top, Stack, [Top | Stack]).

:- pred pop(int::out, stack::in, stack::out) is semidet.

pop(Top, [Top | Stack], Stack).

:- pred add(stack::in, stack::out) is det.

add(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(X + Y, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

:- pred subtract(stack::in, stack::out) is det.

subtract(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(Y - X, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

:- pred multiply(stack::in, stack::out) is det.

multiply(!Stack) :-
    ( if
        pop(X, !Stack),
        pop(Y, !Stack)
    then
        push(X * Y, !Stack)
    else
        % Not enough values on the stack.
        true
    ).

:- pred write_stack(stack::in, io::di, io::uo) is det.

write_stack([], !IO).
write_stack([Head | Tail], !IO) :-
    write_int(Head, !IO),
    (
        Tail = []
    ;
        Tail = [_ | _],
        write_string(" ", !IO),
        write_stack(Tail, !IO)
    ).

:- pred prompt(io.result(string)::out, io::di, io::uo) is det.

prompt(PromptRes, !IO) :-
    write_string("> ", !IO),
    flush_output(!IO),
    read_line_as_string(ReadRes, !IO),
    (
        ReadRes = ok(Line),
        PromptRes = ok(strip(Line))
    ;
        ReadRes = eof,
        PromptRes = eof
    ;
        ReadRes = error(Error),
        PromptRes = error(Error)
    ).

:- pred eval(string::in, stack::in, stack::out) is det.

eval(Input, !Stack) :-
    ( if string.to_int(Input, Number) then
        push(Number, !Stack)
    else if Input = "+" then
        add(!Stack)
    else if Input = "-" then
        subtract(!Stack)
    else if Input = "*" then
        multiply(!Stack)
    else
        % Don't know what to do, just leave the stack alone.
        true
    ).

main(!IO) :-
    main_loop([], !IO).

:- pred main_loop(stack::in, io::di, io::uo) is det.

main_loop(Stack0, !IO) :-
    write_string("Current stack (top to bottom): ", !IO),
    (
        Stack0 = [],
        write_string("empty", !IO)
    ;
        Stack0 = [_ | _],
        write_stack(Stack0, !IO)
    ),
    nl(!IO),
    prompt(PromptRes, !IO),
    (
        PromptRes = ok(Line),
        eval(Line, Stack0, Stack),
        main_loop(Stack, !IO)
    ;
        PromptRes = eof
        % Quit program.
    ;
        PromptRes = error(Error),
        write_string("Error: ", !IO),
        write_string(error_message(Error), !IO),
        nl(!IO)
        % Quit program.
    ).

Exercises

  • Make it possible to enter multiple numbers or operations on the same line, e.g. "3 4 +". The string.words function would be useful.

  • Make the program print error messages for unknown input or invalid operations.

Add a custom footer
Add a custom sidebar
Clone this wiki locally