Re: Visitor and Observer combined?

Responding to Wavemaker wrote:

My instinctive pushback is: Why are you using Visitor a lot?  There
are essentially five conditions that need to prevail for using
Visitor:

(1) There are two separate subclassing trees whose objects must
collaborate.


Perhaps.

There are situations where a single context tree needs different behaviors for its subclasses depending on context. (That's what the Node example in the GoF book does.) In that case one delegates the behaviors to another tree (Visitor) and creates *:* relationship between the subclasses in both trees.

Whether the second tree is a delegation or a direct problem space abstraction, one /always/ has two subclassing trees communicating when using Visitor.

You are correct that technically the Visitors can be any arbitrary objects that are not related by subclassing because the VisitConcreteElementX methods explicitly provides the object type. However, there will almost always be some alternative web of relationships already in place. For example, the GoF Equipment implementation example uses the Composite pattern to provide the relationship structure. In addition, the need for each class to have the same VisitConcreteElementX method responsibilities effectively creates the generalization, so one ends up going there anyway. B-)



(2) The collaborations are at the subclass level (i.e., specialized
subclass properties are accessed).



Yes.


(3) The collaborations are combinatorial.  That is, any leaf object of
one tree potentially collaborates with any instance from any subclass
of the other tree.


Perhaps.



































































Note that /every/ [ConcreteVisitorN] must have a VisitConcreteElementX method for every possible [ConcreteElementX] in the [Element] tree. Similarly, the Accept method in [ConcreteElementX] is tailored to processes any [ConcreteVisitorN] (in fact the examples use iterators). So one effectively has:

                      [Visitor]
                          A
                          |
                +---------+-----------+
                |                     |
            [Concrete1]          [Concrete2]
           0..1 |   | 0..1     0..1 |    | 0..1
                |   |               |    |
                |   +---------+     |    |
                |              \    |    |
                |        +------\---+    |
                |       /        \       |
           0..1 |      / 0..1     \ 0..1 | 0..1
            [ConcreteA]          [ConcreteB]
                |                     |
                +---------+-----------+
                          |
                          V
                       [Element]

[The 0..1 conditionality is because only one relationship at a time is instantiated when some external object is invoking Accept. That's not quite true in the GoF Equipment example because the Visitor only visits Chassis and it is Chassis that maintains the <fixed> relationships with other elements.]

Thus every concrete visitor is potentially related to every concrete element and vice versa or else they wouldn't be part of the pattern.



(4) The collaboration is temporary (i.e., dynamically defined at
run-time on a 1:1 basis).



Yes.


(5) Performance is a problem.  That is, one cannot reify the *:*
relationship and use an identity search of a collection to dynamically
instantiate the "current" relationship in (4).



I'm not sure I understand this one, but performance is definitely an
issue here.

Let me try to clarify what I meant. The real point of Visitor is to allow two <somewhat> arbitrary objects in hand to talk to one another directly. In effect that collaboration means that one navigates a relationship. There are three ways to implement relationship navigation: (a) use an embedded reference attribute in one object to the other; (b) search the set of objects to find the one that one wants to talk to based on object identity; and (c) pass the object reference as a method argument to the first object.

While (a) is the most common, it has a problem in this case because because one needs to find the object before the collaboration to instantiate (initialize) the embedded reference. That is usually done conveniently when one or both objects are created, which usually eliminates the need for a search by identity to find the right object.

But Visitor is aimed at a more complicated dynamic situation where one is navigating a complex structure once, one element at a time, long after the objects have been created. IOW, a Visitor is related to 1 Element at a time, but participation by which Element subclass or which Element within the subclass varies with each navigation. In that case it more efficient to use (c) rather than force Visitor to look for the right Element on each navigation.

However, that requires three things. First, some other entity must traverse the overall structure and keep track of where it is (i.e. some other object invokes Element.Accept(Visitor*)). Second, to avoid searches by that controlling object the traversal must have some predefined ordering to follow. (In the Equipment example that is the Composite pattern of relationships around Chassis.) Third, one needs an infrastructure to get around the type system because one needs to access specializations. That infrastructure is what Visitor provides via accept/visit and the VisitConcreteElementX methods.

To put it another way, there are ways to reify the basic *:* relationship so that one does not have the degree of coupling inherent in passing object references to methods. But they will all involve either ordered collections or some sort of instance search in collection classes that implement reified 1:* relationships. Typically those will be represented in an OOA/D model because they can be abstracted simply and one will only introduce Visitor at the OOP level as a tactical alternative to the <implied> searches.



To justify using Visitor all five of these conditions must prevail.
IME that is quite unlikely in most problem spaces.  [As it happens, as
a translationist I never use Visitor because of (5) since I don't have
to worry about nonfunctional requirements in an OOA model.  B-)  But I
think it would be rare in typical customer problem spaces even without
(5).]

