The Unreasonable Efficiency and Effectiveness of Multiple Dispatch: Your Favourite Examples

General Usage
,
1

@Datseris asked if there’s a formally citable reference with the points, examples and concepts presented by @StefanKarpinski on The Unreasonable Effectiveness of Multiple Dispatch.

In the slack discussion linked above, they suggested a 3 page write-up with appropriate citations. Stefan responded that this write-up should have empirical evidence in contrast with the anecdotal evidence he presented in his talk.

This thread may or may not be useful for the composition of such a write-up, but I thought it useful to open it as a community-curated list of examples where multiple dispatch has been leveraged to great efficiency and effectiveness. I would imagine this thread could be a useful link for people curious about why we rave on about multiple dispatch.

Some ideas on what might be informative and enlightening to share:

  • Package interoperability examples.
  • Your specific experiences at work.
  • Links to other resources on the same topic (maybe with your TL; DR), including other threads in this Discourse on the same topic.

Note that this thread is not motivated on asking “how” multiple dispatch works, but demonstrations on what it has been used for, and how it has benefited you/us. The hope is that this thread will contribute to a nice, referenceable publication specifically on multiple dispatch.

Without further ado, what are your favourite examples of multiple dispatch?

Edit 1: There are many arguments re composability and comparisons between languages. To help with the scope of this thread, keep it positive to examples where Julia’s multiple dispatch design did help. We can worry about the arguments later, or in another post (see my first response in this thread).

Edit 2: That said, @Datseris has an awesome example of composability he wrote up, and links to below.

8 Likes
2

This thread’s scope largely overlaps with this one :sweat_smile:, but doesn’t necessarily point to actionable output, and doesn’t purpose to many examples.

Examples shared there:

And some caveats on preaching multiple dispatch:

1 Like
3

My favorite is printing, but a more specific example is how easy it is to provide rich displays in notebooks like Pluto.jl, IJulia.jl, and QuartoNotebookRunner.jl simply by defining show(::IO, ::MIME, ::T). The utility is demonstrated very well in this Latexify.jl tutorial.

1 Like
4

This is my favorite classic: DifferentialEquations.jl and Measurements.jl

8 Likes
5

ForwardDiff.jl and nearly every other package that accepts generic Real numbers

10 Likes
6

I don’t agree with this statement, in the sense that I don’t agree that the evidence is purely anecdotal. As I mentioned in the slack discussion, the majority of the cited YouTube talk is factual.

I created a short self-contained example to showcase Julia’s composability. It composes reals, duals, symbolics, diffeq, monte-carlo measurements, matrices, and trigonometrics. I created this based on other people’s work (Stefan’s talk, Kristoffer and Fredrerik’s presentation, Frames’ blogpost, and other resources). It is the first section of this notebook:

I am very happy with this example, because it is purely factual, and very much up to date, and even includes symbolic stuff which is currently cutting edge in Julia.

As I discussed at the end of the first section of that notebook, this absolutely crazy composability example is simply, and factually, impossible in Python, because there is no single sin function. There is numpy.sin, sympy.sin, etc. etc… Any Python developer would have to write glue code to create in Python what is possible in Julia out-of-the-box.

Let me also say, anecdotally ( :wink: ) that one day I saw my wife’s code (Python user) and my eye glanced over a statement import jax.numpy, which made me start laughing because I realized that JAX had to re-implement (at least partially) numpy, which is arguably Python’s largest library.

11 Likes
7

This one, including their plot recipes also working together (which is something I haven’t seen in any other language) is also in the Plots.jl paper

3 Likes
8

Multiple dispatch is really nice when converting values between types, e.g. Serialization/Deserialization. Recently I wrote a function conform(::Type{T}, data)::T where T that attempts to convert some less-structured data into a more structured format. The basic use case is that I create 1,000 structs of a type like ExperimentConfig, serialize those into e.g. JSON, and have a cluster of workers go through the files, deserialize back into an ExperimentConfig, and run the experiments. (Except there are dozens of ExperimentConfig types, so writing separate serde for all of them would be brutal.)

