TILChairmarks

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 Training Set: A small set of example TIL programs to test on

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)
  • TIL Parser using TXL

• 1.2 Pretty Printer: Parse input and implement the identity transformation with pretty-printed output
  • TIL Pretty Printer using TXL

• 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 Begin-End Extension using TXL
  • TIL Array Extension using TXL^?
  • TIL Function Extension using TXL^?
  • TIL Module Extension using TXL^?

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
  • For-to-Nondeclaring-For using TXL

• 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
  • For-to-While using TXL

• 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
  • Declarations-to-Global using TXL

• 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
  • Declarations-to-Local using TXL

• 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
  • Goto Elimination using TXL

• 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.1 Statement-level code motion: Moving invariant assignments / computations out of while loops
  • Lift Invariant Assignments using TXL
  • Lift Invariant Assigned Computations using TXL (more sophisticated, with variable renaming)

• 3.2 Common subexpression elimination: Recognizing and factoring out common subexpressions to new temporary variables
  • Common Subexpression Elimination using TXL

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

• 3.4 Constant folding: Recognizing and optimizing compile-time known variables and expressions
  • Constant Folding using TXL

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

• 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.1 Something about redundant declarations: Detecting and removing unused declarations
  • Removing Redundant Declarations using TXL

• 4.2 Something about statistics: Counting the numbers of statements of different kinds in a program
  • Statement Statistics using TXL

• 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
  • Self Tracing Programs using TXL

• 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
  • Type Inference using TXL

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

• 4.6 Clone Detection: Clone detection of repeated statements or sequences of statements in a program
  • Exact clones using TXL
  • Consistently renamed clones using TXL

• 4.7 Syntactic Markup: Marking up program statements or expressions with some structural property
  • Syntactic markup using TXL

• 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.1 TIL Interpreter: Executing TIL programs by source transformation / rewriting
  • TIL Interpreter using TXL

• 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