[Haskell-cafe] Re: What is the current state of affairs with
Peter A. Jonsson
pj at csee.ltu.se
Sun Oct 25 14:32:55 EDT 2009
here are some answers:
> I'm mainly interested in the following:
> - What supercompilers do exist, except for the ones mentioned above?
We have prototype implementations of supercompilers for both GHC and
the Timber compiler, but they are not yet in a suitable form for
public inspection. Neil Mitchell has the source code to Supero
available on his homepage , which I think uses yhc as frontend and
ghc as backend.
> - What academic organizations do research in the area?
Looking at where the authors of some publications on supercompilation
were at the time of the publication gives some hints:
- University of York: Neil Mitchell, Colin Runciman
- University of Copenhagen: Morten Heine Sørensen, Robert Glück, Jens
Peter Secher, Neil Jones
- University of Liverpool: Alexei Lisitsa
- Russian Academy of Sciences: Sergei Romanenko, Ilya Klyuchnikov
- Luleå University of Technology: myself and Johan Nordlander
> - What papers should be read by someone eager to learn about
> supercompilation and maybe to make research contributions?
If you are interested in program optimization, here's two pointers:
- A Positive Supercompiler 
- An Algorithm of Generalization in Positive Supercompilation.
Combine these two and you have a positive supercompiler for a first-
order functional language, using the notation that is familiar to the
functional programming community.
More recent work on program optimization:
- Neil's thesis 
- There's a number of tutorials available from the group at
University of Copenhagen, all worth a read.
Alexei Lisitsa, Sergei Romanenko, and Ilya Klyuchnikov have used
supercompilation to do verification:
- Verification as a parameterized testing (experiments with the SCP4
- Proving the equivalence of higher-order terms by means of
> - What are some solved problems and some open problems in
The algorithms are quite well-studied with respect to correctness.
There's less material available on actual implementations, and how to
get them to perform well. I haven't seen anything discussing code
explosion and similar practical issues. I don't think anyone has
mechanically verified the correctness of supercompilation.
This is by no means an exhaustive list of everything, but it's
something to start with. I hope it helps.
More information about the Haskell-Cafe