Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Principles of Object-Oriented Programming » Visitor Design Pattern

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Visitor Design Pattern

Module by: Dung Nguyen, Stephen Wong. E-mail the authors

Summary: Using the interpreter pattern to implement the overall behavior of a composite structure such as the list structure has one glaring drawback: it presents a static non-extensible interface to the client that cannot handle unforeseen future requirements. Each time a new behavior is needed to process the composite structure, new methods have to be added to the structure. As a result, the task of maintaining the code can quickly become unmanageable. The root of this problem comes from the lack of delineation between the intrinsic and primitive behaviors of the structure itself and its non-primitive application specific behaviors. The visitor design pattern offers a solution to this problem by decoupling these two kinds of behaviors into two separate systems of classes, hosts and visitors, that communicate with each other via only their public interfaces. Here the hosts are the composite structure with its invariant structural behaviors and the visitors are the infinitely varying algorithms that are to be performed on the structure. This approach turns a composite structure into a framework where control is inverted: one hands an algorithm to the structure to be executed instead of handing a structure to an algorithm to perform a computation. The structure is capable of carrying out any conforming algorithm, past, present, or future. Such a system of co-operating objects that is not only reusable and extensible, but also easy to understand and maintain.

1. Decoupling Algorithms from Data Structures

Recall the current formulation of the immutable list structure using the composite pattern.

Figure 1
Figure 1 (graphics1.png)

 

Each time we want to compute something new, we apply the interpreter pattern add appropriate methods to IList and implement those methods in MTList and NEList.  This process of extending the capability of the list structure is error-prone at best and cannot be carried out if one does not own the source code for this structure. Any method added to the system can access the private fields of MTList and NEList and modify them at will.  In particular, the code can change _fist and _rest of NEList breaking the invariant immutable property the system is supposed to represent. The system so designed is inherently fragile, cumbersome, rigid, and limited.  We end up with a forever changing IList that includes a multitude of unrelated methods.

These design flaws come of the lack of delineation between the intrinsic and primitive behavior of the structure itself and the more complex behavior needed for a specific application. The failure to decouple primitive and non-primitive operations also causes reusability and extensibility problems. The weakness in bundling a data structure with a predefined set of operations is that it presents a static non-extensible interface to the client that cannot handle unforeseen future requirements. Reusability and extensibility are more than just aesthetic issues; in the real world, they are driven by powerful practical and economic considerations. Computer science students should be conditioned to design code with the knowledge that it will be modified many times. In particular is the need for the ability to add features after the software has been delivered.  Therefore one must seek to decouple the data structures from the algorithms (or operations) that manipulate it.  Before we present an object-oriented approach to address this issue, let's first eat!

2. To Cook or Not To Cook

Mary is a vegetarian.  She only cooks and eats vegetarian food.  John is carnivorous.  He cooks and eats meat!  If Mary wants to eat broccoli and cheese, she can learn how to cook broccoli and cheese.  If she wants corn of the cob, she can learn how to cook corn on the cob.  The same goes for John.  If he wants to eat greasy hamburger, he can learn how to cook greasy hamburger.  If he wants to eat fatty hotdog, he can learn how to cook fatty hotdog.  Every time John and Mary want to eat something new, they can learn how to cook it.  This requires that John and Mary to each have a very big head in order to learn all the recipes.

But wait, there are people out there called chefs!  These are very special kinds of chefs catering only to vegetarians and carnivores.  These chefs only know how to cook two dishes: one vegetarian dish and one meat dish.  All John and Mary have to do is to know how to ask such a chef to cook their favorite dish.  Mary will only order the vegetarian dish, while John will only order the meat dish!

How do we model the vegetarian, the carnivore, the chef, the two kinds of dishes the chef cooks, and how the customer orders the appropriate kind of dish from the chef?

The Food

To simplify the problem, let's treat food as String.  (In a more sophisticated setting, we may want to model food as some interface with veggie and meat as sub-interface.)

The Food Consumers

