Programming in Modula-2

This text is an introduction to programming in general, and a manual for programming with the language Modula-2 in particular. It is oriented primarily towards people who have already acquired some basic knowledge of programming and would like to deepen their understanding in a more structured way. Nevertheless, an introductory chapter is included for the benefit of the beginner, displaying in a concise form some of the fundamental concepts of computers and their programming. The text is therefore also suitable as a self-contained tutorial. The notation used is Modula-2, which lends itself well for a structured approach and leads the student to a working style that has generally become known under the title of structured programming.

Although this manual assumes that its reader is already familiar with the basic notions of computer and programming, it may be appropriate to start out with the explanation of some concepts and their terminology. We recognize that — with rare exceptions — programs are written — more appropriately: designed — with the purpose of being interpreted by a computer. The computer then performs a process, i.e. a sequence of actions, according to the specifications given by that program. The process is also called a computation.

Let us follow the steps of development of a simple program and thereby explain some of the fundamental concepts of programming and of the basic facilities of Modula. The task shall be, given two natural numbers x and y, to compute their greatest common divisor (gcd).

A formal language is an infinite set of sequences of symbols. The members of this set are called sentences, and in the case of a programming language these sentences are programs. The symbols are taken from a finite set called the vocabulary. Since the set of programs is infinite, it cannot be enumerated, but is instead defined by rules for their composition. Sequences of symbols that are composed according to these rules are said to be syntactically correct programs; the set of rules is the syntax of the language.

The preceding chapter has introduced a formalism, by which the structures of well-formed programs will subsequently be defined. It defines, however, merely the way in which programs are composed as sequences of symbols, in contrast to sequences of characters. This “shortcoming” is quite intentional: the representation of symbols (and thereby programs) in terms of characters is considered too much dependent on individual implementations for the general level of abstraction appropriate for a language definition. The creation of an intermediate level of representation by symbol sequences provides a useful decoupling between language and ultimate program representation. The latter depends on the available character set. As a consequence, we need to postulate a set of rules governing the representation of symbols as character sequences. The symbols of the Modula vocabulary are divided into the following classes: identifiers, numbers, strings, operators and delimiters, and comments.

The specification of an action is called a statement. Statements can be interpreted (executed), and that interpretation (execution) has an effect. The effect is a transformation of the state of the computation, the state being represented by the collective values of the program’s variables. The most elementary action is the assignment of a value to a variable. The assignment statement has the form$ assignment = designator “: =” expression.and its corresponding action consists of three parts in this sequence: 1.evaluate the designator designating a variable,2.evaluate the expression yielding a value,3.replace the value of the variable identified in 1. by the value obtained in 2.

It is a prime characteristic of computers that individual actions can be selected, repeated, or performed conditionally depending on some previously computed results. Hence the sequence of actions performed is not always identical with the sequence of their corresponding statements. The sequence of actions is determined by control structures indicating repetition, selection, or conditional execution of given statements.

We have previously stated that all variables need be declared. This means that their names are introduced in the heading of the program. In addition to introducing the name (and thereby enabling a compiler to detect and indicate misspelled identifiers), declarations have the purpose of associating a data type with each variable. This data type represents information about the variable which is permanent in contrast, for example, to its value. This information may again aid in detecting inconsistencies in an erroneous program, inconsistencies that are detectable by mere inspection of the program text without requiring its interpretation.

It has been mentioned previously that all identifiers used in a program must be declared in the program’s heading, unless they are so-called standard identifiers known in every program (or are imported from some other module).

So far, we have given each variable an individual name. This is impractical, if many variables are necessary that are treated in the same way and are of the same type, such as, for example, if a table of data is to be constructed. In this case, we wish to give the entire set of data a name and to denote individual elements with an identifying number, a so-called index. The data type is then said to be structured — more precisely: array structured. In the following example, the variable a consists of N elements, each being of type CARDINAL, and the indices range from 0 to N-1.

Consider the task of processing a set of data consisting of a header and a sequence of N similar individual units. It might be generally described as $$ \begin{array}{l} ReadHeader;\\ ProcessHeader;\\ WriteHeader;\\ FOR i : = 1 TO N DO\\ {\rm{ ReadUnit; ProcessUnit;}}\\ {\rm{ Write(i); WriteUnit}}\\ {\rm{END}} \end{array} $$

If we inspect the preceding example of procedure Add, we notice that the role of the variable i is strictly confined to the procedure body. This inherent locality should be expressed explicitly, and can be done by declaring i inside the procedure declaration. i thereby becomes a local variable.

