Compiler Optimisations for Strategic Programming

Compiler Optimisations for Strategic Programming
Master Project

Project description

Strategic Programming is a programming paradigm popularised by the Stratego programming language. Stratego is a term rewriting language that operates on tree-structured data. Labelled rewrite rules are applied to a tree with a rewriting strategy, but in Stratego you can write such strategies yourself. This gives you a programming language that resembles pure functional programming, but coming from a different tradition.

The Stratego compiler is written in Stratego with a bit of Java and is compiled to Java. Both language and compiler design are influenced by its original compile target of C though. And we suspect the code generation patterns to Java are suboptimal. So the goal of this project is to discover better code generation patterns from Stratego to Java. Some ideas we could try:

Avoid dynamic dispatch, use static methods
Add a constant pool back in, it got removed when the compiler was made incremental (the old constant pool approach was incompatible, needs a new solution)
Use Trowable (Java Exception mechanism without the expensive part of building up the stack trace) instead of returning null on failure and having null checks everywhere
Create a translation from Java stacktrace to Stratego stackstrace and remove the dynamic stacktracing of Stratego

There are two approaches that I think are reasonable:

Adapt the current compiler. Upsides: it works, there are plenty of example Stratego programs, there is a benchmarking setup, you contribute to the real deal. Downsides: large codebase you need to get to know a bit to change it, technical debt, old tech stack you probably don’t know.
Build a new backend. Upsides: less technical debt, more flexibility in designing the codegen. Downsides: have to redo existing work, doesn’t necessarily integrate with the running system.