CS217 Day 6 Friday, April 7, 2000

Free/Bound vars in Abstract Syntax

We're working with Concrete List Syntax

[expression] ::= [id]
               | [number]
               | (if [expression] [expression] [expression])
               | (lambda ({[id]}*) [expression])
               | (let ({([id] [expression])}*) [expression])
               | ({[expression]}+)

and Abstract Syntax

[var-exp]          var-exp (id)
[lit-exp]          lit-exp (datum)
[if-exp]           if-exp (test-exp true-exp false-exp)
[lambda-exp]       proc-exp (ids body)
[let-exp]          let-exp (ids exps body)
[app-exp]          app-exp (rator rands)

implemented by

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

Also note:

• define-datatype is defined in Petite Scheme on campus machines by preloading datatype-chez.ss. Also available is dj.scm which uses the above list representation for data types.

• Character syntax can be read and parsed by loading (in order)
  • dj.scm
  • sllgen.scm, and
  • grammar-dan.scm
  and using scan&parse.

• cs217d5.scm contains
  • define-datatype for expression
  • parse for parsing list syntax into abstract syntax, and
  • unparse for converting abstract syntax into list syntax.
  • Examples below.

Writing free-vars-parsed and , which return lists of free and bound variables in a parsed expression.

1. Use unparse from cs217d5.scm as a template,

   (define unparse
     (lambda (exp)
       (cases expression exp
         (lit-exp (datum)
   	datum)
         (var-exp (id)
   	id)
         (if-exp (test-exp true-exp false-exp)
   	(list
   	  'if
   	  (unparse test-exp)
   	  (unparse true-exp)
   	  (unparse false-exp)))
         (proc-exp (ids body)
   	(list
   	  'lambda
   	  ids
   	  (unparse body)))
         (let-exp (ids exps body)
   	(list
   	  'let
   	  (map (lambda (id exp)
   		 (list id (unparse exp)))
   	    ids exps)
   	  (unparse body)))
         (app-exp (rator rands)
   	(cons
   	  (unparse rator)
   	  (map unparse rands)))
         (else
   	(error 'unparse exp)))))
   

2. Replace unparse with free-vars-bound and use the definition of free variable.

   (define free-vars-parsed
     (lambda (exp)
       (cases expression exp
         (lit-exp (datum)
   	EMPTY LIST
   	)
         (var-exp (id)
   	LIST OF ID
   	)
         (if-exp (test-exp true-exp false-exp)
   	(list
   	  'if
   	  (free-vars-parsed test-exp)
   	  (free-vars-parsed true-exp)      WANT UNION OF FREE VARS FOUND
   	  (free-vars-parsed false-exp)))
         (proc-exp (ids body)
   	FREE VARS IN BODY EXCEPT FOR VARS IN IDS
   	)
         (let-exp (ids exps body)
   	UNION OF FREE VARS IN ANY OF EXPS
   	AND FREE VARS IN BODY EXCEPT VARS IN IDS
   	)
   	(app-exp (rator rands)
   	(cons
   	  (free-vars-parsed rator)
   	  (map free-vars-parsed rands)))   WANT UNION OF FREE VARS FOUND
         (else
   	(error 'free-vars-parsed exp)))))
   

3. Replace unparse with bound-varsbound and use the definition of free variable.

   (define bound-vars-parsed
     (lambda (exp)
       (cases expression exp
         (lit-exp (datum)
   	EMPTY LIST
   	)
         (var-exp (id)
   	EMPTY-LIST
   	)
         (if-exp (test-exp true-exp false-exp)
   	(list
   	  'if
   	  (bound-vars-parsed test-exp)
     	  (bound-vars-parsed true-exp)     WANT UNION OF BOUND VARS FOUND
   	  (bound-vars-parsed false-exp)))
         (proc-exp (ids body)
   	INTERSECTION OF IDS AND VARS FREE IN BODY
           TOGETHER WITH BOUND VARS IN BODY
   	)
         (let-exp (ids exps body)
   	UNION OF BOUND VARS IN ANY OF EXPS
   	AND INTERSECTION OF IDS AND VARS FREE IN BODY
   	)
         (app-exp (rator rands)
   	(cons
   	  (bound-vars-parsed rator)
   	  (map bound-vars-parsed rands)))  WANT UNION OF BOUND VARS FOUND
         (else
   	(error 'bound-vars-parsed exp)))))
   

4. You will need set-difference, set-intersection which are defined by

   (set-difference '() s2) = ()
   
   (set-difference '(a . rest1) s2)
   		= (set-difference rest1 s2), if (memv 'a s2)
                     (a . (set-difference rest1 s2)), otherwise
   

   and

   (set-intersection '() s2) = ()
   
   (set-intersection '(a . rest1) s2)
   		= (a . (set-intersection rest1 s2)), if (memv 'a s2)
                     (set-intersection rest1 s2), otherwise
   

   and you could use set-union, defined by

   (set-union2 '() s2) => s2
   
   (set-union2 '(a . rest1) s2) =>
                    = (set-union2 rest1 s2)), if (memv 'a s2)
                    = (a . (set-union2 rest1 s2), otherwise
   
   (set-union s1 s2 ...)
                    = (set-union s1 (set-union s2 ...))
   

   An implementation using these defs

   (define set-union2
     (lambda (s1 s2)
       (if (null? s1)
   	s2
   	(if (memv (car s1) s2)
   	    (set-union2 (cdr s1) s2)
   	    (cons (car s1) (set-union2 (cdr s1) s2))))))
   
   (define set-union
     (lambda sets
       (cond ((null? sets)
   	   '())
   	  ((null? (cdr sets))
   	   (car sets))
   	  (else
   	    (set-union2
   	      (car sets)
   	      (apply set-union (cdr sets)))))))
   
   

   This and another implementation, set-append, which preserves order, together with tests, are in cs217d6.scm.

   Also there, is code for string->list-syntax to convert string syntax to list syntax.