9-3. 템플릿 메타 프로그래밍 (Template Meta Programming)

컴파일 타임에 모든 연산을 해보자

• 템플릿을 마치 인자 인것 처럼 사용하는 것을 바로 일반화 프로그래밍(Generic Programming) 이라고 부른다. -> 재네릭 프로그래밍은 컴파일 타임에 타입체크가 가능하다.

• 템플릿 인자로는 타입 뿐 아니라, 특정한 조건을 만족하는 값들이 올 수도 있다. std::array 의 예제를 살펴보자

/* 나만의 std::array 구현 */
#include <iostream>

template <typename T, unsigned int N>
class Array {
  T data[N];

 public:
  // 배열을 받는 레퍼런스 arr
  Array(T (&arr)[N]) {
    for (int i = 0; i < N; i++) {
      data[i] = arr[i];
    }
  }

  T* get_array() { return data; }

  unsigned int size() { return N; }

  void print_all() {
    for (int i = 0; i < N; i++) {
      std::cout << data[i] << ", ";
    }
    std::cout << std::endl;
  }
};

int main() {
  int arr[3] = {1, 2, 3};

  // 배열 wrapper 클래스
  Array<int, 3> arr_w(arr);

  arr_w.print_all();
}

• 참고로 위처럼 배열을 감싸는 wrapper 클래스를 만들어 마치 배열 처럼 사용한다면(물론 그렇게 사용하기 위해 [] 연산자도 오버로드 해야한다) 배열을 사용함으로 발생하는 문제들을 많이 해결할 수 있다.

• 예를 들어, 일반 배열은 배열의 범위가 넘어가도 알 수 없지만, 위 Array 클래스는 index 범위가 넘어가는 곳을 가리키면 뭔가 메세지를 띄우든 오류를 발생 시키든 액션을 취해 사용자에게 알려 줄 수 있다.

과연 아래 두 클래스는 같은 클래스일까? 다른 클래스일까?

Array<int, 5> Array<int ,3> 

• 간단히 아래 코드로 확인해볼 수 있다. -> typeid 를 사용하려면, <typeinfo> 헤더 파일을 추가하면 된다.

std::cout <<  (typeid(Array<int, 3>) == typeid(Array<int, 5>)) << std::endl;

• 결과를 당연하게도 다르게 나온다. 왜냐면, 다른 템플릿 인자로 인스턴스화 되었기 때문이다. -> 컴파일러는 Array<int, 3> 과 Array<int, 5> 를 위해 각기 다른 코드를 생성하여 다른 클래스들의 개체들을 만들게 된다.

• 그렇다면 아래 같이 정의된 Int 클래스를 생각해보자.

  • 이 클래스는 템플릿 인자로 int 값을 받는다. 참고로 왜 static const 에 값을 저장하냐면,

  • 첫 번째로, C++ 클래스 멤버 중에서 클래스 자체에서 아래와 같이 초기화 할 수 있는 멤버의 타입은 static const 밖에 없고,

  • 두 번째로, static const 야 말로 이 클래스는 이 것이다 라는 의미를 가장 잘 나타내기 때문이다.

    • 왜냐면 static 타입 멤버의 특성 상, 이 클래스가 생성한 개체들 사이에서 공유되는 값이기 때문에, '이 타입이면 이 값을 나타낸다' 라고 볼 수 있다.

    • 또한 const 이므로, 그 나타내는 값이 변하지 않는다.

template<int N>
struct Int {
    static const int num = N;
};

• 따라서 아래와 같이 개체를 생성하듯 타입을 정의할 수 있다.

typedef Int<1> one;
typedef Int<2> two;

• 위 와 같이 선언한다면, one 타입과 two 타입은 1 과 2의 값을 나타내는 타입이 된다. -> one 과 two 는 개체가 아니다!

• 선언된 타입은 int 변수를 가리키는 것처럼 사용할 수 있다.

#include <iostream>
#include <typeinfo>

template <int N>
struct Int {
  static const int num = N;
};

