(which itself refers to Schorre, D.V. "META II: A Syntax-Oriented
Compiler Writing Language". Proc. 19'th Nat'l. Conf. of the ACM
(Aug. 1964) [1])
According to Alan Kay, META II ran on an 8k 1401[0].
I was able to bootstrap it using the same technique as for your
quasiquote DSL, composing the following two steps:
- parse (list of tokens -> tree), unfolding with an operator
precedence parser:
binary ops: ., = / (none right-associative)
unary ops: $ .OUT
- codegen (tree -> list of characters) via a bottom-fold
(plus a one-off kludge to handle the .SYNTAX progname ... .END
wrapping)
In other words, the same basic computation as factorial, just with a
few more fiddly details...
Conjecture: given general mixfix ops, can any well-formed LL(1) text
be processed by a precedence-climbing parser? (False; exercise: find
the counterexample)
With Schorre's META II VM also coded, his original syntax-directed
translator[1] self-reproduces.
Furthermore, with a slightly modified grammar spec[2], META II can
produce a python translator from META II code, self-reproduce the
python translator, then reproduce a META II translator from the
original grammar.
Note that Schorre had tight memory limits, and hence META II normally
streams all data (would aggressive deforestation be "clearcutting"?),
reading input a card at a time and punching output similarly. Today,
we have scratch space to burn; given a .EDIT that could (a la sed)
prepend material to the previous production as well as the
existing .OUT which simply appends, one could simplify the grammar
and avoid gratuitous use of monoid identities ('True' and '' for
juxtaposition and output). (cf TREE-META)
Anyhow, the pleasant result that LL parsers are quickly implementable
from simple operator precedence seems to give a relatively smooth
bootstrap path:
- hex loader
- symbol table & stack (roughly a minimal FORTH[-1])
- operator precedence parser (alternatively, ignore precedence but
support juxtaposed literals to get a minimal APL)
- meta-ii style translator (should handle a minimal PASCAL/MODULA/
OBERON or K&R C; cf VALGOL,tcc)
- ...
-Dave
[-1] it's not exactly bare metal, and probably much more complicated
than a forth dictionary, but it might be a neat hack to cheat on a
laptop by using the existing dynamic linker (dlopen/dlsym or
equivalent) for this step...
[0] which was a six-bit machine, explaining the use of '.,' instead
of ';', so should we say 6k for modern comparisons?
[1]
.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
[2]
.SYNTAX PROGRAM
OUT1 = '#1' .OUT('1,') /
'#2' .OUT('2,') /
'#' .OUT('0,') /
.STRING .OUT(# ',').,
OUTPUT = ('.OUT' .OUT('out(') '(' $ OUT1 ')' /
'.LABEL' .OUT('label(') OUT1 ) .OUT('"")').,
EX3 = .ID .OUT (# '()') /
.STRING .OUT('lit(' # ')') /
'.ID' .OUT('id()') /
'.NUMBER' .OUT('num()') /
'.STRING' .OUT('string()') /
'(' .OUT('(') EX1 ')' .OUT(')') /
'.EMPTY' .OUT('True') /
'$' .OUT('loop(lambda:(') EX3 .OUT('))').,
EX25 = (EX3 / OUTPUT) .OUT('and').,
EX2 = EX25 $ EX25 .OUT('True').,
EX1 = EX2 $('/' .OUT('or') EX2 ).,
ST = .ID .OUT(# '=lambda:gnstack(lambda:(') '=' EX1 '.,' .OUT('))') .,
PROGRAM = .LABEL 'from mplib import *'
.LABEL 'if True:'
'.SYNTAX' .ID .OUT ('main=lambda:' # '()')
$ ST '.END' .OUT('if __name__=="__main__": main()') .,
.END
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
