Hirrolot

Thanks for commenting! Yes, automatically predicting whether it's beneficial to specialize a function is not implemented. It's under the section "Further research" to find suitable heuristics to automatically emit annotations like those `@extract` that we already have.

This topic was brought up many times in the past. Most of the time it was suggested to use speculative approaches to detect blowups, but I haven't actually seen any attempts to predict them before supercompilation. For example, while I was writing Mazeppa, I've seen many times that blowups occur because some function call gives insufficient information that is subsequently pattern-matched by another function, and since it cannot be properly pattern-matched at compile-time, a lot of code duplication takes place.

I'm leaning towards a kind of "abstract interpretation pass" before supercompilation to approximate "good" and "bad" interactions between functions. After all, given that offline analyses exist even for harder problems such as detecting non-termination, why cannot we understand how supercompilation gives us desirable results?

Thanks, I'm glad the explanations were helpful.

Checking for blowup sort of works; for example, this paper [1] suggests exactly this approach. However, I'm not leaning to it due to the following reasons:

1. The approach involves magic numbers to implement heuristics. They worked for the samples provided by the authors, but will they work for large programs?

2. I think that there's a smarter approach to detect blowups. Specifically, there can be "good" and "bad" interactions in the form `f(g(...), ...)`, where `f` and `g` are functions; an interaction is good if `g` produces information that is known at compile-time (to be subsequently deconstructed by `f`), and bad if it doesn't. If the interaction is bad, `f` and `g` should be transformed separately.

In general, I see manual annotations as a low-level mechanism that can be used for predictable supercompilation. We haven't yet implemented heuristics that would guarantee predictability, but this is on our priority list.

> Are there any other notable differences between this approach and call-by-value constructors?

Yes, lazy constructors must be implemented differently than eager ones. The standard approach is to enclose constructor arguments under an environment of values, just as we implement closure functions. I don't think that supercompilation can remove all laziness from the constructors.

[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.

The name was inspired by Transcendental Étude No. 4 [1], as correctly suggested by the other comment.

[1] https://www.youtube.com/watch?v=MYSFTtYc4P4

I used to define `Maybe` in C as a macro over a tagged union. It really unveiled a number of logic errors at compile-time, but the issue of course is to use this kind of metaprogramming sanely. E.g., instantiating `Maybe` to some other macro `T(a)`, where `a` is some other (concrete) type, would already cause a headache.

Is there any reason to use SML instead of OCaml in 2024?

Yes, features that are easy to use will be more often used, while inconvenient features will be less used. I don't quite see any controversy with my comment.

Typing features affect the way we design APIs. Libraries written in languages with type classes and without them can have completely different designs. If nested pattern matching is not available, this will not affect the APIs, only the function bodies -- because desugaring is local by definition.

In programming language design, we tend to distinguish between global and local analysis. While type checking and elaboration is an example of global analysis, desugaring is inherently local to some piece of code. Therefore, "power" or "expressiveness" usually mean that something cannot be syntactically "expanded"; e.g., while type classes elaborate into explicit dictionaries, they still require information from the type checker, and therefore considered a "real" feature of a programming language. On the other hand, nested pattern matching can be formulated as local syntax transformation, and therefore it doesn't bring anything fundamentally new to the type system or dynamic semantics.

There's also a great talk on the matter [1], if somebody is interested in formalities.

[1] https://www.youtube.com/watch?v=43XaZEn2aLc

I have a star on your repository, so it seems I was looking into it while designing Datatype99 :)

This is more of syntax sugar than power and generality, since nested pattern matching can be mechanically translated into "top-level" matching (e.g., see [1] and [2]).

[1] L. Augustsson. Compiling Pattern Matching. In Functional Programming Languages and Computer Architecture, pages 368– 381, 1985.

[2] P. Wadler. Efficient Compilation of Pattern Matching. In S.L. Peyton Jones, editor, The Implementation of Functional Programming Languages, pages 78–103. Prentice Hall, 1987.

The technique you describe requires us to predict what data should be partially applied (before actually using it), and what data should be applied and used immediately. In contrast, currying/partial application doesn't require this decision from us -- for this reason I consider the functional approach more flexible than the object-oriented one.

In addition to that, I don't always find the constructor/method approach more readable. It _can_ be readable, if you design your API with care; however, it is common to group related data into records in the FP world as well, which mimicks OOP constructors, in a sense.

Currying and partial application are dualities (think of them as function introduction/function elimination), so neither subsumes the other one.

However, I agree with the wording of the original comment: when you _pass_ some arguments to a constructor and then to a method, this is (at least conceptually) partial application.

Supercompilation acts as global program optimization. As far as I'm aware, there were no attempts to supercompile separate libraries.

In fact, supercompilation subsumes many common optimizations, such as function inlining, constant propagation, list fusion, etc. So we can say that it's actually used "to a small degree", although I wouldn't really call it "supercompilation" per se.

The reason that full-blown supercompilation is not used is that it's too unpredictable -- the direct consequence of being too smart. I've elaborated on it in the final section of the blog post.

Haha, awesome!

There are currently no production-grade compilers that make use of supercompilation in the functional world. Memoization is about caching results of pure functions; supercompilation is about deep program transformation.

The solution has exponential time and space complexity, which I noted in the blog post. It is only interesting for its simplicity and as a stress test for supercompilers.