Programming Language Design

Building a Calculator

---

Calculator 🧮

Now that we have an abstract syntax tree, we can define evaluation semantics for the language — let’s do a calculator!

Components we need for a calculator:

1. An abstract representation for the arithmetic language used as the input, and its parser.
2. A function which computes the value of the parsed term — the evaluator.
3. A way to get user input in order to make the calculator interactive, also known as a REPL.

Using the parser and the evaluator we can define the calculator simply as

Here, is used to lift the to a function . Calling the resulting function with produces an .

Evaluating Terms to Values

Let’s define the implementation of the evaluation function mathematically.

As a reminder, here are all the constructors for :

To implement the function, we can assume the argument is a , so let’s do case analysis on the term, breaking it into four cases for each of the four constructors:

Here, the is used as a notation for a “todo”, i.e. a missing implementation, in math.

By matching the values and with the data constructors, we note that they are of type also. Similarly we see that . The holes () have type .

First, we obviously want evaluation of to result in a , and likewise for other integers, so we can fill the final hole with .

Next, if we think about the term , the evaluation function should result in a , but how? Well, we can recursively evaluate and as we know, by the imaginary induction hypothesis, that and result in the correct results. Then it’s just a matter of matching the constructor with the mathematical operator.

Notice that this evaluation function didn’t require any error handling and there was never any ambiguity about which number to produce. Also, the evaluation is total, as it always a value for every input term.

Now your task is to translate this mathematical implementation into Gleam.

Loading Exercise...

Finally, implement the calculator.

Loading Exercise...