v0.5 "cannot add methods to an abstract type" when overriding call

[dlfivefifty]

I'm updating ApproxFun and this caught me by surprise:

abstract Foo
julia> (f::Foo)(x)=x
ERROR: cannot add methods to an abstract type
 in eval(::Module, ::Any) at ./boot.jl:267

Is this intentional? Is there a way to get around this other than define for each subtype:

julia> immutable CFoo <: Foo end
julia> (f::CFoo)(x)=x

[JeffBezanson]

Yes, unfortunately this is the only capability I could not figure out how to cleanly preserve in #13412. How bad is this for you?

[dlfivefifty]

Not bad actually (only 3 concrete subtypes), but thought I’d double check before working around it.

[vtjnash]

grepping the source, it looks like the (only) problematic definition was: https://github.com/ApproxFun/ApproxFun.jl/blob/cb062d6714412bd342cd7e4682ba7ff9f788b40a/src/Multivariate/Multivariate.jl#L7

[wbhart]

We are hitting this. What is excluded here?

Previously, to define a function for all types that are subtypes of a given abstract type, this would be precisely the syntax used. That seems like a rather fundamental part of Julia.

Or is it only when this syntax is used in combination with an object call overload that is excluded?

Losing that would be rather a blow to us. As you may know, we cannot store all the information we need to define mathematical rings in the type, so we create objects that stand in as types, e.g.

R, x = PolynomialRing(ZZ, "x")

where R is now an object that contains information about the ring of all polynomials in ZZ[x].

However, the mathematical abstraction of a polynomial ring is implemented via a bunch of Julia types, all of which are subtypes of some abstract type.

So it's natural to define methods for all of them at once by overloading the call syntax, e.g.

R() returns 0 in the given ring, or R(1) coerces the integer 1 into the ring.

Before panicking I'd like to understand the change a bit better, and what workarounds there are. But this seems to be a bit of a worrisome and unexpected change.

[KristofferC]

I thought call just changed syntax: 0778a89#diff-5cb043c25dee87c0787a9e1bbbf935baL17

[wbhart]

I think I understand what is happening now. Rather than someone replying in detail, perhaps I can ask if my understanding is correct. I might also take the opportunity to discuss a very related issue which we are hitting, in case it is useful to know about (see further below).

I think call is changing syntax and rather than only being defined for types, it is still defined for objects. The comment in the PR about deprecating call and putting method tables inside types instead refers to implementing that which is formerly known as "call" by putting method tables inside types. This doesn't mean call will be restricted to types, but that objects of a given type will have their call syntax implemented by putting method tables inside the corresponding types. The advantage will be faster anonymous methods. Is this correct?

The only thing disappearing is the former ability to define a method for a given class of types, i.e. all types which are subtypes of a given abstract type. Is this because "call" is now a method and not a generic function?

One place where this will definitely affect us badly is when we want to write a single method that overloads call for all elements of all polynomial rings. E.g. the user may create at runtime R = ZZ[x], S = R[y], T = S[z]. The user may then create polynomials f, g, h each in one of these rings R, S or T. Each of the polynomials f, g, h necessarily has a different type, though all the types belong to the abstract type PolyElem{T} (where T is the type of the coefficients).

We use call to enable things like f(123) to give the value of the polynomial at 123, or f(M) to substitute a matrix M into the polynomial f, etc. It has to be a generic function because the user could in theory substitute absolutely anything into f, g or h.

It's therefore a very serious breakage that we can't overload call for all of these at once using call(R::PolyElem{T}, a).

I would also be quite concerned if a similar thing happened for overloading the array syntax []. We currently write generic functions to overload [] for our objects R, S, T above so that for example U = R["x"] is possible. This creates a polynomial ring over R with variable "x". We use it similarly for matrices.

On a related note, I'd like to take the opportunity to discuss an issue which we hit which we have been surprised has not hit anyone else yet. We accept there is likely nothing that can be done about this, but I want to mention it here in case it helps with future design decisions.

Consider the example of matrices over Z/nZ for multiprecision integer n. The initial thought is to have objects of type Z/nZ. As you know, putting n as a parameter of the type is not really possible, nor desirable (otherwise it would trigger recompilation again and again in multimodular algorithms that used many different values of n).

Therefore, the only option is to have the n in an object, not in the type. Let's call the type in question modint. So objects of type modint will somehow have the residue r associated with them, but also in some way the modulus n.

But now consider Julia's generic algorithms for matrices over a given type. Many of these algorithms require one to be able to create a zero object to insert into the matrix. But the zero function in Julia only takes the type modint as a parameter.

The problem is, the type modint contains no information about n, so it is in fact not able to create the zero object of this type, since it cannot set n.

