RFC: add a Type called AnyType that's subtyped by all other types except Any

Add AnyType between Any and all other types

Situation

The discussions here on Discourse and on Github make it clear that there are disagreements and confusion within the Julia community (including both users and core members, as far as I understand) regarding the root of the type system, where some think that

  1. anything that may be a type parameter (including isbits, Symbol, Module, etc.) should subtype Any
  2. something subtypes Any if and only if it’s an instance of Type (i.e., T isa Type is equivalent to T <: Any)

Proposal

As far as I see this unclear situation could be resolved in an essentially backwards-compatible way that would reconcile the differences of opinion and resolve subtyping inconsistencies by adding a new abstract type, AnyType, which would be implicitly subtyped by all abstract and concrete types that otherwise subtype only Any.

This way

  1. anything that may be a type parameter (including isbits, Symbol, Module, etc.) would subtype Any
  2. T would subtype AnyType if and only if T is a Type and T is not Any.

AnyType would still subtype Any, so Any would still be at the root of the type system, but with AnyType between Any and all other Types.

Examples

Current behavior

julia> abstract type A end

julia> abstract type B <: Any end

julia> struct S end

julia> struct R <: Any end

julia> supertypes(A)
(A, Any)

julia> supertypes(B)
(B, Any)

julia> supertypes(S)
(S, Any)

julia> supertypes(R)
(R, Any)

julia> supertypes(Int)
(Int64, Signed, Integer, Real, Number, Any)

julia> supertypes(3)
ERROR: MethodError: no method matching supertypes(::Int64)

Proposed behavior

julia> abstract type A end

julia> abstract type B <: Any end
ERROR: abstract type B may not have Any as direct supertype

julia> abstract type B <: AnyType end

julia> struct S end

julia> struct R <: Any end
ERROR: type R may not have Any as direct supertype

julia> struct R <: AnyType end

julia> supertypes(A)
(A, AnyType, Any)

julia> supertypes(B)
(B, AnyType, Any)

julia> supertypes(S)
(S, AnyType, Any)

julia> supertypes(R)
(R, AnyType, Any)

julia> supertypes(Int)
(Int64, Signed, Integer, Real, Number, AnyType, Any)

julia> supertypes(3)
(Any,)

julia> supertypes(:sym)
(Any,)

julia> supertypes(Int[])
ERROR: an instance of Vector{Int64} is not admissible as a type parameter

Variant on the proposal

Possibly it would be good to also add special abstract types such as AnyBits, AnySymbol, AnyModule and similar, so that, for example, AnyBits would be the direct supertype of any isbits value:

julia> supertypes(3)
(AnyBits, Any,)
1 Like

That would definitely not satisfy everyone.

Yes, <: Any can obliquely describe bitstypes when used in the context of a type parameter constraint. Yes, it’s inconsistent. Yes, it’s an abuse of the <: syntax. Yes, it can be a bit confusing. It’s not great, but it works.

As Jeff states in the first comment of that GitHub issue:

This is not a high priority, since it doesn’t prevent anybody from getting work done.

3 Likes

Related:

1 Like

Moreover, we can’t really remove the current behavior (at least not without a thorough PkgEval), since some code that runs with explicit T <: Any now may not after the change.

Conceptually, this is mixing up types and instances. It does not really make sense to ask for the supertype of an object that is not itself a type. Yes, the behavior of <: Any in type parameters is also not really respecting that and specifying “I really would like this T to be NOT a type” would be cleaner, but that way very quickly lies abstract multiple inheritance · Issue #5 · JuliaLang/julia · GitHub and related.

2 Likes

Well there are differences of opinions on this matter in the linked discussions, and the point of this proposal is exactly to reconcile these differences of opinion and, at the same time, resolve the incosistency that you note.

I understand that this isn’t exactly a high priority issue, but nonetheless this is a basic issue with the language, and I think this proposal of introducing a new type/types is a surpisingly low-impact way to resolve everything.

