Curiously Recurring Template Pattern(CRTP) 개념과 코드 예제 - Static polymorphism, expression template

 Curiously Recurring Template Pattern 

Curiously Recurring Template Pattern (CRTP)[1]는 derived 클래스를 생성할 때 base 클래스에 derived 클래스의 타입을 template argument로 넘겨주는 패턴을 의미한다. Base 클래스에서 자신을 상속받은 derived 클래스의 타입을 알고 있으면 다양한 기능을 구현할 수 있다. 

CRTP는 generic programming에서의 기법이기 때문에 App 개발 코드에 직접적으로 사용되기 보다는 linear algebra, container의 구현 등 코어 라이브러리에서 많이 사용된다. CRTP 패턴은 TensorFlow의 Tensor 모듈, Eigen Tensor, Microsoft  Active Template Library (ATL), Standard Template Library (STL) 구현 등에서 활용되고 있다.

CRTP 기본 형태

CRTP 단어를 한글로 바꿔보면 '신기하게 재귀하는 템플릿 패턴' 정도로 번역할 수 있다. CRTP 단어 자체에서 유추해 볼 수 있듯이 Template을 이용한 pattern인데 재귀적인 부분이 있고, 형태가 신기하게 생겼다. 어떤 점이 신기하게 생긴 것일까? 아래 코드에서 는 CRTP의 기본 형태를 보도록 하자.

// The Base Class Template
template <typename Derived>
class BaseTemplate
{
	...
};
// A Derived Class
class DerivedClass : public BaseTemplate<DerivedClass>
{
	...
};
// A Derived Class Template
template <typename T>
class DerivedTemplate : public BaseTemplate<DerivedTemplate<T>>{
	...
};

위 예시에서 DerivedClass BaseTemplate 탬플릿 클래스를 상속받는다. 여기서 특이한 점은 DerivedClass 가 상속받는 대상이 BaseTemplate <DerivedClass>이라는 점이다. 곱씹어 생각해 보면 오묘한 패턴이다. Derived class가 Base 클래스를 상속 받는데 base 클래스의 template argument가 derived class 자체이다. 

CRTP 이용 목적

그러면 이렇게 오묘한 패턴을 왜 쓰는 것일까? base class에서 자신을 상속받는 derived class의 타입이 무엇인지 앎으로써 다양한 기능이 구현 가능하기 때문이다. Wikipedia에 CRTP 활용법에 대해 여러가지가 나와있는데 이 중 가장 주요한 목적은 static polymorphism 구현이다.

Static polymorphism을 이해하기 이전에 우선 polymorphism 개념을 짚고 넘어가자. Polymorphism이란 특정 클래스를 사용하기 위한 인터페이스는 동일하게 유지하되, 실제 작동 방식은 구현에 따라 다르게 하는 것을 의미한다. 이는 object-oriented programming 패러다임의 주요 이점 중 하나이다. 

일반적으로 C++ 에서 polymorphism을 구현할 때 base 클래스에 virtual 함수를 만들고, derived 클래스에서 같은 이름과 같은 signature를 가지는 함수를 overrided 하여 내용을 구현한다. 이러한 방식을 이 문서에서는 dynamic polymorphism 이라고 부르자. Generic programming의 경우 template을 활용하여 compile time에 결정되는 타입들로 기능을 구현하는 경우가 많으므로, runtime에 결정되는 type을 활용하는 dynamic polymorphism을 사용하지 못하는 경우가 많다. CRTP를 이용하면 type 확정적인 상황 에서도 파생 클래스들의 인터페이스는 같게 하면서도 각각의 구현은 다르게 만들 수 있다.   

Static Polymorphism 구현 예제

위 링크의 깃허브 코드의 'CRTPTest' 프로젝트에 static polymorphism 내용이 나와 있다. 프로그램은 base 클래스에 데이터를 저장을 하고 있다가 derived 클래스의 종류에 따라 eval() 함수가 다른 값을 return하는 아주 간단한 형태로 구성되어 있다. Base class로는 BaseTemplate<...>를 정의, derived 클래스의 종류는 3종으로 각각 DerivedVanila(값 그대로 반환), DerivedSquared(제곱값 반환), DerivedDouble(두배 값 반환) 를 정의하였다. 
예제에서는 아래 세가지 방식을 이용하였을 때의 함수의 동작을 비교한 결과를 볼 수 있다. 
  • Polymorphism 없음
  • Dynamic Polymorphism (virtual 이용)
  • Static Polymorphism (CRTP 이용)
