Copyright © 1972,2004 P.J. Brown, R.D. Eager
Permission is granted to copy and/or modify this document for private use only. Machine readable versions must not be placed on public web sites or FTP sites, or otherwise made generally accessible in an electronic form. Instead, please provide a link to the original document on the official ML/I web site.
This Edition has been rewritten in Texinfo, so that it can be published in both printed and machine readable form; this has necessitated some re-wording and re-ordering of the text.
There have also been one or two corrections of minor errors in the
previous edition, as well as a few clarifications. The text has been
modernised in places, to reflect current technology, and the Section on
MDREAD has been expanded.
Before the extensions to LOWL needed by ML/I are described, it is necessary to explain its hash table, since this affects several of the extensions.
Clearly, ML/I would be very slow if it compared each atom of scanned
text with all possible construction names. Hence a hashing algorithm is
This involves a hash table of (typically) 32 pointers, each of
which is the head of a chain of construction names. A zero pointer means
the end of a chain. The implementor chooses a hashing algorithm
which assigns every possible construction name to a hash chain.
Every time a new construction is defined, ML/I calls
find out which hash chain it should be added to. However, the names of
the operation macros are built into ML/I in its fixed tables, and the
initial state of the hash table and the chains connecting the built-in
macros need to be supplied as constants. There are two statements
THASH) to generate these constants but it is
usually very hard to write macros to work out hash chains, and, since
there are so few of them, it is often best done by hand.
The size of the hash table need not be 32 pointers. For a small machine it can be reduced to 16 pointers and for a large one increased to 64 pointers or even 128 (a power of two is not essential, but is usually more efficient in terms of the actual hashing algorithm).
The following diagram shows the hash chains where
MCINS are both on chain 1, and
MCLENG is on chain 3.
+-----------+ Chain 0 | 0 | +-----------+ +-----+ +-----+ Chain 1 | ----+----------------->| --+---->| 0 | +-----------+ +-----+ +-----+ Chain 2 | 0 | M M +-----------+ +-----+ C C Chain 3 | ----+---->| 0 | D I +-----------+ +-----+ E N | | M F S . . C . . L . . E . . N . . G . .
When ML/I is running, it may actually create several extra hash tables, but the implementor need not be concerned with these.
ML/I requires the following extensions to LOWL.
LHV is a subsidiary macro of
OF which gives the size of
the hash table. Thus if the hash table consisted of 32 pointers,
LHV would equal 32 times
Two extra names for representing character constants are used. These are
SLREP, and should each be assigned a unique
code that cannot occur naturally in the source text.
MCALTER operation macro in ML/I has the effect of changing
table items. In any multi-user application where the tables are shared,
or in any implementation where these tables are conveniently kept in
MCALTER should be forbidden. This is easily
done by making the
(see Statements for defining table items)
leave it off the hash chains.
The following additional statements are needed:
RL table label,OF
defines an item containing the value of the relative offset of the given
table label. The second, subsidiary argument gives the value of the
offset. For an assembler where the character
. represented the
location counter, then
might be represented as
PIG - .
On less powerful assemblers it is often necessary to make use of the subsidiary argument.
defines an item containing the hash chain link for the macro named within the quote signs.
defines the set of table items representing the starts of all hash
THASH only occurs once, and this is after all the
means a table item consisting of a unique numerical marker. This should be the highest integer acceptable to the object machine.
This additional statement is needed for ML/I:
|inclusive "or" A with literal value
There exists a special routine called the linkroutine. Its name is
STKARG, and it is essentially a recursive subroutine. However,
the MI-logic of ML/I takes care of all problems connected with recursion
and the task of the implementor is therefore very simple. The
linkroutine is declared by the statement:
This should be mapped exactly as a
SUBR with no parameter except
that the return link should be placed in the variable
not in a place designated by the implementor (
automatically stacked and unstacked in recursive situations). The return
from the linkroutine is written simply:
which should be mapped into a jump to the return address contained in
STKARG is called by an ordinary
GOSUB statement. However
the linkroutine is best treated as part of the main logic, rather than
as a subroutine, as there are branches between the linkroutine and the
main logic. If subroutine return addresses are being kept on a stack,
the return link to the linkroutine should not be placed on the
Basically ML/I requires three input/output streams:
If the implementation of ML/I is intended for production work, however,
these facilities may need to be supplemented by some extra options, for
example listings of the source text and/or output text. Being
implementation dependent, these options need to be provided by the
MD-logic. Sometimes an operating system may automatically provide all
the required options, but more often it has proved necessary for the
implementor to program some of them into the MD-logic routines. Options
that are open to the user can either be provided by the S-variables from
S10 upwards (with initial values reflecting the default options)
or by parameters to the command that invokes ML/I. A combination of both
is ideal; S-variables are initially set to default options, but
parameters can cause these to be changed; further dynamic changes can be
made by assignments to the S-variables during a process.
The following list shows a fairly comprehensive collection of options that might be provided by means of S-variables. Ideally all the options should be dynamically changeable. The implementor is certainly not expected to follow this scheme exactly, but it gives a general guide to what may be provided.
S16are translated to characters with the code given by
S17, on input. Initially
S16could be -1, so no translations are performed. This allows characters to be input from devices that do not directly support them.
The initialisation code should perform the following actions:
S1is last) and be immediately followed by a numerical field containing the number of S-variables. The variable
SVARPTshould be set to point at this number. There must be at least nine S-variables.
S9should be initialised to zero and the remaining S-variables should be initialised to reflect default options. The following pictorial example shows how the S-variables might be set if there were eleven of them, and
S11both had an initial value of one.
1 1 0 0 0 0 0 0 0 0 0 SVARPT ----> 11
MDQUIT subroutine should perform the functions described in the
MDCONV is a subroutine with a single exit and no parameter. It
should take the value of the variable
MEVAL and convert it to a
character string representation. This representation should be a string
of decimal digits, preceded by a minus sign if
MEVAL is negative,
and containing no redundant leading zeros. The string should be built up
in some storage locations specially reserved for the purpose.
IDPT should be set to point at the first character and
IDLEN should be set as the length of the string (i.e. as
LCH multiplied by the number of characters in the string). The
original value of
MEVAL need not be preserved.
MDFIND is the hashing algorithm, and is a subroutine with one
exit and no parameter. The atom to be hashed is described by
(which points at the first character),
SPT (which points at the
last character) and
IDLEN (the number of characters in the atom,
MDFIND should set the variable
HTABPT to the head of the hash chain to which the atom belongs.
HASHPT points at the hash table, and therefore
HTABPT should be assigned a value of the form
where N, the hash chain number, is a
LNM and satisfies the relation:
0 <= N < LHV
A simple hashing algorithm, though not the best one, is to add together
IDLEN and the two characters pointed at by
SPT, multiply by
LNM and "and" out redundant high-order
bits (this is why it is useful if
LHV is a power of two).
HTABPT is then set to the resultant value, with
added to it.
MDOP is a subroutine to perform multiplication and division. It
has a single exit label and no parameter. It should test the variable
OPSW; if it is one it should multiply
and place the result in
OPSW is not one it
MEVAL and place the result in
MEVAL. In the latter case there should be a prior test to see if
the divisor (
MEVAL) is zero, and if so a branch should be made to
ERLOVF in the MI-logic. Other cases of overflow are
The division operator should give an integer result. The rules for integer division are given in the ML/I User's Manual; check them carefully, as they may not be quite what is normally expected.
MDREAD is the input subroutine. It has two exits and no
Exit 1 should be used when the source text has become exhausted (if the last line of input received has not been terminated with a newline, the MI-logic will automatically add a newline).
Otherwise the next character of the source text should be read and placed in the C register, and exit 2 should be used. At the end of each line, a newline character should be supplied. There are various possibilities depending on the operating system; for example:
NLREP(it is very likely that the code for line feed will be the same as for
NLREP; as in b), this may be a null conversion.
If an illegal character is found, an error message can be produced by
calling the MI-logic subroutine
ERSIC; after this, the error
character (see Chapter 6 of the ML/I User's Manual) should be
placed in C.
MDREAD subroutine is responsible for providing the input
options described in Input controls, and in particular for
switching input streams if this facility is to be made available.
MDOUCH is the subroutine which outputs all the output text from
ML/I. It has one exit and no parameter. Text is output character by
character, and the character to be output is in the C register. The
character set is exactly that allowed by the
it therefore includes "newline" but not the imaginary characters
STOPCD. Lines of output may be
arbitrarily long, and
MDOUCH is responsible for dealing with any
overflow. It is also responsible for providing the output options
described in Output controls, in particular multiple copies of the
output or suppression of output.
MDERCH is exactly similar to
MDOUCH except that it uses
the messages stream rather than the results stream.
For each implementation, there must be an Appendix to the ML/I User's Manual which describes the special features of that implementation. Each such Appendix is designated by one or more letters, and the writer should request a unique letter combination via the Contact link on the official ML/I web site.
Most of the details given in an Appendix are dependent on the way that the MD-logic is coded; there are, however, a few details that are fixed in the LOWL version of the MI-logic of ML/I.
There follows a sketch of how an Appendix might be written. It is useful
if the section numbering remains constant, with any additional sections
appearing at the end if at all possible. In this sketch, the identifying
letters for the Appendix are XXX.
This implementation of ML/I contains all the features described in the ML/I User's Manual, Sixth Edition.
Describes how to use ML/I, e.g. command format and parameters, how I/O is controlled, and which options are available. Examples of typical commands are useful here.
Enumerates the characters that
MDREAD accepts. Describes
any particular arrangements concerned with specific devices.
This Section is referenced in several places in Chapter 6 of the ML/I User's Manual. It should describe the debugging file (messages stream), any special messages peculiar to the implementation, the action on illegal input characters and what the error character is (if it exists). It should also contain the next paragraph.
With reference to Chapter 6 (of the ML/I User's Manual), the number 2N (the maximum number of characters in a piece of text inserted into an error message without being truncated) is 60. At the end of each process, a message giving processing statistics is sent to the debugging file.
The initial environment contains ten permanent variables, all set to the value zero. All integers in, or derived from, macro expressions should be less than (fill in as appropriate) in magnitude. Overflow is not (always) detected, except in the case of division by zero, and its effect is undefined (alter if necessary).
The following are the layout keywords for this implementation:
|meaning a space.
|meaning a newline.
|meaning a tab.
|meaning the imaginary startline character.
|meaning a sequence of one or more spaces.
States number of S-variables and gives a table showing the usage
S10 upwards and their initial values. Most of the S-variables
will already have been mentioned in previous Sections, particularly
A set of test programs for checking an implementation of ML/I is available. These test programs are issued in the same format as other LOWL material. They are accompanied by sets of sample output from the test programs, as run on an existing implementation of ML/I. In general the output from the test programs should be easy to check at a glance since each line should be of form:
string1 SB string2
SB means "should be" and it is therefore an error if
string1 differs from string2. A few of the test programs
check error detection, and the error messages produced by these require
more careful checking.
Line numbers in messages may differ from those in the supplied sample
results, due to additional macro calls used (for example) to select input
or output streams before invoking the actual test. It may be possible to
S2 to correct for this, and this will certainly make
checking easier if it can be done.
Two of the tests programs, NAMES and ESCALATE, are designed for
preliminary testing of a new implementation of ML/I. A common fault is a
bug in the mapping macros in the LOWL extensions for defining table
items, particularly the
THASH statements. The
NAMES test, which should be the first test fed to a new implementation,
is designed to show up such faults. It does this by generating an error
message which should include all the built-in macros (except
which are tested separately) and their delimiters.
After the NAMES test is working, the ESCALATE test should be applied. This, as its name implies, tests constructions of ever increasing complexity. It covers most of the features of ML/I, and hence when an implementation has successfully run it, that implementation can be said to be in reasonable shape and ready to face the buffeting that the other ML/I tests should give it.
The remaining tests are called ALTER, ERRORS, MACROTIME, OVERFLOW, OVERRIDE, S, SKIPINS and STRUCTURES. These tests should provide a comprehensive check, though no test programs can, of course, be completely foolproof. The names of the tests indicate the feature(s) they concentrate on.
These tests should be supplemented by a set of tests to check all the
implementation-dependent features. In addition, these
implementation-dependent tests should check the
keyword; this is not included in the main tests since not all
implementations support tabs.
The next page contains a table which may be of use in monitoring the tests of the various versions of an implementation.
This is an example of a test schedule sheet, suitable for recording tests on an implementation of ML/I.
+----------------------------------------------------------+ | | Version name or date of implementation | | +-------------------------------------------+ | | | | | | | | | | | | | | Test | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +==============+===+===+===+===+===+===+===+===+===+===+===+ | NAMES | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | ESCALATE | | | | | | | | | | | | +==============+===+===+===+===+===+===+===+===+===+===+===+ | ALTER | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | ERRORS | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | MACROTIME | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | OVERFLOW | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | OVERRIDE | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | S | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | SKIPINS | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | STRUCTURES | | | | | | | | | | | | +==============+===+===+===+===+===+===+===+===+===+===+===+ | Impl. dep. 1 | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | Impl. dep. 2 | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+ | Impl. dep. 3 | | | | | | | | | | | | +--------------+---+---+---+---+---+---+---+---+---+---+---+
Each time ML/I is changed, the new version name/date is entered into a fresh column and a tick placed against those tests that have successfully run. All the tests except NAMES and ESCALATE (and ALTER, if an implementation does not support MCALTER) should be applied to every version.