How is the custom conditional-compilation calculus implemented?

The answer to constexpr has been in front of us the whole time.

I've wondered that even if we add constexpr functions, how do we define the core operations so the constexpr can see them? The answer: we don't. In fact, we can't; the first-principles operations have to be magical. The core routines for the default numeric types use magical types and methods from a BuiltIn module; we have to do the same thing for our constexpr primitives.

But, wouldn't we have to do that primitive work from scratch? Not necessarily; it's already been started! The Boolean operations for conditional compilation do not use the Bool type, but a hard-coded custom calculus (with true, false, !, &&, and ||). We just extend this idea at first for all the default numeric types and Bool, with their states and the operations from the standard protocols they follow. When we gain experience, we add support for the default range types and Optional (when their wrapped type is constexpr-enabled). Then finally add support for String.

For any types and functions we want to make constexpr, their code must be expressible in terms of already-constexpr code, starting from the primitives above. (Functions to possibly make constexpr in user-space can include extensions on the default types that weren't in the original primitive operation list.)

Having worked on the code for conditional compilation in Swift's parser (lib/Parse/ParseIfConfig.cpp), and worked on constant-evaluation subsets of other languages, I do not think the former is appropriate as a basis for the latter: it's very specialized and underpowered code, has almost none of the machinery one needs to do this properly.

There is a much more complete basis for surfacing constant evaluation in the language (i.e. with a const or constexpr keyword) in the already-existing and working mandatory SIL constant folding pass (lib/SILOptimizer/ConstantFolding.cpp), which includes implementations of the builtins and can be extended with extra functions via the @_semantics attribute (eg. see isApplyOfStringConcat which looks for @_semantics("string.concat") that's on the standard library's implementation of func + (lhs:String, rhs:String).

The difficult thing about surfacing constant evaluation in a language (IMO) is that beyond just "knowing that this thing is evaluated at compile time" -- which is not always especially useful -- many people want it as a feature specifically so that it can interact with other static systems in the compiler earlier than the mid-level IR, i.e. the conditional compilation system (as you note) or, more commonly, the type system.

The latter happens in a few surprising yet persistent cases: computing scalar components of types like enum discriminants and pattern constants (in order to check for disjointness, say), and also when people want to statically compute fixed-size array types, which is an immediate request once you add fixed-size array types to the language (and they're on the list of things people have argued for adding to future Swift iterations). This sort of requirement -- constant eval intertwined with type checking -- breaks the phase ordering of a conventional compiler like swiftc, so would be a very significant undertaking. It can be done, but it's a lot of work (eg. watch the very slow process of the Rust compiler shifting from an ad-hoc high-level constant evaluator to the new MIRI evaluator, while trying to carve out a decidable boundary for const evaluation within the type system.)

Indeed, I suspect a major reason why there is a miniature constant evaluator up in the Swift parser is that the phase ordering of the compiler is too rigid to support SIL-ifying compiler-control expressions and evaluating them that early: especially given how much of the language is defined by library code, it's impractical to defer conditional compilation until the presence of a typechecked and lowered stdlib (at least in the current phase-ordering of the compiler). The same is true of the conditional compilation expressions in Rust, FWIW: there's a miniature evaluator for the custom mini-language in attribute expressions, run in early parsing phases, that remains detached from MIRI and probably always will. Not enough of the rest of the world even exists at that point.

(Similarly it's worth noting that LLVM has a gigantic amount of constant evaluation machinery of its own, through many layers of committing-to-facts, all the way down to expressions evaluated in the assembly and linking phases)

It's not ideal to have redundant constant evaluation anywhere at all, but it should be kept to as few as possible, and IMO not replicated yet again at the high level (AST) or in the type system. You really want to centralize as much logic as possible, i.e. by making it possible to synthesize and evaluate small, cheap fragments of that IR, if not in the middle of parsing (which is usually very early, i.e. it even involves masking out unrecognized syntax) then at least by the middle of typechecking.

(Sorry this reply is a bit rambling -- lots to say on this matter and not clear which order it's most useful)

8 Likes

Fortran and C++ (since constexpr support) allow named items as array bounds. How do they do it; do they the phase-order breaking you mentioned Rust trying to do? Do we have to bite the bullet and break phase order to allow looping? Or is there some other way?

C++ constexpr is absolutely terrible to implement: there is basically an AST-based interpreter that supports a limited (but ever larger) subset of the language that kicks in when you try to evaluate the expression. Making an AST-based interpreter is basically duplicating all of the efforts of the next "phase" of the compiler; for Swift that would be SILGen. The problem is even worse in Swift because of the way Swift type inference works: in C++ you can evaluate a constant sub-expression and then use it in a type, but in Swift you're "supposed" to evaluate an entire expression-statement at once (so that type inference can kick in).

We may end up here at some point in the future, but it's not obviously the right answer, and it'd be a very large implementation effort.

(I don't know what Fortran does, so I can't comment on that.)

Maybe there's an implementation of constexpr on the horizon (from Chris' Swift for TensorFlow announcement (which explains a lot about the motivation for the dynamic-language (Python) interop proposals :wink:):

This project includes Swift compiler and language changes, which are in a copy of the Swift compiler sources. We think that some of these changes will be interesting to the broader Swift community, including language-integrated automatic differentiation support, a constant expression model, and improved interoperability with Python (and other dynamic languages).

Yes, I plan to write this up as a proposal for discussion here in the next couple weeks. I have spent way too much time thinking about this. :)

-Chris

And just to +1 Jordan's post, doing this as an AST interpreter would be the wrong way to go. The approach I'm a fan of is to do this at the SIL level. This will also eliminate most of the need for @_transparent, which is a nice bonus. I'll write it up in detail when I can.