Swift type checking is undecidable

Evolution Discussion
40

I'm really glad you pushed me on this because it has forced me to clarify my thinking.

I don't think what SwiftUI needs is the same as having “infinite types” in the sense I mean it. I think what I mean is that today, any given concretization of a generic type can imply the existence of an unbounded number of other concrete types, like C.Indices.Indices.Indices…, each of which is allowed to be different. Here's a really reduced example of a program that uses that fact:

struct X<T> {
  init(_ n: Int) {
    if n != 0 { _ = X<Self>(n - 1) }
  }
}

So I guess what I'm talking about is not a property of types but of programs. Today, the set of concrete types used by a program is unknowable at compile-time. If it were possible to explore type generation paths until the set of types reached a fixed point at compile time, it would allow all such ambiguities to be diagnosed and/or resolved at compile-time. I'm pretty sure this is the same as monomorphizability, and I have to admit I'm not yet sure whether it's compatible with module encapsulation.

I think this is really the other side of the C.Indices.Indices.Indices… coin, in the sense that if we had a finite set of types, maybe(?) it wouldn't matter if the constraint loop on Indices were closed.

Can we tie down Collection.Indices.Indices == Collection.Indices without breaking the world?

Certainly; the number of user-defined collections is (relatively) small and the number with non-defaulted Indices is even smaller. So we might break a small continent, but not the whole world :wink:

4 Likes