ECOOP '99 Workshop

Introducing OO Design and Programming - with Special Emphasis on Concrete Examples



Object-Oriented Programming at the Johannes Kepler University Linz

Christoph Steindl
Hanspeter Mössenböck

Practical Computer Science
Johannes Kepler University, Linz

steindl@ssw.uni-linz.ac.at
moessenboeck@ssw.uni-linz.ac.at


Title of the course:

Object-Oriented Programming

Target audience:

Students of Computer Science at the Johannes Kepler University Linz. This is a compulsory lecture with accompanying excercises in the second year of the curriculum.

Preliminary knowledge:

Introductory course in an imperative language (Oberon-2) and a programming practical. Topics:


Algorithms and Data Structures I. Topics: Learning time: Methods, tools, resources, environments: General description of the course:

At the university of Linz, we teach object-oriented programming to students in the 3rd semester. They have already attended a course on introductory programming in an imperative language (Oberon-2) and a programming practical in the same language. The purpose of our OOP course is to show them how to use OOP for structuring their programs for making them extensible.

We believe that OOP is "programming in the large" and should be preceded by courses on "programming in the small". OOP is a "packaging" technique that helps one to deliver the services of a program in small packages (i.e.classes) with a well-defined interface. Before one can build a package, however, one has know how to build its contents. This is a non-trivial task, and it doesn't have much to do with OOP.

Programming in the small (i.e. building the package contents) has to teach the following concepts:

Programming in the large (i.e. OOP) adds to this mainly the following concepts: From this comparison we conclude that it is not a good idea to teach OOP to programming novices. They would have to learn both the concepts of OOP and the more fundamental programming concepts at the same time. The result is confusion. We don't deny that it is possible to start programming in an OO language (e.g. in Smalltalk), but we don't think that it is good from a paedagocical point of view. Good examples for data abstraction and extensibility cannot be taught with toy examples. In order to convince the students of the power of OOP we need to present large and realistic case studies. This is only possible after the students already know a little bit about programming.

Our OOP course has a special emphasis on design patterns. Patterns are an ideal vehicle for teaching. Starting from a convincing example, we can extract the reusable concept behind it. Students will remember the example and therefore also the concept behind it. By collecting several such examples the students acquire expert experience, which would otherwise take years to learn.

Our course is oriented on concepts and not on a particular programming language. All the concepts such as data abstraction, inheritance, dynamic binding, UML modeling, frameworks, design patterns can be taught in a general form (mostly with a graphical notation). Currently we us Oberon-2 as a programming language because the students already were exposed to it in the previous semesters. In the future we plan to switch to Java because the introductory programming courses will also use Java.

Topics of the course:

  1. Introduction
    Basic idea of OOP, object-oriented thinking, information hiding, data abstraction, inheritance, dynamic binding, terminology, history

  2. Classes
    Attributes, methods, messages, objects and references, classes and modules, examples

  3. Inheritance
    Notation, overriding of inherited methods, class hierarchies, type compatibility, assignment among objects, type test, type guard, multiple inheritance

  4. Dynamic Binding
    Interpretation of messages, static and dynamic binding, abstract classes

  5. Contracts
    Preconditions, postconditions, class invariants, sub-contracts, covariance, contravariance

  6. Typical Applications
    Data abstraction, heterogeneous data structures, generic building blocks, exchangeable behaviour, extension and adaptation of building blocks

  7. Object-oriented Design
    Difference to procedure-oriented design, How-to-proceed, method of Abbott, CRC cards, relationships between classes, frequent design errors, tips

  8. UML Notation
    Object model: classes, attributes, operations, relationships, aggregation, inheritance
    Dynamic model: event diagram, state diagram, activity diagram
    Functional model: data flow diagram, use cases

  9. Class Libraries
    Typical categories of classes, examples: Smalltalk, ET++
    Tools for class libraries

  10. Frameworks
    Definition, possibilities of implementation, Examples: menues, Do/Undo, Dragging, MVC, text elements;
    Application Frameworks, MacApp

  11. Design Patterns
    Definition, Constructor, Abstract Factory, Builder, Factory Method, Prototype, Adapter, Composite, Decorator, Proxy, Facade, Twin, Message Object, Copy, Input/Output, Chain of Responsibility, Iterator, Observer, Strategy, Template Method

  12. Components
    Definition. JavaBeans, ActiveX Controls.

  13. Smalltalk
    Specialties, classes, expressions, blocks, inheritance, meta-classes, class library

  14. C++
    Classes, members, independent compilation, inheritance, visibility of names, dynamic binding, templates

  15. Implementation of Object-Oriented Languages
    Type descriptors, method call, type-test, multiple inheritance, Smalltalk
