newbie question - multiple dipatch algorithm? 
Author Message
 newbie question - multiple dipatch algorithm?

I am not (yet) a Dylan programmer.  I can sort of program in Python, but
my main programming experience is with the Dbase/Clipper/Xbase++ school
of languages. I am keen to learn more about Dylan.

I do not understand the concept of "multiple dispatch".  As I understand
it, a generic method is sent a list of parameters, and the run-time
support
chooses which actual function to call based on the parameter types.  By
contrast, in
single-dispatch languages the "self" (or "this") parameter is the sole
arbiter of which function is actually executed, based on some sort of
(language-dependant) method resolution mechanism. Is this correct?

If so, how does the algorithm for method selection work with multiple
dispatch?  e.g. Is the order of parameters significant?

many tias,

gary



Thu, 06 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:

> I do not understand the concept of "multiple dispatch".  As I understand
> it, a generic method is sent a list of parameters, and the run-time
> support
> chooses which actual function to call based on the parameter types.  By
> contrast, in
> single-dispatch languages the "self" (or "this") parameter is the sole
> arbiter of which function is actually executed, based on some sort of
> (language-dependant) method resolution mechanism. Is this correct?

Right.

Quote:
> If so, how does the algorithm for method selection work with multiple
> dispatch?  e.g. Is the order of parameters significant?

the order of parameters is *not* significant in Dylan.

Do you know C++?

C++ has multiple dispatch of overloaded functions, based on the *declared*
types of the actual parameters.  If a Dylan compiler happens to know the
exact type of each argument then it will do essentially the same thing as
a C++ compiler would do in the same situation -- basically:

  the function which is called has a better match to the actual
  arguments than the other available functions on one parameter,
  and no worse a match on the other arguments.

The difference between C++ and Dylan is that Dylan actually follws the
same rule for the *actual* (dynamic) types of the arguments, not their
declared (static) types.

So, for example:

define class <a> (<object>) end;
define class <b> (<a>) end;

define method m(i :: <integer>, n :: <a>)
  format-out("%d - a called\n", i);
end;

define method m(i :: <integer>, n :: <b>)
  format-out("%d - b called\n", i);
end;

