CS217 Day 5 Wednesday, April 5, 2000

Lexical Address Using Abstract Syntax

Abstract Syntax

• We will find it convenient to process expressions in an abstract syntax form using a cases special form to access the kinds and fields of an expression datatype, which we implement with define-datatype.

  It will also be useful to use both list and a character concrete syntaxes for expressions. Character syntax expressions are easier to read, and will be used for the defined languages we will build interpreters for.

  The following two expressions, in concrete list and character syntax, can be parsed into the same intermediate or abstract syntax.

  (let ((x 2)
        (sqr (lambda (x)
               (prod x x))))
    (sqr x))
  

  and

  let x = 2
      sqr = proc(x)
             (prod x x)
  in (sqr x)
  

  These expressions each parse to the following abstract syntax.

    (let-exp
      (x sqr)
      ((lit-exp 2)
       (proc-exp
         (x)
         (app-exp (var-exp prod) ((var-exp x) (var-exp x)))))
      (app-exp (var-exp sqr) ((var-exp x))))
  

  Each kind of expression is named and has fields which have specified types.

• We will use the following subset of Scheme. (Cf Ex 1.3.10, p36, but with numbers and let.)

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

• We will associate an abstract syntax to each kind of expression.

  [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)
  

• Abstract syntax will be implemented using define-datatype. Each field is provided with a recognizer for its type of value.

  (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?))))
  

• 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 datatypes.

  Character syntax can be read and parsed by loading sllgen.scm and grammar-dan.scm and using scan&parse.

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

Lexical Address, free/bound

• Computing lexical address using abstract syntax.
  lex-add-parsed is implemented for list syntax with BNF

  [exp] ::= [symbol] | (lambda [varlist] [exp]) | ({[exp]}+)
  

  lexical-address parses its argument and then computes its lexical address using lex-add-parsed.

  ;; lex-add-parsed -- lexical address of parsed expressions
  
  (define lex-add-parsed
    (lambda (exp vlsts)
      (cases expression exp
        (var-exp (id)
  	(cons id (depth-pos id vlsts 0)))
        (proc-exp (ids body)
  	(list
  	  'lambda
  	  ids
  	  (lex-add-parsed body (cons ids vlsts))))
        (app-exp (rator rands)
  	(cons
  	  (lex-add-parsed rator vlsts)
  	  (map (lambda (rand)
  		   (lex-add-parsed rand vlsts))
  	      rands)))
        (else
  	(error 'lex-add-parsed "not done ~s" exp)))))
  
  (define lexical-address
    (lambda (datum)
      (lex-add-parsed (parse datum) '())))
  
  (lexical-address '(lambda (x y)
  		    ((lambda (x) (p x y)) (q x y))))
  

  The abstract syntax for the example, and its lexical address are

  (proc-exp
    (x y)
    (app-exp
      (proc-exp
        (x)
        (app-exp (var-exp p) ((var-exp x) (var-exp y))))
      ((app-exp (var-exp q) ((var-exp x) (var-exp y))))))
  

  and

  (lambda (x y)
    ((lambda (x) ((p : free) (x : 0 0) (y : 1 1)))
     ((q : free) (x : 0 0) (y : 0 1))))
  

• occurs-free-parsed?

  ;; occurs-free-parsed?
  
  (define occurs-free-parsed?
    (lambda (var exp)
      (cases expression exp
        (var-exp (id)
  	(if (eqv? var id)
  	    #t
  	    #f))
        (proc-exp (ids body)
  	(and (not (memv var ids))
  	     (occurs-free-parsed? var body)))
        (app-exp (rator rands)
  	(or (occurs-free-parsed? var rator)
  	    (exists? (lambda (rand)
  		       (occurs-free-parsed? var rand))
  	      rands)))
        (else
  	(error 'occurs-free-parsed? "not done ~s" exp)))))
  
  (define exists?
    (lambda (pred lst)
      (if (null? lst)
  	#f
  	(if (pred (car lst))
  	    #t
  	    (exists? pred (cdr lst))))))
  
  (occurs-free-parsed? 'y (parse '(x y z)))
  
  (occurs-free-parsed? 'p (parse '(lambda (x y)
  				  ((lambda (x) (p x y)) (q x y)))))
  

Extend lex-add-parsed and occurs-free-parsed?.
We will be studying/implementing more data types using define-datatype next week. See Ch 2 for expression example.