META II is a
domain-specific
Domain specificity is a theoretical position in cognitive science (especially modern cognitive development) that argues that many aspects of cognition are supported by specialized, presumably evolutionarily specified, learning devices. The posit ...
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
for writing
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
s. It was created in 1963–1964 by Dewey Val Schorre at
UCLA
The University of California, Los Angeles (UCLA) is a public land-grant research university in Los Angeles, California. UCLA's academic roots were established in 1881 as a teachers college then known as the southern branch of the California St ...
. META II uses what Schorre called syntax equations. Its operation is simply explained as:
Each ''syntax equation'' is translated into a recursive subroutine which tests the input string for a particular phrase structure, and deletes it if found.[META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE (Dewey Val Schorre UCLA Computing Facility 1964)]
/ref>
Meta II programs are compiled into an interpreted byte code language. VALGOL and SMALGOL compilers illustrating its capabilities were written in the META II language,
VALGOL is a simple algebraic language designed for the purpose of illustrating META II. SMALGOL was a fairly large subset of ALGOL 60
ALGOL 60 (short for ''Algorithmic Language 1960'') is a member of the ALGOL family of computer programming languages. It followed on from ALGOL 58 which had introduced code blocks and the begin and end pairs for delimiting them, representing a k ...
.
Notation
META II was first written in META I, a hand-compiled version of META II. The history is unclear as to whether META I was a full implementation of META II or a required subset of the META II language required to compile the full META II compiler.
In its documentation, META II is described as resembling BNF, which today is explained as a production grammar. META II is an analytical grammar. In the TREE-META
The TREE-META (or Tree Meta, TREEMETA) Translator Writing System is a compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble augmented Backus–Naur form with embedde ...
document these languages were described as reductive grammars.
For example, in BNF, an arithmetic expression may be defined as:
:= ,
BNF rules are today production rules describing how constituent parts may be assembled to form only valid language constructs. A parser does the opposite taking language constructs apart. META II is a stack-based functional
Functional may refer to:
* Movements in architecture:
** Functionalism (architecture)
** Form follows function
* Functional group, combination of atoms within molecules
* Medical conditions without currently visible organic basis:
** Functional sy ...
parser
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
that includes output directive. In META II, the order of testing is specified by the equation. META II like other programming languages would overflow its stack attempting left recursion. META II uses a $ (zero or more) sequence operator. The expr parsing equation written in META II is a conditional expression evaluated left to right:
expr = term
$( '+' term .OUT('ADD')
/ '-' term .OUT('SUB'));
Above the expr equation is defined by the expression to the right of the '='. Evaluating left to right from the '=', term is the first thing that must be tested. If term returns failure expr fails. If successful a term was recognized we then enter the indefinite $ zero or more loop were we first test for a '+' if that fails the alternative '-' is attempted and finally if a '-' were not recognized the loop terminates with expr returning success having recognized a single term. If a '+' or '-' were successful then term would be called. And if successful the loop would repeat. The expr equation can also be expressed using nested grouping as:
expr = term $(('+' / '-') term);
The code production elements were left out to simplify the example. Due to the limited character set of early computers the character /
was used as the alternative, or, operator. The $
, loop operator, is used to match zero or more of something:
expr = term $( '+' term .OUT('ADD')
/ '-' term .OUT('SUB')
);
The above can be expressed in English: An expr is a term followed by zero or more of (plus term or minus term). Schorre describes this as being an aid to efficiency, but unlike a naive recursive descent
In computer science, a recursive descent parser is a kind of top-down parsing, top-down parser built from a set of mutual recursion, mutually recursive procedures (or a non-recursive equivalent) where each such procedure (computer science), proce ...
compiler it will also ensure that the associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
of arithmetic operations is correct:
expr = term $('+' term .OUT('ADD')
/ '-' term .OUT('SUB')
);
term = factor $( '*' factor .OUT('MPY')
/ '/' factor .OUT('DIV')
);
factor = ( .ID
/ .NUMBER
/ '(' expr ')')
( '^' factor .OUT('EXP')
/ .EMPTY);
With the ability to express a sequence with a loop or right ("tail") recursion, the order of evaluation can be controlled.
Syntax rules appear declarative, but are actually made imperative by their semantic specifications.
Operation
META II outputs assembly code for a stack machine. Evaluating this is like using an RPN calculator.
expr = term
$('+' term .OUT('ADD')
/'-' term .OUT('SUB'));
term = factor
$('*' factor .OUT('MPY')
/ '/' factor .OUT('DIV'));
factor = (.ID .OUT('LD ' *)
/ .NUM .OUT('LDL ' *)
/ '(' expr ')')
( '^' factor .OUT('XPN'/.EMPTY);
In the above .ID and .NUM are built-in token recognizers. * in the .OUT code production references the last token recognized. On recognizing a number with .NUM .OUT('LDL' *) outputs the load literal instruction followed the number. An expression:
:(3*a^2+5)/b
will generate:
LDL 3
LD a
LDL 2
XPN
MPY
LDL 5
ADD
LD b
DIV
META II is the first documented version of a metacompiler
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.
The most common type of compiler- ...
,[Ignoring META I which is only mentioned in passing in the META II document.] as it compiles to machine code for one of the earliest instances of a virtual machine
In computing, a virtual machine (VM) is the virtualization/emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized hardw ...
.
The paper itself is a wonderful gem which includes a number of excellent examples, including the bootstrapping of Meta II in itself (all this was done on an 8K (six bit byte) 1401!)."—Alan Kay
The original paper is not freely available, but was reprinted in Doctor Dobb's Journal (April 1980). Transcribed source code has at various times been made available (possibly by the CP/M User Group). The paper included a listing of the description of Meta II, this could in principle be processed manually to yield an interpretable program in virtual machine opcodes; if this ran and produced identical output then the implementation was correct.
META II was basically a proof of concept. A base from which to work.
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''".
Many META "languages" followed. Schorre went to work for System Development Corporation
System Development Corporation (SDC) was a computer software company based in Santa Monica, California. Founded in 1955, it is considered the first company of its kind.
History
SDC began as the systems engineering group for the SAGE air-defense ...
where he was a member of the Compiler for Writing and Implementing Compilers (CWIC) project. CWIC's SYNTAX language built on META II adding a backtrack alternative operator positive and negative look ahead operators and programmed token equations. The .OUT
and .LABEL
operations removed and stack transforming operations :
and !
added. The GENERATOR language based on LISP 2
LISP 2 was a programming language proposed in the 1960s as the successor to Lisp. It had largely Lisp-like semantics and Algol 60-like syntax. Today it is mostly remembered for its syntax, but in fact it had many features beyond those of early Li ...
processed the trees produced by the SYNTAX parsing language. To generate code a call to a generator function was placed in a SYNTAX equation. These languages were developed by members of the L.A. ACM SIGPLAN sub-group on Syntax Directed Compilers. It is notable how Schorre thought of the META II language:
The term ''META'' "language" with ''META'' in capital letters is used to denote any compiler-writing ''language'' so developed.
Schorre explains META II as a base from which other META "languages" may be developed.
See also
*OMeta OMeta is a specialized object-oriented programming language for pattern matching, developed by Alessandro Warth and Ian Piumarta in 2007 under the Viewpoints Research Institute. The language is based on Parsing Expression Grammars (PEGs) rather th ...
*TREE-META
The TREE-META (or Tree Meta, TREEMETA) Translator Writing System is a compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble augmented Backus–Naur form with embedde ...
Notes
References
{{Reflist
External links
ACM - Paper on META II
1960s software
Computer languages
Parser generators