META II
| Designed by | Dewey Val Schorre |
|---|---|
| Appeared in | 1962 |
| Computational class | Pushdown automata |
| Reference implementation | META I |
| Influenced | TROL, Zaddy |
META II is a two-tiered metacompiler, notable for being the first one that can regenerate itself in practice. It was originally generated in 1962[1] from META I, a handwritten interpreter which served as a bootstrap. The metalanguage of META II uses parsing equations to translate parsing equations to a simple virtual machine.
Syntax
The following program (provided by Schorre) is both an example of META II and also the original specification and implementation. That is, this grammar can recognize and compile META II descriptions into assembly.[2]
.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
When executed by META I, this program generates assembly code for a parsing machine which has the same behavior as META I. When executed by META I or META II, that assembly code parses META II into the same assembly code again; META II reproduces itself when given an appropriate bootstrap as a starting point.
The precise operation of META I's parsing machine is detailed in Schorre's paper (Figure 6), but it is deliberately flexible in order to encourage users to fork and modify META II to suit their needs.
Metasyntax
META II is not presented as a standard language, but as a point of departure from which a user may develop his own META "language". ~ D. V. Schorre
Note that the original program uses ., for the semicolon in place of ; due to typographic limitations. It can be a fun exercise to determine how to fix this infelicity by customizing META II. One approach involves the following algorithm:
- (Chaos) Extend the syntax to allow for either semicolon
- (Discord) Regenerate META II to support the extended syntax
- (Confusion) Change
.,to; - (Bureaucracy) Optional: Remove support for
., - (The Aftermath) Regenerate META II twice and verify that the program is still a fixed point
Note that this algorithm implements the standard Discordian five-act pattern for migrations. Concretely, the extension is performed by changing the rule for statements from this:
ST = .ID .LABEL * '=' EX1 '.,' .OUT('R') .,
To this:
ST = .ID .LABEL * '=' EX1 ( ';' / '.,' ) .OUT('R') .,
The intrepid reader can verify in the Metacompiler Workshop that this algorithm and alteration generate a valid metacompiler.
Complexity class
After a decade of formal analysis what the 1964 META II does is generate top-down recursive-descent parsers with Wirth-Weber code ejection. ~ J. M. Neighbors, 2008
Depending on your programming subculture, you may prefer to call this syntax-directed translation, a visitor pattern, or even an algebraic homomorphism. ~ D. Long, 2014[1]
In modern terms, META II implements context-free parsing with ordered choice, but none of the optimizations, leading to quadratic-time parsing in the worst case. In terms of automata, META II is capable of modeling the behavior of unambiguous pushdown automata. Over such parse trees or automata, in terms of recursion schemata, META II implements a monoidal katamorphism which maps juxtaposition of productions onto concatenation of (lines of) text. Since katamorphisms often extend to hylomorphisms, Schorre's invitation to fork META II can be structurally described as an invitation to customize the target monoid.
The complexity class of META II should not be confused with the complexity of its target, which can be Turing-complete.
See also
External Links
- Neighbors 2008 (PDF), a tutorial on META II
- Compiler from META II to the canonical assembly: http://www.bayfronttechnologies.com/metaii.html
- Interpreter for the canonical assembly language: http://www.bayfronttechnologies.com/mc_workshop.html
References
- ↑ 1.0 1.1 Dave Long. 2015. META II: Digital Vellum in the Digital Scriptorium: Revisiting Schorre’s 1962 compiler-compiler. Queue 13, 1 (December 2014 / January 2015), 50–60. https://doi.org/10.1145/2716276.2724586
- ↑ D. V. Schorre. 1964. META II: a syntax-oriented compiler writing language. In Proceedings of the 1964 19th ACM national conference (ACM '64). Association for Computing Machinery, New York, NY, USA, 41.301–41.3011. https://doi.org/10.1145/800257.808896