www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Multimethod library - mml.d

reply nail <nail_member pathlink.com> writes:
I know some time ago 'pragma' wrote multimethods lib, I used it but unfortunatly
found that it has bugs, has no feature to implicitly choose the best suitable
signature and not always was typesafe.

So I wrote my own, It supports unary and binary multimethods, and has no
mentioned drawbacks.

P.S: And nevertheless, I would very very happy if D begun to support mmethods
natively.

nail-mail <at> mail <dot> ru
Feb 08 2005
next sibling parent "Craig Black" <cblack ara.com> writes:
I agree, multimethods are a very useful and powerful language feature.  They 
should be added to D.

"nail" <nail_member pathlink.com> wrote in message 
news:cuapgb$2ubv$1 digitaldaemon.com...
I know some time ago 'pragma' wrote multimethods lib, I used it but 
unfortunatly
 found that it has bugs, has no feature to implicitly choose the best 
 suitable
 signature and not always was typesafe.

 So I wrote my own, It supports unary and binary multimethods, and has no
 mentioned drawbacks.

 P.S: And nevertheless, I would very very happy if D begun to support 
 mmethods
 natively.

 nail-mail <at> mail <dot> ru
 

Feb 08 2005
prev sibling next sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
I have no experience with using multimethods. Looking at your
implementation, though, I have the feeling that this is an even more
complex issue than multiple inheritance and I doubt whether it is a good
idea to move it into the language.

Multimethods are not very efficient by principle. Even a native
implementation in the compiler will not change that. If there are other
details why you think a native implementation could do better than a
library-based one, it might be an idea to identify these points and try to
find ways to expand the language such that library-based multimethods can
be implemented better.




nail wrote:

 I know some time ago 'pragma' wrote multimethods lib, I used it but
 unfortunatly found that it has bugs, has no feature to implicitly choose
 the best suitable signature and not always was typesafe.
 
 So I wrote my own, It supports unary and binary multimethods, and has no
 mentioned drawbacks.
 
 P.S: And nevertheless, I would very very happy if D begun to support
 mmethods natively.
 
 nail-mail <at> mail <dot> ru

Feb 09 2005
next sibling parent nail <nail_member pathlink.com> writes:
In article <cucij7$1sa3$1 digitaldaemon.com>, Norbert Nemec says...
I have no experience with using multimethods. Looking at your
implementation, though, I have the feeling that this is an even more
complex issue than multiple inheritance and I doubt whether it is a good
idea to move it into the language.

Multimethods are not very efficient by principle. Even a native
implementation in the compiler will not change that. If there are other
details why you think a native implementation could do better than a
library-based one, it might be an idea to identify these points and try to
find ways to expand the language such that library-based multimethods can
be implemented better.

First - dispatch table will be built at compile time. Second - compiler can ignore type checking in the places where it is obvious, i.e. cast(XXX) is similar dynamic_cast in C++, but there are some often called places in my implementation where I'm sure that my Object reference is realy XXX subclass reference, that places can be rewrited to static_cast. Third - compiler can automaticly index classes at compile-time. This topic was rised some time ago, but Walter refuse flatly buitin multimethods as I remember. nail-mail<at>mail<dot>ru
Feb 09 2005
prev sibling parent reply "Craig Black" <cblack ara.com> writes:
 Multimethods are not very efficient by principle. Even a native
 implementation in the compiler will not change that.

You have no experience using multimethods, so how can you make such a rash statement about them? I DO have experience with them and they are very efficient if implemented correctly. They certainly can outperform the alternative, double dispatch. There are efficient ways to ensure a low memory footprint and an O(1) invokation. There has been much academic consideration of multimethods, but the average programmer doesn't know that they exist, let alone how powerful they are, so they are neglected. This is true of many programming paradigms. -Craig "Norbert Nemec" <Norbert Nemec-online.de> wrote in message news:cucij7$1sa3$1 digitaldaemon.com...
I have no experience with using multimethods. Looking at your
 implementation, though, I have the feeling that this is an even more
 complex issue than multiple inheritance and I doubt whether it is a good
 idea to move it into the language.

 details why you think a native implementation could do better than a
 library-based one, it might be an idea to identify these points and try to
 find ways to expand the language such that library-based multimethods can
 be implemented better.




 nail wrote:

 I know some time ago 'pragma' wrote multimethods lib, I used it but
 unfortunatly found that it has bugs, has no feature to implicitly choose
 the best suitable signature and not always was typesafe.

 So I wrote my own, It supports unary and binary multimethods, and has no
 mentioned drawbacks.

 P.S: And nevertheless, I would very very happy if D begun to support
 mmethods natively.

 nail-mail <at> mail <dot> ru


