Metacompiler

A metacompiler is a software development tool used chiefly in the construction of compilers, translators, and interpreters for other programming languages.^[1] They are a subset of a specialized class of compiler writing tools called compiler-compilers that employ metaprogramming languages. Metaprogramming is the writing of computer programs with the ability to treat programs as their data.^[2][3][4] The input to a metacompiler is a metaprogram written in a specialized metalanguage designed chiefly for the purpose of constructing compilers.^[1][4][5] The language of the compiler produced is called the object language.^[4] The minimal input producing a compiler is a metaprogram specifying the object language grammar and semantic transformations into an object program.^[4][5][6]

Metacompilers reduce the task of writing compilers by automating the aspects that are the same regardless of the object language. This makes possible the design of domain-specific languages which are appropriate to the specification of a particular problem. A metacompiler reduces the cost of producing translators for such domain-specific object languages to a point where it becomes economically feasible to include in the solution of a problem a domain-specific language design.^[5][7]

Metacompiler metalanguages are powerful string and symbol processing languages that are also useful for generating a wide range of other software engineering and analysis tools.^[5][7]

Besides being useful for domain-specific language development, a metacompiler is itself a prime example of a domain-specific language, designed for the domain of compiler writing.

A metacompiler is a metaprogram usually written in its own metalanguage or an existing computer programming language. The process of a metacompiler, written in its own metalanguage, compiling itself is called reflection, a metaprogramming term that in this case is equivalent to self-hosting compiler. Most common compilers written today are Self-hosting compilers. Reflection is a powerful tool, of many metacompilers, allowing the easy extension of their own metaprogramming metalanguage. The feature that separates a metacompiler apart from other compiler compilers is that it takes as input a specialized metaprogramming language that describes all aspects of the compilers operation. A metaprogram produced by a metacompiler is as complete a program as a program written in C++, BASIC or any other general programming language. The metaprogramming metalanguage is a powerful attribute allowing the ease of development of computer programming languages and other computer tools. Command line processors, text string transforming and analysis are easily coded using metaprogramming metalanguages of metacompilers.

A full featured development package would include a linker and a run-time support library. Usually a machine oriented language is required for writing the support library. C or C++ could be used as a machine oriented language. A library consisting of support functions required for the compilation process usually rounds out the full metacompiler package.

The meaning of metacompiler

In Computer Science the prefix meta is commonly used to mean about (its own category). As in metadata (about data). Data describing other data. A language that is used to describe other languages is a metalanguage. Meta may also mean on a higher level of abstraction. A metalanguage operates on a higher level of abstraction in order to describe properties of a language. BNF (Backus–Naur Form) is a formal metalanguage originally used to define ALGOL 60. BNF is a weak metalanguage, for it describes only the syntax and says nothing about the semantics or meaning. Metaprogramming is the writing of computer programs with the ability to treat programs as their data. A metacompiler takes as input a metaprogram written in a specialized metalanguages (a higher level abstraction) specifically designed for the purpose of metaprogramming.^[4][5][6] The output is an executable object program.

An analogy can be drawn: That as a C++ compiler takes as input a C++ programming language program, a metacompiler takes as input a metaprogramming metalanguage program.

FORTH metacompiler

Many Forth advocates call the process of creating a new implementation of Forth a meta-compilation and that it constitutes a metacompiler. The FORTH definition of metacompiler is:

"A metacompiler is a compiler which processes its own source code, resulting in an executable version of itself."

This Forth use of metacompiler is disputed in mainstream computer science. See Forth (programming language) and History of compiler construction. The actual Forth process of compiling itself is a combination of a Forth being a Self-hosting Extensible programming language and sometimes Cross compilation long established terminology in Computer Science. FORTH is an amazing language that is easy to program. Not so easy to read sometimes. Metacompilers are a general compiler writing system. Besides the FORTH metacompiler concept being indistinguishable from self-hosting and extensible language. The actual process acts at a lower level defining a minimum subset of forth words, that can be used to define additional forth words, A full FORTH implementation can then be defined from the base set. This sounds like a bootstrap process. The problem is that almost ever general purpose language compiler also fits the FORTH metacompiler description.

When (self-hosting compiler) X processes its own source code, resulting in an executable version of itself, X is a metacompiler.

