The Scheme is on.

I have had my PS3 for almost a year now. and I've rarely had time to use it. Now that I finally do, I find that it's already outdated: the 1.92 firmware won't allow me to log on to the Playstation Store at all.

I would have upgraded the firmware without a second thought if it weren't for the "RSX issue". In firmwares prior to 2.10, the hypervisor contains a vulnerability which allows the operating system to access the nVidia G70-based GPU. My primary goal for bying the PS3 was to code multicore programs and playing with graphics, so I have some incentive to retain GPU access. Of course, downgrading firmwares isn't possible unless I buy a modchip, and this one is near impossible to solder.

However, even if I keep the RSX hole open by not upgrading the firmware, there's actually no OpenGL implementation that will work with the GPU. The closest thing is the Nouveau driver, but that's a long way off, and nobody appears to be working on the PS3-specific parts. I'm guessing that if anything will materialize from this, it will be far into the future.

All hope is not lost, however. There's a Cell-based driver for Mesa under development by Tungsten Graphics and friends. They claim to want full GLSL support eventually, but that will take a lot of time and effort.

I'll delay the firmware update for a few more days, and check if there are any opportunities I've overlooked. There's something fundamentally upsetting by being at the mercy of big corporations. I bought the box. I want to use it for writing my own programs. Why should that be such a crime?

I decided to take a peek at Ruby again. There's something cute about the language. There's a also a bunch of tiny webapp libraries in their CTAN/CPAN-like gem collection. Doing something quick and really dirt was never easier:)

I then decided to add flickr and twitter feeds to my homepage, but I wanted the page to remain static. I picked down the twitter and flickr ruby libraries and go to work. The stability of these libraries leave something to be desired. It didn't take all that many minutes to debug most of the buggy parts, fire off a couple of suggestions for improvements/bug fixes, and start being productive. Using the flickr API to pick out four random photos from my photostream on flickr:

 flickr = Flickr.new(API_KEY)

  user = flickr.users('karltk')

  if user.photos.length < 4 then
    ps = user.photos
  else
    ln = user.photos.length
    ps = []
    ps.push(user.photos[rand(ln)])
    ps.push(user.photos[rand(ln)])
    ps.push(user.photos[rand(ln)])
    ps.push(user.photos[rand(ln)])
  end
  urls = ""
  ps.each do |p|
    urls += "<a href=\"" + p.url + "\"><img src=\"" + p.source('Square') + "\"/></a>"
  end
  urls

Using the twitter API to fetch my four latest status updates:

  
  feed = Twitter::Base.new('username', 'password').timeline(:user)

  msgs = ""
  feed[0,4].each do |s|
    tm = Time.parse(s.created_at)
    msgs += "<p><a href=\"http://twitter.com/karltk\"><b>(" + tm.strftime("%a %H:%M") + ")</b></a> " + s
  end
  msgs

The stings generated by each of these code fragments are inserted into a plain HTML template. The end result, with the twitter feed showing at the bottom right:

Yes, I know I could've done this more easily using the existing JavaScript snippets provided by Twitter and Flickr, but that is totally beside the point:) Now I have this wonderful cron job running every once in a while instead.

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'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.

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.

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.