Curiouser and curiouser

Curiouser and curiouser

Rate This
  • Comments 24

Here's a pattern you see all the time in C#:

class Frob : IComparable<Frob>

At first glance you might ask yourself why this is not a "circular" definition; after all, you're not allowed to say "class Frob : Frob"(*). However, upon deeper reflection that makes perfect sense; a Frob is something that can be compared to another Frob. There's not actually a real circularity there.

This pattern can be genericized further:

class SortedList<T> where T : IComparable<T>

Again, it might seem a bit circular to say that T is constrained to something that is in terms of T, but actually this is just the same as before. T is constrained to be something that can be compared to T. Frob is a legal type argument for a SortedList because one Frob can be compared to another Frob.

But this really hurts my brain:

class Blah<T> where T : Blah<T>

That appears to be circular in (at least) two ways. Is this really legal?

Yes it is legal, and it does have some legitimate uses. I see this pattern rather a lot(**). However, I personally don't like it and I discourage its use.

This is a C# variation on what's called the Curiously Recurring Template Pattern in C++, and I will leave it to my betters to explain its uses in that language. Essentially the pattern in C# is an attempt to enforce the usage of the CRTP.

So, why would you want to do that, and why do I object to it?

One reason why people want to do this is to enforce a particular constraint in a type hierarchy. Suppose we have

abstract class Animal
{
    public virtual void MakeFriends(Animal animal);
}

But that means that a Cat can make friends with a Dog, and that would be a crisis of Biblical proportions! (***) What we want to say is

abstract class Animal
{
    public virtual void MakeFriends(THISTYPE animal);
}

so that when Cat overrides MakeFriends, it can only override it with Cat.

Now, that immediately presents a problem in that we've just violated the Liskov Substitution Principle. We can no longer call a method on a variable of the abstract base type and have any confidence that type safety is maintained. Variance on formal parameter types has to be contravariance, not covariance, for it to be typesafe. And moreover, we simply don't have that feature in the CLR type system.

But you can get close with the curious pattern:

abstract class Animal<T> where T : Animal<T>
{
    public virtual void MakeFriends(T animal);
}

class Cat : Animal<Cat>
{
  public override void MakeFriends(Cat cat) {}
}

and hey, we haven't violated the LSP and we have guaranteed that a Cat can only make friends with a Cat. Beautiful.

Wait a minute... did we really guarantee that?

class EvilDog : Animal<Cat>
{
  public override void MakeFriends(Cat cat) { }
}

We have not guaranteed that a Cat can only make friends with a Cat; an EvilDog can make friends with a Cat too. The constraint only enforces that the type argument to Animal be good; how you use the resulting valid type is entirely up to you. You can use it for a base type of something else if you wish.

So that's one good reason to avoid this pattern: because it doesn't actually enforce the constraint you think it does. Everyone has to play along and agree that they'll use the curiously recurring pattern the way it was intended to be used, rather than the evil dog way that it can be used.

The second reason to avoid this is simply because it bakes the noodle of anyone who reads the code. When I see List<Giraffe> I have a very clear idea of what the relationship is between the "List" part -- it means that there are going to be operations that add and remove things -- and the "Giraffe" part -- those operations are going to be on Giraffes. When I see "FuturesContract<T> where T : LegalPolicy" I understand that this type is intended to model a legal contract about a transaction in the future which has some particular controlling legal policy. But when I read "Blah<T> where T : Blah<T>" I have no intuitive idea of what the intended relationship is between Blah and any particular T. It seems like an abuse of a mechanism rather than the modeling of a concept from the program's "business domain".

All that said, in practice there are times when using this pattern really does pragmatically solve problems in ways that are hard to model otherwise in C#; it allows you to do a bit of an end-run around the fact that we don't have covariant return types on virtual methods, and other shortcomings of the type system. That it does so in a manner that does not, strictly speaking, enforce every constraint you might like is unfortunate, but in realistic code, usually not a problem that prevents shipping the product.

My advice is to think very hard before you implement this sort of curious pattern in C#; do the benefits to the customer really outweigh the costs associated with the mental burden you're placing on the code maintainers?


(*) Due to an unintentional omission, some past editions of the C# specification actually did not say that this was illegal! However, the compiler has always enforced it. In fact, the compiler has over-enforced it, sometimes accidentally catching non-cycles and marking them as cycles.

(**) Most frequently in emails asking "is this really legal?"