I'm actually really surprised no one has hit this issue anywhere else. For this reason it would be really useful if functions like zero and one that are used so pervasively in Julia matrix algorithms could take more information from somewhere.

Note that the n really can't be stored in the type itself, since then things would need recompiling for every n.

As things are, we are not able to use any of the Julia generic matrix functionality in Nemo.

The only solution that I can see is to explicitly support using objects in the place of types in Julia, so that things like zero(R) will be used by Julia when constructing arrays over "parents" [1] like R which aren't implemented as types but as objects, e.g. arrays over R = IntegersMod(7).

I mention this only because it directly relates to the call syntax and calling of objects as though they were types.

In fact, in computer algebra, the distinction becomes blurred. Consider ideals A and B of a ring R. We can certainly perform arithmetic operations on A and B such as A*B. So in one sense they behave like objects or values. But we can also think of ideals as sets of elements in the same way that ZZ or a polynomial ring is. So they can also act as "parents". For example, the element 0 of an ideal could be obtained by zero(A) or A().

Of course we can define zero(A) and A() no problems. But this isn't the way the Julia generic matrix algorithms generate a zero object. They will use zero(typeof(A)) which is not sufficient to construct the zero object of "type" (actually parent) A.

As I say, I'm just mentioning it here since it seems like an opportune moment to do so. I'm not expecting anything, just hoping that it might be of use in future planning.

[1] "parents" is the name computer algebraists give to the objects that represent mathematical types such as polynomial rings or Z/nZ that can't be fully modeled using actual types in the programming language of choice.

[tknopp]

Is there a workaround for this? I was so happy to see this happening in 0.4 and now its gone again. In Gtk.jl this would have allowed to remove a lot of macros that are currently used to create widgets. JuliaGraphics/Gtk.jl#134

[vtjnash]

Gtk doesn't need this. In particular, the limitation is that you can't call an instance of a widget, but you can still define constructors for abstract subclasses.

[JeffreySarnoff]

Many things not yet done in Julia need to add methods to an abstract type.

If this capability were to become absent, fundamental expressiveness would be curtailed.
It is already too hard to gather together multifaceted realization as an abstraction, and to project from intrinsically coherent concept through abstraction into specific entityhoods.

Moreover, it is a substantial boon to clear human communication about Julia code.

[JeffreySarnoff]

@JeffBezanson @wbhart @vtjnash
For example, it has been an essential strength of Julia that one could think and code:

The norm of a number that belongs to a division algebra is the square root of the product of that number with the conjugate of that number.

import Base: conj, *, sqrt

abstract DivisionAlgebraNum <: Number
norm{T<:DivisionAlgebraNum}(x::T) = sqrt( x * conj(x) )

and then define specific types, knowing norm(x) does 'just work'.

immutable QuaternionNum{T<:Real} <: DivisionAlgebraNumber
   r::T;   i::T;   j::T; k::T
end
conj{T<:Real}(x::QuaternionNum{T}) = ...
*{T<:Real}(x::QuaternionNum{T}, y::QuaternionNum{T}) = ...
sqrt{T<:Real}(x::QuaternionNum{T}) = ...
...

immutable OctonionNum{T<:Real} <: DivisionAlgebraNumber ...
immutable ComplexNum{T<:Real} <: DivisionAlgebraNumber ...
immutable RealNum{T<:Real} <: DivisionAlgebraNumber ...

[wbhart]

@JeffreySarnoff There's no evidence ordinary generic functions like your norm function will stop working is there?

[JeffBezanson]

Yes, definitions like that still work fine. The change only affects what used to be the first argument of call.

[JeffreySarnoff]

So does this mean that I would not run into this using abstract types and generics on them to code some category theory as an abstraction and then use that to define some basic categories as working types?

[wbhart]

I suspect you would definitely hit it if you tried to define functors using (the replacement of) the call syntax. This could happen if your functors were treated as objects that had properties, which as you know happens. This is actually a very good example.

[wbhart]

One other area where this functionality is really needed is homological algebra. I'd be surprised if it wasn't also extremely valuable to homotopy theory and to group actions in representation theory.

[dlfivefifty]

I've changed the title of the issue as it may have been confusing people

[wbhart]

Just to clarify, my concerns are not theoretical, but practical. Our code broke because of the syntax change, but some of the call overloads we had are no longer possible at all. We have lost actual features because of this change.

[StefanKarpinski]

Can you post the definitions that no longer work?

[wbhart]

The first one we noticed was:

call{T <: RingElem}(f::PolyElem{T}, a) = subst(f, a)

This is for evaluating polynomials at arbitrary things, e.g. elements of other rings or at matrices, etc.

Note PolyElem is an abstract type acting as a type class for all polynomial types in Nemo.

