6 ms·

" (...) - In an OO language, you can add a new case by creating another subclass and implementing the methods. But, if you want to add a new function to a datat

" (...) - In an OO language, you can add a new case by creating another subclass and implementing the methods. But, if you want to add a new function to a datatype, you have to add it to the superclass and implement it on all the existing subclasses, which means modifying a lot of files and recompiling most of the program. - In a FP language you can add a new function to an existing datatype just by adding a function. But, if you want to add a new case, you have to add the constructor and modify all the functions that use the datatype, which means modifying a lot of files and recompiling most of the program. (...)" ...and by using multiple dispatch (as in Julia) you can do both. And it just works. True code reuse. Why did it take us so long to recognise this?

amboo7 6y ago
Common Lisp Object System had multiple dispatch for ages. Some other religions do not like it.
- StefanKarpinski 6y ago
  A subtlety we've discovered through success and growth of Julia is that even if your language has some solution to the expression problem, if it's has non-zero cost and isn't the default then people won't actually use it, which undermines much of the benefit. Systems like CLOS, Clojure and even R, which have multimethods but where they're opt-in and use slow hash-based implementations, don't in practice see most of the benefits that we've seen in Julia from multiple dispatch in terms of code reuse and composability. Another way to say this is that if multiple dispatch is just a feature that you reach for when you need to do something fancy, then it looks like just another feature; when it's ubiquitous it becomes transformative.
tsimionescu 6y ago
I don't think multiple dispatch fixes this problem in any way. The idea here is that you can have an opaque interface. Then, adding new implementations of that interface is very easy. But, if you want to extend the interface, you need to modify all of the existing implementations. Multiple dispatch suffers of this problem just as much as single dispatch. In the other case, you have a transparent interface - anyone can build code based on your data type. But, if you add more cases to your data type, anyone who had functionality built on it needs to take into account the new cases. I think that this is in inherently an unavoidable problem. You can of course expose both kinds of constructs in your language, but you can't make interface implementation easily modifiable, and you can't make sum types easily extensible. The programmer ultimately has to choose the one that they believe will best capture the domain and its probable evolution. What multiple dispatch can do is take some cases where sum types are obviously preferable to single dispatch (operations on related objects) and apply the interface abstraction to those cases as well (without reaching for horrible solutions like the visitor pattern). Edit: thinking a bit more about the article, what they are showing is that you can essentially use the visitor pattern (and multiple dispatch) to implement GADTs instead of using them for regular multiple dispatch with inheritance. Basically, you can use them bring completely disparate types under the same umbrella, just like a GADT. I'm not sure that this still allows subtyping of that GADT as if it were a regular class.
- contravariant 6y ago
  > I'm not sure that this still allows subtyping of that GADT as if it were a regular class. It does, more or less, since any subtype will have to implement the "accept" method for the visitor, which has been defined to only 'accept' the values that can be represented by the GADT. Any subtype will need to define how its possible values map to that of the supertype.
- hlasdjlfhalwjk 6y ago
  Some Rust libraries use a trick to make sum types extensible without introducing breaking changes when a new invariant is added. There is a private/undocumented invariant in the type so every pattern match over the type must have a default/catch-all/wildcard branch (e.g. it is not possible to do an exhaustive match by naming all existing variants). By having a default branch, the match is always exhaustive and there will be no error if a new variant is added. For fields in a sum type something similar can be done: an undocumented, hidden field that cannot be used when the variant is destructed. Therefore it can be only partially destructed and in this case it doesn't matter how many other fields there are in the type variant. Here is an example: https://github.com/rust-lang/regex/blob/master/regex-syntax/src/ast/mod.rs#L177 https://github.com/rust-lang/regex/blob/master/regex-syntax/...
  - ori_b 6y ago
    Forcing a default case is a big step back towards dynamic typing.
    - heavenlyblue 6y ago
      “Hey - we have a solution to your type problem; we just disabled type checking. Genious”
- codr7 6y ago
  There is no need to modify existing implementations when extending an interface using multiple dispatch. You would need to add the required implementations, but there's really no way around that since the logic has to go somewhere. And as soon as you start actually dispatching on multiple arguments, using sum types to solve the same prolem quickly turns into spaghetti.
08-15 6y ago
> Why did it take us so long to recognise this? It didn't take us long. Schemers did multiple dispatch at least 40 years ago. SICP explains how to do it. (Arguably, both R and Julia are Lisp dialects under the hood, just disguised behind a more arcane syntax. Which goes to show that 'practioners' take Lisp seriously exactly as long as they don't know it's Lisp.)
- FridgeSeal 6y ago
  Too many programmers (in my opinion) give up far too early due to surface level syntactical differences. I have a friend who is like this, looked at some Rust code, saw closures with bars instead of parentheses and practically disregarded it on the spot. Took a lot of convincing that they wouldn’t notice after 15 minutes of actually using the language, and what do you know, I was right.