At another level, Visitor is already so complicated with so much
hard-wired infrastructure that I get nervous about the notion of
embedding an Observer in the middle of it all.  B-)



I think I can only justify, or at least explain, my use of Visitor by
giving a concrete example:

I've been writing a MIDI toolkit in C# for awhile now. Among other
things, it can be used to play and manipulate MIDI files.

Alas, I don't use C# and know zilch about MIDI, so the ice is rather thin... [I go through several iterations below for different possibilities, so it may take awhile to get to the one that fits your situation.]


Within a MIDI file are a collection of tracks. Each track in turn is a
collection of MIDI messages, and there are many different types of
messages. I've created a hierarchy of MIDI message classes. I've also
created a Track class. It is a collection of MIDI message base class
objects (actually, a C# interface) from which all MIDI message classes
are derived.


[MIDI File]
     | 1
     |
     | R1 <<ordered>>
     |
     | contains
     | *
  [Track]
     | 1
     |
     | R2 <<ordered>>
     |
     | contains
     | *
[Message]
     A
     |
+----+-----+---...
|          |
[TypeA]  [TypeB]

I assume the file is sequential so there is an implied fixed order that one encounters Tracks and Messages. Is that order (e.g., track #) important to the processing in your solution or do you need to impose some other order?

I also assume the MIDI format has an embedded type attribute for Message so that it can be identified, right?

Is the above model representative of the file?


As I traverse a track, I need to access the subclass properties of each
object (I think this corresponds to your second Visitor requirement); I
use the Visitor pattern to do this.

A priori I do not see a need for Visitor. Somebody is actually processing the messages. Why can't they use the Strategy pattern to process Message?

          * processes  1           1      uses *
[Message] -------------- [Decoder] ------------- [Strategy]
    A          R1                       R2           A
    | R3                                             | R4
+---+----+---...                                 +---+----+---...
|   |    |                                       |   |    |
        [C]                                              [Y]
         | 1                                            1 |
         | accesses           Rn                          |
         +------------------------------------------------+

The Strategy maps 1:1 with the Message type, just like Visitor. However, instantiating the R2 relationship is a lot easier to do here. One can have a lookup table in [Decoder] that maps message types to [Strategy] instances to dynamically instantiate the R2 relationship for each Message. That lookup table can be instantiated when the Decoder is created based on external configuration data. [For example, a factory reads a file that maps message type to strategy ID. The factory does a one-time search for each entry to the table. (If one creates the Strategy objects in ID order, one can even eliminate that search).]

At the same time that R2 is instantiated, one instantiates the Rn relationship by setting a reference in the Stratgey to the Message (C*) based on its type. (In a statically typed language you will need a cast, but that is forgivable here since it is based on the embedded type variable.)

One has exactly the same dynamic mapping between subclasses as Visitor with no search overhead for navigations. However, one has replaced the VisitConcreteElementX methods with individual Strategy methods in a way that is a better mapping of the problem space. In addition, things are better decoupled because the relationship instantiation has been completely separated from the particular collaborations. Best of all, much of the configuration is defined in external configuration data.

[For example, you can reassign which Strategy is applied to a particular Message type without touching the code. If you get exotic with DLLs, you can even add message types and Strategies without touching the main application logic for processing the MIDI file (i.e., you add the Strategy method to a DLL like a function library and provide a new configuration file for the overall application).]


What I began noticing is that there are situations in which I am only
interested in certain kinds of messages. For example, let's say I want
to transpose all of the notes up an octave as the track is being played.
In this case, I'm only interested in note messages. If I were to derive
a class from the Visitor class, I would only override the Visit method
that visits note messages. But my visitor derived class now has all of
the bagage of the other Visit methods for the various other types of
MIDI messages, none of which it is interested in.

I see that as a different problem. In the above model that collection is the R1 collection that [Decoder] processes. You should be able to create that specific collection based on the type attribute when the MIDI file is actually read and Message objects are created.

OTOH,...


So instead, why not have one Visitor class. Its job is simple: When it
visits an object of a certain type, it generates an event (notifies its
observers) that it has encountered an object in the track of a certain
type. Now the class that manages note transposing (really just a
function object) only has to register itself with the visitor to be
notified when a note message has been encountered.

This sounds like there are multiple filters to apply for multiple processing contexts. I still think the answer lies in multiple collection classes. That is, instead of a single [Decoder] class with one Strategy pattern and one R1 relationship, there might be several different processors (e.g. NoteProcessor). Each Processor would have its own collection relationship and set of Strategies.

This provides better separation of concerns and cohesion among the objects. Nor would it be expensive to create the collection classes -- one just adds the Message reference in hand to multiple collections when it is created.

OTOH,...  B-)


This approach can work for other types of messages, of course. Say I
want to filter the tempo a certain way. I can create a class that is
concerned only with that an register it with the visitor to watch out
for tempo messages. And so on.

This seems more dynamic in that one is, at a minimum, selecting filters based on dynamic context (i.e., the collections and processors are "hard-wired" in a fixed execution context). Here I buy the need for a more generic facility because you want to dynamically define what collections and processors to use.

However, it does not seem to be exactly Observer because it is not something happening to a Message that is triggering the processing. It seems like some context says that you need to use ProcessorX and that processing needs to access certain Messages. I see that as more of a Factory facility that creates the Processor instance, "walks" the message collection looking for the right types, creates the collection for the processor relationship, and instantiates some relationship that puts the Processor in the execution flow of control.

OTOH,...  B-))

