Introduction to Supercompilation

Abstract:

High levels of abstraction, the possibility to reason about software components in isolation, and the ability to compose different components together are crucial to improve productivity in software development. A pure functional language gives the ability to reason equationally about programs, along with features such as higher-order functions that aid programmer productivity. While these mechanisms increase productivity they also come with a problem known as the 'abstraction penalty': as the programmer increases the abstraction level to deal with system complexity, the performance of the resulting program decreases.

I will show, through examples, how the abstraction penalty can be automatically removed through supercompilation. Anyone who has taken a basic course in functional programming should be able to follow my examples. I will briefly survey previous work and identify some open problems.