EECS 662

Programming Languages

Index
Blog

Project 3 - Functions and Elaboration

Project 3 – Static Scoping 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 and a conditional construct 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.

Exercise 1

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 and an if0-then-else construct. Following is the grammar for this language that we will call CFAE:

CFAE ::= number |
         id |
         CFAE * CFAE  |
         CFAE - CFAE |
         CFAE * CFAE |
         CFAE / CFAE |
         lambda id in CFAE |
         app CFAE CFAE |
         if0 CFAE CFAE CFAE

CFAE adds dynamically scope, first-class functions with strict evaluation semantics and removes bind. Your interpreter will use deferred substitution for efficiency and closures to represent function values:

  1. Write a function, evalDynCFAE :: EnvD -> CFAE -> CFAE that evaluates its second argument using the environment provided in its first and returns a CFAE AST structure. The type EnvD is the environment used for dynamic scoping that contains bindings of identifiers to values. Because values are just AST elements in the dynamically scoped interpreter, EnvD contains pairs of strings and CFAE values.

  2. Write a function, interpDynCFAE :: String -> CFAE that combines a parser that will be provided and interpreter for CFAE into a single interpretation function. This function should call evalDynCFAE using an empty environment.

Exercise 2

In this exercise you will write an interpreter for a modified CFAE 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.

  1. Define a datatype called CFAEValue to represent values returned by interpreting CFAE expressions. This datatype should minimally include closures and numeric values.

  2. Write a function, evalStatCFAE :: EnvS -> CFAE -> CFAEValue that interprets its second value using the environment provided in its first. This evaluator needs to return a value rather than a CFAE expression to implement static scoping using closures. The type EnvS is the environment used for static scoping that contains bindings of identifiers to values. Because values are their own data type in the static interpreter, EnvS contains pairs of strings and CFAEValue values.

  3. Write a function, interpStatCFAE that combines a parser that will be provided and interpreter for CFAE into a single evaluation function. This function should call evalStatCFAE using an empty interpreter.

Exercise 3

In this exercise you will write a pair of interpreters for a an extension of the CFAE language that includes the bind construct. This new language will be called CFBAE. The trick is that for this exercise you will not write another interpreter at all. Instead you will write an elaborator that will translate CFBAE language constructs into CFAE constructs, then call the CFAE interpreter:

CFBAE ::= number |
          id |
          CFBAE * CFBAE  |
          CFBAE - CFBAE |
          CFBAE * CFBAE |
          CFBAE / CFBAE |
          bind id = CFBAE in CFBAE |
          lambda id in CFBAE |
          app CFBAE CFBAE |
          if0 CFBAE CFBAE CFBAE
  1. Define a type for representing the abstract syntax for CFBAE. You will need to add a bind expression to the abstract syntax for the CFAE syntax from the previous problem.

  2. Write a function, elabCFBAE :: CFBAE -> CFAE, that takes a CFBAE data structure and returns a semantically equivalent CFAE structure. Specifically, you must translate the bind construct from CFBAE into constructs from CFAE.

  3. Write a function, evalCFBAE :: EnvS -> CFBAE -> CFAEValue, that combines your elaborator and statically scoped CFAE interpreter into a single operation that elaborates and interprets a CFBAE expression.

  4. Write a function, interpCFBAE :: String -> CFAEValue, that combines your evaluator and a parser that will be provide into a single interpreter function. Your new interpreter should have access to a collection of pre-defined symbols - functions and numbers - that will be available to all programs. This collection of pre-defined items is typically called a prelude. Your prelude should minimally define inc and dec, that increment and decrement their arguments, respectively.

The CFBAE interpreter introduces two new concepts to the CFAE interpreter - elaboration and a prelude. The first addition is done by writing a function that transforms CFBAE abstract syntax into CFAE 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 i = v in b == app (lambda i b) v

Thus, to evaluate a bind expression in CFBAE, one need simply translate it into a function application in CFAE and execute the result.

The addition of a prelude makes our interpreter more realistic by adding a collection of pre-defined functions and numbers that are available to all programs. Thankfully, it’s not particularly difficult to do using constructs that are defined for environments already. One need only provide an initial value for the environment that contains things defined in the prelude. Note that there is no env argument to either evaluation function. Thus, they are required to find their prelude definitions elsewhere.

Notes

This project looks long. It’s really not. Most of the changes aside from the recursive function processing are trivial. Don’t be intimidated and just do things step-by-step. Define the first interpreter with dynamic scoping first, then add static scoping for Exercise 2. Finally, the elaborator in Exercise 3 need only translate bind into an app and lambda.

proj3Utils contains a parser and AST data structure for both CFAE and CFBAE. Feel free to roll your own if you prefer. You will continue to use the parserUtils library with the utilities file for this specific project.