Vegetarians and carnivores are basically the same animals.  They have the basic ingredients such as salt and pepper to cook food.  They differ in the kind of raw materials they stock to cook their foods and in the way they order food from a chef.  Vegetarians and Carnivores can provide the materials to cook but do not know how to cook!  In order to get any cooked meal, they have to ask a chef to cook for them. We model them as two concrete subclasses of an abstract class called AEater. AEater has two concrete methods, getSalt and getPepper, and an abstract method called order, as shown in the table below.

Table 1: Top-level abstract definition

public abstract class AEater {  
    public String getSalt() { 
        return "salt";
    }
    public String getPepper() { 
        return "pepper"; 
    }
    /**  
     * Orders n portions of appropriate food from restaurant r.  
     */  
    public abstract String order(IChef r, Integer n);    
    // NO CODE BODY!
}
Table 2: Concrete implementations

public class Vegetarian extends AEater{  
    public String getBroccoli() { 
        return "broccoli"; 
    }    
    public String getCorn() { 
        return "corn"; 
    }    
    public String order(IChef c, Object n) {
        // code to be discussed later;  
    }
}

public class Carnivore extends AEater{  
    public String getMeat() { 
        return "steak"; 
    }    
    public String getChicken() { 
        return "cornish hen"; 
    }   
    public String getDog() {
        return "polish sausage"; 
    }    
    public String order(IChef c, Object n) {     
    // code to be discussed later;  
    }
}

The Chef

The chef is represented as an interface IChef with two methods, one to cook a vegetarian dish and one to cook a meat dish, as shown in the table below.

Table 3: Top-level abstract definition

interface IChef  {  
    String cookVeggie(Vegetarian h, Integer n);
    String cookMeat(Carnivore h, Integer n);
}
Table 4: Concrete implementations
  
public class ChefWong implements IChef {

    public static final ChefWong Singleton
        = new ChefWong();

    private ChefWong() {}

    public String cookVeggie(
        Vegetarian h, Integer n) {
        
        return  n + " portion(s) of " +
                h.getCarrot() + ", " + 
                h.getSalt();
    }

    public String cookMeat(
        Carnivore h, Integer n) {

        return  n + " portion(s) of " +
                h.getMeat() + ", " +
                h.getPepper();
    }
}
  
public class ChefZung implements IChef {

    public static final ChefZung Singleton
        = new ChefZung();

    private ChefZung() {}

    public String cookVeggie(
        Vegetarian h, Integer n) {

        return  n + " portion(s) of " +
                h.getCorn() + ", " +
                h.getSalt();
    }

    public String cookMeat(
        Carnivore h, Integer n) {

        return  n + " portion(s) of " +
                h.getChicken() + ", " +
                h.getPepper() +
                ", " + h.getSalt();
    }
}

Ordering Food From The Chef

To order food from an IChef , a Vegetarian object simply calls cookVeggie, passing itself as one of the parameters, while a Carnivore object would call cookMeat, passing itself as one of the parameters as well.  The Vegetarian  and Carnivore objects only deal with the IChef object at the highest level of abstraction and do not care what the concrete IChef is.  The polymorphism machinery guarantees that the correct method in the concrete  IChef will be called and the appropriate kind of food will be returned to the AEater caller  The table below shows the code for Vegetarian  and Carnivore, and sample client code using these classes.

Table 5: Concrete implementations

public class Vegetarian extends AEater {
    // other methods elided
    public String order(IChef c, int n) {
        return c.cookVeggie(this, n);
    }
}

public class Carnivore extends AEater {
    // other methods elided
    public String order(IChef c, int n) {
        return c.cookMeat(this, n);
    }
}
Table 6: Client code

public void party(AEater e, IChef c, int n) {
    System.out.println(e.order(c, n));
}

    // blah blah blah...
    AEater John = new Carnivore();
    AEater Mary = new Vegetarian();
    party(Mary, ChefWong.Singleton, 2);
    party(John,ChefZung.Singleton, 1);
     

 

