Chapter 1. Introduction

Abstraction is the process by which we factor out some complex subset of "experience" and give it a name. The name then serves as a surrogate for the complexity of the experience. The name itself, as it is used, becomes a part of the complexity of our experience and thus serves as the basis for further abstractions. This book is about abstraction. Humanity has progressed from a primitive state primarily because of the ability to form and use abstractions and to build ever more complex abstractions "on the backs" of simpler ones. Concepts that we use every day in the business world (corporation, loan, credit, etc.) are very abstract, based on simpler abstractions (association, value, etc.), and yet we normally think of them as quite "concrete."

Not only is abstraction useful to us, it is absolutely necessary. Psychologists have determined that the human mind (of most of us, at least) is limited by what I will call the "Rule of Seven"(Miller,G.A., The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 1956, v63, pp. 81-96). According to this rule, we are capable of simultaneously manipulating about seven independent items in our minds. For example, we may drive an automobile, listen to music, talk to the person next to us, and keep generally aware of what our friends are up to in the back seat, all simultaneously. A person learning to drive a car, however, has a much harder time integrating the various tasks needed to manipulate the controls, thinking of each of them as distinct. Each of us will eventually reach a point where we cannot add more tasks without reaching overload. Experiments suggest that overload is reached by most people when the number of independent tasks is about seven. A simple demonstration of this is that it is easier to remember telephone numbers (seven digits) than social security numbers (nine digits). Once we reach the point of overload, we need some organizational or abstraction aid to help us deal with the complexity. For example, I remember my own SSN as a sequence of three smaller numbers rather than as one long number. The hyphens normally written in the SSN seem to be a real help in remembering the number. As an experiment of your own, think about how many telephone numbers you mentally carry around, versus how many social security numbers you think you would be able to remember.

The limitation of the Rule of Seven is overcome by our ability to form abstractions. The ability to factor out some complexity (several independent items) and let it be represented by an abstraction or surrogate (a single item) automatically reduces the tendency to overload and lets us use our mental power to the maximum.

More specifically the book is about how a programmer may use object oriented programming techniques to build software which is maximally reusable by applying principles of abstraction. Programmers have wanted to build reusable software components almost from the beginning. The first (and nearly only successful) attempt was the FORTRAN Library, which contained numerical routines such as SIN and LOG, which freed most programmers from the need to program such subroutines in order to use them. The fact that they were widely implemented and fairly true to an abstract model of behavior increased the portability of programs which used them. Portability, the ability to move software easily from one machine to another, is only one of the goals of reusable software however. Another is the ability to reuse components of one project in others. In nearly every field of human action one hears the admonition "Don't reinvent the wheel" whenever attempts are made to advance the state of the art. In programming however it is still too often true that components are rebuilt from scratch for each new use. This contrasts sharply with the general practice in hardware design of using standardized, off the shelf, components to build much of a new hardware system. The same can and should be true of software.

Object oriented programming offers hope of being able to provide a mechanism by which software components may be more easily reused, extended, and especially, interchanged among practitioners. Smalltalk is a small and simple language developed by Xerox in the 70's and 80's. It is always furnished with a large and complex software library called the "class hierarchy." The Smalltalk class hierarchy has proven to provide a mechanism of reusability and extendibility over a number of years on large and small projects . A person programs in Smalltalk by exploiting the power of the class library more than the power of the language itself. There is a negative aspect to Smalltalk however, if one is to build large, multi-person/year software systems. The class library is on line in source form and easily modified. This advantage for prototyping is a disadvantage for large systems where there is more need of stable specifications as a means of communication among the various people building the system.

Modula-3 offers some advantages, especially to the person learning about how to build large, reliable software systems. It is strongly typed, providing early warning of potential errors. It has a definite modularity, permitting separate compilation of modules. It has good information hiding, making it easier to control change. It is also highly object-oriented, which, as we shall see, offers definite advantages when we require large, modular programs.

1.1 Object Oriented Programming

