Lab 1: Simple Reverse Polish Notation Calculator

Posted on October 4, 2016

Introduction

Let’s build a calculator, one of the simplest examples of all programming machines. Indeed the first computers in the modern sense of the term were calculators. Like other programming languages they feature a context-free language and thus require a stack. The beauty of the reverse Polish notation calculator is that the stack can be defined implicitly by the expression being parsed.

The main twist for this lab is that we are not going to use Haskell’s internal arithmetic implementation for our calculator. Rather we are going to work with integers as an abstract Algebraic Datatype. This form of integers is similar to the computational coding of integers by Alonzo Church. The actual form of the coding is up to you, but it should be sufficient in order to perform calculations.

Chief Deliverables

  1. A commandline calculator using foldl
  2. Calculator implemented with an AbstractInteger algebraic datatype which you will define. You may modify or extend AbstractNatural included in the project skeleton.

Submitting

Our git system is still being set up. Email your submission (make sure to include both Calc.hs and AbstractInteger.hs) to brianhempel@uchicago.edu by 11:59:59pm Friday.

You may submit multiple times if the deadline is close. Only the last submission will be graded.

Getting Started

Download the project skeleton. You will find the file Calc.hs which will import AbstractInteger and use it to run the calculator. You may run the calculator by first compiling:

$ ghc Calc

and then using the command-line tool

$ ./Calc 3 4 +

although you’ll get the following error message:

Calc: Prelude.undefined.

The rest of the lab is to get meaningful outputs. The functions/calculator operations that need to be implemented are:

  1. "abs", absolute
  2. "+", add
  3. "-", difference
  4. "*", multiply (Note to write multiply you’ll need to do ./Calc 3 4 \* to escape the asterisk for proper interpretation)
  5. "%", modulo more on this later.
  6. "/", divide more on this later

The calculator should operate on AbstractInteger so that it can input and output negative numbers.

Basic Calculator Operations

The file you will be modifying is AbstractInteger.hs. First figure out how you will represent the AbstractInteger type. Then implement successor, predecessor, negator, absolute, add, and difference. Notice that undefined is used throughout the file. This is a placeholder that allows us to compile a file without giving full definitions. It’s good practice to use this so that you can work with partial implementations of your code.

Abstract Natural Numbers

To implement AbstractInteger you may use (or build upon, or modify) the implementation of AbstractNatural which represents the natural numbers (in AbstractInteger.hs):

data AbstractNatural = Zero | S AbstractNatural
  deriving (Show)

This code says that natural numbers come in two varieties: Zero, or the successor of some other natural number S AbstractNatural. To get a feel for the natural numbers you can load the file into the Haskell REPL:

$ ghci AbstractInteger

and you should see the following output:

[1 of 1] Compiling AbstractInteger  ( AbstractInteger.hs, interpreted )
Ok, modules loaded: AbstractInteger.
*AbstractInteger>

The deriving (Show) allows the REPL to print out meaningful results

*AbstractInteger> Zero
Zero
*AbstractInteger> S Zero
S Zero
*AbstractInteger> S (S Zero)
S (S Zero)

Typeclasses

You will notice some functions on AbstractNatural that are commented out. You may or may not need these, but you should understand how they work in case you discover that you need to implement similar versions for your AbstractInteger type.

The definition of == for AbstractNatural demonstrates the central Haskell idea of using induction and pattern-matching to define programming constructs. Following the logic here is important:

instance Eq AbstractNatural where
  Zero == Zero = True
  Zero == S y  = False
  S x  == Zero = False
  S x  == S y  = x == y

The line Zero == Zero = True means that zero is always equal to zero. The lines Zero == S y = False and S x == Zero = False means that non-zero things never equal zero. The final line S x == S y = x == y removes an S from the two non-zero terms being compared, this is repeated until one of the terms is zero and then the other comparisons will kick in.

Note the inductive logic. We handle the zero case first, and then we build up from there.

Converting Natural Numbers

That same pattern matching and inductive principle comes into play when we define conversion functions between the concrete numbers and AbstractNatural or AbstractInteger. Think about how these conversions to/from AbstractNatural work:

toAbstract 0 = Zero
toAbstract x = S $ toAbstract (x - 1)

and the conversion back

fromAbstract Zero = 0
fromAbstract (S x) = 1 + (toAbstract x)

You will have to implement your own versions for AbstractInteger.

Adding Natural Numbers

And here’s an example of addition on AbstractNatural:

add Zero y = y
add (S x) y = S (add x y)

Again, you will need to define your own version for AbstractInteger.

Division

We will follow Euclidean division for defining divide (the Euclidean division quotient) and modulo (the Euclidean divison remainder).

For positive numbers, Euclidean division is the simple division with remainder you learned in grade school. Ten divided by three is 3 remainder 1.

$ ./Calc 10 3 /
3
$ ./Calc 10 3 %
1

For negative numbers, the rule is that the remainder is always non-negative.

$ ./Calc -10 3 /
-4
$ ./Calc -10 3 %
2

Why these results? 3 * -4 = -12 is the first multiple of 3 below -10, so we can have a positive remainder of 2.

More formally, given a divided by b, the challenge is to find integers q and r such that

a = bq + r with 0 ≤ r < |b|

Augmenting the definitions

As you define operations, you can add them to the calculator by modifying the definition of foldingFunction in AbstractInteger.hs. Note well that you will want to add the extra operations before the catchall numberString line so that the operator will be matched first.

Note also the definitions for a variety of integers:

zero = undefined
one = successor zero
two = successor one
three = successor two
four = successor three
five = successor four
six = successor five
seven = successor six
eight = successor seven
nine = successor eight
ten = successor nine
...

Once you define zero and successor and predecessor, these will help you test in ghci:

*AbstractInteger> add zero nine