EECS 662

Programming Languages


Project 1 - Predicting Failure

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.

Exercise 1

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
  1. Define a type for representing the abstract syntax of the extended ABE language using data.
  2. Using Parsec, write a function parseABE :: String -> ABE that accepts the concrete syntax of ABE and generates an ABE data structure representing it.
  3. 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.
  4. 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.
  5. 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.

Exercise 2

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

  1. If the expression x + 0 appears in an expression, replace it with x.
  2. 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.

Super Cool Optional Exercise 3

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.