Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #9: Visitors    

Review: What are visitors for?

Visitors simply provide another style for writing code. They are the result of our continued goal of abstracting out the invariant code from computations. With visitors, the invariant code is essentially the template's code, choosing among the different data type options. We've typically packaged this code into a function called execute.

Within the context so far, the benefits may seem a bit unclear. While it may follow from one of our goals, the resulting code is arguably no clearer or shorter than without visitors. A bigger benefit is realized once we change contexts. In object-oriented languages, this execute function can be replaced by a built-in language feature called dynamic dispatching. Working with visitors now is part of a segue towards object-oriented programming.

List visitors

List visitor exercises

The following is the code for using visitors on lists, as seen in class. 

  ;; A Visitor is a structure made up of two functions
  ;; One for the base case and 
  ;; one for the inductive case.
  (define-struct listVisitor (fBase fInduct))

  ;; list-execute: list-of-any1 listVisitor any2 --> any3
  ;; Executes ("accepts") the visitor on the list returning the result.
  ;; param is passed to the visitor unmodified.
  ;; The base case of the listVisitor is called on the empty list:
  ;;   listVisitor-fBase: list-of-any1 any2 --> any3
  ;; The inductive case is called on the non-empty list.
  ;;   listVisitor-fInduct: list-of-any1 any2 --> any3

  (define (list-execute a-list visitor param)
    (cond
        [(empty? a-list) ((listVisitor-fBase visitor) a-list param)]
        [(cons? a-list) ((listVisitor-fInduct visitor) a-list param)]))

Develop the visitor-style versions of the following functions. You've written most of these in a non-visitor style before, and you should use the same algorithms as before.

  1. length
  2. map
  3. append
  4. foldl

Other visitors

Visitors are not specific to lists. The visitor style is just another way of packaging the same information as in a template.

List visitor exercises

  1. Create the natVisitor type and nat-execute for natural numbers.

  2. Develop a visitor-style version of the sum of the numbers 0..n.

  3. Create the visitor types and execute functions for descendant trees. 

             ;; A Person is a structure
         ;; where name is their name, year is their birth year
         ;; and kids is a list the person's children.
         ;; (make-Person symbol num list-of-Persons)
         (define-struct Person (name year kids))

         ;; A list-of-Persons is either
         ;; - empty
         ;; - (cons Person list-of-Persons)

  4. Develop the visitor-style versions of the functions countKids and atleastNkids. 

             ;; countKids: list-of-Persons --> num
         ;; Counts the number of Persons in the list.

         ;; atLeastNKids: Person num --> list-of-sym
         ;; Returns a list of names of all descendents, including the person,
         ;; who have at least n kids.

Last Revised Tuesday, 24-Aug-2004 13:49:15 CDT

©2004 Stephen Wong and Dung Nguyen