Double Dispatch in C++
- Definition: Double dispatch is a design pattern that allows a function to call another function based on the runtime types of two different objects. Itβs often used to handle operations involving multiple object types in a type-safe and flexible way.
Key Points
-
Problem: In simple polymorphism, you can only dispatch based on the type of a single object. Double dispatch solves this by allowing you to decide on behavior based on the type of two objects involved in an operation.
-
Common Use Case:
-
Common in systems where operations involve visiting different types of elements, such as an Abstract Syntax Tree (AST) in a compiler or a visitor pattern in OOP.
-
How It Works:
- A base method in an object calls another method on another object, passing the
this
pointer or reference to help decide which method to invoke on the second object. -
This results in the second object invoking a method on the first object, ensuring the correct overload is chosen based on their runtime types.
-
Example:
- Imagine having a base
ExprAST
class with multiple derived types likeNumberExprAST
,BinaryExprAST
, etc. Double dispatch helps in selecting the correctcodegen
function based on the type of the expression and the context of its use.
Example Code:
#include <iostream>
using namespace std;
// Base class for expressions
class ExprAST {
public:
virtual ~ExprAST() = default;
virtual void accept(class Visitor& v) const = 0; // Pure virtual function for visitor pattern
};
// Derived class for NumberExpr
class NumberExprAST : public ExprAST {
public:
int value;
NumberExprAST(int val) : value(val) {}
void accept(Visitor& v) const override; // Accept method for double dispatch
};
// Derived class for BinaryExpr
class BinaryExprAST : public ExprAST {
public:
ExprAST* left;
ExprAST* right;
BinaryExprAST(ExprAST* l, ExprAST* r) : left(l), right(r) {}
void accept(Visitor& v) const override; // Accept method for double dispatch
};
// Visitor class that handles different types of expressions
class Visitor {
public:
virtual void visit(const NumberExprAST& expr) const {
cout << "Visiting NumberExprAST with value: " << expr.value << endl;
}
virtual void visit(const BinaryExprAST& expr) const {
cout << "Visiting BinaryExprAST" << endl;
expr.left->accept(*this); // Dispatch to the left operand
expr.right->accept(*this); // Dispatch to the right operand
}
};
// Implementations of the accept methods
void NumberExprAST::accept(Visitor& v) const {
v.visit(*this);
}
void BinaryExprAST::accept(Visitor& v) const {
v.visit(*this);
}
int main() {
NumberExprAST num(42);
BinaryExprAST bin(&num, &num);
Visitor visitor;
bin.accept(visitor); // Initiates double dispatch
return 0;
}
Benefits:
- Flexibility: Can easily extend operations without altering the existing classes.
- Decoupling: Allows new operations to be added without modifying the base classes, adhering to the Open/Closed Principle.
Drawbacks:
- Complexity: More intricate code due to the need for additional visitor classes.
- Performance: More dynamic dispatch calls can impact performance if not carefully managed.
When to Use:
- When you need to implement operations that vary based on the types of multiple objects.
- When working with the Visitor Pattern to implement operations on elements of a composite structure, such as ASTs in a compiler.
Best Practices:
- Keep visitor classes clean and focused on handling specific behaviors.
- Ensure classes implementing double dispatch follow the Single Responsibility Principle to keep code manageable.
My code
// Base class
class ExprAST {
public:
virtual ~ExprAST() = default;
// Virtual codegen function to be overridden by derived classes
virtual llvm::Value* codegen(CodeGen& codegenObj) const = 0;
};
// Derived class example
class NumberExprAST : public ExprAST {
public:
llvm::Value* codegen(CodeGen& codegenObj) const override {
return codegenObj.codegen(*this);
}
};
// CodeGen implementation
llvm::Value* CodeGen::codegen(const ast::ExprAST& exprAst) {
// Double dispatch: calls the correct codegen implementation
return exprAst.codegen(*this);
}
// Specialized codegen for NumberExprAST
llvm::Value* CodeGen::codegen(const ast::NumberExprAST& numExpr) {
// Handle NumberExprAST-specific logic here
return ...; // Generate LLVM IR
}