Interfaces for Abstract Types

[tknopp]

I think this feature request has not yet its own issue although it has been discussed in e.g. #5.

I think it would be great if we could explicitly define interfaces on abstract types. By interface I mean all methods that have to be implemented to fulfill the abstract type requirements. Currently, the interface is only implicitly defined and it can be scattered over several files so that it is very hard to determine what one has to implement when deriving from an abstract type.

Interfaces would primary give us two things:

• self documentation of interfaces at a single place
• better error messages

Base.graphics has a macro that actually allows to define interfaces by encoding an error message in the fallback implementation. I think this is already very clever. But maybe giving it the following syntax is even neater:

abstract MyType has print, size(::MyType,::Int), push!

Here it would be neat if one could specify different granularities. The print and push! declarations only say that there have to be any methods with that name (and MyType as first parameter) but they don't specify the types. In contrast the size declaration is completely typed. I think this gives a lot of flexibility and for an untyped interface declaration one could still give quite specific error messages.

As I have said in #5, such interfaces are basically what is planed in C++ as Concept-light for C++14 or C++17. And having done quite some C++ template programming I am certain that some formalization in this area would also be good for Julia.

[lindahua]

Generally, I think this is a good direction to better interface-oriented programming.

However, something is missing here. The signatures of the methods (not just their names) are also significant for an interface.

This is not something easy to implement and there will be a lot of gotchas. That's probably one of the reasons why Concepts was not accepted by C++ 11, and after three years, only a very limited lite version gets into C++ 14.

[tknopp]

The size method in my example contained the signature. Further @mustimplement from Base.graphics also takes the signature into account.

I should add that we already have one part of Concept-light which is the ability to restrict a type to be a subtype of a certain abstract type. The interfaces are the other part.

[IainNZ]

That macro is pretty cool. I've manually defined error-triggering fallbacks, and its worked pretty well for defining interfaces. e.g. JuliaOpt's MathProgBase does this, and it works well. I was toying around with a new solver (https://github.com/IainNZ/RationalSimplex.jl) and I just had to keep implementing interface functions until it stopped raising errors to get it working.

Your proposal would do a similar thing, right? But would you have to implement the entire interface?

[lindahua]

How does this deal with covariant / contravariant parameters?

For example,

abstract A has foo(::A, ::Array)

type B <: A 
    ...
end

type C <: A
    ...
end

# is it ok to let the arguments to have more general types?
foo(x::Union(B, C), y::AbstractArray) = ....

[tknopp]

@IainNZ Yes, the proposal is actually about making @mustimplement a little more versatile such that e.g. the signature can but does not have to be provided. And my feeling is that this is such a "core" that it is worth to get its own syntax. It would be great to enforce that all methods are really implemented but the current runtime check as is done in @mustimplement is already a great thing and might be easier to implement.

[tknopp]

@lindahua Thats an interesting example. Have to think about that.

[tknopp]

@lindahua One would probably want your example to just work. @mustimplement would not work as it defines more specific method signatures.

So this might have to be implemented a little deeper in the compiler. On the abstract type definition one has to keep track of the interface names/signatures. And at that point where currently a "... not defined" error is thrown one has to generate the appropriate error message.

[ivarne]

It is very easy to change how MethodError print, when we have a syntax and API to express and access the information.

Another thing this could get us is a function in base.Test to verify that a type (all types?) fully implements the interfaces of the parent types. That would be a really neat unit test.

[tknopp]

Thanks @ivarne. So the implementation could look as follows:

1. One has a global dictionary with abstract types as keys and functions (+ optional signatures) as values.
2. The parser needs to be adapted to fill the dict when a has declaration is parsed.
3. MethodError needs to look up if the current function is part of the global dictionary.

Most of the logic will then be in MethodError.

[tknopp]

I have been experimenting a little with this and using the following gist https://gist.github.com/tknopp/ed53dc22b61062a2b283 I can do:

julia> abstract A
julia> addInterface(A,length)
julia> type B <: A end
julia> checkInterface(B)
ERROR: Interface not implemented! B has to implement length in order to be subtype of A ! in error at error.jl:22

when defining length no error is thrown:

julia> import Base.length
julia> length(::B) = 10
length (generic function with 34 methods)
julia> checkInterface(B)
true

Not that this does currently not take the signature into account.

[tknopp]

I updated the code in the gist a bit so that function signatures can be taken into account. It is still very hacky but the following now works:

julia> abstract A
julia> type B <: A end

julia> addInterface(A,:size,(A,Int64))
1-element Array{(DataType,DataType),1}:
 (A,Int64)
julia> checkInterface(B)
ERROR: Interface not implemented! B has to implement size in order to be subtype of A !
in error at error.jl:22

julia> import Base.size
julia> size(::B, ::Integer) = 333
size (generic function with 47 methods)
julia> checkInterface(B)
true

julia> addInterface(A,:size,(A,Float64))
2-element Array{(DataType,DataType),1}:
 (A,Int64)
 (A,Float64)
julia> checkInterface(B)
ERROR: Interface not implemented! B has to implement size in order to be subtype of A !
 in error at error.jl:22
 in string at string.jl:30

[tknopp]

I should have add that the interface cache in the gist now operates on symbols instead of functions so that one can add an interface and declare the function afterwards. I might have to do the same with the signature.

[tknopp]

Just saw that #2248 already has some material on interfaces.

[StefanKarpinski]

I was going to hold off on publishing thoughts on more speculative features like interfaces until after we get 0.3 out the door, but since you've started the discussion, here's something I wrote up a while ago.

---

Here's a mockup of syntax for interface declaration and the implementation of that interface:

interface Iterable{T,S}
    start :: Iterable --> S
    done  :: (Iterable,S) --> Bool
    next  :: (Iterable,S) --> (T,S)
end

implement UnitRange{T} <: Iterable{T,T}
    start(r::UnitRange) = oftype(r.start + 1, r.start)
    next(r::UnitRange, state::T) = (oftype(T,state), state + 1)
    done(r::UnitRange, state::T) = i == oftype(i,r.stop) + 1
end

Let's break this down into pieces. First, there's function type syntax: A --> B is the type of a function that maps objects of type A to type B. Tuples in this notation do the obvious thing. In isolation, I'm proposing that f :: A --> B would declare that f is a generic function, mapping type A to type B. It's a slightly open question what this means. Does it mean that when applied to an argument of type A, f will give a result of type B? Does it mean that f can only be applied to arguments of type A? Should automatic conversion occur anywhere – on output, on input? For now, we can suppose that all this does is create a new generic function without adding any methods to it, and the types are just for documentation.

Second, there's the declaration of the interface Iterable{T,S}. This makes Iterable a bit like a module and a bit like an abstract type. It's like a module in that it has bindings to generic functions called Iterable.start, Iterable.done and Iterable.next. It's like a type in that Iterable and Iterable{T} and Iterable{T,S} can be used wherever abstract types can – in particular, in method dispatch.

Third, there's the implement block defining how UnitRange implements the Iterable interface. Inside of the implement block, the the Iterable.start, Iterable.done and Iterable.next functions available, as if the user had done import Iterable: start, done, next, allowing the addition of methods to these functions. This block is template-like the way that parametric type declarations are – inside the block, UnitRange means a specific UnitRange, not the umbrella type.

The primary advantage of the implement block is that it avoids needing the explicitly import functions that you want to extend – they are implicitly imported for you, which is nice since people are generally confused about import anyway. This seems like a much clearer way to express that. I suspect that most generic functions in Base that users will want to extend ought to belong to some interface, so this should eliminate the vast majority of uses for import. Since you can always fully qualify a name, maybe we could do away with it altogether.

Another idea that I've had bouncing around is the separation of the "inner" and "outer" versions of interface functions. What I mean by this is that the "inner" function is the one that you supply methods for to implement some interface, while the "outer" function is the one you call to implement generic functionality in terms of some interface. Consider when you look at the methods of the sort! function (excluding deprecated methods):

julia> methods(sort!)
sort!(r::UnitRange{T<:Real}) at range.jl:498
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,::InsertionSortAlg,o::Ordering) at sort.jl:242
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,a::QuickSortAlg,o::Ordering) at sort.jl:259
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,a::MergeSortAlg,o::Ordering) at sort.jl:289
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,a::MergeSortAlg,o::Ordering,t) at sort.jl:289
sort!{T<:Union(Float64,Float32)}(v::AbstractArray{T<:Union(Float64,Float32),1},a::Algorithm,o::Union(ReverseOrdering{ForwardOrdering},ForwardOrdering)) at sort.jl:441
sort!{O<:Union(ReverseOrdering{ForwardOrdering},ForwardOrdering),T<:Union(Float64,Float32)}(v::Array{Int64,1},a::Algorithm,o::Perm{O<:Union(ReverseOrdering{ForwardOrdering},ForwardOrdering),Array{T<:Union(Float64,Float32),1}}) at sort.jl:442
sort!(v::AbstractArray{T,1},alg::Algorithm,order::Ordering) at sort.jl:329
sort!(v::AbstractArray{T,1}) at sort.jl:330
sort!{Tv<:Union(Complex{Float32},Complex{Float64},Float64,Float32)}(A::CholmodSparse{Tv<:Union(Complex{Float32},Complex{Float64},Float64,Float32),Int32}) at linalg/cholmod.jl:809
sort!{Tv<:Union(Complex{Float32},Complex{Float64},Float64,Float32)}(A::CholmodSparse{Tv<:Union(Complex{Float32},Complex{Float64},Float64,Float32),Int64}) at linalg/cholmod.jl:809

