Lab 12: Dispatching Visitors
Intro
You’ll work in this lab with ad-hoc partners.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You should start this lab with this project skeleton. Unzip the file into your IdeaProjects directory and open it with IntelliJ to get started.
Recall
Operations on union data definitions often require case analysis. Last semester, we handled all cases in one place. For example:
;; A [Listof X] is one of: ;; - '() ;; - (cons X [Listof X]) (define (list-template l) (cond [(empty? l) ...] [(cons? l) (... (first l) ... (list-template (rest l)))])) ;; list-sum : [Listof Number] -> [Listof Number] ;; Sum the elements of the given list of numbers. (check-expect (list-sum '()) 0) (check-expect (list-sum '(1 2 3 4)) 10) (define (list-sum l) (cond [(empty? l) 0] [(cons? l) (+ (first l) (list-sum (rest l)))]))
If we want to add more operations we just write more functions that perform case analysis on lists.
In object-oriented programming we’ve handled case analysis with methods in each of the implementing classes of some interface.
interface IList { |
Integer sum(); |
} |
|
class IntEmpty implements IList { |
public Integer sum() { return 0; } |
} |
|
class IntCons implements IList { |
Integer first; |
IList rest; |
|
IntCons(Integer first, IList rest) { |
this.first = first; |
this.rest = rest; |
} |
|
public Integer sum() { |
return this.first + this.rest.sum(); |
} |
} |
... |
IList il0 = new IntEmpty(); |
IList il1 = new IntCons(1, il0); |
IList il2 = new IntCons(2, il1); |
IList il3 = new IntCons(3, il2); |
IList il4 = new IntCons(4, il3); |
|
boolean testIListSum(Tester t) { |
return t.checkExpect(il0.sum(), 0) |
&& t.checkExpect(il4.sum(), 10); |
} |
If we want to implement new operations on ILists, we would add a method signature to the interface and implement that method in both the IntEmpty and IntCons classes. Easy.
The Problem
How do we add operations to a library that we can’t modify?
We’re all tired of writing the same old List interface and Cons, Empty classes. We should just write one and make it into a library that we can use forever and never touch again.
We can’t always predict which operations we’ll need on Lists. In this lab you’ll learn the visitor pattern: a general way to add arbitrary operations to a fixed set of related classes (e.g. Empty and Cons).
The Solution
We have learned how to implement case analysis for classes using double-dispatch. To solve our operation extension woes, we’ll use the same trick in a more general form.
Any operation on lists must handle empty and non-empty lists. The ListVisitor interface has a visit method for each branch of the union on which we’re operating.
interface ListVisitor<T, U> { |
U visitEmpty(); // Handle empty lists |
U visitCons(T first, List<T> rest); // Handle non-empty lists |
} |
Note: The type parameter T is the type of the elements of the list; U is the return type of the operation.
The ListVisitor interface handles the case analysis by visiting lists. The classes implementing the List interface only need to know how to accept the visitor and dispatch to the proper method.
interface List<T> { |
<U> U accept(ListVisitor<T, U> visitor); |
} |
|
class Empty<T> implements List<T> { |
public <U> U accept(ListVisitor<T, U> visitor) { |
return visitor.visitEmpty(); |
} |
} |
|
class Cons<T> implements List<T> { |
T first; |
List<T> rest; |
|
Cons(T first, List<T> rest) { |
this.first = first; |
this.rest = rest; |
} |
|
public <U> U accept(ListVisitor<T, U> visitor) { |
return visitor.visitCons(this.first, this.rest); |
} |
} |
We can easily implement list-sum as a ListVisitor.
class ListSum implements ListVisitor<Integer, Integer> { |
|
public Integer visitEmpty() { |
return 0; |
} |
|
public Integer visitCons(Integer first, List<Integer> rest) { |
return first + rest.accept(this); |
} |
|
} |
When ListSum visits an Empty list it returns 0; when it visits a Cons list it returns the sum of the first recursive result of the rest accepting the ListSum visitor.
List operations
You’re going to design a number of simple list operations as ListVisitors.
Ex 1: Design ListLength as a ListVisitor. It should work on lists with elements of any type T and return the Integer length of the list.
Ex 2: Design ListAppend as a ListVisitor. It should work on lists with elements of any type T and return the new List<T>.
Hint: List append requires an argument: the list suffix to be added to the end of the list, but we can’t modify the visiting methods’ signatures. Try making a ListAppend constructor that accepts the suffix and holds on to it in a field until it gets used in visitEmpty.
Ex 3: Design ListNth as a ListVisitor. It should work on lists with elements of any type T and return the nth element of the list, if it exists, and throw a runtime exception otherwise.
Hint: This also requires a constructor argument: the index n. You may also have to create a new ListNth visitor in the recursive accept to decrement the index as you walk the list.
Ex 4: Design ListReverse as a ListVisitor. It should work on lists with elements of any type T and return the reversed List<T> as the result. You may either use ListAppend in your implementation or give ListReverse a constructor with an accumulating argument.
Visiting binary trees
Now that we’ve had some practice writing visiting operations on Lists, you’re ready to implement your own visitor pattern for another interface and implementing classes. Here is a simple definition of generic binary trees.
interface BT<T> {} |
|
class Leaf<T> implements BT<T> {} |
|
class Node<T> implements BT<T> { |
T value; |
BT<T> left; |
BT<T> right; |
|
Node(T value, BT<T> left, BT<T> right) { |
this.value = value; |
this.left = left; |
this.right = right; |
} |
} |
Ex 5: Implement an interface BTVisitor for visiting operations on binary trees. It should have two type parameters: one for the type the tree elements and another for the result type of the operation.
Ex 6: Add an accept method to the BT interface and implementing classes that accepts BTVisitor operations with arbitrary return types.
Hint: Take another look at the List accept signature and methods if you run into issues.
Binary tree operations
Ex 7: Design BTSum as a BTVisitor. It should work on binary trees of Integers and return the Integer sum of all the values in the tree.
Ex 8: Design BTDepth as a BTVisitor. It should work on trees with values of any type T and return the Integer depth of the tree.
Ex 9: Design BTMirror as a BTVisitor. It should work on trees with values of any type T and return the mirrored BT<T> as the result.
Ex 10: Design BTInOrder as a BTVisitor. It should work on trees with values of any type T and return a List<T> of the in-order traversal of the tree. This means take the values in the left branch first, then this node’s value, then the right branch’s values.
// 4 |
// / \ |
// 2 => '(1 2 3 4) |
// / \ |
// 1 3 |
// / \ / \ |
Submission
Submit a zip file of your work at the end of lab.