How do I correctly make an "interface" in Julia?

General Usage
1

With multiple dispatch I am able to specialize any function already written to a type, but when it comes time to define my own “interfaces” (although here they are just generic functions) I get a bit confused.

I want to translate this idea to Julia:

Nestable<B, L> {
   branch(n:Nestable<B, L>): Nestable<B, L>[]
   construct(value: B, branches: Nestable<B, L>[]):  Nestable<B, L>[]
   attach(n:Nestable<B,L>, branches: Nestable<B,L>[]): Nestable<B,L>[]
   value(n:Nestable<B, L>): B
   isLeaf(n:L | Nestable<B,L>): n is L
}

This type defines a generic set of functions that work with anything that can be nested.
The naive approach gives me:

# i'm not sure what value this has when I can't use the type params
function isleaf(n::Any)::Bool end 
function value(n::Any)::Any end 
function attach(n::T, branches::T)::T where T end 
function construct(value::Any, branches::T)::T where T end
# AbstractArray might even be too specific, Set, Map etc are all fine. Any iterable will do.
function branch(n::T)::AbstractArray{T} end

I tried to look for a Iterable<T> idea in Julia to get some inspiration but noticed that instead Julia chooses to use functions to define behavior, not types. This is cool and seems powerful but I’m not sure how to apply it to my use case.

Any thoughts? Here’s one of the Nestable related functions I’m trying to port over:

typescript
// this is a concrete example implementation for arrays but i would want to be more general
export type Branch<B, L> = [B, ...(L | Branch<B, L>)[]]
// Ideally I'd be able to say Tree<Branch<B, L>> = L | Branch<B, L>
export type Tree<B, L> = L | Branch<B, L>
export type Forest<B, L> = Tree<B, L>[]

/**
Very generic tree transform. 
Takes 3 functions and a branch and 
returns a new branch where the values are mapped, 
the leaves are transformed, and the nodes themselves are also transformed. 

By default branches generated by transforming leaves are transformed by `n`. 
If you don't want this, then pass `false` for the `deep` parameter. 
*/
function transform<B, L, B2, L2>(
    l: (t: L) => Tree<B2, L2>[], 
    b: (b: B) => B2,
    n: (t: Branch<B2, L2>) => Forest<B2, L2>[],
    tree: Branch<B, L>,
    deep: boolean = true): Branch<B2, L2> {  
  return construct(b(value(tree)), branch(tree) |> R.chain(
    (x: Tree<B, L>) => isLeaf(x) 
      ? l(x) |> (deep ? R.chain((y: Tree<B2, L2>) => isLeaf(y) ? [y] : n(y)) : identity)
      : n(transform(l, b, n, x)) 
  ));
}

// identity = x -> x 
// chain composes functions together
1 Like
2

Julia doesn’t have a formal concept of interfaces (yet?). My understanding is that most people agree it would be useful but finding an implementation that works is difficult.

All you can currently do is use informal interfaces, writing code that only uses functions on structs rather than their properties. For example, the informal dict interface has 9 functions like getindex, setindex, haskey etc. Almost all dict-related code uses these functions, rather than any internals of a dict, by convention. So you can implement your own type with all these functions and expect it to work anywhere a dict works – see e.g. ThreadSafeDicts.jl

So you couldn’t really build functions that work on anything Nestable. Instead, you could implement the functions isleaf, value, etc. on various types, and then you’d have an informal “Nestable” interface. You could define functions like transform that worked on any type for which you had implemented the Nestable interface.

4 Likes
3

That’s not entirely true. While the language itself doesn’t have built-in interfaces, there are several third-party packages that propose designs for this feature.

See also this discussion:

3 Likes
4

Here the correct link: GitHub - mrufsvold/DuckDispatch.jl: If it quacks like a duck... dispatch on it!

1 Like
5

I tried to implement this using DuckDispatch.jl, and this definition introduces a number of very complex nuances that I’ve thought about but haven’t had time to implement.

Namely:

  1. Dispatching on two interfaces (Nestable and Iterable{Nestable})
  2. Dispatching a method where the DuckType is not a top-level type for any argument – construct(::B, Iterable{Nestable}).
  3. Annotating the return type of a method as being a DuckType.

