Project 3 – Functions and Elaboration EECS 662 - Programming Languages
The objective of this project is to add dynamically scoped and statically scoped strict functions to BAE and introduce elaboration to the interpretation process. You will first define an interpreter that adds functions, Booleans, and a conditional to BAE while removing the
bind expression. You will then define an interpreter that uses elaboration to define interpretation of
bind in terms of function application.
To aid in your quest, the file p3.hs implements Haskell data types and function signatures needed for this project. Look at this file carefully before you start as this project requires two abstract syntaxes. Data types cannot share constructor names, so a tick is used to distinguish constructors. I am not providing a parser for this project because parsers remain evil.
In this exercise you will write an interpreter for a modified FBAE language presented in our text that does not include the
bind construct, but does include first-class functions. Following is the grammar for this language that we will call FAE:
FAE ::= number | id | FAE + FAE | FAE - FAE | lambda id in FAE | FAE FAE |
CFAE has numbers, dynamically scoped, first-class functions with strict evaluation semantics and no
bind. Your interpreter will use deferred substitution for efficiency but will not require closures as it is dynamically scoped. Perform the following:
evalDynFAE :: Env -> FAE -> (Maybe FAE)that evaluates its second argument using the environment provided in its first and returns a
In this exercise you will write an interpreter for a modified FAE language from the previous exercise that is statically rather than dynamically scoped. You will need to add closures and values to the interpreter to accomplish this goal.
evalStatFAE :: Env' -> FAE -> (Maybe FAEValue)that interprets its second value using the environment provided in its first. This evaluator needs to return a value rather than a FAE expression to implement static scoping using closures.
In this exercise you will write a pair of interpreters for a an extension of the FAE language that includes the
bind construct. This new language will be called FBAE. The trick is that for this exercise you will not write another interpreter at all. Instead you will write an elaborator that will translate FBAE language constructs into CFAE constructs, then call the FAE interpreter. The new language CFBAE has the form:
FBAE ::= number | id | FBAE + FBAE | FBAE - FBAE | bind id = FBAE in FBAE | lambda id in FBAE | FBAE FBAE |
Write a function,
elabFBAE :: FBAE -> FAE, that takes a
FBAE data structure and returns a semantically equivalent
FAE structure. Specifically, you must translate the
bind construct from CFBAE into constructs from
Write a function,
evalFBAE :: Env' -> FBAE -> (Maybe FAEValue), that combines your elaborator and statically scoped
FAE interpreter into a single operation that elaborates and interprets a
FBAE interpreter introduces elaboration to the
by using a function that transforms
FBAE abstract syntax into
FAE syntax before evaluation. Most of this translation is routine - there are shared constructs in the two languages. For
bind we have to do a bit more work. Thankfully, not too much more.
As discussed in class, the
bind construct can be elaborated to an application of a function. Specifically:
bind id = t0 in t1 == ((lambda id t1) t0)
Thus, to evaluate a
bind expression in
FBAE, one need simply translate it into a function application in
FAE and execute the result.
The work for this project is not big. Define the first interpreter with dynamic scoping first, then add static scoping for Exercise 2. The elaborator in Exercise 3 need only translate