template <typename T, typename U>
struct add {
  typedef Int<T::num + U::num> result;
};

int main() {
  typedef Int<1> one;
  typedef Int<2> two;

  typedef add<one, two>::result three;

  std::cout << "Addtion result : " << three::num << std::endl;
}

• 덧셈을 수행하는 코드를 잘보면, add 클래스의 템플릿은 인자로 두 개의 타입을 받아서, 그 타입의 num 멤버를 더해서 새로운 타입 result 를 만들어 내게 된다.

template <typename T, typename U>
struct add {
  typedef Int<T::num + U::num> result;
};

typedef add<one, two>::result three;

• 실제로 그 결과를 보면 3이 잘 출력됨을 확인할 수 있다.

• 한가지 더 흥미로운 점은 3이라는 값이 프로그램이 실행되면서 계산된는 것이 아닌, 컴파일 시에 컴파일러가 three::num 을 3으로 치환해버린다. -> 다시 말해서 아래 덧셈이 수행되는 시키는 컴파일 타임이고, 런타임에는 단순히 그 결과를 보여주는 것이다.

std::cout << "Addtion result : " << three::num << std::endl;

템플릿 메타 프로그래밍 (Template Meta Programming - TMP)

• 지금까지 타입은 어떤한 개체에 무엇을 저장하느냐를 지정하는데 사용해 왔지, 타입 자체가 어떠한 값을 가지지는 않았다. (초기화 전까지는 어떠한 값을 가지지는 않는다)

• 하지만 위 예제처럼 템플릿을 사용하면 개체를 생성하지 않더라도, 타입에 어떤한 값을 부여할 수 있고, 또 그 타입들을 가지고 연산을 할 수 있다는 점이다.

• 또한 타입은 컴파일 타임에 확정되어야 하기 때문에, 컴파일 타임에 모든 연산이 끝나게 된다.

• 이렇게 컴파일 타임에 생성되는 코드로 프로그래밍 하는 것을 메타 프로그래밍(meta programming) 이라 하고, C++ 의 경우 템플릿을 가지고 이러한 작업을 하기 때문에, 템플릿 메타 프로그래밍, 줄여서 TMP 라고 한다.

/* 컴파일 타임 팩토리얼 계산 */
#include <iostream>
template <int N>
struct Factorial {
  static const int result = N * Factorial<N - 1>::result;
};

template <>
struct Factorial<1> {
  static const int result = 1;
};

int main() {
  std::cout << "6! = 1*2*3*4*5*6 = " << Factorial<6>::result << std::endl;
}

• 만약 템플릿 메타 프로그래밍을 사용하지 않는다면, 다음과 같이 재귀 함수를 통해 구현할 수 있다.

• 따라서, 우리는 아래 처럼 재귀 함수 호출이 끝나게 하기 위해서는, n 이 1 일 때 따로 처리를 해주어야 한다.

int factorial(int n) {
    if(n == 1) return 1;    // 재귀함수 종료 조건
    
    return  n * factorial(n-1);
}

• 템플릿 역시 n=1 일때 템플릿 특수화를 통해 아래와 같이 처리할 수 있다.

template<>
struct Factorial<1> {
    static const int result = 1;
};

• 위 예제에서 볼 수 있듯이, 저기서 실질적으로 값을 가지는 개체는 아무 것도 없다. -> 즉, 720 이라는 값을 가지고 있는 변수는 메모리 상에 없다는 것이다. -> 출력 결과로 나타내는 720 이라는 값은, 단순히 컴파일러가 만들어낸 Factorial<6> 이라는 타입을 나타내고 있을 뿐이다.

• 사실 보통 factorial 함수를 만든다면, 십중팔구 그냥 단순하게 for 문으로 구현을 하였을 것이다.

  • 하지만 안타깝게도 템플릿으로는 for 문을 사용할 수 없기 떄문에, 위와 같은 재귀적 구조를 사용할 수 밖에 없다.

  • 한가지 다행인 소식은 for 문으로 구현할 수 있는 모든 코드는 똑같이 템플릿 메타 프로그래밍을 통해서 구현할 수 있다.

