Stratego

Lennart Kats, Eelco Visser and myself just got a paper accepted to LDTA'09. The paper is about declarative languages for describing programming editors. The main part of it is Lennart's work,  but it's running on top of the Spoofax transformation infrastructure. The idea is simple: You don't want to fight with Java, complicated APIs and complicated XML when you implement an Eclipse-based editor for your DSL. Instead, you describe your language's grammar with SDF, provide some auxiliary information using our declarative editor languages, and Spoofax/IMP does the rest by generating the editor engine for you.

The abstract explains it in the usual academic style:

Modern IDEs increase developer productivity by incorporating many different kinds of editor services. These can be purely syntactic, such as syntax highlighting, code folding, and an outline for navigation; or they can be based on the language semantics, such as in-line type error reporting and resolving identifier declarations. Building all these services from scratch requires both the extensive knowledge of the sometimes complicated and highly interdependent APIs and extension mechanisms of an IDE framework, and an in-depth understanding of the structure and semantics of the targeted language.

We discuss two examples: an editor plugin for WebDSL, a domain-specific language for web applications, and the embedding of WebDSL in Stratego, used for expressing the semantic rules of WebDSL.

Once I get bibtex-tools running on 64bit again, I'll link to the bib and pdf.

Like last year, I'm going to FOSDEM. Last year, I traveled from Paris with the express train (great experience). This year, it's back to planes again. Not looking forward to the security hysteria.

If you're interested in meeting me there, don't hesitate to fire off an e-mail. 

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.

I finally figured out how to add proper navigation history support to Spoofax today. This one has been bugging me for quite some time. I remember spending far too much time diving through the documentation with the hopes of figuring out how this should be done properly. No luck.

Today I had a flash of inspiration, so I dug into the JDT code base. That code seemed to solve the same problem in a very complicated way, so I didn't want to copy their approach outright. Stymied, I started tracing exactly what happens with the navigation history when positions are placed into it. After a bit of fiddling around, I figured out that when I move the cursor, I should mark the position both before and after the cursor/focus moves to get the behaviour of JDT (which I tried to emulate). I've always only tried saving the editor location state either before I changed it, or afterwards. I also tried all kinds of alternative calls on the EditorPart hierarchy in vain. I now use ITextEditor.setHighlightRange() which appears to do the job, provided I call markInNavigatorHistory() "properly".

Anyway, the lesson is simple: if you call AbstractTextEditor.markInNavigationHistory(), remember to do it twice -- once before you change the editor/focus and once afterwards.

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.

I visited Akim Demaille and his posse at EPITA today, and apparently there still is such as thing as free lunch (although, in my excitement over the good food, I kinda promised to help out with fixing some Stratego issues they are experiencing, so it was not entirely without entanglements).

I got to sit in on one of the bi-weekly status updates for the LRDE. The room numbered a little under 30 people, including students and faculty. They were kind enough to hold the meeting in English so that I could follow it. I found it surprising and very encouraging to have everybody report their progress (and, in a very few instances, lack thereof) in front of the entire lab. I've been missing this in many of the institutions I've been working at. It certainly increases the level of team feeling, and also makes it easier to uncover opportunities for collaboration between the various groups. For example, they all shared a lot of common infrastructure, including setups for newsgroups, a build farm, svn repos, etc.

I met two of the guys from the "previous" Transformers generation, Florian and Maxime. Florian was putting the finishing touches on a visualization tool for ambiguities in Transformers' attributed parse trees. It looked pretty sweet. Maxime was hacking a translator from a DSL for their Olena image processing library.

I also got to meet the new generation of Transformer students. I expect that I'll interact a lot more with them in the coming months, as they come to grips with Stratego.

I'm going to FOSDEM again this year. A bunch of old friends will be coming, so the opportunity is too good to pass up. Also, since I'll be in Paris at the time around FOSDEM, travel is both fast and reasonably cheap. (Three cheers for high speed trains.)

If you're interested in meeting me there, don't hesitate to fire off an e-mail. There's no Gentoo room this year, so I'll be hanging around elsewhere. I'm bound to drop by the Free Java devroom, for sure:) Another gang I'm anxious to meet again are the Nix people.

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...;)