define method main(appname, #rest arguments)

  let x :: <a> = make(<a>);
  let y :: <a> = make(<b>);
  let z :: <b> = make(<b>);

  m(1, x);
  m(2, y);
  m(3, z);

  exit(exit-code: 0);
end method main;

This produces:

1 - a called
2 - b called
3 - b called

The equivilent C++ program...

#include <iostream.h>

struct a {};
struct b : a {};

void m(int i, a *n);
void m(int i, b *n);

void m(int i, a *n){
   cout << i << " - a called\n";

Quote:
}

void m(int i, b *n){
   cout << i << " - b called\n";

Quote:
}

int main()
{  
   a *x = new a;
   a *y = new b;
   b *z = new b;

   m(1, x);
   m(2, y);
   m(3, z);

   return 0;

Quote:
}

... produces...

1 - a called
2 - a called
3 - b called

As you can see, Dylan dispatches based on what the object actually *is*
i.e. the second function call knows that the object is actually a <b> even
though the variable holding it is declared to be an <a>.  C++ dispatches
based on how the variable is declared, not what it is holding.

Interestingly, for this particular code, Gwydion Dylan's "d2c" generates a
runtime lookup for the first two calls to m() but calls the correct m(0
directly for the third example.

In order to get the same results as Dylan in C++, we would have had to
make "m()" a virtual function in the "a" and "b" classes, in which case we
would not then be able to have other versions of "m" in which the first
parameter was not an integer.

In Dylan, we could declare:

define method m(f :: <float>, n :: <a>)
end;

define method m(f :: <float>, n :: <b>)
end;

.. and call them with ...

   m(1.0, x);
   m(2.0, y);
   m(3.0, z);

.. and these versions would be called instead of the <integer> ones.  And
the same goes for C++ "overloaded functions".  But it would not work for
C++ virtual functions.

Overall, in my opinion, it's better to think of Dylan multi-methods as an
extension of C++ overloaded functions than as an extension of C++ virtual
functions.

-- Bruce



Thu, 06 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:

>the order of parameters is *not* significant in Dylan.

What is the rationale for this rule?  Does it appear like a bad thing to
rely on a certain argument precedence order because of conceptional
reasons or are there implementational benefits when method specificity
can be ambiguous?


Thu, 06 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:


> >the order of parameters is *not* significant in Dylan.

> What is the rationale for this rule?  Does it appear like a bad thing to
> rely on a certain argument precedence order because of conceptional
> reasons or are there implementational benefits when method specificity
> can be ambiguous?

  1. I can't seem to find the ruling in the DRM, but I don't recall
     an order being enforced on the evaluation of the arguments.

              foo (  a + b ,  b := a )

    Although not the same thing, it seems a tad inconsistant to rely on
    order in one case and not the other.

  2. You have ambiguous methods anyway.  Remember that Dylan dispatches
      on the actual type (multiple inheritance and linearization are
      also contributing factors) . [ The example at the end of that section. ]

 http://www.harlequin.com/products/ads/dylan/doc/drm/drm_50.htm#HEADIN...      

      [ It is doubtful that a "subtle" resolution of ambiguity won't
        run into usage (conceptional mismatch) problems.  Although the
        method's "designer" might be clear it is extremely easy for the
        user not to notice this resolution.  I vaguely recall someone
        from Harlequin talking about surveying senior CLOS designers about
        relying on some CLOS subtlety and it not having good outcomes in
        practice. ]

---

Lyman



Thu, 06 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:

> define class <a> (<object>) end;
> define class <b> (<a>) end;

> define method m(i :: <integer>, n :: <a>)
>   format-out("%d - a called\n", i);
> end;

> define method m(i :: <integer>, n :: <b>)
>   format-out("%d - b called\n", i);
> end;

> define method main(appname, #rest arguments)

>   let x :: <a> = make(<a>);
>   let y :: <a> = make(<b>);
>   let z :: <b> = make(<b>);

>   m(1, x);
>   m(2, y);
>   m(3, z);

>   exit(exit-code: 0);
> end method main;

> This produces:

> 1 - a called
> 2 - b called
> 3 - b called

> [...]

> Interestingly, for this particular code, Gwydion Dylan's "d2c" generates a
> runtime lookup for the first two calls to m() but calls the correct m()
> directly for the third example.

Update:

The reason for the runtime lookup is that we haven't provided a "make"
function for <a> or <b> and the compiler can't be sure whether we intend
to use the built-in one, or provide our own elsewhere.  It's legal (and
useful) in Dylan for the make() function to return a subclass of the
actual class asked for e.g. when you do make(<vector>) you don't actually
get an object of class <vector> (which is an abstract class that you
actually can't instantiate).  Instead you get an object of type
<simple-object-vector>.  So it would be legal for us to provide a
function...

define method make(class == <a>)
  make(<b>);
end;

... in another library, with the result that the compiler cannot know
whether x will actually contain an <a> or a <b>.

We can reassure the compiler about this by either explicitly writing our
own make() function, or else by declaring "sealed domains" on the make
function:

define sealed domain make(singleton(<a>));
define sealed domain make(singleton(<b>));

With this change, the generated C code uses simple function calls for the
three calls to "make" and for the three calls to "m", however there are
now runtime-lookup calls to "initialize" for the three objects.  Adding...

define sealed domain initialize(<a>);
define sealed domain initialize(<b>);

... reassures the compiler that no-one else in another library is going to
implement non-default initialize functionality for these classes and
allows the default initialize to be done at compile time.

It is common in Dylan code where performance is important and
extensibility is known to not be needed to see this pattern:

define class foo (...);
end;

define sealed domain make(singleton(foo));
define sealed domain initialize(foo);

After adding these sealed domain declarations, the generated C code now
consists of three simple function calls to "make" functions, and three
simple function calls to the appropriate implementation of "m".  The Dylan
compiler could, if it wanted to, now inline these function calls into the
main program, but the current version doesn't, leaving that job to the C
compiler.  GCC obliges, and all the calls to make() and m() get inlined in
the machine code.

-- Bruce



Fri, 07 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:



> > >the order of parameters is *not* significant in Dylan.

> > What is the rationale for this rule?  Does it appear like a bad
> > thing to rely on a certain argument precedence order because of
> > conceptional reasons or are there implementational benefits when
> > method specificity can be ambiguous?

I remember hearing the same story as in Lyman's parenthetical comment:
empirical CLOS experience led people to believe that disambiguating
on position ended up just a little too confusing.  Personally I have no
CLOS experience, so I can't argue one way or the other.  (I wouldn't be
surprised if CLOS allowed alternative disambiguation algorithms, which
might have added to the confusion, but that's just conjecture.)

Interestingly, the generic-definer macro in the DRM allows for a list
of key/value pairs after the parameter list: perhaps a backdoor for
future reintroduction of wackier dispatch algorithms?

Quote:
>   1. I can't seem to find the ruling in the DRM, but I don't recall
>      an order being enforced on the evaluation of the arguments.

>               foo (  a + b ,  b := a )

>     Although not the same thing, it seems a tad inconsistant to rely on
>     order in one case and not the other.

It took me a while to find the bit of the DRM which explains this: it's
at the end of Chapter 4

<URL:http://www.harlequin.com/products/ads/dylan/doc/drm/drm_37.htm#HEADIN...>

Basically, execution is left-to-right, except that the right-hand side
of an assignment is executed before the left.  If an assigment is via a
setter function (rather than directly to a binding), "the execution
time of the binding named by the setter function is undefined".  For
example,

  function-setter(one, two, three) // this is the same as the next
  function(two, three) := one      // 'function' could also be a slot

Hugh G. Greene



Fri, 07 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:

> empirical CLOS experience led people to believe that disambiguating
> on position ended up just a little too confusing.  Personally I have no

I've never been confused by CLOS. You might have to write multiple methods, though,
and the further into the tail you go, the worse it gets. But then, maybe that
argument is in a bad position after all.

Quote:
> CLOS experience, so I can't argue one way or the other.  (I wouldn't be
> surprised if CLOS allowed alternative disambiguation algorithms, which.

Of course it does. This is Lisp!

Quote:
> might have added to the confusion, but that's just conjecture.)

As the method combination rule is determined by the :metaclass argument of a
DEFGENERIC, you'll have to keep in mind which methods are `weird' when you write/see
DEFMETHODs elsewhere. Maybe you just need a better editor, one that is not
file-oriented.

Maybe `globally most specific, then left-right' is a better rule. You'll need some
warnings, though.



Fri, 07 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:



> > define class <a> (<object>) end;
> > define class <b> (<a>) end;
> > define method m(i :: <integer>, n :: <a>) [...] end;
> > define method m(i :: <integer>, n :: <b>) [...] end;
> > define method main(appname, #rest arguments) [...] end [...];

> > This produces:

> > 1 - a called
> > 2 - b called
> > 3 - b called

> > [...]

> > Interestingly, for this particular code, Gwydion Dylan's "d2c"
> > generates a runtime lookup for the first two calls to m() but calls
> > the correct m() directly for the third example.

> Update:

> The reason for the runtime lookup is that we haven't provided a "make"
> function for <a> or <b> and the compiler can't be sure whether we
> intend to use the built-in one, or provide our own elsewhere.  ...

Harlequin Dylan (at least the internal release I have -- haven't
checked 1.2) manages to do a direct call for the second example as well.
This puzzled me but a compiler guru tells me it's an optimisation
based on the fact the make is specified to return a general instance
of its first argument (and the two classes here are sealed).  That
can't actually be expressed in-language, though, so this is a bit of
implementation-specific magic.

Quote:
> We can reassure the compiler about this by either explicitly writing
> our own make() function ...

I could be wrong, but I think that writing your own make method isn't
enough unless its in a sealed domain.  Otherwise add-method and
remove-method could be used at runtime to change the method (and so
the type of the returned object).

Quote:
> ... or else by declaring "sealed domains" on the make function:

> define sealed domain make(singleton(<a>));
> define sealed domain make(singleton(<b>));

In Harlequin Dylan you can abbreviate this using the "subclass" type
constructor, which returns a type representing all general subclasses
of the class given as its argument (including that class itself).  In
this case, you'd say

  define sealed domain make (singleton(subclass(<a>)));

This hasn't officially been accepted as a language extension AFAIK,
and I can't remember whether the Gwydion volunteers are planning to
(or already do) support it.

Quote:
> ... there are now runtime-lookup calls to "initialize" ...  Adding...

> define sealed domain initialize(<a>);
> define sealed domain initialize(<b>);

> ... reassures the compiler ...

In this case, the second "define sealed domain" is superfluous, since
<b> is a subclass (and hence subtype) of <a>.  OTOH, it does no harm
and might be useful self-documentation, in a larger code base.  It could
also guard against unintentionally losing sealing over the "lower" if
the code changes to unseal the "higher" one.


Fri, 07 Dec 2001 03:00:00 GMT  
 newbie question - multiple dipatch algorithm?

Quote:


...
> I remember hearing the same story as in Lyman's parenthetical comment:
> empirical CLOS experience led people to believe that disambiguating
> on position ended up just a little too confusing.

  I finally came upon the correct sequence of keywords to pull what I was
  thinking of out of dejanews.  It was so much the order of the arg as
  the order of the superclasses in conjunction with linearization.

http://x42.deja.com/[ST_rn=if]/getdoc.xp?AN=388339195.2&CONTEXT=929985432.1854865477&hitnum=1

  I think the still relevant "problem" is the "flip-flopping" if the order being
  significant over the long term maintenance of a program.  

Quote:
> CLOS experience, so I can't argue one way or the other.  (I wouldn't be
> surprised if CLOS allowed alternative disambiguation algorithms, which
> might have added to the confusion, but that's just conjecture.)

  I can remember on occassion "perturbing" the super list to get the
  dispatch I wanted.  It usually wasn't a good idea over the long run.

Quote:
> Interestingly, the generic-definer macro in the DRM allows for a list
> of key/value pairs after the parameter list: perhaps a backdoor for
> future reintroduction of wackier dispatch algorithms?

  IMHO, no.  The key/optional arguments should contribute to the dispatch.
  They may or may not be there.

Quote:
> >   1. I can't seem to find the ruling in the DRM, but I don't recall
> >      an order being enforced on the evaluation of the arguments.
....
> It took me a while to find the bit of the DRM which explains this: it's
> at the end of Chapter 4

  Ack. I was searching for the wrong "word" in the index. :-) Thanks.


Fri, 07 Dec 2001 03:00:00 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. multiple windows in ST/V DOS - newbie question

2. Newbie Haskell question (combining multiple filter's)

3. Multiple RELEASE in SORTs - Newbie question...

4. Iterating over multiple lists (a newbie question)

5. Newbie Question (Was: Newbie Question...)

6. newbie, fat read routine/algorithm problem

7. newbie, fat read routine/algorithm problem

8. Need simple algorithm for newbie

9. Not a newbie, but a newbie question...

10. Trivial Newbie Question (Newbie)

11. newbie needs help with multiple expressions in awk

12. Newbie on multiple return values

 

 
Powered by phpBB® Forum Software