Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 17:16:10 UTC, Idan Arye wrote: This CAN NOT BE DONE at compile-time, since the compiler doesn't know at compile time the exact subclass of the instance it'll get at runtime. To clarify: I'm not talking about the creation of the multi-method mechanism - which *can* be done at compile-time - I'm talking about invoking that mechanism to determine which overload to call, and this can only be done at runtime. Yes, you're 100% correct. I misinterpreted what you meant. My bad! :P If you look back, you'll notice this argument(and the two before it) was not against multi-methods at the language level - it was about multi-methods by default. If they are optional, instantiating all the overloads will only happen when it's used, so it won't be that bad. I guess not, although I'm still concerned with build time increases. Perhaps I shouldn't be, though. No one is trying to claim that a library implementation will be superior to a language-level solution in terms of speed, memory usage, binary size, compilation speed or syntax elegance. Language-level solutions can usually achieve better results in these regards. The problem is that they come with a price: * External tools needs to be modified to work with them. * Alternative implementations need to implement them(even though the frontend is shared, there can always be some complications(plus I think mutli-methods might need some backend modifications as well, thhoguh I'm no expert on that matter)) * Risking regressions - changing the code will never be as orthogonal as changing the data it works on... The point is that the usefulness of multi-methods, and the inconvenience of having as a library solution are not nearly big enough to pay that price. Well if this was to become a language feature, I think the best way to do it would be a new annotation (@multimethod) on each overload of a certain function, and then during the semantic analysis phase look at invocations of these functions, inserting appropriate casts to the actual object types of any class-type input parameters. Would this work? If so, that should require no changes to the backend. Now obviously it's not going to fit nicely with the standard overloading mechanism in the case of calling a more abstract overload, but that is why it'd be an annotation rather than by-default (although you might be able to get around this by inserting an up-cast manually). By the way, sorry if I'm sounding a little silly at times. I'm an undergrad in Computer Science who's just started a course in Compiler Design, so please forgive me for any obvious holes in my knowledge of the compilation process (or other areas) as I'm still learning it! :P
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 02:04:43 UTC, Aerolite wrote: On Monday, 25 August 2014 at 01:34:14 UTC, Idan Arye wrote: On Monday, 25 August 2014 at 01:10:32 UTC, Aerolite wrote: -- No syntax modification (unless you want the feature to be optional) If this ever gets into the core language, it absolutely must be optional! Think of the implications of having this as the default and only behavior: * Every overloaded function will have to do a runtime typecheck - this not only causes a usually unnecessary overhead but also has a negative impact on branch prediction. Well, you'd only have to resolve *class* parameters (since obviously literals and structs don't support inheritance). My brain is a little foggy at the moment due to this nice flu I have, but do we even need to do this at run-time? It's not like we can do a Java and use run-time reflection to create new class instances. The closest thing we have to that is Object.factory, but that's all compile-time built and type-safe as far as I'm aware? Or am I being silly? If multi-dispatching is done at compile-time, it can't rely on the object's runtime type - only on the static type of the reference that holds it. This is no different than regular function overloading that we already have. * What if you have multiple overloads that happen to be templated? Now the compiler will have to instantiate them all! Hard to say, although surely there could be some examination of what is and is not necessary to instantiate. This is again making the implementation a tad more complicated, though. That said, if something like @multimethod existed, it would assist in this matter. Are you suggesting the compiler will try to resolve the polymorphism at compile-time, looking at all possible paths that lead to a function call to check all possible runtime values it's object arguments can get? Anyways, I don't think you get just how strong this language's tendency to push features to the library is, so I'd like to point you to this post by the language's creator: http://forum.dlang.org/thread/lt00a9$2uoe$1...@digitalmars.com#post-lt00a9:242uoe:241:40digitalmars.com Heh. Well, that's Walter for you! :P But I definitely understand the push towards the library. I just feel that handling method dispatch, even in compile-time template code, is not something that we should really be writing ourselves. It's like trying to do virtual method calls in C! Virtual methods in C can be done with GObject - though the syntax is awkward. D is so much better than C when it comes to metaprogramming, that the syntax for multimethods wouldn't be awkward(unless you consider anything that's not burned to the core syntax awkward)
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 07:36:22 UTC, Idan Arye wrote: Are you suggesting the compiler will try to resolve the polymorphism at compile-time, looking at all possible paths that lead to a function call to check all possible runtime values it's object arguments can get? I've argued for whole program analysis before and this is another example where it would be useful :-). When you have figured out the worst-case use pattern you can either make one function virtual and then inline the others as a switch or you can create class-ids that can be hashed perfectly to an array of function pointers. However, why do you want multiple dispatch? I cannot think of any application level use scenario where you have two class hierarchies that you have no control over. So I don't really see the value of multiple dispatch in a system level programming language. Perhaps if you want to use D for an application level DSL? What are the use scenarios you guys have experience with where multiple dispatch was indispensable? Ola.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 07:36:22 UTC, Idan Arye wrote: If multi-dispatching is done at compile-time, it can't rely on the object's runtime type - only on the static type of the reference that holds it. This is no different than regular function overloading that we already have. Well any library solution has to do this at compile-time... I assume the implementation would be similar, albeit easier because the compiler would have all the necessary information directly accessible. Are you suggesting the compiler will try to resolve the polymorphism at compile-time, looking at all possible paths that lead to a function call to check all possible runtime values it's object arguments can get? Is that not what would have to be done for a library solution in this case, anyway? Virtual methods in C can be done with GObject - though the syntax is awkward. D is so much better than C when it comes to metaprogramming, that the syntax for multimethods wouldn't be awkward(unless you consider anything that's not burned to the core syntax awkward) Of course, I understand this. What I'm saying is that while it's possible to do virtual method calls in C, the very fact that it had to be implemented so awkwardly meant that a library solution was not ideal. Now in D, the syntax is infinitely better, given. Templates and compile-time code-generation are all really good. But as I said, we have a lot of template bloat issues already. Running 3 foreach-loops at compile-time every time that template-function gets instantiated doesn't seem scalable to me... Having something like this in the compiler, which has all the required information available directly, seems like it'd be the most scalable solution.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 08:45:15 UTC, Ola Fosheim Grøstad wrote: However, why do you want multiple dispatch? I cannot think of any application level use scenario where you have two class hierarchies that you have no control over. So I don't really see the value of multiple dispatch in a system level programming language. Perhaps if you want to use D for an application level DSL? What are the use scenarios you guys have experience with where multiple dispatch was indispensable? Ola. Well there are a few go-to use-cases, the handling of collisions between objects in a game-engine being the most well-known (which requires Double-Dispatch). But it's basically anything that requires the Visitor Pattern, plus extra. At the end of the day, most (if not all) of the major software patterns have come about and are used due to shortfalls in the major languages. D, at least in my experience, tends to solve a lot of these shortfalls, and given that design path, why *wouldn't* we want Multiple Dispatch in the language?
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 10:16:29 UTC, Aerolite wrote: Well there are a few go-to use-cases, the handling of collisions between objects in a game-engine being the most well-known (which requires Double-Dispatch). I think a game engine is better off using a simple table or a more homogeneous engine based on properties rather than classes. You usually can assign a small integer to the relevant properties and use a 2D LUT. D, at least in my experience, tends to solve a lot of these shortfalls, and given that design path, why *wouldn't* we want Multiple Dispatch in the language? I have never had a need for it, but maybe I would have used it if it was available. I think, however, that it would fit better in Go which are going for a more dynamic implementation of interfaces without OOP. I certainly see some value in detaching virtual functions from the record definition. I believe bitC might go in that direction as well.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 10:02:41 UTC, Aerolite wrote: On Monday, 25 August 2014 at 07:36:22 UTC, Idan Arye wrote: If multi-dispatching is done at compile-time, it can't rely on the object's runtime type - only on the static type of the reference that holds it. This is no different than regular function overloading that we already have. Well any library solution has to do this at compile-time... I assume the implementation would be similar, albeit easier because the compiler would have all the necessary information directly accessible. This CAN NOT BE DONE at compile-time, since the compiler doesn't know at compile time the exact subclass of the instance it'll get at runtime. To clarify: I'm not talking about the creation of the multi-method mechanism - which *can* be done at compile-time - I'm talking about invoking that mechanism to determine which overload to call, and this can only be done at runtime. Are you suggesting the compiler will try to resolve the polymorphism at compile-time, looking at all possible paths that lead to a function call to check all possible runtime values it's object arguments can get? Is that not what would have to be done for a library solution in this case, anyway? If you look back, you'll notice this argument(and the two before it) was not against multi-methods at the language level - it was about multi-methods by default. If they are optional, instantiating all the overloads will only happen when it's used, so it won't be that bad. Virtual methods in C can be done with GObject - though the syntax is awkward. D is so much better than C when it comes to metaprogramming, that the syntax for multimethods wouldn't be awkward(unless you consider anything that's not burned to the core syntax awkward) Of course, I understand this. What I'm saying is that while it's possible to do virtual method calls in C, the very fact that it had to be implemented so awkwardly meant that a library solution was not ideal. Now in D, the syntax is infinitely better, given. Templates and compile-time code-generation are all really good. But as I said, we have a lot of template bloat issues already. Running 3 foreach-loops at compile-time every time that template-function gets instantiated doesn't seem scalable to me... Having something like this in the compiler, which has all the required information available directly, seems like it'd be the most scalable solution. No one is trying to claim that a library implementation will be superior to a language-level solution in terms of speed, memory usage, binary size, compilation speed or syntax elegance. Language-level solutions can usually achieve better results in these regards. The problem is that they come with a price: * External tools needs to be modified to work with them. * Alternative implementations need to implement them(even though the frontend is shared, there can always be some complications(plus I think mutli-methods might need some backend modifications as well, thhoguh I'm no expert on that matter)) * Risking regressions - changing the code will never be as orthogonal as changing the data it works on... The point is that the usefulness of multi-methods, and the inconvenience of having as a library solution are not nearly big enough to pay that price.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 17:16:10 UTC, Idan Arye wrote:
* Alternative implementations need to implement them(even
though the frontend is shared, there can always be some
complications(plus I think mutli-methods might need some
backend modifications as well, thhoguh I'm no expert on that
matter))
* Risking regressions - changing the code will never be as
orthogonal as changing the data it works on...
The point is that the usefulness of multi-methods, and the
inconvenience of having as a library solution are not nearly
big enough to pay that price.
If we assume just double-dispatch over class-types and that you
instantiate all functions first. Couldn't you then have this:
eat(virtual BaseBeing v, virtual BaseFood f,float amount){}
eat(virtual Human v, virtual Fruit f,float amount){]
eat(virtual Human v, virtual Stone f,float amount){}
eat(virtual Monster v, virtual Corpse f,float amount){}
eat(virtual Human v, virtual Corpse f,float amount){}
Then extend the typeinfo of classes in the first param with a
minimal typeid and 2D table that lists all combinations that the
custom linker can find based on the mangling?
Or maybe there are some hidden traps…
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 17:28:45 UTC, Ola Fosheim Grøstad wrote: Then extend the typeinfo of classes in the first param with a minimal typeid and 2D table that lists all combinations that the custom linker can find based on the mangling? Maybe it would be better to put in the restriction that all double-dispatch functions with the same name are located in the same file.
Re: Why no multiple-dispatch?
Aerolite: I was surprised to learn yesterday that D does not actually support Multiple-Dispatch, also known as Multimethods. Why is this? Support for this feature is already present in Scala, C# 4.0, Groovy, Clojure, etc... Would it not make sense for D to remain competitive in this regard? I think a hypothetical way for D to become more competitive is to have less OOP ;-) D things like onCmp() for classes are ugly and not easy to write correctly. Perhaps Rust solves (avoids) such problems better, and with much less complexity (but Rust will have other problems of course, like the excessive amount of type inference, because no one designs very good languages). Bye, bearophile
Re: Why no multiple-dispatch?
On Sunday, 24 August 2014 at 23:42:51 UTC, Aerolite wrote: Hey all, I was surprised to learn yesterday that D does not actually support Multiple-Dispatch, also known as Multimethods. Why is this? Support for this feature is already present in Scala, C# 4.0, Groovy, Clojure, etc... Would it not make sense for D to remain competitive in this regard? While I think many of us are aware that problems of the nature that require Multiple-Dispatch can be approached with the Visitor Pattern, there seems to be a general consensus that the Visitor Pattern is pretty cumbersome and boilerplate-heavy, and thus should be avoided. The common response from my searching around seems to be that a template-based, static implementation of Multiple-Dispatch is the go-to solution in D, but considering the existing template-bloat issues we have, I can't help but wonder if language support for this feature might be a better path to go down. Seems like it wouldn't be too difficult to implement, although I've not looked very deeply into dmd's source-code. So what seems to be the situation here? At this point, if something can be implemented in a library rather than in the language, the odds are low that it will be solved in the language. The language is very powerful and already a bit complicated, so usually the response for questions like this is that we'll take advantage of D's existing features to implement the new feature rather than complicating the language further. If you could come up with a very good reason why it had to be in the language, then maybe it would happen, but my guess is that that's not likely to happen. - Jonathan M Davis
Re: Why no multiple-dispatch?
On Sunday, 24 August 2014 at 23:42:51 UTC, Aerolite wrote: So what seems to be the situation here? Hi Aerolite, I've never used multiple dispatch in any language, but from looking at the C# syntax here[1]: ReactSpecialization(me as dynamic, other as dynamic); You should be able to implement multiple dispatch yourself, using the getOverloads trait, using this (or a similar) syntax: dynamic!ReactSpecialization(me, other); [1]: http://blogs.msdn.com/b/shawnhar/archive/2011/04/05/visitor-and-multiple-dispatch-via-c-dynamic.aspx
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:20:26 UTC, Vladimir Panteleev wrote: dynamic!ReactSpecialization(me, other); Here's a very basic implementation: http://dpaste.dzfl.pl/5150ca9c13f4 Idan Arye is also working on functional pattern matching for object references: https://github.com/D-Programming-Language/phobos/pull/1266
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:08:25 UTC, Jonathan M Davis wrote: On Sunday, 24 August 2014 at 23:42:51 UTC, Aerolite wrote: Hey all, I was surprised to learn yesterday that D does not actually support Multiple-Dispatch, also known as Multimethods. Why is this? Support for this feature is already present in Scala, C# 4.0, Groovy, Clojure, etc... Would it not make sense for D to remain competitive in this regard? While I think many of us are aware that problems of the nature that require Multiple-Dispatch can be approached with the Visitor Pattern, there seems to be a general consensus that the Visitor Pattern is pretty cumbersome and boilerplate-heavy, and thus should be avoided. The common response from my searching around seems to be that a template-based, static implementation of Multiple-Dispatch is the go-to solution in D, but considering the existing template-bloat issues we have, I can't help but wonder if language support for this feature might be a better path to go down. Seems like it wouldn't be too difficult to implement, although I've not looked very deeply into dmd's source-code. So what seems to be the situation here? At this point, if something can be implemented in a library rather than in the language, the odds are low that it will be solved in the language. The language is very powerful and already a bit complicated, so usually the response for questions like this is that we'll take advantage of D's existing features to implement the new feature rather than complicating the language further. If you could come up with a very good reason why it had to be in the language, then maybe it would happen, but my guess is that that's not likely to happen. - Jonathan M Davis Speaking of library solutions, I checked with my `castSwitch` PR and it managed to implement single-argument multi-dispatch: https://github.com/D-Programming-Language/phobos/pull/1266#issuecomment-53217374 I'll try to get it to support multiple arguments(shouldn't be that hard) and then all we'll need is a simple wrapper to have our very own library implemented single dispatch. I'm thinking we'll want two versions - a regular templated function like in Vladimir's reply, and also a template mixin that can take a bunch of methods with the same name(or annotated with a UDA) and create a multi-method of them. These wrappers will be another PR, but they can be based on `castSwitch` for it's somewhat-optimized type-comparison implementation.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:36:40 UTC, Vladimir Panteleev wrote: On Monday, 25 August 2014 at 00:20:26 UTC, Vladimir Panteleev wrote: dynamic!ReactSpecialization(me, other); Here's a very basic implementation: http://dpaste.dzfl.pl/5150ca9c13f4 Idan Arye is also working on functional pattern matching for object references: https://github.com/D-Programming-Language/phobos/pull/1266 And here I was struggling to think of a way to efficiently check a tuple against a typetuple, neglecting to recall the rarely used continue-to-label... Thanks! I'm gonna borrow that idea for `castSwitch`.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:08:25 UTC, Jonathan M Davis wrote: At this point, if something can be implemented in a library rather than in the language, the odds are low that it will be solved in the language. The language is very powerful and already a bit complicated, so usually the response for questions like this is that we'll take advantage of D's existing features to implement the new feature rather than complicating the language further. If you could come up with a very good reason why it had to be in the language, then maybe it would happen, but my guess is that that's not likely to happen. - Jonathan M Davis I definitely get that, and it's the right idea given how powerful the language is as it stands. :) With respect to something like Multiple-Dispatch though, this seems like something that, conceptually at least, should really be below the library layer. A library solution in this regard is tantamount to writing virtual method handling as a library solution, which is obviously crazy talk. While I understand the strong desire feature-freeze the language itself (I want the same thing!), I really think this feature is one we can get at the language level without any real structural change (i.e. this doesn't seem like something we'd need any extra syntax for - only a semantic change). So, to weigh up the pros and cons of each implementation strategy: Language implementation: - Pros: -- No syntax modification (unless you want the feature to be optional) -- Extremely low likely-hood of it being a breaking change (no one really writes functions/methods that could take advantage of this, currently) -- Potentially transparent to non-users -- Potentially faster builds (just resolve the actual type for each *class parameter*, instead of doing what would likely be a fair few template expansions) -- Less code bloat (see above) -- Overall, shouldn't be very difficult to implement - Cons: -- Yet another step away from a language feature freeze -- We can emulate this with templates -- Potential for slower builds in large projects that have no need of it (unless it's optional, but that would likely require syntactical changes or a new attribute) -- However small, there's still the possibility that it might break existing code Template / library implementation: - Pros: -- No changes to the language syntax or spec -- No chance of any breaking changes -- No potential build-speed impact for those who don't require it - Cons: -- Template bloat (which, as I understand it, is already a significant issue) -- Potentially large build-speed impact, depending on implementation and project size -- Doesn't scale nicely to run-time dispatch (although I can't think of a situation where this would actually be a problem) -- Conceptually the entirely wrong place for this kind of feature (see virtual method comment above, although this could be considered subjective) Just going off that (unless I'm wrong, or have missed something), a language implementation seems like it would actually be the best option. TL;DR: This isn't a feature that conceptually belongs at the library level, and a language implementation has the potential to be transparent to non-users, lessens code-bloat, and would ideally require only a small semantic change that almost no one would be negatively affected by. Also, looking at things from a very vain, marketing perspective, it'd be a nice little thing to add to the 'Power' section on the homepage! :P
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:20:26 UTC, Vladimir Panteleev wrote: On Sunday, 24 August 2014 at 23:42:51 UTC, Aerolite wrote: So what seems to be the situation here? Hi Aerolite, I've never used multiple dispatch in any language, but from looking at the C# syntax here[1]: ReactSpecialization(me as dynamic, other as dynamic); You should be able to implement multiple dispatch yourself, using the getOverloads trait, using this (or a similar) syntax: dynamic!ReactSpecialization(me, other); [1]: http://blogs.msdn.com/b/shawnhar/archive/2011/04/05/visitor-and-multiple-dispatch-via-c-dynamic.aspx Yep, very true. In fact I was looking at doing something like this for the project I'm working on! :) I just can't help but think that really, such a feature should be at the language level. Naturally though, I do understand the want and need to feature-freeze the language, and if the community feels the effort outweighs the gain in this regard, so be it.
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 00:42:41 UTC, Idan Arye wrote: Speaking of library solutions, I checked with my `castSwitch` PR and it managed to implement single-argument multi-dispatch: https://github.com/D-Programming-Language/phobos/pull/1266#issuecomment-53217374 I'll try to get it to support multiple arguments(shouldn't be that hard) and then all we'll need is a simple wrapper to have our very own library implemented single dispatch. I'm thinking we'll want two versions - a regular templated function like in Vladimir's reply, and also a template mixin that can take a bunch of methods with the same name(or annotated with a UDA) and create a multi-method of them. These wrappers will be another PR, but they can be based on `castSwitch` for it's somewhat-optimized type-comparison implementation. Damn, that is really nice! I was wondering when we'd see something like this make its way into the standard library. :)
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 01:10:32 UTC, Aerolite wrote: -- No syntax modification (unless you want the feature to be optional) If this ever gets into the core language, it absolutely must be optional! Think of the implications of having this as the default and only behavior: * Every overloaded function will have to do a runtime typecheck - this not only causes a usually unnecessary overhead but also has a negative impact on branch prediction. * No way to reuse the overload that accepts an object of the parent class inside the implementation of the overload that accepts an object of the child class. * What if you have multiple overloads that happen to be templated? Now the compiler will have to instantiate them all! Anyways, I don't think you get just how strong this language's tendency to push features to the library is, so I'd like to point you to this post by the language's creator: http://forum.dlang.org/thread/lt00a9$2uoe$1...@digitalmars.com#post-lt00a9:242uoe:241:40digitalmars.com
Re: Why no multiple-dispatch?
On Monday, 25 August 2014 at 01:34:14 UTC, Idan Arye wrote: On Monday, 25 August 2014 at 01:10:32 UTC, Aerolite wrote: -- No syntax modification (unless you want the feature to be optional) If this ever gets into the core language, it absolutely must be optional! Think of the implications of having this as the default and only behavior: * Every overloaded function will have to do a runtime typecheck - this not only causes a usually unnecessary overhead but also has a negative impact on branch prediction. Well, you'd only have to resolve *class* parameters (since obviously literals and structs don't support inheritance). My brain is a little foggy at the moment due to this nice flu I have, but do we even need to do this at run-time? It's not like we can do a Java and use run-time reflection to create new class instances. The closest thing we have to that is Object.factory, but that's all compile-time built and type-safe as far as I'm aware? Or am I being silly? * No way to reuse the overload that accepts an object of the parent class inside the implementation of the overload that accepts an object of the child class. Ok, yep, I didn't consider this. Fair point. But surely an attribute such as @nomulti could prevent this problem? Admittedly though, given this problem, the scale of potential breaking changes would necessitate the opposite - an @multimethod attribute, for instance (much like you suggested in your earlier reply). Clojure, it seems[1], explicitly denotes multimethods (with defmulti), so it seems as though an @multimethod might be the way to go. * What if you have multiple overloads that happen to be templated? Now the compiler will have to instantiate them all! Hard to say, although surely there could be some examination of what is and is not necessary to instantiate. This is again making the implementation a tad more complicated, though. That said, if something like @multimethod existed, it would assist in this matter. Anyways, I don't think you get just how strong this language's tendency to push features to the library is, so I'd like to point you to this post by the language's creator: http://forum.dlang.org/thread/lt00a9$2uoe$1...@digitalmars.com#post-lt00a9:242uoe:241:40digitalmars.com Heh. Well, that's Walter for you! :P But I definitely understand the push towards the library. I just feel that handling method dispatch, even in compile-time template code, is not something that we should really be writing ourselves. It's like trying to do virtual method calls in C! [1]: http://clojure.org/multimethods
Re: Why no multiple-dispatch?
On Mon, 25 Aug 2014 01:14:19 + Aerolite via Digitalmars-d-learn digitalmars-d-learn@puremagic.com wrote: I just can't help but think that really, such a feature should be at the language level. this is the first topic about multiple-dispatch in at least... eh... 6 months (maybe more). chances that it will be included in compiler are less than zero. signature.asc Description: PGP signature
