5 Assignment 5: Dynamic scope and Parameter-Passing Conventions

——Randall Munroe, xkcd

Place your code for interpreter in a file named a5.rkt and submit it on Autograder.

Note

You may find the following resources to be useful as you work on part 2 of this assignment:

• An in-depth look at parameter-passing variations from notes on Sep 29, 2011 and Feb 6, 2014.

Assignment

Part 1

Your task is to take the representation dependent dynamically scoped value-of-ds interpreter taught in class (found here), and make it representation independent with respect to both environments and closures using data structures rather than higher order functions. You are supposed to use tagged lists as the data structure representing both environments and closures.

• You should name your interpreter value-of-ds, and the names of your helper functions for environments and closures should be empty-env-ds, extend-env-ds, apply-env-ds, make-closure-ds, and apply-closure-ds.

• Your interpreter must handle the following forms: numbers, +, if-null, cons, car, cdr, empty, let, variables, lambda-abstraction, and application.

• Remember, your solutions should be compositional. So, in the definition of value-of-ds you must not implement let by converting it to a lambda invocation, as the comment shows in the class notes.

These tests are just a few examples; always write your own tests to properly verify your code.

> (value-of-ds

'(let ([x 10])

(let ([f (λ  (a) (+ a x))])

(let ([x 1])

(f 5))))

(empty-env-ds))

6

> (value-of-ds

'(let ([map (λ (map)

(λ (f)

(λ (ls)

(if-null ls

empty

(cons

(f (car ls))

(((map map) f)

(cdr ls)))))))])

(let ([ls (cons 1 (cons 2 (cons 3 empty)))])

(let ([f (λ (a) (cons a ls))])

(((map map) f) ls))))

(empty-env-ds))

'((1 1 2 3) (2 2 3) (3 3))

> (value-of-ds

'(let ([map (λ (map)

(λ (f)

(λ (ls^)

(if-null ls^

empty

(cons

(f (car ls^))

(((map map) f)

(cdr ls^)))))))])

(let ([ls (cons 1 (cons 2 (cons 3 empty)))])

(let ([f (λ (a) (cons a ls))])

(((map map) f) ls))))

(empty-env-ds))

'((1 1 2 3) (2 1 2 3) (3 1 2 3))

Once you’re done making this interpreter using tagged lists, you can trace your output and try to get a better idea about how dynamic scoping works.

Part 2

Below is an interpreter that is complete except for its five helpers empty-env, extend-env, apply-env, make-closure, and apply-closure. This interpreter should look quite familiar to you, except that it adds two new forms to our language, begin2 and random.

(define value-of

(lambda (exp env)

(match exp

[`,b #:when (boolean? b) b]

[`,n #:when (number? n)  n]

[`(zero? ,n) (zero? (value-of n env))]

[`(sub1 ,n) (sub1 (value-of n env))]

[`(* ,n1 ,n2) (* (value-of n1 env) (value-of n2 env))]

[`(if ,test ,conseq ,alt) (if (value-of test env)

(value-of conseq env)

(value-of alt env))]

[`(begin2 ,e1 ,e2) (begin (value-of e1 env) (value-of e2 env))]

[`(set! ,x ,expr) #:when (symbol? x)

(set-box! (apply-env env x)

(value-of expr env))]

[`(random ,n) (random (value-of n env))]

[`,y #:when (symbol? y) (apply-env env y)]

[`(lambda (,x) ,body) (make-closure x body env)]

[`(,rator ,rand) (apply-closure (value-of rator env)

(value-of rand env))])))

Your task is to implement four new versions of this interpreter, each one using a different parameter-passing convention.

Name your interpreters as follows:

• You will need to implement the empty-env, extend-env, apply-env, make-closure, and apply-closure helpers. Use a functional representation of both environments and closures.

• For the most part, you can use the same set of helpers for every interpreter. However, since make-closure calls the interpreter, you’ll need to implement versions of make-closure to go along with each interpreter.

• All interpreters must handle the following: booleans, numbers, variables, lambda, application, zero?, sub1, *, if, and random.

• Your val-of-cbr and val-of-cbv interpreters (not the other two) must also handle begin2 and set!.

• You should use boxes to help implement parameter-passing conventions. For more about boxes and the operations you can perform with them, see the Racket Documentation.

Suggested Tests

Remember, these tests are just a few examples; always write your own tests to help verify your code.

> (val-of-cbr

'((lambda (x) (begin2 (set! x #t)

(if x 3 5))) #f)

(empty-env))

