4 Assignment 4: Interpreters

Inverting the adage that a data type is just a simple programming language, we take the position that a programming language is, semantically, just a complex data type; evaluation of a program is just another operation in the data type.

——Mitch Wand

Assignment

Place your code in a file named a4.rkt and submit it to Autograder.

Part 1: Two Ways to Represent Environments

1. Define fn-environments to be a representation of environments that stores each environment as a function from symbols to values. To do so, finish the three definitions in the following skeleton.

   ; fn-empty-env : -> [Symbol -> Value]

   (define fn-empty-env ...)

   ; fn-extend-env : Symbol Value [Symbol -> Value] -> [Symbol -> Value]

   (define fn-extend-env ...)

   ; fn-apply-env : [Symbol -> Value] Symbol -> Value

   (define fn-apply-env ...)

   (define fn-environments

   `(,fn-empty-env

   ,fn-extend-env

   ,fn-apply-env))

   Test your code:

   > (define env (fn-extend-env 'b 5

   (fn-extend-env 'a 1

   (fn-extend-env 'b 2

   (fn-extend-env 'c 3 (fn-empty-env))))))

   > env

   #<procedure:...>

   > (fn-apply-env env 'a)

   1

   > (fn-apply-env env 'b)

   5

2. Define ds-environments to be a second representation of environments that stores each environment as a list that follows this exact grammar:

   Env		=		()
   		|		((Symbol Value) . Env)

   To do so, finish the three definitions in the following skeleton.

   ; ds-empty-env : -> Env

   (define ds-empty-env ...)

   ; ds-extend-env : Symbol Value Env -> Env

   (define ds-extend-env ...)

   ; ds-apply-env : Env Symbol -> Value

   (define ds-apply-env ...)

   (define ds-environments

   `(,ds-empty-env

   ,ds-extend-env

   ,ds-apply-env))

   Test your code:

   > (define env (ds-extend-env 'b 5

   (ds-extend-env 'a 1

   (ds-extend-env 'b 2

   (ds-extend-env 'c 3 (ds-empty-env))))))

   > env

   '((b 5) (a 1) (b 2) (c 3))

   > (ds-apply-env env 'a)

   1

   > (ds-apply-env env 'b)

   5

3. Define value1 to be a function that takes

   • an Expr

   • a representation of environments, such as fn-environments or ds-environments

   • an environment in the given representation

   and computes the value of the given expression in the given environment.

   (define value1

   (lambda (e environments env)

   (match environments

   (`(,empty-env ,extend-env ,apply-env)

   (match e ... apply-env ... extend-env ...)))))

   There are three kinds of values that this function could produce: numbers, booleans, and closures. Represent closures as Racket functions; for instance, the value of (λ x x) should be a Racket function that returns its input unchanged.

   Value		=		Number
   		|		Boolean
   		|		[Value -> Value]

   This function definition should recur naturally on the given expression; in other words, it must be compositional.

   Tip: In Racket, you may have seen the expansion of (let ((x e)) body) as ((lambda (x) body) e). When you are comfortable with the environment, however, you can implement let without using this expansion.

4. Define value1-program to be a function that takes

   • an Expr

   • a representation of environments, such as fn-environments or ds-environments

   and uses value1 to compute the value of the given expression in an initial environment that binds + and - and zero? to closures.

   (define value1-program

   (lambda (e environments)

   (match environments

   (`(,empty-env ,extend-env ,apply-env)

   (value1 e environments

   (extend-env ... empty-env ...))))))

Part 2: Two Ways to Represent Closures

In the rest of this assignment, you will build a second interpreter that is independent of the representation of closures. This independence will allow you to switch to a data-structure representation of closures, so that the contents of closures can be printed. To achieve full printability, this second interpreter will represent environments as Env data structures, as defined in question 2 above.

5. To start, copy value1 and value1-program, and rename them to value2 and value2-program throughout. Remove the second arguments to these functions, and instead invoke ds-empty-env and ds-extend-env and ds-apply-env directly.

   ; value2 : Expr Env -> Value

   (define value2

   (lambda (e env)

   (match e ... ds-apply-env ... ds-extend-env ...)))

   ; value2-program : Expr -> Value

   (define value2-program

   (lambda (e)

   (value1 e (ds-extend-env ... ds-empty-env ...))))

   Test this code as you did value1. Now you have an interpreter that depends both on the list representation of environments and on the functional representation of closures. The autograder won’t like this interpreter until you make the further changes explained below.

   Take a minute to admire how many lambdas are in your code: the dots in the skeleton above hide at least five lambdas, some nested inside others.

6. In your definition of value2, replace the lambda for interpreting λ with a call to a new helper function fn-make-closure. Because this lambda has three free variables, the helper should take those three free variables as three inputs.

   ; fn-make-closure : Symbol Expr Env -> [Value -> Value]

   Test your interpreter.
   Similarly, in your definition of value2-program, replace the lambda for interpreting + with a call to a new helper function fn-make-add. Because this lambda has no free variable, the helper should take no input.

   ; fn-make-add : -> [Value -> Value]

   Test your interpreter.
   Similarly, in your definition of value2-program, replace the interpretations of - and zero? with calls to new helper functions fn-make-sub and fn-make-zero?, which should take no input.

   ; fn-make-sub : -> [Value -> Value]

   ; fn-make-zero? : -> [Value -> Value]

   Test your interpreter.

   The dots in the skeleton in question 5 should no longer hide any lambdas, because you have moved them all to new helpers.

   Finally, in your definition of value2, replace the function application for interpreting function application with a call to a new helper function fn-apply-closure. This helper should take two inputs: the closure to apply, and the argument value to apply it to.

   ; fn-apply-closure : [Value -> Value] Value -> Value

   Test your interpreter.
   Putting these helpers together, define fn-closures to be a representation of closures that stores each closure as a function from values to values:

   (define fn-make-closure ...)

   (define fn-make-add ...)

   (define fn-make-sub ...)

   (define fn-make-zero? ...)

   (define fn-apply-closure ...)

   (define fn-closures

   `(,fn-make-closure

   ,fn-make-add

   ,fn-make-sub

   ,fn-make-zero?

   ,fn-apply-closure))

7. To value2 and value2-program, add a second argument to take a representation of closures, such as fn-closures. Instead of invoking the fn- helpers directly, invoke helpers provided by this argument.

   (define value2

   (lambda (e closures env)

   (match closures

   (`(,make-closure ,make-add ,make-sub ,make-zero? ,apply-closure)

   (match e ... make-closure ... apply-closure ...)))))

   (define value2-program

   (lambda (e closures)

   (match closures

   (`(,make-closure ,make-add ,make-sub ,make-zero? ,apply-closure)

   (value2 e closures

   (ds-extend-env ... make-add ... make-sub ... make-zero ... ds-empty-env ...))))))

   Test your interpreter with fn-closures. The interpreter is now independent of the closure representation.

8. Finally, define ds-closures to be a second representation of closures that stores each closure as a data structure that follows this exact grammar:

   Closure		=		(closure Symbol Expr Env)
   		|		(add)
   		|		(add Number)
   		|		(sub)
   		|		(sub Number)
   		|		(zero?)

   To do so, fill in the following skeleton. Remember that the ds-make- helpers should just make data structures, not enact any behavior. All behavior, which imbues the symbols λ + - zero? with meaning in our language, should be enacted by the final helper ds-apply-closure. This helper should proceed by matching naturally against the Closure. Each kind of Closure corresponds to a lambda in an fn-make- helper.

   ; ds-make-closure : Symbol Expr Env -> Closure

   (define ds-make-closure ...)

   ; ds-make-add : -> Closure

   (define ds-make-add ...)

   ; ds-make-sub : -> Closure

   (define ds-make-sub ...)

   ; ds-make-zero? : -> Closure

   (define ds-make-zero? ...)

   ; ds-apply-closure : Closure Value -> Value

   (define ds-apply-closure ...)

   (define ds-closures

   `(,ds-make-closure

   ,ds-make-add

   ,ds-make-sub

   ,ds-make-zero?

   ,ds-apply-closure))

   Test your interpreter with ds-closures. I hope you find the closure you deserve.

Just Dessert

9. For a wider understanding of what we’re doing, read Reynolds.