Multiple dispatch

Multiple dispatch

[Yannick Duchêne (Hibou57)]

Hi peoples, Hi Ada world,

In your opinion, what is the best known design pattern for multiple  
dispatch in Ada ? (as far as I know, there is no way to get multiple  
dispatching in Ada the direct way).

As with any design matters, an answer to this question will probably  
depends on the concrete case, so here is an overview of the concrete  
matter: it deals with serialization.

An example: you have multiple object of different types rooted at a some  
root type; you also have multiple containers of different types too, also  
rooted at another root type. Now, say objects are all to have a  
serialization methods, a different one for each type. This could be  
dispatching, OK, except that you have the requirement these objects are  
also to be serialized a way or another, depending on the container which  
will hold the serialized datas. Add to this that you can't change this,  
because this is part of some standard or any other kind of things already  
fixed.

Say Object_1_Type, to be serialized to Container_1_Type, will use  
Method_1_1
…  Object_1_Type, to be serialized to Container_2_Type, will use Method_1_2
… Object_2_Type, to be serialized to Container_1_Type, will use Method_2_1
… Object_2_Type, to be serialized to Container_2_Type, will use Method_2_2
… and so on

A quick solution could be :

1) Define two methods for object : one would be Serialize_To_Container_1  
and Serialize_To_Container_2.
2) Then, a master Serialize method could get two parameters, one object  
and one container,
3) This method would discriminate on container's type, so would invoke  
either Serialize_To_Container_1 or Serialize_To_Container_1 depending on  
the container's type, and this call would be dispatching on object's type.

OK, but why not the opposite ? And then, where the master dispatcher  
should reside ? In the module defining objects ? In the module defining  
containers ? In a third module ? Who should own the knowledge about  
serialization ? I feel it's natural to say, Objects, of course; but this  
also requires dispatching on container's types… Still seems natural the  
serialization should be driven by objects, at least because objects to be  
serialized may hold private stuff, or else are the only ones to know which  
of their properties are to be stored and which are to be derived from the  
ones stored.

Alternatively, may be a seed of a solution : the containers would define  
some serialization primitives for some basic property types objects are  
made of, and objects could request the container to provide these method,  
via dispatching calls.

This would end into…

Steps for the serialization of an object to a container :

1) Determine the object serialization method to use depending on its type.
2) The object is composed of properties of types Property_1_Type,  
Property_2_Type, and so on.
3) The containers provides methods Serialize_Property_Type_1,  
Serialize_Property_Type_2, and so on.
4) The object's serialization method invokes these container's methods,  
via dispatching calls.

Seems OK ? Any one see a better design pattern ? Do someone see something  
wrong with this repartitions of knowledge and responsibilities between  
modules ?

-- 
“Syntactic sugar causes cancer of the semi-colons.”  [Epigrams on  
Programming — Alan J. — P. Yale University]
“Structured Programming supports the law of the excluded muddle.” [Idem]
“c++; /* this makes c bigger but returns the old value */” [Anonymous]

Re: Multiple dispatch

[Dmitry A. Kazakov]

On Sat, 11 Jun 2011 12:13:21 +0200, Yannick Duchêne (Hibou57) wrote:

> This would end into…
> 
> Steps for the serialization of an object to a container :
> 
> 1) Determine the object serialization method to use depending on its type.
> 2) The object is composed of properties of types Property_1_Type,  
> Property_2_Type, and so on.
> 3) The containers provides methods Serialize_Property_Type_1,  
> Serialize_Property_Type_2, and so on.
> 4) The object's serialization method invokes these container's methods,  
> via dispatching calls.
> 
> Seems OK ?

Yes, that looks like the usual pattern for protocols and similar stuff,
when objects do not depend on the containers. The opposite case is
represented by drivers, when objects are maintained by the driver, you
might first dispatch on the driver type and then on the type of its
objects.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Multiple dispatch

[Yannick Duchêne (Hibou57)]

Le Sat, 11 Jun 2011 13:52:05 +0200, Dmitry A. Kazakov  
<mailbox@dmitry-kazakov.de> a écrit:
> Yes, that looks like the usual pattern for protocols and similar stuff,
> when objects do not depend on the container.
What kind of dependencies do you have in mind ? Object existence depending  
on the container ? Or object's properties depending on the container ?

I was trying to figure many cases (in an attempt to invalidate the design,  
and fail with that, to prove this is the good design); among others, this  
one : if the container know enough about the object types because it is  
fully dedicated to these object types, one may argue the container could  
also serialize objects on its own side. However, this would imply a switch  
on object types, which is not clean, due to an implicit though behind  
this: dispatching calls and switch are somewhat similar things, however  
with an important difference, which is that with dispatching calls, the  
corresponding switch is always owned by (under the responsibility of) the  
type on which the switch is to be done, while with the switch approach,  
anything could do a switch. The former more enforce structuring.

