spsc

A Small Positive Supercompiler in Scala, Haskell, Python, Ruby & JavaScript

This site is associated with the project https://github.com/sergei-romanenko/spsc.

A supercompiler is a program transformer that traces the possible generalized histories of computation by the source program, and builds an equivalent target program, whose structure is, in a sense, “simpler” than the structure of the source program. The simplification is achieved by removing certain “redundant” actions from the source program.

The goal of the project is to implement in Scala a positive supercompiler that is very close to the one described in papers by M.H.Sørensen, R.Glück, and N.D.Jones.

The current version of spsc can be run as a command-line application or accessed as a web-application.

SPSC deals with programs written in SLL, a simple lazy first-order functional language. The intended operational semantics of the language is normal-order graph reduction to weak head normal form.

SPSC Lite

SPSC Lite is a minimalistic version of SPSC, which may be useful for educational purposes and as a starting point for experimenting with supercompilation.

Currently, there are 4 versions of SPSC Lite written in: Scala, Haskell, Python 2.6 and Ruby 1.8.

News

2018, February A version of SPSC Lite written in Idris 1.2.

2009, September A version of SPSC Lite written in Ruby 1.8.

2009, August A version of SPSC Lite written in Python 2.6.

2009, August A version of SPSC Lite written in Haskell.

2009, June The paper SPSC: Суперкомпилятор на языке Scala.

2009, May The paper SPSC: a Simple Supercompiler in Scala is accepted for PU’09.

Documentation