Repository navigation
Description
Wrapper types are a mess. The classic example is that TrackedArray{Adjoint{Array}} is no longer seen as an Adjoint and Tracker.jl needed special overloads for handling adjoint arrays. Two deep you can start to special case: three deep is a nightmare. Why?
The issue is that wrapper types aren't exactly new types, they are extended pieces of information. A lot of information stays the same, like length, but only some changes. In the parlance of Julia, this is the kind of behavior that you normally have with type parameters, where Array{T,1} shares dispatches with Array{T,2} but then overrides what changes when you change dimensions. So, we could in theory do Array{T,1,Adjoint}, but now you can see the issue: it's an extendability problem since these tags need to all be pre-specified in the type definition! What if new packages add new tag verbs? SOL, redefine/pirate the type if you want to use it! This is why people use wrapper types: you can always extend, but of course you get the dispatch problem.
What about traits you say? They extend the way things dispatch, but only do so at compile time for a given type. isadjoint(::Array) can't be a thing, unless you have a type parameter for it.
So you need some extra information. That's why I am proposing type tags. A type tag is an extension like Array{Float64,1}{Adjoint}, where the tag adds information to an existing type. It could be like, tag(A,IsAdjoint()). By default, any tags would have the default behavior unless tagged, so Array{Float64,1} would have tag(Adjoint) == DefaultTag(). Then dispatches could be written on the tags, allowing for extension while keeping dispatches.
The one thing to really think about though is ambiguity handling...
Activity
DilumAluthge commentedon Sep 28, 2020
This sounds great!
DilumAluthge commentedon Sep 28, 2020
Could you elaborate on this a little bit?
ChrisRackauckas commentedon Sep 28, 2020
Doing some stuff like
mul!(::IsAdjoint,..)would cause a lot of dispatch ambiguities if inArray{Float64,1}{Adjoint}theAdjointhas equal precedence to the other types. In this sense, I almost thing that a separate rule needs to be applied, like "tags supersede type parameters" in order to break ambiguities in a nice way. One of the type gods could probably point to some literature on an idea like this with its trade-offs.MasonProtter commentedon Sep 28, 2020
Just to copy my thoughts so they don't get lost in the Slack-hole:
I feel like the idea to have "something that extends the idea of type parameters" a-la
Array{Float64,1}{Adjoint}is just re-discovering concrete inheritance.That is,
Array{Float64,1}{Adjoint}are types that are distinct fromArray{Float64,1}, but have the same memory layout and will be accepted by all the same methods. This is essentially what people are talking about when they discuss inheriting from concrete types.My understanding is that concrete inheritance is looked at with a lot of skepticism and scorn but it does feel like our abstract array ecosystem is hitting the limits of simple type composition and it may be time to revisit concrete inheritance and see if we can do it sanely.
DilumAluthge commentedon Sep 29, 2020
Instead of concrete inheritance, is it possible to accomplish this with only abstract multiple inheritance (a la #5)?
E.g. for the tracker example, something like this:
We have a method
adjointwith the following signature:And we have two methods for
trackwith the following signatures:ChrisRackauckas commentedon Sep 29, 2020
That will hit this issue that we want something to be
Tracked,Adjoint, andSymmetric. I think the tagging needs to be "from the outside" instead of being defined at type definition time.DilumAluthge commentedon Sep 29, 2020
Yeah I see what you mean. It's not sustainable to have different structs
struct TrackedAdjointSymmetricArrayfor each possible combination.Also we don't currently have abstract multiple inheritance, so that would be another barrier.
DilumAluthge commentedon Sep 29, 2020
I agree that the tag approach is probably more sustainable.
yuyichao commentedon Sep 29, 2020
Why is this? Trait doesn't have to happe all at compile time, much like dispatch doesn't have to happen at compile time. It's generally even just a way to compute a property from an object for dispatch. Why can't
isadjoint(::Array)be a thing?Is this tag supposed to be per object or per type. When and how is it attached? If it's attached to the type then it seems to be exactly what traits are fore. If it's attached to the object, then this is essentially something that is used for dispatch that can be changed at runtime so it cannot be statically inferred. I don't think that's desireable effect.
DilumAluthge commentedon Sep 29, 2020
If I understand correctly, the information is attached to instances, not types.
DilumAluthge commentedon Sep 29, 2020
To do this at compile time, you need a type parameter. E.g. a Boolean type parameter
Adjointness:Then we define:
To do it at run time, we need a field in the
Arraystruct:Then we define:
In either case, we need to decide ahead of time which properties (adjointness, symmetricness, etc) we will support, and we have to hardcode those as either type parameters or fields.
As Chris says:
DilumAluthge commentedon Sep 29, 2020
@ChrisRackauckas This would also mean that concrete inheritance would also not solve this issue, right?
yuyichao commentedon Sep 29, 2020
If that is the case, then essentially
f(x)will almost never be statically dispatched. It'll be really hard for type inference to know if the type tag is changed. Is this the desired effect? This is roughly equivalent to putting values into type domain, which is a standard form of dispatch abuse for exactly this reason.Still, it's unclear why this should be per-object.
Hmmm, no? What you need, if this property is not defined/determined by yourself, is a way to delegate this check to the part that should determine this, i.e.
TrackedArray{A}should implement anisadjointto call that onAinstead. If there's nothing else to delegate to, a explicit implementation should be provided or the fallback is used and there's no way around this, no matter what you do.If the complaint is that
TrackedArrayhas to implementisadjointand unknown number of other properties and you would rather like a way to transfer all properties to the wrapped object without enumerating over all of them, well,isadjointas sth liketrait(..., ::IsAdjoint)and simply implementtrait(::TrackedArray, ::Any) = trait(<delegate to the wrapped array>)yuyichao commentedon Sep 29, 2020
Or if you replace the
traitfunction I have above withtag, you already get an explicit version of what this is doing without the tag mutation part of the API that kills inference. In another word, instead of doingf(a)you dof(a, tag(a, IsAdjoint()))and that's exactly how all traits works with various different spelling. Thetagfunction can rely on the type or rely on the object which may affect how inference friendly it is but at least it is not guaranteed to kill inference.... And note that even thoughIsAdjoint()is explicitly used here, this is on the consumer of the information which has to know about it and will not be dealing with unknown number of traits.And such a system is already there. Improving it/them and adopting a standard one are certainly things to be worked on. @vtjnash had even made a comment of replacing most complex dispatch with it. Changing the syntax so that this is done automatically without additional argument necessary can potentially be on the table once there's a clear winner/one that's widely adopted.
Another way to look at this is that methods are already a way to attach compiler friendly info to arbitrary object/types (i.e. methods are mappings from object/type to an output). They also already allow very flexible manipulate/inheritance which seems to cover the need here. Attaching other generic metadata to object could have other use and it is basically what
WeakKeyDictare for, but I highly doubt it's the right solution here.MasonProtter commentedon Sep 29, 2020
No, I don't think that's correct @DilumAluthge. We want the information to be a part of the type. Basically, Chris is asking for an un-ordered set of extra parameters we can stick on the end of types to attach additional meaning.
@ChrisRackauckas Can't we do something like
now we have
In principal, other packages should be able to add their own tags as they please without any baking in ahead of time. Of course, the biggest downside to this approach that I see would be that basically all
Tagfunctions would need to be@generatedfor performance which is a total nightmare.However, if we had something that was analogous to
Tuplewhich could have a variable number of parameters and was un-ordered, then perhaps we could make it work.That is, you would need a type
Tagsuch thatand you would need to be able to write methods like
and have it apply to a
x::Array{T, N, Tag{Sorted, Adjoint}}(and thus causing a new host of ambiguities)56 remaining items
MasonProtter commentedon Sep 29, 2020
Huh, interesting I had definitely tried the angry-face operator there and failed to make it work for me, but I probably just did something silly. Thanks for pointing that out. As I said earlier today on Zulip,
Tokazama commentedon Sep 30, 2020
I think that this is a step in the right direction for traits in general. For example, an issue brought up on Zulip was that someone wanted to add the table interface (i.e.
istable) to a bunch of types that did not have a common supertype but had another related trait. A simple solution would be doingistable(x) = istable(tags(x))instead.martinholters commentedon Oct 6, 2020
This is an interesting discussion and being able to attach extra tags to types seems like it might be quite useful, but I'm not convinced it solves the problem it's intended to here. What made me skeptical is the appearance of
AdjointandSortedin the same example somewhere above. That makes sense for vectors, but if you think about higher-dimensional arrays, you see the problem coming. Imagine (and assume for the sake of discussion) theSortedtag is also defined for higher-dimensional arrays, meaning the array is sorted in iteration order. Now one could add theSortedtag when verifying the contents are sorted, andadjointwould attach theAdjointtag. But wait! the adjoint of a sorted matrix is in general no longer sorted, soadjointwould need to be aware of theSortedtag and remove it. Would it also need to remove other tags from other packages? Also the order of operations matters: Taking the adjoint first, and then verifying the result is sorted, one could safely attach theSortedtag. But that's more or less where we're at now:Sorted{<:Adjoint}is sorted,Adjoint{<:Sorted}is not (necessarily) sorted, forSomeOtherWrapper{<:Sorted}we don't know.So I'm afraid for the problem of array wrappers, we replace the combinatorial explosion of wrapper combinations with the same explosion of tag combinations. Or can someone give a brief example, how, say,
Sorted,Adjoint,TrackedArray, andSizedArray, all worked together more easily using tags? Ideally with no code using definition fromTrackedArrayandSizedArrayat once.pablosanjose commentedon Oct 8, 2020
@martinholters: good points. Let me rephrase your comments to digest their consequences. You are essentially saying that if tags are commutative (i.e. their order doesn't matter, so we encode them with a
Unioninstead of aTuple) they need to encode orthogonal information. At the very least they should never conflict with each other. One should be able to add any tag in any order without contradicting (i.e. having to modify) any other existing tag.If we instead want to keep tags general (so we can have both
SortedandAdjointtags, which are not orthogonal), then tags should necessarily be non-commutative. Wrapper types are already explicitly non-commutative. What would we gain with tags over wrapper types then? As presented in the OP, the advantage would be to be able to dispatch on a given tag regardless of the order it occupies in the tag list. But that has little value, I think, as the order is crucial.Matrix{Int}{Sorted, Adjoint}does not allow the same algorithms asMatrix{Int}{Adjoint, Sorted}, as @martinholters notes. Or another example: it doesn't make sense to dispatch on anMatrixwith theUpperTriangulartag ifAdjointwas added after it, because then it is actuallyLowerTriangular. So, it would seem that if we are adamant about allowing general, non-orthogonal tags, we might just as well stick to wrappers.What we could perhaps attempt in relation to the problem in the OP is to allow defining equivalence classes of types in terms of commutation rules of wrappers (or tags), such as
Then, if we write a dispatch like
f(::LowerTriangular{T}) where {T<:AbstractArray}, the type machinery could work out, based on repeated application of the commutation rules, that it also applies tof(::TrackedArray{Adjoint{UpperTriangular{Matrix{Int}}}}). But I wonder whether that is a hopelessly complex task in practice.pablosanjose commentedon Oct 8, 2020
Uhm, I guess there is another aspect in which tags as proposed in the OP are prefereable to wrappers: they don't require unwrapping to access the fields of a type. The interface of a tagged type would not change as a result of the added types. So the above stuff on commutation rules should actually be reformulated in terms of non-commutative tags instead of wrappers so that the same code of the
fmethod could work on types with equivalent sets of tags.martinholters commentedon Oct 19, 2020
But that only holds if the tag (née wrapper) does not interfere with how the internals are to be interpreted. So most algorithms would have to differentiate whether
Adjointis present or not, which would also mean that those that don't would have to opt-in to ignoring it. (Otherwise, functions unprepared for theAdjointtag could silently give wrong results.) That doesn't sound that much better than having to peel off a wrapper. So maybe the tag idea shines for additional information, as in aSortedtag? Not really, the problem persists for mutating functions. And as we don't distinguish mutating/non-mutating functions on the language level, that doesn't really gain us anything.MasonProtter commentedon Oct 23, 2020
Yes, I agree this is a bad fit for
Adjoint. I think the most attractive use for this is things likeSortedand that it gives people a way to 'alias' existingstructs and have a little copy that they can put their own methods on and treat differently without having to do all the extra stuff involved with making wrappers.MasonProtter commentedon Oct 23, 2020
@JeffBezanson I think at least for the purposes of labelling the fields of
structs, we'd be forced for sanity reasons to say that e.g.can only store the un-tagged version. However, I wonder if in all other circumstances, we could get away with having it be 'abstract'? i.e. people can write
and then that would be compatible with
Vector{Int; MyTag}? This has the downside of being an extra rule that people have to remember about spelling types though.bramtayl commentedon Nov 18, 2020
One way to deal with the whole trait/multiple inheritance thing would just be to have a macro for appending to union types. Like if you have
A user could bestow a trait on a new thing
ParadaCarleton commentedon Nov 5, 2023
Question; is this proposal related to the tagged unions implemented in other programming languages, and in some Julia packages?
More broadly, in the time since this was first proposed, has anyone written a possible ecosystem or package solution (not in base) that fixes this/provides this feature (like how there are packages fixing the lack of multiple inheritance, traits, etc. in Julia)?
MasonProtter commentedon Nov 5, 2023
No.
ParadaCarleton commentedon Nov 8, 2023
To clarify, I'm not asking because of the array--I'm asking because the original example in this thread,
Adjoint, looks like it could be implemented by having arrays behave like unions with two basic cases (Adjointand notAdjoint). @ChrisRackauckas would this solve the original problem?ChrisRackauckas commentedon Nov 8, 2023
That addresses the problem of Adjoint, but not Tracked, Symmetric, and every other property someone would want to add.