Eliminating the need for the Visitor Pattern in ParaSail

The "Visitor" pattern is one of the more widely recognized patterns identified by the "Gang of Four" in Design Patterns: Elements of Reusable Object-Oriented Software.  Object-oriented programming makes it relatively painless to add more types into a type hierarchy, but it makes it relatively painful to add more operations to an existing type hierarchy.  The Visitor pattern is intended to allow adding more operations without doing major surgery on the original type hierarchy, but it requires the use of a visitor object, plus an additional operation, often called accept, on each type, which turns around and calls a visit operation on the visitor object that is unique to that particular type in the hierarchy.

Object-oriented frameworks like that of Common Lisp Object System effectively eliminate the need for the visitor pattern by allowing the addition of dispatching operations (aka virtual functions, methods, etc.) after the type hierarchy has been established, with CLOS in particular allowing additional methods to be added to preexisting generic functions.

In ParaSail, we propose to support the definition of additional dispatching operations to be used with polymorphic types in a somewhat more modular way.  The basic idea is that an interface hierarchy can be extended horizontally in addition to vertically.  By this we mean that an additional named bundle of operations may be specified for the root interface of an interface hierarchy, and then this same named bundle may be defined for each descendant of this root interface, such that operations from this new bundle may be "dispatched" to when operating on polymorphic objects, just as can be the operations of the original root interface. 

Here is an example based on a simple interface hierarchy used to represent numeric expressions:

interface Expr <Value_Type is Integer<>> is
    function Evaluate(E : Expr) -> Value_Type;
end interface Expr;

interface Binary extends Expr is
    type Binary_Op_Enum is Enum<[#add, #sub, #mul, #div, ...]>;
    function Create(Op : Binary_Op_Enum; Left, Right : Expr+) -> Binary;
    function Evaluate(B : Binary) -> Value_Type;
end interface Binary;

interface Unary extends Expr is
    type Unary_Op_Enum is Enum <[#plus, #minus, #not, #abs, ...]>;
    function Create(Op : Unary_Op_Enum; Operand : Expr+) -> Unary;
    function Evaluate(U : Unary) -> Value_Type;
end interface Unary;

interface Leaf extends Expr is
    function Create(Value : Value_Type) -> Leaf;
    function Evaluate(L : Leaf) -> Value_Type;
end interface Leaf;

    ...

 interface Calculator<Int_Expr is Expr<>> is
    ...
    procedure Print_Value(Str : Output_Stream; E : Int_Expr+) is
        // E is of the polymorphic type Int_Expr+ 
        // so calls on its operations will dispatch.
        const Result := Evaluate(E);   // dispatching call
        Print(Str, Result);
    end procedure Print_Value;
end interface Calculator;

Now if we decide we want to add some more "dispatching" operations, we could either disrupt the existing hierarchy of interfaces by adding the operation to each interface, or we could add an operation to each interface to support the visitor pattern, and use that for defining additional operations.  For ParaSail, we are proposing a third approach:

interface Expr[#output] is
    function Text_Image(E : Expr) -> Univ_String;
    function XML_Image(E : Expr) -> Univ_String;
    ...
end interface Expr[#output];

interface Binary[#output] is
    function Text_Image(B : Binary) -> Univ_String;
    function XML_Image(B : Binary) -> Univ_String;
    ...
end interface Binary[#output];
...

Here we have defined an interface extension labeled "#output".  We could define additional interfae extensions with other labels.  Now we have effectively added Text_Image and XML_Image as dispatching operations of Expr without a need for a visitor pattern and without disrupting the original Expr interface hierarchy.  These operations are available when we refer to "Expr[#output]" rather than simply "Expr".  If we had another extension labeled "#input," we could gain access to both by referring to "Expr[#input | #output]".

Then we could write:

 interface Calculator<Int_Expr is Expr[#input | #output]<>> is
       // Now we can use operations from the #input and #output extensions
       // of Expr when manipulating polymorphic objects of type Int_Expr+
    ...
    procedure Print_Expr_And_Value(Str : Output_Stream; E : Int_Expr+) is
        // E is of the polymorphic type Int_Expr+ 
        // so calls on its operations (including those from the
        // interface extensions #input and #output) will dispatch.

        const Result := Evaluate(E);   // dispatching call.
        Print(Str, Text_Image(E));      // Now display the expression
        Print(Str, " = ");
        Print(Str, Result);                    // and then display its value.
    end procedure Print_Expr_And_Value;
end interface Calculator;

This approach allows the definition of additional dispatching operations in a modular fashion to an existing type hierarchy, while not disrupting existing users.  It seems to provide some advantages over the Visitor pattern approach as well, as the new operations are not second class citizens requiring the construction of a visitor object, etc.