incur widely varying latencies) wrote
the compiler-compiler2 (of which
Johnson’s later, more famous one was
“yet another” 6) to attack this problem
in the early 1960s. According to Doug
McIlroy, Christopher Strachey’s GPM
(general-purpose macrogenerator—
a macroexpander of the same era)
was only 250 machine instructions,
yet it was sufficient to enable Martin
Richards’s BCPL (Basic Combined
Programming Language) implementation, later inspiring Ken Thompson
to bootstrap C via B, eventually leading to the self-hosting native-code-generating tool chains we now take
for granted.
A horse can pull more than a man,
but by exploiting leverage, Archimedes can, with patience, move what
Secretariat could not. META II is a
fine example of a field-improvised
lever: one can see how the beam has
been roughly attached to the fulcrum
and feel how the entire structure may
be springier than one would like, but
in the end, no matter how unpolished, it serves to get the job done
with a minimum of fuss.
Why Study META II?
1. There is not much to examine.
2. There is not much to examine because its parts are simply defined.
3.It enables significant consequences.
I will not go into detail, as nearly all
of the interest in this exercise comes
from doing it yourself. Programming
(when not constrained, as it often is
in our vocation, by economic con-
cerns) is not a spectator sport. Donald
Knuth, who says a simple one-pass
assembler should be an afternoon’s
finger exercise, might wish to make
some additional plans to fill his week-
end; it might take closer to four or five
evenings if you must first refresh dim
memories of a university compiler
course. Instead, I will describe the gen-
eral route of my ascent and why I am
confident I arrived at the same sum-
mit that Schorre described well before
my birth. By following Schorre’s text,
possibly aided by mine, you should
also find climbing this peak to be an
easy and enjoyable ascent. (An alter-
native for the hardcore: following the
Feynman method, ask yourself one
question: What is the square root of
a compiler?, then head up the moun-
tain without a guide.)
On first reading, Schorre’s text may
seem horribly naive. We have the ben-
efit of a half-century of experience and
a different vocabulary. However, just
as it is often amazing how much our
fathers seem to have learned in the
time between when we turned 14 and
when we turned 21, it becomes easy to
admire what Schorre accomplished as
we follow in his footsteps.
Digression: In examining medieval texts on horses, it is very clear
that while equitation has changed
very little in the intervening centuries, veterinary science has made
giant strides. With this distinction
between art and technique in mind—
and being thankful that Schorre’s
text is, albeit in a typewriter font, neither in medieval French nor, worse,
handwritten Fraktur—we can take
advantage of hindsight to separate
the informatics from the technical artifacts of having run on an IBM 1401
(end of digression).
Here is a smattering of the more
striking passages to be found:
˲ “Although sequences can be defined recursively, it is more convenient
and efficient to have a special operator for this purpose.” With hindsight,
we smile and nod as we recognize the
Kleene star (cf. the “Thompson construction” infra).
˲“These assemblers all have the
same format, which is shown as:
LABEL CODE ADDRESS
1- - 6 8- - 10 12- - 70.”
Having grown up after the popular-
ity of fixed column formats, I was intro-
duced to the concept that other people
might compute in other ways during
high school at a summer job: upon at-
tempting to write a PL/I “hello world”
under CMS, I had to bring in older and
wiser help who shook their heads,
stroked their beards, and gravely in-
formed me all that needed to be done
was to shift my code right one or two
spaces, so it would no longer start in what
was obviously the “comment” column.
˲“Repeated executions, whether
recursive or externally initiated, result
in a continued sequence of generated
labels. Thus all syntax equations con-
tribute to the one sequence.” In the
modern style, or even in the late 1960s
if you were Rod Burstall (his Cartesian
META II is
a fine example
of a field-improvised
lever: one can see
how the beam
has been roughly
attached to
the fulcrum
and feel how
the entire structure
may be springier
than one would like,
but in the end,
it serves to get
the job done with
a minimum of fuss.