Rename isleaftype

[omus]

While re-reading the manual I realized that isleaftype should probably be renamed to either isconcretetype or isconcrete:

julia> abstract Foo

julia> abstract Bar <: Foo

julia> type Baz <: Foo
       end

julia> isleaftype(Bar)  # One could consider Bar a leaf type but not concrete
false

julia> isleaftype(Baz)
true

The documentation for isleaftype does clearly explain it returns true for concrete types which seems like the function name is slightly misleading.

[yuyichao]

Leaf does not mean it is branched off from somewhere, but that it cannot be branched off from.

[ivarne]

In Java you have both leaf types (final class) and concrete types (class that is not abstract). In Julia all concrete types are final, so I think both names will be correct, so it is just a question about what therminolgy we want to use.

[omus]

The terminology used in the manual seems to stick to concrete

[mauro3]

Searching julia-users for "leaf type" returns 8 results, for "concrete type" 351. +1 for isconcrete.

[nalimilan]

@JeffBezanson Do you support this change as well?

[jiahao]

The primary issue is that we don't clearly define what "leaf type" and "concrete type" are - this came up recently in a discussion with @janvitek @lkuper.

Consider a few candidate definitions (insert "leaf type" or "concrete type" in the blanks below):

1. A type T is a _________ when the predicate isleaftype(T) returns true.
2. A type T is a _________ when it is instantiable, in the sense that you can create at least one value whose run time tag is T.
3. A type T is a _________ when it is a bitstype or nominal type defined with type or immutable with no unbound parameters (i.e. all type parameters are specified and are bound to a value that is not a typevar).
4. A type T is a _________ when it has at least one field.
5. A type T is a _________ when it is not an abstract type or a Union type.
6. A type T is a _________ when it is has no subtypes other than Union{}.

Definition 1 can be made tautological.

Here is a table I made testing some of these definitions using introspection from the Julia REPL:

We can rule out Definition 4 since it precludes bits types like Int64 and includes constructs like Complex = Complex{T<:Real} which I presume most people would agree are neither concrete nor leaf.

Intuitively, one wants to say that the remaining definitions (2, 3, 5, 6) are equivalent, but I'm not entirely sure that they are.

[JeffBezanson]

Actually being able to make an instance of something should not be part of the definition, because it is too operational. For example, if all the constructors for a type happen to throw errors, saying it's not a (concrete|leaf) type is misleading --- the type object itself will still share all relevant properties with other concrete types.

Definition 5 will be right after #8974, since then we will no longer allow types with unbound parameters (they will have to be wrapped in UnionAll types). With that caveat, I believe 3, 5, and 6 are equivalent.

The one exceptional case is the singleton types like Type{Int}. Type itself is an abstract type, but Type{Int} is a strict subtype of DataType. This really throws a monkey wrench into the whole thing, and needs to be special-cased everywhere. Taking this into account, I think the two relevant properties are:

1. Can be the direct tag of a value.
2. Has no subtypes other than Union{} and itself.

For most types these are equivalent. DataType has (1) but not (2), and Type{Int} has (2) but not (1).

[JeffBezanson]

Footnote: I believe we could fix the monkey business by making the tag of Int be DataType{Int} (and similarly, typeof(Union{Int,String}) = UnionType{Union{Int,String}}). Type{Int} could then be an abstract type containing all types equal to Int, for example including Union{Int,Int} (which is not easy to construct but is perfectly meaningful). This approach appears, superficially, to be quite expensive, but might be worth it.

[nalimilan]

Do we really need to solve the question of the exact definition to decide on the best naming? As noted above, the documentation already uses concrete everywhere.

[jiahao]

As noted above, the documentation already uses concrete everywhere.

If there is no useful distinction between "leaf type" and "concrete type", then it would be a moot point. However, I very strongly suspect that if we went through our documentation, we would see that there is a conflation of Definition 2 and Definitions 3/5/6 in our usage of the terms, even though we treat them colloquially as interchangeable.

[JeffBezanson]

Yes, it is quite possible we've used "concrete" to refer to a nominal type declared with type or immutable instead of abstract, while "leaf" refers to a concrete type that is also instantiable by virtue of having no unbound parameters. So Complex is concrete but not leaf, and Complex{Int} is leaf.

[nalimilan]

As can be seen at https://github.com/JuliaLang/julia/pull/20709/files#diff-2df71755503be40d805334f1bef57673, there's only a handful of uses of "leaf" or "leaf type" in the documentation. So that's easy to check.

[vtjnash]

I've attempted to put together a list of all of the type-classification queries that I think are meaningful. Of these, only two don't currently exist: is_dispatch_tuple and isconcrete. I think those should replace isleaftype.

type queries

• is_abstracttype / is_structtype / is_primitivetype : kind of the (data)type (complete, disjoint set)
• typename, supertype, etc. (declared properties)
• isType : DataType of the form Type{T}, for any T::Type
• isTupleType : DataType of the form Type{<:Tuple} (aka, subtype(Tuple{<:Tuple}))
• isconcrete : isTupleType ? map(isconcrete, parameters) : (!has_free_typevars && !isabstract) (this does not include Union{})
• has_concrete_subtype : heuristic query, for example: isabstract || isbits || (fields_initialized && all(has_concrete_subtype, fieldtypes)
• iskind : isconcrete subtypes of Type
• is_dispatch_tuple : isTupleType && all(isType || (isconcrete && !iskind)), parameters)

structure queries

• is_mutable, fieldtypes, fieldoffset, sizeof, etc. (declared properties)
• isbits : is_primitivetype || all(isbits, fieldtypes)
• pointerfree : all(is_alloc_inline, fieldtypes)
• is_alloc_inline : equal to the C function predicate jl_layout_inline – we can change this whenever we want, but guaranteed to include isbits and to not include is_mutable
• issingleton : isstructtype && all(issingleton, fieldtypes)

isleaftype

So what should be the fate of isleaftype? We could simply deprecate and remove this name. Another option is to make this the name for the is_dispatch_tuple fieldtype predicate declared above: isType || (isconcrete && !iskind)). In the future, this predicate will need to evolve further, so it could be useful to have this split out. (the required future evolution involves replacing Type{T} with either TypeIntersection{Type{T}, iskind} or Kind{T})

[JeffBezanson]

Good list. I agree with the definition of isconcrete, and that does seem to be what you should typically use when you want to ask something like "is this a simple type that avoids anything weird and abstract?" That set of types is likely to remain very stable. I also believe isleaftype && layout != NULL currently implements it correctly, though that is somewhat subject to implementation details.