# Introduction

Modula-3 invites you to structure your program as a set of modules interconnected via interfaces. Each interface typically corresponds to an abstract data type. Some of these abstractions are particular to the program at hand, but others are more general. This manual describes a collection of interfaces defining abstractions that SRC's programmers have found useful over a number of years of experience with Modula-3 and its precursors.

This manual concentrates on basic abstractions such as the standard interfaces required or recommended by the Modula-3 language definition, various data structures, portable operating-system functions, and control of the Modula-3 runtime. For building distributed systems, see [NetObj] . For building user interfaces, see [Trestle] , [VBTkit] , and [FormsVBT] .

## Naming conventions for types.

We generally give the name `T` to the main type in an interface. For example, the main type in the `Date` interface is `Date.T`.

Most object types have a method that is responsible for initializing the object. By convention, this method is named `init`, and returns the object after initializing it, so that the object can be initialized and used in an expression at the same time: for example,

    VAR s := NEW(Sequence.T).init();

If there are several different ways to initialize the object, there will be several methods. The most basic will be named `init` and the others will receive descriptive names. For example, `Sequence.T.init` initializes an empty sequence; `Sequence.T.fromArray` initializes a sequence from an array.

Many of our types are ``abstract'' in the sense that they define the methods of a type, but not their implementations. Various subtypes of the abstract type define different methods corresponding to different instances of the abstract type. For example, the type `Rd.T` is a abstract reader (a stream of input characters). Its subtype `FileRd.T` is a reader whose source is a file; its subtype `TextRd.T` is a reader whose source is a text string.

If you allocate an object of an abstract type and attempt to use it, you will almost certainly get a checked runtime error, since its methods will be `NIL`. Therefore, you must read the interfaces to find out which types are abstract and which are concrete. The typical pattern is that an abstract type does not have an `init` method, but each of its concrete instances does. This allows different subtypes to be initialized differently. For example, `FileRd.T` has an `init` method that takes a file; `TextRd.T` has an `init` method that takes a text; and `Rd.T` has no `init` method at all.

For some abstract types we choose to honor one of its subtypes as a ``default implementation''. For example, we provide a hash table implementation as the default for the abstract type `Table.T`. In this case we vary the naming convention: instead of a separate interface `HashTable` defining the concrete type `HashTable.T` as a subtype of `Table.T`, we declare the default concrete type in the same interface with the abstract type and give it the name `Default`. Thus `Table.T` and `Table.Default` are respectively the abstract table type and its default implementation via hash tables. If you want to allocate a table you must allocate a `Table.Default`, not a `Table.T`. On the other hand, if you are defining a procedure that requires a table as a parameter, you probably want to declare the parameter as a `Table.T`, not a `Table.Default`, to avoid excluding other table implementations.

We use abstract types only when they seem advantageous. Thus the type `Sequence.T`, which represents an extensible sequence, could have been an abstract type, since different implementations are easy to imagine. But engineering considerations argue against multiple implementations, so we declared `Sequence.T` as a concrete type.

## Concurrency.

The specification of a Modula-3 interface must explain how to use the interface in a multithreaded program. When not otherwise specified, each procedure or method is atomic: it transforms an initial state to a final state with no intermediate states that can be observed by other threads.

Alternatively, a data structure (the state of an entire interface, or of a particular instance of an object type) can be specified as unmonitored, in which case the procedures and methods operating on it are not necessarily atomic. In this case it is the client's responsibility to ensure that multiple threads are not accessing the data structure at the same time---or more precisely, that this happens only if all the concurrent accesses are read-only operations. Thus for an unmonitored data structure, the specification must state which procedures or methods are read-only.

If all operations are read-only, there is no difference between monitored and unmonitored data structures.

## Aliasing.

The procedures and methods defined in this manual are not guaranteed to work with aliased `VAR` parameters.

## Exception parameters for abstract types.

It is often useful for an exception to include a parameter providing debugging information of use to the programmer, especially when the exception signals abstraction failure. Different implementations of an abstract type may wish to supply different debugging information. By convention, we use the type `AtomList.T` for this purpose. The first element of the list is an error code; the specification of the subsequent elements is deferred to the subtypes. Portable modules should treat the entire parameter as an opaque type.

An implementation module can minimize the probability of collision by prefixing its module name to each atom that it includes in the list.

## Standard generic instances.

Several of the interfaces in this manual are generic. Unless otherwise specified, standard instances of these interfaces are provided for all meaningful combinations of the formal imports ranging over `Atom`, `Integer`, `Refany`, and `Text`.

