The Artima Developer Community
Sponsored Link

Weblogs Forum
Curiously Recurring Generic Pattern

8 replies on 1 page. Most recent reply: Aug 24, 2006 9:38 AM by Adam Klein

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 8 replies on 1 page
Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Curiously Recurring Generic Pattern (View in Weblogs)
Posted: Oct 21, 2005 5:28 AM
Reply to this message Reply
Summary
In my posting "Mixins: Something Else You Can't Do With Java Generics?", someone suggested (incorrectly) that this was just the C++ "Curiously Recurring Template Pattern." The analog of the CRTP does work in Java, but is it good for anything?
Advertisement

Although you can't inherit directly from a generic parameter, you can inherit from a class that uses that generic parameter in its own definition. That is, you can say:


//: generics/CuriouslyRecurringGeneric.java

class Generic<T> {}

public class CuriouslyRecurringGeneric
  extends Generic<CuriouslyRecurringGeneric> {} ///:~
This could be called the "Curiously-Recurring Generic Pattern" (CRGP) after Jim Coplien's "Curiously-Recurring Template Pattern" in C++. The "curiously-recurring" part refers to the fact that your class appears, rather curiously, in its own base class. The motivation for the CRGP is to express a form of the Template Method design pattern. The derived class, because it is used in the generic definition of its own base class, must conform to the structure of the base class, which means it must define, for example, any abstract methods that may be in that base class, and it can choose to override other non-abstract methods. Here's a simple example:

//: generics/GenericTemplateMethod.java

abstract class GenerifiedTemplate<T> {
  public void templateMethod() { f(); g(); }
  public abstract void f();
  public abstract void g();
}

class Subtype extends GenerifiedTemplate<Subtype> {
  public void f() { System.out.println("f()"); }
  public void g() { System.out.println("g()"); }
}

public class GenericTemplateMethod {
  public static void main(String[] args) {
    new Subtype().templateMethod();
  }
} /* Output:
f()
g()
*///:~
What does this buy you over simply inheriting from an ordinary base class set up to support the Template Method pattern?


Todor Boev

Posts: 8
Nickname: rinswind
Registered: Nov, 2004

Re: Curiously Recurring Generic Pattern Posted: Oct 21, 2005 8:03 AM
Reply to this message Reply
Bruce,
After staring at this example for some time I realy can't grasp how it differs from simply overriding an abstract class. The GenerifiedTemplate<T> doesn't seem to restrict the extending classes any more than a simlpe abstract class would. What confuses me is that you never used the type parameter T anyware in the definition of GenerifiedTemplate.
Is it just my bad familiarity with generics or there is something else here?

Todor

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Re: Curiously Recurring Generic Pattern Posted: Oct 21, 2005 9:25 AM
Reply to this message Reply
This is why I asked the question at the end of the entry. I can't see the advantage, either. The example may not be complex enough to show it, or erasure might make it useless.

But maybe I'm missing something that someone else can see.

Brian Slesinsky

Posts: 43
Nickname: skybrian
Registered: Sep, 2003

Re: Curiously Recurring Generic Pattern Posted: Oct 21, 2005 12:03 PM
Reply to this message Reply
I agree that it's not useful in the example. But suppose you add these methods to the base class:

abstract T foo();
abstract T bar();

The subclass then overrides it:

class Subclass extends GenerifiedTemplate<Subclass> {
Subclass foo() { ... }
Subclass bar() { ... }
}

It's a way of specifying that the subclass should use covariance for the return values of these methods, and both methods should use the same subtype as the return value. I believe this is what the Enum class is doing.

However, nothing says that the subclass has to return itself. You could also do this:

class Subclass2 extends GenerifiedTemplate<AnotherSubclass> {
AnotherSubclass foo() { ... }
AnotherSubclass bar() { ... }
}

Without the generic type, there are no constraints on how the subclass uses covariance, if at all.

S. Fanchiotti

Posts: 10
Nickname: impatient
Registered: Nov, 2003

Re: Curiously Recurring Generic Pattern Posted: Oct 28, 2005 10:39 AM
Reply to this message Reply
Don't know about Java's template mechanism much but I use the pattern in C++ to quickly mix in a singleton property to a class like this:

template <class T>
class Singleton
{
public:
static T& instance()
{
static T t ;
return t ;
}
} ;


When I need to make Foo a singleton quickly I would use


class Foo: public Singleton<Foo>
...


This way I can use foo as a singleton without having to wrap a Foo inside a singleton handler and all the extra machinery I've seen around. Clearly this works in a limited way but it is effective in most cases I've encountered.

I guess you can do this in Java now. The question is then is this a healthy practice or can it lead to disasters in maintenance?

Sergio

Mohan Radhakrishnan

Posts: 7
Nickname: mindspace
Registered: Oct, 2005