3

> (val-of-cbr

'((lambda (a)

((lambda (p)

(begin2

(p a)

a)) (lambda (x) (set! x 4)))) 3)

(empty-env))

4

> (val-of-cbv

'((lambda (a)

((lambda (p)

(begin2

(p a)

a)) (lambda (x) (set! x 4)))) 3)

(empty-env))

3

> (val-of-cbr

'((lambda (f)

((lambda (g)

((lambda (z) (begin2

(g z)

z))

55))

(lambda (y) (f y)))) (lambda (x) (set! x 44)))

(empty-env))

44

> (val-of-cbv

'((lambda (f)

((lambda (g)

((lambda (z) (begin2

(g z)

z))

55))

(lambda (y) (f y)))) (lambda (x) (set! x 44)))

(empty-env))

55

> (val-of-cbr

'((lambda (swap)

((lambda (a)

((lambda (b)

(begin2

((swap a) b)

a)) 44)) 33))

(lambda (x)

(lambda (y)

((lambda (temp)

(begin2

(set! x y)

(set! y temp))) x))))

(empty-env))

44

> (val-of-cbv

'((lambda (swap)

((lambda (a)

((lambda (b)

(begin2

((swap a) b)

a)) 44)) 33))

(lambda (x)

(lambda (y)

((lambda (temp)

(begin2

(set! x y)

(set! y temp))) x))))

(empty-env))

33

> (define random-sieve

'((lambda (n)

(if (zero? n)

(if (zero? n) (if (zero? n) (if (zero? n) (if (zero? n) (if (zero? n) (if (zero? n) #t #f) #f) #f) #f) #f) #f)

(if (zero? n) #f (if (zero? n) #f (if (zero? n) #f (if (zero? n) #f (if (zero? n) #f (if (zero? n) #f #t))))))))

(random 2)))

> (val-of-cbname random-sieve (empty-env))

#f

> (val-of-cbneed random-sieve (empty-env))

#t

> (val-of-cbname

'((lambda (z) 100)

((lambda (x) (x x)) (lambda (x) (x x))))

(empty-env))

100

Brainteaser

One of the highly influential papers during the 1970s in PL was the paper "CONS should not Evaluate its Arguments", which points out the need for lazy data structures. Cons that does not evaluate its arguments is easy to implement as a thunk, but you will be adding it to your interpreter. To your "val-of-cbv" interpreter, add "cons^" that does NOT evaluate its arguments strictly (in other words, it evaluates them lazily). You should also create the corresponding versions of car and cdr ("car^" and "cdr^") that operate on "cons^". You should add the strict versions (regular "cons", "car", "cdr") to your val-of-cbv interpreter along with add1, empty list, let, and null?.

> (val-of-cbv '(cons^ 1 2) (empty-env))

(#<procedure> . #<procedure>)

> (val-of-cbv '(car (cons^ 1 2)) (empty-env))

#<procedure>

> (val-of-cbv '(car^ (cons^ 1 2)) (empty-env))

1

> (val-of-cbv '(cdr (cons^ 1 2)) (empty-env))

#<procedure>

> (val-of-cbv '(cdr^ (cons^ 1 2)) (empty-env))

2

> (define cons-test

'(let ((fix (lambda (f)

((lambda (x) (f (lambda (v) ((x x) v))))

(lambda (x) (f (lambda (v) ((x x) v))))))))

(let ((map (fix (lambda (map)

(lambda (f)

(lambda (l)

(if (null? l)

'()

(cons^ (f (car^ l))

((map f) (cdr^ l))))))))))

(let ((take (fix (lambda (take)

(lambda (l)

(lambda (n)

(if (zero? n)

'()

(cons (car^ l)

((take (cdr^ l)) (sub1 n))))))))))

((take ((fix (lambda (m)

(lambda (i)

(cons^ 1 ((map (lambda (x) (add1 x))) (m i)))))) 0)) 5)))))

> (val-of-cbv cons-test (empty-env))

(1 2 3 4 5)

Just Dessert

Loeb (and Moeb) are cool functions. Read this and do something neat with it. You could get it working in your call-by-need interpreter, for instance. Or make a spreadsheet thingy with it, I guess. If you have trouble with the syntax, well, then learn you a Haskell for great good!.