I like Julia's solution to it : Multiple dispatch. It's great for code reuse and generic algorithms, but it kind of need the magic of the Julia compiler to make it shine.
Julia's function polymorphism shines in a lot of cases, but in general it is less powerful than the OOP solution and also I find it much more difficult to read.
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
Or whatever and with the right definition of +, everything would work correctly. In Julia I belive the only way to make this work would be to package the next and hasNext functions (or their Julia equivalents) inside the struct itself, which is unidiomatic I believe.
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.
>Julia's function polymorphism shines in a lot of cases, but in general it is less powerful than the OOP solution and also I find it much more difficult to read.
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.
As a Common Lisp head, I love generic functions / multiple dispatch and would take them even over classes and inheritance as a language feature, but it's definitely cheating when the expression problem is framed in terms of static type systems where your code is guaranteed not to fall over at runtime with a 'no applicable method' error'.
(...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...)
The type system. Also making it a zero cost abstraction as mentioned by the other child comment. Type system and language semantics are critical for that as well, not just the compiler.
I think the main concept here is not the exact syntatic construct used, but the idea of removing the behaviour from the data structure, so implementors of new structures are not bound contractually to implement every behaviour.
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)
The misnamed Visitor pattern does exactly this: decouple the operations on a polymorphic object structure from the implementation of the structure. It can be used in a way similar to FP-style pattern matching (although with more boilerplate), but is more flexible because the implementations accepting a Visitor are not coupled to the constructors of a data structure (e.g., a DAG object could accept a tree visitor, or vise versa). It would be interesting to have a language that provides convenient syntactic sugar for the visitor pattern.
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).
So, put's on low level hardware architect's hat, the low level method dispatch paradigm used for polymorphism is a really bad thing.
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.
Your comment was really interesting to read. Do you think you can unpack it a little more for someone like me who sits on top of a much higher level of abstraction?
I'm not sure how much deeper I can go ... in essence an x86 instruction like "jsr *N(r)" is really 4 micro ops: "ld tmp, N(r); st pc, (sp); sub sp, sp, 4; jmp (tmp)" - in RISC-V its more like "ld tmp, N(r); jalr (tmp)" - we can ignore the "st pc, (sp); sub sp, sp, 4" for the moment because they don't slow you from executing that first piece of code in the method you're calling, and it kind of lets us compare apples with apples.
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
> Branching scales well when we want to extend the program by adding functions but it doesn’t scale well when we want to add types.
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 :).
> 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.
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.
> The "problem" in each case is that you have to modify code in a bunch of different places instead of one place.
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.)
Strictly speaking, nothing says a reducer even _has_ to have a switch statement. A reducer can use _any_ conditional logic it wants inside: `if`, `for`, `while`, lookup tables, etc.
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!
This seems very close to a point an engineer made to me on a game. A case / switch statement was considered very ugly in optimized game code. But in terms of performance a polymorphic function was pretty much the same, it just looked cleaner.
Games also have the particular need of being rather database-like in their usage patterns(lots of filtered set iterations), which makes it harder to apply OOP as a whole. OOP likes interfaces, but games are often dealing with aggregates. My observation's that pushing the indirection down to the callsite has the effect of making it easier to view what's happening in terms of concurrency.
It's a good point, because you remind us that domain matter so much. Outside of gaming and some other places, I don't think people would, for one second, care about the relative performance in this scenario.
And people care less in gaming every day. The part of the code that needs to be performant is often in an engine and thus untouched. And optimizing assets is often more important than optimizing code.
Programming is about writing code that's understandable for humans - otherwise we'd just edit the binaries with a hex editor. A polymorphic function may well compile to the exact same binary as a switch, but it puts the responsibilities in the right place and makes future maintenance much easier.
> However, generally, branching offers the compiler more flexibility to optimize because all the jump targets are known in advance. In case of virtual dispatch, a static compiler may not know all the jump targets at the time of compilation so generally such code is harder to optimize.
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.
Only in cases where the compiler knows there is a "closed world" - which are precisely the cases where the compiler can optimize a virtual function call. If it's an "open" situation where there might be other, unknown cases, the compiler will silently accept it.
The same applies to abstract class / trait with a default implementation. The compiler would also silently accept if after adding a new behavior you forget to update the implementations which need a customized version of that behavior.
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.
> The same applies to abstract class / trait with a default implementation.
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.
But then you should compare a trait with no default method to a switch with no default case. And a switch with no default case would be reported as an error if some cases are not covered.
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 Scala or OCaml you get a compile-time warning + runtime error. In Java 14, Kotlin and Rust there is a compile-time error if switch/match expression is non-exhaustive.
The openness of match/switch over a sealed hierarchy is in another dimension - you can add more switches without changing old code. This is something that interfaces don't provide.
It's telling that sum types make a lot of code cleanliness issues disappear to the point we're reevaluating architectural vs performance considerations.
Even in Java, you can always use a switch based on enums or even int constants. The only thing missing would be exhaustiveness checking, but the other claims about extensibility or readability made in the article still hold.