Sure, technically this could break some user code, but I doubt a significant amount of such code exists, because if someone wrote <:Any, they probably thought that had some effect, so these proposed changes would, I think, be much more likely to make user code work as intended than break it. For this proposal to break user code, the user would have had to intentionally write <:Any even though they require it to have no effect.

Here’s a quick search that lists a good amount of code that would break: JuliaHub search for r"Array{[^,]+,\s*<:\s*Any"

And that’s just for the case where folks have used <:Any to describe the parameter that’s probably the integer number of dimensions in an Array{T, <:Any} in a registered open source package.

1 Like

To be brutally honest, I see this whole issue as some “simple” grammar loophole that should have been fixed long ago, ever since it was first mentioned in the GitHub issue. The fact that it was constantly brought back by different people throughout time is perfect evidence. Now it has grown to be so abused that people can form utterly different views of treating the syntax of <: because their code works anyway.

Meanwhile, the hierarchical type system that’s one of the fundamental traits of Julia as a language should be as unambiguous as possible (in my opinion) if we are ever going to push it to a broader user base…

I have been keeping a close eye on this issue for quite some time, but the fact that it’s still considered a low-priority issue that has been ignored simply because the status quo is “working for everyone” is frustrating. And I believe if the core developers don’t treat it seriously, this issue will eventually backfire the language evermore in the future.

Given my opinion for the whole situation, as much as I fall into the type-2 group mentioned in @nsajko’s OP, I genuinely appreciate that they took the time to come up with this solution. I think at least it’s far better than doing nothing about this awkward inconsistency sitting in the corner of Julia’s type system.

1 Like

It’s not just a simple grammar loophole, changing this (even back then) would have far reaching consequences. This is only complicated by the fact that we now CANNOT remove that behavior until a breaking version in julia itself is introduced. What could be done is introduce a sentinel for “is not a type”, but then you might as well go all the way and allow T isa Int there instead. Of course, adding that won’t stop T <: Any from working, but it would at least accomplish the goal of disallowing T to be a type.

The immediate consequence of such an addition though is again running into the various versions of requests for some version of dependent typing, which is a much, MUCH larger change than fixing this would seem in isolation. Just as an example of the trouble this can bring, having such a generic isa allowed would make something like T isa Val{2} work, which I don’t even want to begin to imagine the implications of with different types instead of Val.

1 Like

No, this proposal wouldn’t break that. The only thing that would break as per proposal is in the examples above already - creating a new type with <: Any (creating a direct subtype of Any):

julia> struct R <: Any end
ERROR: type R may not have Any as direct supertype

But even that change is not an essential part of this proposal. That’s why I said it’s essentially backwards-compatible.

The original issue was brought up in January of 2015 when Julia was in the stage of 0.3.X. I think it’s safe to say no matter how complicated the solution would have been to fix the issue back then, it’s simpler than whatever we have to come up with now.

I’m not sure I entirely understand your potential solution to fix the situation, especially its benefits compared to the earliest proposal. However, if you are worried about the complications of “accidentally” allowing more complicated type parameters, I’d say that’s already the reality we live in now:

julia> struct A{T} end

julia> A{Val(2)}
A{Val{2}()}

julia> A{:symbol}
A{:symbol}

julia> A{Tuple{:notT, :notT2}}
A{Tuple{:notT, :notT2}}

I think the fundamental problem is that it’s never made clear whether (or when) a type parameter T in the composite type should be a Type in the official documentation. Yet, before a standardized narrative comes out, people have already developed different beliefs on their images of T

1 Like

I disagree with that position. The fact that you can pass a non-type to a parametric type that explicitly has a <: Any declaration on that type parameter is a bug plain and simple (and not one that has anything to do with grammar or syntax). If there’s code that breaks when that bug gets fixed then so be it—that code has to be fixed. Semantic versioning does not mean we can’t make any changes that change the behavior of any code anywhere. It means we can’t make breaking changes to documented and intentional APIs which I don’t believe this to be.

15 Likes

