Assignment 5

Parameter Passing Variations

This is a long assignment! Start early!

This assignment comprises two parts.

Your finished interpreters should be submitted in a single file, named a5.scm. This file should run all of your test programs when loaded.

You are to write three interpreters.
- value-of-ref implements call-by-reference semantics.
- value-of-name implements call-by-name semantics.
- value-of-need implements call-by-need semantics.
Each interpreter must support the following operations: *, sub1, zero?, if, let, begin, set!, lambda, and procedure application. Below you will find partially completed versions of these interpreters.
As you implement each interpreter, keep in mind the distinction between expressed values returned by the interpreter and denoted values that appear in the environment. For example, in the call-by-need interpreter the environment maps symbols to boxes containing thunks. However, a call to the interpreter will never return a box.
See the test programs at the bottom of this page.

Here is a version of an interpreter implementing call-by-value semantics. This is here for your reference only--it is not part of the assignment.

(define value-of
  (lambda (expr env)
    (pmatch expr
      [,n (guard (or (number? n) (boolean? n)))
       n]
      [,x (guard (symbol? x))
       (unbox (apply-env env x))]
      [(* ,x1 ,x2) 
       (* (value-of x1 env)
          (value-of x2 env))]
      [(sub1 ,x) 
       (sub1 (value-of x env))]
      [(zero? ,x) 
       (zero? (value-of x env))]
      [(begin ,x1 ,x2) 
       (begin
         (value-of x1 env)
         (value-of x2 env))]
      [(set! ,id ,val) 
       (set-box! (apply-env env id) (value-of val env))]
      [(if ,test ,conseq ,alt) 
       (if (value-of test env)
           (value-of conseq env)
           (value-of alt env))]
      [(let ([,id ,rand]) ,body) 
       (value-of body (extend-env id (box (value-of rand env)) env))]
      [(lambda (,id) ,body) 
       (closure id body env)]
      [(,rator ,rand) 
       (apply-proc (value-of rator env) (box (value-of rand env)))])))

Here is a stub for value-of-ref, the interpreter that implements call-by-reference semantics. Fill in the blank parts.

(define value-of-ref
  (lambda (expr env)
    (pmatch expr
      [,n (guard (or (number? n) (boolean? n)))
       ---]
      [,x (guard (symbol? x))
       ---]
      [(* ,x1 ,x2) 
       ---]
      [(sub1 ,x) 
       ---]
      [(zero? ,x) 
       ---]
      [(begin ,x1 ,x2) 
       ---]
      [(set! ,id ,val) 
       ---]
      [(if ,test ,conseq ,alt) 
       ---]
      [(let ([,id ,rand]) ,body) 
       (let ([rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (let ([rand (value-of-ref rand env)])
                             (box rand))])])
         (value-of-ref body (extend-env id rand env)))]
      [(lambda (,id) ,body) 
       (closure id body env)]
      [(,rator ,rand) 
       (let ([rator (value-of-ref rator env)]
             [rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (box (value-of-ref rand env))])])
         (apply-proc rator rand))])))

Here is a stub for value-of-name, the interpreter that implements call-by-name semantics. Again, fill in the blanks.

(define value-of-name
  (lambda (expr env)
    (pmatch expr
      [,n (guard (or (number? n) (boolean? n)))
       ---]
      [,x (guard (symbol? x))
       ---]
      [(* ,x1 ,x2) 
       ---]
      [(sub1 ,x) 
       ---]
      [(zero? ,x) 
       ---]
      [(begin ,x1 ,x2) 
       ---]
      [(set! ,id ,val) 
       ---]
      [(if ,test ,conseq ,alt) 
       ---]
      [(let ([,id ,rand]) ,body) 
       (let ([rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (let ([rand (value-of-name rand env)])
                             (box (lambda () rand)))])])
         (value-of-name body (extend-env id rand env)))]
      [(lambda (,id) ,body) 
       (closure id body env)]
      [(,rator ,rand) 
       (let ([rator (value-of-name rator env)]
             [rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (box (lambda () (value-of-name rand env)))])])
         (apply-proc rator rand))])))

Here is a stub for value-of-need, the interpreter that implements call-by-need semantics. Fill in the blanks once again.

