redesign typeof(::Type)

[JeffBezanson]

A type in Julia takes one of four forms: DataType, Union, UnionAll, or Bottom. These are represented as Julia structs, distinguished by ordinary type tags for each of the four. This arrangement creates some subtle problems.

Types can be compared two ways: structurally (===, "looks the same when printed") and semantically (==, what set of values does it represent). For example Int == Union{Int,Int} but they have different structures (actually we normalize the union to just Int, but in theory such a union type can exist). The representation of a type, which is what you currently get from typeof, only involves its structure and not semantics.

The problem is that the type system prefers to compare types semantically. For example A{X} <: A{Y} iff X == Y (semantic comparison). However it is also possible to dispatch on type representations. For example

f(t::DataType) = 0
f(t::Union) = 1
g(::Type{T}) where {T} = f(T)

A call like g(Int) does not have a clear answer --- strictly speaking we only know that T == Int, not its representation. We currently have to use various hacks to get around this. One such hack is that inference is suboptimal in cases like this:

foo(f) = Ref((f,))
@code_typed foo(Complex) # => RefValue{_1} where _1

A related issue is that types like DataType and Type{Int} have an overly-complex subtype and specificity relationship: one is not a subtype of the other, but their intersection is non-empty, and we're not able to accurately represent that intersection. For various reasons (including backwards compatibility) subtyping currently gets this wrong on purpose, making Type{Int} <: DataType true.

I've come to think we'd be better off getting rid of DataType et. al., and not using type tags to identify type representations. Instead, for instance, we could make typeof(t) give Type for every type, and you'd have to look at fields to determine whether you have a Union, UnionAll, etc.

cc @vtjnash @jrevels

[StephenVavasis]

Just wondering if there is any connection between this issue and the following very old issue (which affected me once)

#10947

[JeffBezanson]

Yes it's connected; if we made this change we would probably have typeof((Int,)) == Tuple{Type{Int}}.

[JeffreySarnoff]

🍉

[Seelengrab]

foo(f) = Ref((f,))
@code_typed foo(Complex) # => RefValue{_1} where _1

Note that this example has improved slightly, though it's of course still not optimal.

julia> foo(f) = Ref((f,))
foo (generic function with 1 method)

julia> @code_typed foo(Complex) # => RefValue{_1} where _1
CodeInfo(
1 ─ %1 = Core.tuple(f)::Tuple{Type}
│   %2 = Main.Ref(%1)::Base.RefValue{T} where T<:Tuple{Type}
└──      return %2
) => Base.RefValue{T} where T<:Tuple{Type}

julia> versioninfo()
Julia Version 1.12.0-DEV.839
Commit 48b44d1c20 (2024-07-05 19:25 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 24 × AMD Ryzen 9 7900X 12-Core Processor
  WORD_SIZE: 64
  LLVM: libLLVM-17.0.6 (ORCJIT, znver4)
Threads: 23 default, 1 interactive, 23 GC (on 24 virtual cores)
Environment:
  JULIA_PKG_USE_CLI_GIT = true