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