could trivially express META II’s sequential composition in Python as short-circuit conjunction (and) with identity (True), the Python-generating META II grammar grew to 33 lines instead of 30. Now I needed to implement the functionality of the META II VM in Python. The advantage was that by generating Python code, I could implement each piece using a full high-level language, essentially a form of “big step” semantics. This consisted of approximately 85 lines of code, developed largely by the mindless method of iteratively rerunning the program and implementing each operation as execution reached the point where it became necessary. Debugging the null program is not to everyone’s taste, but as A.N. Whitehead remarked: “Civilization advances by extending the number of important operations which we can perform without thinking about them. Operations of thought are like cavalry charges in a battle—they are strictly limited in number, they require fresh horses, and must only be made at decisive moments.” 14

At this point, I was able to use the Python-generating META II to regenerate itself. This was still a good deal laterally removed from the direct route to the summit, but it gave me confidence that I was heading in the correct direction, and perhaps more importantly, I have far more frequent occasion to use generated Python code than code generated for Schorre’s META II VM.

Most importantly, I now had a good idea which data structures were necessary and how they fit together. (The vocabulary of programming changes as frequently as hemlines rise and fall, but the importance of structured data remains constant; Frederick P. Brooks said, in the language of his times, “Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.” 3, and before him, John von Neumann not only delineated control flow, but also meticulously tracked representation changes, in his 1947 flow diagrams13.)

With this structure, it was obvious
how to take Schorre’s list of opcodes
for his VM and create a Python ver-
sion. Having gained some experience,
Note that you can easily cut corners
on the lexical analysis. Schorre notes,
“In ALGOL, strings are surrounded by
opening and closing quotation marks,
making it possible to have quotes
within a string. The single quotation
mark on the keypunch is unique, im-
posing the restriction that a string in
quotes can contain no other quotation
marks.” Therefore, a single bit’s worth
of parity suffices to determine if any
given nonquote character is inside or
outside of a string.

Schorre was even more frugal when it came to numeric literals: “The definition of number has been radically changed. The reason for this is to cut down on the space required by the machine subroutine which recognizes numbers.” Compare Schorre’s decisions with those taken in Chuck Moore’s “Programming a Problem-Oriented-Language” 8 for an example of how much thought our forebears were prepared to put into their literal formats when they had to be implemented on these, by current standards, minuscule machines. (Such frugality reminds one of the Romans, who supposedly, during the negotiations to end the first Punic war, multiplexed a single set of silverware among everyone scheduled to host the Carthaginian delegation.)

The syntax analysis can also profitably cut corners. In trying to arrive at a system that can process grammatical input, you do not actually need the full machinery to analyze the grammar from which you start. In fact, if you are willing to ignore a little junk, the grammar in Figure 5 can be parsed as an expression entirely via precedence climbing, with “.,”, “=”, and “/” being the binary operators and “$” and “.OUT” being unary.

All of these cases are good examples
of a general principle when bootstrap-
ping: because you are initially not cre-
ating the cathedral, but merely putting
up ephemeral scaffolding, you can save
a good deal of effort by doing the un-
avoidable work (while still at the lower
level, where everything is relatively
difficult) in a quick and dirty manner,
allowing you to do the desired work
later in the proper manner (presum-
ably much more easily, once you have
a system operating at the higher level).
Schorre’s paper takes two more steps
in this manner, moving from META
II to VALGOL I to VALGOL II all in the
span of a few pages.

Another reason I took this route, rather than Schorre’s direct ascent, is because I had the luxury (much like discovering a fixed line left in place by a previous expedition) of having the skeleton of a precedence-climb-ing parser left over from a previous project; hence, parsing Schorre’s expressions was simply a matter of changing the operator tables. In this case, my luck was due to having been inspired by Martin Richard’s simple parsers9; Richards was a pioneer in the technique of porting and distribution via virtual machine, and his expression parsers are often under a dozen lines each; mine was left over from a reimplementation in sed( 1), and so (having eschewed integer arithmetic) is comparatively bloated: a score of lines.

At this point, I have climbed a bit and can look down with some satisfaction at the valley below, but the switchback means I have moved a good deal sideways from the original line of ascent. I am parsing Schorre’s original file and generating code, but the code is for his VM (virtual machine), which I have not yet rewritten. Again, rather than aiming directly for the summit, I took another switchback. In this case, it was to rewrite Schorre’s grammar to generate Python code rather than META II. This is another invaluable property of good intermediate positions: I have not yet properly reconstituted Schorre’s system, but there is enough of the machinery in place to use it as intended, as a seed that can be unfolded in different ways to solve different sorts of compilation problems.

Sure enough, Schorre’s system was flexible enough to generate code in a language that would not even have been started until a quarter century later. Because of additional .LABELs for the import boilerplate, and an expansion of EX2 to EX2 and EX25 so I