What is supercompilation?

Question

Short and sweet: I've seen several sources talking about "supercompilation". But I have yet to find one single document anywhere on the face of the Internet which describes what this is. Presumably because it seems simple enough to whoever that it isn't even worth explaining.

Does anybody know what this actually is?

Answer 1

Supercompilation can be approached as a generalization of partial evaluation. The idea behind partial evaluation is that many parts of a program can be evaluated at compile time, and so should be. Supercompilation extends this, evaluating things that can't be fully done at compile time as well, like turning map f (map g xs) into map (f . g) xs without anything besides the definition of map (At least I think I got partial evaluation right - I've only read much about supercompilation).

Another way to look at it is as a combination of many other optimizations, like deforestation, specialization, and inlining. By acting as if it already knew the inputs to functions and evaluating, it can get a more direct method of calculating the result - it can get rid of intermediate data structures by seeing how they will be used or it can plug in all possible values and then wrap the result in a case, or do something else with its pretend values.

Max Bolingbroke has a number of useful papers on the subject - I recommend the first one, Supercompilation by Evaluation, as an introduction. Section 2 introduces the subject by example and the rest, while a bit difficult to get through, is very informative about the process. Neil Mitchell also has a number of good presentations describing it.

I hope that helps.

Answer 2

From Wikipedia on Metacompilation:

Metacompilation is a computation which involves metasystem transitions (MST) from a computing machine M to a metamachine M' which controls, analyzes and imitates the work of M. Semantics-based program transformation, such as partial evaluation and supercompilation (SCP), is metacomputation.

More about Metasystems on Wikipedia.

I am not knowledgeable on the subject, but I'll give my understanding of the description. Say we had a simple program that could copy stdin to stdout. This would be our computing machine M. Our metamachine M' is a second program that takes the source of M as input (or is otherwise constructed to inherently know of M) and is therefore able to understand not only what M does, but how it does so.

If my understanding is correct, then the obvious question is why do we care about M'? What comes to my mind is automatic optimisations. If we can understand both how M works and what M is trying to accomplish, M' may solve ways to improve the operation of M, either in space or time. Furthermore, and importantly, M' may substitute M since M' can accomplish whatever M did. This means that M'' can improve on the ways M' optimised M, and subsequently replace M', and so on.