glorified left-fold (mine was about 66 lines of Python).

1. Hand-translate the META II productions to the machine language (211 lines of m2vm opcodes).

follow in Schorre’s footsteps directly,
using the traditional bootstrap:
0. Hand-code the META II ma-
chine—this is basically an assembler-
like virtual machine: in other words, a
product4), you might call this monad-
ic composition. In the days of small
memories and essentially linear card
decks, the flattened sequence was the
norm rather than the exception, and in
our times Rick Hehner’s bunches5 are
a good example of a case where flatten-
ing can make the formulae of “formal
methods” more easily manipulable
than normally nestable sets.

Note that it has taken only two pages for Schorre to describe what we need for META II. The remainder of the article focuses on a description of VALGOL, which might make a suitable destination for another day. Let us take a brief pause, however, to examine a couple of points:

˲ “The omission of statement labels from the VALGOL I and VALGOL II seems strange to most programmers. This was not done because of any difficulty in their implementation, but because of a dislike for statement labels on the part of the author. I have programmed for several years without using a single label, so I know they are superfluous from a practical, as well as from a theoretical, standpoint. Nevertheless it would be too much of a digression to try to justify this point here.” History agrees the digression would have been superfluous; indeed, now it seems strange that it then seemed strange. Tempora mutantur, nos et mutamur in illis (times change, and we change with them).

˲Finally, Schorre discusses the problem of backup vs. no backup, which is still a current topic, as the recent popularity of the parsing expression grammar (PEG) and other parsers will attest. In our times, however, we are not so interested in avoiding backup, but in avoiding the need to start at the beginning and process linearly until we reach the end. Luckily for compiler writers, whether or not a production can be matched by an empty string is a property that can be determined by divide and conquer... but it is one of the few1 that are tackled so simply.

The heart of the matter comes in figures 5 and 6 in the original article, “The META II Compiler Written in its Own Language” (Figure 1 in this article) and “Order List of the META II Machine” (figures 2 through 4 here). Now, it would certainly be possible to

Figure 1. The META II compiler written in its own language (Figure 5 from Schorre’s original paper).

.SYNTAX PROGRAM OUT1 = '* 1' .OUT('GN1') / '* 2' .OUT('GN2') /

'*' .OUT ('CI') / .STRING .OUT('CL ' *)., OUTPUT = ('.OUT' '('

OUT1 ')' / '.LABEL' .OUT ('LB') OUT1) .OUT('OUT')., EX3 = .ID .OUT ('CLL' *) / .STRING .OUT('TST' *) / '.ID' .OUT('ID') /

'.NUMBER' .OUT('NUM') /

'.STRING' .OUT('SR') / '(' EX1 ')' /

'.EMPTY' .OUT('SET') /

'$' .LABEL 1 EX3

.OUT ('BT ' 1) .OUT('SET')., EX2 = (EX3 .OUT('BF ' 1) / OUTPUT)

$(EX3 .OUT('BE') / OUTPUT)

.LABEL 1 ., EX1 = EX2 $('/' .OUT('BT' 1) EX2 )

.LABEL 1 ., ST = .ID .LABEL '=' EX1

'.,' .OUT('R')., PROGRAM = '.SYNTAX' .ID .OUT ('ADR' *)

ST '.END' .OUT ('END')., .END

Figure 2. Order list of the META II machine (Figure 6. 1 in Schorre’s original paper).

Machine Codes

TST STRING TEST After deleting initial blanks in the input string, compare it to the string
given as argument. If the comparison is met, delete the matched
portion from the input and set switch. If not met, reset switch.

ID IDEN TIFIER After deleting initial blanks in the input string, test if it begins with
an identifier; that is, a letter followed by a sequence of letters and/or
digits. If so, delete the identifier and set switch. If not, reset switch.

NUM NUMBER After deleting initial blanks in the input string, test if it begins with
a number. A number is a string of digits which may contain imbeded
periods, but may not begin or end with a period. Moreover, no two
periods may be next to one another. If a number is found, delete it
and set switch. If not, reset switch.

SR STRING After deleting initial blanks in the input string, test if it begins with a
string; that is, single quote followed by a sequence of any characters
other than a single quote followed by another single quote. If a string
is found, delete it and set switch. If not, reset switch.

CLL AAA CALL Enter the subroutine beginning in location AAA. If the top two terms
of the stack are blank, push the stack down by one cell. Otherwise,
push it down by three cells. Set a flag in the stack to indicate
whether it has been pushed by one or three cells. This flag and the
exit address go into the third cell. Clear the top two cells to blanks to
indicate they can accept addresses which may be generated within
the subroutine.