On 15 October 1997 I arrived in Portland, Oregon to do a postdoc at the Oregon Graduate Institute. During the year I lived in pretty Portland NW (picture).

Before arriving in Portland I had defended my thesis on Syntax Definition for Language Prototyping in which I introduced scannerless generalized-LR parsing and a syntax definition formalism (SDF2) supporting that parsing algorithm.

As a side project during writing my thesis I had started experimenting with rewriting strategies together with Bas Luttik. When I left OGI a year later I had designed (with Zino Benaissa and Andrew Tolmach) a programming language based on rewriting with programmable strategies, developed the first bootstrapping compiler for the language, presented it at ICFP’98, and decided that it could have no other name than Stratego. Since then, I and many others have worked on and with Stratego and the transformation toolset XT that connects SDF and Stratego.

Nine years later I was in Portland again to attend OOPSLA/GPCE 2006.To see how SDF and Stratego have fared in those years, it is instructive to see their manifestation at this conference (which was held in the convention center on the southside of the Willamette river with a view on downtown Portland to the north).

downtown portland
Read more

This afternoon Martin Bravenboer presented our OOPSLA’06 paper Declarative, Formal, and Extensible Syntax Definition for AspectJ. The photo shows the coauthors just before the presentation.

Aspect-Oriented Programming (AOP) is attracting attention from both research and industry, as illustrated by the ever-growing popularity of AspectJ, the de facto standard AOP extension of Java. From a compiler construction perspective, AspectJ is interesting as it is a typical example of a compositional language, i.e., a language composed of a number of separate languages with different syntactical styles: in addition to plain Java, AspectJ includes a language for defining pointcuts and one for defining advices. Language composition represents a non-trivial challenge for conventional parsing techniques. First, combining several languages with different lexical syntax leads to considerable complexity in the lexical states to be processed. Second, as new language features for AOP are being explored, many research proposals are concerned with further extending the AspectJ language, resulting in a need for an extensible syntax definition.

This paper shows how scannerless parsing elegantly addresses the issues encountered by conventional techniques when parsing AspectJ. We present the design of a modular, extensible, and formal definition of the lexical and context-free aspects of the AspectJ syntax in the Syntax Definition Formalism SDF, which is implemented by a scannerless, generalized-LR parser (SGLR). We introduce grammar mixins as a novel application of SDF’s modularity features, which allows the declarative definition of different keyword policies and combination of extensions. We illustrate the modular extensibility of our definition with syntax extensions taken from current research on aspect languages. Finally, benchmarks show that the performance of scannerless generalized-LR parsing for this grammar is comparable to the parser of abc.

The Stratego compiler is a pipeline applying over 40 components (some of which are applied more than once) to transform a sugared and modular source program to an implementation in C. This is an example of vertical compilation in the sense that one stage of compilation is applied to the entire program, before the next stage is applied.

The alternative, horizontal compilation, is to apply the entire pipeline, or at least a considerable part of it to a single unit of the program, before considering the next unit. This is of course done in separate compilation, where ‘compilation units’ are compiled separately from other units. But it can be done to smaller units as long as the transformations are compositional, don’t need information from other parts of the program.

After getting rid of nested functions, the next issue on my agenda is to refactor the Stratego compiler to provide a compilation library that offers translation strategies that can be applied to single definitions and that can be composed to form both horizontal and vertical compilers.

The first goal of the operation is to improve the performance of the Stratego compiler by eliminating intermediate ATerm files and by increasing the locality of the operations; instead of traversing the entire program for each stage, apply all stages to a single definition, before moving to the next.

In the longer term, this refactoring should enable the combination of interpreted, statically compiled, and run-time compiled code. Furthermore, it should facilitate the creation of an open compiler for Stratego that supports languages extension libraries.

The catch of course is in the compositionality of the compilation process. While many stages of the compiler can easily be applied per definition, or are even based on local rewriting, there are several stages that require the whole program. One example, is the stage that combines definitions with the same name into a single definition. A compositional compilation will require a scheme that allows the union of such definitions at link time. Another example, is the ‘lifting of dynamic rules’, which requires awares of all dynamic rule definition sites in a program to prevent generation of duplicate definition. Turning these operations into ‘horizontal’ ones may require some new (intermediate) language constructs or meta-data that can be consulted when joining program fragments. Such considerations will no doubt guide the design of a better module system for Stratego. More later.

Last summer I started with a renovation of the back-end of the Stratego compiler. The implementation of failure handling was based on the C exception handling API (setjmp/longjmp). However, this turned out to be costly. In the new compilation scheme failure is now represented as a NULL ATerm.

The second part of the renovation was to get rid of nested functions in the generated C code. After a year I have finally managed to finish this part of the renovation. In this blog I’ll explain the old and new compilation schemes.

At the same time as the setjmp/longjmp were introduced in the Stratego compiler (somewhere in 2001), I discovered that gcc supported nested functions in C. The following example illustrates why this was a useful feature.

The strategy bottomup is defined as follows:

  bottomup(s) = all(bottomup(s)); s

A recursive invocation of bottomup(s) is passed to the one-level traversal operator all.

In the generated C code, strategy operators are implemented as functions that take a function pointer as argument. For instance, the all operator is implemented by the function SRTS_all with signature

  ATerm SRTS_all(ATerm f(ATerm), ATerm);