Another approach, with a more concrete-like example (which is not the one  
I am actually dealing with… I wont tell more, as I prefer to keep this  
talk as much abstract as possible) : you have two types, one for a  
character string and one for an array of numbers, and two containers. Say  
one container is a file and the other is anything else you wish (could be  
a serial communication wire plugged to some device, as an example). Let  
say there are two way to serialize each type. For the string, there is a  
C-like serialization, that is, all characters first, with a final Unicode  
U+0000, and a Pascal-like serialization, with a length first and then the  
all characters. Let say there is something similar with the array of  
numbers : it could either be serialized with a kind of null terminator,  
and the other way, starting with its length and then its numbers. Say each  
of the two container expect one or the other serialization.

This case seems more ambiguous at first sight, at it could seems as much  
easy and clean to dispatch on either the container or the object. Eh, but  
only one container type know about what null terminators are and only one  
know about what lengths are. Now let say none of the array of numbers or  
the character strings, know about what null terminators are. With such a  
case, wouldn't it be better to dispatch first on the container ? Is that  
the kind of dependency you though about ?


> The opposite case is
> represented by drivers, when objects are maintained by the driver, you
> might first dispatch on the driver type and then on the type of its
> objects.
I tried to figure out this one, but couldn't. Could you tell about a tiny  
and short example ?


-- 
“Syntactic sugar causes cancer of the semi-colons.”  [Epigrams on  
Programming — Alan J. — P. Yale University]
“Structured Programming supports the law of the excluded muddle.” [Idem]
“c++; /* this makes c bigger but returns the old value */” [Anonymous]

Re: Multiple dispatch

[Dmitry A. Kazakov]

On Sat, 11 Jun 2011 15:19:00 +0200, Yannick Duchêne (Hibou57) wrote:

> Le Sat, 11 Jun 2011 13:52:05 +0200, Dmitry A. Kazakov  
> <mailbox@dmitry-kazakov.de> a écrit:
>> Yes, that looks like the usual pattern for protocols and similar stuff,
>> when objects do not depend on the container.
> What kind of dependencies do you have in mind ? Object existence depending  
> on the container ? Or object's properties depending on the container ?

Any dependencies (correlations). Imagine the dispatching table. It is a 2D
matrix for double dispatch. In full dispatch the table is irregular, i.e.
there is no preferred way to index this matrix either by columns or by
rows.

In special cases there can be similarities between rows or between columns,
in that case you dispatch across the most varying dimension leaving the
least variance to the secondary dispatch.

> Another approach, with a more concrete-like example (which is not the one  
> I am actually dealing with… I wont tell more, as I prefer to keep this  
> talk as much abstract as possible) : you have two types, one for a  
> character string and one for an array of numbers, and two containers. Say  
> one container is a file and the other is anything else you wish (could be  
> a serial communication wire plugged to some device, as an example). Let  
> say there are two way to serialize each type. For the string, there is a  
> C-like serialization, that is, all characters first, with a final Unicode  
> U+0000, and a Pascal-like serialization, with a length first and then the  
> all characters. Let say there is something similar with the array of  
> numbers : it could either be serialized with a kind of null terminator,  
> and the other way, starting with its length and then its numbers. Say each  
> of the two container expect one or the other serialization.
> 
> This case seems more ambiguous at first sight, at it could seems as much  
> easy and clean to dispatch on either the container or the object. Eh, but  
> only one container type know about what null terminators are and only one  
> know about what lengths are. Now let say none of the array of numbers or  
> the character strings, know about what null terminators are. With such a  
> case, wouldn't it be better to dispatch first on the container ? Is that  
> the kind of dependency you though about ?

Yes, that is full dispatch, which is not decomposable. Returning to the
example with the 2D matrix of dispatch D, when it was the representation:

   D (i, j) = a (i) * b (j)

you can decompose full dispatch into cascaded dispatch (first a(i), then
b(j)).

>> The opposite case is
>> represented by drivers, when objects are maintained by the driver, you
>> might first dispatch on the driver type and then on the type of its
>> objects.
> I tried to figure out this one, but couldn't. Could you tell about a tiny  
> and short example ?

Typically driver has a task processing I/O requests. Queueing the request
naturally goes to the driver, so you dispatch first on the driver object.
Once you dequeue the request, you dispatch on the object handled by the
driver, e.g. write analogue 24-bit output etc.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Multiple dispatch

[Emmanuel Briot]

I have prepared recently a "gem" on the Visitor design pattern (see
the Gang of Four book on design patterns), that will be published this
month on the Adacore web site. I think you might find the pattern
interesting if you do not know about it yet, so looking at the book
might be of interest to you.

Emmanuel

Re: Multiple dispatch

