Towards “mouldable code” via nested code graph transformation

•Many program transformations are usefully understood as flow graph transformations.•Correctness proofs require semantics in Kleene algebras and relational categories.•Different layers of nested flow graphs use common data structures.•Graph-based transformation design will enable complex code adaptation mechanisms.•The overall approach goes back to Gunther Schmidt's ideas of “mouldable code”.

Program transformation is currently de facto restricted to abstract syntax tree rewriting. However, many program transformation patterns, in particular in the realm of high-performance code generation, can more naturally be understood and expressed as graph transformations. We describe the conceptual organisation of a system based on application of algebraic graph transformation rules to data-flow and control-flow graphs, and outline the work, both theoretical and of implementation nature, that still needs to be done to realise this long-term project.