February 08, 2005
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
February 09, 2005
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
> 


February 09, 2005
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

February 09, 2005
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
February 09, 2005
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
February 09, 2005
>
>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
February 09, 2005
> 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.
>
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
> 


February 09, 2005
>
> 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




February 10, 2005
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.

February 10, 2005
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
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home