[Dmitry A. Kazakov]

On Sat, 11 Jun 2011 11:42:25 -0700 (PDT), Emmanuel Briot wrote:

> I have prepared recently a "gem" on the Visitor design pattern (see
> the Gang of Four book on design patterns), that will be published this
> month on the Adacore web site. I think you might find the pattern
> interesting if you do not know about it yet, so looking at the book
> might be of interest to you.

Thanks!

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Multiple dispatch

[Natasha Kerensikova]

Hello,

On 2011-06-11, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On Sat, 11 Jun 2011 15:19:00 +0200, Yannick Duchêne (Hibou57) wrote:
>
>> Le Sat, 11 Jun 2011 13:52:05 +0200, Dmitry A. Kazakov  
>> <mailbox@dmitry-kazakov.de> a écrit:
>>> Yes, that looks like the usual pattern for protocols and similar stuff,
>>> when objects do not depend on the container.
>> What kind of dependencies do you have in mind ? Object existence depending  
>> on the container ? Or object's properties depending on the container ?
>
> Any dependencies (correlations). Imagine the dispatching table. It is a 2D
> matrix for double dispatch. In full dispatch the table is irregular, i.e.
> there is no preferred way to index this matrix either by columns or by
> rows.

I remember having faced that kind of issues with C through dynamic
linker introspection : there is a function that returns a function
pointer corresponding to the given symbol name. I crafted the symbol
name using an operation like
"dispatch_prefix_" & First_Tag & "_" & Second_Tag

This makes the dispatch table completely isotropic and allows to
implement any element of the matrix in any compilation unit (as long as
it is linked (statically or dynamically) to the final binary). I found
this feature very nice when the "glue" between the row type and the
column type does not obviously belong to either type (in the original
example, that would be a very special representation of a given general
data type in a given general container).

I guess the introspection of object files is too low level for Ada, and
even importing libdl from C wouldn't be of much use because of the
name-mangling performed by Ada compiler (or you have to use C symbol
names and give up namespaces, case-insensitivity and other cool Ada
features).

I know other high-level languages do have introspection mechanisms, but
I haven't seen anything like that in Ada. Have I missed them?


Natasha

Re: Multiple dispatch

[Yannick Duchêne (Hibou57)]

Le Wed, 15 Jun 2011 12:30:43 +0200, Natasha Kerensikova  
<lithiumcat@gmail.com> a écrit:
> This makes the dispatch table completely isotropic and allows to
> implement any element of the matrix in any compilation unit (as long as
> it is linked (statically or dynamically) to the final binary). I found
> this feature very nice when the "glue" between the row type and the
> column type does not obviously belong to either type
This is a common source of design ambiguity, and that's one of the reason  
why I've posted this topic. It's a long time (multiple years) I have this  
question in mind. Each time, I encounter difficulties to do a choice.

A common and simple example, while not related to dispatching, is stream  
operations : although its clear a input/ouput method must have two  
arguments, one for the stream and one for the data, how do you decide the  
operation belongs to the package defining the type or to the package  
defining the stream. This one is not the worst, as you would say : if the  
type is primitive enough, it will belongs to the stream package, and if  
the type is complex, it will belong to the package defining the complex  
type. Reasonable enough ?

Not the worst, but expose an example of this common question : does this  
method should belong to this or that type/package ?

Finally the question about multiple dispatch ends to be similar.

> I know other high-level languages do have introspection mechanisms, but
> I haven't seen anything like that in Ada. Have I missed them?
I guess this would disallow many kind of binary code optimization. If one  
need introspection, the he/she have to explicitly implement it.  
Introspection comes as more natural to interpreted language than to  
compiled language. Or else, may be you are thinking about compilers aware  
of introspection as they actually are of dispatching ? This would require  
to mark some type as requiring introspection, like you mark some type as  
tagged and defined dispatching operation on that type.

But I also feel to guess introspection is more suited to interpreted  
language for another reason than the one that is comes more natural with  
the implementation of interpreted language : self modifying program. Why  
would you need introspection if that is not to apply some alteration to  
what your are inspecting ? If this is not to alter the program itself  
(which is clearly a thing for interpreted language only), then that would  
probably be for debugging purpose then; and debugging can be done without  
introspection (while this can be done with introspection, as I my-self did  
when one day I modified an Eiffel compiler that way… the compiler was  
generating code which allowed introspection when the compile-for-debug  
flag was On).

-- 
“Syntactic sugar causes cancer of the semi-colons.”  [Epigrams on  
Programming — Alan J. — P. Yale University]
“Structured Programming supports the law of the excluded muddle.” [Idem]
“c++; /* this makes c bigger but returns the old value */” [Anonymous]

Re: Multiple dispatch

[Yannick Duchêne (Hibou57)]

