Swift type checking is undecidable

Evolution Discussion
42

See the code in that post, you don't know if X<X<X<X<X<X<Int>>>>>> is used in this program.

43

Has it become possible since Self became possible to use in type definition?

44

It has always been possible with recursive functions. Consider this example:

struct G<T> {
  let value: T
}

func nest<T>(value: T, index: Int) {
  if index <= 0 { return }

  nest(value: G(value: value), index: index - 1)
}

Every recursive call to nest() wraps value in a new level of G<...>. Since you don't know what index is at compile time, you have to assume that an unbounded (but finite) number of types of the form G<G<G<G<...>>>> can be instantiated during execution.

3 Likes
45

This example isn't substantially different from the one I posted is it?

46

@Slava_Pestov is answering @AlexSedykh's question by showing an example that does not use Self.

2 Likes