Procedures may be given parameters. They are the essential feature that make procedures so useful. Consider again the previous example of procedure Add. Very likely a program contains several arrays to which the procedure should be applicable. Redefining it for each such array would be cumbersome, inelegant, and can be avoided by introducing its operand as a parameter as follows.

So far we have encountered two possibilities to pass a result from a procedure body to its calling place: the result is either assigned to a non-local variable or to a variable parameter. There exists a third method: the function procedure. It permits the use of the computed result (as an intermediate value) in an expression. The function procedure identifier stands for a computation as well as for the computed result. The procedure declaration is characterized by the indication of the result’s type behind the parameter list. As an example, we rephrase the power computation given above.

Procedures may not only be called, but can call procedures themselves. Since any procedure that is visible can be called, a procedure may call itself. This self-reactivation is called recursion. Its use is appropriate when an algorithm is recursively defined and in particular when applied to a recursively defined data structure.

Every variable declaration specifies the variable’s type as its constant property. The type can be one of the standard, primitive types, or it may be of a type declared in the program itself. Type declarations have the form $$ {\text{\$ TypeDeclaration = identifier = type}}{\text{.}} $$

A new unstructured type may be declared as an enumeration, i.e. by enumerating the set of values which belong to this type. The type declaration $$ T\;{\rm{ = (c1,c2, }} \ldots \;,cn{\rm{)}} $$ introduces the new, unstructured type T, whose values are denoted by the n constant identifiers c1, c2, ... , cn.

If a variable is known (or supposed) to assume values within a certain contiguous range only, this fact can be specified by declaring it to be of a so-called subrange type. Assume, for example, that a variable i assumes values in the range from 1 up to (and including) N only, we specify $$ \begin{array}{l} TYPES\;{\rm{ = [1}}..{\rm{N]}}\\ {\rm{VAR i: S}} \end{array} $$ (this can, of course, be abbreviated by VAR i: [1..N]).

Every data type defines a set of values. In the case of a set type S, this set of values is the set of all possible sets consisting of elements from a given base type B. For example, if the base type B is the subrange $$ B = [0 .. 1] $$ and the set type S is declared as $$ S = SET OF B $$ then the values of type S are the sets {}, {0}, {1}, {0,1}. If the base type has n distinct values, then its set type has 2 to the power of n values.{} denotes the empty set.

In an array all elements are of the same type. In contrast to the array, the record structure offers the possibility to declare a collection of elements as a unit even if the elements are of different types. The following examples are typical cases where the record is the appropriate choice of structuring method. A date consists of three elements, namely day, month, and year. A description of a person may consist of the person’s names, sex, identification number, and birthdate.

Record types offer yet another kind of flexibility. A given record may assume various variant forms. This implies that the number and kind of fields may differ among different variables although they are of the same record type. It is obvious that this flexibility also gives rise to programming errors that are difficult to detect. In particular, it is now possible to assume in some part of a program that a variable is of a certain variant, whereas it actually is of another variant. This facility is therefore to be used with great caution.

Array, record and set structures share the common property that they are static. This implies that variables of such a structure maintain the same structure during the whole time of their existence. In many applications, this is an intolerable restriction; they require data which do not only change their value, but also their composition, size, and structure. Typical examples are lists and trees that grow and shrink dynamically. Instead of providing list and tree structures, a collection that for some applications would again not suffice, Modula offers a basic tool to construct arbitrary structures. This is the pointer type.

So far, we have regarded procedures exclusively as program parts, i.e. as texts that specify actions to be performed on variables whose values are numbers, logical values, characters, etc. However, we may take the view that procedures themselves are objects that can be assigned to variables. In this light, a procedure declaration appears as a special kind of constant declaration, the value of this constant being a procedure. If we allow variables in addition to constants, it must be possible to declare types whose values are procedures. These are called procedure types.

Modules are the most important feature distinguishing Modula-2 from its ancestor, Pascal. We have already encountered modules, simply because every program is a module. However, most programs are partitioned into several modules, each module containing constants, variables, procedures, and perhaps types. Objects declared in other modules can be referenced in a module M, if they are explicitly made to be known in M, i.e. if they are imported into M. In the examples of the preceding chapters, we have typically imported procedures for input and output from modules containing collections of frequently used procedures. These procedures are actually part of our program, even if we have not programmed them and they are textually disjoint.

