1 The Metaprogramming System

A number of tools in the Mjølner BETA System are metaprograms, i.e. programs that manipulate other programs. The metaprogramming system is grammar-based in the sense that a metaprogramming tool may be generated from the grammar of any language. For each syntactic category of the language, a corresponding pattern is generated. The syntactic hierarchy of the grammar is mapped into a corresponding pattern hierarchy. This object-oriented representation of programs is further exploited by including a set of more general patterns that view a program as an abstract syntax tree and by allowing the user to add semantic attributes in sub-patterns.

The Mjølner BETA System is a programming environment that supports design, implementation and maintenance of large production programs. In such an environment support for structure and security is essential. The Mjølner BETA System is primarily aimed at supporting the object-oriented programming style.

All metaprogramming tools in the Mjølner BETA System manipulate programs through a common representation that is abstract syntax trees (ASTs). It was decided that for a language supported by the system, the corresponding ASTs should be instances of a well-defined data type. There is no commonly agreed definition of abstract syntax tree, which implies that each language implementor selects his own definition. A context-free grammar for a language induces an abstract syntax that may be used to give an AST-definition. In the Mjølner BETA System, the representation of a program as an AST is defined by means of a context-free grammar for the language. In addition there is a set of rules that specify how the context-free grammar is mapped into a set of data types. The context-free grammar is then part of the specification of the environment.

The ASTs defined by the context-free grammar may be described as Lisp S-expressions. An example of a Pascal statement and a corresponding AST in the form of an S-expression is:

while p<>q do if p<q then q:=q-p else p:=p-q
(while (<> p q)
        (if (< p q)
               (:= q (- q p))
               (:= p (- p q))))

S-expressions could in fact be used for manipulation of an AST. In order to do this in Simula, BETA, or other languages, predefined patterns (types) modelling S-expressions could be included in the environment.

Not all S-expressions do, however, constitute correct programs. In order for an S-expression to be an AST, a certain context-free structure must be satisfied. E.g. the S-expression '(while (if p) (else q))' does not correspond to an AST for a Pascal program, even though it is a well defined tree structure.

An object-oriented model of the ASTs has been developed as part of the Mjølner BETA System. An AST is modelled as an instance of a pattern. There is a pattern corresponding to each syntactic category (nonterminal) of the grammar. ASTs derived from a syntactic category are then modelled as instances of the corresponding pattern. The pattern IfImp corresponds to the syntactic category <IfImp>. Instances of pattern IfImp then model ASTs that may be derived from <IfImp>.

The grammar hierarchy is modelled by a corresponding pattern hierarchy. E.g. if the nonterminal <Imp> may derive <IfImp>, <WhileImp> etc., then the pattern Imp will be a super-pattern of IfImp. The pattern hierarchy is derived automatically from the context-free grammar. In order for this to work properly, the context-free grammar must obey a certain structure.

Using the metaprogramming system, there is a well defined representation of programs in the form of ASTs. This implies that the various Mjølner BETA System tools and other metaprograms all are able to use the same representation of programs.

The grammar-based interface described above results in a set of patterns for each language. A metaprogram using the grammar-based interface will thus be language specific since it uses the set of patterns generated from the grammar of the actual language. A number of tools are language specific in the sense that usually one exists for each language. Examples of tools that benefit from using the grammar-based interface are: semantic checkers, program analysers, interpreters, browsers, graphical presentation tools, transformation tools.

For certain types of metaprograms it may be inconvenient to use the grammar-based interface, since it implies grammar-based information to be hard-coded in the programs. If manipulation of the AST could only take place through this interface, it would be necessary to write such tools for every language. This is of course not acceptable. Examples of such tools are table-driven parsers and syntax-directed editors.

In order to support both types of tools, the AST in the metaprogramming system may be accessed at three levels.

The three levels are also modelled by a pattern hierarchy. A generated context-free level is a subpattern of tree level, and a semantic level is a subpattern of the context-free level for the language in question.

In the metaprogramming system, an attempt has been made to view traditional tools like editor, compiler and debugger as metaprograms in general. The advantage of this is that all tools including user programs access programs through a common representation. This leads to the integration of the grammar-based interfaces with the tree level and semantic level described above.

The implementation language of the metaprogramming system is BETA. This means that all metaprograms are written in BETA. However, metaprograms can manipulate ASTs of any context-free language.

The metaprogramming system is also known under the name Yggdrasil. This name is used in a few operations, and in some of the diagnostic messages from the system. The name originates in the Nordic mythodology, where Yggdrasil is the name of the "Tree of Life".

The Metaprogramming System - Reference Manual
© 1991-2004 Mjølner Informatics
[Modified: Wednesday April 4th 2001 at 16:28]