Multiple dispatch on function types

I’m designing a small module to compute fractals. I have implemented 2 algorithms: escape time and distance estimation. These algorithms have the exact same arguments except that distance estimation needs 1 more.

On the main code, I have the generic compute function and I’m leveraging multiple dispatch on the arguments to use different variations for Fatou and Mandelbrot sets, and now wanted to implement the same for the 2 classes of algorithms.

function compute(s::FatouSet, canvas::Canvas, algorithm::typeof(escape_time))::Array{Float64}
    c, f, _, max_iter, radius = s
    construct_mesh(canvas) .|> x -> algorithm(z -> f(z, c), x, max_iter, radius)

function compute(s::FatouSet, canvas::Canvas, algorithm::typeof(distance_estimation))::Array{Float64}
    c, f, df, max_iter, radius = s
    construct_mesh(canvas) .|> x -> algorithm(z -> f(z, c), df, x, max_iter, radius)

I read on the docs that functions have a singleton type, and was hoping to use that to differentiate the 2 implementations.

The different implementations are only needed because of that extra argument that makes them different, so maybe a better way exists.

Edit: added implementation details.

1 Like

An alternative is to wrap the algorithm in a type, i.e., define structs EscapeTime, DistanceEstimation etc., and dispatch on these – that setup is used in many libraries, e.g., DifferentialEquations or Optim.
Depending on what you mean with “extra arguments” you could also get away with passing a callable, and supplying the extra arguments via partial application, i.e., escape_time(extra_arg) = x -> do_its_thing_with(extra_arg, x) and just pass escape_time(0.1) which returns a function to compute.

What’s different between the two implementations of compute? If it’s just that you pass in a different algorithm, can’t you just write

function compute(s::FatouSet, canvas::Canvas, algorithm::Function)


Maybe you can provide info about the implementation of compute?

1 Like

Check the original post, I updated it with the implementation. Basically, distance estimation algorithm uses the derivative of the function to compute the distance.

I planned to improve the design in the future, but it seemed like a good way to use multidispatch to “quickly” handle these particular cases for each algorithm.

What’s wrong with DNF’s suggestion? Perhaps we don’t understand what your problem is?

If you’re afraid that the method won’t get specialized, just add a type parameter (where {F<:Function})

1 Like

OK I’ll try to explain why I don’t use Function: imagine I did.

Then, I have no information about the signature of the algorithm, and some algorithms need more arguments than others.

When calling the algorithm function inside the compute function, I don’t know what arguments to pass to it. Particularly, I don’t know if I have to pass the derivative of f, which I call df (f being the holomorphic function that will be iterated) or not to the algorithm function.

One of them (escape_time) needs to be called like escape_time(f, z, etc...) while the other needs to be called like distance_estimation(f, df, z, etc...).

In a way, I want to distinguish between any generic function and the type of functions that are suitable for computing these fractals (lest the user pass just any function and the code fails).
Maybe the thing I want is an interface??

1 Like

I’m not sure if I understood correctly all the limitations you are moving in, but if the two different algorithms intervene as a function of the presence or absence of the df parameter, you could use this to dispatch to the different methods.
Either using an extended set of parameters including common ones and df or using df as an additional parameter.

function compute(s::FatouSet, canvas::Canvas)::Array{Float64}
    c, f, max_iter, radius = s
    construct_mesh(canvas) .|> x -> algorithm(z -> f(z, c), x, max_iter, radius)

function compute(s::FatouSetExtnd, canvas::Canvas)::Array{Float64}
    c, f, df, max_iter, radius = s
    construct_mesh(canvas) .|> x -> algorithm(z -> f(z, c), df, x, max_iter, radius)

function compute(s::FatouSet,df, canvas::Canvas)::Array{Float64}
    c, f, _, max_iter, radius = s
    construct_mesh(canvas) .|> x -> algorithm(z -> f(z, c), df, x, max_iter, radius)
1 Like

Well, if you want control over your algorithm types, just make them types – maybe using that these can be function-like as well. Your compute function could then be compute(f::AbstractFractal, c::Canvas, a::AbstractAlgorithm) with appropriate methods for specific combinations of concrete Fractal and Algorithm types (subtyping AbstractFractal and AbstractAlgorithm respectively).
In case of your example code, which simply unpacks the FatouSet (probably something like a tuple) and passes it to the algorithm, I would simply pass the algorithm as a function receiving x and s and have the algorithm unpack the parts it needs itself, i.e.,

compute(s, c::Canvas, a) = construct_mesh(c) .  |> x -> a(x, s)
1 Like

OK, something like this, then:

helper1(c, f) = Fix2(f, c)

helper0(alg::typeof(distance_estimation), c, f, df, max_iter, radius, x) =
  alg(helper1(c, f), df, x, max_iter, radius)

helper0(alg::typeof(escape_time), c, f, df, max_iter, radius, x) =
  alg(helper1(c, f), x, max_iter, radius)

