What is it

This project has several goals.

  • use strategic term rewriting as DSL for program transformation to build interpreter and supercompiler (explore pros and cons);
  • reuse interpreter (or it's parts) to write configuration tree builder;
  • build environment to experiment with supercompiler.

Running the project

  1. You need Eclipse. Tested for Eclipse 3.5.0 (Helios) and 4.2.0 (Juno)
  2. Install Spoofax 1.1 (use "Help/Install New Software...", update site URL: Details here
  3. Clone this project and add to workspace.
  4. Build project (from menu "Project/Build Project" or right-click on build.main.xml and choose "Run as/Ant Build")
  5. Now you can run examples from "test" folder.

Eclipse can mark some files with errors even after successful build. But when you open such files this mark goes away. I think, it's a Spoofax issue.

Simple Lazy Language (SLL)

This project is inspired by minimal supercompiler written in Haskell [1]. Language considered in the project is "Simple Lazy Language" - a first-order functional language that corresponds to M0 language from [2].

Spoofax and Startego

Spoofax Language Workbench [3] used as primary tool for writing interpreter and supercompiler. Spoofax is based on Stratego, which is a transformation language with programmable rewriting strategies and Syntax Definition Formalism, as language for grammar definition. Spoofax works on Eclipse platform and allows one to create full-featured IDE plugin with syntax highlighting, perform semantic analysis and context completion.


You can run, trace, apply transformations to source program and immediately get the result.

/ib_soft/stratego-sll/raw/default/media/sll-editor-run.png /ib_soft/stratego-sll/raw/default/media/sll-editor-deforest.png

As a result of transformation (deforestation, for example) you get another program that can be ran from the same "Transformation" menu.

Already done

  • interpreter
  • tracer(as list of interpreter steps)
  • configuration tree building/folding (no generalization yet)
  • program generation
  • deforestation

To be done

  • generalization
  • positive information propagation
  • explicit parameterization of configuration tree builder by folding strategy

Stratego pros and cons


It's convenient to build rewriting interpreters. See, for example [4]. Configuration tree manipulations also very convenient with generic rewriting strategies.

For example, simplification used to deforest program:

simplify = bottomup(try(remove-transient))

remove-transient: Node(t, Transient(n)) -> n
  where <not(is-base(|t))> n

is-base(|t) = collect-one(?Fold(t, _))

Great support from Spoofax and Eclipse environment.


Dynamic typing. This is significant for writing big programs. But here we have some interesting alternatives:

Poorly documented some features - dynamic rules, Name Binding Analysis (NaBL).


[1]Ilya Klyuchnikov. The ideas and methods of supercompilation. Practice of Functional Programming, 7, 2011. In Russian.
[2]Sørensen M. H.— Turchin’s Supercompiler Revisited: an Operational Theory of Positive Information Propagation. — Master’s thesis, Københavns Universitet, Datalogisk Institut, 1994.
[4]Eelco Dolstra, Eelco Visser. Building Interpreters with Rewriting Strategies