(***) Mass hysteria!

  • It boils down to being able to describe values in term of dynamic types of other values, e.g. to use some invented Eiffel-like syntax:

     class Foo {

       bool Equals(like(this) other);

     }

     void Bar(Foo x, Foo y) {

        x.Equals(y); // not okay

     }

     void Bar(Foo x, like(x) y) { // type of y is path-dependent

        x.Equals(y); // okay

     }

    I don't think PDTs in Scala can do it - they have significant restrictions on what can be in the path. Doesn't mean it can't be done, though.

  • Here's an example of trying to "enforce a particular constraint in a type hierarchy" : www.typesandotherdistractions.com/.../decorating-recursive-types.html but I wouldn't argue that at the loss of some type safety, casts would be a much more readable option. It's presented for amusement more than anything else...

  • The logic in these two paragraphs is faulty:

    "We have not guaranteed that a Cat can only make friends with a Cat; an EvilDog can make friends with a Cat too. The constraint only enforces that the type argument to Animal be good; how you use the resulting valid type is entirely up to you. You can use it for a base type of something else if you wish.

    "So that's one good reason to avoid this pattern: because it doesn't actually enforce the constraint you think it does. Everyone has to play along and agree that they'll use the curiously recurring pattern the way it was intended to be used, rather than the evil dog way that it can be used."

    As a matter of fact, a Cat can only "MakeFriends" with a Cat. Just because you can create an entirely new subclass and "MakeFriends" with a Cat does not change your original Cat class. The "flaw" here is no different than any other situation where one might create any arbitrary class and write a "MakeFriends" method.

  • @Pavel: any paper with more formal description? However, if you're saying that x.Equals(y); is not okay, you can stop right there, because it's broken.

    Let's take a more detailed example. Say we have A that implements IComparable<A>, then we inherit B from A. Now we can compare As, and also As to Bs. Not allowing to compare A to B would break LSP (in other words you don't have proper subtyping). There's no type safety problem here (no type errors happen), but the implementation of comparison for B discards all new things in B, which can be a problem. Simple ways to fix this is to make A sealed and don't have the problem in the first place, or express A.Compare in terms of virtuals that you can sensibly override in B -- A.Compare discards new stuff in B, but honours overrides. In a single dispatch language with subtyping that's all you can do. Not allowing to call A.Compare(A) is a non-option. Overriding Compare in B will make A.Compare(B) != Reverse(B.Compare(A)).

    Now in a multiple dispatch language when defining B you can define A.Compare(B), B.Compare(A) and B.Compare(B). These new functions will be more specific than A.Compare(A) when you compare Bs and As to Bs, so they will be called. So multiple dispatch language with self-types (like Fortress) solves the problem.

    You can simulate multiple dispatch in a single dispatch language, e.g.

    // in A -- call CompareImpl() on the most specific dynamic type

    int Compare( A rhs ) { if( rhs is this.Type() ) return CompareImpl(rhs); else return Reverse(rhs.CompareImpl(this)); }

    where you don't override Compare in B, but instead override CompareImpl. This implementation is, of course, specific to Compare(), but can be generalized to any binary operation. This leads to a better restriction than "only sealed classes" -- implementations of methods with self types should never be overridden.

    So I argue this is not a typing problem, but a dispatch problem.

  • WindJammer said (on Fri, Feb 4 2011 4:27 PM ):

    "As a matter of fact, a Cat can only "MakeFriends" with a Cat. Just because you can create an entirely new subclass and "MakeFriends" with a Cat does not change your original Cat class. The "flaw" here is no different than any other situation where one might create any arbitrary class and write a "MakeFriends" method."

    Actually, this is true; maybe the MakeFrends() was not the best example... While an Evil dog might make friends with a Cat, a Cat won't do that... And that's the problem with the example - it assumes that making friends operation has nothing to do with the friend-to-be object.

    Speaking of that, how about:

    abstract class Animal<T> where T : Animal<T>

    {

       public virtual bool MakeFriends(T animal);

       public virtual bool AcceptFriendship(Animal<T> animal);

    }

    class Cat : Animal<Cat>

    {

       public override bool MakeFriends(Cat cat)

       {

           return cat.AcceptFriendship(this);

       }

       //err... Animal<Cat> would be animal that might try to make friends with a cat...

       public sealed override bool AcceptFriendship(Animal<Cat> animal)

       {

           if (animal is Cat)

               // ok...

           else

               // I don't wanna be friends with you...

       }

    }

    Of course, this involves some extra work, and partly defeats the initial purpose of the CRTP here. Dumping generics altogether wouldn't make that much of a difference in this case.

    I guess it's better to reconsider the design before opting for such Frankenstein-constructs.

    Also, a method semantically equivalent to MakeFriends() is probably not the best candidate?

    Lucero said (on Thu, Feb 3 2011 5:53 PM):

    "I've been using it in several cases, but typically only for code which is not directly exposed to "end-users" (e.g. private classes, or abstract classes used through derived classes)."

    I think that's a good practice.

  • I've seen this pattern used differently - as a kind of factory.  So an abstract base class can create instances of the specific concrete classes that derive from it, usually in static methods which are invoked DerivedType.StaticMethod().

    The huge problem with that is you can only have one layer of inheritance from that abstract base.

  • Cats Murder Case Solved: Curiosity of the Hook! Turns out it was framed by Ingorance who had an EvilDog do the dirty work.

  • What about this usage of CRTP:

    interface IHierarchical<T> where T : IHierarchical<T>

    {

       T Parent { get; set; }

    }

  • I just want to say, Eric, that when you say the CRTP "really hurts my brain", it makes me feel much better about myself. (Even if I suspect you're being modest.)

Page 2 of 2 (24 items) 12