---
tags: programming languages
---
# A Calculator: The Interpreter

To continue from the previous lecture, the task is to give a formal definition of abstract syntax and then write an intepreter.

Recall our example. Instead of writing

5*((4+3)*2+1)

in concrete syntax, we will write the same in abstract syntax as

Times (Num 5) (Plus (Times (Plus (Num 4) (Num 3)) (Num 2)) (Num 1))

In Haskell, we can define a data type for abstract syntax that comprises exactly all arithmetic expressions built from numbers, plus and times as follows.

data Exp = Plus Exp Exp | Times Exp Exp | Num Integer

Now this is a bit tricky. We have seen recursive definitions of functions. But this is a recursive definition of a data type, a so-called **algebraic data type**. To understand the definition we need to know the following.

- `data` is a key word, indicating a user-defined data type.
- `Exp` is the name of the user-defined data type.
- `|` can be read as an "or". It shows us that there are three different cases that can be used to build an element of type `Exp`.
- `Plus`, `Times`, `Num` are user defined names. They are called *constructors*, but really are just labels that allow the pattern matching algorithm of Haskell to distinguish the three cases.
- `Integer` is a predefined Haskell data type for aribtrary-precision integers.

**Activity:** Can you start listing all elements of type `Exp`?

Now it is easy to write an interpreter. We just need to define a recursive function that evaluates the three cases. Since Haskell already knows about Integers, plus and times we rely on this.

eval :: Exp -> Integer
eval (Num n) = n
eval (Plus n m) = (eval n) + (eval m)
eval (Times n m) = (eval n) * (eval m)

**Remark:** Why is this so simple?
- Haskell allows us to write elegant algorithms that work by recursion over algebraic data types.
- Using abstract syntax, we were able to separate evaluation from two difficult tasks (parsing and arithmetic). In particular, Haskell already knows how to do arithmetic (`+` and `*` in the example).

## <font color=red>Homework</font>

To see how to put everything together have a look at [replit](https://replit.com/@alexhkurz/calculator-interpreter#main.hs). If you want to change the code you need to fork it or to copy it on your local machine.
- Run your own test cases of the interpreter.

- Extend the calculator/interpreter so that it can handle subtraction and division.

- (Optional) Instead of using built-in lists, we can define lists as our own algebraic data type as follows.

data List a = Nil | Cons a List

`a` is a type variable, denoting the type of the elements in the list. `Nil` plays the same role as `[]`. And `Cons` plays the same role as `:`, just that here we do not write it in infix but in prefix notation.

The exercise is now to rewrite some of the programs from the [previous session](https://hackmd.io/@alexhkurz/H1jUka4Gv) that worked by recursion over lists with this new definition of lists.