subsections:


Modules -- a functional interface

ADT



  typedef int element; 
  struct list;
  
  extern list* nil();
  extern list* cons(element e, list* l);
  extern element head(list* l);
  extern list* tail(list* l);
  extern bool equal(list* l, list* m);
  

slide: Modules -- a functional interface


Objects -- a method interface

OOP



  template< class E > 
  class list {
  public:
  list() { }
  virtual ~list() { }
  virtual bool empty() = 0;
  virtual E head()  = 0;
  virtual list* tail() = 0;
  virtual bool operator==(list* m) = 0;
  };
  

slide: Objects -- a method interface


Modules -- representation hiding

ADT



  typedef int element;
  
  enum { NIL, CONS };
  
  struct list {
  int tag;
  element e;
  list* next;
  };
  

Generators


  list* nil()  { 
nil
list* l = new list; l->tag = NIL; return l; } list* cons( element e, list* l) {
cons
list* x = new list; x->tag = CONS; x->e = e; x->next = l; return x; }

slide: Data abstraction and modules


Modules -- observers

ADT



  int empty(list* lst) { return !lst || lst->tag == NIL; }
  
  element head(list* l) {  
head
require( ! empty(l) ); return l->e; } list* tail(list* l) {
tail
require( ! empty(l) ); return l->next; } bool equal(list* l, list* m) {
equal
switch( l->tag) { case NIL: return empty(m); case CONS: return !empty(m) && head(l) == head(m) && tail(l) == tail(m); } }

slide: Modules -- observers


Method interface -- list

OOP



  template< class E >
  class nil : public list< E > { 
nil
public: nil() {} bool empty() { return 1; } E head() { require( false ); return E(); } list< E >* tail() { require( 0 ); return 0; } bool operator==(list* m) { return m->empty(); } }; template< class E > class cons : public list< E > {
cons
public: cons(E e, list* l) : _e(e), next(l) {} ~cons() { delete next; } bool empty() { return 0; } E head() { return _e; } list* tail() { return next; } bool operator==(list* m); protected: E _e; list* next; };

slide: Data abstraction and objects


Adding new generators -- representation

ADT



  typedef int element;
  
  enum { NIL, CONS, INTERVAL };
  
  struct list {
  int tag;
  element e; 
  union { element z; list* next; };
  };
  

Generator


  list* interval( element x, element y ) {
  	list* l = new list;
  	if ( x <= y ) {
  		l->tag = INTERVAL;
  		l->e = x; l->z = y;
  		}
  	else l->tag = NIL;
  	return l;
  	}
  

slide: Modules and generators


Modifying the observers

ADT



  element head(list* l) {  
head
require( ! empty(l) ); return l->e; // for both CONS and INTERVAL } list* tail(list* l) {
tail
require( ! empty(l) ); switch( l->tag ) { case CONS: return l->next; case INTERVAL: return interval((l->e)+1,l->z); } }

slide: Modifying the observers


Adding new generators

OOP



  class interval : public list<int> { 
interval
public: interval(int x, int y) : _x(x), _y(y) { require( x <= y ); } bool empty() { return 0; } int head() { return _x; } list< int >* tail() { return (_x+1 <= _y)? new interval(_x+1,_y): new nil<int>; } bool operator==(list@lt;int>* m) { return !m->empty() && _x == m->head() && tail() == m->tail(); } protected: int _x; int _y; };

slide: Objects and generators


Adding new observers

ADT



  int length( list* l ) { 
length
switch( l->tag ) { case NIL: return 0; case CONS: return 1 + length(l->next); case INTERVAL: return l->z - l->e + 1; }; }

slide: Modules and observers


Adding new observers

OOP



  template< class E >  
  int length(list< E >* l) { 
length
return l->empty() ? 0 : 1 + length( l->tail() ); } template< class E > class listWL : public list<E> {
listWL
public: int length() { return ::length( this ); } };

slide: Objects and observers


  list<int>* r = new cons<int>(1,new cons<int>(2,new interval(3,7))); 
  while (! r->empty()) { 
  	cout << ((listWL< int >*)r)->length() << endl;
  	r = r->tail();
  	}
  delete r;