Canonical Julian way to represent multiple implementations of same algorithm

General Usage
1

Suppose I have some number of different implementations of the same algorithm, or more generally just multiple implementations meeting the same requirements (i.e. identical inputs give identical outputs, modulo usual floating point considerations). All the implementations have the same argument list. Is there a best practice/most Julian way to include all of these in the same module such that the user can choose between them? Let’s assume that there isn’t a priori any reason to prefer one algorithm over the other, although it might be nice for there to be a default.

Alternatives that come to mind:

  1. Just give them different names, i.e. alg_approach_1(), all_approach_2, etc. In this case a default would be expressed simply as alg() = alg_approach_1().
  2. One entry point function with an if block calling an algorithm based on an argument, i.e. alg(approach::T) (in this case, what’s the best type for T? Symbol? Enum? In this case the default would be alg() = alg(a) where a results in the default implementation being called.
  3. Dispatch on a value type, i.e. one method of alg(::Val{a}). Very similar to the above, and again what would be the best type for a? Here it would be alg() = alg(Val(a)) where a is the default.
  4. … something else?

The value type dispatch method (#3) strikes me as the best way to go in terms of an API decision as it ties the implementations together by more than just a naming convention, will show any docstrings together, and should (?) be more efficient by avoiding an if block.

I’ve read the relevant docs on value types but they don’t really (to me anyway) suggest if this is a good use case for them, only that they are an option and that there are certain pitfalls to avoid.

3 Likes
2

One way is to use Singleton Types, with one type per implementation. Then your dispatch on that type instead of the Val type. This is a little more intentional than the Val-type approach because users can’t accidentally pass in an unsupported Val. This pattern is pretty common for specifying algorithms to solve a problem through Julia, for example this list of ODE solvers.

8 Likes
3

The singleton types would also be my proposal.
If the algorithms have even similar subsets you could dispatch there as well, you could also build a certain Hierarchy of algorithms

abstract type AlgorithmType end
struct MyAlg1 <: AlgorithmType end

and then have alg(::MyAlg1, args...) which might be nicer than value dispatch?
Your default (with arguments) would be alg(args...) = alg(MyAlg1(), args...)

edit: semantically the alg function could even be called run or start?

2 Likes
4

I think I follow… So you mean something like

abstract type Implementations end
struct Implementation1 <: Implementations end
struct Implementation2 <: Implementations end

alg(::Implementation1) = pi
alg(::Implementation2) = pi

result1 = alg(Implementation1())
result2 = alg(Implementation2())

?

I guess in both cases you get a MethodError if you supply an unsupported Val or singleton instance. But I kind of like that the singleton types technique plays a bit nicer with tab-complete.

In principle are both techniques equivalent performance-wise? I’m guessing that if DifferentialEquations.jl uses this that it’s pretty Julian too. Also looking at its use there I guess it has the additional benefit that the different algorithm types can be passed parameters which may be relevant for one algorithm but not others.

Thanks for this suggestion!

1 Like
5

You might also take a look at how Julia handles sorting. These algorithm types are also useful for holding parameters for each algorithm (for example, the partial sorts parameterize how much to sort). In any case, it uses the different types to dispatch to different algorithms just like others are suggesting here.

3 Likes
6

More or less, yeah, depending on how you construct the Val-type.

Technically Val(a) is type unstable, unless the compiler know the value of a at compile-time, but depending on how your users are calling alg this may not be a necessary concern. The Val type shouldn’t be more performant, if that’s your concern.

7

Exactly, the error message is a bit more helpful if your algorithm type does not exist – and sure storing a few (algorithm dependent) parameters in there is another advantage. I‘ve seen this approach in a few places, we for example use it to distinguish manifolds in Manifolds.jl as well.

8

More in general implementations don’t need to be SingleTon types… they can be any normal type whose properties host algorithm parameters… so the user can call a default my_general_algo(), my_general_algo(implementation=Implementation1(), or my_general_algo(implementation=Implementation1(option=foo) …

This allows implementations that take different parameters… I use this approach for example in BetaML neural network train!(nn::NN,x,y; opt_alg::OptimisationAlgorithm=ADAM(), [...]) function, where the user can call is with train!(nn,x,y), train!(nn,x,y;opt_alg=SGD()), train!(nn,x,y;opt_alg=SGD(η=t -> 1/(1+t^2), λ=0.5)) or subtype OptimisationAlgorithm, implement a couple of functions (that are those called within the train! function) and provide his/her own optimizer…

2 Likes