Does the visitor pattern violate the Liskov Substitution Principle

Question

When using the Visitor pattern, I have observed the following:

• The visitor has weak dependencies to concrete types (each visit method has the concrete element as a parameter or is a method that corresponds to a concrete element)
• The element (supertype of the concrete types) has a weak dependency to the visitor (the accept method has the visitor as a parameter)

Doesn't this mean that the element (supertype) will have transitive dependency towards the concrete elements?

Does the supertype knowing about the subtypes for violate the LSP [for the purpose of deciding on what behavior to do]? or is this a naive understanding of the principle?

Answer 1

Neither "transitive dependency towards the concrete elements" nor "supertype knowing about the subtypes" leads to a conclusion of LSP being violated. The first one is harmless. The second one is merely a smoking gun.

---

Visitor pattern can be used for several purposes. Judging from the way this question is asked, this answer will put the focus on the case of Double Dispatch.

Visitor pattern might also be used for other purposes. The possibility of those other purposes violating OCP or LSP is practically nil; therefore they will not be discussed in this answer.

---

In cases where the Visitor pattern is used to implement Double Dispatch (or equivalently to get around the lack of double dispatch in OOP languages), it is often said to be incompatible with Open/Closed Principle (OCP), although generally we can't say much about whether it violates Liskov Substitution Principle (LSP) unless there is an implementation mistake.

This article on Double Dispatch explains it better than I do.

An example of double dispatch is that you have one inheritance hierarchy of Shape, and then a different inheritance hierarchy of Display (or ISurface in the article linked above). The project requires an implementation of a polymorphic method, whose behavior varies with both the concrete Shape subtype and the concrete Display subtype. If you have 3 concrete Shape subtypes and 5 concrete Display subtypes, this requires 15 concrete implementations of the polymorphic method, i.e. it is a Cartesian product of implementations.

The most widely used OOP languages do not support Double Dispatch out-of-the-box. There are several ways to get around this; using the Visitor pattern is one way.

However, using the Visitor pattern to achieve Double Dispatch requires you to lock down one of the two inheritance hierarchies: you will not be able to add support for new subtypes to the locked-down inheritance hierarchy anymore (without modifying the supertype/interface). Using the above example, you have to choose either: (1) lock down the Shape hierarchy, or (2) lock down the Display hierarchy. This breaks the "open for extension" part of the OCP.

If the nature of one of the inheritance hierarchy is that it is "complete", i.e. there will never be a future necessity to add any new subtypes to that hierarchy, then locking it down is not an issue, so it does not violate OCP.

There is an alternative implementation of Double Dispatch that does not break OCP, i.e. that will allow adding new subtypes to both the Shape and Display inheritance hierarchies, without modifying existing code. However, this alternative implementation does require checking the concrete types of both arguments via instanceof.

Some would argue that checking the concrete argument types with instanceof is itself an antipattern, or a smell, or something undesirable. This is somewhat an exaggeration of the original opinions held by Java mentors, which was to prefer polymorphism over instanceof and downcasting, not to outright forbid it even when necessitated by software requirements.

---

This brings up another discussion. In light of agile methodology, it is often the case that new software requirements necessitate code changes to certain parts of the project that were once considered immutable. In other words, breaking changes are sometimes needed.

From this perspective, the Open/Closed Principle (OCP) itself often came up as being too rigid/inflexible.

In the past, violation of OCP will cause harm to compiled libraries (binaries) which are then packaged and shipped. Propagating breaking changes in upstream dependencies often has a ripple effect that result in a large number of compiled libraries to be updated.

Agile methodology intends to solve this issue with:

• Versioning (leave the old system in place, but introduce the new system as an alternative, while making both available to customers)
• Continuous integration (literally, recompile everything, every time)
• Open source (customers can see and modify the source code inside dependencies)

---

Agile methodology also views violations of Liskov Substitution Principle in a different way. Instead of branding a violation as a sign that the system or design is unsafe or having questionable correctness, it is merely seen as being a pain point. So, a LSP violation is not a death knell, but is a bad mark that adds up.

There are plenty of new software requirements which require the violation of LSP. In the past, such feature requests will be rejected on the grounds of correctness. Nowadays, it will be given business considerations. If a violation of LSP is accepted, then it shall be properly documented.

The additional cost of documenting an LSP violation, the displeasure of a programmer caught by the astonishment of software breakage (due to not heeding the documented warning), and the software maintenance and support overhead stemming from such breakage, are seen as business costs that are weighted against the business gains from implementing the requested feature.

Answer 2

No.

First, what does the Liskov substitution principle say?

Substitutability is a principle in object-oriented programming. It states that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e., objects of type S may substitute objects of type T) without altering any of the desirable properties of that program (correctness, task performed, etc.).

In other words, it should be possible to substitute the concrete type anywhere the supertype is expected without altering program behavior in an unexpected way. Clearly a subclass will alter behavior because it is a different type, this is meant more to prevent behavior changes that break logic (there are examples but I cannot find them, I will try to edit them in later).

Next, we need to look at the Visitor pattern.

Essentially, each concrete type that can be visited invokes the visitor method for that concrete type. The superclass (or interface) needs no knowledge of the implementations to make this work: in fact the pseudocode example at the Wikipedia article has the supertype being an interface containing no code.