The core logic is the same for most user-defined structs. For each field of the struct, check a dict for a key that has the same name, and attempt to conform it to the type the struct expects:

function default_struct_conform(::Type{T}, d::AbstractDict)::T where T
    struct_inputs = [conform(field_type, d[field_name]) for (field_type, field_name) in zip(fieldtypes(T), fieldnames(T))]
    return T(struct_inputs...)
end

conform(::Type{T}, x::T) where T  = x

but there are loads of special cases – String and Nothing are struct types, but we want to treat them as plain values. Our codebase has a concept of a “time range”, which we convert from a string like “2023-01 - 2023-06” – that requires a separate conform(::Type{TimeRange}, s::String). And so on.

Multiple dispatch works really well here, because the conform methods really care about the types of both arguments. It also lets us place the specific implementations next to the types as they’re defined, while separating the core serialization/deserialization logic as its own module.

2 Likes
9

As an example of non-multiple dispatch falling short – There is a python package called S3Paths. It tries to emulate the Path class in base Python for S3. However, it does not compose with Pandas because Pandas does not interact with Path objects using the correct methods. There is an open issue on the S3Paths repo lamenting the situation because “there is nothing to be done.” But that’s only because there is no way for them to define new behaviors for pd.read_csv(path).

If this were Julia and another library wasn’t using the correct public methods, you could just define a new dispatch for read_csv(p::S3Path, ::DataFrame).

8 Likes
10

Reducing 6 different BLAS functions to one (julia/stdlib/LinearAlgebra/src/blas.jl at master · JuliaLang/julia · GitHub)

for (fname, elty, cty, sty, lib) in ((:drot_, :Float64, :Float64, :Float64, libblastrampoline),
                                     (:srot_, :Float32, :Float32, :Float32, libblastrampoline),
                                     (:zdrot_, :ComplexF64, :Float64, :Float64, libblastrampoline),
                                     (:csrot_, :ComplexF32, :Float32, :Float32, libblastrampoline),
                                     (:zrot_, :ComplexF64, :Float64, :ComplexF64, libblastrampoline),
                                     (:crot_, :ComplexF32, :Float32, :ComplexF32, libblastrampoline))
    @eval begin
        # SUBROUTINE DROT(N,DX,INCX,DY,INCY,C,S)
        function rot!(n::Integer, DX::Union{Ptr{$elty},AbstractArray{$elty}}, incx::Integer, DY::Union{Ptr{$elty},AbstractArray{$elty}}, incy::Integer, C::$cty, S::$sty)

and multiply that across the whole BLAS library.

10 Likes
11

I know this thread is asking for examples, but an earlier post of mine about composability not being novel was represented as a caveat of preaching multiple dispatch. I disagree, doing familiar things easily is actually a very good reason for preaching features, like garbage collection for managing memory. A couple general aspects I like:

  1. Julia can’t have a discrepancy between a compile-time expression’s inferred concrete type and runtime instance’s type, so there’s no syntactic division between static dispatch and dynamic dispatch. If we optimize a dynamic dispatch to a static one, it’s only a matter of improving type inference in the actual algorithm, not a reformatting exercise.
  2. When flexible dynamic dispatch is only available as single dispatch, people can resort to making many composite types just to merge the multiple arguments that they can’t dispatch over. Obviously discouraged, but deadlines don’t wait for refactoring.

Julia’s multiple dispatch alone doesn’t explain the way it accomplishes composability, but reducing mental load sure doesn’t hurt.

3 Likes
12

Does this require multiple dispatch? Or single-dispatch and duck-typing?

2 Likes
13

@jishnub I guess it would work hand-in-hand with Julia’s type system. Maybe we should expand this topic’s scope as such, because Julia’s composability is also due to its type system. No inheritance per-se has really shown its colours in the Julia ecosystem, and I personally much prefer its trade-offs than languages with inheritance OOP.

@Benny Thanks so much for the clarification. Sorry for the misinterpretation and that you had to make this clarification. I’ll edit my above post accordingly.