Some of these methods are intented for public consumption, but others are just part of the internal implementation of the public sorting methods. Really, the only public method that this should have is this:

sort!(v::AbstractArray)

The rest are noise and belong on the "inside". In particular, the

sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,::InsertionSortAlg,o::Ordering)
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,a::QuickSortAlg,o::Ordering)
sort!(v::AbstractArray{T,1},lo::Int64,hi::Int64,a::MergeSortAlg,o::Ordering)

kinds of methods are what a sorting algorithm implements to hook into the generic sorting machinery. Currently Sort.Algorithm is an abstract type, and InsertionSortAlg, QuickSortAlg and MergeSortAlg are concrete subtypes of it. With interfaces, Sort.Algorithm could be an interface instead and the specific algorithms would implement it. Something like this:

# module Sort
interface Algorithm
    sort! :: (AbstractVector, Int, Int, Algorithm, Ordering) --> AbstractVector
end
implement InsertionSortAlg <: Algorithm
    function sort!(v::AbstractVector, lo::Int, hi::Int, ::InsertionSortAlg, o::Ordering)
        @inbounds for i = lo+1:hi
            j = i
            x = v[i]
            while j > lo
                if lt(o, x, v[j-1])
                    v[j] = v[j-1]
                    j -= 1
                    continue
                end
                break
            end
            v[j] = x
        end
        return v
    end
end

The separation we want could then be accomplished by defining:

# module Sort
sort!(v::AbstractVector, alg::Algorithm, order::Ordering) =
    Algorithm.sort!(v,1,length(v),alg,order)

This is very close to what we're doing currently, except that we call Algorithm.sort! instead of just sort! – and when implementing various sorting algorithms, the "inner" definition is a method of Algorithm.sort! not the sort! function. This has the effect of separating the implementation of sort! from the its external interface.