deleted 6y ago
[deleted]
kjeetgill 6y ago
Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping. The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch. The difference, to me, is minimal.
- tsimionescu 6y ago
  > Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping. Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in. In case this is not clear, multiple dispatch refers to choosing which method implementation to call based on the specific runtime subtypes of all function arguments, not just the runtime type of `this` (which is all that Java, C++, and even Python can dispatch based on). It's basically like applying C++ function overloading rules at runtime. > The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch. That's assuming you can modify all existing implementations. If you can't (e.g. if you wanted to modify Iterable to add a new method) then the solution is just.. don't do that. Note that the article also doesn't offer a solution - they're just showing that multiple dispatch can be used to implement a different construct with different limitations (GADTs).
  - jcelerier 6y ago
    > Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in. we're in 2020 using value = std::variant<int, float, string>; void foo(value a, value b, value c) { struct { void operator(int, float, string) { } void operator(float, int, string) { } void operator(float, string, int) { } ///... etc... } visitor; std::visit(visitor, a, b, c); } works fine (and has worked fine since a long time with either boost.variant or in C++11 with eggs.variant, etc...)
pansa2 6y ago
Solving the expression problem requires maintaining static type safety. AFAIK Julia doesn’t do this because it’s dynamically typed.
- shele 6y ago
  People using Julia are quite happy how it alleviates the expression problem compared to languages they used before. Your argument, if I get it right, that Julia can't solve the expression problem because "the expression problem requires maintaining static type safety" reminds of the "Bumblebees can't fly" fable.
  - Hitton 6y ago
    Most people using language X are quite happy how X does things compared to languages they used before. That's why they use the language X. That's also the reason why I consider this type of argument unhelpful.
    - shele 6y ago
      No, not "most people" and not "happy how X does things" but specifically people who have thought about the expression problem's opinion about how Julia alleviates the expression problem compared to other languages they know.
  - saithound 6y ago
    Well, the expression problem is a clearly formulated question: how can we have three desirable things at the same time (no need to modify existing code, no need for code repetition and no need for runtime type errors [1])? See also the project management triangle: if you need something fast, good and cheap, then fast, good and expensive won't be a satisfactory answer, no matter how many millionaires are satisfied with the latter. [1] https://link.springer.com/chapter/10.1007/978-3-540-24851-4_6 https://link.springer.com/chapter/10.1007/978-3-540-24851-4_...
    - shele 6y ago
pa7x1 6y ago
Relevant presentation by one of the creators of Julia: https://www.youtube.com/watch?v=kc9HwsxE1OY https://www.youtube.com/watch?v=kc9HwsxE1OY

amboo7 6y ago

Common Lisp Object System had multiple dispatch for ages. Some other religions do not like it.

StefanKarpinski 6y ago
A subtlety we've discovered through success and growth of Julia is that even if your language has some solution to the expression problem, if it's has non-zero cost and isn't the default then people won't actually use it, which undermines much of the benefit. Systems like CLOS, Clojure and even R, which have multimethods but where they're opt-in and use slow hash-based implementations, don't in practice see most of the benefits that we've seen in Julia from multiple dispatch in terms of code reuse and composability. Another way to say this is that if multiple dispatch is just a feature that you reach for when you need to do something fancy, then it looks like just another feature; when it's ubiquitous it becomes transformative.

tsimionescu 6y ago

I don't think multiple dispatch fixes this problem in any way. The idea here is that you can have an opaque interface. Then, adding new implementations of that interface is very easy. But, if you want to extend the interface, you need to modify all of the existing implementations. Multiple dispatch suffers of this problem just as much as single dispatch. In the other case, you have a transparent interface - anyone can build code based on your data type. But, if you add more cases to your data type, anyone who had functionality built on it needs to take into account the new cases. I think that this is in inherently an unavoidable problem. You can of course expose both kinds of constructs in your language, but you can't make interface implementation easily modifiable, and you can't make sum types easily extensible. The programmer ultimately has to choose the one that they believe will best capture the domain and its probable evolution. What multiple dispatch can do is take some cases where sum types are obviously preferable to single dispatch (operations on related objects) and apply the interface abstraction to those cases as well (without reaching for horrible solutions like the visitor pattern). Edit: thinking a bit more about the article, what they are showing is that you can essentially use the visitor pattern (and multiple dispatch) to implement GADTs instead of using them for regular multiple dispatch with inheritance. Basically, you can use them bring completely disparate types under the same umbrella, just like a GADT. I'm not sure that this still allows subtyping of that GADT as if it were a regular class.

