TILChairmarks

Software Transformation Systems
The TIL Chairmarks are a small set of little benchmark transformation tasks, all based on the Tiny Imperative Language (TIL). They are called "chairmarks" because they are too small to be called "benchmarks". TIL is a very small imperative language with assignments, conditionals, and loops, designed by EelcoVisser and JamesCordy as a basis for small illustrative example transformations.

It is hoped that this page will grow to have a number of small example benchmarks based on TIL and links to example solutions using a variety of tools and systems. The idea is that the examples be reproduceable - that is, the posted solution should contain everything neeeded for someone else to run the task on their own computer using the tool or system. In this way they can see all of the steps and artifacts involved in doing the job.

The purpose is more one of understanding than one of comparison, and the idea is to start small so that everyone will show their tool's method here - although if things work out we may be able to grow this idea into a set of real comparative benchmarks in the long run.

TIL Training Set:

TIL Chairmark 1: Parsing (JamesCordy - 29 Apr 2005)

  • Let's start small: the purpose of this one is to show differences in how the basic grammatical/lexical specs to support transformation of a language are done using different tools, and to create the basis in each tool for other Chairmarks. The TIL grammar can be found on the Tiny Imperative Language page.

  • 1.1 Basic Parser / Syntax Checker: Parse input and check for syntax errors (output format irrelevant)

  • 1.3 Language Extensions: Language extensions and dialects are the meat and potatoes of source transformation. Implement parsing of a language extension to TIL to the parser and pretty-printer above

TIL Chairmark 2: Restructuring (JamesCordy - 22 Aug 2005)

  • Classical restructuring: the purpose of this one is to show differences in how basic simple statement-level restructuring tasks are expressed using different tools. These solutions should normally be based on the parsers and pretty printers from Chairmark 1. However, because they are restructuring tasks, it would also be valid for them to assume well-formed input, since syntax-checking could be a separate screening task.

  • 2.1 For-to-Nondeclaring-For: TIL's for loop automatically declares the control variable; possibly this should not be the case. If that change happens, this transformation will fix old TIL programs by automatically introducing explicit declarations for control variables in all for statements

  • 2.2 For-to-While: Possibly it was a mistake to add for loops to TIL. If for loops are removed, this transformation will restructure all for-loops in a TIL program to their while equivalents

  • 2.3 Declarations-to-Global: Even though TIL declarations seem to be able to appear anywhere according to the grammar, their meaning is apparently global (or is it?) In this transformation we make the true meaning of embedded declarations explicit by promoting all declarations to one global list at the beginning of the program

  • 2.4 Declarations-to-Local: Possibly TIL actually ought to have separate traditional nested scopes for each statement list (e.g., inside each then part, else part, loop, etc.) If that is the case, then good style should keep all declarations as local as possible. In this transformation we move every declaration to its most local context. It might be interesting to run this one on the output of the previous one. Note that there are several quite distinct different ways to achieve this result

  • 2.5 Goto Elimination: A popular and industrially relevant application of source transformation. In a dialect of TIL with statement labels and gotos added, recognize and eliminate while-equivalent goto structures

  • 2.6 Refactoring: Probably the most common application of source transformation. In the extension of TIL with functions, recognize and refactor one or more bad smells

  • 2.7 Language Dialect Implementation: Implement a language extension by transformation to the core language, with or without library calls. In the extension of TIL with modules (anonymous classes), implement the module extension by reduction to the function extension without modules

TIL Chairmark 3: Optimization (JamesCordy - 22 Aug 2005)

  • Classical source level optimizations: the purpose of this one is to show differences in how the basic source-level optimization tasks are expressed using different tools. These solutions should normally be based on the parsers and pretty printers from Chairmark 1. However, it would also be valid for them to assume well-formed input since syntax-checking could be a separate screening task.

  • 3.3 Strength reduction: Recognizing and implementing opportunities to reduce ** to *, or * to + using loop iteration

  • 3.5 Statement folding: Recognizing and optimizing compile-time known if statements, and possibly while and for statements

  • 3.6 Loop unrolling: Unrolling for loops with known bounds

TIL Chairmark 4: Static and Dynamic Analysis (JamesCordy - 22 Aug 2005)

  • Software analysis tasks: the purpose of this one is to show differences in how simple static and dynamic analysis tasks are expressed using different tools. These solutions should normally be based on the parsers and pretty printers from Chairmark 1. However, it would also be valid for them to assume well-formed input since syntax-checking could be a separate screening task.

  • 4.3 Self Tracing Programs: Transform a TIL program to a self-tracing version of itself, that prints out each statement as it is executed. This is a model for a large number of source transformations used in instrumentation and dynamic analysis tasks such as test coverage and dynamic flow analysis

  • 4.4 Type Inference: TIL declares untyped variables, originally intended to be all integer. However, the addition of string values leads one to wonder if "untyped" means dynamically typed, allowing for string variables. If so, probably we want to make these types explicit and make TIL strongly typed sometime. This transformation infers the type of every variable in a TIL program from its uses and explicitly adds types to declarations using a new form: "var x: integer;" where the valid types are "integer" and "string". Variables of inconsistent type should be flagged as an error

  • 4.5 Static Slicing: Forward and / or backward slice of a program given a marked statement as criterion

  • 4.8 Unique Renaming: Unique renaming gives scope-independent names to all declared items in a program, so that a relationship database extracted will not have ambiguities in entities. In the module extension to TIL, uniquely rename all declared items to reflect their scope

  • 4.9 Design Recovery: Creation of a relationship database for the entities of a program

  • 4.10 Design Analysis: Querying of a relationship database to check for architectural flaws

  • 4.11 Semantic Markup: Marking up program statements or expressions using some semantic property inferred from a relationship database

  • 4.12 Program metrics: McCabe? cyclomatic complexity, function points or the like

  • 4.13 Abstract Interpretation: Interpret the TIL program in some semantic domain other than the value domain

TIL Chairmark 5: Language Implementation (JamesCordy - 22 Aug 2005)

  • Compilers and Interpreters: the purpose of this one is to show how simple imperative language compilers and interpreters are expressed using different tools. These solutions should normally be based on the parsers from Chairmark 1.

  • 5.2 TIL Compiler: Compiling TIL programs to byte code by source transformation / rewriting

  • 5.3 TIL Machine: Byte code machine simulator using source transformation / rewriting


Page begun by JamesCordy - 29 Apr 2005; last revised by JamesCordy - 7 May 2009