--- tags: programming languages --- (part of a course on programming languages) # A Calculator: Virtual Machine In the previous session, we wrote an interpreter that takes as input an arithmetic expression in abstract syntax and then evaluates it using Haskell's built-in arithmetic. This interpreter was very simple because we did not tackle the difficult problems of how to implement parsing and how to implement arithmetic. In this lecture, we will look at the simplest way to implement arithmetic. (Btw, it makes sense to consider this implementation as an *executable specification* of arithmetic rather than an *efficient implementation*, but in general it is not always clear where to draw the line separating specification from implementation.) To summarize, we want to build our own virtual machine that can do arithmetic and does not rely on Haskell's built-in arithmetic. **First Consideration:** We do not want to burden ourselves with the subtleties of how to represent binary numbers, nor do we want to complicate our algorithms with the need to carry bits. [^efficiency] [^efficiency]: Remember that in this course clarity and simplicity is more important for us than efficiency. This does not mean that efficiency is not important. But I think the right way to proceed is to first set up a correct specification and then refine it until it meets efficiency requirements. **Activity:** - What is the simplest possible way to represent numbers? [Hint: Ignore efficiency questions.] - I will show you how to implement these numbers as a simple recursive data type in Haskell. Answer. [^successornumbers] Next, we need some operations on numbers. By the way, without our simple representation of numbers we would have to face complications. For example, here is a circuit that adds 4 bit binary numbers (taken from this [Four Bit Full Adder Tutorial](http://langster1980.blogspot.com/2014/12/four-bit-full-adder-tutorial.html)). As they say, "It gets complicated!" ![](https://i.imgur.com/cZKvWSd.png =400x400) **Activity:** How can we define addition and multiplication for these numbers? How can we implement this in Haskell? **Activity:** How do we have to modify the interpreter from last time, so that it now evaluates in the virtual machine (instead of in Haskell's native numbers)? ## Homework (see also the assignment) You can find an implementation of what we have done in class today at [replit](https://replit.com/@alexhkurz/calculator-machine#main.hs). - Extend this implementation by multiplication and subtraction. - Make the implementation more user friendly as follows. Add two functions int_nn :: NN -> Integer nn_int :: Integer -> NN that translate from `Integer` to `NN` and back. Then change the testing part of the program so that the user interface works with `Integer` instead of `NN`, but the algorithm internally still uses `NN`. - Can you add division? This is interesting, but will require some work as one has to find out how to do division with successor numbers. Use subtraction in the recursion. - (optional) Using recursion over data NN = O | S NN - rewrite the programs from the [previous session](https://hackmd.io/@alexhkurz/SJKWvna6U) that worked by recursion over numbers such as `fib`, `factorial`, `triangle_numbers`, etc. - write functions of type NN->NN->NN for less, greater, less_equal, greater_equal, div, mod, exp, ... let me know if you make your own examples. ## A quick look at the history (optional) The inductive definition of addition and multiplication in terms of successor appears to my knowledge for the first time in - Richard Dedekind: [Was sind und was sollen die Zahlen](https://gdz.sub.uni-goettingen.de/id/PPN23569441X). 1888. On page 379 one finds ![](https://i.imgur.com/j5oQtJw.png) We see that Dedekind does recursion on the second argument, uses $1$ as its base case instead of $0$, and writes $'$ for successor. Multiplication is treated similarly on page 382. ## Further Reading (optional) [Alexis King - "Types as axioms"](https://lexi-lambda.github.io/blog/2020/08/13/types-as-axioms-or-playing-god-with-static-types/). One thing that is new to many Haskell beginners is the type system. This blog presents an interesting point of view. In particular the data types we will define to represent abstract syntax are an example of what she calls "postive space". [Implementing a Fractional Data Type and Investigating the Expansion of the Square Root of 2](https://5outh.blogspot.com/2012/08/haskell-implementing-fractional-data.html) builds a data type of fractions in order to compute the expansion of square roots. [^successornumbers]: The easiest way to represent numbers is using [tally marks](https://en.wikipedia.org/wiki/Tally_marks): `I` for one, `II` for two, `IIIIIIIIIIII` for 12, etc. But we also want a symbol for zero. So let us write `O` (pronounced "Oh") for zero, `S O` for 1, `S S O` for two, `S S S S S S S S S S S S S O` for 12, etc. The letter `S` here is used to remind us of "successor". As we will see shortly, these so-called **successor numerals** allow us to implement arithmetic much more easily then if had to use a [place-value system](https://en.wikipedia.org/wiki/Positional_notation) such as binary or decimal numbers.