Maybe this is a good time to mention this idea: Syntactic sugar for ignoring a type parameter · Issue #29875 · JuliaLang/julia · GitHub

1 Like

Fair enough, I spoke too soon.

Still, I don’t believe we can realistically and in a satisfactory way fix this (that is, disallow isbits-values on T <: Any) without a breaking change. It’s commonly understood that leaving a field unspecified is the same as typing it Any. It’s also commonly understood that typing a field some type S behaves the same on construction & as far as restrictions what you can ultimately place there go as giving the new type a type parameter T <: S (the difference being a better memory layout for isbits values and fixing the type in place for mutable structs). Therefore, I don’t think it is unreasonable to believe T and T <: Any to behave the same in terms of what is allowed.

I don’t think so - Any is the documented Top type of the type system:

When no supertype is given, the default supertype is Any – a predefined abstract type that all objects are instances of and all types are subtypes of. In type theory, Any is commonly called “top” because it is at the apex of the type graph. Julia also has a predefined abstract “bottom” type, at the nadir of the type graph, which is written as Union{} . It is the exact opposite of Any : no object is an instance of Union{} and all types are supertypes of Union{} .

Any operation on the types that can’t come to a conclusive answer must fall back to that (or Union{}, in other cases), if it’s a sensible way to express the result of that operation. Not to mention that the <: Any may not have been added by the user themselves, but by a linter enforcing explicit typing everywhere, using the fact that an untyped field is exactly the same as ::Any, even if only a type was intended (a classic case of “do what I mean”).

No, you misunderstood my point - I’m well aware that we can already place such complicated objects in type parameters. I use that feature very often, with much too complicated objects. I wouldn’t dream of disallowing that concept entirely. What I’m concerned about is having that isa Val{2} available as part of the type matching/dispatch machinery, that is, being able to match whether a type parameter is a non-type object of a specific type.

Let me expand on why I think that is a necessary consequence of seperating T <: Any and placing isbits objects there.

Since Any is the documented Top type of the type system, there is naturally a lot of code assuming it to be the “fallback” for when some operation becomes badly type unstable or when some internal typejoin just has to fall back to Any, since there just isn’t any smaller supertype that can hold the values of both joined types. This is natural - if you expect a DataType and Any is the supertype of all instances of DataType, why would you need to change your code? Introducing an AnyType, however, would mean that operations like typejoin(Int, String) (chosen for simplicity, but the argument holds for any two types whose current least common ancestor is Any) who don’t have a common ancestor other than the Top type, would now return a type that is narrower than the Top type. This breaks the (documented!) assumption that Any is the Top type, so I don’t believe this is an option - meaning the proposal can’t be done right now in a non-breaking way (or I’m missing something).

Next, another option other than introducing a new supertype for all instances of DataType, would be to instead introduce a new supertype for all non-Types (or multiple variants thereof, the following argument stays the same), i.e. introduce a common supertype for instances of Symbol, instances of isbitstype, and tuples of the the two, properly elevating their status from “objects that happen to work (by design) as type parameters”, to true nodes in the type lattice with a subtyping relationship. I’ll call these objects ValueTypes here, because they are types defined by their value (not to be confused with Type{T}, which is exclusive to instances of DataType, though conceptually similar). This seems preferrable, since there is no way at all to specify “I need a type parameter that is NOT a type, because I need a value that I’m going to do computation on”, as well as keeping existing code behaving the same (no accidental breakage is possible).

However, this very quickly exposes another conundrum - there are no “instances” of 2. 2 already is an instance of Int - it is not a type in the sense of being an instance of DataType, which is what all operations on types are defined on. You can have it be a type in some interpretation, but then you immediately run into the questions “What are its subtypes? What are its supertypes?”, which you need to have a useful definition of instances of non-DataType objects to be a type themselves, since that’s what defines their position in the type lattice. The easy way out would of course be to just define supertypes(2) === (ValueType, Any), as well as subtypes(2) === Type[] and similar for any non-Type value we can currently use in type parameters, but this then isn’t really a useful definition - you can’t do any type level operations with that information because it effectively creates a type graph that doesn’t have any subtyping relations between non-trivial nodes (i.e., where one of the operands is distinct from any instance of DataType).