Just replace X with any common language, C, C++ ,PASCAL, COBOL, FORTRAN, ADA, MODULA 2, etc. And X would be a meta compiler according to the FORTH usage of metacompiler. A metacompiler operates at an abstraction level above the compiler it compiles. It only operates at the same (self-hosting compiler)level when compiling itself. One has to see the problem with this definition of metacompiler. It can be applied to most any language.

However, on examining the concept of programming in FORTH, adding new words to the dictionary, extending the language in this way is metaprogramming. It is this metaprogramming in forth that makes it a metacompiler.

Programming in FORTH is adding new words to the language. Changing the language in this way is metaprogramming. FORTH is a metacompiler because FORTH is a language specifically designed for metaprogramming.^[4] Programming in FORTH is extending FORTH adding WORDS to the forth vocabulary creates a new FORTH dialect. FORTH is a specialized metacompiler for FORTH language dialects.

Historical

Metacompilers have played a significant role in both computer science and the build-up of the computer industry.

Early metacompilers

The early history of metacompilers is closely tied with the history of SIG/PLAN Working group 1 on Syntax Driven Compilers. The group was started primarily through the effort of Howard Metcalfe in the Los Angeles area.^[8] In the fall of 1962 Howard Metcalfe designed two compiler-writing interpreters. One used a bottom-to-top analysis technique based on a method described by Ledley and Wilson.^[9] The other used a top-to-bottom approach based on a work by glennie to generate random English sentences from a context-free grammar.^[10]

At the same time, Val Schorre described two "meta machines". One generative and one analytic. The generative machine was implemented and produced random algebraic expressions. Meta I the first metacompiler was implemented by Schorre on an IBM 1401 at UCLA in January 1963. His original interpreters and metamachines were written directly in a pseudo-machine language. Meta II, however, was written in a higher-level metalanguage able to describe its own compilation into the pseudo-machine language.^[11][12][13]

Lee Schmidt at Bolt, Beranek, and Newman wrote a metacompiler in March 1963 that utilized a CRT display on the time-sharing PDP-l.^[14] This compiler produced actual machine code rather than interpretive code and was partially bootstrapped from Meta I.

Schorre bootstrapped Mteta II from Meta I during the Spring of 1963. The paper on the refined metacompiler system presented at the 1964 Philadelphia ACM conference is the first paper on a metacompiler available as a general reference. The syntax and implementation technique of Schorre's system laid the foundation for most of the systems that followed. The system was implemented on a small 1401, and was used to implement a small ALGOL-like language.

Many similar systems immediately followed.

Roger Rutman of A. C. Sparkplug developed and implemented LOGIK, a language for logical design simulation, on the IBM 7090 in January 1964.^[15] This compiler used an algorithm that produced efficient code for Boolean expressions.

Another paper in the 1964 ACM proceedings describes Meta III, developed by Schneider and Johnson at UCLA for the IBM 7090.^[16] Meta III represents an attempt to produce efficient machine code, for a large class of languages. Meta III was implemented completely in assembly language. Two compilers were written in Meta III, CODOL, a compiler-writing demonstration compiler, and PUREGOL, a dialect of ALGOL 60. (It was pure gall to call it ALGOL).

Late in 1964, Lee Schmidt bootstrapped the metacompiler EQGEN, from the PDP-l to the Beckman 420. EQGEN was a logic equation generating language.

In 1964, System Development Corporation began a major effort in the development of metacompilers. This effort includes powerful metacompilers, Bookl, and Book2 written in LISP which have extensive tree-searching and backup capability. An outgrowth of one of the Q-32 systems at SDC is Meta 5.^[17] The Meta 5 system incorporates backup of the input stream and enough other facilities to parse any context-sensitive language. This system was successfully released to a wide number of users and had many string-manipulation applications other than compiling. It has many elaborate push-down stacks, attribute setting and testing facilities, and output mechanisms. The fact that Meta 5 successfully translates JOVIAL programs to PL/l programs clearly demonstrates its power and flexibility.

The LOT system was developed during 1966 at Stanford Research Institute and was modeled very closely after Meta II.^[18] It ha6d new special-purpose constructs allowing it to generate a compiler which would in turn be able to compile a subset of PL/l. This system had extensive statistic-gathering facilities and was used to study the characteristics of top-down analysis.

SIMPLE is a specialized translator system designed to aid the writing of pre-processors for PL/I, SIMPLE, written in PL/I, is composed of three components: An executive, a syntax analyzer and a semantic constructor.^[19]

The TREE META compiler was developed at Stanford Research Institute in Menlo Park, California. April 1968.

