Multiple dispatch issue: cat() and a custom abstract array

[Michael Grant]

Consider the following class hierarchy:

module CVX
immutable Scalar{T<:Number}
abstract AbstractArray{T,N} <: Base.AbstractArray{Scalar{T},N}
type Array{T,N} <: AbstractArray{T,N}

Note in particular that CVX.Array{T,N} is an abstract array of Scalar{T} objects. For performance reasons, it is distinctly advantageous to avoid constructing Base.Array{Scalar{T},N} objects, so I'm overloading the various array manipulation operators to handle CVX.Array specially.

But now consider cat(). What I would like to do is this:

function cat( d::Integer, X::Union(Number,CVX.Scalar)... )
function cat( d::Integer, X::Union(Number,CVX.Scalar,CVX.AbstractArray,Base.AbstractArray)... )

The goal here is to override cat() for the case when there is at least one CVX object present. The problem here, of course, is that this overrides the catchall cat function, even if there are no CVX objects present:

function cat( d::Integer, X::Any... )

Is there an easy resolution to this problem? One solution is for Julia, or me, to define

function cat( d::Integer, X::Union(Number,Base.AbstractArray)... )

function cat( d::Integer, X::Number... )

If I do it, I'd be reimplementing  the generic method, in the first case at least, unless there is a way for me to link these new declarations directly to the existing implementations. Is there?

[Leah Hanson]

Have you tried `import Base.cat` or naming your methods `function Base.cat(...`?

The first example on this page of the manual, specifically the `Base.show` part, is relevant: http://docs.julialang.org/en/release-0.2/manual/modules/?highlight=import

-- Leah

[Michael C. Grant]

Yes, Base.cat is imported. The problem is that my new cat() function overrides the old, even when I don't want it to.

[Miles Lubin]

On Monday, August 4, 2014 2:10:36 PM UTC-6, Michael Grant wrote:

Is there an easy resolution to this problem? One solution is for Julia, or me, to define

function cat( d::Integer, X::Union(Number,Base.AbstractArray)... )

function cat( d::Integer, X::Number... )

If I do it, I'd be reimplementing  the generic method, in the first case at least, unless there is a way for me to link these new declarations directly to the existing implementations. Is there?

You could call the generic implementation by using invoke, e.g.,

function cat( d::Integer, X::Number... ) = invoke(cat,(Integer,Any...), d, X...)

I'm not sure what the performance implications of this are, but it would be easy to check.

[Michael Grant]

This is exactly the kind of thing I was looking for, thanks. In theory, this invoke could be inlined away. But even if it can't, I'm not too concerned about the performance issues. My module would not be loaded except by those who are specifically seeking to use it.

I think it would actually be helpful for cat( d::Integer, X::Number... ) in particular to be implemented in the Base package, just like the all-Number equivalents of hcat and vcat have. I might even offer up a pull request with this addition. But your suggestion will certainly help me resolve the other ambiguity issue.

Thanks again!

[Michael Grant]

[This is a continuation/update on a previous question, but with new problem... click this link to see the original post.]

To briefly review, I have an abstract matrix class that is derived from Base.AbstractArray{Scalar{T},N}, where Scalar{T<:Number} is an object of my own design. The array is truly abstract: it is not a contiguous/dense array of Scalars. In fact, the storage format resembles a compressed sparse matrix, except that each column represents a Scalar. Because of this compressed storage format, the default implementations of cat/vcat/hcat are quite suboptimal, so I need to override them.

Now, this is not a problem, if I define methods that take only my arrays. Unfortunately, I need to be able to accept arbitrary mixtures of my arrays and standard numeric AbstractArrays. What I need is a way to override, say, vcat in such a way that my methods are called when at least one of the arguments is mine. With the help of Miles Lubin, I've been experimenting with invoke; for instance:

