[HD] EECS4302 F26 - 2026-10-20 (Tuesday) - Lecture 10

Overview

Jackie Wang reviews course deadlines, then explains the Visitor pattern for recursive language structures, including its class architecture, `accept` implementation, and double dispatch through an evaluator processing an expression tree. The lecture connects the pattern to the Open-Closed and Single Choice principles, while also outlining preparation for the November 5 programming test, the November 19 written test, ANTLR 4 assignment work, and upcoming DFA minimization.

Key takeaways

A Visitor design pairs every concrete structure class, such as `Addition`, with a corresponding method such as `visitAddition` in each operation class.
Double dispatch first selects a structure’s `accept` implementation using the structure object’s dynamic type, then selects a Visitor implementation using the Visitor object’s dynamic type.
The `accept(Visitor)` parameter should use the general Visitor type; operation-specific methods such as an evaluator’s `result()` require the concrete type because the Visitor interface does not declare them.
Recursive evaluation processes each child expression with a Visitor and combines the child results; the same pattern extends from left/right fields to arrays of child nodes.
Visitor favors stable language structures and extensible operations: adding a new operation requires one new Visitor class, while adding a language construct changes the Visitor interface and every concrete operation.
The course’s key upcoming dates are the November 5 programming test, the November 19 written test, and project milestone 1 around November 9.

Chapters

0:00 Fall 2026 Calendar: Tests, Assignment 2, and Project Milestone 1

The programming test is scheduled for November 5, with a guidance PDF, sample test, and possible lab-based mock test planned.
The written test is scheduled for November 19 and will run for 80 minutes in class using paper and pen.
Project milestone 1 is due around November 9; the 1% and 2% milestones are intended to provide feedback and catch teams going off track.
Students are encouraged to work through Assignment 2 alongside the ANTLR 4 tutorial.

3:00 Written-Test Preparation: Lexical Analysis and DFA Conversion

The in-class lexical analysis material still to complete includes DFA minimization and assembling the components into a scanner.
A self-guided lecture covers formal regular-language tools, including regular expressions to epsilon-NFAs and epsilon-NFAs to DFAs.
The lecture site provides recordings, annotated notes, templates, digests, and YouTube timestamps for targeted review before November 19.

7:00 Office Hours and the Visitor Pattern’s Place in the Course

The Thursday-before-reading-week lecture on the Open-Closed Principle is part of written-test and exam coverage.
Visitor is presented as a standard compiler design pattern, with concepts that can be compared against ANTLR 4 generated code.
Weekly office hours are Monday and Thursday at 2:00 p.m.; students are advised to raise project or assignment issues early.

9:13 Visitor Architecture: Separate Language Structures and Operations

The design divides classes into a language-structure package and a language-operation package.
The structure side uses a Composite hierarchy for recursive expression trees; the operation side groups related behaviors.
The expression interface declares `accept(Visitor)`, connecting the two packages through a client-supplier relationship.
The `accept` parameter uses the general `Visitor` type, allowing evaluator, pretty-printer, or type-checker instances through polymorphism.

13:05 Visitor Method Mapping: One Visit Method per Structure Type

The example structure classes are `Constant`, `Addition`, and `Subtraction`.
Each structure class has a matching method such as `visitConstant`, `visitAddition`, or `visitSubtraction` in every operation class.
Named visit methods make the target structure explicit; method overloading is an alternative in languages such as Java.
The Visitor interface declares the full set of visit methods that concrete operation classes must implement.

18:00 Operation Classes and Operation-Specific Results

Each Visitor subclass represents a recursive operation over the Composite tree, such as evaluation, pretty-printing, or type checking.
Concrete operation classes can add their own methods, such as an integer result for evaluation, string result for printing, or boolean result for type checking.
Putting differently typed results in the common Visitor interface may require returning `Object` and casting, a trade-off that weakens type safety.
A useful design exercise is to draw both the Composite hierarchy and its matching Visitor classes from scratch.

22:00 Implementing `accept`: Dispatch by Structure Type

Each concrete structure implements `accept` with a single call to its matching Visitor method.
For example, `Constant.accept(v)` calls `v.visitConstant(this)`, passing the current structure object as the argument.
`Addition` and `Subtraction` follow the same pattern with `visitAddition(this)` and `visitSubtraction(this)`.
The method name is selected from the structure class being implemented, while `this` supplies that concrete expression.

27:50 Visitor Test Setup: Static Types, Dynamic Types, and Result Casting