However, a strategy expression such as bottomup(s) is clearly not something with a function pointer. Therefore, the compiler lifts such expressions from argument positions into local definitions. Thus, the definition of bottomup is rewritten to:

  bottomup_1_0(e_1 : ATerm() -> ATerm()|) =
    let a_0(|) = bottomup_1_0(e_1|)
     in all(a_0|)
    end
    ; e_1

Now the argument of all is just a function name, which can be translated as passing a function pointer. The definition of a_0 has to be nested in the definition of bottomup since it refers to the argument e_1 of that definition.

Nested functions in C provide a very convenient feature for translating such local definitions. A nested function is an ordinary C function that is defined within the scope of another C function. Thus, it can refer to all arguments and local variables of the enclosing function. This enables a straightforward implementation of local definitions in Stratego; a local definition is replaced with a nested function. Using this approach the rewritten definition of bottomup above is translated as follows:

ATerm bottomup_1_0 (ATerm e_1 (ATerm), ATerm t)
{
  auto ATerm a_0 (ATerm t);
  ATerm a_0 (ATerm t)
  {
    t = bottomup_1_0(e_1, t);
    if((t == NULL)) goto fail_1 ;
    return(t);
    fail_1 :
    return(NULL);
  }
  t = SRTS_all(a_0, t);
  if((t == NULL)) goto fail_0 ;
  t = e_1(t);
  if((t == NULL)) goto fail_0 ;
  return(t);
  fail_0 :
  return(NULL);
}

While nested functions make the translation of nested definitions straightforward, they posed several problems.

In the first place, nested functions are only supported by gcc, reducing the portability of code generated by the Stratego compiler.

Secondly, nested functions in gcc are implemented by means of trampolines, a small piece of code that is generated at run-time and stored on the stack. This code essentially stores the closure of the nested function, that is, a pointer to the actual function and (pointers to) the variables in the enclosing stack-frame(s) to which it has access. The problem with this implementation is that it executes code stored on the stack, which is forbidden on more and more platforms, as it poses a security risk. Thus, we were confronted with users not being able to use Stratego/XT on some platforms.

Finally, the implementation of nested functions in gcc does not have a high priority with gcc developers, which caused build failures for the Stratego/XT distribution with some versions of gcc, especially on MacOSX.

While nested functions were quite convenient, they had to go and be replaced with an explicit mechanism for handling closures. The mechanism chosen was to use static links to reach stack frames of enclosing functions and an explicit closure data-structure to represent a function pointer with its environment. For example, in the new translation scheme, the signature of the SRTS_all operator becomes:

  ATerm SRTS_all(StrSL sl, StrCL s, ATerm t)

StrSL represents static links and StrCL is the type of closures.

Locally defined strategies are now translated to top-level (static) functions and an explicit closure is allocated in the enclosing function. Thus, the bottomup strategy is translated to the following pair of C functions:

ATerm bottomup_1_0 (StrSL sl, StrCL e_1, ATerm t)
{
  sl_decl(sl);
  sl_funs(1);
  sl_init_fun(0, e_1);
  {
    struct str_closure a_0 = { &(lifted_0) , &(frame) };
    StrCL lifted_0_cl = &(a_0);
    t = SRTS_all(sl, lifted_0_cl, t);
    if((t == NULL)) goto fail_1 ;
    t = cl_fun(e_1)(cl_sl(e_1), t);
    if((t == NULL)) goto fail_1 ;
  }
  return(t);
  fail_1 :
  return(NULL);
}
static ATerm lifted_0 (StrSL sl, ATerm t)
{
  sl_decl(sl);
  t = bottomup_1_0(sl_up(sl), sl_fun_cl(0, sl), t);
  if((t == NULL)) goto fail_2 ;
  return(t);
  fail_2 :
  return(NULL);
}

The declaration

  struct str_closure a_0 = { &(lifted_0) , &(frame) };

allocates a closure consisting of a pointer to the function lifted_0 and a pointer to the current frame, which is an explicit data-structure in which escaping functions and variables are stored. The frame variable is declared by the macro sl_decl at the start of the bottomup_1_0 function. A pointer to this closure (lifted_0_cl) is passed to the invocation of SRTS_all.

Note that a call to a function passed as a closure needs unwrapping of the closure into a function pointer and a static link:

    t = cl_fun(e_1)(cl_sl(e_1), t);

While I started the implementation of this new translation scheme already in September 2005, I didn’t get around to finishing it until yesterday. We spent a large effort last Fall to get the documentation of Stratego/XT in better shape, and after that I was busy teaching and doing god knows what, but it was not hacking the Stratego compiler.

With this stumbling block out of the way, the door is open to a whole new set of innovations to the compiler and the Stratego language. A better module system is high on the wish list. Also we want to move from a separation of the compiler in phases to a compiler library that will allow larger parts of the compilation process to be applied to a single definition and elimination of intermediate ATerm files.

When you fill in the registration form for OOPSLA and GPCE don’t forget to check the G4 box for our (Martin, Karl and me) tutorial on Building Java Transformations with Stratego/XT. The tutorial will be held on Monday afternoon.

In this tutorial we give an overview of techniques for program transformation, illustrated through the Stratego/XT program transformation system. We explain the general architecture of transformation systems, and how Stratego/XT is used to assemble such systems from components. We introduce a set of ready made components for Java transformation, and show how to program custom transformation components using Stratego. In particular, we show how to express local transformations using rewrite rules and strategies and how context-sensitive transformations can be expressed easily using dynamic rewrite rules. All techniques and language features are illustrated with implementations of transformations on Java programs, that show how to apply all introduced techniques in practice.

See also the page on the GPCE’06 site.