Type Constructors (=multiple dispatch for `UnionAll`)

Internals & Design
1

TL;DR

Let’s use (static) multiple dispatch for UnionAll type application!
This would introduce type constructors. They would take a UnionAll to construct a type similar to how inner (object/value) constructors take a type to construct an object/value.

Motivation

Backwards Compatibility

Suppose we wanted to generalize SubString from

struct SubString{T <: AbstractString} <: AbstractString
    string::T
    offset::Int
    ncodeunits::Int
end

into:

struct SubString{T <: AbstractString, R <: AbstractUnitRange{<:Integer}} <: AbstractString
    string::T
    ind::R
end

This would have multiple advantages (allowing smaller index types, allow something like Base.OneTo, generally reusing code) which are not relevant for our discussion here.

Object constructors and properties could preserve much of the existing interface. However, SubString{String} would become a UnionAll, so existing fields declared as ::SubString{String} would no longer be concrete. For all I know, this incompatibility could not be avoided (withing the desired solution space, i.e without introducing additional types or something) with Julias features as of today.

Constraining Types

Currently, it’s often not possible to usefully constraint types so that invalid types cannot even be constructed (used). Instead, constructors need to make sure that they don’t construct an object of an (then already existing) invalid type.

So assume we wanted to define for our example above (to not introduce a more useful, but another example)

SubString{UnitRange{Int}}(bytes::Vector{UInt8}) =
    SubString{String, UnitRange{Int}}(String(bytes), 1:length(bytes))

then this could not be constructed, as SubString is a UnionAll, which only accepts a T <: AbstractString as first TypeVar, not an AbstractUnitRange.
The only possibility to make this work is to remove the type constraint(s) from the type definition and let the constructor do this work. While that kind of works, it not only feels wrong, but it becomes obvious, that regular constructors are currently more powerful.

Asymmetry

There is also an inherent asymmetry involved in defining parametric types with more than one type parameter, closely related the the point mentioned before: SubString{T <: AbstractString} automatically is a UnionAll, while SubString{R <: AbstractUnitRange{<:Integer}} isn’t, although they are clearly distinguishable. Again, regular constructors, using multiple dispatch, are just more powerful due to their multiple dispatch.

Conclusion

Julia lets us customize object construction through constructor methods, but type application such as Foo{T} always follows positional parameter substitution.
If we only had multiple (static) dispatch for type construction! So could we support inner type constructors, analogous to inner object constructors?

Proposed Syntax

Inside the type definition, allow (type) constructors without the parenthesized object argument list:

struct SubString{T <: AbstractString, R <: AbstractUnitRange{<:Integer}} <: AbstractString
    string::T
    ind::R

    SubString{T <: AbstractString} = new{T, UnitRange{Int}}
    SubString{R <: AbstractUnitRange{<:Integer}} =
        new{T,R} where T <: AbstractString
    SubString{T,R} = new{T,R}
end

The distinction would be:

  • new{T,R} returns the canonical type through native parameter substitution.
  • new{T,R}(string, ind) constructs an instance, as today.

From the user’s perspective:

SubString{String}
# Concrete type: String parent, UnitRange{Int} indices

SubString{String, UnitRange{Int32}}
# Concrete type: String parent, UnitRange{Int32} indices

SubString{UnitRange{Int}}
# UnionAll: any permitted string type, UnitRange{Int} indices
# Equivalent to:
SubString{T, UnitRange{Int}} where T <: AbstractString

SubString{String, R} where R <: AbstractUnitRange{<:Integer}
# UnionAll: String parent, any permitted range representation

SubString would still denote the generic UnionAll.

Semantics

Type constructors would dispatch on parameter combinations and bounds. Their bodies could use = begin … end with Julia code to validate parameters, supply defaults, or reorder them before returning a type.

Like inner object constructors, defining an inner type constructor would suppress automatic public type-application defaults. Explicit forwarding, as above, would restore the desired forms. Types without custom definitions would behave exactly as today.

So this should be fully backwards-compatible with the exception of local type aliases in the constructor which could have the same syntax. I have never seen them, but if they exist in larger frequency, we could either require, at least initially, a new (but this would disallow type constructor delegates) or change the syntax. Although I think that the proposed syntax is the logical choice, we could introduce a block-form with some keyword needing an end.

Arguments would be type objects, permitted value parameters, or TypeVars, so everything would need to be “static”. Ambiguous applications would be errors. At least initially constructors would be fixed with the type definition, so their would be no external type constructors. Type constructors must return specializations of that same nominal type (so a SubString type constructor must return a concrete or UnionAll SubString, not a Vector).

Summary

The goal is to make type application customizable in the same spirit as object construction, allowing a type’s representation to evolve while preserving useful existing spellings such as SubString{String}. This should solve all motivating problems and could make the language more consistent by allowing the same (and defining) language mechanism (multiple dispatch) to be applied not only on functions and on objects (=callables), but also on types.

What do you think? Obviously, a lot of details would need to be clarified before/while implementing it, but does the general idea sound interesting?

3 Likes