Transformations and Abstractions

moving blog

2007-01-07T14:03:00.000+01:00

Dear reader of my blog, if you exist. After foolishly renaming the url of my blogger blog to throw off your rss subscription, here is another attempt to make sure I loose you. I have set up camp under the new domain http://www.eelcovisser.net where I intend to collect all my personal webmusing, including my photography work. Part of the new site is a serendipity based blog, which you'll find at http://blog.eelcovisser.net

Flickr

2006-12-30T19:26:00.001+01:00

This is a test post from , a fancy photo sharing thing.

Declarative, Formal, and Extensible Syntax Definition for AspectJ

2006-10-26T02:55:00.000+02:00

coauthors
Originally uploaded by Eelco Visser.

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.

From Vertical to Horizontal Compilation?

2006-08-03T13:18:00.000+02:00

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.

Getting rid of nested functions

2006-08-03T11:20:00.000+02:00

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.

Learn Stratego/XT at OOPSLA/GPCE

2006-07-05T17:05:00.000+02:00

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.

Partial Evaluation and (Semantics-based) Program Manipulation

2006-07-05T14:25:00.000+02:00

Once you are done with your contribution for the Software Transformation Systems workshop in Portland (co-located with OOPSLA/GPCE), you should start thinking about your contribution to PEPM 2007, which I am chairing together with Ramalingam from IBM.

Last year PEPM broadened its mission from a narrow focus on partial evaluation techniques and applications, to all topics concerned with analysis and manipulation of programs. In particular, the aim is to attract work that applies such techniques to real languages and large code bases. That is, not just design of clever techniques, but also validation of these techniques in practice. The website provides extensive advice for authors of research and tool presentation papers.

Program and model manipulation techniques such as transformations driven by rules, patterns, or analyses, partial evaluation, specialization, slicing, symbolic execution, refactoring, aspect weaving, decompilation, and obfuscation.
Program analysis techniques that are used to drive program/model manipulation such as abstract interpretation, static analysis, binding-time analysis, dynamic analysis, constraint solving, and type systems.
Analysis and transformation for programs/models with advanced features such as objects, generics, ownership types, aspects, reflection, XML type systems, component frameworks, and middleware.
Techniques that treat programs/models as data objects including meta-programming, generative programming, staged computation, and model-driven program generation and transformation.
Application of the above techniques including experimental studies, engineering needed for scalability, and benchmarking. Examples of application domains include legacy program understanding and transformation, domain-specific language implementations, scientific computing, middleware frameworks and infrastructure needed for distributed and web-based applications, resource-limited computation, and security.

We especially encourage papers that break new ground including descriptions of how program/model manipulation tools can be integrated into realistic software development processes, descriptions of robust tools capable of effectively handling realistic applications, and new areas of application such as rapidly evolving systems, distributed and webbased programming including middleware manipulation, model-driven development, and on-the-fly program adaptation driven by run-time or sttistical analysis.

From Natural Semantics to Stratego

2006-06-30T21:36:00.000+02:00

Yesterday, Brad Alexander from the University of Adelaide visited the Uithof and gave a talk in the Software Technology Colloquium with the title "From Natural Semantics to Stratego". He explained how he was in the process of converting an implementation of an optimizer for a second-order functional language in natural semantics (using the Centaur system) to a Stratego program using rewrite rules and strategies. As a result of using Stratego, transformations that took hundreds of lines of code could be reduced to only a few. The exciting thing about his presentation was that the basic Stratego techniques he used were quite unexiting. That is, using the basic ideas of separate rewrite rules and parametric strategies he could greatly simplify his optimizer. I hope to see more of his work in the future. Brad was on his way to Estonia to deliver a talk at the AMAST 2006 conference.

Career Evolution (Moving to Delft)

2006-06-30T15:34:00.000+02:00