In the example test, a variable declared as `Visitor` is assigned `new Evaluator()`, so its static type is Visitor and its dynamic type is Evaluator.
The expression variable `at` holds the root of the Composite expression and receives the operation through `at.accept(v)`.
Calling `result()` directly on `v` does not compile because `Visitor` does not declare that operation-specific method.
The test must cast to `Evaluator` to access its integer result method.

32:50 Building the Expression Tree for `1 + 2`

The example creates two separate `Constant` objects, one containing 1 and the other containing 2.
An `Addition` object stores references to those constants as its left and right children.
The root variable has a general Composite expression type, while the runtime object at the root is an `Addition`.
A suggested practice exercise is to construct a more complex tree such as `1 + 2 + 3`.

39:20 Double Dispatch: First Select the Structure’s `accept` Method

The call `at.accept(v)` begins double dispatch, meaning dynamic method binding determines a method implementation twice.
The first dispatch selects the concrete `accept` implementation using the dynamic type of the context object to the left of the dot.
Because `at` refers to an `Addition` object, the runtime invokes `Addition.accept`.
When explaining dispatch, identify the context object and its runtime type rather than relying on informal descriptions of references.

45:50 Second Dispatch: Choose `Evaluator.visitAddition`

`Addition.accept` executes `v.visitAddition(this)`, creating the second method call in the dispatch sequence.
The `Visitor` interface defines the method signature, but concrete implementations exist in Evaluator, PrettyPrinter, and TypeChecker.
Since `v` has dynamic type `Evaluator`, the second dispatch invokes `Evaluator.visitAddition`.
For each dispatch, determine the context object at that exact point and use its dynamic type to identify the implementation.

50:50 Recursive Evaluation of Addition’s Left and Right Subtrees

`Evaluator.visitAddition` retrieves the Addition node’s left and right expressions with `getLeft()` and `getRight()`.
It creates separate evaluator instances for the two child expressions and calls `accept` on each subtree.
Each child’s Visitor result is combined to produce the result for the full addition expression.
If a node stores an array of children instead of two fields, the same recursive approach can iterate over the array and collect results.

57:00 Tracing Nested Dispatch and Practicing with More Complex Trees

Calling `accept` on a constant child first selects `Constant.accept`, because the child’s dynamic type is Constant.
The second dispatch then selects the appropriate visit method using the dynamic type of the local evaluator, such as `evaluatorLeft`.
Students are advised to trace both child calls in writing and extend the tree with nested additions or subtractions.
The same two-step reasoning applies recursively at every level of the expression tree.

1:04:00 Open-Closed Principle: Stable Structures, Extensible Operations

Adding a new language construct such as Multiplication requires a new Composite class, a new Visitor method, and matching implementations in every operation class.
That change touches multiple classes, so the Visitor pattern is a poor fit when the language’s structure changes frequently.
Adding a new operation such as assembly generation requires one new Visitor subclass that implements behavior for every existing structure.
Visitor works best when language structures are stable and operations are expected to grow, preserving the Single Choice principle for new operations.

Transcript excerpt

0:05 All right, welcome back. Hope everybody had a good reading week, had a good rest. So, we got 7 more weeks to go. Definitely a lot is is to happen still. I would suggest we revisit the semester calendar very quickly just to see what we can expect and I do have some important announcement to really share with you. You definitely want to keep in mind. Okay. First of all, [clears throat] let's start with the semester calendar. Okay. Okay, so if you go to the lecture site and then look at the semester calendar over here. I believe the exam schedule should be out very soon. Okay, but I don't know yet, but should be out very soon. As soon as I know that's official, I'll share with you. Okay. Okay, so now we are here.

0:56 Oh. I'm so Okay, I'm so sorry. That's a different semester. Okay, my bad. Okay. Fall 26, of course. All right, there we go. Sorry about that. All right, [snorts] so now we are on 20th of October here. And just don't forget about your assignment number two. I would say for now the ANTLR 4 tutorial, hopefully everybody at least started with that and you definitely want to use assignment number two, try to complete it along and use that as the best opportunity to really get yourself familiar. Okay, I I'll tell you how why it is so important. Your programming test is actually coming on the 5th of November. Okay. So, I'm going to let you know exactly the logistics, but that's something we

1:43 already set on day one of the semester. Okay. So, programming test will be on 5th of November. It's about more than slightly more than 2 weeks away. Okay. I'll definitely give you guys some

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.