TMP 를 왜 쓰는가?

• 한가지 재밌는 사실은 어떠한 C++ 코드도 템플릿 메타 프로그래밍 코드로 변환할 수 있다는 점이다. (물론 코드량은 엄청나게 길어진다..)

• 게다가 템플릿 메타 프로그래밍으로 작성된 코드는 모두 컴파일 타임에 모든 연산이 끝나기 때문에, 프로그램 실행 속도를 향상 시킬 수 있다는 장점이 있다. (당연하게 컴파일 시간은 엄청 늘어나게 된다..)

• 하지만 그렇다고 해서 템플릿 메타 프로그래밍으로 프로그램 전체를 구현하는 일은 없다. 일단 템플릿 메타 프로그래밍은 매우 복잡하다. -> 프로그래밍은 트레이드오프의 연속이다..

• 그 뿐만 아니라, 템플릿 메타 프로그래밍으로 작성된 코드는 버그를 찾는 것이 매우 힘들다. -> 일단 기본적으로 컴파일 타임에 연산하는 것이기 때문에, 디버깅이 불가하고, (디버깅은 컴파일 이후에 이루어진다) -> C++ 컴파일러에 특성 상 템플릿 오류 시에 엄청난 길이의 오류를 내뿜게 된다.

• 때문에, TMP 를 이용하는 경우는 꽤나 제한적이지만, 아래와 같은 장점 때문에 많은 C++ 라이브러리 들이 TMP 를 이용해서 구현되었다.

  • TMP 를 통해서 컴파일 타임에 여러 오류들을 잡아낼 수 있고(타입 체크),

  • 속도가 매우 중요한 프로그램의 경우 TMP 를 통해서 런타임 속도도 향샹시킬 수 있다.

조금 더 복잡한 예제를 가지고 TMP 를 어떻게 사용할 지에 대해서 생각해보자.

• 보통 컴퓨터 상에서 두 수의 최대공약수를 구하기 위해서는 보톤 유클리드 호제법을 사용한다.

• 이를 일반적인 함수로 구현하면 다음과 같다.

int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }

  return gcd(b, a % b);
}

• 이를 TMP 로 표현하면 다음과 같다.

#include <iostream>

template <int X, int Y>
struct GCD {
  static const int value = GCD<Y, X % Y>::value;
};

template <int X>
struct GCD<X, 0> {
  static const int value = X;
};

int main() {
  std::cout << "gcd (36, 24) :: " << GCD<36, 24>::value << std::endl;
}

• 이 최대공약수 계산 클래스를 만든 이유는, 바로 Ratio 클래스를 만들기 위함인데, Ratio 클래스는 유리수를 오차 없이 표현해 주는 클래스이다.

• Raito 클래스를 TMP 방식으로 아래와 같이 만들 수 있다.

  • 분모와 분자를 템플릿 인자로 받고, 타입을 나타내게 된다.

template <int N, int D = 1>
struct Ratio {
  typedef Ratio<N, D> type;  // 편의를 위해 typedef 로 선언
  static const int num = N;
  static const int den = D;
};

• 이 Ratio 로 덧셈을 수행하는 템플릿을 만들어보자, 상당히 직관적이다. -> 두 분수를 더한 결과를 Ratio 에 분자 분모로 전달하면 알아서 기약분수로 만들어준다.

template <class R1, class R2>
struct _Ratio_add {
  typedef Ratio<R1::num * R2::den + R2::num * R1::den, R1::den * R2::den> type;
};

• 그 후에, 그 덧셈 결과를 type 로 나타내게 된다. -> 따라서 덧셈을 수행하기 위해서는 아래와 같이 사용하면 된다.

typedef _Ratio_add<rat, rat2>::type result;

• 한 발 더 나아가서 귀찮게 :: type 를 치고 싶지 않다면, 아래와 같이 구현할 수 있다.

  • Ratio_add<R1, R2>::type 을 상속 받는 Ratio_add 클래스를 만들어 버리는 것이다.