None of these are intractable, but they are delicate and require some internals black magic.

Anyway, at this time, DuckDispatch can’t help you with this intricate of an Interface declaration, but hopefully, it will soon!

1 Like
6

Thank you all for the help.

I like the multiple dispatch approach… interfaces are clunky because you have to introduce extra names and stick to the types that are defined and define either everything or nothing. This feels like the “limit” of interfaces which is great.

One more snag I ran into is that I cannot define recursive types in Julia. I can define recursive structs, but that’s it. So I can’t write ArrayBranch{B, L} = Vector{Union{L, ArrayBranch{B, L}}}. Ragged arrays are one main type of tree I’m trying to process - how best can I express this?

I tried to get a simpler Rose Tree working and ran into some issues there too:

abstract type Branch{V, L} end 
Tree{B} = Union{L, B} where {V, L, B <: Branch{V, L}}
Forest{B} = Union{
  <: AbstractVector{Tree{B}}} where {V, L, B <: Branch{V, L}}

# Trying to make this work with Branch type
function isleaf(n::B)::Bool where {V,L, B <: Branch{V, L}} end 
function value(n::B)::V where{V, L, B <: Branch{V,L}} end 
function attach(n::B, branches::Forest{B})::B where {V, L, B <: Branch{V, L}} end 
function construct(value::V, branches::Forest{B})::B where {V, L, B <: Branch{V, L}} end
function branch(n::B)::Forest{B} where {V, L, B <: Branch{V, L}} end


abstract type RoseBranch{V, L} <: Branch{V, L} end 
TupleRoseBranch{V, L} = Tuple{V, Forest{<: RoseBranch{V, L}}}

But sadly

julia> isa((1, [2]), TupleRoseBranch{Int, Int})
false #oops, should be true

When I did some inspection I got

julia> Forest{RoseBranch{Int, Int}}
AbstractVector{<:Union{L, B1} where {L, B1<:Branch{B, L}}} 
                              where {L, B<:Branch{RoseBranch{Int64, Int64}, L}} 
(alias for AbstractArray{<:Union{L, B1} where {L, B1<:Branch{B, L}}, 1} where {L, B<:Branch{RoseBranch{Int64, Int64}, L}})

For some reason Julia is assigning RoseBranch to V instead of B and forcing B1 to be <: Branch{B< L} instead of <: RoseBranch{B, L}

This is also not working:

julia> Tree{RoseBranch{Int, Int}}
Union{L, B} where {L, B<:Branch{RoseBranch{Int64, Int64}, L}}

Any ideas how to fix this?

7

Even this basic example I’m not able to get working:

julia> abstract type RoseBranch{V, L} end
julia> TupleRoseBranch{V, L} = Tuple{V, Vector{Union{<: RoseBranch{V, L}, L}}}
Tuple{V, Array{Union{RoseBranch{V, L}, L}, 1}} where {V, L}

julia> isa((1, [2]), TupleRoseBranch{Int, Int})
false

And neither did this:


julia> struct RoseBranchS{V, L} <: RoseBranch{V, L}
         v::V
         branches::Vector{Union{<: RoseBranch{V, L}, L}}
         end

julia> RoseBranch
RoseBranch

julia> RoseBranchS{Int, Int}
RoseBranchS{Int64, Int64}

julia> RoseBranchS{Int, Int}(120, [123])
RoseBranchS{Int64, Int64}(120, Union{Int64, RoseBranch{Int64, Int64}}[123])

julia> RoseBranchS{Int, Int}(120, [123, RoseBranchS(120, [])])
ERROR: MethodError: Cannot `convert` an object of type
  RoseBranchS{Int64, Any} to an object of type
  Union{Int64, RoseBranch{Int64, Int64}}
8

Could you specify your desired data structures? Some examples could also help, I guess.

A Web search leaves me confused. Apparently a ragged array is just an array of arrays. So why are you calling it a tree? Can you help me understand the requirements so I could help you implement this?

Looking at the Wikipedia page, I’m again confused. Why is this called a tree? Does it actually represent a tree in the graph theoretic sense? The Wikipedia page presents some graphs that are not trees.

