[Haskell-cafe] Re: What is the current state of affairs with supercompilation?

[Peter A. Jonsson]

Hi Eugene,

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 [1], 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 [2]
- An Algorithm of Generalization in Positive Supercompilation.[3]

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 [4]
- 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  
supercompiler). [5]
- Proving the equivalence of higher-order terms by means of  
supercompilation. [6]

>  - What are some solved problems and some open problems in  
> supercompilation?

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.

Kind Regards,

Peter

[1] http://community.haskell.org/~ndm/supero/
[2] ftp://ftp.diku.dk/pub/diku/semantics/papers/D-300.ps.gz
[3] http://citeseerx.ist.psu.edu/viewdoc/download? 
doi=10.1.1.49.1869&rep=rep1&type=pdf
[4] http://community.haskell.org/~ndm/thesis/
[5] http://www.springerlink.com/content/c8623847257w22j9/
[6] http://pat.keldysh.ru/~roman/doc/Klyuchnikov,Romanenko-2009-- 
Proving.the.Equivalence.of.Higher- 
Order.Terms.by.Means.of.Supercompilation.pdf