Data Abstraction in Oberon

Karl Landström 2018-01-16 (edited 2018-01-27)

In this article we will look at the constructs that Oberon provides for data and procedural abstraction. More specifically we will implement a simple stack as a concrete data structure, an abstract data structure, an abstract data type and a class.

1. A Concrete Data Structure

The simplest and most straight-forward way to implement a stack of integers is to use a concrete data structure, for instance an array of sufficient size. We also need an integer variable to keep track of the number of elements in the stack:

stack: ARRAY 100 OF INTEGER
count: INTEGER

Before the stack is used we initialize count to zero. Every time we want to insert an element x into the stack we do

stack[count] := x;
INC(count)

When we want to remove and retrieve the top element from the stack we do

DEC(count);
x := stack[count]

The stack is cleared by simply setting count to zero. The insert operation is called push and the remove operation is called pop.

2. An Abstract Data Structure

Instead of manipulating the stack array and the count variable directly, it is more convenient to define Push and Pop as procedures. This also enables us to change the representation of the stack at a later stage without having to change every push and pop operation throughout the module. If we want to use a linked list instead of an array, say, we only need to reimplement the procedures Push and Pop.

Another observation is that the parts of the program which uses the stack don't need to know how the stack is implemented. We also want to make sure that Push, Pop and Clear are the only operations that can be performed on our stack. This is solved by defining the stack in a separate module which exports only the interface of the stack:

MODULE Stack;

	VAR
		items: ARRAY 100 OF INTEGER;
		count*: INTEGER; (**number of elements in the stack*)

	PROCEDURE Push*(x: INTEGER);
(**inserts x on the top of the stack*)
	BEGIN
		items[count] := x;
		INC(count)
	END Push;

	PROCEDURE Pop*(VAR x: INTEGER);
(**removes the top element from the stack and returns it in x*)
	BEGIN
		ASSERT(count > 0);
		DEC(count);
		x := items[count]
	END Pop;

	PROCEDURE Clear*;
(**empties the stack*)
	BEGIN
		count := 0
	END Clear;

BEGIN
	Clear
END Stack.

All exported identifiers (and comments) are marked with an asterisk. Exported variables in Oberon are read-only in client modules, so the variable count can not be modified outside of module Stack. Pop is implemented as a proper procedure rather than a function procedure because it changes the state of the stack; a function procedure should have no side effects.

With the OBNC compiler, the module interface can be extracted with the command obncdoc:

DEFINITION Stack;

	VAR
		count: INTEGER; (*number of elements in the stack*)

	PROCEDURE Push(x: INTEGER);
(*inserts x on the top of the stack*)

	PROCEDURE Pop(VAR x: INTEGER);
(*removes the top element from the stack and returns it in x*)

	PROCEDURE Clear;
(*empties the stack*)

END Stack.

The unit test module StackTest below shows how the stack is used. When StackTest is run it should terminate successfully with no output.

MODULE StackTest;
	
	IMPORT Stack;
	
	VAR
		x: INTEGER;

BEGIN
	ASSERT(Stack.count = 0);
	Stack.Push(1);
	Stack.Push(2);
	Stack.Push(3);
	ASSERT(Stack.count = 3);
	Stack.Pop(x);
	ASSERT(x = 3);
	Stack.Pop(x);
	ASSERT(x = 2);
	Stack.Pop(x);
	ASSERT(x = 1);
	ASSERT(Stack.count = 0);
	Stack.Push(1);
	Stack.Clear;
	ASSERT(Stack.count = 0)
END StackTest.

3. An Abstract Data Type

An obvious limitation of the abstract data structure is that it only allows for one single global stack. If more than one stack is needed we can instead implement an abstract data type:

MODULE Stacks;

	TYPE
		Stack* = RECORD
			items: ARRAY 100 OF INTEGER;
			count: INTEGER
		END;

	PROCEDURE Init*(VAR s: Stack);
	BEGIN
		s.count := 0
	END Init;

	PROCEDURE Push*(x: INTEGER; VAR s: Stack);
	BEGIN
		s.items[s.count] := x;
		INC(s.count)
	END Push;

	PROCEDURE Pop*(VAR s: Stack; VAR x: INTEGER);
	BEGIN
		ASSERT(s.count > 0);
		DEC(s.count);
		x := s.items[s.count]
	END Pop;

	PROCEDURE Count*(s: Stack): INTEGER;
	RETURN s.count
	END Count;

