The Unreasonable Effectiveness of Multiple Dispatch | Stefan Karpinski | JuliaCon 2019
ฝัง
- เผยแพร่เมื่อ 29 ธ.ค. 2024
- If you're familiar with Julia and its ecosystem, you may have noticed something lovely but a bit puzzling: there seems to be an unusually large amount of code reuse between packages compared to other seemingly similar languages. This sharing of code comes in two forms:
1. Sharing basic types among a wide variety of packages providing disparate functionality;
2. Sharing generic algorithms that work on various implementations of common abstractions.
Why does generic code in Julia "just work"? Why do Julia packages seem to share types with so little friction? Both kinds of reuse are supposed to be natural benefits of class-based object-oriented languages. After all, inheritance and encapsulation are two of the four pillars of OOP. Even more puzzling is that Julia has no encapsulation and doesn't allow inheriting from concrete types at all. Yet both kinds of code reuse are rampant. What is going on? In this talk, I make the case that both of kinds sharing stem directly from Julia's multiple dispatch programming paradigm.
![[10x24] What does "Multiple Dispatch" mean in Julia?](http://i.ytimg.com/vi/hesjQz__yb8/mqdefault.jpg)
![[10x24] What does "Multiple Dispatch" mean in Julia?](/img/tr.png)
I lost count of how many time I watch this videos. It just gets better the more I dig into Julia
video starts at 1:05
Hùng Nguyễn actually more like at 2:20
I had no idea what multiple dispatch was and its just a mere 35 minutes and now I know. Brilliant.
Good job. In addition, you could have compared the complete version of the c++ code (which have the same dynamic behavior using virtual methods). This would have been even more highlighted the simplicity of Julia.
I think one problem with multipledispatch comparing to a trait system is that the developer needs to know and fully understand the detail of a function in order to let that function use some optimized operation for calculation. E.g. in the "inner" example, one needs to read the code of the function "inner" then can he know the function "inner" uses "*" (multiplication). After that, he can write a specialized "*" for the "OneHotVector". This may be obvious for "inner" but sooner it becomes not obvious for other complicated functions.
Eh. If it needs a function that hasn't been implemented yet on the input types you generally just get an exception when you try to run it for the first time. So it's rarely an issue in practice.
@@BosonCollider and with the strong static analysis that's possible in Julia, but not yet there as demonstrated by JET.jl, it doesn't even need to be at runtime. There's already enough information at "compile-time" to check if a function has been implemented on an input type, but it's just not tapped into yet. If only it had the same resources Python has been given with tooling...
@@BosonColliderBut he is not really talking about a missing function for the code to run, but a fallback function that may be poorly optimised?
There's serious complexity with implementing multiple dispatch and it increases the overhead of function calls. Already function inlining is huge for performance, but if every function has to be looked up dynamically that may take serious overhead. Either something like JIT or language runtime needs to be exist or it needs to be opt in like C++ virtual. MD is absurdly useful for sure, but it's not trivial to implement or fit into exisiting languages.
Implementing it in Julia has been one of the core focus points of early Julia development, and yes, implementing it retroactively into a language is a no-go.
Which is exactly the reason, why Julia has a legitimate reason to exist.
This video does have a lot of incredibly interesting moments. Like in 7:15. Dog and Cat are both pets but they have to have "name" declared explicitly. What if I have 28 types of pets, would I have to declare all structs with names (and ages, for example) to them?
Also, "meets" shows how we can have "a" and "b" being Dog, Cat or Cat, Dog respectively. That's a cool feature, but what if both methods returned "fights". Is there a way to write it so that I only need 1 Dog and 1 Cat (in any position), or do I really need to duplicate this specific line of code?
@Stefan Karpinski As a C++ developer and Julia enthusiast, I'm also disturbed by the encounter() function using the undefined Pet::name I guess this is something very difficult for somebody discovering the code of someone else.
@@quentinquadrat9389 If you go to the Julia Discourse, people will be very willing to help you with the transition. In your particular case, it seems simples. the two struct lines up there are usually made in multiple lines. in the second "line", there's a name for dog and a name for cat. So those fields would exist and be accessible during meets. Since Pet is abstract, there's no problem with "name" not existing there (since you can't create a concrete Pet object), but 'encounter' does make it mandatory for all Pets (all derived concrete structs) to have a 'name' field.
@@Dan1loBC I know for Discourse they helped me on other topics :) Julia is a little disturbing for this point. Your reasoning is exactly what I said "difficult for somebody discovering the code of someone else" because for each field he has to redo your reasoning "in which concrete class .name is defined ?". C++ is more code-reading friendly because Pet::name shall exist, but of course C++ is less flexible (i.e. dynamic_cast). I'm not found of duplicating lines of code (name::String) I know that Julia prefers the composition which is a named way for inheritance, but these names makes the code more "noisy" a.b.c.d.name. I guess on a bigger example they would give more refinement by adding a function such as name(p::Pet) which gives more flexibility and allows throwing if a Pet has no name (for example).
Not trying to be a wet blanket, but wouldn't it be more apt to say that the expressive power is polynomial rather than exponential? Which is still good, just sayin
2:10
Type classes also solve this problem, but statically (and optionally dynamically, with existential types). How do the solutions compare?
Looks fascinating and I'm curious look back at my code and see if there are places where I could have really used multiple dispatch, or if I would have written my code differently if I'd had multiple dispatch which I think is the more important question.
Having said that, I do think that as far as the common types single dispatch goes for what you call CBOO, you give only two solutions. I'd be curious what you think about the third solution implemented by languages like Ruby that allow packages to modify and add methods to already closed classes. It trades off one namespace problem for another, as you mentioned, in Ruby you have to be careful with naming menu when you insert methods in a previously defined class. It has the benefits of using the same namespace, with the obvious trade off of possibly having collisions.
Just to mention that in c++ you can make the encouter function a template function and it solves the problem for any type you'll give (even future type like Lion or even Sloth, as long as you overload the meet function with the corresponding behavior, as you did in the julia's snippet).
And it comes with a 0 overhead efficiency, compiler will generate the right functions according to the type you gave.
Plus with such template function you don't need the pet class at all.
You are right, but the point is Julia can do that in runtime.
You can do that with templates, yes, and people do. And it’s using code generation which means that all different options must be pre-compiled. That’s why compile times of C++ programs easily spiral out of control. People use it despite the long compile times, which kind of votes with their feet that multiple dispatch is a feature worth having.
@@ArneBab The compile-time cost of template instantiation is really not as large as people seem to think it is. There are many other reasons why C++ is slow to compile; the clue that just instantiating some boring templates is not the reason is that there are other languages with template-like functionality that compile faster. It's really the frontend that's the bottleneck here, _not_ the backend.
Also. It's a _feature_ that this stuff gets resolved at compile time and I won't get stuck indirecting across N vcalls in a hot loop. A feature like runtime multiple dispatch could be interesting but it would have to be opt-in. Note that even as is C++ offers essentially the same composability benefits except it actually provides tools to define and constrain interfaces (concepts with C++20, and SFINAE before that, with ordinary nominal typing available also), which makes it much easier to ensure behaviors are globally correct and to fail compilation otherwise, rather than the Julia way of "silently returning the wrong result".
To slide at 27:40 - I think that this Expression problem is nicely solved by Interfaces, hugely used not by in OO langs. They make it possible to define new types for existing operations by implementing them on existing types, and also define new operations for existing types - again by implementing new interfaces for those already existing types. I like this concept for being runtime-costless. However, I don't know Julia at all, even though it looks really nice for that "numeric" stuff. And the use of Unicode - that's amazing :D
That's pretty much what Rust does, right? And I guess, to an extent, is what julia does as well, but every function is its own, separate interface. That's probably why the syntax is quite a bit simpler.
I think the key difference is that interfaces need to be implemented upstream, at the source code you wanna extend from. And they still gonna be restrictive to potential new usecases.
With multiple dispatch you don't require changes upstream at the source and don't impose restrictions on the future.
Typeclasses in functional languages (e.g. Haskell) are like interfaces but can be defined and implemented in the 'user' codebase.
Traits in Rust are admittedly a lot more restrictive, although for good, extremely Rust-specific reasons.
"It just works" - a great man
Is there a way to have "name" be part of Pet and not having to re-define it for every subtype?
Edit: I found it mentioned in the video and also that it's a long discussed controversial feature, but still I didn't find anything regarding programming. If the fields are in the abstract type there are tons of checks that can be done in compilation time and save you future heart attacks.
Please cut the silent parts using youtube editor
Wery good lesson. What best books according to can you offer you Julia for learning?
Este vídeo es absurdamente bueno
I think I have to learn this language now.
Could we download the presentation slides?
How is this different from trait objects (dyn) in Rust?
I struggle with the question of how to *properly* assemble new types in a sensible way. Like there are few concrete guildelines .. i
Way back early in my career, I wrote an interactive graphics program on MSDOS. Think of AutoCAD but simpler and geared toward metal roofing only. I was learning OO, developing our own geometry and graphics and input device libraries, and later on learning Windows 16-bit API. Fun times :(
There were times multiple dispatch would have been great, but I had to come up with ways for the right method to be called given two specific class. Writing methods for the specific classes to work with specific other classes, with only single-dispatch polymorphism, without using switch statements and an "const int object_type;" member, ugh! No wonder it took so long and had subtle bugs.
We are living in good times now with Julia and other new languages.
About adding methods to CBOO types... well, it can be done in at least Python and C++. In Python you can monkey-patch anytime, anywhere, and expand classes as you see fit. You can easily use free-standing functions that get inserted into classes when the module is imported, based on single dispatch. In C++ you can also do it. Edit the header, add the stuff you need, then implement it in another .cpp file, done. Sure, it takes vendoring of dependencies, and rebuilding everything but it's not impossible. Worst case you can invoke UB that really isn't on all common compilers, and duplicate just the header you want, and add the methods you need. Then fix whatever code broke, and you're set.
Lol, yeah, it's not pretty in CBOO languages. I'm starting to look at Julia for embedded numerical programming. It looks much nicer to use than C++ for digital control and DSP. Gonna give it a go.
Reflection will be added to C++ next. Why not multiple dispatch? What if?
C++ does have runtime polymorphism through virtual functions, it achieves a similar effect without having to deal with template hell
Nice talk. On the slide at 11:13, I would say "polynomial" instead of "exponential".
n function arguments = X^n
Oh, come on, C++ (since C++17) has std::variant and std::visit, they are exactly about multiple dispatch - std::visit can accept multiple variants. So std::visit can do everything that's mentioned in the video, with C++'s static typing, optimizing based on concrete types and with a dispatch performance of single virtual call (clang, gcc) or faster (msvc). And that's not some ad hoc library or handwritten thing, that's a part of the standard for some time.
I'm a C++ dev and I hate the C++ visitor pattern (the classic design pattern) since it's trying to fix the missing of multiple dispatch in C++ so it makes bloat of code, and you have to define all methods in the base class. std::variant also try to fix missing C++ union and allow you to have heterogeneous types in a container, but this is slow and not cache friendly. In Andy G's Blog "A true heterogeneous container in C++" he offers a better way, but all containers are owned by a single owner class so very dangerous.
One reason I sometimes remove C++ from my resume and linkedin is these complexities. So many things easy in other languages can be done in C++ but only with using several std::strangenewthings and messy syntax. Many C++ developers seem to be the type of people who enjoy complexity just for the sake of complexity and abstractions. I would never want to work at a company where that's allowed.
The class-like version of this is aspect-oriented programming, no?
People laud multiple dispatch, but you really should say multiple dispatch with a type hierarchy. MD would not fly without it.
i feel like multiple dispatch already implies type hierarchy.
About the RBG example, you point OOP difficulties, but you didn't mention that over languages deals with it in the exact same way as julia does.
Again in c++ you can define function outside of a class, make it a template function if needed, create overlaoded functions etc.
That's addressed in the prelude: function overloading ≠ multiple dispatch - what definition is called is based only on the *static* types of the arguments, which means that it does not call the correct method and adds no additional expressiveness over C, which is extremely weak at generic programming. Template functions similarly can only be based on the static types of arguments.
@@StefanKarpinski But your examples don't do a very convincing job of showing why you would want dynamic dispatch over static dispatch. You could argue that Julia gets dynamic for free, but in a non-JIT language, you always want the dispatch to be static, because otherwise the performance will be absolutely terrible.
A lot of languages nowadays also introduce a trait or an extension method system, which allows people to add methods to existing types after the fact. This 'issue' has largely been solved already.
Am always confused about multiple dispatch..it doesn't really help with speed of execution, just helps with making the code generic right ? I can always make specalized functions to get the same behavior or use if-else.... Or am I misunderstanding this. Also in my experience the more helpful dynamic multiple dispatch is slow.
Nitin Arora Well the thing is you would have to write a specialized method every time for a new type, whereas you only need a single generic method definition to work on any inheriting types in Julia. Furthermore, there is no speed penalty, since Julia will just compile a type-specialized version of the method for each type.
@@LongNguyen-nd2bt thanks and agreed. Was trying to make sure I understand properly.
There is still a speed penalty for dynamic dispatch, which is resolved at runtime based on some use value,.. right ?
Nitin Arora Not in Julia. As long as the function is type stable, the compiler is able to infer the types of everything inside the function and prepares type-specific code at compile time. Julia only drops down to dynamic dispatch if a variables change types and/or the compiler gives up on type inference. So most of the times, generic code has no dynamic dispatch: Julia compiles a type-specialized version automatically.
@@LongNguyen-nd2bt But you still need to write a new dispatch for a new type right? Otherwise, it will either not work or not specialized, am I correct? It is slightly easier than writing a function but not different in my opinion.
Khoa Tran It depends. You might want to write specialized methods for your type (for example, linear algebra methods for sparse arrays should take advantage of the sparsity). However, because of Julia’s multiple dispatch paradigm, codes are usually written to be extremely generic. This way, if you want to make your own custom array, you only need to write dispatch for a few functions (size, getindex, setindex, getindex!, setindex!, there are a few more but they are optional) and Julia’s array code base will not just work for your new array, but has great performance. This is because other array functions use the generic, basic ones, so as long as you define them, everything else will be specialized on your array to make code fast.
The C++ code at 8:54 is really stupid. None of the experienced C++ users write such a code. For a possible implementation of multiple dispatch in C++, check Item 31 of More Effective C++. The C++ frontend of Pytorch actually implemented a huge dispatch engine inside.
The C++ code is clearly toy code to show the semantic difference between function overloading and multiple dispatch. Saying that you'd do it some other way seems to miss the point of the prelude section.
So PyTorch developers found multiple dispatch so essential that they went to the trouble of implementing and using it internally. Doesn't that kind of prove the premise of this presentation? Wouldn't it be even better to have really good (and fast) implementation of multiple dispatch in the language so that everyone can use and interoperate with it instead of having a limited implementation hidden away in a library?
Visitor pattern really shows how it sucks in Java 🤣
Not even once mentioned other languages with multiple dispatch (e.g. Haskell, Clojure) or did I miss it? There by the way, arbitrary redefinition is frowned upon ("orphan instances"), and it is advised only to extend implementation if you own either the API or an implementaion. Is not it a problem in Julia?
Yes, you missed it, he mentions Lisp and Closure starting here: 33:51
@@AndriyDrozdyuk I do not watch Q/A, usually...
I didn't think Haskell had subtype polymorphism. Can you show working Haskell code for the 'Pets' example, which doesn't suffer the same problem as C++ overloading?
It looks like multi-dispatch with static typing (compile-time) is hard. Nim language decided to deprecate it to simplify their implementation.
14:24 yea some good vector code .. largely scalar arithmetic
I *think* the argument about the short-comings of C++ is solved using the virtual keyword, which does dynamic dispatch at run-time. Not an issue for Java- everything is already virtual under the hood.
Virtual runtime dispatch is slow though. What is described here utilizes the JIT compiler to get around that issue, but that's precisely the case where C++ goes to runtime dispatch in order to handle the combinatorial complexity that's required, while Julia does JIT compilation to handle it. It is effectively something that you cannot always do ahead of time, which is the point.
You can only add the virtual keyword to methods, not overloaded functions. Methods are internal to classes, which is exactly the problem discussed later in the presentation. So in C++ you have a choice between function overloading, which looks right but doesn't dispatch and does the wrong thing, or methods, which can still only dispatch on one argument, and doesn't allow external addition of methods to already defined types. It's also possible to use templates, but then everything has to be known completely statically. One of these features might solve your particular problem, but it introduces others and you have to make a choice between very different designs.
C boo :D Way better than D++
this Stefan fella is clearly woke
Dude doesn't even understand that classes are defined when there's an invariant to be maintained, so it's hard to take any other opinions seriously. "Oh it's only good for namespacing :))" no, brother, just no.
Yeah I’m sure a Harvard-educated guy who has a PhD in Computer Science and co-wrote one of the world’s most popular programming languages doesn’t understand what classes are for 🙄 The arrogance and stupidity of people in TH-cam comments is just breathtaking sometimes.
@@therainman7777 He obviously doesn't, and we know that because he told us :) I don't care what chairs he sat on.
@@isodoubIet The problem is obviously that you misunderstood what he was saying. At no point did he say he doesn’t understand that classes provide invariance. That’s the entire point: the fact that they provide invariance is what leads to the expression problem, where you cannot simultaneously modify the data model and the operations at the same time in a OOP language, without needing to modify the original code.
The entire foundation of his talk is built on the fact that classes provide invariance. But rather than thinking that maybe you missed something in the talk, or misunderstood something, you jumped straight to thinking that a world-class computer scientist does not understand the point of classes-despite this being something that is taught in the first year of every CS program on earth. Ridiculous.
@@therainman7777 No, I misunderstood nothing. It doesn't matter that he didn't say it, and in fact I expect him to not say it: why would he explicitly mention the thing he doesn't know he doesn't know?
Fact remains, Julia as a language and ecosystem is still a buggy mess, largely as a result of their early design decisions surrounding unconstrained interfaces (the very point of the talk), as well as some other bad decisions (indexing starting at 1 for example), so excuse me if I'm not impressed by this person's language design chops, especially _when he gives me unambiguous evidence that he doesn't understand basic concepts._
@@therainman7777 PS: "That’s the entire point: the fact that they provide invariance is what leads to the expression problem, "
Somehow I don't think you know what an invariant is, either.