Compile-Time Constant Expressions for Swift

(Tino) #82

I see it the other way round:
To make something hard, I want a better motivation than "it's not used often"; unless there are good reasons to discourage the use of a feature, imho it should be as convenient as possible, even if I never use it at all.

Did I miss something? Why do we have this proposal if everything can already be evaluated at compile time (and outside SPM ;-)?
Compile-time evaluation is not limited to theoretical examples like computing fib(17) (who ever needs that? ;-). It can be very powerful, and actually, I hope it won't be utilized in a hypothetical macro-system as outlined in the proposal, but rather make macros completely redundant.

(Félix Fischer) #83

I don't think you can make macros completely redundant.

Macros can generate code. This proposal can only generate values.

3 Likes
(Tino) #84

Swift has neither macros nor advanced compile-time evaluation, so both cannot generate anything ;-).

But something built on top of the current proposal could be used to implement fancy stuff like automatic conformance to Equatable or Codable in Swift itself easily - without a different language on top (macros), or below (C++ in the compiler).
This would definitely be a long way to go, but imho it's one of the coolest features a language can have.

(Lukas Stabe 🙃) #85

This is also a thing I thought about when reading this proposal, but I'm not sure that would be a good approach barring major enhancements to the capabilities of the constexpr interpreter.

E.g. how do we actually generate the code/how do we parse existing code (say the types we want to generate conformances for)? We'd probably want to use something like the Swift interface to lib/Syntax, which will probably never be doable in constexprs because it needs to call through to C++ code under the hood.

Similarly, many other cool uses of a macro system need access to the file system or other resources.

I would love a macro system similar to Rust's proc-macros (where macros (at least this kind) are basically rust libraries loaded as compiler plugins), but I don't think constexpr is the functionality to base it on, although it should be helpful to have constant parameters such macros could accept.

2 Likes
(Tino) #86

This is all way out of scope for the near future, so if this spawns any questions, I'd prefer not to discuss those in this thread... but for a moment, let's pretend we already have compile time evaluation and full introspection :-)

That's probably the easiest part - Jai (https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md) looks like a good example what can be done here.

The Swift compiler is doing this all the time, so the whole functionality to create types, methods and other entities is already there - it just has a syntax that's not suited for meta programming.
To make this less abstract, imagine

struct Point {
    var x: Float
    var y: Float
    var z: Float
}

could be written as

let point = #Swift.createStruct(name: "Point") // this is all hypothetical, but I hope it's enough to illustrate the idea
point.properties += Property(kind: .var, name: "x", type: Float)
point.properties += Property(kind: .var, name: "y", type: Float)
point.properties += Property(kind: .var, name: "z", type: Float)

Of course, that's not nearly as nice as way we declare types now... but it is regular Swift syntax, so the compiler knows it, and we also don't have to learn a dedicated macro language either.

... and of course, the example could also be written as

let point = #Swift.createStruct(name: "Point") // this is all hypothetical, but I hope it's enough to illustrate the idea
for name in ["x", "y", "z"] {
    point.properties += Property(kind: .var, name: name, type: Float)
}

I haven't seen any drafts how this could be done with a macros, but I'd expect that solution to contain some ugly special characters to differentiate the two contexts.

3 Likes
(Chris Lattner) #87

I'm responding to several points at once, the comment above is illustrative:

As others have said upstream, the compiler doesn't need this attribute to be able to constant fold a function: it can and already does that it many cases when the optimizer is on.

It is really really important to understand that this proposal is not about optimization. It is about correctness and the ability to compile a piece of code: these functions get compile-time-evaluated because there is something in the code (e.g. a static assertion) that requires their value to exist at compile time - even when the optimizer is not enabled. Making a change to the code that prevents this from happening will stop the build.

This is why the attribute exists: it makes it clear that "being compiler evaluable" is a part of the contract of the function. As @jawbroken mentions upthread, I don't expect this to be a widely used attribute - it is something some low level stuff in the standard library will adopt on integer and other similar types.

That said, it is perfectly reasonable to say that the attribute is not needed internal or private symbols. If there is some strong rationale, we could make it only be required on public ones.