The early metacompiler history is well documented in the TREE META manual. TREE META paralleled some of the SDC developments. Unlike earlier metacompilers it separated the semantics processing from the syntax processing. The syntax rules contained tree building operations that combined recognized language elements with tree nodes. The tree structure representation of the input was then processed by a simple form of unparse rules. The unparse rules used node recognition and attribute testing that when matched resulted in the associated action being performed. In addition like tree element could also be tested in an unparse rule. Unparse rules were also a recursive language being able to call unparse rules passing elements of thee tree before the action of the unparse rule was performed.

The concept of the metarnachine originally put forth by Glennie is so simple that three hardware versions have been designed and one actually implemented. The latter at Washington University in St. Louis. This machine was built from macro-modular components and has for instructions the codes described by Schorre.

CWIC (Compiler for Writing and Implementing Compilers) is the last known Schorre metacompiler. It was developed at Systems Development Corporation by Erwin Book, Dewey Val Schorre and Steven J. Sherman With the full power of (lisp 2) a list processing language optimizing algorithms could operate on syntax generated lists and trees before code generation. CWIC also had a symbol table built into the language.

With the resurgence of domain-specific languages and the need for parser generators which are easy to use, easy to understand, and easy to maintain, metacompilers are becoming a valuable tool for advanced software engineering projects.

Schorre metalanguages

The earliest Schorre metacompilers, META I and META II, were developed by Val D. Schorre at UCLA. Other Schorre based metacompilers followed. Each adding improvements to language analysis and/or code generation.

In programming it is common to use the programming language name to refer to both the compiler and the programming language. The context distinguishing the meaning. A C++ program is compiled using a C++ compiler. That also applies in the following. For example META II is both the compiler and the language.

The metalanguages in the Schorre line of metacompilers are functional programming languages that use top down grammar analyzing syntax rules having embedded output transformation constructs.

A rule is a compiled test function having the form of an equation:

<name> = <body>;

returning success or failure. <name> is the function or rule name. <body> is a form of logical expression consisting of tests that may be grouped, have alternates, and output productions. A test is like a bool in other languages, success being true and failure being false.

Defining a programming language analytically top down is natural. For example a program could be defined as:

 program = $declarations;

Defining a program as a sequence of zero or more declarations.

In the Schorre META X languages there is a driving rule. The program rule above is an example of a driving rule. The program rule is a test function that calls declaration, a test rule, that returns success or failure. The $ loop operator repeatedly calling declarations until failure is returned. The $ operator is always successful, even when zero declarations occur. Above program would always return success.

The character sets of these early compilers were limited. The character / was used for the alternant (or) operator. A or B is written as A / B. ( ) are used for grouping.

A (B / C)

Describes a construct of A followed by B or C. As a boolean expression it would be

A and (B or C)

A sequence X Y has an implied X and Y meaning. ( ) are grouping and / the or operator. The order of evaluation is always left to right as an input character sequence is being specified by the ordering of the tests.

Special operator words whose first character is a "." are used for clarity. .EMPTY is used as the last alternate when no previous alternant need be present.

X (A / B / .EMPTY)

Indicates that X is optionally followed by A or B. This is a specific charistric of these metalanguages being programming languages. Backtracking is avoided by the above. Other compiler constructor systems may have declared the three posable sequences and left it up to the parser to figure it out.

The charestricts of the metaprogramming metalanguages above are common to all Schorre metacompilers and those derived from them.

META I

META I was a hand compiled metacompiler used to compile META II. Little else is known of META I except that the initial compilation of META II produced nearly identical code to that of the hand coded META I compiler.

META II

Each rule consists optionally of tests, operators, and output productions. A rule matches some part of the input program source character stream returning success or failure. On success the input is advanced over matched characters. On failure the input is not advanced.

Output productions produced a form of assembly code directly from a syntax rule.

TREE-META

TREE-META introduced tree building operators :<node_name> and [<number>] moving the output production transforms to umparse rules. The tree building operators were used in the grammar rules directly transforming the input into an abstract syntax tree. Unparse rules are also test finctions that matched tree patterns. Unparse rules are called from a grammar rule when an abstract syntax tree is to be transformed into output code. The building of an abstract syntax tree and unparse rules allowed local optimizations to be performed by analyzing the parse tree.

Moving of output productions to the unparse rules made a clear separation of grammar analysis and code production. This made the programming easier to read and understand.

