Prev: Newbie help with OOD/ADO.NET with C#
Next: Implementation Of a Football League Database
From: Daniel Pitts on 27 Oct 2007 13:23
Stefan Ram wrote:
> What is the most difficult aspect of the implementation of
> multimethods?
>
> Given a call
>
> f( 1, 2 )
>
> and a single method
>
> f( int, int )
>
> things seems to be simple.
>
> But what if each �int� is a �number�, and there is the call
>
> f( 1, 2 )
>
> and the declarations
>
> f( int, number )
> f( number, int )
>
> Now the call is ambigous.
>
> So, an implementation needs to find all possible declarations,
> find the subset of all declarations matching the call, then
> use some metric to find a unique best match or issue an error,
> if there is no such unique best match.
>
> Is this the most difficult part when implementing dynamic
> multimethod dispatch?
>
> Is there a standard algorithm one can use to resolve a call
>
> f( arg[0], arg[1], ... arg[n-1] )
>
> , given a hierarchy of types and a set of definitions for �f�?
>
> I ask this in the context of the thread �Creating a "toy"
> OO/AO language...� because if I ever would implement a toy oo
> language, I believe its core would be such a dynamic dispatch.
>
I would think the standard approach would be to iterate in order all of
the named matches. If the current named match is more specific, put it
into an accumulator. Once you're finished, if the accumulator is
empty/null, then handle that appropriately, otherwise dispatch to where
the accumulator points.

If you wish to handle ambiguity as an error, you could also have an
ambiguity flag that you reset when you set accumulator, and you set if
the current named match is the same specificity as the accumulator. The
final state of that flag would tell you whether there was an ambiguous
match or not.

As for deciding on specificity, I would probably determine a number for
each parameter that expresses how specific it is to the argument, based
on hierarchy or other conditions. The higher the combination of these
numbers, the more specific the call.

Some languages might be defined that ambiguities are resolved in a
left-to-right manor. So, in your example f(int, number) would win out,
since the left-most parameter is more specific.

although, what of the case:

f(int, number, number)
f(number, int, number)
f(number, int, int)

f(1, 2, 3)

By using the left-to-right rule alone, f(i,n,n) would be executed. using
the method I outlined above, f(n,i,i) would be executed. It becomes
even more complicated. Say you have a (magic) type prime, which is a
specialization of int.

f(number, int)
f(int, number)
f(number, prime)

f(1,3) should pick f(n,p). where f(1,4) *could* pick any of them.
Using the left-to-right, it would pick f(i,n), using my method, it would
pick f(n,i) since it was the first declared.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: S Perryman on 27 Oct 2007 13:32
Stefan Ram wrote:

> What is the most difficult aspect of the implementation of
> multimethods?

[ examples snipped ... ]

> So, an implementation needs to find all possible declarations,
> find the subset of all declarations matching the call, then
> use some metric to find a unique best match or issue an error,
> if there is no such unique best match.

> Is this the most difficult part when implementing dynamic
> multimethod dispatch?

> Is there a standard algorithm one can use to resolve a call

> f( arg[0], arg[1], ... arg[n-1] )

> , given a hierarchy of types and a set of definitions for �f�?

> I ask this in the context of the thread �Creating a "toy"
> OO/AO language...� because if I ever would implement a toy oo
> language, I believe its core would be such a dynamic dispatch.

AFAIK, the algorithm used by CLOS is widely documented over the years.
I also recall Craig Chambers' group (Cecil etc) also have papers in
OOPSLA on multiple dispatch.

So they may be good first points to check for good description of
underlying algorithms.


Regards,
Steven Perryman
From: Dmitry A. Kazakov on 27 Oct 2007 15:07
On 27 Oct 2007 16:20:47 GMT, Stefan Ram wrote:

> What is the most difficult aspect of the implementation of
> multimethods?

[Should be posted to comp.compilers, I guess (:-))]

> Given a call
>
> f( 1, 2 )
>
> and a single method
>
> f( int, int )
>
> things seems to be simple.
>
> But what if each �int� is a �number�, and there is the call
>
> f( 1, 2 )

(this is not dispatch, it is types conversion. See below)

> and the declarations
>
> f( int, number )
> f( number, int )
>
> Now the call is ambigous.
>
> So, an implementation needs to find all possible declarations,
> find the subset of all declarations matching the call, then
> use some metric to find a unique best match or issue an error,
> if there is no such unique best match.

If the above is dispatching and not overloading then there is no need to
search for anything. There is a sufficient difference between overloading
and overriding with that respect. Multiple dispatch works as follows. f has
a dispatching table associated with it. This table is a 3D array (cube),
because f has 3 *covariant* parameters (result is counted too). The array
indices are types. For each type which f is a method of, there is an index
value in the table. So you take the result type, the types of arguments,
hash them to dense index in the table and then index the table. Here you
are. [Whether dispatch happens at compile or run-time plays no role]

> Is this the most difficult part when implementing dynamic
> multimethod dispatch?

No, it is an easy part. This works same way for full multiple dispatch
(when types build unrelated hierarchies).

The hard problem with MD is ensuring that the dispatch never fails, that is
that the table of f is always filled. For multi-methods there is a way to
do it because there is only one derivation point where you have to add new
planes to the table. At this point you can check if the programmer has
defined all possible combinations of parameters or else they could be
constructed by the compiler. For instance when int gets derived from number
the programmer shall define:

f : int, number -> int
f : number, int -> int
f : int, int -> int

This number can be reduced if f is anti-symmetric, commutative, group
complement etc, or contravariant in some parameters. In the former case,
the compiler can deduce some combinations from others. In the latter case
the table has a lesser dimension.

Full dispatch is way harder, because one type can be derived from in one
context another in another which might be absolutely unrelated, even
compiled separately.

> Is there a standard algorithm one can use to resolve a call
>
> f( arg[0], arg[1], ... arg[n-1] )
>
> , given a hierarchy of types and a set of definitions for �f�?
>
> I ask this in the context of the thread �Creating a "toy"
> OO/AO language...� because if I ever would implement a toy oo
> language, I believe its core would be such a dynamic dispatch.

Yes. Ideally there should be no overloading except than for polymorphic
(contravariant) parameters. But it is not clear how to achieve that.

As for overloading and types conversions, as in your example with literals,
which are of some universal type convertible to either int or number, or,
equivalently, overloaded parameterless functions. I.e.

Variant A (conversions):

1 : universal_number;
2 : universal_number;
....
conversion : universal_number -> number
conversion : universal_number -> int (generated from number -> int)

Variant B (overloaded literals):

1 : -> number
2 : -> number
....
1 : -> int
2 : -> int
....

(No matter whether interpretation you choose for literals)

The method selected shall have a parameters profile which types dominate
all other profiles in all parameters (again including result). That is:

exist S=(S1,..., SN) forall T=(T1,..,TN) forall i, Si :> Ti

Then you take S. When there are many incomparable alternatives, then you
filter out all dominated ones and present the rest as a list of ambiguity
in the error message generated. This is not that difficult. A reasonable
error messages in complex ambiguous expressions is hard, especially when
the subroutines can be overloaded in their results. In that case simple
bottom-up matching does not work.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
 | 
Pages: 1
Prev: Newbie help with OOD/ADO.NET with C#
Next: Implementation Of a Football League Database