Carleton University
School of Computer Science
95.501 Assignment 2 (Fall '2001)

Due:    October 26, before class

All forms of computation can be explained in terms of how environments and bindings are created, maintained and destroyed by the language processor. The contour model provides a simple graphical way to show what happens during a computation. Working with a scheme metacircular interpreter provides a mechanism for you to become intimately aware of the inner workings of how the interpreter manages environments, bindings and evaluates of scheme expressions. The base metacircular interpreter for this assignment is located by following the following link (meta.scm) . You should follow the programming style and guidelines set forth in class. In particular, use meaningful names for variables and procedures, use recursion wherever possible and write concise readable procedures. For each problem, turn in a listing of your procedures, when applicable, and a demonstration showing the problem has been solved. It is up to you to make up a convincing test plan.
1) Trace the execution of the following expressions. Give the execution snapshots just before the points marked with a ** and indicate what is displayed.
 
(define (new-point ix iy)
     ((lambda (x y)
          (define (getx) x)
          (define (setx sx) (set! x sx))
          (define (gety) y)
          (define (sety sy) (set! y sy))
            **
          (define (dispatch m y)
                **
               (cond    ((= m 1) (getx))
                            ((= m 2) (gety))
                            (( = m 3) (setx y))
                            ((= m 4) (sety y))))
          dispatch)
     ix iy))

(define getx 1)
(define gety 2)
(define setx 3)
(define sety 4)
(define point (new-point 20 40))
(define first car)
(define reset cdr)
**
(display (point 3 32 ))
**

2) Write the following DEFINE_PROCEDURE and WHILE macros for Scheme (NOT THE Metacircular Interpreter):
 
(DEFINE_PROCEDURE procedureName (arg1 ar2 ...)        e.g. (DEFINE_PROCEDURE add_and_divide_by_two (x y)
    local1 value1                                                                                    sum (+ x y)
    local2 value 2
    ...
                                                                                                            BEGIN
    BEGIN                                                                                                (/ sum 2)
    expression1
    expression2                                                                                      END_PROCEDURE)
    ...
    END_PROCEDURE)
 

(WHILE (someTest) DO                                                            e.g. (WHILE (< x 10) DO
    BEGIN                                                                                            BEGIN
        expression1                                                                                        (set! x (+ 1 x))
        experssion2                                                                                        (display (* x x))
        .....                                                                                               END-WHILE)
    END-WHILE)

2) Implement a macro facility for the metacircular interpreter that  will eliminate the need for adding speciall forms to it . Write and test the DEFINE_PROCEDURE  and WHILE macros for the metacircular interpreter (NOT Scheme) using its new macro facility:
IN GENERAL Don’t forget to demonstrate that your changes to the metacircular work in all cases! When you hand in your new listing of Meta.scm, be sure to CLEARLY indicate all of the changes you have made. The easiest way is to use a pen to highlight the modified areas.

Testing:

Be sure to test your procedures thoroughly and make sure to pick meaningful test cases.  It is up to you to make up a convincing test plan (i.e. convince the TAs that your procedures work properly).   Make sure you test all your procedures.

Submission:

Submit a printout of all of your procedures and along with a copy of the output generated from the testing.   Be sure to include comments where appropriate in your code and make sure that all output is clearly explained.  Testing will be marked!   It is always a good idea to highlight the beginning of the procedure on the printout.  Place your name, student #, course#, and assignment # on the top of each page.   Put all printouts in one unsealed envelope, with this same information clearly marked on the envelope. You should also include a diskette containing the procedures and test output files you generated for the assignment. All of these files should be stored in the directory A:\ASS2 (actually B:\ASS2 when in the labs here).  Finally, hand in your assignment in the correct slot in room 4135 of the Herzberg Building (beside the lab) or slide it under your professor's door if the slot is full. Don't forget that the assignment will be marked for style, testing and your solutions.