(define value-of-need
  (lambda (expr env)
    (pmatch expr
      [,n (guard (or (number? n) (boolean? n)))
       ---]
      [,x (guard (symbol? x))
       ---]
      [(* ,x1 ,x2) 
       ---]
      [(sub1 ,x) 
       ---]
      [(zero? ,x) 
       ---]
      [(begin ,x1 ,x2) 
       ---]
      [(set! ,id ,val) 
       ---]
      [(if ,test ,conseq ,alt) 
       ---]
      [(let ([,id ,rand]) ,body) 
       (let ([rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (let ([rand (value-of-need rand env)])
                             (box (lambda () rand)))])])
         (value-of-need body (extend-env id rand env)))]
      [(lambda (,id) ,body) 
       (closure id body env)]
      [(,rator ,rand) 
       (let ([rator (value-of-need rator env)]
             [rand (pmatch rand
                     [,x (guard (symbol? x)) (apply-env env x)]
                     [else (box (lambda () (value-of-need rand env)))])])
         (apply-proc rator rand))])))

You may use either procedural or data-structural representation of environments and procedures. The helper functions are defined below.

You will not need to modify these helper functions. However, you will need to redefine either apply-proc or closure after each interpreter definition, depending on whether you are using DS or procedural representation of closures. For example, if you use procedural representation of closures, you must add the definition

(define closure (make-closure value-of-ref))

immediately after your definition of value-of-ref. If you use DS representation of closures, you must add the definition

(define apply-proc (make-apply-proc value-of-ref))

instead. Here are the helper functions.

Enivronment helper functions using DS representation.

(define empty-env
  (lambda ()
    '()))

(define extend-env
  (lambda (id val env)
    `((,id . ,val) . ,env)))

(define apply-env
  (lambda (env x)
    (pmatch env
      [()  (error 'apply-env "Unbound variable ~s" x)]
      [((,y . ,v) . ,env) 
       (if (eq? y x)
           v
           (apply-env env x))])))

Enivronment helper functions using procedural representation.

(define empty-env
  (lambda ()
    (lambda (x)
      (error 'empty-env "Unbound variable ~s" x))))

(define extend-env
  (lambda (id val env)
    (lambda (x)
      (if (eq? x id)
          val
          (apply-env env x)))))

(define apply-env
  (lambda (env x)
    (env x)))

Closure helper functions using DS representation.

(define make-apply-proc
  (lambda (value-of)
    (lambda (rator rand)
      (pmatch rator
        [(clos ,id ,body ,env) 
         (value-of body (extend-env id rand env))]))))

(define closure
  (lambda (id body env)
    `(clos ,id ,body ,env)))

Closure helper functions using procedural representation.

(define apply-proc
  (lambda (rator rand)
    (rator rand)))

(define make-closure
  (lambda (value-of)
    (lambda (id body env)
      (lambda (a)
        (value-of body (extend-env id a env))))))

The following macros and test expressions will be used to test your code.

The test-divergence macro may not load properly under SWL--you may need to test your code from the command-line, or from within Emacs.

(define-syntax test
  (syntax-rules ()
    ((_ title tested-expression expected-result)
     (let* ((expected expected-result)
            (produced tested-expression))
       (if (equal? expected produced)
           (printf "~s works!\n" title)
           (error
            'test
            "Failed ~s: ~a\nExpected: ~a\nComputed: ~a"
            title 'tested-expression expected produced))))))

(define-syntax test-divergence
  (syntax-rules ()
    ((_ title tested-expression)
     (let ((max-ticks 1000000))
       (printf "Testing ~s (engine with ~s ticks fuel)\n" title max-ticks)
       ((make-engine (lambda () tested-expression))
        max-ticks
        (lambda (t v)
	  (error title "infinite loop returned ~s after ~s ticks" v (- max-ticks t)))
        (lambda (e^) (void)))))))

(define fact-5
  '((lambda (f)
      ((f f) 5))
    (lambda (f)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((f f) (sub1 n))))))))


(define fact-5-let
  '(let ([f (lambda (f)
              (lambda (n)
                (if (zero? n)
                    1
                    (* n ((f f) (sub1 n))))))])
     ((f f) 5)))

(define test-lambda
  '((lambda (x)
      ((lambda (y)
         (begin
           (set! y 5)
           x))
       x))
    0))

(define test-let
  '(let ((x 0))
     (let ((y x))
       (begin
         (set! y 5)
         x))))