# vcat{T}(V::AbstractVector{T}...) (abstractarray.jl:541)
vcat{T}( X::Union(Base.AbstractVector{T},CVX.AbstractVector{T})... ) =
    any(iscvx,X) ? cat_cvxa( 1, X ) :
    invoke( vcat, (Base.AbstractVector{T}...), X... )

The any(iscvx,X) test returns true if at least one of the arguments is an object of mine, and false otherwise. In this way, the standard Base.AbstractVector version of the method can be called if none of my objects are present.

Astute readers already know the problem. In theory, Union(Base.AbstractVector{T},CVX.AbstractVector{T}) is actually just the same as Base.AbstractVector{T}, since my arrays are derived from the base abstract array. So there's an ambiguity here; a potential for a stack overflow, too.

The funny thing is: sometimes this works exactly the way I want it to! That is, if I feed vcat a mix of array types, this is the function that is called. But then, I've rearranged my code a bit more, and now it never calls this modified form of the function. What has never happened, at least not yet, is a infinite loop/stack overflow. But nor has there ever been a warning about the potential ambiguity.

What I'm really looking for, I suppose, is a way to override the previous definition of this method, but somehow be able to invoke the overridden version if my test demands it.

Honestly, I think part of the problem is that Base.AbstractArray is not taking its status as an abstract class seriously. Many of the implementations of vcat, hcat, cat, and other functions assume a storage format and proceed as if they know best how every possible subclass would want to handle heterogenous sets of arrays. Honestly, I think that most of the implementations in abstractarray.jl ought to be relegated to the Array class; let ever concrete class determine for itself how to efficiently navigate its storage when concatenating matrices. Alas, I think that attempting to do that would run into some of the very problems I'm facing here.

Any suggestions would be welcome! The one thing I am considering that I know would work is to remove Base.AbstractArray as as subclass of mine. Then the Union above would no longer be trivial, and there would be no ambiguities to deal with. Unfortunately, that would mean I'd have to reimplement a lot of the convenience functions that do work well in abstractarray.jl and elsewhere; including, for instance, showarray.

Thanks for listening

Michael

[vav...@uwaterloo.ca]

Michael,

I am much more of a newbie at Julia than you, but it seems to me that there is a brute-force solution to this problem, namely define a few dozen methods:

vcat(A1::CVXArray{T}, rest::AbstractArray{T}...)

vcat(A1::AbstractArray{T}, A2::CVXArray{T}, rest::AbstractArray{T}...)

vcat(A1::AbstractArray{T}, A2::AbstractArray{T}, A3::CVXArray{T}, rest::AbstractArray{T}...)

Maybe you could automate the generation of all of these with a Julia macro?  

It would be rare for a user to have a vcat statement with more than a handful of arguments, so you should be able to cover all the cases that would ever occur in practice.  You could define the 100th in this sequence to throw an error, so that if any user ventured outside the range of cases covered, at least he/she would know that something is wrong.

-- Steve

[Michael Grant]

Thanks, Steve. I certainly think this will work if I need it to.

I actually managed to squeak out a reasonably compact solution by overriding Base.cat_t, an unexported function in abstractarray.jl used by cat. Here's its signature:

function cat_t(catdim::Integer, typeC, A::AbstractArray...)

typeC is actually a Type, computed by applying promote_type to all of the element types of the abstract arrays.

So I defined some promote methods to ensure that if even one CVX array appears in the list, the promoted type will be CVX-specific, and I can pick that up.

Base.cat_t{T}( catdim::Integer, ::Type{Scalar{T}}, X::Base.AbstractArray... ) = cat_cvx( catdim, X )

Of course, this is a bit fragile, because it depends on unexported behavior. But by having this discussion here and on the GitHub issues page, we can hopefully find a solution that will work more generally.

[Tim Holy]

On Monday, August 04, 2014 01:10:36 PM Michael Grant wrote:
> If I do it, I'd be reimplementing the generic method, in the first case at
> least, unless there is a way for me to link these new declarations directly
> to the existing implementations. Is there?

Check out `invoke`, it may help you.

--Tim