There are various specialisations of this where "a" is a specific type. I'll omit these since they are of the same kind.

(There will be similar things for PowerSeriesElem instead of PolyElem.)

Here are some specific examples from Hecke.jl:

call(O::GenNfOrd, a::nf_elem, check::Bool = true)

This function is for coercing a number field element into the ambient number field of an order.

There's about a dozen similar examples for coercing various things into such. This is done because there are multiple different number field order types.

There is also:

call(M::Map, a::Any)

This is for applying any kind of map in Hecke to anything. Map is an abstract type to which many types belong. Our map objects contain data about the maps.

The guy writing Singular.jl says he has a problem with this change too, but I don't have explicit examples from his code right now. He basically said he used this generic call thing to reduce code duplication. He's modelling a system written in C that uses dynamic types, and instead of duplicating everything for each individual type, he has a generic implementation that he specialises per type.

My biggest concern actually is the project I was about to work on which was an object model for group theory and commutative algebra. I produced a very small prototype some months back which relies heavily on call. I just had a look now and miraculously the prototype doesn't yet make use of abstract types for the first argument. But there's no doubt it will. And this is very worrisome as I just convinced some colleagues to use Julia for this precisely on this basis. I'm visiting them next week as it happens to thrash out the details.

Consider homomorphisms between many different types of groups. The homomorphisms are modeled as objects that can be called. All the homomorphism types will belong to an abstract type, and a fundamental part of the mechanism that allows propagation of new knowledge along the homomorphisms requires generic overloading of call for all homomorphisms (similar to the Map example above).

[yuyichao]

Hmm, so, what was it?

[wbhart]

Sorry, I accidentally pressed enter whilst writing the post. If you look at the post on GitHub itself you will see I've filled in what I wanted to write now.

[StefanKarpinski]

The post is empty.

[wbhart]

Well I see it, but here it is again:

The first one we noticed was:

call{T <: RingElem}(f::PolyElem{T}, a) = subst(f, a)

This is for evaluating polynomials at arbitrary things, e.g. elements of other rings or at matrices, etc.

Note PolyElem is an abstract type acting as a type class for all polynomial types in Nemo.

There are various specialisations of this where "a" is a specific type. I'll omit these since they are of the same kind.

(There will be similar things for PowerSeriesElem instead of PolyElem.)

Here are some specific examples from Hecke.jl:

call(O::GenNfOrd, a::nf_elem, check::Bool = true)

This function is for coercing a number field element into the ambient number field of an order.

There's about a dozen similar examples for coercing various things into such. This is done because there are multiple different number field order types.

There is also:

call(M::Map, a::Any)

This is for applying any kind of map in Hecke to anything. Map is an abstract type to which many types belong. Our map objects contain data about the maps.

The guy writing Singular.jl says he has a problem with this change too, but I don't have explicit examples from his code right now. He basically said he used this generic call thing to reduce code duplication. He's modelling a system written in C that uses dynamic types, and instead of duplicating everything for each individual type, he has a generic implementation that he specialises per type.

My biggest concern actually is the project I was about to work on which was an object model for group theory and commutative algebra. I produced a very small prototype some months back which relies heavily on call. I just had a look now and miraculously the prototype doesn't yet make use of abstract types for the first argument. But there's no doubt it will. And this is very worrisome as I just convinced some colleagues to use Julia for this precisely on this basis. I'm visiting them next week as it happens to thrash out the details.

Consider homomorphisms between many different types of groups. The homomorphisms are modeled as objects that can be called. All the homomorphism types will belong to an abstract type, and a fundamental part of the mechanism that allows propagation of new knowledge along the homomorphisms requires generic overloading of call for all homomorphisms (similar to the Map example above).

[thofma]

I guess as there is no equivalent of call(x::Integer, args...) there is also no equivalent of call{T <: Integer}(x::T, args...)?

I see that this can be overcome by defining call(x::T, args...) for every concrete subtype of T. But what if there are infintely many of them you don't know at parse time? More concretely I am thinking of a "recursive" type as follows:

type A{T <: Integer} <: Integer
  x::T