Feb 09 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Craig Black wrote:

 Multimethods are not very efficient by principle. Even a native
 implementation in the compiler will not change that.

You have no experience using multimethods, so how can you make such a rash statement about them? I DO have experience with them and they are very efficient if implemented correctly. They certainly can outperform the alternative, double dispatch. There are efficient ways to ensure a low memory footprint and an O(1) invokation.

OK, sorry - I have rather strict criteria when talking about 'efficient'. Of course, efficiency always depends on the kind of problem you want to solve. If the problem inherently demands multi-dispatch, then it is certainly more efficient to have it built into the compiler than to do it 'by hand'. What I meant, is that you generally need to do some kind of a lookup at runtime. You say that this can be done O(1) - if that is indeed possible, it might change my view of the issue. As far as I can see, multi-dispatch will always need some lookup in a table. You may be able to implement this by using a btree or a hash-table, but neither of them is strictly O(1). Single-dispatch can simply be done by dereferencing a single pointer. This is still less efficient than static calls (especially on modern architectures, where it severely breaks branch prediction) but it is strictly O(1) with next to no overhead. For multi-dispatch, I cannot see any way to do that. If you have any pointers about it, I would personally be very interested. As for the design of D: it clearly is a difficult decision which features a language should support. Every programmer has some favorite programming style that depends on certain features in the language. Supporting everything is impossible and would lead to a cluttered language. Whether multimethods are important enough to include them is a matter of investigation. In any case, I would really want to see some real-world example that inherently depends on multimethods.
 There has been much academic 
 consideration of multimethods, but the average programmer doesn't know
 that
 they exist, let alone how powerful they are, so they are neglected.  This
 is true of many programming paradigms.

I can only fully support this statement.
Feb 10 2005
next sibling parent nail <nail_member pathlink.com> writes:
In article <cuf58k$1b8b$1 digitaldaemon.com>, Norbert Nemec says...
Craig Black wrote:

 Multimethods are not very efficient by principle. Even a native
 implementation in the compiler will not change that.

You have no experience using multimethods, so how can you make such a rash statement about them? I DO have experience with them and they are very efficient if implemented correctly. They certainly can outperform the alternative, double dispatch. There are efficient ways to ensure a low memory footprint and an O(1) invokation.

OK, sorry - I have rather strict criteria when talking about 'efficient'. Of course, efficiency always depends on the kind of problem you want to solve. If the problem inherently demands multi-dispatch, then it is certainly more efficient to have it built into the compiler than to do it 'by hand'.

Also, the bonus is elegant simple syntax for mm defenition.
What I meant, is that you generally need to do some kind of a lookup at
runtime. You say that this can be done O(1) - if that is indeed possible,
it might change my view of the issue. As far as I can see, multi-dispatch
will always need some lookup in a table. You may be able to implement this
by using a btree or a hash-table, but neither of them is strictly O(1).

Single-dispatch can simply be done by dereferencing a single pointer. This
is still less efficient than static calls (especially on modern
architectures, where it severely breaks branch prediction) but it is
strictly O(1) with next to no overhead.

For multi-dispatch, I cannot see any way to do that. If you have any
pointers about it, I would personally be very interested.

The best method for multi-dispatching I seen is multi-row displacement(matching). My library to some extent use ideas from it, but I couldn't implement it completely, 'cause it must be done within compiler. Read more at http://www.ifs.uni-linz.ac.at/~ecoop/cd/papers/1628/16280304.pdf. Alghorithm implemented on compiler side make binary multimethod call equivalent by time penalty to two virtual calls, triary to 4 virtual calls, n-ary to 2^(n-1) virtual calls, not bad.
As for the design of D: it clearly is a difficult decision which features a
language should support. Every programmer has some favorite programming
style that depends on certain features in the language. Supporting
everything is impossible and would lead to a cluttered language. Whether
multimethods are important enough to include them is a matter of
investigation. In any case, I would really want to see some real-world
example that inherently depends on multimethods. 

