Mini Project 1 - Booleans, Identifiers, and Types
EECS 662 - Programming Languages
The objective of this mini-project is to add Booleans and types to our
bind. We will implement both an interpreter using
substitution and an interpreter using an environment. Then we will
write a type checker and integrate it with our interpreter.
To aid in your quest, the file p1.hs implements Haskell data types and function signatures needed for this project. I am not providing a parser for this project because parsers are evil.
Our first task is to implement
bind as we’ve discussed in class. We
will do an implementation that uses substitution and an implementation
that uses an environment. Here is the new abstract syntax that
evalS :: BBAE -> (Maybe BBAE)that uses
substto handle replacement of identifiers with their values.
evalM :: Env -> BBAE -> (Maybe BBAE)that uses an environment to implement replacement of identifiers with their values.
testBBAE :: BBAE -> Boolthat takes a BBAE expression and tests our evaluators.
testBBAEshould take the expression and evaluate with both interpreters and compare their results.
Now let’s add type checking. Here is a datatype representing number and Boolean types, respectively:
TBBAE is identical to our previous type definition with
only a change in the datatype name. We could have used the original
datatype without modification.
typeofM :: Cont -> BBAE -> (Maybe TBBAE)that returns the type of an expression. Note the
evalT :: BBAE -> (Maybe BBAE)that finds the type of an expression and evaluates the expression if a type is found for it.
Note the signature of
evalT does not accept an environment as
input. You will need to provide an appropriate initial environment to
evalM function. This is not hard!
We have talked through both the interpreters and the type inference function in class. What is required for this project is cleaning up code and fully implementing the interpreters. To give you an idea of the effort required for this mini-project, my code is about 200 lines long and took me roughly an hour to write and debug starting from the examples provided in the text. This is the most challenging project so far this semester. Do not put it off and please ask questions in class.