In Defense of a Switch
pkolaczk.github.io
pkolaczk.github.io
JuliaCon 2019 | The Unreasonable Effectiveness of Multiple Dispatch | Stefan Karpinski https://www.youtube.com/watch?v=kc9HwsxE1OY
For example, I recently ran into this problem when prototyping a new Julia library. Without going too into the specifics, I can only match on a type of a object. With Scala say, I can override the method of an object at creation without actually defining a class.
In order to do a similar thing with Julia, I have to package the function as a field of the struct, I can't do multiple dispatch on it.
In general I think multiple dispatch is great for the incremental adding of new functionality without modifying the original source but bad at dynamically augmenting functionality at runtime.
A common example in Scala is creating an iterator. I can override the next and hasNext methods at object creation instead of creating a whole new class with a name. With Julia I would have to define a new kind of iterator at the top-level and then implement the necessary functions.
Let's say I want to have an iterator type of numbers in which I want to multiply or add constants to. In Scala I can easily return a new iterator that wraps the old one with overridden methods that adds or multiples by the constant. I could write
val newIter = 2 + iter
Also the amount of type-piracy can get a little annoying. A lot of libraries end up defining alternative dispatches that are inappropriate.
For Julia's problem domain, I do think this approach makes more sense than OOP and leads to saner scientific code. A lot of Python scientific computing libraries have these crazy baroque mutation heavy brain dead OOP interfaces that serve no purpose. It's just that in some cases, the packaging of data and functions together is really the only way to sanely solve a given problem.
Given that OOP is single dispatch and multiple dispatch is a strict generalization, that's not just wrong or an opinion but it's a statement that can't be true. a.b(x) is equivalent to b(a,x) where b is a (possibly callbale struct) function you allow dispatching on a but not x. Multiple dispatch is the case where you can, well, dispatch on both.
>Without going too into the specifics, I can only match on a type of a object. With Scala say, I can override the method of an object at creation without actually defining a class.
You could also just drop to Val to dispatch on values or even define calls from the parameters like GeneralizedGenerated. That's pretty much the behavior you're trying to recreate so that would just do it directly. It's not the most common thing to do since you will hit dynamic dispatch, but of course if you're trying to dynamically add or change functions that's bound to happen.
>Also the amount of type-piracy can get a little annoying. A lot of libraries end up defining alternative dispatches that are inappropriate.
Interesting. Can you please make a list?
(...although I could have gotten a lot of useful work done with my dirty dynamic types and shameful runtime errors in all the years people searched for a solution to the expression problem...)
In a way, the concept of monads attempts to solve this, since each specific data type would only need to implement its respective map/bind method, to be able to work for any other specific operation, since bind can be used to perform both transformation as well as reduction depending on the operation you give it.
(to purists, forgive my nomenclature, I am not a mathematician or fluent in FP lingo)
EDIT: Just to clarify: The visitor pattern is usually presented in the context of "visiting" nodes in a recursive traversal. But the pattern is actually independent from the "traversal" use case. Its essence is really just the "switching", or case distinction, over an algebraic sum-like type (or over a type that provides a sum type view of itself).
Something like "jsr *N(r)" which in RISC terms is "ld tmp, N(r);jalr (tmp)" is a real pipe-breaker - the load finishes near the end of the pipe while the jump has to be predicted at the beginning, but it can't be resolved until close to the end - this means that a mis-predicted branch (and indirect branches are harder and more expensive to predict) means that many many more instructions need to be discarded (could be 100+ on a high-end CPU).
Tests and branches suffer from mispredictions too, but they often can be resolved earlier in the pipe, discarding fewer instructions, and of course are more open to compiler optimisation.
So you need a memory fetch followed by an indirect jump, the results from the memory fetch come at the very end of the cpu's pipelines, if the CPU is simple it wont fetch the next instruction until it knows the value of tmp.
However any modern high end CPU is going to guess ('predict') the destination of the jump and start executing code from that predicted destination, if it guesses wrongly those instructions and their results will have to be discarded (a "pipe-flush"). There tend to be two sorts of predictors - for conditional branches and for indirect branches, the conditional ones tend to have a better hit rate, the indirect ones (this case) always fail on the first attempt and tend to be broken by things like a random mix of function pointers in vtables (to be fair the same can probably be said for using conditional branches in a similar situation)
In RISC-V the compiler can still schedule the "ld tmp, N(r)" earlier in the instruction stream, not so the x86. However if you use a conditional branch (an if statement rather than an indirect call) you can move those instructions earlier into the instruction stream and tolerate load delays and branches can be resolved earlier in the pipe (meaning a pipe flush flushes fewer instructions).
Modern speculative CPUs are very dynamic things, a lot of it designed to ameliorate those load delays, sometimes they are a couple of clocks (from an L1 cache) other times they are 100s (from dram) by finding other stuff to do in the mean time. That means that real-world performance measurement can be a bit mushy because there's so much going on at once
In languages such as OCaml, when you add a constructor to an algebraic data type (which is the equivalent of adding a type here), the compiler will guide you towards the completeness of all the functions in your codebase that match over your type. So this burden is not on the programmer.
> Polymorphism scales well when we want to extend the program by adding types, but it doesn’t scale well when we want to add functions over these types.
In the same manner, you can add an abstract method to your base type to have the compiler force you to implement it in every types that you have defined and that extend it.
So I guess these are not real problems.
The author's two other conclusions are valid however. And I'll add that I believe good software engineering structure programs around data structures rather than functions. So I completely agree with them: long live the switch :).
Tools help with abstract methods and exhaustive enum checks, but it's the difference between a change in one place vs changes in many places.
And by extension, different places include ones you don't own, and therefore can't change. For example, say you have an interface in your library that consumers of that library implement. If you want to add an operation to that interface, all consumers of your library, ones you don't even know about, have to support that operation.
But, if you want to add a new interface, consumers only have to implement that interface if they want to use functionality based around that new interface.
(And of course, the same applies in the opposite direction if you're using an operation-first approach.)
That only works if all the functions you care about are in one codebase. If not, then the changes the article talks about become backwards incompatible changes in your library.
> So I guess these are not real problems.
If you're designing a library, the approach you take determines what types of additions are breaking changes and which are not.
It's just that the most obvious conditional construct for "checking multiple possible values of a single field" is a `switch` statement [0].
Having said that, we now officially teach our new Redux Toolkit package as the default way to write Redux code [1], and its `createSlice` API [2] does actually use a lookup table approach instead.
On a related note: my next task is rewriting that existing Redux "Basics/Advanced" tutorial to modernize it, and I'm currently taking notes on what I do and don't like about it [3]. If you've got any relevant feedback on things you don't like or ways to improve that tutorial sequence, please feel free to comment and let me know!
[0] https://blog.isquaredsoftware.com/2017/05/idiomatic-redux-ta...
[1] https://redux.js.org/tutorials/essentials/part-1-overview-co...
But those are precisely the cases where the behaviour of a switch may be wrong (for example, if a different module adds another implementation of the interface that you don't know about). I'll take slow correct code over fast incorrect code any day.
Also in the case described in the post, somehow the compiler didn't optimize the polymorphic case despite being able to see all implementations. I guess separate compilation of units makes the closed-world appear like an open-world to the compiler.
If you deliberately choose to give a default implementation, yes. But you have the option of not giving a default implementation, forcing a compilation error if someone adds a new case and doesn't implement that behaviour. There's no way to achieve the same thing with a switch; if the switch is "closed" then in some languages a missing case is a warning or error, but I've never seen a language where an "open" switch won't be silently accepted and fail at runtime.
Also a switch with no default case is still open to extension. But the extensibility happens in a different dimension, as described in the article - the analogue of adding more implementations of an interface is adding more switches, not adding more case clauses. That's why a switch is not a replacement for interfaces.
In what language? It's not an error in Scala, which is what the post is talking about.
Not if you're on a recent version of Java, switch expressions are exhaustive and they're a stable (non-preview) feature now as of Java 14.
Sum types rock.