I'm work in gamedevelopment industry and here there are a LOT of examples. Consider collision-detection: how beautiful will be if to compute collision point between two physical primitives using compact syntax of multimethods, not using annoying visitor pattern. Or another example: class RenderInstruction {} abstract class RenderSystem { void apply(RenderInstruction ins); } class Mesh : RenderInstruction {...} class MeshVB : RenderInstruction {...} class MeshIB : RenderInstruction {...} class D3DRenderSystem : RenderSystem { void apply(RenderInstruction ins); void apply(Mesh ins); void apply(MeshVB ins); void apply(MeshIB ins); } class NURBSSurface : RenderInstruction {...} class SomeNURBSRenderSystem : RenderSystem { void apply(RenderInstruction ins); void apply(NURBSSurface ins); } class SomeAnotherWayToDescribeShape : RenderInstruction {...} class SomeNotYetExistentRenderSystem : RenderSystem { void apply(RenderInstruction ins); void apply(SomeAnotherWayToDescribeShape ins); } I can store reference to RenderSystem wich actualy can be any and call apply with any RenderInstruction derived argument. Concrete render system will self make decision what to do whith this instruction. This architecture allows to add new render systems (even with absolutely another paradigm) without RenderSystem class changes. Of course this exaples can be solved without multimethods, but any problem can be solved without OOP at all. So the question is about readability and code maintenance.
 There has been much academic 
 consideration of multimethods, but the average programmer doesn't know
 that
 they exist, let alone how powerful they are, so they are neglected.  This
 is true of many programming paradigms.

I can only fully support this statement.

Victor Nakoryakov nail-mail<at>mail<dot>ru
Feb 10 2005
prev sibling parent "Craig Black" <cblack ara.com> writes:
 For multi-dispatch, I cannot see any way to do that. If you have any
 pointers about it, I would personally be very interested.

I am currently developing a simulation engine for DoD modeling and simulations. The simulation engine uses a template for two dimensional multimethods. The multimethods are used to describe relationships between different kinds of objects in the simulation. It requires that each type be enumerated. This is difficult to do using C++ RTTI, so I use my own type system. Once each type is enumerated, O(1) algorithms are possible. The simplest way to do this is with an N-Dimensional array of methods. Since each type's enumerated value will be its index into the array. Each multimethod must have its own array. The number of dimensions will correspond to the number of virtual parameters. It is easy to see why this method is so fast. It is simply indexing a lookup table. The problem is that these arrays can become considerably large, especially as the number of virtual parameters increases. For this reason, my currently implementation is limited to two dimensions. However, there are algorithms that compress the lookup tables and still retain the O(1) performance. The drawback is that this approach is considerably more complex and difficult to implement.
 As for the design of D: it clearly is a difficult decision which features 
 a
 language should support. Every programmer has some favorite programming
 style that depends on certain features in the language. Supporting
 everything is impossible and would lead to a cluttered language. Whether
 multimethods are important enough to include them is a matter of
 investigation. In any case, I would really want to see some real-world
 example that inherently depends on multimethods.

Well my vote is to include multimethods natively. I suppose that a first step to providing high-performance multimethods in D is providing enumeration values for the types. They would have to be enumerated from each base class. Thus if B inherits A and C inherits B, C would have two enumerations: one with base A and another with base B. (If I'm confusing you just let me know and I will expound some more.) This would allow for high-performance multimethod libraries to be written. The next step would be to add the keywords and syntax sugar that replaces those libraries. -Craig
Feb 10 2005
prev sibling parent reply Mark Junker <mjscod gmx.de> writes:
nail schrieb:
 I know some time ago 'pragma' wrote multimethods lib, I used it but
unfortunatly
 found that it has bugs, has no feature to implicitly choose the best suitable
 signature and not always was typesafe.

What are multimethods? Regards, Mark
Feb 09 2005
next sibling parent nail <nail_member pathlink.com> writes:
What are multimethods?

Realization of so called late type binding. So if you have class A {} class B : A {} void foo(A u, A v) {...}; void foo(B u, B v) {...}; void main() { A b = new B(); foo(b, b); // foo(A, A) will be called } Multimethods is mechanism to redirect call to more suitable foo(B, B). To learn more google it. nail-mail<at>mail<dot>ru
Feb 09 2005
prev sibling parent "Craig Black" <cblack ara.com> writes:
 What are multimethods?

Virtual methods could be considered to be a special case of multimethod. A virtual method is similar to a one-dimensional multimethod where "this" pointer is the virtual parameter. Multimethods are essentially methods with one or more virtual parameters. However, unlike virtual methods multimethods are not members of a particular class. Instead, they define relationships between classes. I like to use the term "object-relational paradigm" to describe multimethods. Here is an example where multimethods describe the relationship between simple shapes. This syntax uses the virtual keyword to denote a virtual parameter. class Shape { ... } class Triangle : Shape { ... } class Rectangle : Shape { ... } class Circle : Shape { ... } bool overlap(virtual Shape *a, virtual Shape *b) = 0; bool overlap(virtual Triangle *a, virtual Rectangle *b) { ... } bool overlap(virtual Rectangle *a, virtual Circle *b) { ... } bool overlap(virtual Triangle *a, virtual Circle *b) { ... } Then if you have two shape pointers, just invoke the overlap method and the appropriate overload will be called. Shape *a = new Triangle(...); Shape *b = new Circle(...); overlap(a, b); -Craig
Feb 09 2005