CS217 Day 7 Monday, April 10, 2000

Data Abstraction

A data type is a set of quantities represented in some way, together with operations for manipulating these quantities.
An abstract data type (ADT) is a specification of operations on a set of quantities which is independent of a particular representation of the quantities.
We have already used define-datatype to implement an expression data type for internally representing concrete list syntax expressions in a subset of Scheme. It is an abstraction that allows us to implement data types which can be specified concretely in a list syntax using BNF.
The internal representation of a data type defined using define-datatype depends upon its implementation -- as procedures (datatype.ss), Chez Scheme records (datatype-chez.ss), and lists (dj.scm). The representing data structure is a variant record whose fields can be extracted using the cases special form. The variant records define an abstract syntax tree for the represented data value.
BNF for a concrete list representation of a data type implemented with define-datatype can be read off from the definition. E.g.,
(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?))))
implements the concrete syntax defined by
[expression] ::= (lit-exp [symbol])
               | (var-exp [number])
               | (if-exp [expression] [expression] [expression])
               | (proc-exp ({[symbol]}*) [expression])
               | (let-exp ({[symbol]}*) ({[expression]}*) [expression])
               | (app-exp [expression] ({[expression]}+))
This is concrete syntax for abstract syntax for Scheme expressions!! The value of an expression in this language is an abstract syntax tree for the represented datum.
We will be studying the meaning of various programming language concepts by writing interpreters which implement their meaning. In evaluating expressions, we will need to represent bindings of free variables. This will be done via a finite function ADT.
Our interpreters will be Scheme programs, so the meaning of concepts will be defined relative to the semantics of Scheme. But the ultimate goal is to represent the interpreters in terms of data types manipulated by a low level machine with obvious semantics. We won't be able to go that far, but we will be rewriting our interpreters to eliminate their dependency on recursion in Scheme, writing them in continuation-passing style or CPS.
Examples of ADTs and their implementation.
nni, the nonnegative integers.
nni has a constant zero and procedures is-zero?, succ and pred such that
 is-zero: nni -> bool
(is-zero n) = #t, if n = zero, and #f otherwise.

 succ : nni -> nni
(succ n) is different from n

 pred : nni - {zero} -> nni
(pred (succ n)) = n
For testing, we also want procedures
integer->nni : integer -> nni
nni->integer : nni -> integer
which convert a Scheme integer to an nni and an nni to a Scheme integer
Unary representation
(define zero '())
(define is-zero? null?)
(define succ (lambda (n) (cons #t n)))
(define pred cdr)
(define integer->nni (lambda (n) (duple #t n)))
(define duple
  (lambda (x n)
    (if (zero? n) '() (cons x (duple x (- n 1))))))
(define nni->integer list-length)
Scheme representation
(define zero 0)
(define is-zero? zero?)
(define succ (lambda (n) (+ n 1)))
(define pred (lambda (n) (- n 1)))
(define integer->nni (lambda (n) n))
(define nni->integer (lambda (n) n))
Abstract Syntax Tree representation using define-datatype
;; BNF for concrete syntax:
;; [nni-rep] ::= (the-zero)
;;             | (succ [nii-rep])


(define-datatype nni nni?
  (the-zero)
  (succ (n nni?)))

(define is-zero?
  (lambda (n)
    (cases nni n
      (the-zero () #t)
      (succ (m) #f))))

(define pred
  (lambda (n)
    (cases nni n
      (the-zero ()
	(error 'pred "no pred of ~s" n))
      (succ (m)
	m))))

(define integer->nni
  (lambda (n)
    (if (zero? n)
	(the-zero)
	(succ (integer->nni (- n 1))))))

(define nni->integer
  (lambda (n)
    (cases nni n
      (the-zero ()
	0)
      (succ (m)
	(+ (nni->integer m) 1)))))
We can use the nni interface to define plus and times which implement addition and multiplication for any of these representations.
(define plus
  (lambda (x y)
    (if (is-zero? x)
	y
	(succ (plus (pred x) y)))))

(define times
  (lambda (x y)
    (if (is-zero? x)
	zero
	(plus (times (pred x) y) y))))
We can test any of these implementations using
(define test-nni
  (lambda (proc . args)
    (let ((nni-args (map integer->nni args)))
      (nni->integer (apply proc nni-args)))))
For example, for each implemation of nni,
(test-nni succ 2) => 3
(test-nni pred 5) => 4
(test-nni plus 2 3) => 5
(test-nni times 2 3) => 6
Binary tree
A bintree is either a leaf-node or an interior-node. A leaf node consists of a number, its datum, and an interior node consists of a key that is a symbol, and bintrees left and right. An ADT prescribes constructors for each variant, recognizers, and selectors for the fields of each variant.
List representation
(define leaf-node (lambda (n) n))
(define interior-node (lambda (s lt rt) (list s lt rt)))

(define leaf-node? number?)

(define interior-node?
  (lambda (x)
    (and (list? x)
	 (= (length x) 3)
	 (symbol? (car x))
	 (bintree? (cadr x))
	 (bintree? (caddr x))))))
    
(define bintree?
  (lambda (x)
    (or (leaf-node? x)
	(interior-node? x))))

(define leaf->datum (lambda (x) x))
(define interior->key car)
(define interior->left cadr)
(define interior->right caddr)
Abstract Syntax Tree representation
(define-datatype bintree bintree?
  (leaf-node
    (datum number?))
  (interior-node
    (key symbol?)
    (left bintree?)
    (right bintree?)))

(define leaf-node?
  (lambda (x)
    (and (bintree? x)
	 (cases bintree x
	   (leaf-node (datum) #t)
	   (else #f)))))

(define leaf->datum
  (lambda (x)
    (cases bintree x
      (leaf-node (datum) datum)
      (else (error 'bintree "Not a leaf-node")))))

(define interior->key
  (lambda (x)
    (cases bintree x
      (interior-node (key left right) key)
      (else 'bintree "Not an interior-node"))))
      
(define interior->left
  (lambda (x)
    (cases bintree x
      (interior-node (key left right) left)
      (else 'bintree "Not an interior-node"))))
      
(define interior->right
  (lambda (x)
    (cases bintree x
      (interior-node (key left right) right)
      (else 'bintree "Not an interior-node"))))

(define list-rep->bintree
  (lambda (x)
    (if (number? x)
	(leaf-node x)
	(interior-node
	  (car x)
	  (list-rep->bintree (cadr x))
	  (list-rep->bintree (caddr x))))))

(define bintree->list-rep
  (lambda (x)
    (cases bintree x
      (leaf-node (datum) datum)
      (interior-node (key left right)
	(list
	  key
	  (bintree->list-rep left)
	  (bintree->list-rep right))))))
Writing leaf-sum to the interface:
(define leaf-sum
  (lambda (x)
    (if (is-leaf? x)
	(leaf->datum x)
	(+
	  (leaf-sum (interior->left x))
	  (leaf-sum (interior->right x))))))
Writing leaf-sum for the abstract syntax or define-datatype rep.
(define leaf-sum-dd
  (lambda (x)
    (cases bintree x
      (leaf-node (datum)
	datum)
      (interior-node (key left right)
	(+ (leaf-sum-dd left) (leaf-sum-dd right))))))
Environment ADT
cs217d7.scm