Also, we'll switch the proposal to use #assert instead of #staticAssert, thanks for the feedback!

-Chris

11 Likes
(Alexander Momchilov) #88

I'm trying to get a better understanding of the usecases this can support. One of the reasons I've wanted something like this before was to save me the headache of making static members to hold compiled regex patterns. Declaring them as local variables causes their destruction and re-compilation on every invocation.

I thought it would be nice to have a compile-time compiled regex expression, that you can effortlessly use as a local variable, without the impact of recomputation.

Would this proposal be able to support such a use case?

(Félix Fischer) #89

I think so, assuming:

  • You get them from a function
  • The inputs for that function are known at compile-time
(Joe Groff) #90

Without going to full compile-time evaluation, it's also conceivable that if regex construction were understood to be pure, that the optimizer ought to hoist such computations into one-time global initializations instead of leaving them as local variables to be recomputed on every call.

1 Like
(Michel Fortin) #91

D has compile-time function execution (without the need for an attribute). D can use compile-time evaluated functions to generate compile-time constant strings, and D strings that are compile time constants can be mixed-in as statements in the code. This is used for instance by ctRegex in the standard library to convert regular expressions from string contants to D code that transparently get compiled with the rest of your own code.

All that to say if we add a string mixin concept similar to the one in D and a way to pass guarantied constant strings to functions (accomplished using templates in D), @compilerEvaluatable functions could form the heart of a powerful code generation feature.

4 Likes
(Félix Fischer) #92

That sounds really cool! Very close to first-class syntax support in the language itself :heart_eyes:

(Michel Fortin) #93

It's interesting that you bring purity into the picture. Purity has the same problem that @compilerEvaluatable has: all the functions it calls must have the same attribute, and it quickly becomes viral.

(And you can always invent more useful attributes that are like this. For instance a @noAllocation attribute, guarantying some code will not silently allocate memory for some real-time operations. Or a @concurrent attribute that would make sure some code is free of low-level data races using the type system.)

Most functions focussed on one encapsulated task can and probably should be annotated if they can to make them usable in more contexts, yet most high-level code cannot and should not use these annotations to preserve flexibility, so there is no good default to choose.

If you decide that @pure or @compilerEvaluatable can be inferred for functions within the same module to lessen the annotation burden, then you basically get whole call stacks in errors (similar to C++ templates) and changing the implementation of one function somewhere can cause another function elsewhere to not compile. Perhaps it's tolerable when confined within the same module, but it's certainly not ideal.

Things becomes even muddier for annotations when @compilerEvaluatable becomes conditional. For instance, you might be able to easily evaluate at compile time max([1,2,3]), but perhaps not max([1,2,3] as [SomeBigIntType]). Yet, it's the same max function in both cases. I made a tentative for declaring conditions like this for purity in an earlier exploratory proposal and I think it'd work for @compilerEvaluatable too, but there's probably some loose ends remaining.

(Howard Lovatt) #94

I get that is what you mean.

But it is not strictly that; in particular in your use case you want to force them to be compile time evaluated, it is not something the compiler can optionally do. If it were simply about correctness then you could make the annotation apply to any expression and issue a warning/error if it wasn't compile time evaluable, e.g.:

@isCompilerEvaluable let i = f() // Issues warning/error if compiler can't evaluate the expression.

What you are really introducing is something more akin to an annotation processor in Java were part of the AST can be modified by the compiler, this goes far beyond testing if the function can be evaluated by the compiler. Another analogy might be a pure function (and maybe that is a better pitch); although again you are really going beyond that, you are forcing the evaluation.

The annotation is bound to be viral; if you want to annotate your function and it calls my function then I need to annotate my function also! Suppose we said that functions could be marked as pure, there would be no argument that this annotation would spread virally throughout everyone's code.

(Chris Lattner) #95

Agreed. Something like this is mentioned as a potential future direction. I hope you agree that this makes "evaluability" a core part of the semantics of f(). If it compiles with some version of f(), it would be bad to stop compiling with a future version of f().

There is some relation there, but they are different things. I agree that all constant evaluable functions are also pure though! I agree that this proposal is forcing evaluation of when the caller is a #assert. To give an example from up-thread, if max were compiler evaluatable, then yes: max(1,2,3) could be evaluated, but perhaps not max(1,2,3) as SomeBigIntType and definitely not max(someUnknowableVariable, 42).

