Languages

This last week, I spent some free cycles hacking together a small project instantiation tool for Stratego/XT. It makes setting up a fresh Stratego project really simple by automatically populating the project space with a default directory layout, build system files and some minimal program and syntax samples.

To create a project p0, all you have to do is:

$ crap --new-project p0

This creates all the files necessary for a complete GNU Autotools-based build system, including a sample Stratego program (src/xmpl.str):

p0/
   Makefile.am
   README.Developer
   README
   AUTHORS
   bootstrap
   p0.spec.in
   NEWS
   p0.pc.in
   configure.ac
   ChangeLog
   xmpl/
        Makefile.am
   syn/
       Makefile.am
   tests/
         Makefile.am
   src/
       Makefile.am
       xmpl.str

Once this is done, you can configure and compile the project,

$ ./bootstrap
$ ./configure
$ make all

install it,

$ make install

and even run the example transformation program:

$ echo "foo" | /usr/local/bin/xmpl
"Hello, World!"

The example program expects an input on stdin [or in a file specified by the -i switch], and will always produce the output string "Hello, World!".

The crap tool is part of the strategoxt-utils package. You can also download a stand-alone snapshot of crap.

More comprehensive documentation is available in the wiki. The tool is still very rough, so any suggestions for improvements and bug reports are very welcome.

It's official: I'm the bootstrapper. My hacking life in the last few weeks have hardly been anything but bootsrapping. I've already said a few things about the Stratego compiler hacking. Since it takes ~3-4 hours for a full build of the Stratego compiler in the Delft buildfarm, I've had a couple of other projects to dive into in parallell. One of these has been the porting of Eclipse IMP from Eclipse 3.2 to 3.3.

In short, IMP is an IDE generator based on Eclipse. It provides set of plugins and wizards that makes the development of programming language environments (a lot) easier. The basic workflow when building an IDE for you favourite language with IMP is, (1) provide a grammar defined using the LPG grammar language, (2) use the IMP-provided wizards inside Eclipse to generate things like syntax highlighting support, outline support, code folding support, templates, text hovers, etc, then (3) fill in the skeletons provided by the generator. My personal view (subject to change without warning) of the generated code is that it's a guide to which parts of the Eclipse framework you need to extend in order to provide a given piece of functionality. Sort of a little helpful gnome pointing you in the right direction. In some cases, the generated code will actually do all you want, but more often than not, you will want to go beyond it.

That was the backgrounder on IMP. A major drawback of the current IMP releases is that they will only work on 3.2. Oh, and, of course, that IMP requires IMP to build IMP. Getting this beast ported to 3.3 wasn't as straightforward as I'd hoped. It took a few iterations. The first was getting it to build properly without any problems on my plain 3.2 installation. That took me several days. All kinds of subtle bugs surfaced, presumably because I have a different set of development habits than the IMPers.

Once those were patched and fixed upstream, I managed to bootstrap my first version on 3.2. An ensuing battle with race conditions in the startup code of various plug-ins followed. I hate static initializers, but apparently not everybody does. In a multi-plugin architecture where the order to plugin loading is not guaranteed, I cannot see how you can safely assume the order of static initializers across plugins, but those questions are not for me to ponder. I ripped them out, and replaced them with lazy initializers as far as possible, and that worked wonders. With that hurdle out of the way, it was all down hill: a couple of internal JFace and JDT classes had changed locations and APIs between 3.2 and 3.3, but it was quick enough to rewrite the offending code (another reason why depending on internal APIs is a bitch, though I realize that the features in question could not have been provided without doing so).

It's a huge disappointment to realize that my patches are only a couple of hundreds of lines. I felt like I had to rewrite the world, at places... Anyway, here's hoping to its inclusion in one of the pending releases. I've updated our sdf2imp tool to use the 3.3-based IMP, so we're already seeing a return on my investment:)

A limitation of my previous stack tracing patches was that io-wrap and io-stream-wrap did not properly report traces on failure. The reason for this is easy to spot if we look at how the error is handled (this is where execution flow ends up when you call io-wrap):

  option-wrap(opts, usage, about, announce, s) =
    parse-options(opts, usage, about)
    ; announce
    ; (s; report-success <+ report-failure)

  report-failure =
      report-run-time
    ; <fprintnl> (stderr(), [ (), ": rewriting failed"])
    ; <exit> 1

