- Project 0 - A First Interpreter
- Project 1 - Predicting Failure
- Project 2 - Booleans, Identifiers, and Lists
- Project 3 - Functions and Elaboration
- Project 4 - Type Checking

Blog

Mini Project 1 - Predicting Failure

EECS 662 - Programming Languages

The objective of this miniproject is to develop your first type checker. You will start with the ABE language presented in class and develop techniques for predicting failure.

Write a parser and interpreter for the ABE language discussed in class and presented in our text extended to include multiplication and division. Work with the parser that is defined in the example from class.

```
ABE ::= number | boolean
ABE + ABE |
ABE - ABE |
ABE * ABE |
ABE / ABE |
ABE && ABE |
ABE <= ABE |
isZero ABE |
if ABE then ABE else ABE
```

- Define a type for representing the abstract syntax of the extended ABE language using
`data`

. - Using
`Parsec`

, write a function`parseABE :: String -> ABE`

that accepts the concrete syntax of ABE and generates an ABE data structure representing it. - Write a function,
`eval :: ABE -> (Either String ABE)`

, that takes a ABE data structure and interprets it and returns an ABE value or an error message. Your`eval`

function should check for divide-by-zero errors at runtime. - Write a function,
`typeof :: ABE -> (Either String TABE)`

, that returns either a`String`

representing an error message or an`TABE`

structure. Your`typeof`

function should return an error message if it encounters a constant 0 in the denominator of a division operator. - Write a function,
`interp`

that combines your parser, type checker and evaluator into a single operation that parses, type checks, and evaluates an ABE expression. Take advantage of the`Either`

type to ensure`eval`

is not called when`typeof`

fails.

And now, something completely different. Remembering that programs are just data structures, write a new function called `optimize :: ABE -> ABE`

that does two things:

- If the expression
*x*`+ 0`

appears in an expression, replace it with`x`

. - If the expression
`if true then`

*x*`else`

*y*appears in an expression, replace it with*x*. Similarly for`false`

and*y*.

Integrate this new `optimize`

into your `ABE`

interpreter by calling it right before `eval`

.

Reimplement the `ABE`

interpreter using a `Either`

monad. Both `typeof`

and `eval`

return `Either`

constructs, you simply need to modify the `eval`

and `typeof`

functions. This is not particularly difficult and you should be able to find plenty of examples both in the class text and online.

Most if not all the code for the ABE `eval`

and `typeof`

functions can be found in our text. Again, I would encourage you to try to write as much of them as possible without referring to the textbook examples.

To give you an idea of the effort required for this mini-project, my code is about 150 lines long and took me roughly an hour to write and debug. I view this as a reasonably easy project at this point in the semester. Do not put it off as many of you are still becoming friends with Haskell. Hopefully the previous project shook out any difficulty with Haskell tools.