Agreed, there is some amount of vitality to this. I don't expect "users" to be applying this pervasively to their code though! This should be adopted by low level things like numeric algorithms particularly in the standard library.

-Chris

6 Likes
(André Videla) #96

What do you think about compile-time expression used in type signatures?

The proposal says

Compile-time constant expressions allow the compiler to evaluate the values of generic value parameters, which is an important first step in allowing the type checker to check types involving generic value parameters.

What do you think of introducing (maybe for a different proposal) compile-time functions in the type signature?

here is a simple example

@compilerEvaluable
func StrOrInt(_ a: Bool) -> Type {
    if a {
        return String.self
    } else {
        return Int.self
    }
}

func representation(value: Int, asString: Bool) -> StrOrInt(asString) {
    switch asString { // using switch because they must be exhaustive
    case true: return String(value)
    case false: return value
    }
}

This simple example could be extended to support more complex functions like vector operations

func append<let N: UInt, let M: UInt, T>(_ v1: Vector<size: N, T>, _ v2: Vector<size: M, T>) -> Vector<size: N + M, T> {
//                                                                                                             ^
//                                                                                                       compile time

or

@compileEvaluable
func AddVectorSizes<T>(n: UInt, m: UInt, content: T.Type) -> Type {
    return Vector<size: n + m, content>
}
func append<N: Int, M: Int, T>(_ v1: Vector<size: N, T>, _ v2: Vector<size: M, T>) -> AddVectorSizes(n: N, m: M, T.self) {
//                                                                                            ^
//                                                                                        compile time
(Chris Lattner) #97

This isn't something our model supports. We evaluate the values of constant expressions after type checking is done, so you can't have something that depends on the result of a constant change the argument.

What you want is even more broad that that though because you want contextually dependent types or something. That is definitely out of scope for our initial proposal. Maybe there is a way to build a generics feature around this, but I haven't thought enough about it to be sure, and can't see a good way to make that work without having the type checker fold expressions (something that cuts against the design of much of Swift).

(David Sweeris) #98

Could it maybe be done by treating the value of the "compile-time constant expression" similarly to how we handle "self or associatedtype requirements"? They're both something that isn't known at "function writing"-time but is known at "function-calling"-time.

(Brent Royal-Gordon) #99

This looks really cool!


When you talk about types, you mention Builtin.Int*, tuples, and structs, but not function types. This is sort of implied by the fact that you support function application, but it might make sense to clarify a few points. Some questions:

  1. Do you support operations on functions besides calls, such as storing a function into a variable or returning it?
  2. Do you support closures? Can they capture values? Can they mutate vars, and will those mutations be seen by other closures?
  3. Can function types be returned from a @compilerEvaluable function? Can closures with captured values be returned from a @compilerEvaluable function and then have those values available at runtime?
  4. Can you refer to non-@compilerEvaluable functions, even if you can't call them? I bet there are some use cases for evaluating some criteria at compile-time to select a function which will be called at runtime.
  5. Can you create a non-@compilerEvaluable closure in a @compilerEvaluable function, return it, and then call it at runtime?
  6. Can we make the first apply of an unbound method @compilerEvaluable even if the second isn't? That would let you bind methods to instances at compile time.

On the generic issue: I think that in the long run, option 3—"Introduce significant extensions to the generics system"—is the right answer. But it might be best to defer that for now. Let me try to sketch what I think would be needed for #3:

  1. Compiler evaluation supports only certain types: certain function types, tuples containing only supported types, and nominal types conforming to CompilerEvaluable. (It'd be nice if we could get structural type conformances in, even if there's no syntax for it, so that we could simply say that these other types are CompilerEvaluable. Oh, well.)

  2. When a type conforms to CompilerEvaluable, the compiler verifies that its storage contains only supported types.

  3. Protocols can mark requirements as @compilerEvaluable, but these requirements only apply to types which also conform to CompilerEvaluable. That is, a @compilerEvaluable attribute in a protocol is meaningless unless the conforming type is also constrained to be CompilerEvaluable.

  4. All concrete types used in an @compilerEvaluable function must conform to CompilerEvaluable, and all generic parameters are implicitly constrained to be CompilerEvaluable.

  5. As a future extension, we could introduce a syntax like @compilerEvaluable(T) to indicate that the function is @compilerEvaluable if its T type parameter is. (Alternative: Put this in right away and use @compilerEvaluable(Self) for the "only @compilerEvaluable for certain conformances" feature.

This is substantial work, but I don't think it's horrible. It might make sense to start with "runtime" (i.e. interpreter) enforcement and hope to transition to "compile-time" (i.e. pre-interpreter) enforcement in the future.


I was thinking about that—it makes a lot of sense to me.

I was going to ask if there would be a way to make a declaration @compilerEvaluable internally only, but I think making the attribute only be needed on public symbols handles that well. For cases where it's important that some value be computed at compile time, we could provide a #compileTime(…) expression which forces the compiler to evaluate it at compile time (peeking inside local declarations and relying on @compilerEvaluable for cross-module ones) or error out if it can't.

Edit: Sorry, didn't mean to necromance this thread.

1 Like
(Chris Lattner) #100

Sounds good. One point of clarification: there is a big difference between the "first proposal" version of this, and the end game. The first is intentionally minimal to get the point of the infrastructure and "how it works" through the community. Below I refer to the full design.

If you look at the TensorFlow branch, the implementation already supports calls (including through generics, witness methods etc), strings, and will soon support arrays. It can interpret a ton of the standard library.

  1. yes, 2) yes, 3a) yes, 5) yes. I haven't tested all of these and there may be bugs, but they "should" work.