As you can imagine, even though the program now happily prints a stack trace when the main strategy exits with a failure, it will not be printed when exit is called.

I've introduced a couple of stack introspection functions for dealing with this: stacktrace-get-current-frame-name returns the name of the current frame s, stacktrace-get-all-frame-names returns a list of all frame names and, stacktrace-get-current-frame-index returns integer that holds the current depth of the stack. These are actually implemented by primitives in the Stratego Standard Library (SSL).

A caveat of these strategies is that calling them will of course alter the stack. Even in the wonderful world of computing, we're not entirely free of Heisenbergian effects, apparently. However, there's a simple workaround: call the primitives directly, since this bypasses the way the compiler registers the stack frames.

With this trick in hand, I rewrote the two above strategies to include proper stack tracing for io-wrap:

  option-wrap(opts, usage, about, announce, s) =
    parse-options(opts, usage, about)
    ; announce
    ; (s; report-success <+ prim("SSL_stacktrace_get_all_frame_names") ; report-failure)

  report-failure =
      ?stacktrace
    ; report-run-time
    ; <fprintnl> (stderr(), [ <whoami> (), ": rewriting failed, trace:"])
    ; <reverse ; map(<fprintnl> (stderr(), ["\t", <id>]))> stacktrace
    ; <exit> 1

Applying the modified io-wrap on the following sample program

 
  main = io-wrap(my-wrap(foo))

  my-wrap(s) = s

  foo = debug(!"foo") ; bar

  bar = debug(!"bar") ; fap ; zap

  fap = debug(!"fap") ; id

  zap = debug(!"zap") ; debug ; fail

gives

./prog: rewriting failed, trace:
        main_0_0
        io_wrap_1_0
        option_wrap_5_0
        lifted144
        input_1_0
        lifted145
        output_1_0
        lifted0
        my_wrap_1_0
        foo_0_0
        bar_0_0
        zap_0_0

Due to the compiler lifting inner strategies into freshly named, top-level strategies, the trace will contain some lifted* entries. Also, should you call strategies or rules which are compiled with older versions of the compiler, there will be "dark spots" in your trace. It won't be truncated -- only the frames due to the old library will be hidden.

Prompted by my visit to EPITA, I hacked together some very basic support for stack traces in Stratego that might come in handy when a Stratego program fails.

Here's a simple Stratego program, called prog (which, if you look at it closely, will always fail):

  main = foo

  foo = bar

  bar = fap ; zap

  fap = id

  zap = fail

On the latest and greatest version of the compiler (build 17522 and later), you will get the following trace when this program is executed:

prog: rewriting failed, trace:
        main_0_0
        foo_0_0
        bar_0_0
        zap_0_0 

There are a number of caveats with the tracing that I will try to get rid of, and, when there are only very hard problems left, explain myself out of, in a couple of future posts.

Martin recently got his PhD . It's very well deserved. I've seen first hand how serious and focused he's been for the last 4+ years.

Inspired by his didactical skills, I decided to rearrange my own dissertation page so that the individual chapters of my dissertation are easily downloadable.

Since I don't expect anybody to have neither the time nor the inclination to read the entire thesis from start to finish, Martin's idea of making it available as a split download makes a lot of sense.

Having done this, I got inspired to continue with spring (winter?) cleaning on a lot of other pieces of my PhD work.

I've set up an Ant Ivy repository for Spoofax. This means that you are now able to check out the various Spoofax subprojects from the source code repository and expect each subproject to compile separately, since all its dependencies will be fetched from my Ivy repo. Some of the subprojects require Eclipse. For those, you must run a script, fetch.sh, which will pick out the necessary jars from your Eclipse installation. It would best to have this repo hosted along with the rest of Stratego/XT, since it's definitely part of the Stratego/XT umbrella, but the new infrastructure in Delft is still being set up, I've been told.

Trying my hand as a webmonkey, I've decided to upload new Spoofax pages with a revamped design.

With those things out of the way, I'm now working on a reflection API for Stratego/J so that we may easily instantiate Java objects and call methods on them from Stratego scripts. This is needed for another project I'm cooking. However, I keep running into the lack of a fully interactive Stratego interpreter on the JVM, and that's a very itchy spot just now...;)

