CIS 352   —   SPRING 2009

Homework 6

Coverage

• Essentials of Programming Languages (EOPL): Section 3.4.

Logistics

• You may work singly or in pairs on this assignment.

• Be sure you mark (via comments) each change you make to the LET interpreter files.
  (See the Homework Policy for more details.)

What to Turn in:

• A copy of the source code of each file modified.

• DO NOT turn in the source code from files you did not modify.

• A run of your code that verifies that it passes all the tests in your test harness.

  For Exercise 3.28, make the necessary changes to interp.scm, debug the result, and when you are done, save this version of the file as interp2.scm which you can include in the zip archive.

How to turn in your work:

1. If you have more than one file to submit, bundle them into a zip or tar archive.

2. Click on this electronic-submission link, and use your NetID and password for authorization.
   Important: Make sure you select CIS 352 as the course for which you're submitting.

PROBLEMS

1. (10 points)   EOPL Exercise 3.20

2. (30 points)   EOPL Exercise 3.21

3. (30 points)   EOPL Exercise 3.27

4. (30 points)   EOPL Exercise 3.28
   Ignore the procedure-representation part.

• (20 points)   EOPL Exercise 3.23

Notes

• For Exercise 3.21:

  • In data-structures.scm, you will need to change the procedure case of the proc data-type to:

    (procedure
      (vars (list-of symbol?))
      (body expression?)
      (env environment?))
    

  • In lang.scm, you will need to change the procedure and application productions in the-grammar to:

    (expression
     ("proc" "(" (separated-list identifier ",") ")" expression)
     proc-exp)
    
    (expression
     ("(" expression (arbno expression )")")
     call-exp)
    

  • In interp.scm, you will also have to change the proc-exp and call-exp cases of value-of as well as changing apply-procedure.

• For Exercise 3.27:
  • To the expval datatype, add the clause:

    (traceproc-val 
     (proc proc?))

    You will also have to add traceproc (or traceproc-val or traceproc-exp) cases to expval->proc, the-grammar, value-of, apply-procedure, and the proc datatype.

  • As how to display the tracing info, consider the example:

    (define traced-fact
      (lambda (n)
        (display "entering with argument ")
        (display n)
        (newline)
        (let ((answer (if (zero? n) 
                          1
                          (* n (traced-fact (- n 1))))))
          (display "exiting with result: ")
          (display answer)
          (newline)
          answer)))

• For Exercise 3.28, you will need to change value-of and apply-procedure for this problem. In particular, apply-procedure will now take an environment parameter for the “environment at the point of call”. You do not have to change the representation of procedures — even though the saved-env field is not used for anything in dynamic binding. (Hint, hint, hint!!!)

• Exercise 3.23 is a version of the famous Y combinator.

• (Changed)

  Be sure to include the following test. (Yes, you need more tests than this one.)

       (scoping-1 "let a = 3
   in let p = proc(x) -(x,a) 
       in let a = 5
           in -(a,(p 2))" 6) 
        

  Under dynamic scoping, the answer should be 8, not 6. So change this test in those runs.

  Some of the other procedure related tests may give you different results under dynamic scoping.

• (Added)

  You might want to include

    (define extend-env*
      (lambda (syms vals old-env)
        (if (null? syms)
            old-env
            (extend-env 
              (car syms) 
              (car vals) 
              (extend-env* (cdr syms) (cdr vals) old-env)))))

  in environments.scm. It is useful for a couple of the problems.

• (Added)

  In my solution to the dynamic scoping problem, I ended up changing only 4 lines of code — and that is with making traceproc's dynamically scoped too.