Assignment 2, Due Monday, April 10, 2000

1. Write a procedure parse which converts the following input language into the following intermediate datatype.

   (Note: You can use parse provided in the Scheme file cs217d5.scm supporting Day 5 notes. But it is an excellent exercise to write your own, using the provided version as a guide if you need one.)

   The input language is the subset of Scheme defined by

        [input-exp]          ::=
            [number]                                  ; literal
          | [symbol]                                  ; variable reference
          | (if [input-exp] [input-exp] [input-exp])  ; if expression
          | (let [list of input-decl] [input-exp])    ; let expression
          | (lambda [list of symbol] [input-exp])     ; procedure
          | ([input-exp] [input-exp]*)         ; application
   
        [input-decl]         ::=
            ([symbol] [input-exp])
   
        [list of input-decl] ::=
            () | ([input-decl] . [list of input-decl])
   

   The intermediate datatype is defined with define-datatype:

   
   (define-datatype expression expression?
          (lit-exp     (datum     number?))
          (var-exp     (id        symbol?))
          (if-exp      (test-exp  expression?)
                       (true-exp  expression?)
                       (false-exp expression?))
          (let-exp     (ids       (list-of symbol?))
                       (exps      (list-of expression?))
                       (body      expression?))
          (proc-exp    (ids       (list-of symbol?))
                       (body      expression?))
          (app-exp     (rator     expression?)
                       (rands     (list-of expression?))))
   

   You can just copy this code.

2. Write a procedure show-exp which takes an intermediate datatype expression and returns a list "debug" form, using the syntax.

   (Note: If you use dj.scm, the intermediate representation is already in this list form, but you can't depend on that. See unparse in cs217d5.scm for an example to follow.)

   [debug-exp] ::=
           (lit-exp [integer])
         | (var-exp [symbol])
         | (if-exp [debug-exp] [debug-exp] [debug-exp])
         | (let-exp [list of symbol] [list of debug-exp] [debug-exp])
         | (proc-exp [list of symbol] [debug-exp])
         | (app-exp [debug-exp] [list of debug-exp])
   

3. Write free-vars-parsed which takes an expression and returns a list of its free variables. Write free-vars which applies parse and then free-vars-parsed to its list syntax argument.

   Note: You can use append for set-union
   But you will need to write set-difference. (See below.)

4. Similarly, write bound-vars-parsed and bound-vars which returns a list of bound variables.

   Note: You can use append for set-union
   But you will need to write set-intersection. (See below.)

5. Complete the definition of lex-add-parsed in cs217d5.scm so lexical-address (defined there) works for expressions containing if and let.

6. Write set-difference and set-intersection.

   • (set-difference s1 s2) => list of elements in s1 but not in s2
     
     Recursive def:
     
     (set-difference '() s2) = ()
     
     (set-difference '(a . rest1) s2)
     		= (set-difference rest1 s2), if (memv 'a s2)
                       (a . (set-difference rest1 s2)), otherwise
     

   • (set-intersection s1 s2) => list of element in both s1 and s2
     
     Recursive def:
     
     (set-intersection '() s2) = ()
     
     (set-intersection '(a . rest1) s2)
     		= (a . (set-intersection rest1 s2)), if (memv 'a s2)
                       (set-intersection rest1 s2), otherwise