It's been rather quiet on the northern front for quite some time. I've been mostly busy with diagnosing old ladies with chest pain of late, and trying to make heads and tails of the horrible electronic health record system at the hospital. Sheesh.

Anyway, today I found time to do some compiler hacking. It feels great, as always! I resurrected the strc-java project -- a Java backend for the Stratego compiler. After a couple of hours of fiddling around, I now have an extremely rudimentary runtime up and running, and the compiler can compile simple build expressions properly.

Given the simple strategy

main = !Foo(1,2)

the following Java code is produced:

public static class main_0_0 extends Strategy
{
    public final static main_0_0 instance = new main_0_0();
   public ATerm apply(ATerm term)
    {
      try
      {
        {
          ATerm[] b_0 = new ATerm[2];
          {
            ATerm c_0 = atermFactory.makeInt(1);
            b_0[0] = c_0;
          }
          {
            ATerm d_0 = atermFactory.makeInt(2);
            b_0[1] = d_0;
          }
          ATerm a_0 = atermFactory.makeAppl(atermFactory.makeAFun("Foo", 2, false), b_0);
          term = a_0;
        }
      }
      catch(Failure f)
      {
        return null;
      }
      return term;
    }
  }

There are a number of unnecessary blocks in the above code fragment, but that's an artifact of the way I wrote the Java code templates. I'll see if I can't get rid of them eventually.

I've spent some time hacking about in order to get closures working without too much overhead. I think the current scheme will work, but will require a bit of sophistication and context-awareness in the code generator.

You can see the scheme in the example above. Every strategy is compiled to its own class, with an apply method. The signature for this method is not fixed. Rather, the number of strategy and term arguments may vary. The last argument is always the current term. Every class has a singleton instance, called instance. This is how we get the pointer. All context information that's required will have to be passed in, through the argument list.

There are in principle two possible schemes for passing in arguments. The first is to do as Stratego/J (the Stratego interpreter for Java): use two arrays, e.g. ATerm apply(Strategy[] svars, ATerm[] tvars, ATerm currentTerm). This costs two calls to new (in the general case) for every strategy invocation. Not very appealing.

The other possibility is to sequence the strategy and term arguments in the argument list, e.g.:

ATerm apply(Strategy s0, Strategy s1, ATerm t0, ATerm t0, ATerm currentTerm) 

The problem here is that the arity of s.apply() is not fixed. We really have:

ATerm apply(Strategy<x0,y0> s0, Strategy<x1,y1> s1, ATerm t0, ATerm t0, ATerm currentTerm)

where x and y are the strategy and term arities, respectively. If we were generating C++ code, we could just use integers here. In Java, we'll have to insert real types. I'm tempted to use enums, and manually define the types N0 through N31. Nobody will ever invent a strategy with more than 32 strategy or term arguments, right?

I'll keep mulling this one over a bit. Feel free to drop me a line if you see better solutions.

As part of the PhD formalities, I'm required to hold a seminar on a topic of my own choosing. It's supposed to demonstrate to willing (or not-so-willing) listeners that I know how to talk scientifically and intelligibly about at least one subject.

I decided to present the Eclipse plugin for Stratego I've been hacking on for the last two years. It's becoming a rather interesting development environment, and I suspect that people with an interest in computer languages and/or development environments might actually find some of the material interesting.

Everybody, even (perhaps especially!) non-university folks are of course welcome to drop in, if they have the time.

Software development is expensive primarily because of the associated
maintenance cost; recent estimates suggest that about 70-90% of the
total cost of a software product is due to maintenance. It is therefore
desirable to automate as tasks as possible by supplying convenient and
powerful maintenance tools to the developers. This automation requires
the construction of software that analyses and transforms
other software.

In this talk, I will demonstrate Spoofax, an interactive program
transformation environment based on Eclipse. This environment supports
the development of stand-alone software transformation programs using
the Stratego software transformation language and the XT toolkit of
transformation components. I will demonstrate the applicability of
Spoofax and Stratego/XT through a series of transformation programs for
Java code.

Time: 14:15, Tuesday 8th of May (Updated Again)
Location: Lunchroom, 3rd Floor, Informatikkblokken, Høyteknologisenteret i Bergen
Cookies: Yes

If you're vaguely interested in dropping in, but don't know exactly where to go, contact me or drop by room 4152A (my office) in the fourth floor in the Informatics-wing of HIB around 14:05, and I'll guide you.

