View mode: basic / threaded / horizontal-split · Log in · Help
February 08, 2005
Multimethod library - mml.d
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
Re: Multimethod library - mml.d
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
Re: Multimethod library - mml.d
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
Re: Multimethod library - mml.d
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
Re: Multimethod library - mml.d
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
Re: Multimethod library - mml.d
>
>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
Re: Multimethod library - mml.d
> 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
Re: Multimethod library - mml.d
>
> 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
Re: Multimethod library - mml.d
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
Re: Multimethod library - mml.d
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