Grammar Based Definition Of Metaprogramming Systems

Robert Cameron^? and Robert Ito^?. Grammar-Based Definition of Metaprogramming Systems. ACM Transactions on Programming Languages and Systems Vol. 6, No. 1, January 1984, Pages 20-54. (ACM Digital Library)

Summary

This paper describes the GRAMPS method for meta-programming. GRAMPS stands for GRAmmar-based MetaProgramming Scheme. The method basically describes how abstract syntax tree^? manipulation can be done in a general-purpose programming language. Given an API for analyzing and constructing syntax trees, transformations can be expressed. For example, the transformation

  repeat statement-list until true   ===>   begin statement-list end

is programmed as

  if NodeType(stmt) = RepeatLoop then
     if TrueQ(TerminatingExpressionOf(stmt)) then
       Replace(stmt, MakeCompoundstatement(LabelOf(stmt), StatementsOf(stmt)))

At various points in the paper this style is described as `fairly simple and reasonably elegant'.

The paper illustrates the approach with a number of example transformations, including expression simplification^?, loop unrolling^?, and inaccessible statement elimination^?.

The abstract syntax API is based on a grammatical specification of the object programming language. How the API is derived from the specification seems more a matter of methodology than generation.

Along the way the paper discusses all kinds of problems that have to be addressed by a meta-programming system.

The use of concrete syntax^? in meta-programs is considered, but deemed too difficult for a first stab at designing a meta-programming system. Potential problems in this area that are mentioned include: how to deal with comments and whitespace, how to control the appearance of the resulting program text, and how tto deal with abstract syntax that does not directly correspond to the grammatical structure, for example, as a result of removing parentheses and de sugaring^?.

The paper dismisses schema or rule-based meta-programming. Rules would not be capable of dealing with the complex side-conditions involved in determining whether a transformation applies. Also the implementation of pattern matching is deemed as innefficient and impractical.

In relation to the problems caused by the dangling-else construct of Pascal, the authors mention that ease of transformation^? should be a criterion in language design.

The paper does not mention tree traversals^? as a source of overhead in meta programs^?, let alone introduce generic traversals^?, as introduced for example in strategic programming.

In conclusion: This paper is an early attempt at getting to grips with the construction of meta-programming systems. The paper touches upon many of the issues that one encounters building such systems,

-- EelcoVisser - 20 Jun 2002

---

CategoryPaper