Object oriented programming (OOP) began with the language Simula, developed in Scandinavia in the mid 60's. Simula was used primarily for simulation programming, where it is natural to model external entities in the software system, and to think in terms of the entities and their behavior. Simula has a syntax much like that of Pascal (which was created at about the same time, and in the same tradition), but the practitioner thinks quite differently when designing a program that will be built in Simula. Rather than deciding on the various processes that must be implemented to complete the system, the designer thinks in terms of the entities (objects) which do exist in the system being modeled, and how they will be represented in the model. The designer then thinks about whether the objects are unique in the system, or whether several objects of the same kind will exist. These collections of similar objects are called "classes", and the chief job of the designer is to design the classes. Objects within a class have the same behavior, so the primary job in designing a class is to determine the behavior of the objects in the class. Often these behaviors are interactions with objects of the same or other classes, so communication patterns must be established to model the interactions. These communication patterns result in objects sharing information by sending messages to each other. One object requests a service from another by sending it a message. The receiving object executes some procedure to provide the service to the sender.

A fundamental idea of OOP, introduced in Simula, is that of inheritance. Using inheritance, a programmer describes a class by extending or specializing some existing class. The description of the new class is only a description of the differences between the old and the new classes. New behaviors can be added and old ones can be modified. There are two benefits of this. The first, though less important, is that it eases the programmers task if much of the behavior of a new kind of object is already programmed into the system. More importantly, classes organized by inheritance into a class hierarchy constitute a unifying structure around which a software system may be built and understood (as per Rule of Seven) by its designers, programmers and users. In effect each class forms an abstraction on which other abstractions may be built.

In brief, the main difference in programming in the object oriented style is that the design of the data items (objects within classes) comes before the design of the procedures (behaviors of the objects, called "methods" in OOP).

After Simula, the next generally known language to adopt support for object oriented programming was Smalltalk, developed in the 70's at XEROX PARC (Palo Alto Research Center). The design of the language was driven by the desire to provide a rapid prototyping system on powerful, personal workstations. It was developed as an aid in the design of graphical human-computer interface systems, and was originally an experiment. Smalltalk and the systems built with it, while not wildly successful in the marketplace (in fact it was purposely kept out of the marketplace for years) have been responsible for much of the evolution in desk top systems that has led to the Macintosh and to OS/2.

Both Simula and Smalltalk are elegantly designed, offering a small number of powerful concepts, and a purity or uniformity that makes them easy to learn, relative to the complexity of the things that may be done with them. Smalltalk does have a reputation for being difficult to learn, but this is due to the richness of the library of source code which is provided with each system, and which must be learned to make full use of the language.

1.2 Other Languages

Object Pascal was developed at Apple Computer in the early 80's to add support for OOP to a popular and fairly standardized version of Pascal: UCSD Pascal. The language was designed by a team headed by Larry Tesler (formerly of XEROX PARC, and a developer of Smalltalk) and aided by Niklaus Wirth (the developer of Pascal). UCSD Pascal (from the University of California at San Diego) already had a modular structure, permitting separate compilation of modules (called units) and separation of interface and implementation. Rather than creating a language from the ground up, Object Pascal was to be an extension of Pascal. The only changes were those necessary to permit the creation of a class hierarchy, to create classes, and to implement the message passing method of procedure execution that appears in Smalltalk and Simula. Even here the syntax changes were simple extensions of constructs already in the language, primarily the record structure. This makes it very easy to get started for those who know Pascal, as the syntax is very familiar. It is only necessary to learn the OOP style of programming, which, admittedly, may be wrenching for a while. The negative side is that Object Pascal lacks the uniformity of some other languages. Integers aren't objects for example, and occasionally you would like them to behave as objects. Sometimes you have to do some extra work to overcome the lack of uniformity. A conscious effort was made to keep the number of new concepts in Object Pascal as small as possible without overly affecting the power of the language, so this is not a great problem. Also on the negative side is the problem that most current implementations of Object Pascal have in hiding information that should not be seen and used by programmers, but which needs to be seen by compilers. Object Pascal is one of the primary development languages on the Macintosh and was originally used to develop MacApp, the standard application development environment. MacApp has now been rewritten in C++. The American National Standards Organization (ANSI) recently wrote a report on object oriented extensions to Pascal, based on the current standard "Extended Pascal". C++, developed in the 1980's at Bell Labs by Barjne Stroustrup, has become emensely popular recently by virtue of its support for object-oriented programming and its improved abstraction facilities over its predecessor, the C language. It is also being standardized by ANSI. Early versions of the language were relatively simple extensions of C. Today, C++ is probably the most widely used "object-oriented" language, though much of the code written in the language is not particularly object-oriented, as least not by the definition given later in this book. More properly, C++ can be described as a language that is optimized for data abstraction and information hiding, in which it is possible to program in an object-oriented style. This author has a book, similar to this one, that attempts to teach such a style in C++.

