Implement predictability heuristics

[hirrolot]

We already have the @extract thing, but it is only a low-level mechanism. It is desirable for supercompilation to be predictable both in terms of the supercompiler itself (memory consumption & running times) and residual programs (memory consumption & running times & program size).

There is already some prior work on this matter, see ¹, ², ³, and ⁴.

We can also take inspiration from adjacent fields, most notably deforestation and partial evaluation.

Footnotes

1. Jonsson, Peter & Nordlander, Johan. (2011). Taming code explosion in supercompilation. PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. 33-42. 10.1145/1929501.1929507. ↩

2. Jonsson, Peter A. Time-and size-efficient supercompilation. Diss. Luleå tekniska universitet, 2011. ↩

3. Inoue, Jun. "Supercompiling with Staging." Fourth International Valentin Turchin Workshop on Metacomputation. 2014. ↩

4. Askar, Ammar and Benjamin Delaware. “Tailored Termination for Optimal Supercompilation.” (2019). ↩