(define test-let-strictness
  '(let ((y ((lambda (x) (x x)) (lambda (x) (x x)))))
     3))

(define test-begin
  '(let ((x 3))
     (begin
       (set! x 4)
       x)))

(define test-cbn
  '((lambda (f)
      5)
    ((lambda (f)
       (f f))
     (lambda (f)
       (f f)))))

(define test-count
  '((lambda (count)
      ((lambda (x) (* x x))
       ((lambda (y)
          (begin
            (set! count (* count 2))
            count))
        5)))
    1))

(define test-set!
  '(let ((f (lambda (x) (* x x))))
     (let ((n 5))
       (f (begin (set! n (sub1 n)) n)))))

You should run the following tests immediately after defining `value-of`.

(test "value-of-fact-5"
  (value-of fact-5 (empty-env))
  120)

(test "value-of-fact-5-let"
  (value-of fact-5-let (empty-env))
  120)

(test "value-of-test-lambda"
  (value-of test-lambda (empty-env))
  0)

(test "value-of-test-let"
  (value-of test-let (empty-env))
  0)

(test-divergence "value-of-test-let-strictness"
  (value-of test-let-strictness (empty-env)))

(test "value-of-test-begin"
  (value-of test-begin (empty-env))
  4)

(test-divergence "value-of-test-cbn"
  (value-of test-cbn (empty-env)))

(test "value-of-test-count"
  (value-of test-count (empty-env))
  4)

(test "value-of-test-set!"
  (value-of test-set! (empty-env))
  16)

You should run the following tests immediately after defining `value-of-ref`.

(test "value-of-ref-fact-5"
  (value-of-ref fact-5 (empty-env))
  120)

(test "value-of-ref-fact-5-let"
  (value-of-ref fact-5-let (empty-env))
  120)

(test "value-of-ref-test-lambda"
  (value-of-ref test-lambda (empty-env))
  5)

(test "value-of-ref-test-let"
  (value-of-ref test-let (empty-env))
  5)

(test-divergence "value-of-ref-test-let-strictness"
  (value-of-ref test-let-strictness (empty-env)))

(test "value-of-ref-test-begin"
  (value-of-ref test-begin (empty-env))
  4)

(test-divergence "value-of-ref-test-cbn"
  (value-of-ref test-cbn (empty-env)))

(test "value-of-ref-test-count"
  (value-of-ref test-count (empty-env))
  4)

(test "value-of-ref-test-set!"
  (value-of-ref test-set! (empty-env))
  16)

You should run the following tests immediately after defining `value-of-name`.

(test "value-of-name-fact-5"
  (value-of-name fact-5 (empty-env))
  120)

(test "value-of-name-fact-5-let"
  (value-of-name fact-5-let (empty-env))
  120)

(test "value-of-name-test-lambda"
  (value-of-name test-lambda (empty-env))
  5)

(test "value-of-name-test-let"
  (value-of-name test-let (empty-env))
  5)

(test-divergence "value-of-name-test-let-strictness"
  (value-of-name test-let-strictness (empty-env)))

(test "value-of-name-test-cbn"
  (value-of-name test-cbn (empty-env))
  5)

(test "value-of-name-test-count"
  (value-of-name test-count (empty-env))
  8)

(test "value-of-name-test-set!"
  (value-of-name test-set! (empty-env))
  12)

You should run the following tests immediately after defining `value-of-need`.

(test "value-of-need-fact-5"
  (value-of-need fact-5 (empty-env))
  120)

(test "value-of-need-fact-5-let"
  (value-of-need fact-5-let (empty-env))
  120)

(test "value-of-need-test-lambda"
  (value-of-need test-lambda (empty-env))
  5)

(test "value-of-need-test-let"
  (value-of-need test-let (empty-env))
  5)

(test-divergence "value-of-need-test-let-strictness"
  (value-of-need test-let-strictness (empty-env)))

(test "value-of-need-test-cbn"
  (value-of-need test-cbn (empty-env))
  5)

(test "value-of-need-test-count"
  (value-of-need test-count (empty-env))
  4)

(test "value-of-need-test-set!"
  (value-of-need test-set! (empty-env))
  16)

Brainteaser:Add to your call-by-value interpreter a lazy cons operator, cons$, and associated operators car$ and cdr$, which can be used to define the primes program shown in lecture.