Double dispatch

[shadowmouse]

I'm making a binary tree as well as various different classes that act upon it, with the idea being that the tree itself would be separated from the actions that can be done to it, so that the project would be more easily extensible. However seeing as nodes with no descendants have to act differently to those with one descendant, which are different to those with two, I have four classes, Node (base class), LeafNode, UnaryNode and BinaryNode. My problem is that because of this, I've had to implement double dispatch by adding a new virtual function into the classes for every action that has to be done to the tree. Is there any way to avoid this? Basically what I'm asking, is there a neat way to write double dispatch so that the classes aren't full of functions which each correspond to a function in a different class.

This is what the declaration of the classes has become, and I haven't even declared all of the methods that will be required yet. Also, is it possible to hide the code under a spoiler tag? I tried [spoiler][/spoiler], but it didn't work.

class ParseNode {
public:
    virtual bool isConstant() const = 0;
    virtual const std::string& getLexeme() const = 0;
    virtual const LexicalClass& getClassification() const = 0;
    virtual std::string getFullExpression() const = 0;
    virtual void getSymbolInformation(SymbolTable& symbolTable) const = 0;
    virtual void replace(const std::string& lexeme, const Token& information) = 0;
    virtual std::unique_ptr<ParseNode> optimise(Optimiser& optimiser) = 0;
    virtual ~ParseNode() = default;
};

class LeafNode: public ParseNode {
public:
    /**
     * \brief Basic Constructor
     *
     * \param token A Token containing the lexical information of the LeafNode.
     */
    LeafNode(const Token& token);

    /**
     * \brief Returns whether or not the value of the LeafNode is constant.
     */
    virtual bool isConstant() const override;

    /**
     * \brief Returns a const reference to the lexeme stored within the LeafNode.
     */
    virtual const std::string& getLexeme() const override;
    virtual const LexicalClass& getClassification() const override;
    virtual std::string getFullExpression() const override;
    virtual void getSymbolInformation(SymbolTable& symbolTable) const override;
    virtual void replace(const std::string& lexeme, const Token& information) override;
    virtual std::unique_ptr<ParseNode> optimise(Optimiser& optimiser) override;
    virtual ~LeafNode() override = default;
private:
    LexicalClass m_Classification;
    std::string m_Lexeme;
};

class UnaryNode: public ParseNode {
public:
    UnaryNode(const Token& token, std::unique_ptr<ParseNode> descedant);
    virtual bool isConstant() const override;
    virtual const std::string& getLexeme() const override;
    virtual const LexicalClass& getClassification() const override;
    virtual std::string getFullExpression() const override;
    virtual void getSymbolInformation(SymbolTable& symbolTable) const override;
    virtual void replace(const std::string& lexeme, const Token& information) override;
    virtual std::unique_ptr<ParseNode> optimise(Optimiser& optimiser) override;
    virtual ~UnaryNode() override = default;
private:
    LexicalClass m_Classification;
    std::string m_Lexeme;
    std::unique_ptr<ParseNode> m_Descendant;
};

class BinaryNode: public ParseNode {
public:
    BinaryNode(const Token& token, std::unique_ptr<ParseNode> left, std::unique_ptr<ParseNode> right);
    virtual bool isConstant() const override;
    virtual const std::string& getLexeme() const override;
    virtual const LexicalClass& getClassification() const override;
    virtual std::string getFullExpression() const override;
    virtual void getSymbolInformation(SymbolTable& symbolTable) const override;
    virtual void replace(const std::string& lexeme, const Token& information) override;
    virtual std::unique_ptr<ParseNode> optimise(Optimiser& optimiser) override;
    virtual~BinaryNode() override = default;
private:
    LexicalClass m_Classification;
    std::string m_Lexeme;
    std::unique_ptr<ParseNode> m_LeftDescendant;
    std::unique_ptr<ParseNode> m_RightDescendant;
};
}

[coder777]

What is this 'double dispatch'? All you showed are classes with a unified interface that should be easily used with a pointer to the base class.

Also, is it possible to hide the code under a spoiler tag?

What does that mean? If you don't want to post certain code don't post it?

[shadowmouse]

What I mean is the following instance:

class Object {
public:
    virtual void ModifierA(ModifierA& a) =0;
    virtual void ModifierB(ModifierB& b) =0;
    //etc..
};

class SubX: public Object{
public:
    void ModiferA(ModifierA& a) { a.Modify(*this);} //These functions have to be put in all the derived classes because they have to pass themselves not as a pointer to base class, but as a derived object, hence choosing a different overload based on their derived type
    void ModiferB(ModifierB& b) { b.Modify(*this);}
};