TestMain.cpp 파일 내에서 namespace를 지정하여 각각을 테스트 해 볼 수 있도록 구성햐였다. 아래와 같이 코드를 변경하면, CRTP를 이용한 static polymorphism을 테스트 하는 것이다. 만약 polymorphism이 없는 경우의 테스트를 보고 싶은 경우 nopoly로, dynamic polymorphism을 테스트 하고 싶은 경우에는 dynamicpoly로 변경하면 된다. 
void comparePolymorphism()
{
	//namespace ns = nopoly;
	//namespace ns = dynamicpoly;
	namespace ns = CRTPstaticpoly;
	...
}

int main()
{
	comparePolymorphism();
    ...
}

Base Class

Base 클래스의 코드는 아래와 같다. Constructor에서 T 타입의 데이터를 입력받아 이를 m_data에 저장해 놓는 클래스 탬플릿이다. Static polymorphism을 위해 클래스 템플릿은 derived class type을 CRTP 형태로 받기 위한 Derived 를 template parameter로 정의하고 있다. 

template <typename T, typename Derived>
class BaseTemplate
{
public:
	explicit BaseTemplate(const T& inData) :m_data(inData) {}
	T eval() const { return derived()->eval(); }

protected:
	T m_data;

private:
	const Derived* derived() const { return static_cast<const Derived*>(this); }
	Derived* derived() { return static_cast<Derived*>(this); }

};

여기서 derived() 함수를 주목해 볼 필요가 있다. 이 함수는 this 포인터를 (const) Derived의 pointer로 casting하는 역할을 한다. 이 derived() 함수가 있기 때문에 base 클래스는 언제든지 derived 타입으로 static casting 가능하다. 즉. Derived 타입만 알고 있다면, base 클래스는 자신을 상속받은 클래스의 포인터를 접근할 수 있다. 그렇다면, Derived 타입을 어떻게 알려주는 것일까? 바로 CRTP 형태를 이용하는 것이다. 아래 Derived 클래스의 정의를 보자. 

Derived Class

template<typename T>
class DerivedVanila : public BaseTemplate<T, DerivedVanila<T>>
{
public:
	explicit DerivedVanila(const T& inData) :BaseTemplate<T, DerivedVanila<T>>(inData) {}
	inline T eval() const { return this->m_data; }
};
template<typename T>
class DerivedSquared : public BaseTemplate<T, DerivedSquared<T>>
{
public:
	explicit DerivedSquared(const T& inData) :BaseTemplate<T, DerivedSquared<T>>(inData) {}
	inline T eval() const { return this->m_data * this->m_data; }
};
template<typename T>
class DerivedDouble : public BaseTemplate<T, DerivedDouble<T>>
{
public:
	explicit DerivedDouble(const T& inData) :BaseTemplate<T, DerivedDouble<T>>(inData) {}
	inline T eval() const { return 2 * this->m_data; }
};
template <typename T, typename Derived>
inline void showEvaluation(const BaseTemplate<T, Derived>& inobj) { std::cout <<  inobj.eval() <<std::endl; }클래스 사용 부분

위 코드에서 derived 클래스들이 BaseTemplate 클래스를 상속받을때, derived 자신을 template argument로 입력해 준다. 이렇게 하면 derived 클래스로 객체를 생성할 때 BaseTemplate 는 Derived의 타입을 알 수있다. 

실행 결과

각각의 derived 클래스의 eval() 함수가 작동되어 결과를 출력한다. 

Expression Template 예제

Expression Template[3]은 CRTP의 static polymorphism 구현과 proxy pattern[4]을 응용하여 클라이언트 개발자에게 익숙한 표현식 (더하기 빼기 등) 인터페이스를 제공하면서, 실제 작동 (계산) 시점은 라이브러리 개발자가 의도한 때에 작동하게 하는 기법을 의미한다. 앞서 보았던 static polymorphism 개념은 보여주기 위한 예제에 가깝지만, expression template는 linear algebra 라이브러리에서 lazy evaluation[5] 등을 구현하기 위해 널리 활용된다. 
같은 깃허브에 소스이고 'ExpressionTemplateTest' 프로젝트를 빌드하여 테스트할 수 있다. 이번 코드는 위의 CRTPTest와는 아래와 같이 다르다.
  • BaseTemplate이 데이터를 저장하는 역할을 하지 않는다. BaseTemplate은 순수하게 interface 역할을 하고, derived 클래스들이 공통적으로 가지고 있어야 하는 함수들을 정의한다.
  • DerivedVanila는 데이터를 저장하는 역할을 맡고, DerivedSquared와 DerivedDouble은 데이터를 계산하는 역할을 한다. 

