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.

Downvoted your comment because of spelling. Consider learning some English grammar.

> I'm pretty sure that this is one of the unsafeties that rust borrows from c

But integer arithmetic is safe in terms of Rust.

> Checking every addition adds a massive slowdown

It only does so for debug mode. In release mode, it uses modular arithmetic.

Thanks for your comprehensive answer, it's really nice to see that async traits and etc. might be coming soon.

Async traits, async `Drop`, TAITs, variadic generics (unlikely they will every be implemented), generic closures, optional/named parameters, anonymous enums. These are the first that came to my mind.

Exactly. The point is that most Rust libraries use semantic versioning, which actually forces you to determine if the change you've made to your library is backwards-compatible or not. I think it's a good practice but it's unclear to me how it should be applied to `const` functions.

> As long as the time is much larger than it takes to handle the old statement limit it is preserved.

As a library developer, how can I know that?

> The old version might have prevented your code from compiling as mentioned in the notes.

Does it mean that rustc tracks function BC? I think I've misunderstood you.

Since I entered Rust (circa 2018-2019) and async/.await was stabilized, I started to lose my expectations on the growth of the language. Almost every language issue I wanted to be resolved is still unresolved (besides GATs, which are great but took a really long time to be shipped). Meanwhile, the community doesn't cease to perpetually endorse the language; you literally see top-scoring posts like "I felt in love with Rust, can't stop loving Rust, it's so wonderful" every month or so on r/rust, a lot of reaffirming articles expounding on the "success" of the language, collective exultation when it's again most loved on SO, etc.

The current situation with the language is somewhat sad.

> To avoid having long compilations without feedback, the compiler will always emit a message after your compile-time code has been running for a while, and repeat that message after a period that doubles each time.

Is this "period" measured in statements or computer time?

> By default, the compiler will also emit a deny-by-default lint (const_eval_long_running) after a large number of steps to catch infinite loops, but you can allow(const_eval_long_running) to permit especially long const evaluation.

So the default behaviour now is to nonetheless "catch" infinite loops by default? Why not make the default behaviour to just notify a user by emitting a message after some time (as described)? If rustc "catches" infinite loops by default, how is backwards compatibility preserved with respect to `const` functions? If I split one statement into two in `const fn`, do I break BC?

> Surprisingly, these particles were found decades ago by Alonzo Church, the inventor of Lambda calculus long before electronic computers even existed!!

Lambda calculus is not the simplest computational device based on functions; with SKI calculus, you only need to define two combinators (S and K) to perform any conceivable computation. Going further, you can define the full SKI calculus with only a single combinator called Iota, so in fact, you only need one function to perform any computation. Yes, Turing tarpits exist, why that should be a revelation? Practical programming languages (both functional and imperative and object-oriented) tend to find a compromise between a minimal core and ergonomics, otherwise the result will be disastrous.

> the great benefit of the y-combinator is that it permits indefinite iteration in a system that seems at first glance to not support iteration at all

This is only the case for untyped systems. If we try to type the Y combinator, we will eventually need some notion of recursion. For example, in Haskell/OCaml we can type it with iso/equi-recursive types. How many truly untyped systems we use in practice?

The Y combinator as a counterexample of termination is a great insight though!

You keep answering with the same words though. My question was _where_ the Y combinator is useful, not _what_ it is designed for, which I am of course aware of.

What are the useful cases of the Y combinator then? (I don't say that the lambda calculus is useless, I was responding to a comment that claimed the lambda calculus is useless without the Y combinator.)

> which is what makes it a useful concept rather than an arbitrary bundle of rules.

I cannot recall a single practical FP language based on the Y combinator for recursion. The typical approach is to extend lambda calculus with a separate recursion primitive.