Multiple dispatch design with different algorithms and default values


#1

We are designing a generic interface for a library to take expectations of distributions , and would love some help trying to get the dispatch design correct. The basic idea is that there are a set of different algorithms (which we are writing) which can be applied to different types (which come from other libraries). There is a default algorithm that works for any of the types, but we want to change which is the default algorithm used based on the particular type. Lets start by defining some abstract types to help us out:

#These come from other libraries...
abstract type AbstractValue end
type Value1 <: AbstractValue end
type Value2 <: AbstractValue end

#These are in our package, and we can define these in whatever way is easiest.
abstract type AbstractAlgorithm end
type Algorithm1 <: AbstractAlgorithm end
type Algorithm2 <: AbstractAlgorithm end

The set of algorithms implementations is then a bunch of f(v::AbstractValue, alg::AbstractAlgorithm) A few of the principles (which I will condense to a test-suite for the impatient) are

  • There always needs to be a concrete AbstractValue (i.e., think of this as algorithms on Distributions.jl)
  • For any AbstractValue without any further specialization, the algorithm Algorithm1 always works, and we want it to be chosen by default
  • While Algorithm1 is always possible for any distribution, Algorithm2 is only defined for some AbstractValue. In particular, assume that it isn’t meaningful for Value2
  • For a Value1 we want to change the default algorithm to Algorithm2
  • There are different default parameters for Algorithm1 and Algorithm2, which could have different names or values.
    • Assume that the default parameter is N=10 for Algorithm1 and N=5 for Algorithm2
    • It would be nice if Default values were by algorithm-value combination, but can live without it
  • It is preferred if algorithm parameters use keyword arguments, but not strictly necessary
    • We don’t need to worry about there being extra, unused, parameters
  • It would be nice if we didn’t need to force a particular set of parameter names to be shared by Algorithms (i.e. use variable argument keywords)
  • We expect to add in many more AbstractValue types, and a couple more Algorithm types

A Test Suite

using Base.Test
v1 = Value1()
v2 = Value2()

@test f(v1) == f(v1, Algorithm2, N=5) #i.e. defaults to Algorithm 2 with N=5 as the default
@test f(v1, N = 7) == f(v1, Algorithm2, N=7) #Can change the default value
@test f(v1, Algorithm1) == f(v1, Algorithm1, N=10) #can use use Algorithm1 (with the different default)
@test f(v2) == f(v2, Algorithm1, N=10) #i.e. uses algorithm 1 by default
@test f(v2, N = 8) == f(v2, Algorithm1, N=8) #Can change the default value
@test_throws f(v2, Algorithm2) #Not defined! Should throw

I tried to come up with something that would fulfill the test suite, but cannot figure out how to organize the functions, etc. to avoid ambiguity issues. Here was my (not passing the test) attempt

#Forwards based on default algorithm
f(v::AbstractValue, alg::Type{<:AbstractAlgorithm} = Algorithm1; kwargs...) = f(v,alg, kwargs...)
f(v::Value1, alg::Type{<:AbstractAlgorithm} = Algorithm2; kwargs...) = f(v,alg, kwargs...)

#Implementations
f(v::AbstractValue, alg::Type{Algorithm1}; N=10, kwargs...) = (1,N) #i.e. algorithm 1, N=N
f(v::Value1, alg::Type{Algorithm2}; N=5, kwargs...) = (2,N) #i.e. algorithm 2 specialization, N=N

#2

I would recommend that you

  1. pack the options into a type (struct), eg in your example

    struct AlgoOptions
        N::Int
    end
    
  2. have a default_options(value, algorithm) that has a sensible fallback, but can be customized for some algorithm/value pairs,

  3. have also a default_algorithm(value) function, again with sensible default that are customized for certain combinations,

  4. then f(value; algorithm = default_algorithm(value), options = default_options(algorithm, value))


#3

It is just so nice to be able to use keyword arguments for users. Is this not possible?

(Just to verify, the N name is just one of potentially many default parameters that different algorithms could have, and we don’t want to establish common names if not required. I only listed it because it is an example where the name may be identical)


#4

Similar to Tamas Papp, I also recommend encapsulating your algorithm options into a type. As an example, I refer you to

Here, there is a Fatou.Define type that contains the necessary information. Then for each algorithm type, I created a constructor method that creates a new instance of Fatou.Define type, but the constructor keywords default values are used to specify the algorithm defaults.

Yes, it is possible, that’s what I did in Fatou.


#5

I usually pack the keyword arguments into the algorithm types and use QuickTypes:

abstract type AbstractAlgorithm end

@qstruct Algorithm1(;
    n::Int=1,
    special_alg1_option=...) <: AbstractAlgorithm

@qstruct Algorithm2(;
    n::Int=4,
    ...) <: AbstractAlgorithm

#6

One issue is that I would prefer for the users to not have to worry about the underlying algorithm names to change the values (hence why keyword values are easy to use). i.e.

f(v1, N=10)
f(v2, N=8)

Is exactly the interface to shoot for. Changing the algorithm type is much more rare, and I want the interface to be as clear as possible. Is there no way to organize the dynamic dispatching to accomplish this?

Also, it is possible the default values are somewhat of a red-herring, and that it is just the organization of the ambiguity problems that is causing the failures in my attempt.


#7

OK, I think I may have figured out a solution. Leaving aside the questions on whether this is a good API design (i.e., the “pack things in an algorithm structure” approach). This pattern requires an additional layer of indirection because of the need for defaults in on of the (dispatched) parameter types and the (non-dispatched) parameter defaults. If anyone has thoughts on the following, it would be appreciated

using Base.Test
#These come from other libraries...
abstract type AbstractValue end
type Value1 <: AbstractValue end
type Value2 <: AbstractValue end

#These are in our package, and we can define these in whatever way is easiest.
abstract type AbstractAlgorithm end
type Algorithm1 <: AbstractAlgorithm end
type Algorithm2 <: AbstractAlgorithm end

#Forwards based on default algorithm and add in defaults as required
f(v::AbstractValue, alg::Type{<:AbstractAlgorithm} = Algorithm1; kwargs...) = _f(v,alg; kwargs...)
f(v::Value1, alg::Type{<:AbstractAlgorithm} = Algorithm2; kwargs...) = _f(v,alg; kwargs...)

#Concrete implementations require an "implementation" abstraction
_f(v::AbstractValue, alg::Type{Algorithm1}; N=10, kwargs...) = (1,N) #i.e. algorithm 1, N=N
_f(v::Value1, alg::Type{Algorithm2}; N=5, kwargs...) = (2,N) #i.e. algorithm 2 specialization, N=N

Tests (passing) are

v1 = Value1()
v2 = Value2()

@test f(v1) == f(v1, Algorithm2, N=5) #i.e. defaults to Algorithm 2 with N=5 as the default
@test f(v1, N = 7) == f(v1, Algorithm2, N=7) #Can change the default value
@test f(v1, Algorithm1) == f(v1, Algorithm1, N=10) #can use use Algorithm1 (with the different default)
@test f(v2) == f(v2, Algorithm1, N=10) #i.e. uses algorithm 1 by default
@test f(v2, N = 8) == f(v2, Algorithm1, N=8) #Can change the default value
@test_throws MethodError  f(v2, Algorithm2) #Not defined! Should throw