Re: Curiously Recurring Generic Pattern Posted: Nov 2, 2005 3:43 AM
Reply to this message Reply
Am I right in assuming that this 'Singleton' case is a very simple usage ? If I am able to call methods on a type variable 'T' then this CRGP will be more useful. I can pass different classes that have common methods.

Adal Chiriliuc

Posts: 1
Nickname: adal
Registered: Nov, 2005

Re: Curiously Recurring Generic Pattern Posted: Nov 6, 2005 11:25 AM
Reply to this message Reply
This method allows me do do a very neat trick. I don't remember all the specifics, but this was the only way I managed to do this thing.

I have a Python application and I've extended it with about 10 types implemented in C++. As you probably know, the code to implement a Python type in C contains a lot of boilerplate. I managed to eliminate a lot of it so that a very simple class can now look like the one below:
class CriticalSection : public PyUtil::Type<CriticalSection>
{
public:
static bool TypeInit();

CriticalSection();
~CriticalSection();

private:
PyObject* Acquire();
PyObject* Release();

private:
CRITICAL_SECTION m_CriticalSection;
};

PYUTIL_TYPE_IMPLEMENT(_px, CriticalSection)

bool CriticalSection::TypeInit()
{
PYUTIL_TYPE_METHOD_NOARGS(Acquire)
PYUTIL_TYPE_METHOD_NOARGS(Release)
return true;
}

CriticalSection::CriticalSection()
{
InitializeCriticalSection(&m_CriticalSection);
}

CriticalSection::~Critica lSection()
{
DeleteCriticalSection(&m_CriticalSection);
}

PyObject* CriticalSection::Acquire()
{
PYUTIL_THREAD_SAVE;
EnterCriticalSection(&m_CriticalSection);
PYUTIL_THREAD_LOAD;

Py_RETURN_NONE;
}

PyObject* CriticalSection::Release()
{
PYUTIL_THREAD_SAVE;
LeaveCriticalSection(&m_CriticalSection);
PYUTIL_THREAD_LOAD;

Py_RETURN_NONE;
}

PyUtil::Type is declared like this:
namespace PyUtil
{

template <typename T>
class Type
{
...
{

}

CRTP is used in this class to decide which methods to override. This is a bit tricky to explain without showing the code. Basically I'm doing this: PyUtil::Type implements a lot of methods corresponding to the Python C/API handlers: init, clear, traverse, richCompare, sequenceLength, sequenceItem, sequenceSlice. But the actual type I'm implementing might not support these (like the CriticalSection object from above, which is not a sequence). To decide if to set the corresponding field from the PyType object, I do this:
    if (&_init != &T::_init)
ms_Type.tp_init = _init;

In derived classes which implement _init, this test will succeed and we will add an entry for this method.

I tried doing this without CRTP, but I didn't succeded (with or without virtual methods). I don't remember exactly why, but there were big problems (VS .NET 2003)

At that time I had no idea this pattern was called CRTP. It seemed natural to me to parametrize the base class using the actual final class.

PS: The CriticalSection type shown above doesn't actually need this, as it doesn't implement any special method. All other types I have do, but they are too long to show here. Also, PyUtil::Type's implementation has about 600 lines of complicated code (including a lot of macros to generate the default handlers), but it's worth it. On average, a Python type converted to use this method of implementation was about half the size of the original.

Olaf Lenzmann

Posts: 1
Nickname: lenzmann
Registered: Dec, 2005

Re: Curiously Recurring Generic Pattern Posted: Dec 21, 2005 12:28 PM
Reply to this message Reply
I might not get this right impromptu, but I think I have used this to implement scenario-aware bidirectional reference classes that inherit from a common base. Something like:

abstract class Reference <BackReference extends Reference> {
private BackReference backRef;

// Helper methods common to all referece types to collaborate on managing back-refs
}

class OneToOne extends Reference <OneToOne>;

class OneToMany extends Reference <ManyToOne>;

class ManyToOne extends Reference <OneToMany>;

class ManyToMany extends Reference <ManyToMany>;



Though I'd have to go back to my code to double-check...

Adam Klein

Posts: 1
Nickname: cubey
Registered: Aug, 2006

Re: Curiously Recurring Generic Pattern Posted: Aug 24, 2006 9:38 AM
Reply to this message Reply
I can think of a reason: the clone() method returns an Object, and you could save yourself a cast throughout the code. For instance,


public interface NoCastCloneable<T> extends Cloneable {
public T clone();
}

public class NoCastCloneableImpl
implements NoCastCloneable<NoCastCloneableImpl> {

public NoCastCloneableImpl clone() {
return (NoCastCloneableImpl)this.clone();
}
}


then:


NoCastCloneableImpl a = new NoCastCloneableImpl();
NoCastCloneableImpl b = a.clone(); // no cast!


thoughts?

Flat View: This topic has 8 replies on 1 page
Topic: Curiously Recurring Generic Pattern Previous Topic   Next Topic Topic: Types on the Stack

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use