Materials:

H.Mössenböck: Objekt-oriented Programming in Oberon-2, third edition, Springer-Verlag, 1998.

Further courses after this one:

Software Engineering Courses

A concrete exercise specification:

The following example is worth 15 points of 120 points that may be reached with exercises.

Object-oriented File System

Task 1 (9 Points): Implement an object-oriented file system.

The base class Object is abstract with the following interface:

  TYPE
    Object = POINTER TO ObjectDesc;
    ObjectDesc = RECORD
      PROCEDURE (o: Object) GetName (VAR name: ARRAY OF CHAR);
      PROCEDURE (o: Object) SetName (name: ARRAY OF CHAR);
      PROCEDURE (o: Object) Print (indent: INTEGER);
      ...
    END ;
Method Print can be used in concrete classes to output the object textually. When the parameter indent is less than zero, the output is generated flat, otherwise the output starts with indent tabulators at the beginning of the line. Each object is output in one line (with a terminating new line at the end).
The classes Directory, Device, File, and Link are derived from class Object.
  TYPE
    File = POINTER TO FileDesc;
    FileDesc = RECORD (Objects.ObjectDesc)
      PROCEDURE (f: File) Length (): LONGINT;
      PROCEDURE (f: File) SetLength (len: LONGINT);
      PROCEDURE (f: File) Print (indent: INTEGER);
      ...
    END ;

    Link = POINTER TO LinkDesc;
    LinkDesc = RECORD (Objects.ObjectDesc)
      PROCEDURE (l: Link) Target (): Objects.Object;
      PROCEDURE (l: Link) SetTarget (o: Objects.Object);
      PROCEDURE (l: Link) Print (indent: INTEGER);
      ...
    END ;

    Device = POINTER TO DeviceDesc;
    DeviceDesc = RECORD (Objects.ObjectDesc)
      PROCEDURE (d: Device) Print (indent: INTEGER);
      ...
    END ;

    Directory = POINTER TO DirectoryDesc;
    DirectoryDesc = RECORD (Objects.ObjectDesc)
      PROCEDURE (d: Directory) Insert (obj: Objects.Object);
      PROCEDURE (d: Directory) Remove (obj: Objects.Object);
      PROCEDURE (d: Directory) NumOfElems (): LONGINT;
      PROCEDURE (d: Directory) Print (indent: INTEGER);
      PROCEDURE (d: Directory) NewIterator (): Iterator;
      ...
    END ;

    Iterator = POINTER TO IteratorDesc;
    IteratorDesc = RECORD
      PROCEDURE (it: Iterator) Current (): Objects.Object;
      PROCEDURE (it: Iterator) Advance;
      PROCEDURE (it: Iterator) Reset;
    END ;

A Directory can contain arbitrarily many other objects that can be inserted into the directory with Insert and removed from the directory with Remove. NumOfElems gives the number of objects in the directory. Print outputs the directory. An object of type Device reprents a device driver, an object of type File a file whose length can be queried with function Length. An object of type Link represents a link to another object (a physical file can thus be referenced from two directories). Each class can have additional attributes and methods if necessary.
An Iterator can be used to iterate over all entries of a directory. NewIterator allocates a new iterator. Current returns the current object (or NIL). Advance advances the iterator to the next entry, Reset resets the iterator the the first entry.
Implement the classes Directory and Iterator in the same module, the other classes in separate modules. For each concrete class, a command New shall allocate a new object (possible ask the user for necessary parameters) and make it available in the global variable Objects.new. For each class a procedure for the initialization must be available, as well as a procedure for the allocation of initialized objects for all concrete classes, e.g.
  PROCEDURE InitSomething* (s: Something);
  BEGIN
    Base.InitBase(s);
    initialize new fields
  END InitSomething;

  PROCEDURE NewSomething* (): Something;
    VAR s: Something;
  BEGIN NEW(s); InitSomething(s); RETURN s
  END NewSomething;

