Lab 1: Simple Reverse Polish Notation Calculator

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. Expressions will be given to our calculator in reverse Polish notation, which has the advantage that we don’t have to worry about order of operations.

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 data type. We will use a form of integers that 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 to perform calculations.

What You Will Do

1. Figure out how you will define integers as an algebraic data type.
2. Implement arithmetic operations in terms of your AbstractInteger. You may modify or extend AbstractNatural included in the project skeleton.

Getting Started

Run git pull on your repository and cd into the lab01 folder. 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 + (fromAbstract 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|

You do not need to handle division by zero. It won’t occur during grading.

Note: If you are on Windows and ./Calc 10 3 / gives you a parse error, try a double slash ./Calc 10 3 // instead. If that doesn’t work, it is acceptable to look for "div" instead of "/" in evalRPNStack.

Augmenting the definitions

As you define operations, you add them to the calculator by modifying the definition of evalRPNStack 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

Testing

Test your code while you work, after each function you write. Do not wait until the end. It is much easier to track down and fix problems if you test in small pieces.

An ungraded file TestAbstractInteger.hs is provided with a few test cases you can copy-paste into GHCi.

You should also test on the command line, as that is how your lab will be graded:

$ ghc Calc
$ ./Calc -10 -7 / 0 \* abs 3 -9 \* -
27

Submitting

You only need to modify AbstractInteger.hs, but be sure to leave Calc.hs in your repository. All you have to do is make sure that you have commited to your repo by 4:59:00pm Tuesday. Be sure to check mit.cs.uchicago.edu to see if your changes were correctly pushed. Push early and often!

Grading

We will test the executable produced by Calc.hs with various RPN expressions. Your grade will be based on how many evaluate correctly. A few notes:

• Make sure your Calc.hs file compiles. A submission that uses undefined in a few places will receive more points than a lab that simply does not compile.
• In general, make sure you read this entire lab page carefully.
• All your math functions must be defined in terms of AbstractInteger (you cannot simply write add x y = toAbstract $ fromAbstract x + fromAbstract y).
• Other than that, this first lab will be graded only on correctness, not style.
• You will, however, receive un-graded comments on style. Future labs will include style points based on these guidelines:
  • Understandable names. Naming is one of the two hard problems in computer science. Short names are fine for common uses: i for index, x:xs for generic array elements, n for generic number, c for counter, etc. Abbreviations are fine too, but the rule is a reader should know the meaning of the thing just by reading its name. I (Brian) tend tend to err on the side of longer names.
  • Type definitions on all top-level functions.
  • No commented-out code.
  • Avoid long lines (>100 characters).
  • Parentheses in the correct place: sqrt (5 * 2) not sqrt(5 * 2).
  • Avoid unnecessary code, e.g. pattern match cases that could be combined, or deconstructing a value and then just putting it back together.
  • No “spaghetti code” (long, hard-to-follow, or deeply nested functions that should be broken up). Take advantage of where and let.
  • Comments explaining any hard-to-understand logic, e.g. what does this helper function do?
  • Tasteful use of whitespace for vertical alignment.
  • η-reduction is not necessary, but can be tasteful.

Collaboration

Again, quick reminder about collaboration:

Mention all collaboration with your classmates, but always do your own work from memory. The best place to mention collaboration is in a comment at the top of the file or near the relevant code. Commit messages are typically not read. Do not post partial or complete solutions on public websites.