Blog

Project 0 - Implementing our First Interpreters EECS 662 - Programming Languages

The objective of this project is to develop your first rudimentary
interpreters. You will extend with the AE language presented in class
to get up-to-speed with Haskell and write three different interpreters
using three different styles. For this project AE will be extended
to include an `if0`

construct in addition to constructs discussed in
class:

```
AE ::= Nat
AE + AE |
AE - AE |
AE * AE |
AE / AE |
if0 AE then AE else AE
```

The new construct, `if0`

, is an expression that evaluates its first
argument and if it is `0`

evaluates its second. If not it evaluates
its third.

Assume that `Nat`

represents the natural numbers as we have
been discussing in class. You must add error handling for
negative numbers.

To aid in your quest the file p0.hs implements the Haskell AE data type and a parser from strings to the data type. At the bottom of the file you will find signatures for the four functions required for the four exercises below. Take a careful look at this file before you begin.

Write a function, `evalAE::AE -> Int`

, that takes a AE data structure,
evaluates it, and returns an `Int`

. If your interpreter fails, it
should throw an error using the `error`

function discussed in class.
Remember that `Nat`

is a natural number and cannot be negative.

Write a function, `evalAEMaybe::AE -> Maybe Int`

, that takes the same
AE data structure as Exercise 1, evalutes it, and returns a value.
Use `Just`

to return a number and `Nothing`

to indicate an error. Do
not use `Maybe`

as a monad in this interpreter. Use `if`

and/or
`case`

to process errors.

Write a function, `evalM::AE -> Maybe Int`

, that takes the same AE
data structure as Exercises 1 & 2, evaluates it, and returns a number.
This time, use the `do`

notation to treat `Maybe`

as a monad.

Write a function, `interpAE`

that combines the AE parser and `evalM`

into a single operation that parses and then evaluates an AE
expression. You will be provided a parser and must integrate it with
your interpreter.

Most if not all the code for the AE interpreter can be found in our text. I would encourage you to try to write as much of it as possible without referring to the textbook examples.

The `evalM`

function closely resembles the interpreters we will write
for the remainder of the semester. The `do`

notation and monads make
things much easier and make our code look more like its formal
representation. You don’t have to deeply understand monads to use
them. The `Maybe`

monad in this project is an example of that.

To give you an idea of the effort required for this project, my code is about 100 lines long and took me roughly an hour to write and debug. I view this as an easy project at this point in the semester. Do not put it off as most of you haven’t used Haskell in some time. Additionally, you’ll need to figure out how to use the Haskell tools installed on EECS machines or install them on your own.