16 Visitors

Here is a high-level outline of what we covered in class today. Below is the code we wrote. These notes will be fleshed out soon—we’re posting them in this unfinished form now so they can help you work on your assignment.

16.1 The Visitor Pattern

The visitor pattern is a general design pattern that allows you to seperate data from functionality in an object-oriented style.

For instance, suppose you want to develop a library of ranges. Users of your library are going to want a bunch of different methods, and in principal, you can’t possibly know or want to implement all of them. On the other hand, you may not want to expose the implementation details of how you chose to represent ranges.

The visitor pattern can help—it requires you to implement one method which accepts what we call a "visitor" that is then exposed to a view of the data. Any computation over shapes can be implemented as a visitor, so this one method is universal—no matter how people want to use your library, this one method is enough to ensure they can write whatever computation they want. What’s better is that even if you change the representation of ranges, so long as you provide the same "view" of the data, everything will continue to work.

So here is our data definition for ranges:

We will add a single method to the interface for ranges:

We haven’t said what is in the [IRangeVisitor X] interface, but the key idea is that something that implements a [IRangeVisitor X] represents a computation over ranges that computes an X. So for example, if we wanted to compute where a number is included in a range, we would want to implement the [IRangeVistitor Boolean] interface since that computation would produce a yes/no answer.

The idea, in general, of the visitor pattern is that the visitor will have a method for each variant of a union. And the method for a particular variant takes as many arguments as there are fields in that variant. In the case of a recursive union, the method takes the result of recursively visiting the data.

Under that guideline, the [IRangeVisitor X] interface will contain 3 methods:

Notice that the contracts for lo and hi-range match the contracts on the constructors for each variant, but rather than constructing a Range, we are computing an X. In the case of union-range, the method takes two inputs which are Xs, which represent the results of visiting the left and right ranges, respectively.

Now we need to implement the visit method in each of the Range classes, which will just invoke the appropriate method of the visitor on its data and recur where needed:

We’ve now established the visitor pattern. Let’s actually construct a visitor that does something.

We forgot to implement the in-range? method, but no worries – we dont’ need to edit our class definitions, we can just write a visitor that does the in-range? computation, which is an implementation of [IRangeVisitor Boolean]:

Now if we have our hands on a range and want to find out if a number is in the range, we just invoke the visit method with an instance of the in-range?% class:

16.2 Generators

generator-bad.rkt

#lang class/2

(require 2htdp/image class/universe)

;; A World is (world% Generator Number)

;; and implements IWorld

(define-class world%

(fields generator num)

;; to-draw : -> Scene

(define (to-draw)

(overlay

(text (number->string (field num)) 20 "black")

(empty-scene 500 500)))

;; on-key : Key -> World

(define (on-key k)

(world% (field generator)

((field generator) . pick))))

;; A Generator is a (generator% [Listof Number])

;; and implements

;; pick : -> Number

;; produce a number to show that isn't in bad

(define-class generator%

(fields bad)

(define (pick)

(local [(define x (random 10))]

(cond [(member x (field bad)) (pick)]

[else x]))))

(check-expect (<= 0 ((generator% empty) . pick) 10) true)

(check-expect (= ((generator% (list 4)) . pick) 4) false)

(big-bang (world% (generator% empty) 0))

generator-register.rkt

#lang class/2

(require 2htdp/image class/universe)

;; A World is (world% Generator Number)

;; and implements IWorld

(define-class world%

(fields generator num)

;; to-draw : -> Scene

(define (to-draw)

(overlay

(text (number->string (field num)) 20 "black")

(empty-scene 500 500)))

;; on-key : Key -> World

(define (on-key k)

(cond [(key=? k "x")

(local [(define g ((field generator) . add-bad (field num)))]

(world% g (g . pick)))]

[else

(world% (field generator)

((field generator) . pick))])))

;; A Generator is a (generator% [Listof Number])

;; and implements

;; pick : -> Number

;; produce a number to show that isn't in bad

;; add-bad : Number -> Generator

;; produce a generator like that with an additional bad number

(define-class generator%

(fields bad)

(define (add-bad n)

(generator% (cons n (field bad))))

(define (pick)

(local [(define x (random 10))]

(cond [(member x (field bad)) (pick)]

[else x]))))

(check-expect (<= 0 ((generator% empty) . pick) 10) true)

(check-expect (= ((generator% (list 4)) . pick) 4) false)

(check-expect (= (((generator% empty) . add-bad 4) . pick) 4) false)

(big-bang (world% (generator% empty) 0))

generator-initial.rkt

#lang class/3

(require 2htdp/image class/universe)

;; A World is (world% Generator Number)

;; and implements IWorld

(define-class world%

(fields generator num)

;; to-draw : -> Scene

(define (to-draw)

(overlay

(text (number->string (field num)) 20 "black")

(empty-scene 500 500)))

;; on-key : Key -> World

(define (on-key k)

(cond [(key=? "x" k)

(begin ((field generator) . tell-bad)

(world% (field generator)

((field generator) . pick)))]

[else

(world% (field generator)

((field generator) . pick))])))

;; A Generator is a (generator% [Listof Number] Number)

;; interp: the list of bad numbers, and the last number picked

;; and implements

;; pick : -> Number

;; produce a number to show not in the list

;; tell-bad : ->

;; produces nothing

;; effect : changes the generator to add the last number picked to the bad list

(define-class generator%

(fields bad last)

(define (tell-bad)

(set-field! bad (cons (field last) (field bad))))

(define (pick)

(local [(define rnd (random 10))]

(cond [(member rnd (field bad)) (pick)]

[else (begin

(set-field! last rnd)

rnd)]))))

(check-expect (<= 0 ((generator% (list 2 4 6) 0) . pick) 100) true)

(big-bang (world% (generator% (list 2 4 6) 0) 0))

(check-expect (member ((generator% (list 2 4 6) 0) . pick)

(list 2 4 6))

false)

(define (tell-bad-prop g)

(local [(define picked (g . pick))]

(begin (g . tell-bad)

(not (= picked (g . pick))))))

(check-expect (tell-bad-prop (generator% (list 1 2 3) 0)) true)

generator-mutate.rkt

#lang class/3

(require 2htdp/image class/universe)

;; A World is (world% Generator Number)

;; and implements IWorld

(define-class world%

(fields generator num)

;; to-draw : -> Scene

(define (to-draw)

(overlay

(text (number->string (field num)) 20 "black")

(empty-scene 500 500)))

;; on-key : Key -> World

(define (on-key k)

(cond [(key=? k "x")

(world% (field generator)

((field generator) . pick-bad))]

[else

(world% (field generator)

((field generator) . pick))])))

;; A Generator is a (generator% [Listof Number] Number) ;; interp: numbers not to pick, last number picked ;; and implements ;; pick : -> Number ;; produce a number to show that isn’t in bad ;; pick-bad : -> Number ;; pick a number to show, and remember that the last one was bad (define-class generator% (fields bad last) (define (pick-bad) (begin (set-field! bad (cons (field last) (field bad))) (pick))) (define (pick) (local [(define x (random 10))] (cond [(member x (field bad)) (pick)] [else (begin (set-field! last x) x)]))))

(check-expect (<= 0 ((generator% empty 0) . pick) 10) true) (check-expect (= ((generator% (list 4) 0) . pick) 4) false)

(big-bang (world% (generator% empty 0) 0)) )