CSE P 505 Spring 2013 Homework #3

Due: Monday, May 13 at 11:59pm

Revision History

1 More Interpreters

Problem 1

In class, we used store-passing style to implement boxes in the language we were interpreting. In this exercise, use the same technique to write an interpreter for an eager language with mutable variables instead of boxes. The language (including the parser) should support the following features:

• Numbers and simple arithmetic operators (just + and * is fine). The arguments to an arithmetic operation should be evaluated left-to-right.

• if0 as in the first homework.

• Functions and applications (single-argument is fine). Within a function application expression, e.g., (fe ae), the function subexpression fe should be evaluated before the argument subexpression ae. (Both of these are evaluated before the body of the funV to which fe evaluates.)

• Non-recursive with expressions (via desugaring is fine).

• A form (set var expr) that sets var to the value of expr and also returns that value. The set form is not a binding construct, so var must already be in scope.

• A begin form that evaluates two expressions sequentially and returns the result of the second (via desugaring is fine).

Some examples:

(test (parse/run '(with (x 3)

(+ x (begin (set x (+ x 1))

(* x x)))))

(numV 19))

(test (parse/run '(with (x 3)

(with (f (fun (y) (with (z x)

(begin (set x (+ x 1))

(* y z)))))

(+ (f 5) x))))

(numV 19))

(test (parse/run '(with (x 3)

(with (f (fun (y) (begin (set y (+ y 1))

(* x y))))

(+ (f x) x))))

(numV 15))

(test (parse/run '(with (f 3)

(begin

(set f (fun (n)

(if0 n 1 (* n (f (+ n -1))))))

(f 4))))

(numV 24))

You may implement store-passing either by hand or in the monadic style presented in class. Do not use Racket boxes. Define a parse/run function as in the test cases above to parse an expression, call your interp procedure with an appropriate initial environment and store, and extract just the Value field of the Result.

Problem 2

Define a parser and interpreter for a language with the following features:

• Numbers and simple arithmetic operators (just + and * is fine).

• if0 as in the first homework.

• Functions and applications (single-argument is fine).

• Non-recursive with expressions (via desugaring is fine).

In this language, function arguments (and therefore bound expressions in with forms) should be evaluated lazily. Use a data structure (not a Racket procedure) to represent unevaluated expressions. You may (if you want) use a box to cache the result in order to avoid repeated evaluation.

Some examples:

(test (interp (parse '(with (x ((fun (x) (x x))

(fun (x) (x x))))

(+ 1 2)))

initial-env)

(numV 3))

(test (interp (parse '(with (f (fun (z) 2))

(with (x ((fun (x) (x x))

(fun (x) (x x))))

(+ 1 (f x)))))

initial-env)

(numV 3))

(test (interp (parse '(with (y (fun (f)

((fun (g) (f (g g)))

(fun (g) (f (g g))))))

(with (fact (y (fun (f)

(fun (n)

(if0 n 1 (* n (f (+ n -1))))))))

(fact 6))))

initial-env)

(numV 720))

Written question. In Problems 1 and 2, suppose your interpreter supported functions with more than one argument and allowed you to put built-in functions into the initial environment (as in Homework 2, Problem 6).

Part (a). In each case (eager and lazy), is it possible to implement if0 (as in Homework 1) as a built-in function? If so, explain how you would do so, or if not, why not?

Part (b). In each case (eager and lazy), is it possible to implement if0 via a combination of desugaring and built-in functions? Again, explain how this would work, or why it’s not possible.

For both parts of this question, your interpreter must implement the standard definition of function application in an eager/lazy language. You may not add any special-case logic for conditional evaluation in the interpreter.

2 Mutation

Problem 3

Use lexical scope and variable mutation (i.e., let and set!) to implement a Ref abstraction whose semantics are identical to Racket’s boxes. (Do not use Racket’s boxes.) You may also find λ, begin, (void), and the optionof type constructor useful. (For this problem, you do not need to write an interpreter.)

(define-type (Ref 'a) ...) OR

(define-type-alias (Ref 'a) ...)

; Makes a new reference whose initial content is v.

(define (ref [v : 'a]) : (Ref 'a)

...)

; Returns the current content of r.

(define (deref [r : (Ref 'a)]) : 'a

...)

; Updates the content of r to v.

(define (set-ref! [r : (Ref 'a)] [v : 'a]) : void

...)

(define a-ref (ref 3))

> (deref a-ref)

- number

3

> (set-ref! a-ref 10)

- void

> (deref a-ref)

- number

10

3 Handin Mechanics

Submit a separate .rkt file for each problem in this assignment, along with a .txt or .pdf for the written question.