Puzzle: A variation of the Visitor Pattern
The visitor pattern allows to structure programs in conventional OO languages such that a method implementation is chosen based on the type of two arguments instead of just the receiver of a message (a.k.a. the object which a method is called on).
In one of the exercises to the advanced aspects of OO programming class, we had to write a little program with an "Expression" hierarchy and an expression-evaluating visitor class, just like in this illustration:
The solution to this exercise as presented to us was to keep track of the current ongoing evaluation in the visitor by using a stack. So, each visit method looked something like this:
def visitMul(mulExp) mulExp.leftSubExpression.accept(self) mulExp.rightSubExpression.accept(self) @stack.push(@stack.pop(), @stack.pop()) end
The important invariant is: When accept or one of the visit methods are called for an expression instance, the overall effect is pushing the result of that expression's evaluation onto the stack. Consequently, by using accept recursively, the subexpressions' values can be popped from the stack afterwards.
That solution is not very elegant. There's a variation of the visitor pattern that solves the problem without using an explicit stack. Can you guess how it works?
Update: For the solution, see the third comment.
Update: Here's quite a prominent example where this is used:
TreeVisitor in the javac compiler. :-)