The object oriented paradigm has been successfully applied to functional programming with several extensions to Lisp and Scheme. In particular the Common Lisp Object System (CLOS) has been used to build several commercial systems. One of the advantages of the Lisp family of languages is that it is possible to add something as sophisticated as object oriented programming to the language without actually changing or extending the language. This is due to the great flexibility of Lisp.

In addition there are a number of other languages that support object oriented programming very well. Some of the best of these are Eiffel, Trellis/Owl, and Beta. Each of these is languages is suitable for the construction of large, complex software systems.

1.3 The Language Modula-3

In the middle 80's a team composed of people from Digital Equipment's Systems Research Center in Palo Alto and Olivetti Corporation undertook the development of a new language that was to be used both in research and in systems development. The language report was first published in 1988 and has been revised once [Modula-3 Report...]. The language was to be a successor to Modula-2, though not, precisely, an extension. Nicklaus Wirth, developer of Pascal and Modula-2, participated in the effort, mostly by simplifying the proposals as they were developed. The final language is approximately as complex as Pascal, but is much more powerful. The simplicity was achieved by providing uniform rules, without exceptions, as well as a small number of very powerful features that cover the necessary techniques without overlapping. A number of language features were left to libraries, which provided additional simplification of the core language. For example, input and output, is handled through libraries, rather than in the language proper. This is the same approach taken by C and C++. In a few other areas, the language provides core functionality that is supplemented by the libraries. Thus TEXT is a built in type (character strings), but most functionality is provided by a library interface Text.i3.

1.4 Programming In Modula-3

A language is only a tool and not a panacea. Any language has advantages and disadvantages. Any language provides better support in some areas than in others. It is often useful to look at what application areas the designers of a language were interested in when you are trying to match a language to a software project. Even those languages that try to be all things to all programmers have their drawbacks, usually size and complexity. Programming in Modula-3, like in any language, is easier if the programmer adopts a mental attitude appropriate for the language, and adopts a style which complements the language and mitigates the weaknesses. This book will attempt to develop such a mental attitude and teach such a style.

Modula-3 is a powerful tool and a very complex language. Learning to use it well will empower the programmer. This is true in several ways, but the most important is the following. Given facility with powerful tools, especially organizational tools, and ideas, it becomes easier to use all tools, even simpler ones. The reverse is not true. Thus it is worth learning to program in the object oriented way, even if you have to program ultimately in languages offering no support whatever for OOP, as you will have learned additional important ways to organize software components that will make the task easier and the product more reliable.

1.5 Introduction to the Elementary Ideas and Syntax of Modula-3

Modula-3 contains a subset that is similar to, though not exactly the same as, Modula-2. Simple programs look very much like Pascal programs. In this section we will present some of the low level details that a programmer needs to know to be able to read Modula-3 effectively. We assume here that the reader is a "skilled novice" in either C or Pascal. This means that the reader is fluent with her or his language in terms of the usage of functions and procedures, arrays, program control statements, structs-records, and has had some experience programming with pointers. Appendix A has some additional material, especially on pointers. A more complete source of this information may be found in the book "Modula-3," by Sam Harbison. [Prentice-Hall, 1992]. A more complete source is the so-called Green Book, "Systems Programming with Modula-3" Greg Nelson, Editor, Prentice-Hall, 1991. Here we are going to focus on a few topics that we will need in this book. Some of them are quite elementary and some are not. We won't give the last word on any of them.

1.5.1 What a Modula-3 Program Looks Like.

Modula-3 programs are built from Modules. Each Module consists of an interface part, stored in a file with file suffix ".i3," and an implementation part, stored in a file with suffix ".m3." The system provides an interface "Main.i3" and the main part of a Modula 3 program is an implementation of this interface. For example, the following is the traditional "Hello World" program written in Modula-3. Note that Module-3 is "case sensitive." Capitalization is important and must be consistent.

