CS247 Lecture 20

Last Time: Multiple Inheritance

This Time: D in SOLID, Visitor Pattern

Dependency Inversion Principle: High level modules (closer to main) should not depend on low-level modules (simpler tasks)- instead, each should depend on an abstraction.

Abstract classes should not depend on concrete classes.

Example: Microsoft word. Word counter $\to$ rely on some sort of keyboard input. Breaks dependency inversion principle because counting words is “high-level”, getting input “low-level”.

Another example: Timer, lights/bell that goes off

Apply dependency inversion once ⇒ Timer should no longer rely directly on Bell.

Abstract Responder class shouldn’t depend on concrete Timer. So apply dependency inversion again.

This is simply the observer pattern - where Sources are subjects, Responders are observers.

We could apply dependency inversion again $\to$ introduce another layer of abstraction between Timer and bell/lights - but at some point, usefulness runs out. Too many layers of abstraction creates needless complexity.

---

Visitor Design Pattern (AMAZON INTERVIEW QUESTION) Problem: How do we write a method that depends on two polymorphic types?

Example:

We might want different behaviours for each combination of these concrete classes.

class Weapon {
	public:
		virtual void strike(Enemy& e) = 0;
};

We can override this in Rock and Stick - but we don’t know which enemy we’re hitting. Same problem exists in reverse, if we implement it inside Enemy. We don’t know what kind of weapons we are using.

Solution: Visitor Pattern - Combine overloading with overriding.

class Enemy{
	public:
		virtual void beStruckBy(Weapon& w) = 0;
		...
};
 
class Monster: public Enemy{
	public: 
		void beStruckBy(Weapon& w){
			w.strike(*this); // *this decided during compile time
		}
};
 
class Turtle: public Enemy{
	public:
		void beStruckBy(Weapon& w){
			w.strike(*this);
		}
};
 
class Weapon{
	public:
		virtual void strike(Monster& m) = 0;
		virtual void strike(Turtle& t) = 0;
};
 
class Rock: public Weapon{
	public:
		void strike(Monster& m) override{
			cout << "Rock + Monster" << endl;	
		}
		void strike(Turtle& t) override{
			cout << "Rock vs. Turtle" << endl;
		}
}; // Stick looks similar
 
Enemy* e = ...;
Weapon* w = ...;
e->beStruckBy(*w);

1. beStruckBy is a virtual function → either calling Monster::beStruckBy or Turtle::beStruckBy (runtime).
2. Call w.strike on the Weapon&. Strike is virtual→ Rock::Strike or Stick::Strike (runtime).
3. Are we calling Rock::Strike(Turtle&) or Rock::Strike(Monster&)? We know the type of this. If this is a Turtle* → call turtle version, if this is a Monster* → call monster version. (compile time) $\to$ This achieves double dispatch. Very powerful technique that combines overloading with overriding.

Basically the dynamic type of Weapon and Enemy will both decide which exact function will be called.

Double Dispatch

Double dispatch is a way to dynamically determine the operation to perform based on both the runtime types of two objects. In your example, it’s used to determine the correct operation (strike) to perform based on the combination of an Enemy and a Weapon.

Another use of the Visitor Pattern - add behaviour and functionality to classes, without changing the classes themselves.

Compile-time Dispatch

Compile-time Dispatch: The compile-time dispatch is achieved by calling the correct Weapon’s strike method based on the dynamic type of this. If this is a Turtle*, the Turtle version of strike is called, and if it’s a Monster*, the Monster version is called.

Example: Compiler Design

I might want to collect information about my AST. I could add a virtual method in ASTNode, override in concrete classes. … But → lots of changes scattered over many classes. Difficult to understand, harder to implement incrementally.

Instead: provide nodes an accept method, taking in a polymorphic AST Visitor.

class ASTNode{ // Like Enemy
	public:
		virtual void accept(ASTVisitor& a) = 0; // Like beStruckBy
};
 
class IfStatement: public ASTNode{
	public:
		void accept(ASTVisitor& a){
			a.visit(*this);
			//Call accept on subnodes in our ifStatement (boolean expression, block of statemnts in ifStatement)
		}
};
 
class ASTVisitor{ // Like Weapon
	virtual void visit(IfStatement& i) = 0;
	virtual void visit(WhileStatement& w) = 0;
	...
	for each ASTNode
};

Now, we can write different types of visitors to work on the parse tree. For example:

• String Visitor $\to$ Collect string literals in program, that must go in the DATA segment.
• Scope Visitor $\to$ Match variables with associated scope.
• CodeGeneration Visitor $\to$ Generates assembly for each given Node.

Solution improves cohesiveness $\to$ all code for a particular visiter is located in one class. New visitors are easy to create, and can be made with zero changes to the AST.

Next: CS247 Lecture 21