ML/I Macroprocessor

ML/I is a general-purpose, stand-alone macroprocessor. Peter J. Brown created it at the University Mathematical Laboratory, Cambridge, and the first User’s Manual is dated July 1966. It reads any text and copies it to the output, replacing macro calls as it goes. A call can take almost any notation the user chooses. ML/I was also built as a tool for implementing software. Its logic was written in a machine-independent language, and ML/I was then used to translate that description into code for each new machine. The experiment was a success: in Brown’s best case, the PDP-7, the generated code was only about 3% less efficient in size and speed than hand-coded sections written to the same goal of compactness.

A note on this entry

The master list behind this encyclopedia has the same program twice: once as ML/I and once as ML/I Macroprocessor. They are the same program. The ML/I page covers its general history, its use today, a beginner’s session and the list of ports. This page covers how the macroprocessor works inside. It draws on Brown’s 1967 CACM paper, his 1968 dissertation, and the implementor documents that Bob Eager has republished on the official site, ml1.org.uk.

History & Origins

A research project with a practical goal

Brown’s dissertation, Macro processors and their use in implementing software, is dated March 1968. It thanks Maurice Wilkes, who supervised him in his first and third years, and David Barron, who supervised his second year, and it records funding from the Science Research Council. It has three parts:

The ML/I User’s Manual and the L-Map Implementor’s Manual were its two appendices. Brown wrote that the dissertation’s research was mainly “designing and implementing a macro processor … and in using it to generate versions of itself for several computers.”

What ML/I took from earlier systems

In Part II Brown is open about ML/I’s ancestry. Its basic idea of a macro, he writes, puts it in the family of GPM, TRAC and the 803 Macro-generator, and “of these ML/I has leaned most heavily on GPM.” Its skips generalise GPM’s literal brackets. Its macro-time statements are “a cross between the ideas of GPM and the PL/I Macro Processor.” The 1967 paper also discusses XPOP, Wilkes’s WISP and LIMP. These matched each input line against templates, while ML/I recognises a call by its name and then searches for the remaining delimiters.

Reception

According to the dissertation, more than sixty computer installations had asked about ML/I after the CACM paper appeared. They included computer manufacturers, industrial firms, universities and research establishments.

Design Philosophy

Delimiter structures: the one big idea

Brown named a single innovation as the feature by which ML/I “stands or falls”: the delimiter structure. Each macro has a name and a graph of possible successor delimiters, so one macro can accept many forms of call. In the 1967 paper’s example, an IF macro allows both IF a = b THEN c END and IF a = b THEN c ELSE d END, because THEN has two alternative successors, END and ELSE. A structure can also loop back on itself, which allows any number of arguments.

Brown also explained the trade-off. Template systems such as XPOP and LIMP were better when calls were written one to a line. ML/I was better when calls were nested inside each other or a macro had many different forms. Because ML/I does not depend on a particular notation, it can also be used for editing and symbol manipulation, not just for extending a programming language.

Small enough to sit beside other programs

The PDP-7 that ML/I was developed on had 8K 18-bit words. (The 1967 paper gives the other early machine as the I.C.T. Atlas 2; Cambridge’s Titan was the prototype of that machine.) Brown wrote that keeping ML/I small enough to run there was “one important factor” in its design: features were added only if they were “solid improvements” that could be implemented easily. He quoted T. C. O’Brien of Honig Associates, who saw a macro processor as “belonging in the ‘card reader’ or ‘printer’ category rather than as a preprocessor,” with several translators stacked “one behind the other, without the use of an intermediate file.” Brown wrote: “This is a view I fully support.”

Key Features

Constructions and the environment

The 1967 paper calls the things ML/I recognises constructions. There are four kinds:

All the constructions in force at a given moment make up the environment. Scanning text and expanding the calls in it is called evaluating the text. ML/I makes one pass, so a definition only affects the text that follows it. Arguments are evaluated when they are inserted, not when the call is scanned. The paper calls this call by name, and notes that it lets generated assembly code adapt to the context it lands in.

Macro-time variables

Permanent variables P1, P2, … are global. Each call of a user macro also gets its own temporary variables T1, T2, …, and ML/I initialises the first three:

• T1: the number of arguments
• T2: the number of macro calls performed so far. The value is unique to each call, so it is used to generate unique labels
• T3: the current depth of nesting of macro calls

The 1967 IF macro

The CACM paper’s main example generates PDP-7 assembly code. In the paper’s notation, : begins an insert and . ends it, ⟨ ⟩ are literal brackets, and operation macros end with a semicolon. Later versions end operation macros with a newline. Here is the definition as printed:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

MCDEF IF = THEN OPT ELSE END OR END ALL AS
⟨        LAC :A1             /Load first argument.
         SAD :A2.            /Skip if it differs from the second argument.
         SKP                 /Equal case: skip one instruction.
         JMP XX:T2.          /Unequal case: jump over inserted code.
         :A3.                /Inserted code.
MCGO L1 UNLESS :D3. = ELSE;  /Macro-time jump if else clause is absent.
         JMP YY:T2.          /Jump over else clause.