Create a structure of directories with multiple sub-directories interactively (e.g. via commands).
Output the result hierarchically (where the contents of directories is indented in level higher then the
directory itself) and flatly.
Provide commands to search for all objects with a specific name (matching a pattern) and to delete all objects matching a specific pattern.

Task 2 (3 Points): Static View of the Class Hierarchy with UML

Represent the static view of the class hierarchy with UML. Distinguish between generalization, aggregation and assoziation.

Task 3 (3 Points): Event Diagram

Draw an event diagram for the hierarchical output of a directory tree. Specify the names of methods and the result types of functions (if applicable).

The complete solution
MODULE Objects;

TYPE
  Object* = POINTER TO ObjectDesc;
  ObjectDesc* = RECORD
    name: ARRAY 32 OF CHAR
  END ;

VAR
  new*: Object;

PROCEDURE InitObject* (o: Object);
BEGIN o.name := ""
END InitObject;

PROCEDURE (o: Object) GetName* (VAR name: ARRAY OF CHAR);
BEGIN COPY(o.name, name)
END GetName;

PROCEDURE (o: Object) SetName* (name: ARRAY OF CHAR);
BEGIN COPY(name, o.name)
END SetName;

PROCEDURE (o: Object) Print* (indent: INTEGER);
BEGIN HALT(99)
END Print;

END Objects.

MODULE OOFiles;

IMPORT Objects, In, Out;

TYPE
  File* = POINTER TO FileDesc;
  FileDesc* = RECORD (Objects.ObjectDesc)
    len: LONGINT
  END ;

PROCEDURE InitFile* (f: File);
BEGIN Objects.InitObject(f); f.len := 0
END InitFile;

PROCEDURE NewFile* (): File;
  VAR f: File;
BEGIN NEW(f); InitFile(f); RETURN f
END NewFile;

PROCEDURE (f: File) Length*(): LONGINT;
BEGIN RETURN f.len
END Length;

PROCEDURE (f: File) SetLength*(len: LONGINT);
BEGIN f.len := len
END SetLength;

PROCEDURE (f: File) Print* (indent: INTEGER);
  VAR i: INTEGER; name: ARRAY 32 OF CHAR;
BEGIN
  FOR i := 1 TO indent DO Out.Char(9X) END ;
  Out.String("File "); f.GetName(name); Out.String(name); Out.String(", length: "); Out.Int(f.len, 0); Out.Ln
END Print;

PROCEDURE New*;  (* name len *)
  VAR f: File; s: ARRAY 32 OF CHAR;
BEGIN
  In.Open; In.Name(s);
  IF ~In.Done THEN In.Open; In.String(s) END ;
  IF In.Done THEN
    f := NewFile(); f.SetName(s); In.LongInt(f.len);
    Objects.new := f
  END
END New;

END OOFiles.

MODULE OOLinks;

IMPORT Objects, In, Out;

TYPE
  Link* = POINTER TO LinkDesc;
  LinkDesc* = RECORD (Objects.ObjectDesc)
    other: Objects.Object
  END ;

PROCEDURE InitLink* (l: Link);
BEGIN Objects.InitObject(l)
END InitLink;

PROCEDURE NewLink* (): Link;
  VAR l: Link;
BEGIN NEW(l); InitLink(l); RETURN l
END NewLink;

PROCEDURE (l: Link) Print* (indent: INTEGER);
  VAR i: INTEGER;
BEGIN
  FOR i := 1 TO indent DO Out.Char(9X) END ;
  Out.String("Link to "); l.other.Print(indent)
END Print;

PROCEDURE (l: Link) SetTarget* (o: Objects.Object);
BEGIN l.other := o
END SetTarget;