An alternative definition could involve not having supertype(ValueType) === Any at all, but this would require even more code churn (any use of NTuple{N, T} or Array{T, N} would break) and thus doesn’t help the situation - though I like the thought of it, since it makes it very clear that the type graph of values is very different from that of the instances of DataType.

Regardless, both of these definitions bring us dangerously close to dependent typing, without taking the final leap of actually implementing that and all its associated dispatch difficulties, just to fix an inconsistency in what the syntax <: Any means. To me at least, that is not worth it - and seeing as how that’s been the common ground in the issue where this was originally brought up, I feel fairly confident in saying that this won’t change anytime soon. Not to mention that as soon as you start to mess with 2 (and similar) as a type of its own (without wrapping in something like Val), lots and lots and lots of people will repeat the request for dispatching on something like iseven(T) (myself included), which time after time has been answered with “Trust constant propagation and branch” (which I “pray & preach” too, as long as we don’t have dependent typing). You can of course create your own orthogonal IsEven{2}() object that allows you to dispatch on that right now, at the cost of introducing an orthogonal & incompatible layer to the existing iseven function (for example, that type cannot hold a BigInt, and you can’t write a IsEmpty{T} that can hold an array, since both of those aren’t isbits).


I hope this makes my concern clearer and even though I agree that it would be very nice to fix this inconsistency, as well as getting better support for values at the type level, ultimately I don’t think it’s a realistic change that can actually be done right now, breaking or not.

1 Like

You’re mixing up two different things:

  1. My proposal here: it doesn’t in any way change the fact that Any is the root of the type system
  2. Stefan Karpinski’s intent on fixing the unintuitiveness

I can’t say I’m a fan of this. The fact that a type can be parameterized either by a type or by an isbits object, isn’t reason to start considering isbits objects to be types.

If asserting the type of an isbits parameter is desired, it could be communicated like so:

NTuple{n, T} where {n isa Int, T<:Any}

although, that seems to suggest we could dispatch on the types of isbits parameters; I don’t know if that’s possible. Even without dispatch however, it’s appealing to throw an appropriate error if someone tries Array{Int, 2.0}.


I fear this may be true. It may not be statutory law that Foo{2} <: Foo{<:Any}, but it’s common law. It’s totally nonsensical, but it’s so common that although breaking it mightn’t fit the official definition of breaking, in practice it could arguably be considered breaking.

That said, breaking might be a good thing. The package ecosystem, as impressive as its size is, also has many uncared-for projects (classroom projects, toy gimmicks, experiments, underscore macros, and the like) that are honestly distractions. It might be due for a wildfire to pass through and consume the weeds and dead brush—things that people aren’t motivated to port over to 2.0—to clear room for active and healthy projects to receive greater attention and resources. The ecosystem is probably robust enough by now that it could bounce back stronger.

As boring as this issue sounds superficially, striking at the heart of the type system makes it seem to be a reasonable issue to trigger Julia 2.0. And maybe boring is what we want.


On Shorthands

I think it’s notable that the only reason for this issue to exist is because we want a shorthand for Foo{T} where T, so we allow Foo{<:Any} == Foo{T} where T. If we simply had a more accurate shorthand, such as Foo{:} == Foo{T} where T, then we could free <:Any from the nonsense of matching isbits objects. Then we could have:

Foo{T} where T           # T can be a type or an isbits object
Foo{:}                   # * can be a type or an isbits object
Foo{T} where T<:Any      # T can be a type only
Foo{<:Any}               # * can be a type only
Foo{T} where T>:Union{}  # T can be a type only
Foo{>:Union{}}           # * can be a type only

Foo{<:Any} <: Foo{:}     #-> true
Foo{<:Any} >: Foo{:}     #-> false

