Mini Project 1 - Predicting Failure EECS 662 - Programming Languages
The first 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. The second objective is developing a trivial optimizer that removes constants in
To aid in your quest, the file p1.hs implements the Haskell
TABE data types and function signatures. If you would like to play with a parser, p1-parser.hs adds a parser from strings to the
ABE data type. You do not need the parser for this project. It is included if you find the concrete syntax easier to read and to give you another example using Parsec.
Write an interpreter for the ABE language discussed in class and presented in our text extended to include multiplication and division.
ABE ::= number | boolean ABE + ABE | ABE - ABE | ABE * ABE | ABE / ABE | ABE && ABE | ABE <= ABE | isZero ABE | if ABE then ABE else ABE
evalM :: ABE -> (Maybe ABE), that takes a ABE data structure and interprets it and uses
Maybeto return an ABE value or
evalMfunction should do full run-time type checking in addition to divide-by-zero and negative number checking.
typeofM :: ABE -> (Maybe TABE), that returns either
Nothingrepresenting an error or an
TABEvalue representing a type.
evalMinto a single operation that type checks and evaluates an ABE expression. Take advantage of the
Maybemonad to ensure
evalMis not called when
And now for 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 x.
if true thenx
elsey appears in an expression, replace it with x. Similarly for
evalM in hand, you can create an optimized interpreter:
evalOptM::ABE -> Maybe ABE, that integrates your new
ABEinterpreter by calling it right before
Do not make this harder than it is. The optimizer replaces literal
0 in addition and literal
false in the
if. That’s all. Nothing else. I know you can do much more, but not for this project.
Most if not all the code for the ABE
typeofM 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. The
optimize function is a chance for you to stretch a bit. There are resources in the text and online that will help you if you don’t see a solution immediately. Recursion is your friend and the pattern we use for interpreters is a useful thing.
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.