cline@cheetah.ece.clarkson.edu (Marshall Cline) (12/19/90)
In article <Dec.11.13.41.32.1990.19330@remus.rutgers.edu> schaum@remus.rutgers.edu (schaum) writes: >I and my group partners are constructing a calculator which operates >on integers, matrices and sparse matrices. Our current heirarchy is >as follows: Operand > / | \ > Integer | Sparse > Matrix >Class operand is an abstract class containing no data and only virtual >member functions which are defined in the subclasses. Our goal is to >produce a client class Calculator which evaluates expressions in >reverse Polish notation, doing addition, subtraction and >multiplication on objects of subclasses of operand, passing parameters >of type operand in order to be able to pass any of the subclasses as >parameters. You've stumbled into the wild and wolly world of multiple polymorphism, which is simulated in C++ via double dispatching. It's a lot of fun, so hold on to your hat! Given N types of Operands, there'll be N^2 `add' routines: Int+Matrix, Int+Sparse, Int+Int, etc. So, for starters, we *have* to simply accept the fact that this is going to be messy: there *will* be N^2 chunks of code; our job is to find the `right' one, given any pair of Operands. Suppose you have two People in a room. If one is a Plumber and the other wants a Plumber, they can do business in the usual way. But they can't just assume they're a `match'; they have to check it out. What do they do? The first says, ``Hello. I'm Joe Shmow. I'm a Plumber,'' to which the second replies, ``Great! I'm Sam Smith, and I need a Plumber.'' This is the basic technique of double dispatching: first the left Operand tells what it *actually* is (an Integer, for example), after which the right Operand responds accordingly. add(Operand& x, Operand& y) then goes like this: pass a generic message to `x' such as `add yourself to the Operand called y', or x.add(y). If all Operands are equipped with an add(Operand&) virtual member function, this will identify the exact class of `x' (for example, an Integer), so that Integer::add(Operand& y) will get control. That unambiguously identifies the left arg, the cost being one polymorphic dispatch. Like the Plumber who holds out his hand, `x' then passes another generic message to `y' that says `add me to yourself, and I know for a fact that I am an Integer'. This is accomplished by equipping all Operands with a virtual function called `add_Integer(Integer& x)'. Next, suppose `y' is actually a Matrix, in which case `Matrix::add_Integer(Integer& x)' will get control. A Matrix knows how to add itself to an Integer, so the rest happens quickly. There are some tricky spots, but that's double dispatching for you. For the brave: you don't *have* to call it add_Integer(Integer&), since the compiler can disambiguate them based on the parameter list, so you might just want to call all these `add(...)' (provided you don't suffer from double vision that is!) The major disadvantage of double dispatching is that class Operand and all its subclasses will need to be updated if a new Operand is added to the hierarchy. Ie: we lose the OO-ideal of ``adding a class won't require you to change existing classes'' (Meyer's Open-Closed principle; Meyer, OOSC, P/H, 1988). But thems the brakes; if you want to polymorphically resolve on more than one parameter, double dispatching is the only solution in C++ (or in Eiffel, Smalltalk, etc; CLOS is the most prominent OOPL which *directly* supports multiple polymorphism). >NOTE: > I had defined class operator with a set of virtual functions. ^^^^^^^^ Another typo; I'm sure you meant `Operand', as `operator' is a C++ keyword. > Each class: integer, matrix, sparse_matrix inherited publicly > from operand. Yet I could not assign a pointer of type class > operand to an integer, matrix, or sparse_matrix. I eventually > wrote a struct within class operand containing one object of > integer, one of matrix and one of sparse_matrix. I got kind > of [expletive deleted --MPC] at Borland Turbo C++ for this. >ex: >class base { public: virtual void foo(){}; }; ^^^ Probably another typo. You don't want a ``;'' after that ``}''. But ``=0;'' would probably be much closer to what you want. Ie: the following declares `Base' to be an `abstract base class' (ABC): class Base { public: virtual void foo()=0; }; >class sub1 : public base { void foo() {printf("sub1\n");} }; >class sub2 : public base { void foo() {printf("sub2\n");} }; ^---Another typo: Insert `public:' here >main() >{ > base *a; > sub1 d; > a = &d; > a->foo(); >} This should probably work, but TC++ will probably resolve this statically, as it doesn't take an overly intelligent optimizer to see that `a' is actually pointing to a `sub1'. >//Do not assume that I am using correct syntax. >//I tried a similar test program with Turbo C++. The program did not >//compile and I could not find my error. C++ should have >//polymorphism. Obviously, I must be stupid, ignorant, or something. Not stupid. Just a few typos that will probably fix things up. I suspect that inserting `public:' will solve your major problem. Marshall Cline PS: You probably want to get into the habit of saying: { cout << "sub1\n"; } rather than: { printf("sub1\n"); } PPS: The memory management for the above will be a big headache. The other C++ idiom which you'll want is to wrap an ABC pointer in a small lightweight class. The problem is that nearly all your `Operand's will be allocated dynamically (ie: `new Integer' etc), yet when a pointer or ref falls off then end of its scope, C++ doesn't kill the pointed-to object (since C++ correctly assumes there may be other live references to it). *However* a tiny class like `Op' (see below) can have a destructor which can `delete' the pointed-to memory. This requires yet another C++ idiom: `Operand' should have a virtual `clone()' member function, so `Op' can get its own copy from the freestore. This is tricky to get right, but you'll learn a lot about C++ in the process! Something like this: //Warning: the following compiles but hasn't been tested: class Integer; class Matrix; class Sparse; class Operand { void operator=(const Operand&) { } //`private' and therefore inaccessible public: virtual ~Operand() { } virtual Operand& clone() const = 0; virtual Operand& add(const Operand&) const = 0; virtual Operand& add_Integer(const Integer&) const = 0; //etc ad nauseum... }; class Integer: public Operand { int i; public: Integer(int ii) : i(ii) { } Integer(const Integer& I) : i(I.i) { } //copy constructor Operand& clone() const { return *new Integer(*this); } Operand& add(const Operand& y) const { return y.add_Integer(*this); } Operand& add_Integer(const Integer& x) const { return *new Integer(i + x.i);} //...etc... }; class Matrix : public Operand { /*...*/ }; class Sparse : public Operand { /*...*/ }; // There are several C++ idioms up there (ex: *new being a reference, // returning *new Integer(*this) in Integer::clone(), privatizing the // assignment operator thus making it illegal by default, using a // virtual destructor, `const' member functions and refs, etc). // Finally you can write `Op' which will `wrap' a pointer to `Operand': class Op { Operand* o; Op(Operand& oo, int):o(&oo) { } //private constructor; does NOT clone its arg public: ~Op() { delete o; } Op(const Operand& oo) : o(&oo.clone()) { } //clone its Operand Op(const Op& oo) : o(&oo.o->clone()) { } //copy constructor Op& operator=(const Op& oo) // assignment; be careful! { if (o != oo.o) { delete o; o = &oo.o->clone(); } } friend Op operator+(const Op& x, const Op& y) {return Op(x.o->add(*y.o),0);} //friend Op operator*(const Op& x, const Op& y) {return Op(x.o->mul(*y.o),0);} //...etc etc etc... }; // Note: Op's private ctor is disambiguated from Op::Op(const Operand&) by // the extra (ignored) argument in Op::Op(Operand&,int) // Note: Op's destructor `delete's the pointed-to op // Note: no virtual functions are needed in class `Op' // Note: class Op is a `by value' class; ex: you CAN have a local of type `Op' // Note: `Op' doesn't have any `destructive' operations such as +=, *=, etc main() { Op x = Integer(3); Op y = Integer(4); Op z = x + y; //initialization z = x + y; //assignment } Hope all this helps! -- PS: If your company is interested in on-site C++/OOD training, drop me a line! PPS: Career search in progress; ECE faculty; research oriented; will send vita. -- Marshall Cline / Asst.Prof / ECE Dept / Clarkson Univ / Potsdam, NY 13676 cline@sun.soe.clarkson.edu / Bitnet:BH0W@CLUTX / uunet!clutx.clarkson.edu!bh0w Voice: 315-268-3868 / Secretary: 315-268-6511 / FAX: 315-268-7600
philip@pescadero.Stanford.EDU (Philip Machanick) (12/19/90)
In article <CLINE.90Dec18151352@cheetah.ece.clarkson.edu>, cline@cheetah.ece.clarkson.edu (Marshall Cline) writes: |> Given N types of Operands, there'll be N^2 `add' routines: Int+Matrix, |> Int+Sparse, Int+Int, etc. Shouldn't that be N! (factorial)? -- Philip Machanick philip@pescadero.stanford.edu
philip@pescadero.Stanford.EDU (Philip Machanick) (12/19/90)
In article <1990Dec18.214229.28951@Neon.Stanford.EDU>, philip@pescadero.Stanford.EDU (Philip Machanick) writes: |> In article <CLINE.90Dec18151352@cheetah.ece.clarkson.edu>, cline@cheetah.ece.clarkson.edu (Marshall Cline) writes: |> |> Given N types of Operands, there'll be N^2 `add' routines: Int+Matrix, |> |> Int+Sparse, Int+Int, etc. |> Shouldn't that be N! (factorial)? No, it shouldn't - thanks to Charles Allen for the correction. -- Philip Machanick philip@pescadero.stanford.edu
horstman@sjsumcs.sjsu.edu (Cay Horstmann) (12/20/90)
In article <1990Dec18.214229.28951@Neon.Stanford.EDU> philip@pescadero.stanford.edu writes: >In article <CLINE.90Dec18151352@cheetah.ece.clarkson.edu>, cline@cheetah.ece.clarkson.edu (Marshall Cline) writes: >|> Given N types of Operands, there'll be N^2 `add' routines: Int+Matrix, >|> Int+Sparse, Int+Int, etc. >Shouldn't that be N! (factorial)? >-- >Philip Machanick Indeed there are N^2. (N^k for a k-ary operation.) For example, if N ==2, there are Int * Int, Int * Matrix, Matrix * Int, Matrix * Matrix. (* is a lot more realistic that +, unless you like the APL interpretation). This question on double dispatching pops up every few months, so let me make a plug for my C++ book (Horstmann, Mastering C++, Wiley) which discusses it in the last chapter. Anything to get those royalty $$$ rolling... Cay