META II

META II

Designed by	Dewey Val Schorre
Appeared in	1964
Computational class	Pushdown automata
Reference implementation	META I
Influenced	TROL

META II is a two-tiered metacompiler, notable for being the first one that can regenerate itself in practice. It was originally generated in 1964 from META I, a handwritten interpreter which served as a bootstrap.

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.

.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:

1. (Chaos) Extend the syntax to allow for either semicolon
2. (Discord) Regenerate META II to support the extended syntax
3. (Confusion) Change ., to ;
4. (Bureaucracy) Optional: Remove support for .,
5. (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

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.

Computational class

Since META II utilizes Backus-Naur form grammars with additional operators which are effectively syntactic sugar for existing operations, META II is only capable of modeling the behavior of context-free grammar recognizers (pushdown automata). While META II may output Turing-complete code, actual programs/grammars written in the language can at most recognize context-free languages.

See also

• META II (Wikipedia)
• [1] a tutorial on META II