author: Bui Hong Thien Nhat
title: Improvise. Adapt. Overcome. Transform.
keywords: language design, program transformation
topics: Algorithms and Data Structures , Case studies and Applications , Languages , Software Technology
committee: Vadim Zaytsev
started: November 2020


Many program transformation and model transformation frameworks work as follows: there is a predefined (sometimes extendable) suite of transformation operators, usually with readable names like rename or replace, and then the transformation itself can be expressed as a sequence of superimposed "calls" to these operators: first we rename A to B, then replace X with Y, etc. This design mimics the so called instruction set architecture which views a computing unit as a machine capable of executing any instructions from a given set (this is a very old idea, the first instruction set was designed by Kathleen Booth in 1952, but it is still dominant in both hardware and software).

However, this is not the only possible way. In Negotiated Grammar Evolution, it was proposed (for grammars, but the same holds for any model or program) to have a negotiated transformation framework, in which case the end result will be a compromise between the transformation engine (the "computing unit") and its user (the side requesting the transformation). For instance, renaming can go like this:

  • [User to Engine] rename A to B
  • [Engine to User] A not found, do you mean A1?
  • [User to Engine] rename A1 to B
  • [Engine to User] B is already in use, would you rather have B1 or C?
  • [User to Engine] rename A1 to C
  • [Engine to User] done

When this is explored minimally or not at all, the transformation engine works exactly like the normal non-negotiating one. When this is pushed to the other extreme, we enter the domain of unification with backtracking and other powerful features. The negotiated setup allows to search for sweet spots between the two extremes. One of these sweet spots is automatic negotiated transformation based on programmable strategies, which is exactly what this project is supposed to be about.

Expected workflow

  • Leverage an existing framework for parsing (LLVM, JDT, Roslyn, anything — student's choice)
  • Design a language to express negotiation strategies (there are some useful ideas to reuse from the cited paper, but this is still a very open-ended creative process) and a language for actual transformations (this is easier: can be textual or pre-encoded in clickable menu items like "extract method")
  • Implement it either as a plugin or as a command-line tool
  • Evaluate the expressive power and usefulness of the result by encoding some sensible strategies and running them on real open-source code.