I don’t think I am. I responded to Stefans’ answer and your proposal at the same time, in the long explanation below the section quoting @frankwswang. If I actually misunderstood your proposal, please point me to the section in my answer where I’m going wrong, so I can understand what you actually mean.

But it absolutely is:

julia> Foo{2} <: Foo{<:Any}
true

That’s the basis for (Vector{T} where T) <: (AbstractArray{T, 1} where T) <: (AbstractArray{T, N} where {T, N}) after all.

1 Like

It’s not. The fact that Foo{2} <: Foo{<:Any} evaluates to true is an artifact of the fact that Foo{2} <: Foo{T} where T (as it should, per decree), and that Foo{<:Any} == Foo{T} where T (which is an implementation detail unmentioned in the manual).

The fact that a UnionAll whose TypeVar has a ub of Any and a lb of Union{} doesn’t check whether the type parameter is even a type is merely an implementation detail; it could have been chosen instead that a special value (what’s the antonym of a sentinel value?) of Colon() would serve the role of indicating “don’t check.”

This is NOT an implementation detail! As I’ve explained above, Any is the Top of the type system; the apex; the supertype of all types and the subtype of no types, by definition. Union{} (specifically the empty union) is to Bottom of the type system; the subtype of all types, the supertype of none. Writing Foo{<:Any} is exactly equal to writing Foo{T} where T, which is exactly equal to writing Foo{T} where Union{} <: T <: Any. This is documented:

Type variables can be restricted with subtype relations. Array{T} where T<:Integer refers to all arrays whose element type is some kind of Integer. The syntax Array{<:Integer} is a convenient shorthand for Array{T} where T<:Integer . Type variables can have both lower and upper bounds. Array{T} where Int<:T<:Number refers to all arrays of Numbers that are able to contain Int s (since T must be at least as big as Int ). The syntax where T>:Int also works to specify only the lower bound of a type variable, and Array{>:Int} is equivalent to Array{T} where T>:Int .

Changing the Any in that last expression to anything else is a breaking change, there is no way around that. This is not just me “making things up to justify the current behavior”, this is type theory and a requirement to have a sound, designed type system. Sure, you could argue that the implicit expansion to Union{} <: T <: Any itself is technically not documented (other than in that little paragraph), but that doesn’t change the fact that Foo{2} <: Foo{<:Any} still is required to be true in future versions, even under our (slightly bent) SemVer. Hence, my proposal for an alternative implementation above, giving the existence of isbits values in the type lattice an explicitly defined semantic - which unfortunately introduces quite a number of additional complications (which I’m guessing is why it hasn’t been formalized further in julia to this day. Maybe @jeff.bezanson has a reasoning).

Yes, but it wasn’t, and that’s the point I’m trying to make. It would be hugely disruptive to any struct wrapping an array with arbitrary dimensions or an NTuple, forwarding the type parameter N to be required to actually now write this differently.

No, what is documented there is that Foo{<:Any} should equal Foo{T} where T<:Any, *not* that Foo{T} where T<:Any should be Foo{T} where T. It’s an important distinction.

Foo{2} <: Foo{T} where T evaluating to true makes sense.
Foo{2} <: Foo{T} where T<:Any evaluating to true is nonsense.

The only reason that Foo{2} <: Foo{<:Any} evaluates to true is because of an implementation detail, and is not documented. If a UnionAll’s TypeVar having a ub of Any didn’t mean “just don’t check,” then a test would run to confirm if 2 <: Any, and it would throw an error.

julia> Foo{2} <: Foo{T} where T # evaluating to true makes sense
true

julia> Foo{2} <: Foo{<:Any} # evaluating to true is nonsense
true

julia> 2 <: Any # error makes sense
ERROR: TypeError: in <:, expected Type, got a value of type Int64

I agreed with this, and I took it a step further by speculating that the disruption may be healthy and desireable, a form of hormesis for the package ecosystem like exercise or fasting for the body.

1 Like