Generic Traversal Fusion for Strategic Programming
Master Project of Gijs van der Heide

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.

Rewriting strategies traverse the tree-structured data to apply the rewriting rules. These traversal are “generic” in that they do not inspect the data, but instead use primitives such as all, some, and one to visit children of nodes in the tree, and recursion to traverse deeply. A typical stratego program will traverse and manipulate tree-structured data in multiple passes and sub-passes. Fusing traversals would be an interesting compiler optimisation to explore.

Further reading

• Constructing Hybrid Incremental Compilers for Cross-Module Extensibility with an Internal Build System (2020) by Smits, Jeff and Konat, Gabriël D.P., and Visser, Eelco. (Describes the current compiler setup with blocks connected in Java in an incremental system)
• The old Stratego manual (2008) by Visser, Eelco. (Not the most up-to-date, but pretty complete)

Contacts for the project

• Jeff Smits (TU Delft)
• Jesper Cockx (TU Delft)