Then you can construct A{Int}, A{A{...{A{Int}}} but with the new behavior of call I don't know how to overload an object of this type. Before the change I could just do

call{T <: Integer}(a::A{T}, args...) = ...

One solution now would be

call(a, args...) = ...

But this cannot be used as soon as there is another type with the same behavior.

Note that this is not an artificial problem: Think of polynomials f whose coefficients are polynomials whose coefficients are polynomials whose coefficients are polynomials whose coefficients are of type Int. And now I would like to evalute this polynomial using the using the syntax f(a).

I hope I could properly communicate my concerns.

[mbauman]

To be clear: the only restriction here is with defining call for all objects that belong to an abstract supertype with just one definition. You are still able to define call for non-concrete parametric types.

These are ok (I'll use the old 0.4 syntax for clarity):

abstract AbstractFoo
type Bar <: AbstractFoo end
type Baz{T} <: AbstractFoo end

call(::Bar,x) = 1
call{T}(::Baz{T},x) = 2
call{T<:Integer}(::Baz{T},x) = 3
call(::Type{AbstractFoo},x) = 4
call{T<:Union{Bar,Baz}}(::Type{T},x) = 5

These are the cases that are not supported:

call(::AbstractFoo, x)
call(::Union{Bar, Baz}, x)
call{T<:AbstractFoo}(::T, x)
call(a, x)

So your A{T} example is just fine, @thofma.

[thofma]

Thanks for the clarification @mbauman. Very helpful.

I guess one of my problems was that I could not find out how to do this with the new synatx. The following gives me a syntax error:

{T<:Integer}(::Baz{T},x) = 3

As a user it is quite unfortunate to have all cool features of parametric types except for this one. In particular, since it was possible in 0.4. While I don't mind the change of syntax with new versions, but the removing of features from the language (and not providing equivalent functionality) is hard to cope with.

[mbauman]

It does feel a little backwards right now, but you can do it:

(::Baz{T}){T<:Integer}(x) = 4

[toivoh]

The way that I see it, the fundamental problem here is that, given a large number of methods definitions, a data structure is needed to find the most specific match to dispatch a given function call.

Method tables stored per type of the first (implicit) argument are one implementation of such a data structure, but it's not the only possibility. (E.g. in PatternDispatch.jl I built a graph based on the partial order, but I'm not thinking of such major rewrites here. )

How bad would it be to visit the method tables of both a type and it's super types when looking for the most specific match for dispatch?

[JeffBezanson]

Yes, we could do that. It seemed kind of ugly to me but I might just have to deal with it.

[rakeshvar]

+1
Need this feature to work for beauty and ease of coding (in my case).

[marius311]

I haven't been able to find much discussion on this issue either here or on the forums since 1.0 came out. Are there any "new" workarounds for this with 1.0? (while awaiting a fix in 1.x it seems)

[AzamatB]

Bump. Just run into this.

[cossio]

Just got this error in Julia 1.1. Calling abstract types seems like a nice feature to have. Since there have been no comments here for a few months, what is the status of this issue? Will there be a fix eventually or will this remain an error in future versions?

[StefanKarpinski]

This is technically difficult and not a high priority, so I wouldn't hold your breath. Might happen eventually when there are no more important things on Jeff's plate or someone else takes it on.

[findmyway]

Could you share any plan (or hints) for how to implement this feature so that people who wish to have this feature may take some attempts?

(I was surprised to find this error for the first time and thought it should be relatively easy to support this feature. After struggling for a while, I had to admit that there was no easy approach.)

[StefanKarpinski]

@JeffBezanson may be able to provide some guidance.

[JeffBezanson]

This is certainly possible to implement. However, it is necessarily deeply tied to internals of how dispatch works, which is quite complex for performance reasons. So it may not be practical to attempt unless you really want to roll up your sleeves.

Currently (in what can perhaps be seen as a "premature optimization") the dispatch table is split based on the concrete type of the called object. Each TypeName has a mt::MethodTable field with the methods for just that type family (e.g. (f::F{T})() for any T). So a method lookup always starts with typeof(f).name.mt. Instead, we would need a single global MethodTable, and simply add all methods to it and do all lookups in it. I think that can be implemented fairly easily.

The main complication is that that is likely to cause some significant performance regressions in dynamic dispatch (see e.g. #21760 and linked issues), and also in method insertion (which is often the bottleneck in loading packages) and invalidation (the backedges array in MethodTable). Getting back this performance might be difficult, especially since it's not fast enough as it is.

[JeffreySarnoff]

for some purposes, this may suffice

abstract type Abstract end
isabstract(x) = false
isabstract(x::T) where {T<:Abstract} = true

abstract type Abstraction <: Abstract end
isabstraction(x) = false
isabstraction(x::T) where {T<:Abstraction} = true

struct Concrete <: Abstract
    value::String
end
concrete = Concrete("this is abstract")

struct Concretion <: Abstraction
    value::String
end
concretion = Concretion("this is abstraction")

(isabstract(concrete), isabstract(concretion)) == (true, true)
(isabstraction(concrete), isabstraction(concretion)) == (false, true)

[JeffreySarnoff]

@JeffBezanson is a global method table not akin the old "ball of call"?

[AzamatB]

Whoa! So excited to see this fixed! Thank you! :)