PROCEDURE (l: Link) Target* (): Objects.Object;
BEGIN RETURN l.other
END Target;

PROCEDURE New*;  (* name Objects.new *)
  VAR l: Link; s: ARRAY 32 OF CHAR;
BEGIN
  In.Open; In.Name(s);
  IF ~In.Done THEN In.Open; In.String(s) END ;
  IF In.Done THEN
    l := NewLink(); l.SetName(s); l.SetTarget(Objects.new);
    Objects.new := l
  END
END New;

END OOLinks.

MODULE OODevices;

IMPORT Objects, In, Out;

TYPE
  Device* = POINTER TO DeviceDesc;
  DeviceDesc* = RECORD (Objects.ObjectDesc)
  END ;

PROCEDURE InitDevice* (d: Device);
BEGIN Objects.InitObject(d)
END InitDevice;

PROCEDURE NewDevice* (): Device;
  VAR d: Device;
BEGIN NEW(d); InitDevice(d); RETURN d
END NewDevice;

PROCEDURE (d: Device) Print* (indent: INTEGER);
  VAR i: INTEGER; name: ARRAY 32 OF CHAR;
BEGIN
  FOR i := 1 TO indent DO Out.Char(9X) END ;
  Out.String("Device "); d.GetName(name); Out.String(name); Out.Ln
END Print;

PROCEDURE New*;  (* name *)
  VAR d: Device; s: ARRAY 32 OF CHAR;
BEGIN
  In.Open; In.Name(s);
  IF ~In.Done THEN In.Open; In.String(s) END ;
  IF In.Done THEN
    d := NewDevice(); d.SetName(s);
    Objects.new := d
  END
END New;

END OODevices.

MODULE OODirectories;

IMPORT Objects, In, Out;

TYPE
  Node = POINTER TO NodeDesc;
  NodeDesc = RECORD
    obj: Objects.Object;
    prev, next: Node;
  END ;

  Directory* = POINTER TO DirectoryDesc;
  DirectoryDesc* = RECORD (Objects.ObjectDesc)
    head: Node;
    size: LONGINT
  END ;

  Iterator* = POINTER TO IteratorDesc;
  IteratorDesc* = RECORD
    head, n: Node
  END ;

PROCEDURE RemoveNode (p: Node);
  VAR n: Node;
BEGIN
  n := p.next; p.prev.next := n; n.prev := p.prev
END RemoveNode;

PROCEDURE InitDirectory* (d: Directory);
BEGIN
  Objects.InitObject(d); d.size := 0;
  NEW(d.head); d.head.next := d.head; d.head.prev := d.head
END InitDirectory;

PROCEDURE NewDirectory* (): Directory;
  VAR d: Directory;
BEGIN NEW(d); InitDirectory(d); RETURN d
END NewDirectory;

PROCEDURE InsertBefore (n, before: Node);
BEGIN
  n.prev := before.prev; n.next := before; before.prev.next := n; before.prev := n
END InsertBefore;

PROCEDURE (d: Directory) Insert* (obj: Objects.Object);  (** inserts the object into the directory *)
  VAR n: Node;
BEGIN
  NEW(n); n.obj := obj; InsertBefore(n, d.head); INC(d.size)
END Insert;

PROCEDURE (d: Directory) Remove* (obj: Objects.Object);  (* removes the object from the directory *)
  VAR p: Node;
