Having your compile-time cake and eating it too

22 points by emschwartz

andrewrk

Programmers should have to explicitly run things at compile-time. The language shouldn’t do it for them.

Most programming languages disagree with this, including C:

char array[3 + 4]; // OK

It only worked because the expression was compile-time known. If we use a runtime-known value, it fails:

int len;
char array[len]; // error: variable length array declaration not allowed at file scope

Here the language ran 3 + 4 at compile-time. So why doesn’t this work?

static unsigned len() { return 3 + 4; }
char array[len()]; // error: variable length array declaration not allowed at file scope

This is silly. Every language can and should support this. No special keyword needed.

matklad
I wouldn’t agree that this is 100% silly. Some functions can be run at comptime, and some can’t, and that depends on function’s implementation. So you need to choose between:
- Not annotating “can run this function at comptime”, which means that changes to body of the function can break downstream code without breaking function’s contract, which at least in theory complicates semver story. (*)
- Annotating comptime-safe function, which adds a whole dimension to your type system unless your type system is already powerful enough to express this.
- Relying on privacy here (can only run stuff from current CU at comptime), such that changes to comptime-safety can only break your own code. Which I think works, but significantly restricts what you can do there.
So I don’t think this is 100% clear case.

Though, I am at 0.7 that it would’ve been better for Rust to allow calling any function at comptime, and to rely on culture&linting to keep this a theoretical semver problem, rather than a practical sevmer problem, the same way it currently relies on culture to limit the prevalence of unsafe code.

(*): I think this is meaningfully different from changes in runtime behavior breaking downstream program. If sorting function promises stability in the docs, and then becomes unstable in a patch release, that’s the upstream bug. If sorting function explicitly not promises stability (while actually being stable), that’s a bug in the downstream code. If sorting utility doesn’t say anything about stability, it’s a gray area. With const fn, you effectively add a huge gray area to more or less every function.

EDIT: this = “calling any function at compile time”, not “having explicit sigil to demarcate comptime evaluation”.
doug-moen

The ability to call an arbitrary function at compile time raises some tricky issues that could cause a lot of implementation and/or specification complexity. Especially if the compiler decides to do it automatically based some criteria. What are the criteria? I would argue that the compiler’s choice to automatically evaluate a constant expression should not change the result, vs what the result would be if the expression was not compile-time evaluated. That design principle might lead to complex restrictions on what functions can be called at compile time, or it might lead to a more complex implementation.

Cross compilation raises some issues, if the constant expression evaluates to a different value on the development machine and the target machine. Eg, floating point expressions can have a lot of variability in what numbers are computed, across different target CPU architectures and operating systems and system libraries. Maybe floating point expressions are excluded from compile time evaluation, or maybe the cross compiler emulates the floating point behaviour of the target platform?

What if the constant expression involves a call to a function in an external library, that might be precompiled? Does the compiler load the DLL and call the function at compile time? What about side effects, or cross compilation? Does it prohibit compile time evaluation in this particular case? In the latter case, moving a function out of the current module and into a library might cause code to stop compiling.

What if the function being called at compile time throws an exception? What if the language supports algebraic effect handlers, and an effect is raised while the function call is running? A function might have a pure functional interface (no observable side effects), but it might allocate memory while it is running. Can these functions be called at compile time? It seems perfectly reasonable to want constant expressions involving bignum arithmetic to be evaluated at compile time, but you might be using a bignum library that allocates memory.

Sorry, I know that Zig supports compile time evaluation of constant expressions, but I don’t know how it answers these questions.

In any case, I think it is easier to resolve these issues if the language is designed from the beginning to support compile time evaluation, rather than retrofitting it into an existing imperative language. I’m not sure that every language can and should support this, because I think it could be a big can of worms for many languages.
adam_d_ruppe

Here the language ran 3 + 4 at compile-time. So why doesn’t this work?

You probably know this, but this is exactly the history behind D’s compile time function evaluation (aka CTFE) feature: it was extending constant folding to function results. Just seemed like an obvious thing to do. Then over time, it grew more and more capabilities.

Though, you’re right 3+4 will be compile time evaled almost anywhere, even in an otherwise runtime context… but the D rule for functions is they will be run at compile time only when the result must be known at compile time, where the context gives the compiler no other choice but try or error. This might not be as explicit as the blog author wants, but it is pretty explicit once you know how to read it.

jado

To understand what type weird_function returns, you’ll need to understand exactly how ListIfOddLength works. You’d have to know what % means and what to_string does. … With silly type-to-type functions like this, you lose the ability to reason about your program.

I disagree that this example even showcases an increased difficulty in reasoning about these kinds of functions. Since the type-level operators are the same as the value-level operators, I can parse the ListIfOddLength function, however weird it is, faster than any spelling of the same idea in TypeScript/Rust/Scala/etc.

If anything, those HM++ type systems make it harder to reason about more complicated types, requiring new syntax or macros for the same concepts. Zig closes that gap, letting me use my existing taxonomy at the type-level.

Yes, you heard it here first: types are not values. Especially if you want the compiler to do logic and proofs with them, like Hindley-Milner requires. Zig tried having types be values, and it led to stuff like weird_function where you don’t know what type things are until you compile your program, which defeats the whole purpose.

Reports of Zig’s incongruence with IDEs are greatly exaggerated. ZLS has existed for years, letting you see the types of things “before you compile”. I will be continuing to think that types are values.

janus

How do HM++ systems require new syntax? In Lean, it doesn’t seem like there is special syntax for dependent types, they reuse the syntax for rank 1 polymorphism.
- jado
  
  I was using “HM++” to refer to the list of languages the author says use HM, the ++ coming from the non-HM-compliant / undecidable additions. Whereas dependent typed languages I would throw in the category of not requiring new syntax.
matklad

However, things in code objects shouldn’t be restricted by traits. This is unfortunate, but otherwise it would just be impossible to make many of our code-generating functions.

This is the central tension here.

You can say that function only access parameters via interface specific in the signature. Than you get declaration type-checking, nicer error messages, true separate compilation even, if you try hard enough, but you are severely restricted in what your comptime reflection can do.

Or you can say that comptime reflection can do whatever, and then your signature is a mere suggestion. At which point, why have traits at all? You’ll get much smaller language without them!

I don’t have a good feeling for midpoints. What if we do “suggestion” signatures (I think concepts work that way)? Would it be genuinely useful? Or just extra complexity, as it doesn’t change the fundamentals?

Or can we perhaps make signatures expressive enough? E.g., a generic to_json function expresses it in the signature that every field is convertible to JSON?
dataangel

To get there, we’ll add code objects (Code), which are comptime-only strings that describe source code. You’re free to model them as ASTs, but I think that encourages devs to overuse them.

Why? If you don’t someone is going to make turning the strings into an AST at compile time a library anyway.
runxiyu

The title doesn’t make much sense to me.
- fanf
  
  It’s a strange idiom that doesn’t make much sense to many native speakers either :-)
  
  https://en.wikipedia.org/wiki/You_can't_have_your_cake_and_eat_it