next up previous contents
Next: Language Design and Implementation Up: CS2111: Design and Implementation Previous: Vectors and Arrays -   Contents


Abstract Data-Types, Modules, Classes and Objects

If we want to group together several related declarations, ideally we would use one of the following three forms of abstraction:
Abstract Data Type (ADT)
Used mainly in functional languages
User-defined type(s)
User-defined operations
Used in imperative languages
Used in all object-oriented languages (an object is an instance of a class)
Dynamic binding (c.f. $\S $19.5)
Polymorphism (c.f. $\S $12.3)
The earliest, and thus least standardised, form is the module. Few languages directly provide ADTs, modules or classes (although most recent languages do) but most recognise the importance of the concept and provide facilities that can be used to approximate it.

Abstract Data Types (ADTs)

An abstract data type is a named data type defined solely through operations for creating and manipulating values of that data type. If values are available directly, they are known by name only. Any internal structure is known, and so can be manipulated, only inside the ADT.

The associated scope rules define this distinction between public (exported) identifiers, that can be seen both inside and outside the ADT, and private (local) identifiers, that can only be seen inside the ADT. Therefore, unlike a classical block structured language, scopes are no longer strictly nested (c.f. $\S $14). This is known as encapsulation.

Example of using ADTs in SML ($CS2111/e*/stack/*):

type intlist = int list
abstype STACK = Stack of intlist
  exception stack_is_empty
  val stack = Stack []
  fun push (Stack stk, number) = Stack (number :: stk)
  fun pop (Stack []) = raise stack_is_empty
     |  pop (Stack (x::stk)) = Stack stk
  fun top (Stack []) = raise stack_is_empty
     |  top (Stack (x::stk)) = x
  fun empty (Stack []) = true
     |  empty (Stack stk) = false

val stk = stack
val stk = push (stk, 42)
val stk = push (stk, 17)
val stk = pop (stk)
val top_one = top (stk)
Here Stack is private, and stack_is_empty, stack, push, pop, top, and empty are public. The local keyword can be used to make identifiers private.

Modules e.g. ADA

Example of not using Modules in Ada:

 procedure RANDOM(RR: FLOAT out) is
                A: constant FLOAT := LAST_RANDOM*125.0;
                LAST _RANDOM := A_TRUNC(A);
                RR := LAST_RANDOM;
Users of RANDOM should not be allowed to get at the variable LAST_RANDOM. This can be prevented by wrapping these declarations up in a module (package) from which LAST_RANDOM will not be exported. Note that the declaration of the package is separate from its implementation (body). This is a feature found in many, but not all, languages providing ADTs, modules or classes.

Example of using Modules in Ada:

 package RANDOM_PACKAGE is
        procedure RANDOM(RR: FLOAT out);
        -- only identifiers declared here will be exported

 package body RANDOM_PACKAGE is
        -- insert LAST_RANDOM and RANDOM as above

        use RANDOM_PACKAGE;
        -- here we can see RANDOM but not LAST_RANDOM
The scope of RANDOM is the inside of the package body plus the inside of the block where RANDOM_PACKAGE is used. The scope of LAST_RANDOM, however, is the inside of the package body only.

Classes: Object-Oriented Programming Languages (OOPLs)

Inheritance: when we create a new class, we can automatically reuse some or all of the definitions of similar objects, leading to hierarchies of objects. Some languages allow multiple inheritance, where a new object can reuse the definitions of several other objects.

Binding: inheritance and polymorphism make it harder to decide the exact type of every object and thus which version of an overloaded operation to use. (Does the object belong to the class where the operation was defined, or did it inherit it, or could it have inherited it but is in a class where the operation was redefined?) Therefore, whereas in many programming languages we can decide this at compile time (static or eager binding), in many but not all OO languages we can only decide this at run time (dynamic or lazy binding)


In C++, a class is essentially an elaboration of a C typedef struct that can also contain function definitions. C++ uses new and delete, rather than malloc and free, to create heap instances of classes, and can have static and auto instances, just like C variables.

A C++ class can have private and public components, with the standard meaning. It can also include special constructor and destructor functions, which are automatically used to create and destroy instances of the class, usually because entities of the class need initialising - they can also be used to new and delete dynamic entities within the class. A constructor function has the same name as the class, a destructor function has the same name preceded by a ~. Overloaded functions can be created using the virtual keyword.

There are various facilities to help create related classes and sub-classes, including protected entities and friend classes. A hierarchy of classes is simply created by using entities of one class type inside another.

Example of using Objects/Classes in C++:

#include <iostream.h>
class stack {
  int *stack_ptr, max_len, top_ptr;
  stack (int size)
        { stack_ptr= new int [size];
          max_len= size - 1;
          top_ptr= -1;
 ~stack (void)
        {delete stack_ptr;};
 void push (int number)
        { if (top_ptr == max_len)
            cout << "Error in push: stack is full\n";
          else stack_ptr[++top_ptr]= number;
 void pop (void)
        { if (top_ptr == -1)
            cout << "Error in pop: stack is empty\n";
          else top_ptr--;
 int top (void)
        { if (top_ptr == -1)
            cout << "Error in top: stack is empty\n";
          else return (stack_ptr[top_ptr]);
 int empty (void)
        {return (top_ptr == -1);}

int main (void)
  int top_one;
  stack stk (100);

  stk.push (42);
  stk.push (17);
  stk.pop ();
  top_one= ();
  return 0;


Louden: chs. 8, 9
Bal & Grune: chs. 2.2.2, 2.5, 2.5.3-2.5.5
van der Linden: ch. 11
next up previous contents
Next: Language Design and Implementation Up: CS2111: Design and Implementation Previous: Vectors and Arrays -   Contents
Pete Jinks