This is the “put it all together” project. The objective is to add Boolean operations, type checking, and a fixed point operation to FBAE from Project 3. You will first add boolean operations to the FBAE interpreter by extending the AST and updating the evaluator. You will then add a fixed point operator to your AST and interpreter. Finally, you will define a type checker for the extended FBAE language and integrate type checking into the FBAE interpreter. Specifically, you will type check your AST, elaborate to FBAE if you choose to, and evaluate the result.
Please note that I will only grade Exercise 4, the entire combined interpreter. The 4 exercises are laid out separately only to help you organize your project. If you choose, you may submit a solution that only contains the final FBAE interpreter.
If you worry about such things, this is Project 4 only because I
accidentally named the template file for Project 2
p3.hs. There is no Project 3.
The base language for this project is the extension of FBAE defined as follows:
None of these operations is new. We have implemented them in some form in earlier projects or in class. You are taking the things we’ve learned so far and assembling them into a single language.
evalM :: Env -> FBAE -> (Maybe FBAVal)that performs call-by-value function interpretation using static scoping. Your interpreter need only do minimal runtime error checking as it will be integrated with a type inference function later in the project.
The syntax for
lambda in FBAE includes specification of a
Lambda has a placeholder for the domain type. While
this would be populated by the parser if we were using one and you
must include types in your AST, they are ignored by the evaluator.
Note specifically that
ClosureV has no domain type specified. Think
carefully about why this is the case.
If you choose to you may continue to use the elaborator from Project 3
bind and reuse your evaluator for CFAE. Alternatively,
you may extend the CFAE interpreter to include
bind as the beginning
of your new interpreter. This is completely up to you.
In this exercise you will add recursion to CFWAE by adding a
operator to CFWAE. This is accomplished by adding the term:
to the original FBAE language from Exercise 1. Note that the AST provided for Project 4 already includes this construct. Thus, you need not change your AST for this exercise.
evalMfunction from Exercise 1 to include the
In this exercise you will write a type checker for the FBAE language identical to that used in Project 2 with the addition of syntax for types.
typeofM :: Cont -> FBAE -> (Maybe TFBAE), that takes an FBAE data structure and returns its type given a context. If no type can be found,
Nothing. Think of this as an evaluator that produces type values rather than traditional values.
An AST for the type values is included in the Project 4 template file.
In this exercise you will put all the pieces together to write an interpreter for FBAE and its extensions.
evalMfunctions into a function
interp :: FBAE -> (Maybe FBAEVal)that finds the type of the input AST and evaluates the result if a type is found.
Note that the type inference function is called before evaluation. Evaluation should only occur if type inference returns a type.
You can get quite a bit of your code from class notes or the
text. However, you will need to write
evalM cases for
Boolean operations on your own.
Keep error checking in
evalM to a minimum. If the purpose of
typeofM is to predict errors, then very little error checking need
be performed during evaluation. This is one advantage of type
inference and type checking.
Following are the AST structures defined in the template file.