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
- You need Eclipse. Tested for Eclipse 3.5.0 (Helios) and 4.2.0 (Juno)
- Install Spoofax 1.1 (use "Help/Install New Software...", update site URL: http://download.spoofax.org/update/stable/). Details here
- Clone this project and add to workspace.
- Build project (from menu "Project/Build Project" or right-click on build.main.xml and choose "Run as/Ant Build")
- 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 . Language considered in the project is "Simple Lazy Language" - a first-order functional language that corresponds to M0 language from .
Spoofax and Startego
Spoofax Language Workbench  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.
As a result of transformation (deforestation, for example) you get another program that can be ran from the same "Transformation" menu.
- tracer(as list of interpreter steps)
- configuration tree building/folding (no generalization yet)
- program generation
To be done
- 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 . 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.
|||Ilya Klyuchnikov. The ideas and methods of supercompilation. Practice of Functional Programming, 7, 2011. In Russian.|
|||Sørensen M. H.— Turchin’s Supercompiler Revisited: an Operational Theory of Positive Information Propagation. — Master’s thesis, Københavns Universitet, Datalogisk Institut, 1994.|
|||Eelco Dolstra, Eelco Visser. Building Interpreters with Rewriting Strategies|