Eelco and I have a second paper at the LDTA workshop this year -- a tool description paper about Spoofax. The paper is very space-constrained, so we dropped the abstract, but if we had one, it would read like this:

Many programmable software transformation systems are based around novel domain-specific languages, with a long history of development and successful deployment. Despite their reasonable maturity and applicability, these systems are often discarded as esoteric research prototypes partly because the languages are frequently based on less familiar programming paradigms such as term and graph rewriting or logic programming, and partly because modern development environments are rarely found for these systems. The basic and expected interactive development aids such as source code navigation, searching, content completion, real-time syntax highlighting and error checking, are rarely available to developers of transformation code.

In this system description paper, we introduce Spoofax, an interactive development environment based on Eclipse for developing program analyses and transformations with Stratego/XT -- a language and toolset for developing stand-alone software transformation systems based on formal language descriptions. Spoofax provides the aids mentioned above, in addition to a code outliner and incremental building of projects, and thus significantly eases the development of language processing tools using Stratego/XT. Furthermore, Spoofax is extensible with scripts written in Stratego that are executed within Eclipse, and allow live analyses and transformations of the code under development.

(pdf, bib)

There is already a website for Spoofax, www.spoofax.org, but it's hardly inviting and informative. I have a new one in SVN, but as always, I tend to spend my time hacking code instead of making releases and web pages. I'll try to remedy that very soon.

Together with Eelco Visser, I got a paper (two actually, see the other post) accepted to this year's Workshop on Language Descriptions, Tools and Applications, which is held in Braga Portugal. My visit to IBM Research last summer started me thinking about a good way to integrate existing compiler frontends with Stratego/XT. This is the result, and I think it turned out quite well.

Transformation systems such as Stratego/XT provide powerful analysis and transformation frameworks and concise languages for language processing, but instantiating them for every subject language is an arduous task, most often resulting in half-completed frontends. Open compilers, like the Eclipse Compiler for Java, provide mature frontends with robust parsers and type checkers, but solving language processing problems in general purpose languages without transformation libraries is tedious. Reusing these frontends with existing transformation systems is therefore attractive. However, for this reuse to be optimal, the functional logic found in the frontend should be exposed to the transformation system -- simple data serialization of the abstract syntax tree is not enough, as this fails to expose important compiler functionality, such as import graphs, symbol tables and the type checker.

In this paper, we introduce a scriptable analysis and transformation framework for Java built on top of the Eclipse Java compiler. The framework consists of an adapter extracted from the abstract syntax tree of the compiler, and an interpreter for the Stratego language. The adapter allows the Stratego interpreter to rewrite directly on the compiler AST. We illustrate the applicability of our system with scripts written in Stratego that perform framework and library-specific analyses and transformations.

(pdf, bib)

The prototype code is already available in the Spoofax SVN repo, but I will clean it up and make a separate release once I get a bit of breathing space from my thesis writing.

Anya, Valentin, Magne and myself recently wrote a paper that was presented at GPCE this year. Valentin and me implemented the extension using the Transformers transformation system (Valentin did most of the hacking for C -- I was hacking for TIL. More on that later). We designed the extension to capture most of Magne's original idea into the result. Anya helped out with the writing and finding illustrative examples.

Abstract

Dealing with failure and exceptional situations is an important but tricky part of programming, especially when reusing existing components. Traditionally, it has been up to the designer of a library to decide whether to use a language's exception mechanism, return values, or other ways to indicate exceptional circumstances. The library user has been bound by this choice, even though it may be inconvenient for a particular use. Furthermore, normal program code is often cluttered with code dealing with exceptional circumstances.

This paper introduces an alert concept which gives a uniform interface to all failure mechanisms. It separates the handling of an exceptional situation from reporting it, and allows for retro-fitting this for existing libraries. For instance, we may easily declare the error codes of the POSIX C library for file handling, and then use the library functions as if C had been extended with an exception mechanism for these functions -- a moulding of failure handling to the user's needs, independently of the library designer's choices.

(pdf, bib)

The code for this experiment will be released shortly, once Anya finishes the final set of examples that we will bundle with the release. She's been a bit under the weather lately, but hopefully she'll shake it off pretty soon. I will post about the release when it happens.