For each interface that is likely to be used as a generic parameter, we define procedures `Equal`, `Compare`, and `Hash`.

The procedure `Equal` must compute an equivalence relation on the values of the type; for example, `Text.Equal(t, s)` tests whether `t` and `s` represent the same string. (This is different from `t = s`, which tests whether `t` and `s` are the same reference.)

If there is a natural total order on a type, then we define a `Compare` procedure to compute it, as follows:

    PROCEDURE Compare(x, y: X): [-1..1];
    (* Return
    | -1 `if` x R y `and not` Equal(x, y)`,`
    |  0 `if` Equal(x, y)`, and`
    |  1 `if` y R x `and not` Equal(x, y)`.`
    *)

(Technically, `Compare` represents a total order on the equivalence classes of the type with respect to `Equal`.) If there is no natural order, we define a `Compare` procedure that causes a checked runtime error. This allows you to instantiate generic routines that require an order (such as sorting routines), but requires you to pass a compare procedure as an explicit argument when calling the generic routine.

The function `Hash` is a hash function mapping values of a type `T` to values of type `Word.T`. This means that (1) it is time-invariant, (2) if `t1` and `t2` are values of type `T` such that `Equal(t1, t2)`, then `Hash(t1) = Hash(t2)`, and (3) its range is distributed uniformly throughout `Word.T`.

Note that it is not valid to use `LOOPHOLE(r, INTEGER)` as a hash function for a reference `r`, since this is not time-invariant on implementations that use copying garbage collectors.

## Sets and relations.

The specifications in this manual are written informally but precisely, using basic mathematical concepts. For completeness, here are definitions of these concepts.

A set is a collection of elements, without consideration of ordering or duplication: two sets are equal if and only if they contain the same elements.

If `X` and `Y` are sets, a map `m` from `X` to `Y` uniquely determines for each `x` in `X` an element `y` in `Y`; we write `y = m(x)`. We refer to the set `X` as the domain of `m`, or `dom(m)` for short, and the set `Y` as the range of `m`. A partial map from `X` to `Y` is a map from some subset of `X` to `Y`.

If `X` is a set, a relation `R` on `X` is a set of ordered pairs `(x, y)` with `x` and `y` elements of `X`. We write `x R y` if `(x, y)` is an element of `R`.

A relation `R` on `X` is reflexive if `x R x` for every `x` in `X`; it is symmetric if `x R y` implies that `y R x` for every `x`, `y` in `X`; it is transitive if `x R y` and `y R z` imply `x R z` for every `x`, `y`, `z` in `X`; and it is an equivalence relation if it is reflexive, symmetric, and transitive.

A relation `R` on `X` is antisymmetric if for every `x` and `y` in `X`, `x = y` whenever both `x R y` and `y R x`; `R` is a total order if it is reflexive, antisymmetric, transitive, and if, for every `x` and `y` in `X`, either `x R y` or `y R x`.

If `x` and `y` are elements of a set `X` that is totally ordered by a relation `R`, we define the interval `[x..y]` as the set of all `z` in `X` such that `x R z` and `z R y`. Note that the notation doesn't mention `R`, which is usually clear from the context (e.g., lower or equal for numbers). We say `[x..y]` is closed at its upper and lower endpoints because it includes `x` and `y`. Half-open and open intervals exclude one or both endpoints; notationally we substitute a parenthesis for the corresponding bracket, for example `[x..y)` or `(x..y)`.

A sequence `s` is a map whose domain is a set of consecutive integers. In other words, if `dom(s)` is not empty, there are integers `l` and `u`, with `l<=u`, such that `dom(s)` is `[l..u]`. We often write `s[i]` instead of `s(i)`, to emphasize the similarity to a Modula-3 array. If the range of `s` is `Y`, we refer to `s` as a sequence of `Y`'s. The length of a sequence `s`, or `len(s)`, is the number of elements in `dom(s)`.

In the specifications, we often speak of assigning to an element of a sequence or map, which is really a shorthand for replacing the sequence or map with a suitable new one. That is, assigning `m(i) := x` is like assigning `m := m'`, where `dom(m')` is the union of `dom(m)` and `{i}`, where `m'(i) = x`, and where `m'(j) = m(j)` for all `j` different from `i` and in `dom(m)`.

If `s` is a finite sequence, and `R` is a total order on the range of `s`, then sorting `s` means to reorder its elements so that for every pair of indexes `i` and `j` in `dom(s)`, `s[i] R s[j]` whenever `i <= j`. We say that a particular sorting algorithm is stable if it preserves the original order of elements that are equivalent under `R`.