A definition part of a module is called a definition module. It contains the list of exported objects and their declarations. These may be any kind of objects, but a few additional rules must be mentioned.

The quality of a program has many aspects and is an elusive property. A user of a program may judge it according to its efficiency, reliability, or convenience of user dialog. Whereas efficiency can be expressed in terms of numbers, convenience of usage is rather a matter of personal judgement, and all too often a program’s usage is called convenient as long as it is conventional. An engineer of a program may judge its quality according to its clarity and perspicuity, again rather elusive and subjective properties. However, if a property cannot be expressed in terms of precise numbers, this is no reason for classifying it as irrelevant. In fact, program clarity is enormously important, and to demonstrate (prove?) a program’s correctness is ultimately a matter of convincing a person that the program is trustworthy. How can we approach this goal? After all, complicated tasks usually do inherently require complex algorithms, and this implies a myriad of details. And the details are the jungle in which the devil hides.

So far we have encountered modules as sections of text to be considered “side by side”. However, we now have to learn that modules can be textually nested. An immediate consequence is that nested modules are not separately compilable. They are called local modules, and their only purpose is the hiding of details of their internally declared objects.

The usefulness and the success of high-level programming languages rests on the principle of abstractions, the hiding of details that pertain to the computer which is used to execute the program rather than to the algorithm expressed by the program. The domain that has most persistently resisted abstraction is that of input and output operations. This is not surprising, because input and output inherently involve the activation of devices that are peripheral to the computer, and whose structure, function, and operation differ strongly among various kinds and brands. Many programming languages have typically incorporated statements for reading and writing data in sequential form without reference to specific devices or storage media. Such an abstraction has many advantages, but there exist always applications where some property of some device is to be utilized that is poorly, if at all, available through the standard statements of the language. Also, generality is usually costly, and consequently operations that are conveniently implemented for some devices may be inefficient if applied to other devices. Hence, there also exists a genuine desire to make transparent the properties of some devices for applications that require their efficient utilization. Simplification and generalization by suppression of details is then in direct conflict with the desire for transparency for efficient use.

Sequential input and output implies that elements of data can be transmitted without explicit indication of position. This is natural, if the position is predetermined by the storage medium, such as a tape (which by definition constitutes a sequence), or a keyboard (from which data originate in strict sequence in time), or a typewriter (where character positions are determined by the mechanical movement of the printing device). Even if the storage device would allow for greater flexibility, sequential input and output is convenient, if the structure of the data is inherently sequential. For example, a text is inherently sequential, and the omission of positioning information for each character is a great simplification of the reading and writing tasks. And lastly, sequential input and output is economical, because buffering of data is easily possible between processes (devices) that operate concurrently. All this explains, why sequential data handling is so common and highly recommendable.

High-level languages encourage and even force the programmer to conceive his programs in a structured fashion. Structured statements provide a high degree of order and perspicuity of the programmed algorithmic text. Structured data declarations allow a high level of abstraction in the organization of a program’s data and their organization in terms that are appropriate for the problem at hand. The principal advantage is additional safety against mistakes, because structure provides redundancy which can (and must) be used by implementations — in particular compilers — to detect inconsistencies of the program which become manifest as violations of language rules. In this respect, the concept of data types is particularly powerful and is therefore the primary characteristic of high-level programming languages.

In this chapter we introduce concepts for multiprogramming, i.e. the programming of several, concurrently executed computations. These facilities are deliberately restricted to the formulation of so-called loosely coupled processes. We exclude the area of tightly coupled arrays of processes, considering their field of application as fairly narrow and specialized. Instead, we restrict the discussion to programs that describe several processes that interact relatively infrequently, and are therefore said to be loosely coupled. By infrequently is meant that interaction occurs at a few, well-defined, explicit points in the program, and by a process we understand a sequence of actions, i.e. an inherently sequential process. Programming as encountered so far can therefore be considered as a special case involving one single process only. Inversely, we can inherit for multiprogramming all facilities and techniques learned so far, and we need to add merely a few facilities for the designation of concurrent processes and for their interaction. In this regard we follow the tradition of earlier languages for multiprogramming such as Modula-1 and Brinch Hansen’s Concurrent Pascal.

In the last chapter we have discussed systems with several processes and how to simulate concurrent processes by time-sharing a single processor. Now we consider the inverse situation, where several processors participate in the execution of a single process. For the sake of simplicity, let us look at a cyclic process consisting of a producing and a consuming part.