BEGIN
  p := d.head.next;
  WHILE (p # d.head) & (p.obj # obj) DO p := p.next END ;
  IF p # d.head THEN RemoveNode(p); DEC(d.size) END
END Remove;

PROCEDURE (d: Directory) NumOfElems* (): LONGINT;
BEGIN RETURN d.size
END NumOfElems;

PROCEDURE (d: Directory) NewIterator* (): Iterator;
  VAR it: Iterator;
BEGIN
  NEW(it); it.head := d.head;
  IF d.head = d.head.next THEN it.n := NIL ELSE it.n := d.head.next END ;
  RETURN it
END NewIterator;

PROCEDURE (it: Iterator) Current* (): Objects.Object;
BEGIN
  IF it.n = NIL THEN RETURN NIL ELSE RETURN it.n.obj END
END Current;

PROCEDURE (it: Iterator) Advance*;
BEGIN
  IF it.n.next = it.head THEN it.n := NIL ELSE it.n := it.n.next END
END Advance;

PROCEDURE (it: Iterator) Reset*;
BEGIN
  it.n := it.head.next
END Reset;

PROCEDURE (d: Directory) Print* (indent: INTEGER);  (** prints the objects of the directory *)
  VAR it: Iterator; o: Objects.Object; i: INTEGER; name: ARRAY 32 OF CHAR;
BEGIN
  FOR i := 1 TO indent DO Out.Char(9X) END ;
  Out.String("Directory "); d.GetName(name); Out.String(name); Out.Ln;
  it := d.NewIterator(); o := it.Current();
  WHILE o # NIL DO
    IF indent >= 0 THEN o.Print(indent + 1) ELSE o.Print(indent) END ;
    it.Advance; o := it.Current()
  END
END Print;

PROCEDURE New*;  (* name *)
  VAR d: Directory; s: ARRAY 32 OF CHAR;
BEGIN
  In.Open; In.Name(s);
  IF ~In.Done THEN In.Open; In.String(s) END ;
  IF In.Done THEN
    d := NewDirectory(); d.SetName(s);
    Objects.new := d
  END
END New;

END OODirectories.

MODULE Test;

IMPORT Objects, OODirectories, OOFiles, In, Strings;

VAR
  d: OODirectories.Directory;

PROCEDURE Print*;
BEGIN d.Print(-1)
END Print;

PROCEDURE PrintIndented*;
BEGIN d.Print(0)
END PrintIndented;

PROCEDURE Insert*;
BEGIN d.Insert(Objects.new)
END Insert;

PROCEDURE InsertList*;
  VAR f: OOFiles.File; s: ARRAY 32 OF CHAR; len: LONGINT;
BEGIN
  In.Open;
  REPEAT
    IF In.Next() = In.string THEN In.String(s) ELSE In.Name(s) END ;
    IF In.Done THEN
      f := OOFiles.NewFile(); f.SetName(s);
      In.LongInt(len); f.SetLength(len);
      d.Insert(f)
    END
  UNTIL ~In.Done
END InsertList;

PROCEDURE Search*;
  VAR pat: ARRAY 32 OF CHAR;

  PROCEDURE Search0(d: OODirectories.Directory);
    VAR it: OODirectories.Iterator; o: Objects.Object; name: ARRAY 32 OF CHAR;
  BEGIN
    it := d.NewIterator(); o := it.Current();
    WHILE o # NIL DO
      o.GetName(name);
      IF Strings.Match(name, pat) THEN o.Print(-1) END ;
      IF o IS OODirectories.Directory THEN
        Search0(o(OODirectories.Directory))
      END ;
      it.Advance; o := it.Current()
    END
  END Search0;

BEGIN
  In.Open; In.Name(pat);
  IF ~In.Done THEN In.Open; In.String(pat) END ;
  IF In.Done THEN
    Search0(d)
  END
END Search;

PROCEDURE Remove*;
  VAR pat: ARRAY 32 OF CHAR;

  PROCEDURE Remove0(d: OODirectories.Directory);
    VAR it: OODirectories.Iterator; o: Objects.Object; name: ARRAY 32 OF CHAR;
  BEGIN
    it := d.NewIterator(); o := it.Current();
    WHILE o # NIL DO
      o.GetName(name);
      IF Strings.Match(name, pat) THEN d.Remove(o) END ;
      IF o IS OODirectories.Directory THEN
        Remove0(o(OODirectories.Directory))
      END ;
      it.Advance; o := it.Current()
    END
  END Remove0;

BEGIN
  In.Open; In.Name(pat);
  IF ~In.Done THEN In.Open; In.String(pat) END ;
  IF In.Done THEN
    Remove0(d)
  END
END Remove;


BEGIN
  d := OODirectories.NewDirectory(); d.SetName("root")
END Test.

Static View with UML

Event Diagram