CSE P 505 Spring 2013 Homework #2

Due: Monday, April 22 at 11pm

This assignment will give you some more practice with functional programming and with writing interpreters for languages with variables and functions.

1 Higher-Order Functions

We talked about lambda, currying, and fold functions in class. The definitions of the fold functions are:

; If lst is (list x1 x2 ... xn), computes

; (fn xn ... (fn x2 (fn x1 init))...).

(define (foldl [fn : ('a 'b -> 'b)]

[init : 'b]

[lst : (listof 'a)]) : 'b

(if (empty? lst)

init

(foldl fn (fn (first lst) init) (rest lst))))

; If lst is (list x1 x2 ... xn), computes

; (fn x1 (fn x2 ... (fn xn init)...)).

(define (foldr [fn : ('a 'b -> 'b)]

[init : 'b]

[lst : (listof 'a)]) : 'b

(if (empty? lst)

init

(fn (first lst) (foldr fn init (rest lst)))))

Problem 1

Part 1. Define a function map-by-fold using one of the fold functions above. Try to use lambda in your definition. The function should behave identically to the built-in map function. Here’s a function to help test your implementation:

; Tests that (map-by-fold fn lst) computes the same thing as

; (map fn lst).

(define (test-map fn lst)

(test (map-by-fold fn lst) (map fn lst)))

In one of your test cases, pass the following list of functions as the second argument:

(list add1 sub1 (λ (x) (/ (* x (add1 x)) 2)))

and for the first argument, pass a lambda expression that applies its argument to the number 10.

Part 2. Define reverse-by-fold (equivalent to reverse) using a fold.

Question. Does the running time of this implementation differ from what you submitted in the first homework? Explain why (or why not).

Part 3. Define contains?-by-fold (equivalent to contains? from the first lecture) using a fold. As a reminder, here’s the function signature:

; Returns whether a-list contains the-thing.

(define (contains?-by-fold [a-list : (listof 'a)]

[the-thing : 'a]) : boolean

...)

Question. In what cases does the running time of this implementation differ from the hand-coded version? Why?

Part 4. Implement a more general version of test-map called test-binary-fn:

; Tests that two binary functions compute the same result.

(define (test-binary-fn [fn1 : ('a 'b -> 'c)]

[fn2 : ('a 'b -> 'c)]) : ('a 'b -> void)

...)

Redefine test-map in terms of test-binary-fn; also define test-contains?, and use it to test contains?-by-fold.

Problem 2

We discussed in class a strategy for evaluating functions with environments modeled by lists. However, an environment is just a mapping from symbols to values, so a function would also be a natural representation. We can capture this type equivalence in Racket with define-type-alias. (We use the built-in type constructor optionof to convey the fact that there may or may not be a binding for a given symbol in an environment.)

; Define an environment to be a function from symbols to (maybe)

; values (of some type 'a).

(define-type-alias (Env 'a) (symbol -> (optionof 'a)))

Complete this implementation of environments (and test it thoroughly).

; The empty environment.

(define empty-env : (Env 'a)

...)

; Returns an environment that contains the bindings in env, plus

; a binding from var to value.  If env already contains a binding

; for var, the new environment overrides that binding.

(define (extend-env [var : symbol]

[value : 'a]

[env : (Env 'a)]) : (Env 'a)

...)

; Looks up var in the environment.  If it's bound to some value,

; returns (some value).  Otherwise, returns (none).

(define (lookup [var : symbol]

[env : (Env 'a)]) : (optionof 'a)

...)

2 Implementing Functions and Variables

In class we added some new forms to our language’s syntax. Examples:

; A 'with' expression binds a value to a variable within its body.

(with (x (+ 1 2))

(* x 3)) ; => 9

; A 'fun' (function) abstracts a body over a variable.

(fun (x) (+ x 5)) ; A function that adds 5 to its argument.

; Functions have access to variable bindings in the enclosing

; (lexical) scope.

(with (y (+ 3 4))

(fun (x) (* x y))) ; A function that multiplies its argument by 7.

; Applying a function to a value.

((fun (x) (* x x)) 5) ; => 25

; Example combining 'with', 'fun', and application.

(with (y 3)

(with (f (fun (x) (* x y)))

(+ (f 8) (f (f 2))))) ; => 42

We represent these in the abstract syntax tree like this:

(define-type Expr

... ; Old hat (numbers and stuff).

[withE (var : symbol) ; The variable being bound.

(bound : Expr) ; What the variable is being bound to.

(body : Expr)] ; The body in which the variable is bound.

[varE (name : symbol)] ; A variable reference.

[funE (var : symbol) ; The name of the function argument.

(body : Expr)] ; The body of the function.

[appE (fun : Expr) ; The function being applied.

(arg : Expr)]) ; The argument to the function.

Problem 3

Extend your parser to recognize these new forms and produce the new abstract syntax.

Problem 4

We saw that the result of interpreting an expression could be either a number or a function, and we defined a new type, Value to represent these results. The body of a function can contain references to variables that were in scope when the function was evaluated, so we capture the environment at that point, creating a closure (so-called because it is self-contained).

(define-type Value

[numV (value : number)] ; A numeric value.

; A function closure:

[funV (var : symbol) ; The name of the function's argument.

(body : Expr) ; The body of the function.

(env : (Env Value))]) ; The function's evaluation environment.

We arrived at an interpretation strategy that used environments to track variable bindings:

(define (interp [expr : Expr] [env : (Env Value)]) : Value

(type-case Expr expr

... ; Old hat (numbers and stuff).

[withE (var bound body)

(interp body (extend-env var (interp bound env) env))]

[varE (name) (type-case (optionof Value) (lookup name env)

[some (value) value]

[none () (error 'unbound (to-string name))])]

[funE (var body) (funV var body env)]

[appE (fun arg) ...]))

Complete this implementation of interp such that the language provides the correct semantics for function calls (with lexical scoping). Write test cases to check that it works the way you expect.

Problem 5

Use this relationship to eliminate the withE form from the Expr datatype (and interpreter). However, continue to support the with form in the language’s concrete syntax.

Problem 6

Part 1. Extend the language to support multi-argument fun expressions and applications. All of the arguments to a function should have different names. If a function is applied to the wrong number of arguments, the interpreter should raise an error. For example,

(test (interp (parse '((fun (x y z) (* x (+ y z))) 2 3 4)) empty-env)

(numV 14))

; Duplicate argument name.

(test/exn (interp (parse '(fun (x x) (* x x))) empty-env)

"error")

; Too few arguments.

(test/exn (interp (parse '((fun (x y z) (* x (+ y z))) 2 3)) empty-env)

"error")

; Too many arguments.

(test/exn (interp (parse '((fun (x y z) (* x (+ y z))) 2 3 4 5)) empty-env)

"error")

Part 2. Delete the variants that you defined for arithmetic operators from the Expr datatype (but leave the numE variant!). Add back support for arithmetic operators by defining a base-env that maps the symbols +, *, etc. to suitable values. (Hint: define a new variant of Value.)

3 Handin Mechanics

As before, submit a single .rkt file with your code, along with a .txt or .pdf for the two written questions in Problem 1.