[lambdaheads]Program 2
[Programming][Languages]

Don't panic. The length of code you will write for this assignment is probably much less than the length of the assignment itself.

Consider the language AFunExp, which is AExp extended with division and closures. AFunExp adds the following two kinds of concrete syntax terms: 

<L> := ... 
     | (<L> / <L>)
     | (fun (<id>) <L>)
     | <id>
     | (<L> (<L>))
where / implements division, fun evaluates to a function (closure), and the ids are represented by symbols. Your parser must map this syntax to values of the following datatype: 
(define-datatype AFunExp AFunExp?
  [numE (n number?)]
  [addE (lhs AFunExp?) (rhs AFunExp?)]
  [multE (lhs AFunExp?) (rhs AFunExp?)]
  [divE (lhs AFunExp?) (rhs AFunExp?)]
  [funE (var symbol?) (body AFunExp?)]
  [varE (v symbol?)]
  [appE (fun AFunExp?) (arg AFunExp?)])

Your interpreters do not need to deal with type errors (such as using a number instead of a closure in the function position of an application, or division by zero). You can leave the error handling and reporting to Scheme.

Exercises

  1. Preliminaries:
    1. Implement the procedure closed?: 
      closed? : AFunExp -> boolean
      closed? accepts a parsed AFunExp? value. It returns true when there are no free (unbound) variables in the expression, and false otherwise. Tip: Use an environment!
    2. Using the external and internal representations specified above, extend an interpreter for AExp with the division operation. (Don't implement funE, varE or appE yet.) Your interpreter can return numE values.
  2. Using the definition of AFunExp above, provide a program that will produce different results under the eager and lazy disciplines. (You may use let to simplify writing the expression.) Also provide the computation steps and value (if any) under each discipline. The two computations may differ in any way, so long as if they both yield a value, the value must not be the same number or a closure that produces the same value for all values it is applied to. You can assume that evaluators for both disciplines return values, not compuations. Tip: There are indeed concise, two-line solutions to this problem, so think simple.
  3. For the following problems, your interpreters do not need to handle programs with free variables. For each problem:
    • provide an interface procedure named main that accepts a source program (using the external representation) and returns
      • the boolean value false if the program is not closed;
      • the symbol '<closure> if the program evaluates to a closure;
      • a Scheme number if the program evaluates to a number.
    • use an environment in your interpreter.
    Here are the problems:
    1. Implement (via an interpreter) AFunExp with the eager semantics using a datatype to represent AFunExp closures.
    2. Implement AFunExp with the eager semantics using Scheme's closures (lambda) to represent AFunExp closures and Scheme's procedure application to represent AFunExp application.
    3. Consider AFunExp with the lazy semantics using a datatype to represent AFunExp closures. If you believe this is difficult or impossible to implement, state and justify your claim; otherwise, provide an implementation.
    4. Consider AFunExp with the lazy semantics using Scheme's closures to represent AFunExp closures. If you believe this is difficult or impossible to implement, state and justify your claim; otherwise, provide an implementation.

Turn in all the code needed to run programs in AFunExp (parser, interpreter, libraries, etc). Your code is due by 11am on 2000-09-22. Email the code to the TA before, and submit it in print at, the start of class.