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

[Eugene Kirpichov]

Thanks you very much Peter, that helped quite a lot!
I'll be looking into all the material you provided.

2009/10/25 Peter A. Jonsson <pj at csee.ltu.se>:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru