Barry Margolin <barmar@bbnplanet.com> wrote:
> <mayurnaik@my-dejanews.com> wrote:
>>4. Why does C++ not implement double dispatch? Is it
>>   because
>>   a. of the large overhead that such methods would
>>      impose, or
>>   b. that run time errors might occur, or
>>   c. it feels double dispatch is simply not OOP, or
>>   d. something else?
>
>Probably mostly (c) ...
>And there's probably some issue with (a).

Stroustrup discusses this in D&E: it's entirely (a).  He never
hesitated to implement features that were useful but not "O-O".
He did resist implementing features that could not be done
better than users could do themselves.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

If you read Stroustrups D&E of CPL (look for 'workaround for multi-methods')
you can read the reasoning behind this as well as a perfectly elegant
workaround for most practical cases.

Silvio Bierman

mayurnaik@my-dejanews.com wrote in message <705292$v38$1@nnrp1.dejanews.com>...
>I was facing a C++ design problem for the past few months. Recently,
>I realized that this problem is phrased as "the double dispatch
>problem" in the context of Object-Oriented languages.
... [excessive quoting snipped. -mod]
>4. Why does C++ not implement double dispatch? Is it
>   because
>   a. of the large overhead that such methods would
>      impose, or
>   b. that run time errors might occur, or
>   c. it feels double dispatch is simply not OOP, or
>   d. something else?
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <70iefh$moc$1@shell7.ba.best.com>,
Nathan Myers <ncm@nospam.cantrip.org> wrote:
>He did resist implementing features that could not be done
>better than users could do themselves.

Multi-methods are pretty difficult to do well in user code.  You can have a
member function specialized on one argument that then calls a
class-specific member function specialized on the second argument, but this
means that any time you add a new first-argument class you have to make a
whole new set of second-argument functions.  There's no way to make it
automatically find the best matching pair.  And you probably also need
enormous friend tables to allow access to member variables.

--
Barry Margolin, barmar@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 20 Oct 98 05:32:14 GMT, mayurnaik@my-dejanews.com

I really don't know what double dispatch means.  The following
paragraph needs to be explained further.

>The problem can be solved by replacing each double
>dispatch (viz. functions labelled 1 and 2)with two
>single dispatches.


In any case, here's an efficient solution to your problem.  We
had a discussion about this on comp.lang.c++ recently.

// abstract class
class symbol {
     // representation of the data type
public:
     friend symbol* add(const symbol&, const symbol&);         /* 1 */
     // ...
private:
     virtual symbol* homoadd(const symbol&) const = 0;
     virtual symbol* heteroadd(const symbol&) const;
};

// BTW, abstract classes normally have no data


class variable : public symbol
{
     /* ... */
private:
     virtual variable* homoadd(const symbol&) const;
};


// abstract class
class constant : public symbol {
public:
     // ...
private:
};

class i_const : public constant
{
     /* ... */
private:
     virtual constant* homoadd(const symbol&) const;
};

>class f_const : public constant { /* ... */ };


symbol* add(const symbol& lhs, const symbol& rhs)
{
     if (typeid(lhs)==typeid(rhs)) // fast: just compare vptrs
          return lhs->homoadd(rhs);
     else
          return lhs->heteroadd(rhs); // add two objects of different type
     return 0;
}


symbol* symbol::heteroadd(const symbol& rhs) { ... }

constant* constant::homoadd(const symbol& rhs)
{
     assert(typeid(rhs)==typeid(constant)); // not necessary if you're careful
     ...;
}



>The problem can be solved by replacing each double
>dispatch (viz. functions labelled 1 and 2)with two
>single dispatches.

Huh?



--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Barry Margolin <barmar@bbnplanet.com> wrote:
>Nathan Myers <ncm@nospam.cantrip.org> wrote:
>>He did resist implementing features that could not be done
>>better than users could do themselves.
>
>Multi-methods are pretty difficult to do well in user code.

They're hard for the compiler to do well, too.  In fact, if you
don't know a lot about the problem being solved, what you do will
probably be a lot less efficient than what you would do otherwise.
The compiler is always in that position.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

mayurnaik@my-dejanews.com wrote:

> Hi,
> I was facing a C++ design problem for the past few months. Recently,
> I realized that this problem is phrased as "the double dispatch
> problem" in the context of Object-Oriented languages. The problem I
> was facing was related to representing symbols in a miniature C
> compiler:
>
> (snip)

Scott Meyers covers the issues relating to multiple-dispatch
in his excellent "More Effective C++", Item 31 [1].  It may
help you.  (Personal recommendation - I've no connection with
the author or publisher)

[1] "More Effective C++" Addison-Wesley ISBN: 0-201-63371-X

--
+---------------------------------+
|         Paul Grealish           |
|       GEOPAK-TMS Limited        |
|       Cambridge, England        |
| paul.grealish@uk.geopak-tms.com |
+---------------------------------+


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

mayurnaik@my-dejanews.com writes:

|>  I was facing a C++ design problem for the past few months. Recently,
|>  I realized that this problem is phrased as "the double dispatch
|>  problem" in the context of Object-Oriented languages. The problem I
|>  was facing was related to representing symbols in a miniature C
|>  compiler:

|>  // abstract class
|>  class symbol {
|>       // representation of the data type
|>  public:
|>       friend symbol* add(symbol*, symbol*);         /* 1 */
|>       // ...
|>  };

|>  class variable : public symbol { /* ... */ };
|>
|>  // abstract class
|>  class constant : public symbol {
|>  public:
|>       friend constant* add(constant*, constant*);   /* 2 */
|>       // ...
|>  };

|>  Considering only integer and floating point constants,

|>  class i_const : public constant { /* ... */ };

|>  class f_const : public constant { /* ... */ };

|>  At the time of parsing, if both symbols to be added
|>  are constants, I want to do constant folding,  else
|>  I want to generate intermediate code. Thus, here is
|>  the problem. Furthermore, if the two symbols do
|>  happen to be constants, I must determine whether both
|>  are floats, or ints or mixed.

For the general response concerning double dispatch, see Nathan Myer's
response.  In this particular case, however, I suspect that the double
dispatch is necessitated by a design error -- IMHO, the type information
concerning a symbol (constant or variable) or an expression is just an
attribute of the symbol, a bit of information which concerns it, and not
part of the node type.  In general, when processing binary operators,
whether for constant propagation or otherwise, the solution involves
passing the two types to a function which determines the resulting type
of the expression (which might not be either of the two types), then
generating conversion nodes as needed.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Barry Margolin <barmar@bbnplanet.com> writes:

|>  In article <70iefh$moc$1@shell7.ba.best.com>,
|>  Nathan Myers <ncm@nospam.cantrip.org> wrote:
|>  >He did resist implementing features that could not be done
|>  >better than users could do themselves.
|>
|>  Multi-methods are pretty difficult to do well in user code.  You can have a
|>  member function specialized on one argument that then calls a
|>  class-specific member function specialized on the second argument, but this
|>  means that any time you add a new first-argument class you have to make a
|>  whole new set of second-argument functions.  There's no way to make it
|>  automatically find the best matching pair.  And you probably also need
|>  enormous friend tables to allow access to member variables.

I suspect that the real reason has to do with the enormous difficulty of
implementing them using existing linker technology (or separate
compilation in general).  At present, all the compiler needs to know to
generate the vtbl for a class B is in the definition of B; with multiple
dispatch, either it would have to know all of the possible overrides of
the second class, or it would have to use some dynamic scheme using
run-time registration and look-up (e.g. in a hash table).  The first is
by definition impossible with separate compilation, and the second
causes problems with the order of initialization (since all
registrations must be finished before the first virtual call).  Neither
is impossible, but either result in more work than they are worth.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

mayurnaik@my-dejanews.com wrote:
>
> Why does C++ not implement double dispatch?

In the most general case, double dispatch involves writing n-squared
functions, where n is the number of types you need to deal with. Where
would you put these? You have only n classes, so you have to decide
either to put one conceptual "row" of functions in each class, or one
"column" of functions in each class. When you make that choice, either
way, you are deciding which parameter becomes the "receiver" of the
message, and are implicitly moving back to single-dispatch. When you
next add a new type, you still have to add both a row _and_ a column to
the conceptual function array, which means you still have to modify
every class. There's no way around that, not even in theory. In other
words, double dispatch makes class encapsulation impossible, no matter
how you implement it.

--

Ciao,
Paul


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
I was facing a C++ design problem for the past few months. Recently,
I realized that this problem is phrased as "the double dispatch
problem" in the context of Object-Oriented languages. The problem I
was facing was related to representing symbols in a miniature C
compiler:

// abstract class
class symbol {
     // representation of the data type
public:
     friend symbol* add(symbol*, symbol*);         /* 1 */
     // ...
};

class variable : public symbol { /* ... */ };

// abstract class
class constant : public symbol {
public:
     friend constant* add(constant*, constant*);   /* 2 */
     // ...
};

Considering only integer and floating point constants,

class i_const : public constant { /* ... */ };

class f_const : public constant { /* ... */ };

At the time of parsing, if both symbols to be added
are constants, I want to do constant folding,  else
I want to generate intermediate code. Thus, here is
the problem. Furthermore, if the two symbols do
happen to be constants, I must determine whether both
are floats, or ints or mixed.

The problem can be solved by replacing each double
dispatch (viz. functions labelled 1 and 2)with two
single dispatches.

1. Since this is a work-around, is there a fatal flaw
   in my design?

2. If not, is there a more clean and efficient
   solution (which is nearly at par with a C solution
   as far as efficiency is concerned)?

3. Would scurrying back to type fields be a better
   choice in such a situation?

4. Why does C++ not implement double dispatch? Is it
   because
   a. of the large overhead that such methods would
      impose, or
   b. that run time errors might occur, or
   c. it feels double dispatch is simply not OOP, or
   d. something else?

Thanking you,
With best regards,
Mayur





-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <705292$v38$1@nnrp1.dejanews.com>,
 <mayurnaik@my-dejanews.com> wrote:
>4. Why does C++ not implement double dispatch? Is it
>   because
>   a. of the large overhead that such methods would
>      impose, or
>   b. that run time errors might occur, or
>   c. it feels double dispatch is simply not OOP, or
>   d. something else?

Probably mostly (c), the same reason that most OO languages don't implement
multi-methods.  Most OO paradigms are based on message passing, which
requires a distinguished "receiver" of the message; in C++ this is
indicated with <receiver>.<message>(<parameters>).

Also, multi-methods make it difficult to do information hiding.  If a
method doesn't "belong" to a specific class, how do you know which class's
private data it can access?  CLOS and Dylan sidestep this issue by doing
away with the notion of private data, but many OO designers probably feel
that this is an important feature of OO languages.

And there's probably some issue with (a).  The techniques necessary to do
efficient multiple virtual dispatch in CLOS were harder to come up with
than those used for single dispatch (the vtable).  I'm not sure how much of
this was due to CLOS's dynamic nature; C++'s static class hierarchy may
simplify things a bit.

--
Barry Margolin, barmar@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]