helper0(alg::F, c, f, df, max_iter, radius) where {F<:Function} =
  let a = alg, c = c, f = f, df = df, mi = max_iter, r = radius
    x -> helper0(a, c, f, df, mi, r, x)

function compute(s::FatouSet, canvas::Canvas, algorithm::F) where {F<:Function}
    c, f, df, max_iter, radius = s
    construct_mesh(canvas) .|> helper0(algorithm, c, f, df, max_iter, radius)

Unfortunately, this is not conveyed by the function type either. A function type does not tell you what parameter types it will accept, and a single function can have multiple different methods, that have different signatures.

Unless you are using your human knowledge that ‘this function takes these arguments’.

1 Like

Looking at your updated code, maybe algorithm should simply accept a FatouSet object?

1 Like

Let me reformulate the question, in a more generic way. When you type hint in Python you can make something like Callable[[T1,T2,...,TN], T_out] to indicate the types of the arguments of the function and the output. In Haskell, functions can have types such as e.g. map, with type (a -> b) -> [a] -> [b], which means an argument of type a -> b (a function that has input type a and output type b), an argument of type [a] (list of as) and output type [b].

Julia seems to only provide a generic Function, or am I missing some language feature that lets you do this kind of typing? In a strongly typed language with functional paradigm and higher order functions, I would expect to have access to that.

Julia provides a unique type for each function, foo, and that type is typeof(foo), which is a subtype of Function. Due to multiple dispatch, each function can accept many different input signatures, so the in/output signatures cannot be part of the function type. A signature would have to be to attached to methods instead.

1 Like

But I can’t dispatch on typeof(foo). And from the POV of the function that receives an argument function, it doesn’t matter which function or method is being passed, only that the number of arguments and in/out types match.

Well, yes, you can. But you probably meant something else?

I’m not 100% sure I understand your goal. But in my earlier post I was thinking about a design like this

function compute(s::FatouSet, canvas::Canvas, algorithm::F) where {F}
    construct_mesh(canvas) .|> x -> algorithm(s, x)

and then provide different algorithm functions where some use df and some don’t.

Just in case it’s still not clear, in Julia functions are basically sets of arbitrary methods, so the methods are the ones with type signatures. For example, Base.sqrt is a function, and these are its methods:

julia> methods(sqrt)
# 19 methods for generic function "sqrt" from Base:
  [1] sqrt(::Missing)
     @ Base.Math math.jl:1580
  [2] sqrt(x::BigFloat)
     @ Base.MPFR mpfr.jl:695
  [3] sqrt(a::ComplexF16)
     @ Base.Math math.jl:1559
  [4] sqrt(x::BigInt)
     @ Base.MPFR mpfr.jl:703
  [5] sqrt(a::Float16)
     @ Base.Math math.jl:1558
  [6] sqrt(x::Union{Float32, Float64})
     @ Base.Math math.jl:685
  [7] sqrt(x::Real)
     @ Base.Math math.jl:1575
  [8] sqrt(A::LinearAlgebra.UnitUpperTriangular{T, S} where S<:AbstractMatrix{T}) where T
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/triangular.jl:2173
  [9] sqrt(J::LinearAlgebra.UniformScaling)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/uniformscaling.jl:173
 [10] sqrt(z::Complex)
     @ complex.jl:527
 [11] sqrt(A::LinearAlgebra.Adjoint{T, <:AbstractMatrix} where T)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/dense.jl:907
 [12] sqrt(D::LinearAlgebra.Diagonal)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/diagonal.jl:723
 [13] sqrt(A::LinearAlgebra.Hermitian{T, S} where S<:(AbstractMatrix{<:T}); rtol) where T<:Complex
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/symmetric.jl:796
 [14] sqrt(A::LinearAlgebra.LowerTriangular)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/triangular.jl:2191
 [15] sqrt(A::LinearAlgebra.Transpose{T, <:AbstractMatrix} where T)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/dense.jl:908
 [16] sqrt(A::LinearAlgebra.UnitLowerTriangular)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/triangular.jl:2192
 [17] sqrt(A::LinearAlgebra.UpperTriangular)
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/triangular.jl:2172
 [18] sqrt(A::Union{LinearAlgebra.Hermitian{T, S}, LinearAlgebra.Symmetric{T, S}} where S; rtol) where T<:Real
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/symmetric.jl:785
 [19] sqrt(A::AbstractMatrix{T}) where T<:Union{Real, Complex}
     @ LinearAlgebra ~/tmp/jl/jl/julia/usr/share/julia/stdlib/v1.11/LinearAlgebra/src/dense.jl:877

If you want to dispatch on a type signature, you need to do that separately from dispatching on a function, since the concepts are independent.

Yeah I think I understand it better now. I somehow wanted to have Haskell pattern matching in Julia, but to each language their own, Haskell has that, Julia has other idioms and ways to achieve my implementation goals.