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.

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.

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.

I've written a proposal in concert with Anya and Martin about namespaces in Stratego.

I think we have most things ironed out so that it is both backwards compatible, supports separate compilation and is rather clean, nor does it require extensive changes to the Stratego compiler.

The troublesome spots are dynamic rules and parameterised modules. I am not entirely convinced that we have solved the dynamic rules issue sufficiently, but a few more days and I may be convinced.

Parameterised modules, however, may not make it into the first public proposal. The main issue with parameterised modules is as follows:

• I want every module to be compiled separately, to an .o file
• I want some modules to be higher-order: they should accept another module as a parameter at import time. I.e. imports lib[linux] will import the generic Stratego library instantiated for the linux platform.
• Inside the lib module, I will not care which platform implementation I receive, as long as it follows the correct interface, and is provided to me before final compilation.
• The same module can be instantiated multiple times, each time with a different value for its parameters

.

• No changes to the runtime should be necessary. Most specifically, I don't want to pass around context state between modules.
• All intermodule references should be resolved at compilation time.
• A module may exist as a .so, as an .o
• The module that imports a parameterised module may eventually be compiled into either a .so or a binary program.
• I want as little code duplication as possible

.

I have solved most of these issues with some recent ELF hacks, but it only works reliably in the absence of .so files. These are non-issues for the JVM, and will be available directly there when we get the JVM backend running.

Talked to Martin about the possibility of a JVM backend for Stratego. He told me he had considered it, but that it wasn't top priority.

The main problem, Martin pointed out, is that vital parts of the Stratego library has been rewritten in the later years from an abstract level of readfile to fopen, thus tieing it tightly to C/POSIX.

Both Rob and me pointed out that we could add namespaces to the library, thus clearly marking out Unix-specific parts and Java-specific parts. Namespaces is something I have wanted to work on anyway.

However, upon later reflection I don't think it is all that desirable to keep the all the legacy code after all. We will undoubtedly write a lot of stuff afresh, for specific purposes related directly to the Java platform.

In fact, if Stratego on JVM is to make any sense, Stratego code must be able to call Java libraries, in which case, the Unix-specific bits of the Stratego library is automaticaly supplanted by the much richer Java library.

Again, with proper namespacing, it will also be obvious for developers when they are relying on Unix-specific or Java-specific library calls.