Le Wed, 15 Jun 2011 13:10:50 +0200, Yannick Duchêne (Hibou57)  
<yannick_duchene@yahoo.fr> a écrit:
> A common and simple example, while not related to dispatching, is stream  
> operations : although its clear a input/ouput method must have two  
> arguments, one for the stream and one for the data, how do you decide  
> the operation belongs to the package defining the type or to the package  
> defining the stream.
I forget to say there is another alternative to that kind of ambiguity :  
defining a third package. In that third package, both the stream type and  
the data type are treated equally, this is the package which represent the  
union or collaboration of both together, with no one of both looking like  
dominated or controlled by the other (because there is no reason for the  
design to act as if this was, as it is not). This obviously applies even  
better when there are more than two types involved (but the question most  
commonly raises when there are two types).


-- 
“Syntactic sugar causes cancer of the semi-colons.”  [Epigrams on  
Programming — Alan J. — P. Yale University]
“Structured Programming supports the law of the excluded muddle.” [Idem]
“c++; /* this makes c bigger but returns the old value */” [Anonymous]

Re: Multiple dispatch

[Georg Bauhaus]

On 15.06.11 12:30, Natasha Kerensikova wrote:

> I know other high-level languages do have introspection mechanisms, but
> I haven't seen anything like that in Ada. Have I missed them?

You could build something around (external) tag names.

Or you could build a compiler into an ASIS program or
vice versa. This should be a pretty powerful team.

Re: Multiple dispatch

[Yannick Duchêne (Hibou57)]

Le Wed, 15 Jun 2011 16:59:13 +0200, Georg Bauhaus  
<rm.dash-bauhaus@futureapps.de> a écrit:
> You could build something around (external) tag names.
>
> Or you could build a compiler into an ASIS program or
> vice versa. This should be a pretty powerful team.
If he/she was talking about runtime introspection, the former is more  
advised (I supposed runtime introspection).

-- 
“Syntactic sugar causes cancer of the semi-colons.”  [Epigrams on  
Programming — Alan J. — P. Yale University]
“Structured Programming supports the law of the excluded muddle.” [Idem]
“c++; /* this makes c bigger but returns the old value */” [Anonymous]

Re: Multiple dispatch

[Georg Bauhaus]

On 15.06.11 17:18, Yannick Duchêne (Hibou57) wrote:
> Le Wed, 15 Jun 2011 16:59:13 +0200, Georg Bauhaus
> <rm.dash-bauhaus@futureapps.de> a écrit:
>> You could build something around (external) tag names.
>>
>> Or you could build a compiler into an ASIS program or
>> vice versa. This should be a pretty powerful team.
> If he/she was talking about runtime introspection, the former is more advised
> (I supposed runtime introspection).

Hypothetically, you compile GNAT into a program that uses
the ASIS libraries (seems redundant, but anyway). Then,
the compiler, being part of the running program, may be
able to replace parts of the running program with
new ones that have new types in them. Based on the
program or based on information gathered at runtime.
There is

- code compiled from sources input at runtime;
  information about previous compiler runs is preserved

- code compiled from sources produced by some ASIS
  machinery;  the sources may be the product of
  the running program

- code that is possible to make because the
  compiler knows enough about the program that it has
  produced. For example, when a compiler knows the
  layout of any dispatch tables, then it can compute
  more elaborate dispatch tables as it wishes.
  Providing for code injection, say.

Re: Multiple dispatch

[Randy Brukardt]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1727 bytes --]

"Yannick Duch�ne (Hibou57)" <yannick_duchene@yahoo.fr> wrote in message 
news:op.vwwpcjicule2fv@douda-yannick...
...
>An example: you have multiple object of different types rooted at a some 
>root type; you also have multiple containers of different types too, also 
>rooted at another root type. Now, say objects are all to have a 
>serialization methods, a different one for each type. This could be 
>dispatching, OK, except that you have the requirement these objects are 
>also to be serialized a way or another, depending on the container which 
>will hold the serialized datas. Add to this that you can't change this, 
>because this is part of some standard or any other kind of things already 
>fixed.

Serialization is one of those problems that really requires being 
implemented with composition, such that every type knows how to finalize 
itself and dispatches properly to use the similar routine of any component 
types. (It's annoying that Ada compilers know how to do this automatically, 
given that they do it for streams and for equality, but they won't help you 
do it in other cases.)

However, if you have external requirements that prevent you from doing that 
in the natural way, then some other solution will be needed. That solution 
is likely to look like a hack -- and that's OK, because the problem itself 
requires a hack (it doesn't map to a natural solution).

Which is a long way of saying that there are a lot of problems that can't 
really be solved elegantly, and it isn't very worthwhile to look for the 
perfect design for such problems. Come up with some design that solves the 
problem and don't obsess about it too much.

                                                  Randy.