XX:T2.,  :A4.                /Insert else clause.
YY:T2.,  MCGO L2;            /Macro-time jump to end of replacement text.
:L1.XX:T2., :L2. ⟩;          /Placing of macro-time labels.

OPT ELSE END OR END ALL is the delimiter structure: after THEN, the call may continue with ELSE … END or end with END. :D3. inserts whichever third delimiter was actually used, so MCGO can test for it at macro time. The paper shows these two calls:

1
2
3
4
5
6
7

IF A = B THEN JMS SUB
END
IF PIG = DOG THEN LAC C
                  DAC D
ELSE LAC Y
     DAC Z
END

and the code they generate:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

     LAC A        /First call.
     SAD B
     SKP
     JMP XX1
     JMS SUB
XX1, LAC PIG      /Second call.
     SAD DOG
     SKP
     JMP XX2
     LAC C
     DAC D
     JMP YY2
XX2, LAC Y
     DAC Z
YY2,

The labels XX1, XX2 and YY2 come from T2.

Loops and nodes

A node such as N1 names a point in the structure that a later delimiter can loop back to. The paper’s INDEX macro uses one to accept a list of any length. It returns the position of the first later argument that matches its first argument:

1
2
3
4
5
6

MCDEF INDEX WITH (N1 OPT, N1 OR) ALL AS
⟨      MCSET T2 = 2;
:L2.   MCGO L1 IF :AT2. = :A1.;
       MCSET T2 = T2 + 1;
       MCGO L2;
:L1.   :T2. ⟩;

The paper then uses it to build a computed macro-time jump that depends on which delimiter appeared in a call: MCGO L INDEX (:D2., +, -, *, /);.

Inside the Macroprocessor

Two stacks and no lists

In Part II, Brown explains why ML/I does not use list processing. All dynamic storage comes from two stacks that grow towards each other from opposite ends of free memory, and character strings are stored contiguously. He argued that this was “much faster than list processing” on machines with block-move and block-compare instructions, at the cost of making ML/I “hard to extend in some directions”. He added: “the decision not to use list processing techniques in ML/I has not been regretted.”

How ML/I works (1971; the revised edition of 2004 credits P. J. Brown, R. C. Saunders and R. D. Eager) describes the layout in detail:

• FSTACK, the forwards stack, holds permanent information: global macro definitions, the permanent variables, and the source text currently being scanned, plus workspace for operation macros. When a new global definition is added, everything above it is shifted up to make room.
• BSTACK, the backwards stack, works as a pushdown list. It holds the context stacked at each call or insert, local definitions, local labels, and the state of any enclosing text while a nested construction is scanned. When a call finishes, BSTACK is reset to its state on entry, which is how local definitions disappear automatically.
• If the two stacks meet, the run is aborted.

The same document describes the logic as about 270 lines of declarations and about 2,170 lines of code in L, for version AIB of December 1970.

Hashing atoms

Brown measured the PDP-7 version and found that the most time-consuming activity was “the comparison of each atom of the scanned text with all possible macro names,” even with hashing. Construction names are kept on hash chains, separate for locals and globals. Each name is stored as a sequence of LIDs: a length followed by the characters of one atom. Brown reported that with a 64-entry hash table, each atom in an average job needed to be compared with only one or two names. He also warned against making the tables too large, because up to four could exist at once. The LOWL implementor’s supplement for ML/I suggests 32 chains as typical, 16 for a small machine, and 64 or 128 for a large one.

Local names and protected inserts

Because local definitions live on BSTACK, the scope of a definition follows the nesting of the text. Bob Eager’s hints page shows a case that surprises beginners: a macro defined inside replacement text does not apply to an argument inserted there.

1
2
3
4
5

MCINS %.
MCSKIP MT,<>
MCDEF TEST NL AS <MCDEF XXX AS YYY
%A1.>
TEST XXX

The output is XXX, not YYY. By default an insert is protected: inserted text is evaluated in the environment that was in force where the call was written. Declaring the insert as unprotected with MCINS U,%. makes it use the environment in force at the insert, and the output becomes YYY. (This example uses the modern conventions: % for inserts, <> for literal brackets and newline-terminated operation macros.)

Portability: Making ML/I Implement Itself

DLIMP and the L-map

Part III of the dissertation names its method DLIMP, short for Descriptive Language Implemented by Macro Processor. You design a language just rich enough to describe one piece of software, write the software in it, and then write macros that translate the language into each target. For ML/I, that language was L, and a translation was called an L-map. The machine-independent part of the program (the MI-logic) was mapped. The machine-dependent part (the MD-logic: input/output, character codes, start-up) was written by hand for each machine. Brown’s 1967 paper hoped that a new machine would take “about one man-month.”

Results reported in 1968

Brown measured each L-map. Inefficiency means how much bigger or slower the macro-generated code was than code a competent programmer would write by hand from the same L description, without tricks. On Titan and the PDP-7, ML/I ran at about two to three thousand macro calls a minute. A complete L-map of roughly two thousand L statements took about twenty minutes of computer time on either machine.

