supercompilation-resources

The supercompilation-resources repository serves as a comprehensive collection of materials focused on the concept of supercompilation—a powerful program transformation technique aimed at optimizing computational efficiency through symbolic evaluation. This method generates an enhanced version of a given input program by minimizing computational overhead. At its core, it constructs a process graph representing dynamically encountered configurations (expressions with unknown variables) and transforms loops into specialized edges that connect these configurations. Ultimately, the process graph is residualized into a more streamlined program format, which can be expressed in either the same or a different programming language. With the right extensions, supercompilation can realize asymptotic speedups for certain functional algorithms.

This repository encompasses a diverse range of resources, suitable for both newcomers and those with advanced knowledge, including:

Projects

• SPSC - A Small Positive Supercompiler compatible with Scala, Haskell, Python, Ruby, JavaScript, and Idris.
• HOSC - A higher-order call-by-name supercompiler for a subset of Haskell.
• JSCP - A supercompiler designed for the Java programming language.
• MRSC - A toolkit for rapid design and prototyping of multi-result supercompilers.
• TT-Lite - A supercompiler for a version of Martin-Löf’s Type Theory (MLTT).
• sc-mini - A minimal positive supercompiler developed in Haskell.
• erlscp - A supercompiler pass for the Erlang programming language.
• agda-simple-scp - A simple supercompiler that has been formally verified in Agda.
• Mazeppa - A modern supercompiler for call-by-value functional languages.
• Distiller - Implementation of the distillation algorithm.

Videos

• Nate Nystrom - A Scala Framework for Supercompilation | Scala Symposium 2017

Papers

1986

• Turchin, Valentin F. "The concept of a supercompiler." ACM Transactions on Programming Languages and Systems (TOPLAS) 8.3 (1986): 292-325. Read the paper here

1993

• Glück, Robert, and Andrei V. Klimov. "Occam's razor in metacomputation: the notion of a perfect process tree." International Workshop on Static Analysis, Springer Berlin Heidelberg, 1993. Read the paper here
• Turchin, Valentin F. "Program transformation with metasystem transitions." Journal of Functional Programming 3.3 (1993): 283-313. Read the paper here

1995

• Turchin, V., and A. Nemytykh. "Metavariables: Their implementation and use in Program Transformation." CCNY Technical Report CSc TR-95-012, 1995. Read the paper here

... (the list continues with extensive papers from various years)...

This repository is continuously open for questions and discussions regarding supercompilation in the issues section, making it a collaborative platform for enhancing knowledge in this advanced area of program transformation.