Last week I accepted a position as associate professor at the Software Engineering Group of Delft University of Technology. I will join forces there with Arie van Deursen who recently started at TUD as a full professor. The ambition is to build a strong research group in the area of software engineering, based on our work in software evolution (Arie) and program transformation. With NWO funding for a project on extensibility of transformation systems and one on model-driven software evolution my tenure at TUD can start full force. Of course, I will continue work on Stratego/XT and applications together with Martin Bravenboer, who will join me at TUD. I also hope to convince Eelco Dolstra to make the move to Delft. We are aiming at setting up a new buildfarm for supporting our own, but hopefully also other research projects.

Model-Driven Software Evolution

2006-06-30T15:01:00.000+02:00

We just got word from NWO, the dutch national research funding organization, that our project proposal on Model-Driven Software Evolution has been granted. This means that we will have funding to hire two PhD students, a postdoc, and an assistant professor. The project is a collaboration between Arie van Deursen (principal investigator) and myself and is going to take place at Delft University of Technology, (where I'll be moving; see next blog).

If you have an interest in program transformation and domain-specific languages, and the ambition to contribute to the state-of-the-art in these areas, then you might consider applying for one of these jobs. Official job adverts will be available later (we really just learned about acceptance), but in the mean time you can contact me if you have questions.

Here is the summary of the research proposal:

The promise of model-driven engineering (MDE) is that the development and maintenance effort can be reduced by working at the model instead of the code level. Models define what is variable in a system, and code generators produce the functionality that is common in the application domain.

The problem with model-driven engineering is that it can lead to a lock-in in the abstractions and generator technology adopted at project initiation. Software systems need to evolve, and systems built using model-driven approaches are no exception. What complicates model-driven engineering is that it requires multiple dimensions of evolution. In regular evolution, the modeling language is used to make the changes. In meta-model evolution, changes are required to the modeling notation. In platform evolution, the code generators and application framework change to reflect new requirements on the target platform. Finally, in abstraction evolution, new modeling languages are added to the set of (modeling) languages to reflect increased understanding of a technical or business domain. While MDE has been optimized for regular evolution, presently little or no support exists for metamodel, platform and abstraction evolution. It is this gap that this project proposes to address.

The first fundamental premise of this proposal is that evolution should be a continuous process. Software development is a continuous search for recurring patterns, which can be captured using domain-specific modeling languages. After developing a number of systems using a particular meta-model, new patterns may be recognized that can be captured in a higher-level or richter meta-model. The second premise is that reengineering of legacy systems to the model-driven paradigm should be a special case of this continuous evolution, and should be performed incrementally.

The goal of this project is to develop a systematic approach to model-driven software evolution. This approach includes methods, techniques, and underlying tool support. We will develop a prototype programming environment that assists software engineers with the introduction, development, and maintenance of models and domain-specific languages.

Software Transformation Systems

2006-05-12T15:32:00.000+02:00

Together with Magne Haveraaen, Jim Cordy, and Jan Heering, I am organizing the next Workshop on Software Transformation Systems (STS'06), which will be co-located with GPCE and OOPSLA in Portland, Oregon in October. If you are interested in the design, implementation, and use of transformation systems you should consider submitting an abstract. (Note that the webpage is being updated, so check back on details of submissions.) If it will be like last time, it promisses to be a lively day full of interesting discussions.

Transformations for Abstractions (Looking for a Postdoc or PhD student)

2006-05-10T12:32:00.000+02:00

Recently I got notice from NWO, the dutch research funding organization, that the project proposal `Transformations for Abstractions (TFA)' that I submitted last September was accepted. (In a very competitive round; only 15% of proposals was accepted this year.) As a consequence, I have funding for a three year postdoc or a four year PhD student position. The topic of the project is language extensions (abstractions), in general, and extension of transformations on/for language extensions, in particular. Here is the summary of the proposal:

This proposal is about techniques at the intersection of two areas of software engineering. (1) In order to automate software engineering we would like to automate the process of producing programs by means of automatic transformations, thereby computing with programs as we do with other data. (2) In order to improve the expressivity of programming languages to the concepts and notations of specific application domains, we would would like to extend general-purpose languages with domain-specific abstractions. Combining these desiderata leads to the need to extend transformations for new domain-specific abstractions.

The goal of this project is to develop a systematic approach to the extension of general purpose languages with domain-specific abstractions, integrating those abstractions in the syntax and transformations of the programming environment. This requires research into the following issues:

strategies for the definition of domain abstractions
mechanisms for open extensibility of transformations
methods and patterns for design of open transformations
constraints for independent extensibility of transformations
derivation of transformation extensions from definitions of abstractions

We approach this goal by analyzing a variety of existing domain-specific languages and transformations, developing generic extensibility mechanisms, and validating these first in an `in vitro' setting and then in a programming environment for the Java language. The project builds on a solid body of work from the Stratego/XT project that will allow us to concentrate on the core of the problem, rather than being distracted by infrastructural issues.

If you are interested in the project, either as a candidate for the position or as a collaborator, I would like to hear from you. Further information (such as the full project proposal) is available on request.

Image Transformation

2006-05-07T19:59:00.000+02:00

After many years, I finally have a new picture for my home page. Here is the transformation from December 1998 to May 2006:

Clearly the main reason for a new picture was the quality of the old one; I don't look a day older, do I;-) My renewed interest in photography was sparked by the discovery of autostitch, a tool that stitches together pictures from different parts of the same scene. It allows easy composition of panoramas such as the following picture of a canal in Amersfoort: It is composed from a bunch (10?) pictures taken by hand (no tripod) with my not so fantastic Samsung digital camera. Autostitch discovers how to put the pieces together. It does not only work for landscape panoramas, as illustrated by the following 180 degrees interior shot: It can also be used for funny things such as the following composition of three pictures I took back in 2004 at OOPSLA/GPCE in Vancouver of Martin Bravenboer and Jurgen Vinju: Or even more surrealistic compositions with multiple occurrences of the same people: See my autostitch experiments for more examples. That was a fun diversion in the past week. I've neglected this blog for a while. Much has happened in the meantime, and there are many plans for new (program) transformation work. Now that I've found time for messing around with picture transformation, I expect I'll find time for new blogs as well in the near future. Stay tuned. (I will mainly publish new photos at my flickr account.)

MetaBorg in Action

2005-09-15T21:55:00.000+02:00

This morning Rene de Groot presented his thesis work in our Software Technology Colloquium. He has worked on two case studies of embedding domain-specific languages in Java --- applying and refining our MetaBorg approach to `concrete syntax for objects'.

In the first case study Rene elaborated the JavaSwul extension of Java with the SWing Userinterface Language. Rather than the usual spaghetti code of Swing method invocations, the language allows you to follow the hierarchical structure of the Swing class hierarchy to create userinterface objects. For example, the following GUI

is produced by this Java program

import javax.swing.*;
import java.awt.*;
  
public class Test3 {
  public static void main(String[] ps) {
    JFrame frame = frame {
      title = "Welcome!"
      content = panel of border layout {
        center = label { text = "Hello World" }
        south = panel of grid layout {
          row = {
            button { text = "cancel" }
            button { text = "ok"}
          }
        }
      }
    };
    frame.pack();
    frame.setVisible(true);
  }
}

The JavaSwul Examples page contains a number of other cool examples including the creation of menus with eventhandlers and gridbags with a semi-visual layout syntax.

The second case study is the extension of Java with concrete syntax for regular expressions. First it provides a syntax for regular expressions and checks regular expressions in a program against that syntax at compile-time. Second because of the explicit syntax extension, there is no need for escaping special characters as has to be done when encoding regular expressions using strings. Finally, the extension provides syntax for defining string rewrite rules and combining those into compound string rewrite operations (analogously to rewriting strategy combinators in Stratego). Here is an example, with some wiki-like rewrite rules:

public String publish(String page) {
  regex body = [/ <body[^>]*?> .* </body> /]

  regex amp = [/ & /] -> [/ &amp; /] ;
  regex lt  = [/ < /] -> [/ &lt;  /] ;
  regex gt  = [/ > /] -> [/ &gt;  /] ;

  regex escape = amp <+ lt <+ gt

  regex noattach  = [/ <a[^>]*?> \s* Attach \s* </a> /]
                 -> [/ <strike> Attach </strike> /] ;
  regex edittopic = [/ %EDITTOPIC% /]
                 -> [/ <a href="${editAction}"><b> Edit </b></a> /] ;
  input ~= one( body
                <~>
                all( edittopic <+ noattach <+ escape  )
              )
  return input ;
}

In addition to the syntactic extensions of Java and their definition using transformations, the implementations include an extension of Martin Bravenboer's typechecker for Java, so that Java programs using the extensions are typechecked before transformation.

A preview of the work is presented in MetaBorg in Action, a paper for the Summer School on Generative and Transformational Techniques in Software Engineering (GTTSE'05) that was held in Braga, Portugal last Summer. Rene's thesis is due soon.

Service Configuration Management

2005-09-05T21:05:00.000+02:00

Today our sysadmin asked me to setup a new wiki for use in some course. (Due to early wiki enthusiasm I became wiki master in our department. In fact it took quite some time to convince people that not having a single web master was a good idea.) When I set up my first wikis, one for our Software Technology research group and the other for Program-Transformation.Org, it took me quite some time to get everything installed in the right place, customize the configuration file, and such misery. For instance, on the webserver of our department perl was not installed in /usr/bin as was expected by the CGI scripts of TWiki, but rather in /sw/bin. This required patching all scripts each time I upgraded the installation. Also the directories containing the site were mounted on a different path in the webserver than on the user server. Thus, scripts that were invoked via cron job (for example to update statistics) needed a different path configuration than scripts running on the server. As a result, updating the site was not something to look forward to, let alone adding new installations.

Today I didn't flinch a second when receiving the request to create a new wiki. I just copied the 60 line Nix file of another wiki, changed the name of the wiki, the directories in which to store the wiki data, the port at which to approach the wiki on the server, and customized a few other options. Then I called the install script, and there I had a new wiki set up and running. Well, actually I had to ask sysadmin to open the new port, but then it was just there.

This is all thanks to service configuration management with Nix. In this paper that Eelco Dolstra will present tomorrow morning at SCM-12 in Lisbon (Portugal), we show that the management of services requires the integrated management of software and configuration. By treating software configurations just like any other software components, rather than as state managed in global directories, one can uniquely and reproducibly describe a specific instance of a service. We have used this to succesfully deploy quite a few services already, including a subversion version management server, a Jira issue tracking server, a buildfarm and automatic release management system. The description of the machine specific parts of the deployment of these services is factored out into a small Nix expression, such that I could create a combined subversion/wiki server on my little home machine with the push of a button (well almost).

So if you don't have a chance to attend Eelco's talk tomorrow morning, at least have a look at the paper.

Stratego/XT 0.16M1

2005-09-02T11:05:00.000+02:00

The new translation scheme turned out quite well. On Linux it gives a slight performance improvement, on Macs it gives a major performance improvement; speedups of 3 times have been observed. Good reason for a new release:

Stratego/XT 0.16M1 is now available from

http://www.stratego-language.org/Stratego/StrategoRelease016M1

This release is the first milestone release (M1) towards the new major release 0.16. (The zero-th milestone was called 0.15.)

The purpose of the 0.16 development is a major overhaul of the language and compiler internals. Release 0.15 introduced the Stratego Core language and the corresponding refactoring and clean up of the compiler. This release features a lot of fixes to the Stratego Core compiler and lots of other small improvements. Noteworthy features include:

call(f|s*|t*) is a new language constructs that supports calling strategies by name, i.e., f is a term that is interpreted as the name of the strategy to call. Can be used for callbacks in libraries.
checksum strategy gives MD5 checksum of a term

Furthermore, this release already contains some features planned for future milestones:

For 0.16M2: A new translation scheme for implementing choice. Rather than using setjmp/longjmp the scheme now use NULL pointers to indicate the failure of a strategy. This produces a slight performance improvement on Linux and a great performance on Macs, where the setjmp/longjmp feature is quite expensive to use.

For 0.16M3: A good number of improvements to the implementation of dynamic rules. In particular, the compiler now detects overlapping dynamic rules and forbids their use.

While the 0.15 release was still rather experimental, the 0.16M1 release is much improved and is fairly reliable. We are interested in your experiences. Please report any problems such that we can solve these as soon as possible. We plan to have a stable 0.16 release by the end of September.

Translating Failing Transformations

2005-08-21T23:47:00.000+02:00

After deliberating about it for a long time (several years even), I finally implemented a new translation scheme for the Stratego Compiler. The old scheme used the C feature of setjmp/longjmp to deal with failing transformations. This provided the opportunity to go from using C as an assembly language, where an entire Stratego program was compiled to a single C function using gotos for control-flow, to a more idiomatic style of C programs in which each strategy definition was compiled to a C function. The setjmp/longjmp feature elegantly dealt with the notion of a failure by declaring a choice point (with setjmp) and jumping to it from anywhere (with longjmp). However, since choice points are the control-flow mechanism in Stratego, the speed of programs depends heavily on the cost of this feature. On Intel machinery (running Linux) this is not a big issue, but on Apples and Suns (RISC machines) the number of registers saved at each choicepoint is quite expensive; at least that is a theory about possibilities for improving the performance of Stratego programs.

Eelco Dolstra suggested a long time ago to return NULL to indicate failure of a strategy. Indeed, this representation closely matches the formal operational semantics of the language, in which the set of terms is extended with a failure value; exactly the ATerm data-type extended with an extra value (NULL). While conceptually simple, the idea seemed too disruptive to the run-time system, compiler, and native parts of the library to start work on, and there were always plenty of other things to do. (Especially considering the fact that the change does not add one bit of functionality.)

After the recent Stratego Core refactoring and clean up of the intermediate representation and the compiler, and solving lots of outstanding issues, this translation scheme refactoring came into view again. Interestingly, it took less then a week real time to achieve, which included a camping trip, a visit to Philips Research, and reading a couple of theses and articles. So either the problem was never that problematic to start with, or the recent drastic refactorings of the Stratego/XT source tree, configuration, and build system has paid off. Also the change to baseline-based bootstrapping (from self-based bootstrapping) has enormously simplified the process of changing the foundations of the compiler. Finally, the reliance on a solid continous build and release system gives one much more confidence in committing to a new version to bootstrap against. If there is a general lesson here: refactoring and continuous integration pay off.

As for the new translation itself; it is pretty standard fair. Have a look at s2c-ng.str and compare it to the classic s2c.str. The only flaw is that I had to resort to producing code with gotos. Noteworthy about the new version is the use of concrete syntax of Stratego and C almost everywhere, which makes a difference between night and day in maintaining the translation scheme. For example, the following rule defines the translation of the crucial guarded choice construct:

  TranslateStrat(|S,F) :
    |[ s1 < s2 + s3 ]| ->
    stm|[
      {
        ATerm ~id:x = t;
        ~stm:<translate-strat(|Next,F')>s1
        ~stm:<translate-strat(|S,F)>s2
        ~id:F' : t = ~id:x; 
        ~stm:<translate-strat(|S,F)>s3
      }
    ]|
    where <not(Next)> S; new => x; new => F'

Another interesting new feature is the collection of code fragments using dynamic rules, and the synthesis of the target program from these fragments afterwards; in contrast to the old method in which the source program was traversed for each type of fragment `driven by' the target program.

I'm writing this blog while waiting for the bootstrap build to go through, but from the regression tests for the compiler the implementation seems to work fine. What is not clear yet, is the performance improvement this will bring, if any. Another feature of the current translation scheme that seems to have negative impact on the performance of Stratego programs, especially on Apples and Suns, is the use of nested functions in the target C code. This is a feature of GCC, and therefore fraught with portability and performance problems. The implementation using trampolines also does not go very well with the tendency to forbid executable code on the stack. So this aspect of the translation is next in line to be changed. The basic idea is again simple and the use of fragment collection was partly motivated by this change. More later.

Transforming Bibliographies

2005-08-11T10:29:00.000+02:00

Among the useless things one can do in life, maintaining one or more publication lists ranks high. My tendency to waste time on my publication list probably dates back to my days as a PhD student when I badly needed publications to put on a list. On the other hand, as publications are the measure of achievement in research, more researchers may have this problem.

Anyway, maintaining a list of publications can be quite tedious, in particular if you want to provide multiple views on the publications. For example, a listing with most recent publications first, one providing the most important ones first, one organized by research topic, and finally a separate list for each project. Also your department may require regular submission of lists. On the web version the entries should come with links to the pdf files and/or the webpage of the publisher, but these links should not be displayed in the version for printing, since they are quite useless there.

Being a computer scientist, I elevated the activity of maintaining content to maintaining a program for generating the various lists. This is still a waste of time, of course, but the excuse is that it will save me time in future. Another excuse is that I developed my program as a case study for the transformation language Stratego.

In fact, the bibtex-tools package has emerged over a long time, starting with a syntax definition for BibTeX first written in 1999. It turns out that BibTeX has quite an intricate syntax that is not so easily formalized with a traditional approach based on a separate lexical analyzer and context-free parser. With the scannerless approach of SDF this poses no problems at all.

Also, the use of the Stratego to perform transformations on a structured representation of a BibTeX file is a definite improvement over directly transforming its text representation. Moreover, these transformations can be expressed quite concisely. For example, the following strategy definitions define an inliner for BibTeX that replaces occurrences of string identifiers with their body. (BibTeX allows the definition of strings such as @string{LNCS={Lecture Notes in Computer Science}}, which can then be quoted in entry fields using the identifier, e.g., series = LNCS.)

  bib-inline = 
    bottomup(try(DeclareInlineString + InlineString + FoldWords))

  DeclareInlineString =
    ?String(_, StringField(key, value))
    ; rules( InlineString : Id(key) -> value )

  FoldWords :
    ConcValue(Words(ws1), Words(ws2)) -> Words((ws1, ws2))

After having developed my own set of BibTeX tools using the Stratego transformation language over the last couple of years, I decided to make them into a proper software package that could be used by others, complete with a manual that explains the LaTeX/BibTeX/Hevea techniques used to get a publication list into HTML. The currently availabe version is a pre-release of the first official release 0.2. I'm waiting for a new stable version of Stratego/XT and for some feedback from users before I make the release official.

So if you don't want to waste time on editing your publication list webpage, but instead want to wast time learnig to use my tools, you now know where to find them.

Software Engineering News

2005-07-21T21:52:00.000+02:00

Or niews rather. I'm warming up for another installment of our software engineering course, and browsing to see what is going on. The monthly seniews newsletter written by members of CIBIT (formerly SERC) provides pointers to developments in software engineering, and has an online archive. This month with a pointer to the new book Pragmatic Version Control Using Subversion, which might be recommendable reading for our students.

Software Deployment in the News

2005-07-21T21:19:00.000+02:00

``The deployment role is a role that is often overlooked much to the pain of the users. '' writes Robert Bogue in a series about roles in software engineering. He forgets to mention the Nix Deployment System unfortunately. In Bogue's world (which is most of the world) software deployment is mostly a craft that has to be repeated for each and ever application to be installed, and one has to pray that a carefully crafted installation program will not break on the target machine. Nix expressions encode all the dependencies of an application, and once tested succesfully, deployment consists of transmitting the closure of those dependencies, in order to guarantee that everything is present at the target site.

Managed desktops, the next step for Nix? Chad Dickerson writes about outsourcing the management of desktop systems. We have been getting quite good at managing all aspects of services with Nix. That is, management of all software components and their configuration in one formalism. Examples are our subversion and Wiki servers. It would be great if this can be expanded to an entire desktop environment.

By the way, I found these items on ACM's careernews.

Transformations for Abstractions

2005-07-19T15:27:00.000+02:00

I finally finished my keynote paper for SCAM 2005, the worshop on Source Code Analysis and Manipulation, which will be held at the end of September in Budapest. This is a good occasion for finally making a start with my blog as well, as the title of the paper `Transformations for Abstractions' suggests that it is related to the topic of my blog. As the introduction states:

What is common in the transformations that we are exploring is that they are for supporting abstractions. That is, to enable programming at a higher-level of abstraction. Our aim is to integrate such transformations in the software development process and make them available to programmers. That is, create programming environments with full meta-programming support that let the (meta-) programmer extend the language, the compiler, and other aspects of the environment such as documentation generators. This requires the transformations provided by the programming environment to be extensible. The base programming language should be extensible with new constructs and/or with new (primitive) APIs implementing new abstractions. Likewise the compiler should be extensible with new transformations, and existing transformations should be extensible to new language constructs. New constructs may be implemented by reduction to the base language, or by extension of the back-end of the compiler. APIs may require domain-specific optimizations to ensure efficient execution.

The paper presents a small case study in the definition of extensible programming environments, where a programming environment is understood as consisting of a syntax definition of a language and a bunch of transformations on programs in that language. The programming environment in case is called TFA and is a tiny imperative language with a number of extensions.

A couple of highlights:

The language in the paper is strongly modularized. Each aspect such as built-in data types and language features are defined as a separate component. The framework provides a syntax definition and a number of transformations to be applied to programs in the language. Both the syntax definition and the implementation of the transformations in Stratego are modularized per extension. The transformations include desugarings, bound-variable renaming, evaluation (an interpreter), data-flow transformations, and function specialization.

Of course, the implementation of all the transformations use concrete syntax. For example, desugaring of for-loops is defined by the following rewrite rule:

ForToWhile :
  |[ for x := e1 to e2 do st* end ]| ->
  |[ begin
       var x : int; var y : int;
       x := e1; y := e2;
       while x <= y do
           st* x := x + 1;
       end
     end ]|
  where new => y

A particularly cool extension is the embedding of the domain-specific language of regular expressions. In the regexps extension one can write /re/e to match the string resulting from evaluating the expression e to the regular expression re. This extension is implemented by means of a bunch of desugaring rewrite rules that use dynamic rules to create new function definitions that should be added to the program at top-level. For example, the following rule defines the assimilation of the Kleene star operator:

ReKle : |[ /re*;f/ x ]| -> |[ g(x) ]|
where new => g
    ; add-def(||[
        function g(a : string) : int
        begin
          return /re;g/a | f(a);
        end ]|)

The sources for TFA can be found at the Transformations For Abstractions page of the Stratego wiki (although they are currently in very alpha state).

So what is my blog going to be about then? (First of all, I'm getting really annoyed with this editor as I haven't seem to find the right way to include code snippets, so I may well give up and go back to good old wiki editing). Well, in the coming months at least, I intend to further explore the TFA framework to see how far I can get with extensibile transformations in Stratego. In the course of this project I intend to add new extensions, both in the area of traditional programming language features as in the area of domain-specific language embeddings, andincorporate more types of transformations. The end result should be an extensible programming environment that might actually become useful in itself, a catalogue of transformations, and a better insight in the problems of extensibility.

How does this blog?

2005-05-23T08:05:00.000+02:00

An experimental post to see how this thing works and find out whether I'll be comfortable with putting content on some other server. (And is it possible to get the content out again?) I'd rather integrate a blog with my wiki homepage, but that hasn't worked so far.

Ok, checking the configuration options it turns out that everything is adaptable and that I can even store the blog on my own server (if i'd want that). So I'll leave things as they are and change them when I feel like it.