TypeScript
Visitor design
Write the AST visitor with the visitor pattern.
Visitor design
The visitor pattern allows performing a separate operation for each node type while traversing a data structure. An AST visitor contains a visit method for each node type; the traverse function takes a node and calls the appropriate visit method.
interface Visitor {
visitNumber(value: number): void;
visitString(value: string): void;
visitAdd(): void;
}
function traverse(n: Node, v: Visitor): void {
switch (n.kind) {
case "number": v.visitNumber(n.value); break;
case "string": v.visitString(n.value); break;
case "add": v.visitAdd(); break;
}
}
Walking with traverse
The traverse function recursively walks the AST. For each node the relevant visit method is called; for nodes with children (e.g. add) the children are also traversed. This processes the whole tree.
function traverse(n: Node, v: Visitor): void {
switch (n.kind) {
case "number": v.visitNumber(n.value); break;
case "string": v.visitString(n.value); break;
case "add":
v.visitAdd();
traverse(n.left, v);
traverse(n.right, v);
break;
}
}
Exercise Walk the AST with a visitor
Define the Node discriminated union type ("number" (value: number), "string" (value: string), "add" (left: Node, right: Node)). Define the Visitor interface: with visitNumber(value: number): void, visitString(value: string): void, visitAdd(): void methods. Write a traverse(n: Node, v: Visitor): void function using switch. Create a Visitor implementation: visitNumber does console.log("n:" + value), visitString does console.log("s:" + value), visitAdd does console.log("add"). Call traverse({ kind: "add", left: { kind: "number", value: 1 }, right: { kind: "string", value: "x" } }, visitor).
Show example solution
type Node =
| { kind: "number"; value: number }
| { kind: "string"; value: string }
| { kind: "add"; left: Node; right: Node };
interface Visitor {
visitNumber(value: number): void;
visitString(value: string): void;
visitAdd(): void;
}
function traverse(n: Node, v: Visitor): void {
switch (n.kind) {
case "number":
v.visitNumber(n.value);
break;
case "string":
v.visitString(n.value);
break;
case "add":
v.visitAdd();
traverse(n.left, v);
traverse(n.right, v);
break;
}
}
const visitor: Visitor = {
visitNumber: (value) => console.log("n:" + value),
visitString: (value) => console.log("s:" + value),
visitAdd: () => console.log("add"),
};
traverse({ kind: "add", left: { kind: "number", value: 1 }, right: { kind: "string", value: "x" } }, visitor);
Test yourself
-
What is the core purpose of the visitor pattern?
- To hide runtime errors
- To merge node types
- To perform a separate operation for each node type
- To delete nodes
Show answer
To perform a separate operation for each node type — The visitor pattern defines a separate visit method for each node type; the traverse function calls the correct method based on the node type.
-
Visitor interface method
interface Visitor {
visitNumber(value: number): void;
visitString(value: string): void;
visit____(): void;
}
Show answer
interface Visitor {
visitNumber(value: number): void;
visitString(value: string): void;
visitAdd(): void;
}
-
Visitor design parts
- Visitor interface
- visit methods
- traverse fonksiyonu
- walks the tree
- switch (n.kind)
- calls correct visit
- özyinelemeli traverse
- processes children
Next lesson: Type guards
