Assignment No. 4 SLP 2011

Navigation

The SLP course

Lab dates / deadlines

  • July 19, 2011; 4.15pm: Sketch solution
  • July 21, 2011; 2.15pm: Present solution

Title

Code transformation and generation

Instructions

Extract a non-trivial source-code transformation or code-generation scenario from the lectures on the TXL cookbook (31 May, 21 June), intermediate code generation (28 June) and code generation (30 June) and implement the scenario in a declarative manner up to a level that you can demonstrate a test case.

Discussion

You can use Haskell, Scala, or Prolog as the implementation language, for example. Some language implementation frameworks of earlier parts of the lecture are acceptable, too: MPS, Converge, MetaML. Parser generators, by themselves, are not suitable for non-trivial transformation and generation problems. Attribute grammars are possibly applicable to intermediate code generation, but they are not applicable very well to code generation and transformation scenarios.

Please make sure to pick a non-trivial scenario from the lectures. In case of doubt, please ask the lecturer, and argue how the scenario is or could be made to be non-trivial. In the following, suggestions are given. (In fact, the number of suggestions exceeds the number of teams. Hence, please pick one of the suggestions, in case of doubt.) Suggestions: i) local-to-global (TXL); ii) global-to-local (TXL); iii) goto elimination (TXL); iv) backward slicing (TXL); v) intermediate code generation by translation to three-address code — preferably for a language with simple scopes; vi) derivation of control-flow graph with basic blocks (see slides 17-20 of code-generation lecture); vii) a very simple code generation with very simple register allocation / assignment (slides 36-41).

In all cases, you need to make clever decisions so that you can test the scenario without implementing a complete frontend.