CS217 Day 8 Wednesday, April 12, 2000

Data Abstraction II

Some more ADTs and their implementation.
  1. Primitive expressions
    Let a primitive expression be an integer arithmetic expression involving addition, subtraction, multiplication, adding one and subtracting one.
    • List Concrete Syntax 
      [pe-list] ::= [number]
            | (+ [pe-list] [pe-list])
            | (- [pe-list] [pe-list])
            | (* [pe-list] [pe-list])
            | (add1 [pe-list])
            | (sub1 [pe-list])
    • Character Concrete Syntax 
      [pe-char] ::= [number]
            | +([pe-char], [pe-char])
            | -([pe-char], [pe-char])
            | *([pe-char], [pe-char])
            | add1([pe-char])
            | sub1([pe-char])
    • Abstract Syntax for pe can be defined by 
      (define-datatype pe pe?
  (lit-pe (datum number?))
  (add-pe (rand1 pe?) (rand2 pe?))
  (subtract-pe (rand1 pe?) (rand2 pe?))
  (mult-pe (rand1 pe?) (rand2 pe?))
  (incr-pe (rand1 pe?))
  (decr-pe (rand1 pe?)))
    • Concrete representation of Abstract Syntax 
      [pe-rep] ::= (lit-pe [number])
           | (add-pe [pe-rep] [pe-rep])
           | (subtract-pe [pe-rep] [pe-rep])
           | (mult-pe [pe-rep] [pe-rep])
           | (incr-pe [pe-rep])
           | (decr-pe [pe-rep])
    • Define the pe ADT to be quantities with constructors lit-pe, add-pe, subtract-pe, mult-pe, incr-pe and decr-pe, with argument types as specified by define-datatype.

      • parse-pe : pe-list -> pe -- list syntax to abstract syntax 
        (define parse-pe
  (lambda (datum)
    (cond ((number? datum)
	   (lit-pe datum))
	  ((pair? datum)
	   (case (car datum)
	     ((+) (add-pe
		    (parse-pe (cadr datum))
		    (parse-pe (caddr datum))))
	     ((-) (subtract-pe
		    (parse-pe (cadr datum))
		    (parse-pe (caddr datum))))
	     ((*) (mult-pe
		    (parse-pe (cadr datum))
		    (parse-pe (caddr datum))))
	     ((add1) (incr-pe (parse-pe (cadr datum))))
	     ((sub1) (decr-pe (parse-pe (cadr datum))))
	     (else
	       (error 'parse-pe "bad prim exp ~s" datum))))
	  (else
	    (error 'parse-pe "bad prim exp ~s" datum)))))
      • show-pe : pe-list -> pe-rep -- abstract syntax to concrete reprentation of abstract syntax 
        (define show-pe
  (lambda (x)
    (cases pe x
      (lit-pe (datum)
	(list 'lit-pe datum))
      (add-pe (rand1 rand2)
	(list 'add-pe (show-pe rand1) (show-pe rand2)))
      (subtract-pe (rand1 rand2)
	(list 'subtract-pe (show-pe rand1) (show-pe rand2)))
      (mult-pe (rand1 rand2)
	(list 'mult-pe (show-pe rand1) (show-pe rand2)))
      (incr-pe (rand)
	(list 'incr-pe (show-pe rand)))
      (decr-pe (rand)
	(list 'decr-pe (show-pe rand)))
      (else
	(error 'show-pe "bad pe ~s" x)))))
      • unparse-pe : pe -> pe-list -- abstract syntax to list syntax 
        


      •  eval-pe : pe -> number -- evaluate abstract syntax tree

        


      •  eval-pe-list : pe-list -> number -- evaluate pe-list

        (define eval-pe-list
  (lambda (datum)
    (eval-pe (parse-pe datum))))

        

      

One could compute other things for a pe, such as the number of
parenthesis in its list representation or the number of lit-pe's.


    

    


  2.  The Environment Interface

    

An environment is a function whose domain is
a finite set of Scheme symbols and whose range is the set of Scheme
values.


    


      


    • The environment interface has three procedures,

      empty-env : Nothing -> environment
apply-env : environment x symbol -> value
extend-env : list-of-symbol x list-of-value x environment -> environment

      
with meanings

      (empty-env) -- f such that f(s) is undefined for all s
(apply-env env sym) -- the value of sym in environment env
(extend-env syms vals env) -- f such that f(s) = v if s is in syms
                              and v is corresponding value in vals,
                              otherwise the value of s in env

      


    •  Procedural representation
      

A procedural representation of data is often the easiest in a language
such as Scheme, in which procedures are first-class,
objects which can be returned as a value and stored in data structures.


      (define empty-env
  (lambda ()
    (lambda (sym)
      (error 'empty-env "no association for ~s" sym))))

(define extend-env
  (lambda (syms vals env)
    (lambda (sym)
      (let ((p (list-find-position sym syms)))
	(if p
	    (list-ref vals p)
	    (apply-env env sym))))))

(define apply-env
  (lambda (env sym)
    (env sym)))

;; (list-find-position sym los) => zero- based position of sym
;;                                 in los, otherwise #f

(define list-find-position (lambda (sym los) ...))

      


    •  Abstract Syntax Tree representation
      
The interface constuctors are implemented by define-datatype

      (define-datatype environment environment?
  (empty-env)
  (extend-env
    (syms (list-of symbol?))
    (vals (list-of scheme-value?))
    (env environment?)))

(define scheme-value? (lambda (x) #t))

(define apply-env
  (lambda (env sym)
    (cases environment env
      (empty-env ()
	(error 'empty-env "no association for ~s" sym))
      (extend-env (syms vals env)
	(let ((p (list-find-position sym syms)))
	  (if p
	      (list-ref vals p)
	      (apply-env env sym)))))))

(define list-find-position (lambda (sym los) ...))

      


    •  Ribcage representation

      (define empty-env
  (lambda () '()))

(define extend-env
  (lambda (syms vals env)
    (cons
      (cons
	syms
	(apply vector vals))
      env)))

(define apply-env (lambda (env sym) ...))

      
Some efficiency is achieved by using vectors and
vector-ref instead of list-ref in looking up the value of a symbol.


    


    


  3. cs217d8.scm has pe defs, tests.