All these figures are Brown’s own estimates for the specific mappings listed. He stressed that a second L-map into the same language could turn out quite differently. His overall conclusion was that an L-map into an average assembly language took about six weeks. The whole job could be done “by one skilled person in two months”, with inefficiency ranging from almost nothing to 50% and averaging about 20%. L-maps into System/360 assembly language and Honeywell 200 EASYCODER were also started but not finished when he wrote.

LOWL: a simpler abstract machine

Implementors who did not already know ML/I well found L-maps hard. At Kent, Brown used ML/I to translate L into LOWL (“low-level L”), an assembly language for an abstract machine. The current implementor’s guide, Implementing software using the LOWL language, specifies three notional registers:

• A, the numerical accumulator
• B, the index register
• C, the character register

The three are never used at the same time, so one physical register can hold all of them. Here is the guide’s sample of LOWL:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

           NB      'Sample LOWL statements'
           LAV     SIZE,X
           CAL     6
           GOGR    BIG,2,X,X
           BUMP    PTR,OF(LCH)
           MESS    'Size is six or less'
   [BIG]   GOSUB   CHECK,236
           LAI     PTR,X
           FSTK
           LAV     NUPT,X
           AAV     SIZE
           STV     PTR,X

LOWL was designed to be “mappable by almost any macro processor, including a macro-assembler.” The mapping tool did not have to run on the target machine; the guide’s example names a hypothetical processor MACWILLING. A test program, LOWLTEST, exercises every statement in the LOWL kernel before the mapping macros are applied to the real program. The guide says the hand-written MD-logic is usually smaller than the MI-logic “by a factor of twenty or more.”

Brown’s Own Critique

Part II of the dissertation lists ML/I’s weaknesses. They show what Brown thought was worth fixing:

• Speed. Brown called slowness “the most obvious defect”, mainly because MCSET and MCGO were interpreted every time they ran. He also noted that slow applications could often be made “an order of magnitude” faster by avoiding the most expensive features.
• Line-oriented input. ML/I handled one-call-per-line text clumsily, a niche where LIMP and WISP did better. The later startline feature addressed this.
• No character variables. Text could only be remembered by defining a global macro, and an old definition could not be thrown away. Version CKA later added character variables.
• Layout characters. Users had to be careful with spaces and newlines. Brown also wrote that “it would have been better to use a newline rather than a semicolon as the standard closing delimiter for operation macros”. Version AIC made that change.

The official site notes that most of Eager’s later changes to the core logic were, without his knowing it at the time, ones already proposed in this critique.

Evolution

The core logic has changed little. Version identifiers have three letters: the source the build came from (A for L or LOWL, B for BCPL, C for C), then a major and a minor version. The version table runs from AGA through AIC–AIH and the AJB/BJB/CJB family to the CK series; AIB, the December 1970 logic described in How ML/I works, is not listed there. CKA added character variables, CKD added | and & in macro-time expressions, CKJ added all 256 character codes, and CKL let one punctuation character be treated as alphanumeric. CKM to CKP are portability fixes for Microsoft compilers, gcc, clang and 64-bit systems. The Sixth Edition of the User’s Manual describes CKP. The macOS (Intel) build page, added in 2020, lists its core version as CKQ, which is not yet in the version table.

The current manual documents operation macros including MCDEF/MCDEFG, MCINS/MCINSG, MCSKIP/MCSKIPG, MCWARN/MCWARNG, their MCNO… counterparts, MCSTOP/MCSTOPG, MCALTER, MCSET, MCGO, MCSUB, MCLENG, MCPVAR, MCCVAR and MCNOTE. The G suffix makes a definition global. Eager’s hints say the local form should almost always be used, because the global form costs significantly more processing.

A self-checking test suite

The official test suite has a format that suits a macroprocessor. Each test line produces some output and then SB (“should be”) followed by the expected value, so a correct run prints matching pairs. The macro-time test checks the CKD logical operators with lines like this:

1

%1&0.%0|1&15.%15|32&2.%3&7|1.%4&7.%31&5.%31&7&2|4.%1|4|2|8&7. SB 01234567

The reference output for a correct run is 01234567 SB 01234567.

Current Relevance

ML/I is a historical program that is still maintained. The official site distributes binaries and test suites for current systems, including macOS and Raspberry Pi Linux. It also hosts the L and LOWL sources of ML/I, LOWLTEST, both internals documents, and the complete dissertation. In June 2024 the site added documents on the use of ML/I in implementing the SAL systems programming language. There is no Docker image.

Why It Matters

ML/I is often remembered as a flexible macro processor. Its implementation history matters just as much. Brown did not just claim that a macroprocessor could carry software between machines; he did it, and he published the line counts, man-weeks, macro-call totals and efficiency losses. The PL/I result was a failure, and he published that too. LOWL took the same approach further, to an abstract machine simple enough for almost any macro-assembler to target. This is the same idea as the abstract machines and intermediate languages behind later portable software. The design that made this possible (two stacks, contiguous strings and hashed atoms) fitted in about three thousand words of 1960s memory, and it has needed few changes in the six decades since.