The basic sequence of events looks like this:

1. Your code creates a visitable object. Normally this is represented as some sort of tree, where objects may contain other objects.

2. Your code creates a visitor object that works with the type you created in the previous step.

3. Your code tells the object created in step 1 to "accept" the visitor.

4. Using dynamic dispatch, the concrete object's method is called.

   1. The object will normally tell the visitor to visit this object, where this resolves to the concrete type. Using method overloading, this invokes the specific method on the visitor for that type.

   2. If this object contains child objects, iterate them and tell them to accept the visitor. This repeats step 4 above but on a different object.

Going back to LSP, at no point does a supertype have knowledge about its subtypes, nor does the behavior change in program-breaking ways. The only knowledge of other types in the context of the visitor is when an object has child objects, but this is normal and good (in fact, mostly required for statically-typed languages although there are ways around it such as dependency injection).

Answer 3

The Liskov Substitutability Principle (LSP) only says whether a subclass is valid or not. Your concerns only mean that there may be fewer subclasses that can satisfy the LSP. A violation would occur only when a subclass was made that violated the behavioral constraints. Of course, for this to happen, behavioral constraints need to be provided in the first place, e.g. pre- and post-conditions.

Below is an example of a base class that has very tight binding to (some of) its subclasses. Nevertheless, the subclasses that exist satisfy the LSP. (And actually, since there are no behavioral constraints (i.e. post-conditions) when the subclasses aren't one of the two provided, any other subclass would satisfy the LSP in this case.)

// Untested C#
abstract class List<T> {
    // pre-condition: v != null
    // post-condition: if this instanceof Nil then return v.NilCase
    //                 if this instanceof Cons then 
    //                     return v.ConsCase(this.head, this.tail.Accept(v))
    public abstract R Accept<R>(ListVisitor<T, R> v);
}

interface ListVisitor<T, R> {
    R NilCase { get; }
    R ConsCase(T x, R xs);
}

class Nil<T> : List<T> {
    public Nil() {}
    public R Accept<R>(ListVisitor<T, R> v) {
        return v.NilCase;
    }
}

class Cons<T> : List<T> {
    private T head;
    private List<T> tail;
    public Cons(T hd, List<T> tl) {
        this.head = hd;
        this.tail = tl;
    }
    public R Accept<R>(ListVisitor<T,R> v) {
        return v.ConsCase(this.head, this.tail.Accept(v));
    }
}

The following case is a little more interesting because it puts constraints on all possible subclasses.

abstract class List<T> {
    // pre-condition: v != null
    // post-condition: if this.IsEmpty then return v.NilCase
    //                 if !this.IsEmpty then 
    //                     return v.ConsCase(this.Head, this.Tail.Accept(v))
    public abstract R Accept<R>(ListVisitor<T, R> v);
    public abstract bool IsEmpty { get; }
    public abstract T Head { get; }
    public abstract List<T> Tail { get; }
}

class Nil<T> : List<T> {
    public Nil() {}
    public R Accept<R>(ListVisitor<T, R> v) {
        return v.NilCase;
    }
    public bool IsEmpty { get { return true; } }
    public abstract T Head { 
        get { 
           throw new ApplicationException(); 
        } 
    }
    public abstract List<T> Tail { 
        get { 
           throw new ApplicationException(); 
        } 
    }
}

class Cons<T> : List<T> {
    private T head;
    private List<T> tail;
    public Cons(T hd, List<T> tl) {
        this.head = hd;
        this.tail = tl;
    }
    public R Accept<R>(ListVisitor<T,R> v) {
        return v.ConsCase(this.head, this.tail.Accept(v));
    }
    public bool IsEmpty { get { return false; } }
    public abstract T Head { get { return this.head; } }
    public abstract List<T> Tail { get { return this.tail; } }
}

The post-condition constrains subclasses of List<T> to "look like" lists as far as Accept is concerned even though they may, internally, look like a tree, say. Furthermore, there are now potential subclass implementations that violate LSP, e.g. a subclass that return false for IsEmpty but nevertheless returned the NilCase property of the visitor.

Focusing on the Visitor pattern, rather than the LSP, the Visitor pattern more or less corresponds to pattern matching which is common in functional programming languages. More precisely, it is roughly a fold. There are some ways in which FP and OOP appear to be "dual" in the forms of extensibility they most naturally support. In OOP, it's easy to add a new subclass, but if you want to add a new method to a base class you need to go back and change all your other subclasses. Dually, in FP it's easy to add a new function that walks over data, but if you want to add a new data constructor, you need to change all your existing functions for that type. The Visitor pattern allows you to switch to the other side of this duality in OOP, but you get the downsides too which are going to show up as violations of (other) OO design guidelines (but not LSP which I wouldn't view as a design guideline but rather as a correctness criterion). Trying to get the best of both worlds, particularly in a well-typed way, is the Expression Problem.

Returning to the LSP, and stepping back a bit, in practice, it's a very difficult constraint to meet, particularly for mutable objects. Checking it is undecidable, however, you can constrain yourself in ways that guarantee it will hold. The result, however, is extremely rigid and very non-idiomatic. In practice, it's rare for the behavioral constraints of a class to be stated. The reasonable implied constraints are also rarely met. Violation of LSP are essentially ubiquitous.