Representation and implementation

intro, types, algebra, modules, classes, summary, Q/A, literature

The realization of abstract data types as modules with functions requires additional means to hide the representation of the list type. In contrast, with an object-oriented approach, data hiding is effected by employing the encapsulation facilities of classes.

Modules -- representation hiding

Modules provide a syntactic means to group related pieces of code and to hide particular aspects of that code. In slide 8-modules an example is given of the representation and the generator functions for a list of integers.

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

For implementing the list as a collection of functions (ADT style), we employ a struct with an explicit tag field, indicating whether the list corresponds to nil or a cons. The functions corresponding with the generators create a new structure and initialize the tag field. In addition, the cons operator sets the element and next field of the structure to the arguments of cons. The implementation of the observers is given in slide 8-mod-impl.

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

To determine whether the list is empty it suffices to check whether the tag of the list is equal to NIL. For both head and tail the pre-condition is that the list given as an argument is not empty. If the pre-condition holds, the appropriate field of the list structure is returned. The equality operator, finally, performs an explicit switch on the tag field, stating for each case under what conditions the lists are equal. Below, a program fragment is given that illustrates the use of the list.

  list* r = cons(1,cons(2,nil()));
  while (!empty(r)) { 
  	cout << head(r) << endl;
  	r = tail(r);
  	}

Note that both the generator functions nil and cons take care of creating a new list structure. Writing a function to destroy a list is left as an exercise for the reader.

Objects -- method interface

The idea underlying an object-oriented decomposition of the specification matrix of an abstract type is to make a distinction between the (syntactic) subtypes of the data type (corresponding with its generators) and to specify for each subtype the value of all possible observer functions. (We speak of syntactic subtypes, following [Dahl92], since these subtypes correspond to the generators defining the value domain of the data type. See [Dahl92] for a more extensive treatment.)

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<E>* m) { return m->empty(); }
  };
  
  template< class E >
  class cons : public list< E > {   cons  
  public:
  cons(E e, list<E>* l) : _e(e), next(l) {}
  ~cons() { delete next; }
  bool empty() { return 0; }
  E head() { return _e; }
  list<E>* tail() { return next; }
  bool operator==(list<E>* m);
  protected:
  E _e;
  list<E>* next;
  };

slide: Data abstraction and objects

In the object realization in slide 8-objects, each subtype element is defined as a class inheriting from the list class. For both generator types nil and cons the observer functions are defined in a straightforward way. Note that, in contrast to the ADT realization, the distinction between the various cases is implicit in the member function definitions of the generator classes. As an example of using the list classes consider the program fragment below.

  list<int>* r = new cons<int>(1, new cons<int>(2, new nil<int>)); 
  while (! r->empty()) { 
  	cout << r->head() << endl;
  	r = r->tail();
  	}
  delete r;

For deleting a list we may employ the (virtual) destructor of list, which recursively destroys the tail of a list.