www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Experiment: Implementing Multiple Dispatch in D (need vararg call)

reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
I watched some time ago a Google TechTalk about Common Lisp (
http://video.google.com/videoplay?docid=448441135356213813&q=peter+seibel
) where, as expected from a Lispanatic, LISP is idolized and Java is 
whined about.

The second part of the talk, talks about the CLOS (Common Lisp Object
System) multiple dispatch system (called multimethods on Lisp lingo),
and how it can be useful, etc.., and how in Java it all had to be
implemented manually and non-generically (i.e., for each particular usage).

I wondered, how would D fare? I started to think if and how that feature 
could be implemented in D, as an experimental, proof-of-concept, and 
template learning exercise. The first thing needed, I noticed, was a 
compile time reflection mechanism, for functions at least (to find it's 
parameter types). With some IFTI incantations this is actually already 
possible, but with the number of the funtion's parameters limited to 
some point(this is what TomS's funcmeta does).

So, I've started out and I got a near complete implementation, but
... then I've just noticed I need one more thing: the ability to call a
function with a constant but parameterized number of arguments. That is, 
I have a:

Compile time parameter which is the number of arguments:
   N

The arguments:
   Object[N] objar;

An array-like template that provides the exact (class) type of each of 
those arguments:
   funcTypeINFO.arg!(int n)

And then I would need to call a function like this:

   dispatchfn(
     cast(funcTypeINFO.arg!(0)) objar[0],
     cast(funcTypeINFO.arg!(1)) objar[1],
     ...
     cast(funcTypeINFO.arg!(N)) objar[N]
   );

Note that dispatchfn is not a variadic function, it is a normal function 
with N parameters.
Is this possible? I fear it is not, at least without entering into 
ABI-dependent hackery, which I would like to avoid :/ (but which I guess 
is still better than nothing).


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jul 31 2006
next sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Bruno Medeiros wrote:

 I watched some time ago a Google TechTalk about Common Lisp (
 http://video.google.com/videoplay?docid=448441135356213813&q=peter+seibel
 ) where, as expected from a Lispanatic, LISP is idolized and Java is 
 whined about.
 
 The second part of the talk, talks about the CLOS (Common Lisp Object
 System) multiple dispatch system (called multimethods on Lisp lingo),
 and how it can be useful, etc.., and how in Java it all had to be
 implemented manually and non-generically (i.e., for each particular usage).
 
 I wondered, how would D fare? I started to think if and how that feature 
 could be implemented in D, as an experimental, proof-of-concept, and 
 template learning exercise. The first thing needed, I noticed, was a 
 compile time reflection mechanism, for functions at least (to find it's 
 parameter types). With some IFTI incantations this is actually already 
 possible, but with the number of the funtion's parameters limited to 
 some point(this is what TomS's funcmeta does).
 
 So, I've started out and I got a near complete implementation, but
 .... then I've just noticed I need one more thing: the ability to call a
 function with a constant but parameterized number of arguments. That is, 
 I have a:
 
 Compile time parameter which is the number of arguments:
   N
 
 The arguments:
   Object[N] objar;
 
 An array-like template that provides the exact (class) type of each of 
 those arguments:
   funcTypeINFO.arg!(int n)
 
 And then I would need to call a function like this:
 
   dispatchfn(
     cast(funcTypeINFO.arg!(0)) objar[0],
     cast(funcTypeINFO.arg!(1)) objar[1],
     ...
     cast(funcTypeINFO.arg!(N)) objar[N]
   );
 
 Note that dispatchfn is not a variadic function, it is a normal function 
 with N parameters.
 Is this possible? I fear it is not, at least without entering into 
 ABI-dependent hackery, which I would like to avoid :/ (but which I guess 
 is still better than nothing).
 
 


Ah crap... I sent two messages by mistake. This is the one I wanted to
send. (this was due to me being under dialup now during Summer, and
wobbling around between TB's online and offline mode)

Anyway, yes, bind does work for that, I should have remembered that. I
guess I was thinking of something that would work for an unlimited
number of parameters.

This experiment was rich, I've noted quite some issues about D, although
it's a very small piece of code. I'll post it later when it is done,
plus the issue comments. It won't properly work though, as one of the
thing I've stumbled is a template bug that I think I can't workaround
(the code that triggers it is itself was a workaround for another
limitation...).

[PS: And this message was supposed to have been sent yesterday]

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 02 2006
prev sibling next sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Bruno Medeiros wrote:

 I watched some time ago a Google TechTalk about Common Lisp (
 http://video.google.com/videoplay?docid=448441135356213813&q=peter+seibel
 ) where, as expected from a Lispanatic, LISP is idolized and Java is 
 whined about.
 
 The second part of the talk, talks about the CLOS (Common Lisp Object
 System) multiple dispatch system (called multimethods on Lisp lingo),
 and how it can be useful, etc.., and how in Java it all had to be
 implemented manually and non-generically (i.e., for each particular usage).
 




I've attached the code if anyone is interested. It is two files, the MDF 
dispacher MultiDisFunction.d, some user/test code MDF_usercode.d, and 
TomS's meta library (thx!). Basically the idea is this: suppose you have 
two types of objects, Circle and Rect, and you want to check for a 
collision between two objects of any of those types. The exact algorithm 
will vary depending on the combination of the objects involved (checking 
for collision between <Circle,Circle> is different from <Circle,Rect>), 
so we create a multiple dispatch function that will redirect to each 
algorithm depending on each parameter. (See the user code) This only 
works for class parameters of course.
The dispatcher works by maintaining a map of entries, where the value is 
a function pointer (a dispatch), and the key is an array of ClassInfo's, 
which are the parameters of that dispatch. A dispatch is only selected 
if the parameter's types match exactly, but this could be a more 
complicated algorithm, checking superclass relations, etc., but that was 
beyond my interest.


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 02 2006
prev sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Bruno Medeiros wrote:

 I watched some time ago a Google TechTalk about Common Lisp (
 http://video.google.com/videoplay?docid=448441135356213813&q=peter+seibel
 ) where, as expected from a Lispanatic, LISP is idolized and Java is 
 whined about.
 
 The second part of the talk, talks about the CLOS (Common Lisp Object
 System) multiple dispatch system (called multimethods on Lisp lingo),
 and how it can be useful, etc.., and how in Java it all had to be
 implemented manually and non-generically (i.e., for each particular usage).
 
 I wondered, how would D fare? I started to think if and how that feature 
 could be implemented in D, as an experimental, proof-of-concept, and 
 template learning exercise. The first thing needed, I noticed, was a 
 compile time reflection mechanism, for functions at least (to find it's 
 parameter types). With some IFTI incantations this is actually already 
 possible, but with the number of the funtion's parameters limited to 
 some point(this is what TomS's funcmeta does).
 



Here are some miscellaneous comments I gathered from the MDF experiment:

* One can't just instantiate a template.
Sometimes one just wants to instantiate a template, but that is not
allowed, a declaration of some entity must be made, example:
   alias tpl!(foo) _DUMMY;


* is-expression is tricky:
Using the is expression for type comparison is error-prone. Because it
also fails if the expression is not semantically correct, then
is-expressions like these:
   is(typeof(foo) == typeof(bar))
may evaluate to false when you make a typo, instead of generating a
compile-time error. :(


* Template forwarding referencing problems are annoying
Template forwarding referencing problems are annoying. Ye pretty much. 
But easy to work around I guess.

* IFTI doesn't work for member functions. (members of aggregate types)
Oskar had already pointed this out recently. It happens like this:

   struct st {
     void iftifunc(T) (T a) {  }
   }

   void test() {
     st s;
     s.iftifunc(1);
   }

  main.d(2): template main.st.iftifunc(T) templates don't have properties
  main.d(7): no property 'opCall' for type 'st'
  main.d(7): function expected before (), not 1 of type int


* Templates are not allowed in functions
This restriction makes sense for some templates, but not for all. These 
templates could be allowed, but with restrictions to the kind of member 
entities they can have (similarly to struct and class inner templates). 
Specifically, a template with only function members or with compile-time 
members, could be allowed. I ran into three situations where I wanted 
such templates inside a function, in MDF.


* Static arrays ... :(
Static arrays are a stain in the language. They're the black sheep of 
the D types, as, most inconsistently, they are the only type which 
cannot be assigned (with various ramifications as, cannot be inout 
parameters, cannot be the key of AAs, etc.).
Again this is nothing new, both I and Oskar have mentioned this before, 
but this is the first time I've been actually stinged by it.
We should seriously consider how and if it would be feasible to change 
arrays so that they work as proper value types.


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 02 2006