this version was not only cleaner, but
also shorter. Each of Schorre’s opcodes turned out to be simply imple-mentable in one to three lines of Python, so it was a relatively painless
process. I had effectively implemented small-step semantics instead of a
big step. To the extent that one could
have arrived here directly, by following Schorre’s description immediately from the paper, the switchbacks
have been a waste of time. I found the
diversion useful, however, because
instead of needing to work out small-step semantics from scratch, or to
read and understand what Schorre
had written, the direction to take at
each step (as if I were following a well-blazed trail) was almost forced by the
data given.
By this time, I appear to have
reached a peak. In the distance, I can
see the other peaks that Schorre discussed, VALGOL I, VALGOL II, as well
as an entire chain of different peaks
that might be more attractive to modern sensibilities. But how can I be sure
(especially if the clouds have come in,
and in the absence of a summit book)
that I am standing where Schorre did
half a century ago? This is the first time
I might actually need to use some intellect, and luckily for me it is known
that self-reproducing systems are
fixed points, and bootstrap processes
should therefore converge. Little need
for intellect then: you merely need to
confirm that running Schorre’s program in Figure 1 through a program
for the machine given in figures 2–4 reproduces12 itself. In fact, if you follow
a similar set of switchbacks to mine,
you will find that all of the possibilities
converge: not only does META II via
META II reproduce itself, but Python
via Python (as noted supra) reproduces
itself, and the two cross terms check as
well: META II via Python produces the
same output as META II via META II,
and Python via META II is identical to
Python via Python.
Note well the importance of self-
reproduction here. It is not difficult to
find self-referential systems: We may
take the 1839 Jacquard-woven por-
trait depicting inventor Joseph Ma-
rie Jacquard seated at his workbench
with a bunch of punched cards, or the
fictional Baron Münchhausen pull-
ing himself up by his pigtail (rather
than by his bootstraps; having needed
to lift his horse as well as himself,
bootstraps were never an option—he
sought a greatest rather than a least
fixed point) as entertaining examples,
but META II is a useful example of
self-reference: it derives almost all
of its power, both in ease of propaga-
tion and in ease of extension, from
being self-applicable: from being the
square-root of a compiler.
What has this exercise accomplished? It has resulted in a self-reproducing system, executing both
on the original META II VM (working
from the original listing) and on Python or another modern language.
Obviously, I could use the same process I followed to bootstrap from the
Python to the META II machine not
only to port to yet another underlying technology, but also to become
self-hosting. Less obviously, the basic problem I have solved is to translate (in a “nice” manner) one Kleene
Algebra (consisting of sequences,
alternations, and repetitions) to another, which is a pattern that, if not
ubiquitous in computing, is certainly
common anytime we deal with something that has more structure than a
linear “shopping list” of data. Compare Thompson’s NFA (
nondeterministic finite automaton) construction11
in which a search problem is solved
by parsing a specification that is then
executed on a virtual (
nondeterministic) machine, with the twist that the
nondeterministic virtual code has
been further compiled into actual deterministic machine code.
Finally, remember that META II
lends itself well to this kind of exer-
cise precisely because it was designed
to be bootstrapped. As Schorre says in
his introduction: “META II is not in-
tended as a standard language which
everyone will use to write compilers.
Rather, it is an example of a simple
working language which can give one
a good start in designing a compiler-
writing compiler suited to his own
needs. Indeed, the META II compiler
is written in its own language, thus
lending itself to modification.”
I hope the exercise of implement-
ing your own META II will have not
only the short-term benefit of provid-
ing an easily modifiable “workbench”
with which to solve your own prob-
lems better, but also a longer-term
benefit, in that to the extent you can
arrange for functionality to be easily
bootstrappable, you can help mitigate
the “perpetual palimpsest” of infor-
mation technology, in which the para-
dox of bitrot means many artifacts ef-
fectively have a shorter half-life than
even oral history.
After all, barbarians may be perfectly adapted to their environment, but to
be part of a civilization is to be aware of
how other people, in other places and
times, have done things, and hence
to know how much of what one does
oneself is essential and how much
accidental. More specifically, barbarians must learn from their own mistakes; civilized people have the luxury
of learning from other people’s mistakes. Very specifically, for engineers
faced with ephemeral requirements,
it is often helpful to avoid thinking of
the code base at hand as a thing in itself, and instead consider it only a particular instantiation of the classes of
related possible programs.
References
1. Backhouse, R. Regular algebra applied to
language problems. Journal of Logic and Algebraic
Programming 66 (2006); http://www.cs.nott.
ac.uk/~rcb/MPC/RegAlgLangProblems.ps.gz.
2. Brooker, R.A., MacCallam, I.R., Morris, D. and Rohl, J.S.
The compiler compiler. Annual Review in Automatic
Programming 3 (1963), 229¬275.
3. Brooks, F.P. The Mythical Man-Month. Addison Wesley, 1975.
4. Burstall, R.M. Proving properties of programs by
structural induction. Computer Journal 12, 1 (1969),
41–48.
5. Hehner, E.C.R. A practical theory of programming. Texts
and Monographs in Computer Science. Springer, 1993.
6. Johnson, S. C. Yacc: Yet another compiler-compiler;
https://www.cs.utexas.edu/users/novak/yaccpaper.htm.
7. Landin, P. J. The next 700 programming languages.
Commun. ACM 9, 3 (Mar. 1966), 157–¬¬166; http://doi.
acm.org/10.1145/365230.365257.
8. Moore, C.H. Programming a problem-oriented-
language, 1970; http://www.colorforth.com/POL.htm.
9. Richards, M. The MCPL Programming Manual and
User Guide. (2007) 58–63; http://www.cl.cam.
ac.uk/~mr10/mcplman.pdf
10. Schorre, D.V. ME TA II: A syntax-oriented compiler
writing language. In Proceedings of the 19th ACM
National Conference (1964), 41.301–41.3011; http://
doi.acm.org/10.1145/800257.808896.
11. Thompson, K. Programming techniques: Regular
expression search algorithm. Commun. ACM
11, 6 (June 1968), 419–422; http://doi.acm.
org/10.1145/363347.363387.
12. Thompson, K. Reflections on trusting trust. Commun.
ACM 27, 8 (Aug. 1984), 761–763; http://doi.acm.
org/10.1145/358198.358210.
13. von Neumann, J., Goldstine, H. H. Planning and Coding
of Problems for an Electronic Computing Instrument.
Institute for Advanced Study, Princeton, NJ, 1947.
14. Whitehead, A.N. An Introduction to Mathematics.
Henry Holt and Company, New York, NY, 1911.
Dave Long divides his time between developing equine
area network sensor systems as an application of current
technology to the problem of training horses for an old
mounted game, and simply enjoying playing it.
Copyright held by author.
Publication rights licensed to ACM. $15.00.