class SubY: public Object {
public:
    void ModiferA(ModifierA& a) { a.Modify(*this);}
    void ModiferB(ModifierB& b) { b.Modify(*this);}
};

class ModifierA {
public:
    Modify(Object& o) {o.ModifierA(*this);}
    Modify(SubX&) {/*Do something specific to a SubX*/}
    Modify(SubY&) {/*Do something specific to a SubY*/}
};

class ModifierB {
public:
    Modify(Object& o) {o.ModifierB(*this);}
    Modify(SubX&) {/*Do something specific to a SubX*/}
    Modify(SubY&) {/*Do something specific to a SubY*/}
};

This is an example where you have Object, SubX and SubY, which are basically data carrying classes, and ModiferA and ModiferB, which act upon SubX and SubY. However because SubX has to be treated differently to SubY, the only way to do that without using dynamic casting and type enums or RTTI, is to do multiple dispatch. The idea is that an Object is passed into Modify(Object&), which calls a virtual function in SubX or SubY, which chooses a different overload of Modify, depending on whether the Object& was actually referring to a SubX or SubY. This works and isn't too bad when you don't have many classes. But when you have lots of classes inheriting from Object and lots of modifying classes, it gets messy, so I was asking if there was a cleaner way of achieving the same goal. And yes, I know that code needs forward declarations, but it's meant to demonstrate something, not implement it.

And what I meant about spoiler tags, is that in other forums, if your code is long and you don't want it to affect the readability of the post, you put it in [spoiler][/spoiler] tags, which create a hide/show button for the code.

[tipaye]

Hi @shadowmouse, I don't quite follow what you're trying to do. Forgive me for being dense, but it appears this is how the language already works. I'm struggling to see the need for these Modifier classes.

#include <iostream>

class Object
{
public:
	virtual void Modifier() = 0;
	virtual ~Object() = 0;
};

Object::~Object() {}

class SubX : public Object
{
	void Modifier() { std::cout << "SubX!" << std::endl; }
};

class SubY : public Object
{
	void Modifier() { std::cout << "SubY!" << std::endl; }
};

void UseObject(Object &anObject)
{
	anObject.Modifier();
}

int main()
{
	SubX anX;
	SubY aY;
	
	UseObject(anX);
	UseObject(aY);
	
	return (0);
}

Functionality specific to a class belongs in the class. The point of line 22 in your previous post is that you shouldn't need lines 23 and 24. As it is, line 22 is unreachable, because Object is abstract, and the dynamic type will always be SubX or SubY. I think if you forcibly pass an "Object &" to Modify(), you're likely to end up in an infinite loop of callbacks.

Trying to simplify your example for my own sake, I get:

#include <iostream>
#include <vector>

using namespace std;

class Object {
public:
    virtual void Modifier() = 0;
    //etc..
};

class SubX: public Object{
public:
	void Modifier() { cout << __PRETTY_FUNCTION__ << endl; }
};

class SubY: public Object {
public:
	void Modifier() { cout << __PRETTY_FUNCTION__ << endl; }
};

class Modifier {
public:
    void Modify(Object& o) { o.Modifier(); }
};

// Just demonstrating usage here.
int main()
{
	SubX x;
	SubY y;
	
	Modifier m;
	
	m.Modify(x);
	m.Modify(y);

	vector<Object *> vo;
	
	for ( int i = 0; i < 10; ++i)
	{
		if (i%2)
		{
			vo.push_back(new SubX);
		}
		else
		{
			vo.push_back(new SubY);
		}
	}
	
	for (auto obj : vo)
	{
		m.Modify(*obj);
	}
	
	for (auto obj : vo)
	{
		delete obj;
	}
	
	return (0);
}

[shadowmouse]

The reason I've been trying to do this, is that I've been trying to modularise my code, and come up with a way to pass an Object pointer to a modifier, and then have a SubX function be called if the object pointer actually points to a SubX, ot have a SubY function be called if the object pointer actually points to a SubY. The example I gave has a typo, A was meant to be ModifierA in the Modifier functions. However, with that corrected, it manages this, by using a virtual function which is defined in SubX to pick the SubX function, and one defined in SubY to pick the SubY function. This way, when a ModifierA passes itself into an object pointer's ModifierA function, the correct method will be called. My problem is that this requires the Object call to know about ModifierA and ModifierB in advance, which makes my code much less modular and extensible.
I may have come up with a solution using templates, but it's mesdy and I'll post it when I can get on my laptop.