Add an abstract type for `AbstractTrees` to `AbstractTrees.jl`

[roland-KA]

I'm currently implementing a plot recipe for decision trees in order to be able to visualize all decision trees within the MLJ-package.

The goal is a plot recipe that

1. has no dependency on Plots.jl
2. is independent of any specific decision tree implementation

Goal 1 is an inherent characteristic of plot recipes. So we have reached it just by using plot recipes. Goal 2 is realised by requiring each decision tree implementation which wants its trees to be visualized to implement a narrow part of the AbstractTrees-interface (namely children and printnode).

I have already done such an implementation for DecisionTree.jl (see https://github.com/JuliaAI/DecisionTree.jl/blob/dev/src/abstract_trees.jl). The plot recipe itself exists also (see JuliaAI/DecisionTree.jl#147; the recipe is btw so general that it can be applied to each tree implementing the above mentioned interface, it isn't restricted to decision trees).

The only missing part to make all that work, is a type for dispatch. If we have a tree which we would like to plot (e.g. an instance of DecisionTree) then we want to be able to call plot(tree). In order for plot to chose the correct plot recipe, tree must be of the type that is associated with the plot recipe.

As we want a recipe that is independent of any specific decision tree implementation, this type has to be independent of all these implementations. Therefore I have defined a new abstract type AbstractNode.

The question is now, where this new type should be placed. A very natural place would be AbstractTrees.jl (as the AbstractTrees-interface is already used as a common denominator).
Therefore the question: Could such an abstract type be added to AbstractTrees.jl?

BTW: If AbstractTrees.jl wouldn't be "just" an interface but define also a type (like AbstractTree), the whole problem wouldn't exist at all).

@ablaom: Do you want to add some remarks?

[oscardssmith]

the hard thing here is that not all trees in abstract trees have a node, and those the do often have a more useful super type than tree node.

[roland-KA]

@oscardssmith, the name of the new type doesn't matter for my issue. It's about having a type (in contrast to not having a type), because dispatch needs a type. We could also call it AbstractTree, if that makes things easier.

[roland-KA]

I'm currently implementing the AbstractTrees-interface also for BetaML/DecisionTrees and noted that they define in that package an abstract type called AbstractNode.

So in order to avoid confusion, it would even be better to name the abstract type I need for the plot recipe AbstractTree.

Just to make the idea of the new type clearer: An object of (sub)type AbstractTree would be something that implements (partially) the AbstractTrees-interface.

The question here is, how much of the AbstractTrees-interface it should implement, in order to qualify for being of type AbstractTree?

• For my plot recipe I need children as well as printnode.
• But I would also be happy, if we could agree on a minimal interface, consisting only of children.

Comments on this are welcome 🤓.

[jlumpe]

The interface section of the documentation currently says "All trees must define children" but could probably be clearer that this is the only thing they are required to implement.

[roland-KA]

Thanks for the hint! In the top section it also states:

"Using this package involves implementing the abstract tree interface which, at a minimum, requires defining the function AbstractTrees.children for an object."

So my question from above is already clearly answered. That's good news! 😊

Then I would suggest that we add the new abstract type

abstract type AbstractTree end

to the AbstractTrees-package (presumably in base.jl?) and define that:

Any object x for which holds isa(x, AbstractTree) must implement at least children.

Would that be a solution everybody could agree on?

[jlumpe]

@roland-KA what exactly is your use case for the AbstractTree type? I'm not familiar with DecisionTrees.jl, but I imagine that a decision tree has to define some additional attributes/methods besides just conforming to the AbstractTrees API. Why not just an AbstractDecisionTree type?

There is also an issue with the AbstractTree name - despite the name of this package the core type should really be AbstractNode. There is a whole tree-vs-nodes issue with this package that so far hasn't been addressed. Any node (something that implements children()) can be considered as a tree with itself as the root, but there are other ways a type could represent a tree without also being a node (IndexedTree is the current one, but I can envision others). I've definitely put some thought into having these base classes but that would be for an API which is aware of the tree-vs-node issue and needs to dispatch on one or the other.

[roland-KA]

Use Case

@jlumpe the use case is, as described above, to enable a visualization of (arbitrary) decision trees. We are currently focused on decision tree implementations within MLJ, but the concept is not limited to that meta-package.

The visualization should meet the following goals:

1. no dependency on Plots.jl
2. independence of any specific decision tree implementation