I’ll admit that an ulterior motive I had in making this thread is also to take multiple people’s examples and opinions to help me form an opinion for myself more thorough than my currently partial and inexperienced opinion, especially in comparison with other languages.

And yes, examples were requested, but discussion and context for those examples I think are still very valuable. Especially clarifications. :smiling_face:

14

Good point, I guess you can do most of it with single dispatch. I tried to think of some things that require multiple dispatch, and the best example I could come up with is multiplication. The following three methods have very different implementations:

  • *(::Real, ::Real)
  • *(::Dual, ::Real)
  • *(::Dual, ::Dual)

Although to be fair maybe promotion gets us most of the way there

1 Like
15

Does this require multiple dispatch? Or single-dispatch and duck-typing?

I think this does require multiple dispatch to avoid needing coordination between library authors.

Multiple dispatch encourages you to have one read_csv(filename, output_type) method that can be extended by many libraries, and that pattern lets you solve this without explicit coordination by library authors.

Python has functions (that don’t really dispatch) and classes (which allow single dispatch.) If the Pandas maintainers put read_csv in a class, they would probably have put it under the DataFrame class. And then you’d still have this problem: the S3Paths maintainers would not be able to extend DataFrame.read_csv to have different behavior on their types.

If Python were to try to do it the other way around, e.g. have a Path.read_dataframe_from_csv() method, then Pathlib would need to depend on Pandas, which is also infeasible.

7 Likes
16

I think this does require multiple dispatch to avoid needing coordination between library authors.

Also, I think this might be a general strength of multiple dispatch that gets overlooked. If you have complete control over a codebase, you might not need it, but as soon as you start dealing with packages you can’t/don’t want to modify it becomes a lot more useful.

A similar example is extension methods in OO languages like Kotlin, that let you attach a method to an existing class. I find these hugely useful (because e.g. you can make sure all the types you use have a .to_json() method), but they’re also completely unnecessary if you control all the code and only need to modify your own classes.

4 Likes
17
11 Likes
18

That’s a good example of composability becoming feasible when multiple arguments need to be extended, but single dispatch can do that for single arguments between disparate libraries. Numpy’s NEP-18 comes to mind, but it’s readily apparent that it’s a lot of work to get around the class organization.

NEP-18 is a much more elaborate example, but there are patterns for linking the disparate syntax of unimethod functions and single dispatch of member methods over classes. The simplest one:

def foo(x): return x._foo() # forward to methods in classes
# instead of implementing one type-checking branch like:
# if isinstance(x, A): return 0
# elif isinstance(x, B): return "zero"

class A:
  def _foo(self): return 0

class B:
  def _foo(self): return "zero"

foo(A()), foo(B()) # same call as if foo implemented it

It’s not a syntactic division between static and dynamic dispatch that I mentioned earlier (CPython doesn’t do static dispatch on its own), but it’s clear that people don’t like to rewrite function calls just to involve any dispatch/duck-typing at all. I guess Julia’s function calls are always dispatched, but it looks the same whether there’s only 1 method or it’s done statically.

1 Like
19

This. Now you’ve said it it’s so obvious :slight_smile:.
And @mrufsvold example is quite good too.
As a matter of fact, now I remember I had to add a new method to the AWSS3.jl package, so that it can easily handle a custom type (forgot the details, it was in a private package at my former company, a few years ago) to send / retrieve specific objects from a MinIO server. Actually it was so simple I never gave a second though about it.

7 Likes
20

Pardon my uncultivated understanding of programming language terms.

Isn’t multiple-dispatch kinda like overloading on steroids?

The issue with heavily “overloaded” code is that they are hard to understand because it’s sometimes difficult to know where a piece of code is defined.

In Julia, a function’s definition could be set in multiple locations depending on which method is dispatched. This makes it hard to understand the code or it could give you the false sense that you understood it but the implementation could literally be unchanged from under your feet but defining a method with a more restrictive type signature.

@which is handy but it requires you to know the inputs before you know exactly which method is called.

Isn’t that an issue with dynamic multiple dispatch, i.e. multiple dispatch that doesn’t require you to have specified the input types exhaustively.

2 Likes