Interpreter Pattern Sample Code & Iterator Pattern (GoF)

This section covers the concrete C++ implementation of the Interpreter pattern using Boolean expressions, then introduces the Iterator pattern — a behavioral pattern that provides sequential access to aggregate elements without exposing internal representation.

Key Concepts

Interpreter (completion):

• VariableExp, AndExp, OrExp, NotExp, Constant form a class hierarchy implementing BooleanExp
• Three operations — Evaluate, Replace, Copy — are all forms of "interpretation" distributed over the composite tree
• Replace is an interpreter whose context is a variable name and substitution expression; its result is a new expression tree
• The distinction between Interpreter and plain Composite operations is perspective: if the class hierarchy represents a language, operations on it are interpretations
• Known uses: Smalltalk compilers, SPECTalk (input format descriptions), QOCA (constraint evaluation)

Iterator:

• Intent: Access elements of an aggregate sequentially without exposing its underlying representation
• Also known as Cursor
• Separates traversal responsibility from the aggregate into a dedicated iterator object
• Supports polymorphic iteration via abstract Iterator and abstract Aggregate classes connected by a CreateIterator() factory method
• Minimal interface: First(), Next(), IsDone(), CurrentItem()

Commands and Syntax

Interpreter — Boolean expression tree construction and evaluation:

VariableExp* x = new VariableExp("X");
VariableExp* y = new VariableExp("Y");
BooleanExp* expression = new OrExp(
    new AndExp(new Constant(true), x),
    new AndExp(y, new NotExp(x))
);
Context context;
context.Assign(x, false);
context.Assign(y, true);
bool result = expression->Evaluate(context);  // true

// Substitution via Replace
BooleanExp* replacement = expression->Replace("Y", not_z);

Iterator — external iterator usage:

List<Employee*>* employees;
ListIterator<Employee*> forward(employees);
ReverseListIterator<Employee*> backward(employees);

void PrintEmployees(Iterator<Employee*>& i) {
    for (i.First(); !i.IsDone(); i.Next()) {
        i.CurrentItem()->Print();
    }
}

Polymorphic iteration with factory method:

AbstractList<Employee*>* employees;
Iterator<Employee*>* iterator = employees->CreateIterator();
PrintEmployees(*iterator);
delete iterator;

IteratorPtr (RAII proxy for safe cleanup):

IteratorPtr<Employee*> iterator(employees->CreateIterator());
PrintEmployees(*iterator);  // auto-deleted when proxy goes out of scope

Internal iterator (ListTraverser with subclassing):

class PrintNEmployees : public ListTraverser<Employee*> {
protected:
    bool ProcessItem(Employee* const& e) {
        _count++;
        e->Print();
        return _count < _total;  // false stops traversal
    }
};

Relationships

• Interpreter + Composite: The abstract syntax tree IS a Composite; Interpreter adds the "language" interpretation perspective
• Interpreter + Visitor: All interpretation operations (Evaluate, Replace, Copy) can be refactored into separate Visitor classes
• Interpreter + Flyweight: Share terminal symbols in the AST
• Iterator + Factory Method: CreateIterator() connects parallel aggregate/iterator hierarchies
• Iterator + Composite: External iterators over recursive composites must store a traversal path; internal iterators use the call stack implicitly
• Iterator + Proxy: IteratorPtr uses the Proxy pattern (RAII) to ensure proper cleanup of heap-allocated polymorphic iterators
• Iterator + Memento: Cursor-style iterators (where aggregate controls traversal, iterator stores state) resemble Memento
• Iterator + Null Object: NullIterator (always IsDone() == true) simplifies traversal of tree structures with leaf nodes

Exam-Relevant Points

• External vs. internal iterators: External = client controls (for loop); Internal = iterator controls (applies operation to each element). External is more flexible (can compare two collections); internal is easier to use but weak in C++ without closures
• Cursor vs. iterator: When the *aggregate* defines the traversal algorithm and the iterator merely stores position, it's called a cursor
• Robust iterators register with the aggregate so insertions/deletions during traversal don't cause missed or duplicate elements
• NullIterator: IsDone() always returns true; enables uniform traversal of composites without special-casing leaf nodes
• Polymorphic iterators require heap allocation (via factory method) — use IteratorPtr (stack-allocated proxy) to prevent memory leaks
• Friend access trade-off: Making Iterator a friend of Aggregate enables efficient traversal but makes adding new traversal types harder; use protected access methods on Iterator base class instead
• Three consequences of Iterator: (1) supports traversal variations, (2) simplifies aggregate interface, (3) allows multiple concurrent traversals
• FilteringListTraverser adds a TestItem() predicate to skip elements — shows how internal iterators encapsulate iteration policies
• The Interpreter pattern should be reserved for class hierarchies you think of as defining a language — not every Composite with distributed operations qualifies