We have realised these goals by using a plot recipe and by requiring each decision tree to implement the AbstractTrees interface (see JuliaAI/DecisionTree.jl#147 for details and one recent version of the recipe).

A few months ago I already published this article on Towards Data Science, where I explain the whole concept.

but I imagine that a decision tree has to define some additional attributes/methods besides just conforming to the AbstractTrees API.

No, I could indeed implement a plot recipe that depends exclusively on the AbstractTrees-API (only children and printnode are required).
Remark: But perhaps the explanation in "Use Case (Part 2)" (see below) answers this question completely.

Why not just an AbstractDecisionTree type?

There are at least two reasons for an AbstractTree-type:

1. The decision trees implement the AbstractTrees-interface (not a, currently not existing, AbstractDecisionTree-interface) and I think it's a good idea to build such things on existing packages like AbstractTrees and not reinvent the wheel again.
2. The plot recipe is actually so generic, that it can plot each tree conforming to the AbstractTrees-API (not only decision trees).

... and perhaps it is a good occasion to grow the user base of AbstractTrees.jl and thus appreciating the work that you and your fellow contributors have put into that package 😊.

Current state of implementation

Just to make the situation clear. We already have

• an implementation of a plot recipe that meets the above mentioned requirements
• an implementation of the AbstractTrees-API for JuliaAI/DecisionTree.jl
• an implementation of the AbstractTrees-API for BetaML/DecisionTrees.jl

The only part that lacks in order to make the whole thing publicly available is this abstract type that allows us to call plot in the following way

tree :: TreeImplementingTheAbstractTreesAPI
plot(tree)

and thus enabling plot (via dispatch on that type) to chose our plot recipe.

Tree vs. Node

Yes there are indeed different ways to implement a tree. In some implementations the tree is simply represented by the top-most node. But for the use case described above, this distinction is irrelevant, as it relies only on children (and printnode to have some meaningful content when printing).

And from a more general software engineering perspective, I think this distinction shouldn't show up in a type definition. It is the very purpose of an abstract data type (like a tree) to hide details of the implementation.

But perhaps I just don't know what applications you have in mind, where this distinction should show up on a type level. Do you have any examples?

BTW: This wouldn't conflict with the definition of an AbstractTree-type. You could simply define subtypes like AbstractNodeTree and AbstractRealRootTree (or whatever that would be called).

[roland-KA]

To make it easier to understand, I have created a diagram of the intended structure, which I described above:

Here we can see, that AbstractTrees.jl plays an important role. All tree implementations which want the ability to be visualized, have to implement the AbstractTrees-API - but only that! It's the only dependency they get in this scenario.

The plot recipe DecisionTreesRecipe.jl has also a dependency on AbstractTrees.jl (because it uses the AbstractTree type). But again, it's the only dependency it has.

Only a script that wants to visualize a tree has dependencies to several components: To the tree itself, to the plot recipe and to Plots.jl, which is finally responsible for plotting.

[roland-KA]

Use Case (Part 2)

Perhaps I need to explain the use case a bit in more detail. Not everybody is familiar with plot recipes.

Each plot recipe is defined on a type (that's why I need something like AbstractTree). This type is used on the call to plot to select the right recipe. When plot gets passed a tree (as in the example above), and tree isn't an object which plot knows how to plot, then plot searches for a plot recipe which is defined on the type of tree.

For that reason all tree implementations not only have to implement children and printnode but they have to "present" themselves as a subtype of AbstractTree. E.g. in BetaML/DecisionTrees we added for that purpose the following type:

struct InfoNode{T} <: AbstractTree
    node    :: DecisionNode{T}
    info    :: NamedTuple
end

The decision tree from BetaML is in its basic form a DecisionNode, but we wrap that into this new structure InfoNode which is a subtype of AbstractTree.

And for plotting we pass actually an object of type InfoNode to plot (not a DecisionNode).

[ablaom]

Be good to get a decision here. @roland-KA 's suggestion is clear, and the use-case comprehensively explained.

In view of discussion at #116, AbstractNode sounds like the best name.

[roland-KA]

Hi alltogether,

it's now almost one month since I explained my use case in detail and there hasn't been any feedback since. I understand that many may be (or have been) on vacation during this time. But it would be nice to get some answer, so we know how to proceed with our project, because this issue stalls our works completely.

If you need more details on the use case, feel free to ask. If you object the proposal, please say so (and explain why) and of course the most pleasing answer would be that you add the abstract type within a reasonable timeframe 😃.

[roland-KA]

Hi @jlumpe, @ExpandingMan, @timholy, @oscardssmith you seem to be the most active contributors/maintainers of this package, so I would appreciate your opinion, decision or comment on this issue.

Can we add an abstract type AbstractTree to this package as proposed above?

[ExpandingMan]

Sorry, we've been pretty distracted by solving iteration without abusing the compiler, so those of us who've worked on this package recently have been very focused on that (I also am not a maintainer... I don't think, so I wasn't getting notifications on this thread).

Anyway, I'm going to have to come back and read the above extremely carefully, but so far my take on your problem is that you have a whole bunch of types that all implement the AbstractTrees interface and you want them to have a common abstract type. In that case, the question this issue needs to answer is: should that type be defined in AbstractTrees.jl or somewhere in plot recipes world?

My initial reaction to this is pretty firmly toward the latter, that you should define an abstract type somewhere in your own packages and that AbstractTrees.jl should not implement this. The reason is that trees in general do not have and cannot have a common abstract type. For example, nested arrays are tree nodes, but they cannot descend from a node type since they clearly need to be AbstractArray. This is ultimately attributable to the broader problem with Julia that type hierarchies and dispatch are global rather than contextual (at least that's my take on the problem, others have suggested multiple inheritance which I personally don't want). Hence, the existence of non-dispatching interface packages such as AbstractTrees.jl (the naming of which is a bit unfortunate) and Tables.jl.

In spite of the above, it could still be argued that the AbstractTree you are looking for should be defined here. My main problem with that is that I don't see a clear use case for it. Maybe it can provide some clever solution to our ongoing type-stability recursion problem, but it's certainly not immediately obvious to me how it would do that.

So, my question at this point is: why not define an AbstractTree somewhere in the plotting ecosystem instead of here?