The above design is an example of what is called the visitor pattern.

  • The abstract class AEater and its concrete subclasses are called the hosts.  The method public String order(IChef c, Object n) is called the hook method.  Each concrete subclasses of AEater knows exactly to call the appropriate method on the IChef parameter, but does know and need not how the IChef concretely perforns its task.  This allows an open-ended number of ways to cook the appropriate kinds of food.
  • The chef interface IChef and all of  its concrete implementations are called visitors.  When an IChef performs cookMeat/cookVeggie, it knows that its host is a Carnivore/Vegetarian and can only call the methods of Carnivore/Vegetarian to cook a dish.  Java static type checking will flag an error should there be a call on the host to getCarot in the method cookMeat.  This is makes the interaction between hosts (Vegetarian and Carnivore) and visitors (IChef and all of its concrete implementations) much more robust.

3. The Visitor Pattern

The visitor pattern is a pattern for communication and collaboration between two union patterns: a "host" union and a "visitor" union.  An abstract visitor is usually defined as an interface in Java.  It has a separate method for each of the concrete variant of the host union.  The abstract host has a method (called the "hook") to "accept" a visitor and leaves it up to each of its concrete variants to call the appropriate visitor method.  This "decoupling" of the host's structural behaviors from the extrinsic algorithms on the host permits the addition of infinitely many external algorithms without changing any of the host union code.  This extensibility only works if the taxonomy of the host union is stable and does not change.  If we have to modify the host union, then we will have to modify ALL visitors as well!

Figure 2
Figure 2 (graphics2.png)

 

NOTE: All the "state-less" visitors, that is visitors that contain no non-static fields should be singletons.  Visitors that contain non-static fields should not be singletons.

4.  Fundamental Object-Oriented Design Methodology (FOODM)

  1. Identify and separate the variant and the invariant behaviors.
  2. Encapsulate the invariant behaviors into a system of classes.
  3. Add "hooks" to this class to define communication protocols with other classes.
  4. Encapsulate the variant behaviors into a union of classes that comply with the above protocols.

The result is a flexible system of co-operating objects that is not only reusable and extensible, but also easy to understand and maintain.

Let us illustrate the above process by applying it to the design of the immutable list structure and its algorithms.

  1. Here, the invariant is the intrinsic and primitive behavior of the list structure, IList, and the variants are the multitude of extrinsic and non-primitive algorithms that manipulate it, IListAlgo.
  2. The recursive list structure is implemented using the composite design pattern and encapsulated with a minimal and complete set of primitive structural operations:  getFirst() and getRest()
  3. The hook method Object execute(IListAlgo ago,  Object inp) defines the protocols for operating on the list structure. The hook works as if a IList announces to the outside world the following protocol: If you want me to execute your algorithm, encapsulate it into an object of type IListAlgo, hand it to me together with its inp object as parameters for my execute(). I will send your algorithm object the appropriate message for it to perform its task, and return you the result.
    • emptyCase(...) should be the part of the algorithm that deals with the case where I am empty.
    • nonEmptyCase(...) should be the part of the algorithm that deals with the case where I am not empty.”
  4. IListAlgo and all of its concrete implementations forms a union of algorithms classes that can be sent to the list structure for execution.

Below is the UML class diagram of the resulting list design.  Click here to see the full documentation.  Click here to see the code.

Figure 3
Figure 3 (graphics3.png)

The above design is nothing but a special case of the Visitor Pattern.  The interface IList is called the host and its method execute() is called a "hook" to the IListAlgovisitors.  Via polymorphism, IList knows exactly what method to call on the specific IListAlgo visitor.  This design turns the list structure into a (miniature) framework where control is inverted: one hands an algorithm to the structure to be executed instead of handing a structure to an algorithm to perform a computation. Since an IListAlgo only interacts with the list on which it operates via the list’s public interface, the list structure is capable of carrying out any conforming algorithm, past, present, or future. This is how reusability and extensibility is achieved.

5. List Visitor Examples

Table 7: Singleton constructor for list algorithm

/**
 * Computes the length of the IList host.
 */