MODULE Main;
IMPORT  Wr, Stdio;

BEGIN
		Wr.PutText(Stdio.stdout, "Hello World.\n");
END Main.

implementation 	(Main)
import		(libm3)
program 	(Hello)

IMPORT Wr, Rd;  

MODULE Main;
IMPORT  Wr, Stdio, Fmt;

BEGIN
	FOR i := 1 TO 3 DO
		Wr.PutText(Stdio.stdout, "Hello World ");
		Wr.PutText(Stdio.stdout, Fmt.Int(i));
		Wr.PutChar(Stdio.stdout, `\n');
	END;
END Main.

Types               Examples                                       
                                                                   
INTEGER		48, -53  
CARDINAL 	0, 34358192  
REAL		4.2, 8.0, 2.3E-6  
LONGREAL                                                 
EXTENDED                                                 
TEXT		"Hello World."  
CHAR		c', '\n'  
BOOLEAN		TRUE, FALSE  
MUTEX                                                 
enumerations	{North, East, South, West}  
subranges 	[1..10], [North..South]  
sets  		SET OF {North, East, South, West}  
arrays		ARRAY [1..10] OF INTEGER  
records		RECORD x,y:REAL END  
pointers	REF INTEGER  
packed types	BITS 4 FOR [1..10]  
procedures	PROCEDURE(i:INTEGER):INTEGER  
objects		OBJECT x: CHAR; METHODS show(); END            

IF a<b OR c < 0 THEN
	SWAP(a,b);
END;

IF I < 0 THEN
	. . .
ELSIF  I <= 5 THEN
	. . .
ELSIF I < 10 THEN
	. . .
ELSE
	. . .
END;

CASE I OF
| 1..5 => . . .
| 6..9 => . . .
ELSE . . .  (* I < 0 or I >= 10 *)
END;

LOOP
	. . .
	IF X < 0 THEN EXIT;
	. . .
END;

FOR I := 1 TO 10 BY 2 DO 
	. . .
END; 

WITH  X = Employed^.Name DO
	. . .  X.First . . . X.Last . . .  
END;

TYPE
	RefInt = REF INTEGER;

VAR
	p0, p1: RefInt;

	p0 := NEW(RefInt);

	p1 := NEW( REF INTEGER);

	p0^ := 5;

	p0  := 5;

	p1^ := p0^;

	p1 := p0;

RefInt <: REFANY;   (* Read: RefInt is a subtype of REFANY *)

VAR
	PTop : REFANY;

	PTop := p0;

	Wr.PutText(Stdio.stdout, Fmt.Int(PTop^));

	Wr.PutText(Stdio.stdout, Fmt.Int(NARROW (PTop, RefInt)^));

VAR A: REF ARRAY OF INTEGER;

	A := NEW (ARRAY OF INTEGER, size);

	A[3] := 5;  (* Equivalent to A^[3] := 5 *) 

	FOR i := FIRST(A^) TO LAST(A^)
		A[i] := 0;
	END;

TYPECASE X OF
	| NULL =>  T := ""; (* The empty string in case X = NIL *)
	| REF INTEGER (Y) => T := Fmt.Int(Y^);
	| REF CHAR (Y) => T := Fmt.Char(Y^);
	ELSE T := "";
END;
Wr.PutText(Stdio.stdout, T);

IF ISTYPE(X, RefInt) THEN
	WITH I = NARROW(X, RefInt) DO
		I^ := I^ + 99;
	END;
END;

PROCEDURE Min (x,y:INTEGER):INTEGER =
BEGIN
	IF x <= y THEN RETURN x ELSE RETURN y; END;
END Min;

PROCEDURE (x,y:INTEGER):INTEGER;

TYPE CompareFunc = PROCEDURE (x,y:INTEGER):INTEGER;

VAR compare: CompareFunc;
. . .
compare := Min;
y := compare(z,3);  (* Min will be called *)

PROCEDURE Min (x: INTEGER; y:INTEGER := 0):INTEGER =
BEGIN
	IF x < y THEN RETURN x ELSE RETURN y; END;
END Min;

	. . . Min (3,4) . . .			(*Usual positional arguments *)
	. . . Min (3) . . .			(* y defaults to zero *)
	. . . Min (x := 3,y := 4) . . .	(* Named arguments *)
	. . . Min (y := 4, x := 3) . . .	(*   in any order. *)

PROCEDURE Sort(A: someArrayType; Compare: CompareFunc) = 
BEGIN
	. . .
	IF A[x] = Compare(A[x], A[y]) THEN . . . END;
	. . .
END Sort;

Sort(A, Min);

EVAL Min(4,5);

INTERFACE Nothing;
	PROCEDURE Message(i:INTEGER);
END Nothing. 

MODULE Nothing
EXPORTS Nothing; (* This line is optional, since they have the same name. *)
IMPORT Wr, Stdio, Fmt;

	PROCEDURE Message(i.INTEGER) =
		Wr.PutText(Stdio.stdout, "Hello World number: ");
		Wr.PutText(Stdio.stdout, Fmt.Int(i));
		Wr.PutText(Stdio.stdout, " .\n");
	END Message;

END Nothing.

MODULE Main; (* EXPORTS Main, of course *)
IMPORT Nothing;
BEGIN
	Nothing.Message(365);
END Main.

module		(Nothing)
implementation	(Main)
import		(libm3)
program		(test) 

(* SimpleStack.i3 *)
INTERFACE SimpleStack;

TYPE

	T = RECORD 
		elements: ARRAY[0..99] OF REAL;
		top: INTEGER;
		END;

(* Call INITIALIZE before using any SimpleStack.T *)

PROCEDURE INITIALIZE (VAR S: T) ;
	(* Postcondition: S is empty);
PROCEDURE PUSH (VAR S: T; E: REAL) ;
	(* Precondition: S not full *)
	(* Postcondition: E = S.top *)
PROCEDURE POP (VAR S: T; VAR E: REAL) ;
	(* Precondition: S not empty *)
	(* Postcondition:  -- see the next chapter. *)
PROCEDURE EMPTY(S: T) ;

PROCEDURE TOP(S: T; VAR E: REAL) ;
	(* Precondition: S not empty *)
	(* Postcondition: E is the top and S is not modified. *)

END SimpleStack;

(* SimpleStack.m3 *)
MODULE SimpleStack;

PROCEDURE INITIALIZE (VAR S: T) =
BEGIN
	S.top := -1;
END INITIALIZE;

PROCEDURE PUSH (VAR S: T; E: REAL) =
BEGIN
	IF S.top < 99 THEN
		INC(S.top);
		S.elements[S.top] := E;
	END;
END PUSH;

PROCEDURE POP (VAR S: T; VAR E: REAL) =
BEGIN
	IF S.top >= 0 THEN
		E := S.elements[S.top];
		DEC(S.top);
	END;
END POP;

PROCEDURE EMPTY(S: T) =
BEGIN
	RETURN S.top < 0;
END EMPTY;

PROCEDURE TOP(S: T; VAR E: REAL) =
BEGIN
	IF S.top >= 0 THEN E := S.elements[S.top]; END;
END TOP;

END SimpleStack.

(* Main.m3 *)
MODULE Main;
IMPORT SimpleStack, Stdio, Fmt, Wr.  

VAR S: SimpleStack.T;

SimpleStack.INITIALIZE(S);
SimpleStack.PUSH(S, 5.0);
SimpleStack.PUSH(S, 3.0);
SimpleStack.PUSH(S, 3.0);
SimpleStack.POP(S);
Wr.PutText(Stdio.stdout, Fmt.Real(SimpleStack.TOP(S)));
SimpleStack.PUSH(S, 2.0);
	. . .
END Main.

GENERIC INTERFACE Stack(ELEMENT);

TYPE

	T = RECORD 
		elements: ARRAY[0..99] OF ELEMENT.T;
		top: INTEGER;
		END;

PROCEDURE INITIALIZE (VAR S: T) ;
	(* Postcondition: S is empty);
PROCEDURE PUSH (VAR S: T; E: ELEMENT.T) ;
	(* Precondition: S not full *)
	(* Postcondition: E = S.top *)
PROCEDURE POP (VAR S: T; VAR E: ELEMENT.T) ;
	(* Precondition: S not empty *)
	(* Postcondition:  -- see the next chapter. *)
PROCEDURE EMPTY(S: T) ;

PROCEDURE TOP(S: T; VAR E: ELEMENT.T) ;
	(* Precondition: S not empty *)
	(* Postcondition: E is the top and S is not modified. *)

END SimpleStack;

GENERIC MODULE SimpleStack (ELEMENT);

PROCEDURE INITIALIZE (VAR S: T) =
BEGIN
	S.top := -1;
END INITIALIZE;

PROCEDURE PUSH (VAR S: T; E: ELEMENT.T) =
BEGIN
	IF S.top < 99 THEN
		INC(S.top);
		S.elements[S.top] := E;
	END;
END PUSH;

PROCEDURE POP (VAR S: T; VAR E: ELEMENT.T) =
BEGIN
	IF S.top >= 0 THEN
		E := S.elements[S.top];
		DEC(S.top);
	END;
END POP;

PROCEDURE EMPTY(S: T) =
BEGIN
	RETURN S.top < 0;
END EMPTY;

PROCEDURE TOP(S: T; VAR E: ELEMENT.T) =
BEGIN
	IF S.top >= 0 THEN E := S.elements[S.top]; END;
END TOP;

END SimpleStack.

INTERFACE RealStack = Stack(Real) End RealStack.

MODULE RealStack EXPORTS RealStack = Stack(Real) End RealStack.

MODULE Main;
IMPORT RealStack, Stdio, Fmt, Wr.  

VAR S: RealStack.T;

RealStack.INITIALIZE(S);
RealStack.PUSH(S, 5.0);
RealStack.PUSH(S, 3.0);
RealStack.PUSH(S, 3.0);
RealStack.POP(S);
Wr.PutText(Stdio.stdout, Fmt.Real(RealStack.TOP(S)));
RealStack.PUSH(S, 2.0);
	. . .
END Main.

INTERFACE Integer;
TYPE
	T = INTEGER;
END Integer;

generic_module	(Stack)
module		(RealStack)
implementation	(Main)
import		(libm3)
program		(test) 

EXCEPTION fatal;

RAISE fatal;

PROCEDURE Error(s:TEXT) RAISES {fatal};

. . .
TRY
	. . .
	Error("We seem to be out of barrakas.");

EXCEPT
	| fatal => (* try to get more barrakas *)
		. . .
	ELSE
END;

	values : ARRAY[1..10] OF INTEGER;

PROCEDURE readarray(VAR A: ARRAY OF INTEGER; LENGTH: INTEGER);
PROCEDURE writearray(READONLY A: ARRAY OF INTEGER );
	(* READONLY means that the procedure will not modify A *)
PROCEDURE sumarray(READONLY A: ARRAY OF INTEGER):INTEGER;

TYPE CheckType = PROCEDURE(a,b:INTEGER):BOOLEAN;

PROCEDURE Sort(A: ARRAY OF INTEGER) =
VAR temp: INTEGER;
BEGIN
	FOR i := FIRST(A) TO LAST(A) DO
		FOR j := FIRST(A)+1 TO LAST(A) - i DO
			IF A[j] < A[j-1] THEN
				temp := A[j];
				A[j] := A[j-1];
				A[j-1] := temp;
		END;
	END;
END Sort;

PROCEDURE less(a,b:INTEGER):BOOLEAN = 
BEGIN
	RETURN a < b; 
END less;

PROCEDURE more(a,b:INTEGER):BOOLEAN = 
BEGIN
	RETURN a > b;
END more;

INTERFACE Test;

PROCEDURE printIt(msg: TEXT);

END Test.

MODULE Test;
IMPORT Fmt, Stdio, Wr, Text;

PROCEDURE printIt(msg: TEXT) =
BEGIN
	Wr.PutText(Stdio.stdout, Text.Cat(msg , Text.FromChar(`\n')));
END printit;

END Test.

MODULE Main;
IMPORT Test;
VAR hello : Text;
BEGIN
	hello := "Hello world.";
	Test.printIt( hello);
END Main.