If all this processing is done in a streaming context when reading the MIDI file, then one does not have a fixed set of [Message] objects conveniently in memory that one initialized from the file.

Assuming one invokes all relevant processors for each Message and processes only one message at a time, I think there is a much simpler solution. Instead of Observer, I would just use event-based processing. Whoever reads the file would put an event on the queue directed at the relevant Processor when the current Message is of the relevant type. This is essentially an Observer activity except that the file reader would be parametrically driven by a collection of {message type, event, processor ID} entries that would define what to look for and what events to generate. (Presumably those entries would be defined before one starts streaming.)

The event queue pops the events and dispatches them to the relevant processors, who grab the Message on their own terms:

          1 does       *
[Message] -------------- [Processor]

Since only one Message is instantiated at a time, there is no searching to find it. When the queue is empty an event to the stream reader can be put on the queue to acquire the next message. (Note that a Processor can process multiple Message types using a Strategy pattern as above.)


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@xxxxxxxxxxxxxxxxx
Pathfinder Solutions  -- Put MDA to Work
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
(888)OOA-PATH



.

Relevant Pages

  • Re: [acyclic visitor]The "accept" operation of an object
    ... there are usually issues of behavior substitution basecon collaboration context. ... Visitor is somewhat unique in that it deals with a very special problem where the collaborating objects are from subclasses in different trees but they need to access the specializations of the subclass ... an object from any subclass in one tree may collaborate with an object of any subclass in the other tree. ... {if(visitor instanceof MyVisitor) ...
    (comp.object)
  • RE: MIDI on SB Live! ?
    ... While I have the "official" Creative Labs MIDI to DB15 cable, ... Creative Labs MIDI cable, but nothing else appeared on the console. ... subclass = ATA ... vendor = 'Creative Labs' ...
    (freebsd-current)
  • Re: How to draw on "Microsoft Web Browser" control?
    ... I am doing semantic analysis on the HTML DOM tree, ... Draw on existing elements doesn't change the structure of the html ... which is a subclass of CWnd. ...
    (microsoft.public.vc.mfc)
  • Re: forEach and Casting
    ... superclass is because I needed a common class to use with the tree. ... the underlying information in each subclass is very different ... different depending on the class in question. ...
    (comp.lang.java.programmer)
  • Re: __init__(self, *args, **kwargs) - why not always?
    ... > A subclass may be a specialized case, ... These will work even if tree is later enhanced to keep ... indicates that the base class also needed to see position. ... required by passing position in your original example. ...
    (comp.lang.python)