END Stacks.

Since Stack is now the name of a data type, we use the plural form Stacks for the module. Procedure parameters are declared in input-modify-output order. Note that we don't export the field count from the record type Stack since it would allow a client to change it directly. Instead it is retrieved through the procedure Count. A Clear procedure is not needed since Init clears the stack.

Here is the corresponding unit test for module Stacks:

MODULE StacksTest;

	IMPORT Stacks;

	VAR
		s: Stacks.Stack;
		x: INTEGER;

BEGIN
	Stacks.Init(s);
	ASSERT(Stacks.Count(s) = 0);
	Stacks.Push(1, s);
	Stacks.Push(2, s);
	Stacks.Push(3, s);
	ASSERT(Stacks.Count(s) = 3);
	Stacks.Pop(s, x);
	ASSERT(x = 3);
	Stacks.Pop(s, x);
	ASSERT(x = 2);
	Stacks.Pop(s, x);
	ASSERT(x = 1);
	ASSERT(Stacks.Count(s) = 0);
	Stacks.Push(1, s);
	Stacks.Init(s);
	ASSERT(Stacks.Count(s) = 0)
END StacksTest.

4. A Touch of Class

In Oberon there is no class construct. Instead, object oriented programming is realized by means of extensible records, procedure fields and type tests. There are essentially three different approaches. For each approach described below we build an object oriented interface on top of the previously defined abstract data type Stacks.Stack. This avoids code repetition and also highlights the fact that object oriented programming is essentially about packaging data and procedures.

4.1 Object-bound Procedures

With object-bound procedures we add a procedure field for each method that our class is to support:

MODULE OPStacks;

	IMPORT Stacks;

	TYPE
		Stack* = RECORD (Stacks.Stack)
			push*: PROCEDURE (x: INTEGER; VAR s: Stacks.Stack);
			pop*: PROCEDURE (VAR s: Stacks.Stack; VAR x: INTEGER);
			count*: PROCEDURE (s: Stacks.Stack): INTEGER
		END;

	PROCEDURE Init*(VAR s: Stack);
	BEGIN
		Stacks.Init(s);
		s.push := Stacks.Push;
		s.pop := Stacks.Pop;
		s.count := Stacks.Count
	END Init;

END OPStacks.

In the module OPStacks the record Stack extends the record Stacks.Stack. However, if we were to implement OPStacks from scratch we would instead add the procedure fields alongside the fields items and count and include the procedures from the module Stacks.

The unit test OPStacksTest shows how a class with object-bound procedures is used:

MODULE OPStacksTest;

	IMPORT Stacks := OPStacks;

	VAR
		s: Stacks.Stack;
		x: INTEGER;

BEGIN
	Stacks.Init(s);
	ASSERT(s.count(s) = 0);
	s.push(1, s);
	s.push(2, s);
	s.push(3, s);
	ASSERT(s.count(s) = 3);
	s.pop(s, x);
	ASSERT(x = 3);
	s.pop(s, x);
	ASSERT(x = 2);
	s.pop(s, x);
	ASSERT(x = 1);
	ASSERT(s.count(s) = 0);
	s.push(1, s);
	Stacks.Init(s);
	ASSERT(s.count(s) = 0)
END OPStacksTest.

Unlike traditional object-oriented programming languages, each method needs to receive its object as an explicit parameter. On the other hand, with this transparency it is easier to understand how method calls really work.

4.2 Type-bound Procedures

If there is a large number of objects of the same class and the class has many methods, storing all methods in each object may seem like a waste of memory. The alternative approach is to store only a single pointer to a separate record which contains the methods. Then all instances of the class will refer to the same method record. This is how classes are typically implemented in traditional object oriented languages.

