Avoiding Combinatorial Explosions

Evolution Discussion
1

Could we get a list of things that cause a combinatorial explosion in the type checker?

I am wondering if we can avoid this in common cases by providing a default assumption for the type checker to start with. The checker would only check the assumed case(s), and then only if that failed would it try the normal path.

For example, if we have overloaded return types, but one of them is expected to be used 90% of the time, then if we have a way to tell the compiler that, we only have to check multiple types 10% of the time.

2

Does as T not already provide a way to do exactly this?

3

Oh, I mean at the declaration site as opposed to the call site. That is, when I define the functions which have overloaded return types, I have a way of telling the compiler which one to check first.

4

I could also imagine having a default type for generic types like so:

struct MyStruct<T = Int> {
    var store:T
}

Then it would assume T is Int, until it proves that it isn't. This means you could probably just say MyStruct instead of MyStruct<Int> without getting an error. But you could still specify something specific if you wanted it (e.g, MyStruct<String>)

An alternate spelling could be:

struct MyStruct<T> assuming T == Int {
    var store:T
}
1 Like
5

Wouldn't the compiler still be forced to check the other cases to be able to detect if the construct is ambiguous or not ?

6

No, because we are essentially declaring that this is the thing we want it to use in the case of ambiguity.

We are saying check this first and use it if it fits. If it doesn't fit, then check other things too.

This is a change in behavior from the status quo. There are parts of swift that behave the way I am proposing already though. For example, if I say:

let x = 2.0  //X is a Double

then my variable x is of type Double, even though there is ambiguity between several types which implement ExpressibleByFloatLiteral. If I want it to be a CGFloat, I have to say:

let x:CGFloat = 2.0

or

let x = 2.0 as CGFloat

This is because the compiler special-cases double to avoid making float literals too annoying to deal with. My proposal would let us do the same thing for our own types (and hopefully remove some magic from the compiler).

The benefits would be less stress on the type checker (meaning faster compilation), and better ergonomics when a default is well chosen.

3 Likes
7

Default generic arguments are mentioned in the generics manifesto. Notably it's under minor extensions so it may not be too much of an ask. Though for functions you'd need to introduce the ability to specialize it at the call site i.e. let x = foo<Int>(bar: baz). Which IIRC is something that is wanted.

3 Likes