Communications of the ACM

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.