MODULE TPStacks;

	IMPORT Stacks;

	TYPE
		Stack* = RECORD (Stacks.Stack)
			do*: POINTER TO Methods
		END;

		Methods* = RECORD
			push*: PROCEDURE (x: INTEGER; VAR s: Stacks.Stack);
			pop*: PROCEDURE (VAR s: Stacks.Stack; VAR x: INTEGER);
			count*: PROCEDURE (s: Stacks.Stack): INTEGER		
		END;

	VAR
		methods: POINTER TO Methods;

	PROCEDURE Init*(VAR s: Stack);
	BEGIN
		Stacks.Init(s);
		s.do := methods
	END Init;

BEGIN
	NEW(methods);
	methods.push := Stacks.Push;
	methods.pop := Stacks.Pop;
	methods.count := Stacks.Count	
END TPStacks.

In use the type-bound procedures are quite similar to object-bound procedures:

MODULE TPStacksTest;

	IMPORT Stacks := TPStacks;

	VAR
		s: Stacks.Stack;
		x: INTEGER;

BEGIN
	Stacks.Init(s);
	ASSERT(s.do.count(s) = 0);
	s.do.push(1, s);
	s.do.push(2, s);
	s.do.push(3, s);
	ASSERT(s.do.count(s) = 3);
	s.do.pop(s, x);
	ASSERT(x = 3);
	s.do.pop(s, x);
	ASSERT(x = 2);
	s.do.pop(s, x);
	ASSERT(x = 1);
	ASSERT(s.do.count(s) = 0);
	s.do.push(1, s);
	Stacks.Init(s);
	ASSERT(s.do.count(s) = 0)
END TPStacksTest.

4.3 Message Records

A different approach to object orientation is to use message records. With message records each message is an extension of the common base type Message and is passed to a central message handler:

MODULE MRStacks;

	IMPORT Stacks;

	TYPE
		Message* = RECORD END;
		PushMsg* = RECORD (Message) x*: INTEGER END;
		PopMsg* = RECORD (Message) x*: INTEGER END;
		CountMsg* = RECORD (Message) n*: INTEGER END;

		Stack* = RECORD (Stacks.Stack)
			handle*: PROCEDURE (VAR s: Stack; VAR msg: Message)
		END;

	PROCEDURE Handle(VAR s: Stack; VAR msg: Message);
	BEGIN
		CASE msg OF
			  PushMsg: Stacks.Push(msg.x, s)
			| PopMsg: Stacks.Pop(s, msg.x)
			| CountMsg: msg.n := Stacks.Count(s)
			| Message: (*unhandled message*)
		END
	END Handle;

	PROCEDURE Init*(VAR s: Stack);
	BEGIN
		Stacks.Init(s);
		s.handle := Handle
	END Init;

END MRStacks.

Using message records is more verbose than the alternatives since each message needs a variable declaration and each message (with input parameters) also needs to be setup before the message is sent to the object.

MODULE MRStacksTest;

	IMPORT Stacks := MRStacks;

	VAR
		s: Stacks.Stack;
		countMsg: Stacks.CountMsg;
		pushMsg: Stacks.PushMsg;
		popMsg: Stacks.PopMsg;

BEGIN
	Stacks.Init(s);
	s.handle(s, countMsg);
	ASSERT(countMsg.n = 0);
	pushMsg.x := 1;
	s.handle(s, pushMsg);
	pushMsg.x := 2;
	s.handle(s, pushMsg);
	pushMsg.x := 3;
	s.handle(s, pushMsg);
	s.handle(s, countMsg);
	ASSERT(countMsg.n = 3);
	s.handle(s, popMsg);
	ASSERT(popMsg.x = 3);
	s.handle(s, popMsg);
	ASSERT(popMsg.x = 2);
	s.handle(s, popMsg);
	ASSERT(popMsg.x = 1);
	s.handle(s, countMsg);
	ASSERT(countMsg.n = 0);
	pushMsg.x := 1;
	s.handle(s, pushMsg);
	Stacks.Init(s);
	s.handle(s, countMsg);
	ASSERT(countMsg.n = 0)
END MRStacksTest.

The advantage of message records is that a message can be broadcast over a collection of objects even when not all of the objects recognize it. The typical example is that of a graphics editor which can be extended with new shapes and operations. If we add a shape which supports a fill operation, a fill message can be sent to all drawn objects and only the objects which handles it are filled. With object-bound (or type-bound) procedures we would have to add the fill method to the core editor.