It's actually amazing how many people don't understand that many languages (particularly java) are single dispatch. None of my peers going through university even know what the term means and I have been docked marks because the prof computed the answer to a problem as if java supported multiple dispatch. I had to convince the professor to actually compile the code before she believed it. I wonder where this is best taught because it's a really interesting decision of languages yet very few people learn about it.
I run into the same problem. I thought it was because I work in infosec so many people here don't have CS degrees or do a lot of dev work. I don't remember exactly where I learned dispatch, binding, etc. We did have a software dev class where I learned different design patterns.
Visitor pattern always blows people's minds when they first see it in action hehe.
Exactly: foo.bar() has dynamic behavior based on the runtime type of foo. Why shouldn't foo.bar(baz) similarly be able to distinguish the runtime type of baz and pick the 'right' overload?
Would it be more surprising to Java newbies if it did work that way?
But then, what is the point of foo being associated with the class of bar?
Multiple dispatch screams for the abolishment of methods as properties of objects, in favor of generic functions.
Youc an still have the syntactic sugar obj.foo(arg), but it basically just translates to foo(obj, arg) where foo is a generic function not associated with foo's class in any way, and obj and arg have equal status.
But then, what is the point of foo being associated with the class of bar?
Multiple dispatch screams for the abolishment of methods as properties of objects, in favor of generic functions.
Youc an still have the syntactic sugar obj.foo(arg), but it basically just translates to foo(obj, arg) where foo is a generic function not associated with foo's class in any way, and obj and arg have equal status.
This generic function is what has methods.
Say we implemented "funky" numbers, and would like to implement multiplication of funky and real. When funky is the left argument we get funky.mult(real). If real is no the left, we get real.mult(funky). These functions do the same thing (the multiplication is commutative), yet ... they have to live in separate classes? It is nonsensical.
Under generic functions, we just have mult(real, funky) and mult(funky, real) which are methods of the generic mult(whatever, whatever). They both belong to the one generic function: that is the more reasonable organization.
> But then, what is the point of foo being associated with the class of bar?
One benefit is that the name `bar` is looked up in `foo`'s namespace, which means that it doesn't have to be in the current global namespace. This is a mixed blessing, but it's sometimes what you want.
That's an interesting point and basically leads us to "member generic functions". An object has some static slot which is a function, and treated as a method: it can be called obj.meth(args, ...). But, this method is also a generic function. A generic function is a function; an object can have a function, and so an object can have a generic function.
Object must have name spaces by definition, because they are collections of named properties.
These name spaces do not have to be conflated with program lexical scopes, whereby if you are a piece of code such and such a "blessed" function, you "see" the name space of the class as if it were lexical variable bindings.
You definitely don't want crud like different scopes in the program which are all working with exactly the same object, and want to access slot S, but they all refer to a different S because they are associated with a different place in the inheritance hierarchy, and that hierarchy contains unrelated slots named S at different levels. A given object must just have one S.
class Bar
def foo(baz :: Baz)
...
end
end
def foo(bar :: Bar, baz :: Baz)
...
end
could be in this hypothetical language that the former would be allowed to access private member variables on bar = Bar.new, while the latter wouldn't.
The questions then are:
a) Is private state something we want?
b) Could private state access control be implemented in a different way (Lexically? Package level? Additional annotation?)
> Could private state access control be implemented in a different way
The idea of friend functions of a class could be adapted from C++.
It could work dynamically like this.
Firstly, given obj.slot or obj.fun(); if the type of obj is not known in the given scope, then these accesses are disallowed unless slot and fun are public.
Secondly, a class can be (dyamically) associated with a (dynamically extensible) list of friend generic functions.
When a new method is being compiled for a generic function, the compiler uses the class information about the argument (which specializes it) to check the friend list of that class. Then inside the friend method, obj.slot and obj.fun() are allowed even if slot and fun are private.
(Friendship of compiled code couldn't be revoked; once a method is processed by at least the expanding code walker, if not compiled, then it cannot lose access even if the generic function is removed from the friend list of that class.)
I tripped over this as an undergraduate. On the surface, overloading looks like it has the same purpose and function as (virtual) method dispatch, but the difference between static and dynamic typing is subtle enough that they don't interact the way one might expect them to.
This is why I spent a section on showing the "failed
attempt". It's surprising how many folks don't understand the difference between overloaded functions (compile-time dispatch) and true multiple dispatch (at run time).
I have to admit, the failed attempt is the first thing I thought of. Thanks for including that and helping me understand why it doesn't work as expected.
I learned about double/single dispatch when I was an undergrad taking a course on design patterns. Trying to wrap my head around the visitor pattern was kind of a pain, but once I saw how it was done in a language that supported double dispatch, it made a lot more sense. Overall, it was one of the more interesting and useful courses I took.
One downside of the brute-force approach not mentioned is there's a pretty heavy penalty paid for dynamic_cast. You're going to be bringing in RTTI which for a lot of C++ domains can be a non-starter.
It used to be common for RTTI to require jumping through extra hoops (i.e. adding compiler options) but it's supported by default by most C++ compilers these days.
True. Alexandrescu touches upon this in his Modern C++ take on multimethods. He uses static per class integers to uniquely identify them instead of RTTI. This is not unlike the special home-cooked "RTTI" LLVM uses (http://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html) to avoid the large cost of typeid and dynamic_cast, so that it can be built with -fno-rtti but still provide runtime identification for types.
Naturally, these approaches require intrusion (special field/static member in each class)
Generalized multimethods are an inherently costly abstraction. This paper[1] provides a good survey of the state-of-the-art—at least as of 20 years ago—in the context of Dylan.
I'll have to re-read that section of Modern C++ to recall the runtime algorithm, but I'd be interested on any pointers to newer research or engineering on dispatch techniques.
It's too bad that (AFAIK) no 'mainstream' high performance language has a multiple dispatch abstraction that could motivate more work.
Julia does it right, but then also cheats. It uses high performance multi-methods, partially because it's a lisp and common lisp has been optimizing multi-methods for decades now. But also because Julia has a built in JIT with a very powerful type analyzer. Which means that while every function in Julia is a multi-method, you almost never pay the costs when writing high performance code.
The cheating comes from the run-time compilation features being leveraged to inspect "already compiled" code and dodge around the dispatch. However this causes problems in larger systems (Julia has some serious shortcomings when it comes to large projects, and they ban people who talk about it too much) because if you add a method to the multiple dispatch already compiled functions won't make use of it without recompiling them too, this is basically the expression problem being displayed in a dynamic language (because they choose speed over true dynamicism; they leverage the dynamic features for a different purpose and loose the feature typically gained). This is a very bad form of cheating because multi-methods are often seen as a solution to the expression problem, but Julia still has the problem even though they use multi-methods.
Try the following:
# Library
abstract bar
ex(x) = println("dynamic")
ex(x::bar) = println("bar")
test(x::bar) = ex(x)
type foo <: bar
x :: Int
end
test(foo(5))
# Now our code
ex(x::foo) = println("foo")
test(foo(5))
It's probably doable, but also note how they say there will be a performance cost at runtime and it will be everywhere. Like I said, julia is cheating right now with the speed they are achieving while having multi-methods. It can be done, but they will loose their shiny performance numbers, or (for example) have to check to see if you need to recompile their entire standard library when you overload + while not crashing currently executing code. They are playing a shell game with the dynamic calls, and taking up large amounts of memory because of it, this will take up even more memory. And is another reason why Julia is not good for any large code base or doing anything but what the language was designed for.
I mean scientific computing is what the language was designed for, use it if that's what you need.
Just don't expect to be using those shiny numbers for anything but scientific computing (and most specifically when involving large matrices). Their namespacing and modularity is terrible, writing a complex gui, non-trivial web server, 3d renderer, or any sort of real time system is right out. And they seem dead set against changing that (did I mention they ban people for making too much noise about it). But if you want to simulate something over a cluster it's a great choice.
I should probably note that I have a poor opinion of their community from my observations (they are hilariously salty), I may be a bit biased.
Can you explain why you couldn't write a 3D renderer or complex gui in Julia? As someone who does exactly that it's a bit hard to follow your reasoning...
Well, real-time 3d rendering anyway, thanks to the garbage collector and having very little control over it. How complex of a GUI are we talking here? Do you split it into many namespaces? Have long load times when not on a powerful dev machine? Ever tried to deploy said GUI? Do the right thing when exceptions in your program happen, or does it just crash the GUI or spit you out to the repl? Because I'm betting your GUI is not meant to be used by anyone but a couple of people with familiarity with the system, which is fine, but not generally what a GUI is made for.
Reference counted ones, by carefully controlling when the reference count for objects are released you can make sure that the rendering thread never has to do any of the expensive ones, and instead all (non-trivial) reference releases are shunted off into a different thread for deallocation. In the general case you don't care, and in the specific case you have a fine enough control you can get around the problem of unknown gc-pauses. It's slower - it is a dynamic language afterall - but it's consistent and real-time is more about being consistent.
deployment + load times: obviously things aren't perfect, Julia is at version 0.4, after all ;) There are a lot of low hanging fruits for compile time and deployment, so I'm sure that the situation will look a lot different in a year or two.
I'm not sure why Julia itself should make it difficult to "do the right thing" when exceptions occur...
Real-time 3D rendering is a big area. Will we have virtual reality with ultra low latency in the next year? Definitely not! Can we have 3D CAD/scientific visualizations which hardly stutters? Definitely! Our library is already very smooth and we didn't even start optimizing yet. That's something that seems to be almost impossible in e.g Python (without just calling C for everything).
So while most of these arguments are currently spot on, I do think that there is nothing fundamentally wrong with Julia. And while the maturity is not there yet, you can already be very productive with Julia and build for the future.
Yeah and there is already an improvement to that: https://github.com/JuliaLang/julia/pull/12541. Well, anyways, I think you can easily find a lot of unsatisfactory constructs in any language, especially in young ones ;) If they outweigh the advantages is debatable. So far I've been finding satisfactory workarounds for the most daring issues, so for me the conclusion is indeed very positive.
> Their namespacing and modularity is terrible, writing a complex gui, non-trivial web server, 3d renderer, or any sort of real time system is right out. And they seem dead set against changing that
There are many dozens of open issues discussing namespacing, interfaces, levels of type abstraction and extensibility, garbage collector improvements, i/o latency problems, task-switching performance, and more.
Prioritization of core effort in certain directions does not mean other issues are suppressed or even forgotten. Considerate proposals in other areas are welcome, and pull-requests implementing such proposals will be gratefully reviewed. They may not always be accepted -- immediately or sometimes ever. There is certainly some conservatism about adding features (such as interfaces), because features have costs and are near-impossible to remove once added. But other things just take time to get merged; for example, the generational GC took over a year, and there are other very large proposals that have been pending for longer than that because the implementation is lacking in some way or the implications are not fully worked-out to the point of consensus acceptance. That's ok, and IMHO healthy.
Except their consensus making prevents real needed features from seeing any progress, sure they have thousands of open issues on the topic, but when did any of them last move. Oh and arguing too strongly on controversial issues (hex stringification! oh no!) gets you banned (that was a hilarious read). So how is anything supposed to move when there is a split in the community?
It looks like someone got banned for submitting a PR as a hypothetical solution which a core team member disagreed with, why would I ever contribute to a project like that.
I'm not aware of any pull-requests implementing an incremental GC with pinning support, or any alternative module/namespacing scheme. Those would certainly be welcome.
As I said, the people actively working on the compiler have to prioritize because time and resources are finite. This is not the same as anyone being "dead set against changing", or a "ban people for making too much noise about it".
> when did any of them last move.
Here's a sampling of some improvements over the past 4 months.
There is no runtime cost to fixing this. You have to track dependencies between functions, which costs memory, and recompile functions when methods they depend on are changed, which costs compile time, but fixing this will not affect runtime performance.
The current behavior, although theoretically a problem, is not a big issue in practice. The reason is simple: unlike the example above, real-world programs tend to define a bunch of types and methods first and then the main program runs, using those types and methods.
Where it is actually a problem is in interactive development. At the REPL, people tend to redefine the same methods over and over, and it can be quite bothersome that those changes aren't always reflected. You can force an update by redefining the calling method as well, or you can just restart the REPL. Annoying, but not the end of the world.
I'll quote you as my response: "That would move the performance impact to runtime (and it would be everywhere)" and "You have to track dependencies between functions, which costs memory, and recompile functions when methods they depend on are changed, which costs compile time" and then quote myself "this will take up even more memory". Also I'd be curious to hear your thoughts on multi-threading.
Also real systems have many libraries. Which will each take turns in defining things. And some may run initialization code, causing certain things in their library to run. The fact of the matter is you don't have "real" multi-methods because of it, and it's a problem with making large systems.
I'm not saying that interleaving of execution and definition doesn't happen – it definitely does, that's how library loading works in dynamic languages. However, it is demonstrably not common to define methods for a type, call them, and then define methods that overwrite those methods.
But in a language with multi methods defining new extensions to the type hierarchy is defining methods that overwrite some other methods. If startup code for a library calls any methods which are later meant to be extended you are going to get weird unexpected behavior.
Lets see, there is a logging library with a custom string formatter, in another library I specialize the string formatter, and I log that the library started up with a value based on that abstract tag. Now as a user I specialize a concrete type for logging, but it doesn't work, why? That's a weird error, and also, the expression problem via multi-methods, well done you guys implemented multi-methods that don't solve one of the core purposes of multi-methods.
How much you wanna bet I can find startup code in many python libraries which calls code that is later specialized by users. Edge cases are where it's important.
> Julia has some serious shortcomings when it comes to large projects, and they ban people who talk about it too much
Only one person has ever been banned on GitHub and it was not for talking about any shortcomings. That person is still allowed to and regularly does post on Julia mailing lists – no one has ever been banned from mailing lists.
Shrug I've never seen the mailing lists for Julia, I just recently started reading the github every now and then because it is an interesting language, and I like seeing the development of it. But ~~your community is~~ you are one of the most hilariously salty one's I've ever watched. And sorry but it does look like you banned him for being pushy about the problems making modular software, and doing real development with the language. Which I note you don't dispute.
Multiple dispatch is a great way to handle branching complexity. Let's say you have Process 1 which requires Steps A, B, C and D, and Process 2, very close to Process 1, which requires Steps A, B, C' and D.
The naive implementation would be:
def process():
A()
B()
if [conditions for process 2]:
C'()
else:
C()
D()
process() becomes a lot easier to test, since you only need to mock out/outsmart figure_out_right_process() instead of mimicking the right logic for [conditions for process 2]. You can test each process independently, since you don't need to fulfil the [conditions for process 2] in each test, and if those conditions should change, you only need to change figure_out_right_process() instead of at each branch in your code.
It may look verbose with only one branch, but the second you have more than two processes, or nested branches, the class based way looks a lot cleaner.
i don't understand what this has to do with multiple dispatch. only the this argument is dynamically dispatched on. multiple dispatch is the same idea, except with more than just the this argument being dispatched on, allowing you to define custom methods for any combination of possible arguments and getting to the right one at runtime.
69 comments
[ 44.8 ms ] story [ 2283 ms ] threadVisitor pattern always blows people's minds when they first see it in action hehe.
Would it be more surprising to Java newbies if it did work that way?
Multiple dispatch screams for the abolishment of methods as properties of objects, in favor of generic functions.
Youc an still have the syntactic sugar obj.foo(arg), but it basically just translates to foo(obj, arg) where foo is a generic function not associated with foo's class in any way, and obj and arg have equal status.
This generic function is what has methods.
Multiple dispatch screams for the abolishment of methods as properties of objects, in favor of generic functions.
Youc an still have the syntactic sugar obj.foo(arg), but it basically just translates to foo(obj, arg) where foo is a generic function not associated with foo's class in any way, and obj and arg have equal status.
This generic function is what has methods.
Say we implemented "funky" numbers, and would like to implement multiplication of funky and real. When funky is the left argument we get funky.mult(real). If real is no the left, we get real.mult(funky). These functions do the same thing (the multiplication is commutative), yet ... they have to live in separate classes? It is nonsensical.
Under generic functions, we just have mult(real, funky) and mult(funky, real) which are methods of the generic mult(whatever, whatever). They both belong to the one generic function: that is the more reasonable organization.
One benefit is that the name `bar` is looked up in `foo`'s namespace, which means that it doesn't have to be in the current global namespace. This is a mixed blessing, but it's sometimes what you want.
These name spaces do not have to be conflated with program lexical scopes, whereby if you are a piece of code such and such a "blessed" function, you "see" the name space of the class as if it were lexical variable bindings.
You definitely don't want crud like different scopes in the program which are all working with exactly the same object, and want to access slot S, but they all refer to a different S because they are associated with a different place in the inheritance hierarchy, and that hierarchy contains unrelated slots named S at different levels. A given object must just have one S.
The questions then are:
a) Is private state something we want?
b) Could private state access control be implemented in a different way (Lexically? Package level? Additional annotation?)
The idea of friend functions of a class could be adapted from C++.
It could work dynamically like this.
Firstly, given obj.slot or obj.fun(); if the type of obj is not known in the given scope, then these accesses are disallowed unless slot and fun are public.
Secondly, a class can be (dyamically) associated with a (dynamically extensible) list of friend generic functions.
When a new method is being compiled for a generic function, the compiler uses the class information about the argument (which specializes it) to check the friend list of that class. Then inside the friend method, obj.slot and obj.fun() are allowed even if slot and fun are private.
(Friendship of compiled code couldn't be revoked; once a method is processed by at least the expanding code walker, if not compiled, then it cannot lose access even if the generic function is removed from the friend list of that class.)
Firstly, obj.member could be disallowed if
I think this comment sums it up well: https://news.ycombinator.com/item?id=11528588
This is why I spent a section on showing the "failed attempt". It's surprising how many folks don't understand the difference between overloaded functions (compile-time dispatch) and true multiple dispatch (at run time).
Naturally, these approaches require intrusion (special field/static member in each class)
I'll have to re-read that section of Modern C++ to recall the runtime algorithm, but I'd be interested on any pointers to newer research or engineering on dispatch techniques.
It's too bad that (AFAIK) no 'mainstream' high performance language has a multiple dispatch abstraction that could motivate more work.
[1] http://www.eecs.berkeley.edu/~jrb/Projects/pd.pdf
The cheating comes from the run-time compilation features being leveraged to inspect "already compiled" code and dodge around the dispatch. However this causes problems in larger systems (Julia has some serious shortcomings when it comes to large projects, and they ban people who talk about it too much) because if you add a method to the multiple dispatch already compiled functions won't make use of it without recompiling them too, this is basically the expression problem being displayed in a dynamic language (because they choose speed over true dynamicism; they leverage the dynamic features for a different purpose and loose the feature typically gained). This is a very bad form of cheating because multi-methods are often seen as a solution to the expression problem, but Julia still has the problem even though they use multi-methods.
Try the following:
It should print `bar\nfoo` it doesn't.https://github.com/JuliaLang/julia/issues/265
Look at the commits at the bottom.
I'm wondering what this performance cost will be and if significant, can all that brainpower at MIT etc really not find a way to mitigate it?
This is a practical question for me because I'm considering Julia for a project and my personal data language.
This is the upcoming python alternative ecosystem, also with multi dispatch:
https://github.com/libdynd/libdynd https://github.com/numba/numba https://github.com/blaze/blaze
Just don't expect to be using those shiny numbers for anything but scientific computing (and most specifically when involving large matrices). Their namespacing and modularity is terrible, writing a complex gui, non-trivial web server, 3d renderer, or any sort of real time system is right out. And they seem dead set against changing that (did I mention they ban people for making too much noise about it). But if you want to simulate something over a cluster it's a great choice.
I should probably note that I have a poor opinion of their community from my observations (they are hilariously salty), I may be a bit biased.
I want to keep my general code and scientific code in the same language.
So python it is.
I'm not sure why Julia itself should make it difficult to "do the right thing" when exceptions occur...
Real-time 3D rendering is a big area. Will we have virtual reality with ultra low latency in the next year? Definitely not! Can we have 3D CAD/scientific visualizations which hardly stutters? Definitely! Our library is already very smooth and we didn't even start optimizing yet. That's something that seems to be almost impossible in e.g Python (without just calling C for everything).
So while most of these arguments are currently spot on, I do think that there is nothing fundamentally wrong with Julia. And while the maturity is not there yet, you can already be very productive with Julia and build for the future.
Untyped, sometimes incorrect, exceptions, https://github.com/JuliaLang/julia/issues/12485 and related.
There are many dozens of open issues discussing namespacing, interfaces, levels of type abstraction and extensibility, garbage collector improvements, i/o latency problems, task-switching performance, and more.
Prioritization of core effort in certain directions does not mean other issues are suppressed or even forgotten. Considerate proposals in other areas are welcome, and pull-requests implementing such proposals will be gratefully reviewed. They may not always be accepted -- immediately or sometimes ever. There is certainly some conservatism about adding features (such as interfaces), because features have costs and are near-impossible to remove once added. But other things just take time to get merged; for example, the generational GC took over a year, and there are other very large proposals that have been pending for longer than that because the implementation is lacking in some way or the implications are not fully worked-out to the point of consensus acceptance. That's ok, and IMHO healthy.
Other people seem to agree on that point: http://danluu.com/julialang/
As I said, the people actively working on the compiler have to prioritize because time and resources are finite. This is not the same as anyone being "dead set against changing", or a "ban people for making too much noise about it".
> when did any of them last move.
Here's a sampling of some improvements over the past 4 months.
- Debugging, everyone's priority by astronomic margins, has seen massive work and a recent preview-release (I've been using it since the announcement: rough edges, but very solid core): https://github.com/Keno/Gallium.jl/commits/master https://github.com/Keno/ASTInterpreter.jl/commits/master https://github.com/JuliaLang/julia/pull/15859 https://github.com/JuliaLang/julia/pull/15444
- Revamp of closures to make anonymous functions as fast as any other: https://github.com/JuliaLang/julia/pull/13412
- Significant compiler performance improvements: https://github.com/JuliaLang/julia/pull/15300 https://github.com/JuliaLang/julia/pull/14543 https://github.com/JuliaLang/julia/pull/15609
- Work towards static compilation (a number of PRs): http://juliacomputing.com/blog/2016/02/09/static-julia.html
- Multithreading improvements: https://github.com/JuliaLang/julia/pull/15917 https://github.com/JuliaLang/julia/pull/15106
- Someone else pointed you to recent commits toward fixing the recompilation issue.
The current behavior, although theoretically a problem, is not a big issue in practice. The reason is simple: unlike the example above, real-world programs tend to define a bunch of types and methods first and then the main program runs, using those types and methods.
Where it is actually a problem is in interactive development. At the REPL, people tend to redefine the same methods over and over, and it can be quite bothersome that those changes aren't always reflected. You can force an update by redefining the calling method as well, or you can just restart the REPL. Annoying, but not the end of the world.
Also real systems have many libraries. Which will each take turns in defining things. And some may run initialization code, causing certain things in their library to run. The fact of the matter is you don't have "real" multi-methods because of it, and it's a problem with making large systems.
Lets see, there is a logging library with a custom string formatter, in another library I specialize the string formatter, and I log that the library started up with a value based on that abstract tag. Now as a user I specialize a concrete type for logging, but it doesn't work, why? That's a weird error, and also, the expression problem via multi-methods, well done you guys implemented multi-methods that don't solve one of the core purposes of multi-methods.
How much you wanna bet I can find startup code in many python libraries which calls code that is later specialized by users. Edge cases are where it's important.
Only one person has ever been banned on GitHub and it was not for talking about any shortcomings. That person is still allowed to and regularly does post on Julia mailing lists – no one has ever been banned from mailing lists.
https://groups.google.com/forum/#!forum/julia-users
Here's a recent (and typical) example of a lengthy series of technical and sometimes pointedly-critical questions:
https://groups.google.com/forum/#!searchin/julia-users/%22ve...
The naive implementation would be:
You should implement it as: process() becomes a lot easier to test, since you only need to mock out/outsmart figure_out_right_process() instead of mimicking the right logic for [conditions for process 2]. You can test each process independently, since you don't need to fulfil the [conditions for process 2] in each test, and if those conditions should change, you only need to change figure_out_right_process() instead of at each branch in your code.It may look verbose with only one branch, but the second you have more than two processes, or nested branches, the class based way looks a lot cleaner.
2) For symmetry, I would make C abstract in the parent class, and create two subclasses, one implementing C, one implementing C'.
3) Having done that, the logic defining the order of the steps can be moved into the parent class.
4) If you want to mock things, it may help to make A, B, and D overridable in the parent class, too.
[1] https://www.youtube.com/watch?v=VeAdryYZ7ak
P.S. I love Seibel's PCL - great book