3b: I don't know what you mean "available at runtime"
4: compilerEvaluable functions are normal functions. You can curry them, pass their address, pass variables, etc.
6: I don't know what you mean, example?

Having gotten a bit deeper into the implementation of this feature and seeing its capability, I have been pretty strongly swayed to the camp of "we should only require @compilerEvaluable on public functions, and it should be a superset of @inlinable (thus can replace it). In the standard library, for example, TONS of stuff is evaluable.

This is what my prototype implementation does.

Right. I think the best way to go is to only require @compilerEvaluable on public functions, it defines this concern away.

-Chris

4 Likes
(Brent Royal-Gordon) #101

These are silly examples, but here's what I mean by 3b:

@compilerEvaluable func largerFn(_ value: Int) -> () -> Int {
    return { value + 1 }
}
// Does the value captured by largerFn persist into runtime?
print(largerFn(3)())    // => 4, right?

@compilerEvaluable func pairedFns(_ value: Int) ->
        (incr: ()->Void, getter: ()->Int) {
    var _value = value
    func incr() { _value += 1 }
    func getter() -> Int { return _value }
    return (incr, getter)
}
// Is the fact that incr and getter capture the same variable 
// preserved at runtime?
let funcs = pairedFns(3)
funcs.incr()
print(funcs.getter())   // => 4, right?

4:

func fastPowerOfTwoImpl() { // notice, not @compilerEvaluable
    assert(isPowerOfTwo(dataSize))
    ...
}
func slowerGeneralImpl() { // not @compilerEvaluable
    // no such assertion
    ...
}
@compilerEvaluable func implFn(_ dataSize: Int) -> () -> Void {
    return isPowerOfTwo(dataSize) ?
        fastPowerOfTwoImpl : slowerGeneralImpl
    // Can a @compilerEvaluable function refer to and return
    // fastPowerOfTwoImpl and slowerGeneralImpl, even though it
    // can't call them?
}

6:

// Assume Hasher is forbidden in @compilerEvaluable.
func makeHashInMysteryValueFn<T>(as type: T.Type) -> (inout Hasher) -> Void
        where T: BinaryInteger  {
    // (Assume T is a type we can use in @compilerEvaluable.)
    return type.hash(into:)(42)
    // Can a @compilerEvaluable function partially apply hash(into:),
    // even though it can't fully apply it?
}
// This is the same as (42 as Int).hash(into: hasher), right?
let hashInMysteryValue = makeHashInMysteryValueFn(as: Int.self)
hashInMysteryValue(hasher)