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
Parsec, write a function
parseABE :: String -> ABEthat accepts the concrete syntax of ABE and generates an ABE data structure representing it.
eval :: ABE -> (Either String ABE), that takes a ABE data structure and interprets it and returns an ABE value or an error message. Your
evalfunction should check for divide-by-zero errors at runtime.
typeof :: ABE -> (Either String TABE), that returns either a
Stringrepresenting an error message or an
typeoffunction should return an error message if it encounters a constant 0 in the denominator of a division operator.
interpthat combines your parser, type checker and evaluator into a single operation that parses, type checks, and evaluates an ABE expression. Take advantage of the
Eithertype to ensure
evalis not called when
And now, something completely different. Remembering that programs are just data structures, write a new function called
optimize :: ABE -> ABE that does two things:
+ 0appears in an expression, replace it with
if true thenx
elsey appears in an expression, replace it with x. Similarly for
Integrate this new
optimize into your
ABE interpreter by calling it right before
ABE interpreter using a
Either monad. Both
Either constructs, you simply need to modify the
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
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.