public class GetLength implements IListAlgo {
    /**
     * Singleton Pattern.
     */
    public static final GetLength Singleton = new GetLength();
    private GetLength() {  }
Table 8: Empty and non-empty cases of algorithm
  
/**
 * Returns Integer(0).
 * @param nu not used
 * @return Integer(0)
 */
public Object emptyCase(
    MTList host, Object... nu) {

    return 0;
}
  
/**
 * Return the length of the host's rest 
 * plus 1.
 * @param nu not used.
 * @return Integer > 0.
 */
public Object nonEmptyCase(
    NEList host, Object... nu) {

    Object restLen 
        = host.getRest().execute(this);
    return 1 + (Integer)restLen);
}
Table 9: Singleton constructor for list algorithm
  
package listFW;
/**
 * Computes a String reprsentation of IList showing a left parenthesis followed
 * by elements of the IList separated by commas, ending with with a right parenthesis.
 */
public class ToStringAlgo implements IListAlgo {
    public static final ToStringAlgo Singleton = new ToStringAlgo();
    
    private ToStringAlgo() {  }
Table 10: Empty and non-empty cases of algorithm
  
/**
 * Returns "()".
 */
public Object emptyCase(
    MTList host, Object... inp) {

    return "()";
}
  
/**
 * Passes "(" + first to the rest of IList 
 * and asks for help to complete the 
 * computation.
 */
public Object nonEmptyCase(
    NEList host, Object...  inp) {

    return host.getRest().execute(
        ToStringHelper.Singleton, 
        "(" + host.getFirst());
}
} //closing parenthesis for the class

 

Table 11: Singleton constructor for helper visitor

/**
 * Helps ToStringAlgo compute the String representation of the rest of the list.
 */
class ToStringHelper implements IListAlgo {
    public static final ToStringHelper Singleton = new ToStringHelper();
    private ToStringHelper() {   }
Table 12: Empty and non-empty cases of algorithm

/**
 * Returns the accumulated String + ")".
 * At end of list: done!
 */
public Object emptyCase(
    MTList host, Object... acc) {

    return  acc[0] + ")";
}

/**
 * Continues accumulating the String 
 * representation by appending ", " + first 
 * to acc and recurse!
 */
public Object nonEmptyCase(
    NEList host, Object... acc) {

    return host.getRest().execute(
        this, 
        acc[0] + ", " + host.getFirst());
    }
}

We now can use to ToStringAlgo to implement the toString() method of an IList.

Table 13
  
package listFW;

public class MTList implements IList {

    /**
     * Singleton Pattern
     */
    public final static MTList Singleton 
        = new MTList();

        private MTList() { }

        /**
         * Calls the empty case of the 
         * algorithm algo, passing to it 
         * itself as the host parameter
         * and the given input inp as the 
         * input parameter.
         * This method is marked as final 
         * to prevent all subclasses from 
         * overriding it. Finalizing a 
         * method also allows the compiler 
         * to generate more efficient 
         * calling code.
         */
         public final Object execute(
             IListAlgo algo, 
             Object... inp) {

            return algo.emptyCase(
                this, inp);
         }
         public String toString() {
            return (String)ToStringAlgo
                .Singleton.emptyCase(this);
         }
    }
  
package listFW;

public class NEList implements IList {
    /**
     * The first data element.
     */
    private Object _first; 
    /**
     * The rest or "tail" of this NEList.
     * Data Invariant: _rest != null;
     */
    private IList _rest;
    /**
     * Initializes this NEList to a given 
     * first and a given rest.
     * @param f This NEList's first element 
     * @param r !=null; rest of this NEList.
     */
    public NEList(Object f, IList r) {
        _first = f;
        _rest = r;
    }
    /**
     * Returns the first data element of 
     * this NEList.
     * Marked final for the above reasons.
     */
    public final Object getFirst() {
        return _first;
    }
    /**
     * Returns the rest of this NEList which
     * is an IList.
     * Marked final for the above reasons.
     */
    public final IList getRest() {
       return _rest;
    } 
    /**
     * Calls the nonEmptyCase method of the 
     * IListAlgo parameter, passing itself 
     * as the host parameter and the given 
     * input as the input parameter.
     * Marked final for the above reasons.
     */
    public final Object execute(
        IListAlgo algo, Object... inp) {
        return algo.nonEmptyCase(this, inp);
    }
    public String toString() {
        return (String)ToStringAlgo
            .Singleton.nonEmptyCase(this);
    }
}

Download the above code here.

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks