Skip to topic | Skip to bottom


EelcoVisser.OptimizersFromInterpretersr1.2 - 03 Jan 2002 - 10:15 - EelcoVisser

Start of topic | Skip to actions

Deriving Optimization Strategies from Evaluation Strategies

An program optimizer reduces a program to a more efficient program with the same behaviour. This often means that part of the computation the program defines is performed at compile time. This suggests that it should be possible to derive an optimizer from an interpreter. If this can be done systematically we would obtain a correct

In several prototypes interpreters were defined using the following approach:

  • Define a set of constant folding rules defining computations
  • Define an abstract syntax tree traversal that defines the control flow

Using this approach it is very easy to make different versions of an interpreter defining different evaluation strategies or incorporating new language constructs. The approach has been used succesfully for the following languages:

  • Stratego:TigerCompiler
  • Stratego:RhoStratego
  • Stratego:StrategoScript

The paper Stratego:BuildingInterpretersWithRewritingStrategies describes the approach.

Now the question is whether optimizers can be obtained by taking a different evaluation strategy (and maybe adding a few rules).

In the end it would be interesting to automatically derive an optimizer from an interpreter. In this project we restrict the question to exploring systematic derivations by hand.

Rearch Project

  • Define/take an interpreter for a language using rewrite rules and a strategy for combining them

  • Explore optimizations for this language

  • How is an optimizer related to the interpreter

  • What extra rules are needed for optimization?

  • How does the strategy differ from the evaluation strategy?

  • Does an interpreter provide enough information to optimize programs?

  • In practice optimizers are quite different beasts than interpreters. Why?

-- EelcoVisser - 27 Nov 2001

You are here: EelcoVisser > OptimizersFromInterpreters

to top

Copyright © 2003-2018, Software Engineering Research Group, Delft University of Technology, The Netherlands