Base Class

template <typename T>
class DerivedVanila;

template<typename T>
class DerivedSquared;

template<typename T>
class DerivedDouble;

template <typename Derived>
class BaseTemplate
{
public:
	inline auto eval() const { return derived()->eval(); }
	inline DerivedSquared<Derived> calcSquare() const { return  DerivedSquared<Derived>(*derived()); }
	inline DerivedDouble<Derived> calcDouble() const { return  DerivedDouble<Derived>(*derived()); }

private:
	const Derived* derived() const { return static_cast<const Derived*>(this); }
	Derived* derived() { return static_cast<Derived*>(this); }
};
위에서 볼 수 있듯이 BaseTemplate은 static polymorphism 을 이용하기 위해 Derived 클래스를 template parameter로 입력받는다. 이는 앞서 보았던 CRTPTest 프로그램 예시와 비슷해 보이지만, 사용되는 목적은 서로 다르다. 
Expression template에서는 '계산을 한다'는 정보를 Type으로 표현한다. 즉, DerivedDouble<SomeType> 클래스는 라이브러리 개발자가 의도한 시점에 SomeType  계산 결과에 두배를 해 반환하는 역할을 한다. 이 때 SomeType에 해당하는 타입은 BaseTemplate를 상속받는 클래스로 한정하려 한다. 이를 위해 derived 클래스도 세심하게 구현할 필요가 있다. Derived 클래스들에 대한 코드는 링크에서 확인 가능하다.

실행 결과 및 분석

각 Derived 클래스의 constructor와 eval() 함수에 메시지를 띄워 주도록 구현해 놓았다. 

Case 1.

아래는 가장 단순한 계산을 진행하는 모습이다. 
double dvalue = 3.1;
ns::DerivedVanila<double> tmpdVanila(dvalue);
auto dDouble = tmpdVanila.calcDouble();
ns::showEvaluation(dDouble);

실행 결과 DerivedVanila가 생성된 후 calcDouble에 의해 DerivedDouble이 생성된다. 각 Template들은 입력받은 expression을 m_InExpr라는 변수에 담고 있다. 아래 그림에서는 DerivedSquared 클래스의 m_InExpr 변수의 타입은 DerivedVanila<double> 형태이다.

모든 derived 클래스들이 compile-time에 결정되기 때문에 Visual Studio에서도 해당 타입을 확인할 수 있다. 

Evaluation은 showEvaluation 함수에서 이루어 진다. 따라서 계산을 정의하는 부분인 calcDouble에서 계산이 바로 이루어지지 않고, assignment, 또는 명시적으로 eval 함수가 불리는 곳에서 계산이 이루어지게 된다. 계산은 아래와 같은 순서로 이루어지게 된다. 

Case 2.

이번엔 조금 더 계산이 많은 케이스를 보고자 한다. 
double dvalue = 3.1;
ns::DerivedVanila<double> tmpdVanila(dvalue);
auto dSqrDoubleSqr = tmpdVanila.calcSquare().calcDouble().calcSquare();
ns::showEvaluation(dSqrDoubleSqr);

결과는 위 그림과 같다. eval 계산이 클래스의 생성보다 더 많이 이루어지는데, 이는 DerivedSquared의 구현에서 입력되는 eval의 결과를 두번 계산하여 곱하기 때문이다. 캐싱 기능을 구현하면 계산을 좀더 효율적으로 진행할 수 있을 듯 하다. 
클래스의 관계는 위 그림과 같다. 클래스가 꼬리에 꼬리를 무는 식으로 연결되어 있다. 이렇게 연결되어 있는 클래스들은 eval()이 계산 되면서 순차적으로 값을 전파한다. 아래는 eval() 함수의 call과 그 때의 return 값을 표시한 것이다. 

References

  1. "Curiously Recurring Template Pattern," Wikipedia, https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern, (last accessed on Feb. 18, 2022)
  2. "CRTPExample," https://github.com/QUOPA/CRTPExample
  3. "Expression Template," Wikipedia, https://en.wikipedia.org/wiki/Expression_templates (last accessed on Feb. 21, 2022)
  4. "Proxy Pattern," Wikipedia, https://en.wikipedia.org/wiki/Proxy_pattern (last accessed on Feb. 21, 2022)
  5. "Lazy Evaluation and Aliasing" Eigen  Documents, https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html (last accessed on Feb. 21, 2022)

Comments