template <class R1, class R2>
struct Ratio_add : _Ratio_add<R1, R2>::type {};

• 이를 통해 Ratio_add 는 Ratio 처럼 사용할 수 있게 된다.

#include <iostream>
#include <typeinfo>


template <int X, int Y>
struct GCD {
  static const int value = GCD<Y, X % Y>::value;
};

template <int X>
struct GCD<X, 0> {
  static const int value = X;
};

template <int N, int D = 1>
struct Ratio {
  typedef Ratio<N, D> type;
  static const int num = N;  // 분자
  static const int den = D;  // 분모
};
template <class R1, class R2>
struct _Ratio_add {
  typedef Ratio<R1::num * R2::den + R2::num * R1::den, R1::den * R2::den> type;
};

template <class R1, class R2>
struct Ratio_add : _Ratio_add<R1, R2>::type {};

int main() {
  typedef Ratio<2, 3> rat;
  typedef Ratio<3, 2> rat2;
  typedef Ratio_add<rat, rat2> rat3;

  std::cout << rat3::num << " / " << rat3::den << std::endl;

  return 0;
}

• 참고로 C++11 부터는 typedef 대신 좀 더 직관적인 using 을 사용할 수 있다. -> 아래 두 문장은 동일한 의미를 갖는다. -> 코드가 좀 더 직관적이다.

typedef Ratio_add<rat, rat2> rat3;
using rat3 = Ratio_add<rat, rat2>;

• 따라서 위 코드를 수정하면 아래와 같이 직관적으로 표현할 수 있다.

int main() {
  using rat = Ratio<2, 3>;
  using rat2 = Ratio<3, 2>;

  using rat3 = Ratio_add<rat, rat2>;
  std::cout << rat3::num << " / " << rat3::den << std::endl;

  return 0;
}

결론적으로 Ratio 클래스의 개체를 생성한 것 같지만, 실제로 생성된 개체는 하나도 없고 단순히 타입들을 컴파일러가 만들어 낸 것이다.

• 마찬가지 방법으로 모든 사칙연산을 만들어 낸다면 다음과 같이 코드를 만들어 낼 수 있다.

#include <iostream>

template <int X, int Y>
struct GCD {
  static const int value = GCD<Y, X % Y>::value;
};

template <int X>
struct GCD<X, 0> {
  static const int value = X;
};

template <int N, int D = 1>
struct Ratio {
 private:
  const static int _gcd = GCD<N, D>::value;

 public:
  typedef Ratio<N / _gcd, D / _gcd> type;
  static const int num = N / _gcd;
  static const int den = D / _gcd;
};
template <class R1, class R2>
struct _Ratio_add {
  using type = Ratio<R1::num * R2::den + R2::num * R1::den, R1::den * R2::den>;
};

template <class R1, class R2>
struct Ratio_add : _Ratio_add<R1, R2>::type {};

template <class R1, class R2>
struct _Ratio_subtract {
  using type = Ratio<R1::num * R2::den - R2::num * R1::den, R1::den * R2::den>;
};

template <class R1, class R2>
struct Ratio_subtract : _Ratio_subtract<R1, R2>::type {};

template <class R1, class R2>
struct _Ratio_multiply {
  using type = Ratio<R1::num * R2::num, R1::den * R2::den>;
};

template <class R1, class R2>
struct Ratio_multiply : _Ratio_multiply<R1, R2>::type {};

template <class R1, class R2>
struct _Ratio_divide {
  using type = Ratio<R1::num * R2::den, R1::den * R2::num>;
};

template <class R1, class R2>
struct Ratio_divide : _Ratio_divide<R1, R2>::type {};

int main() {
  using r1 = Ratio<2, 3>;
  using r2 = Ratio<3, 2>;

  using r3 = Ratio_add<r1, r2>;
  std::cout << "2/3 + 3/2 = " << r3::num << " / " << r3::den << std::endl;

  using r4 = Ratio_multiply<r1, r3>;
  std::cout << "13 / 6 * 2 /3 = " << r4::num << " / " << r4::den << std::endl;
}