contravariant 6y ago
> I'm not sure that this still allows subtyping of that GADT as if it were a regular class. It does, more or less, since any subtype will have to implement the "accept" method for the visitor, which has been defined to only 'accept' the values that can be represented by the GADT. Any subtype will need to define how its possible values map to that of the supertype.
hlasdjlfhalwjk 6y ago
Some Rust libraries use a trick to make sum types extensible without introducing breaking changes when a new invariant is added. There is a private/undocumented invariant in the type so every pattern match over the type must have a default/catch-all/wildcard branch (e.g. it is not possible to do an exhaustive match by naming all existing variants). By having a default branch, the match is always exhaustive and there will be no error if a new variant is added. For fields in a sum type something similar can be done: an undocumented, hidden field that cannot be used when the variant is destructed. Therefore it can be only partially destructed and in this case it doesn't matter how many other fields there are in the type variant. Here is an example: https://github.com/rust-lang/regex/blob/master/regex-syntax/src/ast/mod.rs#L177 https://github.com/rust-lang/regex/blob/master/regex-syntax/...
- ori_b 6y ago
  Forcing a default case is a big step back towards dynamic typing.
  - heavenlyblue 6y ago
    “Hey - we have a solution to your type problem; we just disabled type checking. Genious”
codr7 6y ago
There is no need to modify existing implementations when extending an interface using multiple dispatch. You would need to add the required implementations, but there's really no way around that since the logic has to go somewhere. And as soon as you start actually dispatching on multiple arguments, using sum types to solve the same prolem quickly turns into spaghetti.

08-15 6y ago

> Why did it take us so long to recognise this? It didn't take us long. Schemers did multiple dispatch at least 40 years ago. SICP explains how to do it. (Arguably, both R and Julia are Lisp dialects under the hood, just disguised behind a more arcane syntax. Which goes to show that 'practioners' take Lisp seriously exactly as long as they don't know it's Lisp.)

FridgeSeal 6y ago
Too many programmers (in my opinion) give up far too early due to surface level syntactical differences. I have a friend who is like this, looked at some Rust code, saw closures with bars instead of parentheses and practically disregarded it on the spot. Took a lot of convincing that they wouldn’t notice after 15 minutes of actually using the language, and what do you know, I was right.

deleted 6y ago

[deleted]

kjeetgill 6y ago

Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping. The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch. The difference, to me, is minimal.

tsimionescu 6y ago
> Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping. Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in. In case this is not clear, multiple dispatch refers to choosing which method implementation to call based on the specific runtime subtypes of all function arguments, not just the runtime type of `this` (which is all that Java, C++, and even Python can dispatch based on). It's basically like applying C++ function overloading rules at runtime. > The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch. That's assuming you can modify all existing implementations. If you can't (e.g. if you wanted to modify Iterable to add a new method) then the solution is just.. don't do that. Note that the article also doesn't offer a solution - they're just showing that multiple dispatch can be used to implement a different construct with different limitations (GADTs).
- jcelerier 6y ago
  > Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in. we're in 2020 using value = std::variant<int, float, string>; void foo(value a, value b, value c) { struct { void operator(int, float, string) { } void operator(float, int, string) { } void operator(float, string, int) { } ///... etc... } visitor; std::visit(visitor, a, b, c); } works fine (and has worked fine since a long time with either boost.variant or in C++11 with eggs.variant, etc...)

pansa2 6y ago

Solving the expression problem requires maintaining static type safety. AFAIK Julia doesn’t do this because it’s dynamically typed.

shele 6y ago
People using Julia are quite happy how it alleviates the expression problem compared to languages they used before. Your argument, if I get it right, that Julia can't solve the expression problem because "the expression problem requires maintaining static type safety" reminds of the "Bumblebees can't fly" fable.
- Hitton 6y ago
  Most people using language X are quite happy how X does things compared to languages they used before. That's why they use the language X. That's also the reason why I consider this type of argument unhelpful.
  - shele 6y ago
    No, not "most people" and not "happy how X does things" but specifically people who have thought about the expression problem's opinion about how Julia alleviates the expression problem compared to other languages they know.
- saithound 6y ago
  Well, the expression problem is a clearly formulated question: how can we have three desirable things at the same time (no need to modify existing code, no need for code repetition and no need for runtime type errors [1])? See also the project management triangle: if you need something fast, good and cheap, then fast, good and expensive won't be a satisfactory answer, no matter how many millionaires are satisfied with the latter. [1] https://link.springer.com/chapter/10.1007/978-3-540-24851-4_6 https://link.springer.com/chapter/10.1007/978-3-540-24851-4_...
  - shele 6y ago

pa7x1 6y ago

Relevant presentation by one of the creators of Julia: https://www.youtube.com/watch?v=kc9HwsxE1OY https://www.youtube.com/watch?v=kc9HwsxE1OY