9

Blockquote
julia> abstract type RoseBranch{V, L} end
julia> TupleRoseBranch{V, L} = Tuple{V, Vector{Union{<: RoseBranch{V, L}, L}}}
Tuple{V, Array{Union{RoseBranch{V, L}, L}, 1}} where {V, L}

In this example you need TupleRoseBranch{V, L} = Tuple{V, Vector{<:Union{<: RoseBranch{V, L}, L}}}. Because a Vector{Union{Int, X} is not a Vector{Int} – Julia’s collection types are invariant, rather than covariant or contravariant.

It’s harder to get the second example to work. This will work:

a = RoseBranchS(120, Int[])
julia> RoseBranchS{Int, Int}(121, [a])
RoseBranchS{Int64, Int64}(121, RoseBranchS{Int64, Int64}[RoseBranchS{Int64, Int64}(120, Int64[])])

But if we add an Int to the second argument, it no longer works:

julia> RoseBranchS{Int, Int}(121, [1, a])
ERROR: MethodError: no method matching (Vector{<:Union{Int64, var"#s3"} where var"#s3"<:RoseBranch{Int64, Int64}})(::Vector{Any})
Stacktrace:
 [1] convert(::Type{Vector{<:Union{Int64, var"#s3"} where var"#s3"<:RoseBranch{Int64, Int64}}}, a::Vector{Any})
   @ Base ./array.jl:665
 [2] RoseBranchS{Int64, Int64}(v::Int64, branches::Vector{Any})
   @ Main ./REPL[7]:2
 [3] top-level scope
   @ REPL[18]:1

Because [1, a] has type Vector{Any} – it doesn’t default to a union type
I think you can make it work with Vector{Union{Int, RoseBranchS{Int, Int}}}([1, a]) but that’s significantly clunkier. Given how challenging it is to get the vectors to have the right types, you might just want to define them as Vector{Any} – it’s unlikely that you’ll be dispatching on such specific vector types.

10

Such recursive types are probably not a sweet spot of Julia’s type system. On the other hand, Julia is dynamically typed and thus, you can get away with much less type information:

struct MyRose
   val
   branches
end

isleaf(node::MyRose) = isempty(node.branches)
value(node::MyRose) = node.val
branch(node::MyRose) = node.branches
attach(node::MyRose, branches::AbstractVector) = MyRose(value(node), vcat(branch(node), branches))
# Note: Such type based dispatch is often harder to get bullet-proof in dynamically typed languages
construct(val, branches::AbstractVector{<:MyRose}) = MyRose(val, branches)

Parametric types are available in Julia, but usually serve different purposes than in statically typed languages:

  1. Information to the compiler to allow for specialized code, i.e., type stability
    For this, I usually just use
    struct MyRose{V,F}
    val::V
    branches::F
end
    and let the compiler figure out whatever types are needed.
  2. Dispatch on argument and element types – most often this does not require deeply nested, abstract types.

If data need to have certain type invariants an inner constructor with @assert can be used. In the end, there are no compile-time type errors anyways.

PS: For inspiration on how an interface for trees might look like in Julia, you may want to check AbstractTrees.jl

3 Likes
11

Hi, thank you again for all the advice.
I don’t know what it means for something to be a tree from a “graph theoretic principle” per se but I am working on a project where there are a lot of trees in various formats, such as:

  • structs (like basic tree node from C++ or something)
  • ‘ragged array’ (maybe the wrong name, I meant something like: GitHub - weavejester/hiccup: Fast library for rendering HTML in Clojure)
  • file system (which is also a tree)
  • tuples (think (tag, attrs, children) or named tuple like format. the last position will hold the children and the rest will have data)

So I want to abstract away the traversals (so I don’t write lots of subtly different ones) and be able to absorb all of those structures and use them. Hence the interface approach.

I looked at that library and I can see all the zero-entry structs being used - yeah that seems complicated. For now I will stick to using concrete implementations and worry about type hierarchies later.

12

I would encourage you to look at Graphs.jl, specifically their API page. There you can see the minimal interface functions you need to define for a type to opt into the whole ecosystem’s Graph traversal, analysis, etc and tooling!

2 Likes