CWIC

In 1969-1970, Erwin Book, Dewey Val Schorre, and Steven J. Sherman developed CWIC.^[5] (Compiler for Writing and Implementing Compilers) at System Development Corporation Charles Babbage Institute Center for the History of Information Technology (Box 12, folder 21),

CWIC is a meta-compiler system composed of three special-purpose languages, each intended to permit the description of certain aspects of translation in a straightforward, natural manner. The syntax language is used to describe the recognition of source text and the construction from it to an intermediate tree structure. The generator language is used to describe the transformation of the tree into appropriate object language. MOL/360 ,Machine Oriented Language-360, is a mid-level systems programming language for the IBM System/360 family of computers that is used to provide an interface with the machine and its operating system. MOL/360 was independently developed in 1968 and used to develop the ADEPT time sharing system.

The syntax language is similar to that of Dewey Val Schorre's line of metacompilers. It most resembles TREEMETA having tree building operations in the syntax language. The unparse rules of TREEMETA are extended to work with the object oriented generator language based on LISP 2.

CWIC includes three languages:

• Syntax: Transforms the source program input, into list structures using specialized grammars. A parsed expression structure is passed to a generator by placement of a generator call in a rule. A tree is a list whose first element is a node. The language has operators, < and >, specifically for making lists. The colon : operator is used to create node objects. :ADD creates an ADD node. The exclamation ! operator combines a number of parsed entries with the most previous created node to make a tree . The syntax rules are processed by generator functions, returning success or failure. The syntax language is very close to TREEMATA. Both use a colon to create a node. CWIC's tree building exclamation !<number> functions the same as TREEMETA's [<number>].
• Generator: a named series of transforming rules, each consisting of an unparse, pattern matching, rule. and an output production written in a LISP 2 like language. the translation was to IBM 360 binary machine code. Other facilities of the generator language generalized output.^[5]
• MOL-360: an independent mid level implementation language language developed in 1968 and used for writing the underlying support library.

Generators language

Generators Language had semantics similar to Lisp. The parse tree was thought of as a recursive list. The general form of a Generators Language function is:

  function-name(first-unparse_rule) => first-production_code_generator
           (second-unparse_rule) => second-production_code_generator
           (third-unparse_rule) => third-production_code_generator
               ...

The code to process a given tree included the features of a general purpose programming language, plus a form: <stuff>, which would emit (stuff) onto the output file. A generator call may be used in the unparse_rule. The generator is passed the element of unparse_rule pattern in which it is placed and returns values are listed in (). For example:

  expr_gen(ADD[expr_gen(x),expr_gen(y)]) =>
                                <AR + (x*16)+y;>
                                releasereg(y);
                                return x;
               (SUB[expr_gen(x),expr_gen(y)])=>
                                <SR + (x*16)+y;>
                                releasereg(y);
                                return x;
               (MUL[expr_gen(x),expr_gen(y)])=>
                              .
                              .
                              .
               (x)=>     r1 = getreg();
                            load(r1, x);
                            return r1;
...

That is, if the parse tree looks like (ADD[<something1>,<something2>]), expr_gen(x) would be called with <something1> and return x. A variable in the unparse rule is a local variable that can be used in the production_code_generator. expr_gen(y) is called with <something2> and returns y. Of note here is a generator call in an unparse rule is passed the element in the position it occupies. Hopefully in the above x and y will be registers on return. The last transforms is intended to load an atomic into a register and return the register. The first production would be used to generate the 360 "AR" (Add Register) instruction with the appropriate values in general registers. The above example is only a part of a generator. Every generator expression evaluates to a value that con then be further processed. The last transform could just as well have been written as:

               (x)=>     return load(getreg(), x);

In this case load returns its first parameter, the register returned by getreg(). the functions load and getreg are other CWIC generators.

CWIC addressed domain-specific languages before the term domain-specific language existed

From the authors of CWIC:

"A metacompiler assists the task of compiler-building by automating its noncreative aspects, those aspects that are the same regardless of the language which the produced compiler is to translate. This makes possible the design of languages which are appropriate to the specification of a particular problem. It reduces the cost of producing processors for such languages to a point where it becomes economically feasible to begin the solution of a problem with language design."^[5]

See also

• Compiler-compiler
• Metaprogramming
• History of compiler construction
• Self-hosting compilers
• Domain-specific language
• Domain analysis
• Program transformation

References