Assignment 5: Parameter-Passing Conventions

Below is an interpreter that is complete except for its five helpers empty-env, extend-env, apply-env, closure, and apply-proc. 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)
    (pmatch exp
      [,b (guard (boolean? b)) b]
      [,n (guard (number? n)) n]
      [,x (guard (symbol? x)) (apply-env env x)]
      [(zero? ,n) (zero? (value-of n env))]
      [(sub1 ,n) (sub1 (value-of n env))]
      [(* ,n1 ,n2) (* (value-of n1 env) (value-of n2 env))]
      [(lambda (,x) ,body) (closure x body 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))]
      [(random ,n) (random (value-of n env)]
      [(,rator ,rand) (apply-proc (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, closure, and apply-proc helpers. Use a procedural representation of both environments and procedures.
• For the most part, you can use the same set of helpers for every interpreter. However, since closure calls the interpreter, you'll need to implement versions of 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!.
• During lecture, Dan showed how we can use boxes to help implement parameter-passing conventions. For more about boxes and the operations you can perform with them, see the Chez Scheme User's Guide. However, if you don't want to use the boxes built into Chez Scheme (for example, if you're using a different Scheme implementation), feel free to implement your own boxes using the box, unbox, and set-box! procedures shown in lecture.

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

;; Making sure set! works
(test "set!"
  (val-of-cbr
   '((lambda (x) (begin2 (set! x #t)
                         (if x 3 5))) #f)
   (empty-env))
  3)
 
;; Returns 4 under CBR...
(test "interesting-cbr-1"
  (val-of-cbr
   '((lambda (a)
       ((lambda (p)
          (begin2
           (p a)
           a)) (lambda (x) (set! x 4)))) 3)
   (empty-env))
  4)
 
;; ...but returns 3 under CBV.
(test "interesting-cbv-1"
  (val-of-cbv
   '((lambda (a)
       ((lambda (p)
          (begin2
           (p a)
           a)) (lambda (x) (set! x 4)))) 3)
   (empty-env))
  3)
 
;; returns 44 under CBR...
(test "interesting-cbr-2"
  (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)
 
;; ...but returns 55 under CBV!  You can change the "begin2" to
;; "begin" and evaluate this in the Scheme REPL as evidence that
;; Scheme uses CBV.
(test "interesting-cbv-2"
  (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)
 
;; Returns 44 under CBR...
(test "interesting-cbr-3"
  (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)
 
;; ...but returns 33 under CBV.
(test "interesting-cbv-3"
  (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)))
 
;; call-by-name
;;P(false positive) ≤ .01                                                     
(test "random-by-name"
  (val-of-cbname random-sieve (empty-env)) #f)
 
;; call-by-need                                                                  
(test "random-by-need"
  (val-of-cbneed random-sieve (empty-env)) #t)
 
;; Does not terminate with val-of-cbr or val-of-cbv -- try it!
(test "omega-by-name"
  (val-of-cbname
   '((lambda (z) 100)
     ((lambda (x) (x x)) (lambda (x) (x x))))
   (empty-env))
  100)

Super-awesome brainteaser coming soon!