Some Useful Modula-3 Interfaces
Data Structures
Sequence
Sequence is a generic interface de ning extensible sequences. Elements can be added or removed at either end of a sequence; they can also be accessed or updated at speci ed indexes. The expected cost of every method of a sequence is constant.
GENERIC INTERFACE Sequence(Elem);
Where Elem.T is a type that is not an open array type.
TYPE
T <: Public;
Public = OBJECT METHODS
init(sizeHint: CARDINAL := 5): T;
fromArray(READONLY a: ARRAY OF Elem.T): T;
addhi(READONLY x: Elem.T);
addlo(READONLY x: Elem.T);
remhi(): Elem.T;
remlo(): Elem.T;
put(i: CARDINAL; READONLY x: Elem.T);
size(): CARDINAL;
gethi(): Elem.T;
getlo(): Elem.T;
get(i: CARDINAL): Elem.T
END;
A Sequence(Elem).T (or just a sequence) represents an extensible sequence of
Elem.Ts.
The rst group of methods have side e ects on the sequence. The call
s.init(sizeHint)
initializes s to be the empty sequence. Furthermore init assumes that at least sizeHint elements will be added to the sequence; these operations may be executed more e ciently than if sizeHint was defaulted. The call
s.fromArray(a)
initializes s to be the sequence with elements a[0], …, a[LAST(a)]. The call
s.addhi(x)
appends x to the end of s. Thus it does not change the index of any existing element. The call
s.addlo(x)
appends x to the front of s. Thus it increases the index of all existing elements by one. The call
s.remhi()
removes and returns the last element of s. Thus it does not change the index of any of s’s other elements. If s is empty, s.remhi() causes a checked runtime error. The call
s.remlo()
removes and returns the rst element of s. Thus it decreases the index of all other elements of s by one. If s is empty, s.remlo() causes a checked runtime error. The call
s.put(i, x)
replaces element i of s with x. Element 0 is the rst element. It is a checked runtime error unless i is less than s.size().
The second group of methods have no side e ect on the sequence. The call
s.size()
returns the number of elements in s. The call
s.get(i)
returns element i of s. It is a checked runtime error unless i is less than s.size(). The call
s.gethi()
returns the last element of s; that is, it is equivalent to s.get(s.size()-1). The call
s.getlo()
returns the rst element of s; that is, it is equivalent to s.get(0).
PROCEDURE Cat(s, t: T): T;
Return a sequence whose elements are the concatenation of s and t.
PROCEDURE Sub(s: T; start: CARDINAL;
length: CARDINAL := LAST(CARDINAL)): T;
Return a sub-sequence of s: empty if start >= t.size() or length
= 0; otherwise the subsequence ranging from start to the minimum of start+length-1 and s.size()-1.
Cat and Sub create new sequences; they have no side-e ects.
Atom 27
Sequences are unmonitored: a client accessing a sequence from multiple threads must ensure that if two operations are active concurrently, then neither of them has side e ects on the sequence.
END Sequence.
The standard instances are named AtomSeq, IntSeq, RefSeq, and TextSeq.
An Atom.T is a unique representative for a set of equal texts (like a Lisp atomic symbol)
INTERFACE Atom;
TYPE T <: REFANY;
PROCEDURE FromText(t: TEXT): T;
Return the unique atom a such that for any text u, if Text.Equal(u, t), then FromText(u) = a.
PROCEDURE ToText(a: T): TEXT;
Return a text t such that FromText(t) = a.
PROCEDURE Equal(a1, a2: T): BOOLEAN;
Return a1 = a2.
PROCEDURE Hash(a: T): INTEGER;
Return a hash code for a by taking the image of ToText(a) under some xed hash function.
PROCEDURE Compare(a1, a2: T): [-1..1];
Cause a checked runtime error.
END Atom.
Compare causes a checked runtime error because there is no default order on atoms.
List and ListSort
The generic interface List provides operations on linked lists of arbitrary element types.
GENERIC INTERFACE List(Elem);
Where Elem.T is not an open array type and Elem contains
PROCEDURE Equal(k1, k2: Elem.T): BOOLEAN;
Equal may be declared with a parameter mode of either VALUE or READONLY, but not VAR.
TYPE T = OBJECT head: Elem.T; tail: T END;
A List.T represents a linked list of items of type Elem.T.
None of the operations of this interface modify the head eld of an existing list element. Operations that may modify the tail eld of existing list elements are called destructive. By convention, their names end in D.
PROCEDURE Cons(READONLY head: Elem.T; tail: T): T; Equivalent to NEW(T, head := head, tail := tail).
PROCEDURE List1(READONLY e1: Elem.T): T;
Return a list containing the single element e1.
PROCEDURE List2(READONLY e1, e2: Elem.T): T;
Return a list containing the element sequence e1, e2.
PROCEDURE List3(READONLY e1, e2, e3: Elem.T): T;
Return a list containing the element sequence e1, e2, e3.
PROCEDURE FromArray(READONLY e: ARRAY OF Elem.T): T; Return a list containing the elements of e in order.
PROCEDURE Length(l: T): CARDINAL;
Return the number of elements of l.
PROCEDURE Nth(l: T; n: CARDINAL): Elem.T;
Return element n of list l. Element 0 is l.head, element 1 is l.tail.head, etc. Cause a checked runtime error if n >= Length(l).
PROCEDURE Member(l: T; READONLY e: Elem.T): BOOLEAN;
Return TRUE if some element of l is equal to e, else return FALSE. The comparison is performed by Elem.Equal.
PROCEDURE Append(l1: T; l2: T): T;
PROCEDURE AppendD(l1: T; l2: T): T;
Append two lists together, returning the new list. Append does this by making a copy of the cells of l1; AppendD modi es the tail eld in the last cell of l1.
PROCEDURE Reverse(l: T): T;
PROCEDURE ReverseD(l: T): T;
Return a list containing the elements of l in reverse order. Reverse copies the cells; ReverseD modi es the tail elds of the existing cells.
END List.
The standard instances are named AtomList, IntList, RefList, and TextList.
The generic interface ListSort extends the generic interface List with sorting operations.
GENERIC INTERFACE ListSort(Elem, ElemList); Where Elem.T is not an open array type, Elem contains
PROCEDURE Compare(e1, e2: Elem.T): [-1..1];
and ElemList equals List(Elem). Compare may be declared with any parameter mode, side-e ects.
must be a total order. It but must have no visible
TYPE T = ElemList.T;
PROCEDURE Sort(l: T; c := Elem.Compare): T;
PROCEDURE SortD(l: T; c := Elem.Compare): T;
Sort a list in ascending order using c to compare pairs of elements of l.
The implementation is time- and cons-e cient but not guaranteed to be stable.
Sort copies the cells; SortD modi es the tail elds of the existing cells.
END ListSort.
The standard instances are named AtomListSort, IntListSort, RefList-Sort, and TextListSort. AtomListSort and RefListSort are useful only if you supply a non-default comparison procedure.
Sx
An Sx.T is a symbolic expression represented as a recursive linked list structure, as in Lisp. This interface provides routines for reading and printing symbolic expressions, as well as some convenience procedures for manipulating them. The syntax of an Sx.T is as follows:
Sx = Char | Text | Int | Real | Longreal | Extended
| Atom | Boolean | « ( » List « ) ». List = {Sx}.
A Char is a Modula-3 character literal; the corresponding Sx.T is of type
REF CHAR.
A Text is a Modula-3 text literal. The corresponding Sx.T is a TEXT.
An Int is a Modula-3 integer literal, possibly preceded by a plus sign (+) or minus sign (-). The corresponding Sx.T is of type REF INTEGER.
A Real, Longreal, or Extended is a floating-decimal number parsed using the grammar for Float speci ed in the Lex interface. The corresponding Sx.T is of type REF REAL, REF LONGREAL or REF EXTENDED, depending on whether the letter introducing the exponent is ‘e’, ‘d’, or ‘x’. If there is no exponent, the result will be of type REF REAL.
An Atom is either (1) a Modula-3 identi er, or (2) a non-empty sequence of characters from the set
! #$%&*+-./:<=>?@[]^_{}~
or (3) a sequence of characters and escape sequences surrounded by vertical bars (|s). The escape sequences are the same as those allowed in Modula-3 text literals, with the addition of \| to allow an atom to contain |. In all three cases, the corresponding Sx.T is an Atom.T.
For example, the following are valid atoms:
A Boolean is either TRUE or FALSE; the corresponding Sx.T is of type Atom.T; in other words, this is not a distinct type.
The Sx.T corresponding to a List is a RefList.T containing the items of the list in order.
The tokens of an Sx.T can be separated by arbitrary sequences of blanks, tabs, newlines, carriage returns, form feeds, and vertical tabs, which are ignored. (These are the same whitespace characters that are ignored between tokens of a Modula-3 program.) They can also be separated by comments, which begin with a semicolon and end with newline.
The syntax of tokens can be extended with the SetReadMacro procedure.
INTERFACE Sx;
IMPORT Atom, Rd, RefList, Thread, Wr;
TYPE T = REFANY;
EXCEPTION
ReadError(TEXT);
PrintError(TEXT);
PROCEDURE FromChar(c: CHAR): REF CHAR;
Return a Char with value c.
PROCEDURE FromInt(i: INTEGER): REF INTEGER;
Return an Int with value i.
PROCEDURE FromReal(r: REAL): REF REAL;
Return a Real with value r.
PROCEDURE FromLongReal(r: LONGREAL): REF LONGREAL; Return a Longreal with value r.
PROCEDURE FromExtended(r: EXTENDED): REF EXTENDED; Return an Extended with value r.
PROCEDURE FromBool(b: BOOLEAN): Atom.T;
Return a Boolean. If b is TRUE, return Sx.True. Otherwise, return Sx.False.
The From… procedures do not necessarily perform an allocation: if the same value is passed to two calls, the same reference may be returned. As a consequence, clients should not modify the referent of a reference returned by any of these procedures.
Each REF CHAR, REF INTEGER, REF REAL, REF LONGREAL, REF EXTENDED, TEXT, or Atom.T, no matter how constructed, is an Sx.T.
VAR (*CONST*) True, False: Atom.T;
True = Atom.FromText(« TRUE »), False = Atom.FromText(« FALSE »).
PROCEDURE Read(rd: Rd.T; syntax: Syntax := NIL): T RAISES {ReadError, Rd.EndOfFile, Thread.Alerted};
Read and return a symbolic expression from rd, ignoring whitespace and comments. If syntax is NIL, use the syntax described above; otherwise use any read macros that have been registered in syntax.
PROCEDURE ReadDelimitedList(
rd: Rd.T; delim : CHAR; syntax: Syntax := NIL): RefList.T
RAISES {ReadError, Thread.Alerted};
Repeatedly read symbolic expressions from rd, ignoring whitespace and comments, until the next character is delim; consume the delimiter and return the list of symbolic expressions that were read. Raise ReadError if there is a syntax error, including unexpected end of le.
PROCEDURE Print(
wr: Wr.T;
sx: T;
maxDepth: CARDINAL := LAST(CARDINAL);
maxLength: CARDINAL := LAST(CARDINAL))
RAISES {PrintError, Wr.Failure, Thread.Alerted};
Print the symbolic expression sx on the writer wr, assuming the standard syntax.
Each sublist will contain no more than maxLength elements; extra elements are replaced by an ellipsis (three dots). Any sublist nested at a depth greater than maxDepth is also replaced by an ellipsis. Print inserts | around atoms if necessary to ensure that they are readable. Print does not insert line-breaks or indentation to produce a human-readable (\pretty-printed ») format for large symbolic expressions.
Print will raise PrintError if it tries to print something that is not \printable » (as de ned below). If a list contains an unprintable element that is beyond the limits established by maxDepth and maxLength, PrintError may or may not be raised.
1 Introduction
1.1 Naming conventions for types.
1.2 Concurrency.
1.3 Aliasing.
1.4 Exception parameters for abstract types.
1.5 Standard generic instances.
1.6 Sets and relations.
2 Standard interfaces
2.1 Text
2.2 Thread
2.3 Word
2.4 Real, LongReal, and Extended
2.5 RealFloat, LongRealFloat, and ExtendedFloat
2.6 FloatMode
2.7 Lex
2.8 Fmt
3 Data Structures
3.1 Sequence
3.2 Atom
3.3 List and ListSort
3.4 Sx
3.5 Table
3.6 SortedTable
3.7 Bundle
4 Algorithms
4.1 ArraySort
4.2 Random
4.3 Fingerprint
5 I/OStreams
5.1 IO
5.2 Wr
5.3 Rd
5.4 TextWr and TextRd
5.5 Stdio, FileWr, and FileRd
6 Operating System
6.1 Time
6.2 Date
6.3 Tick
6.4 OSError
6.5 File
6.6 Pipe
6.7 Terminal
6.8 RegularFile
6.9 Pathname
6.10 FS
6.11 Process
6.12 Params
6.13 Env
7 Runtime
7.1 WeakRef
7.2 RTType
7.3 RTAllocator
7.4 RTCollector
7.5 RTHeap
7.6 RTTypeFP
A Basic Data Types
References