C++ 템플릿과 템플릿 특수화를 이용해 컴파일 타임 고차 메타프로그래밍 언어를 만들고, 람다 계산을 구현해 튜링 완전성을 설명합니다.
제 고급 컴파일러 수업의 할로윈 강의에서, 저는 C++ 템플릿 메타프로그래밍으로 학생들을 겁줍니다.
C++ 템플릿이 튜링 완전하다는 것을 증명하기 위해, 우리는 그것들로 고차 함수형 프로그래밍 언어를 구성했습니다.
이 언어는 고차 함수, 리터럴 값(원시 타입), 자연수(타입으로서), 불리언과 조건식을 지원합니다.
구체적으로, 우리는 템플릿으로 SICP와 비슷한 eval/apply 인터프리터를 만들었습니다.
이 내장 언어는 계산 가능한 모든 함수가 C++에서 컴파일 타임에 계산될 수 있음을 보여 줍니다.
C++에서 템플릿의 튜링 완전성은 두 기능, 즉 템플릿과 템플릿 특수화의 충돌에서 우연히 생겨난 결과입니다.
이 두 기능은 C++ 템플릿이 타입 없는 항 재작성 언어처럼 동작할 수 있게 합니다.
템플릿은 몇몇 상수와 몇몇 타입으로 매개변수화된 데이터 타입을 선언합니다. 예를 들면 다음과 같습니다:
template <typename A> struct ListNode { A data ; ListNode<A>* next ; } ;
템플릿 특수화는 프로그래머가 템플릿 매개변수의 어떤 조합에 대해 템플릿의 정의를 재정의할 수 있게 해 줍니다.
예를 들어, unsigned int 타입으로 매개변수화되었을 때 ListNode의 정의를 재정의할 수 있습니다:
template <> struct ListNode<unsigned int> { /* unsigned int를 쓰지 못하게 하자. / int data ; ListNode<int> next ; } ;
특수화를 원하는 이유에 대한 표준적인 예는 Vector<bool>을 요소당 한 워드를 낭비하는 대신 진짜 비트 벡터로 구현할 수 있기 때문입니다.
컴파일 타임 계산의 전형적인 예는 템플릿으로 작성한 팩토리얼입니다:
template <int N> struct Factorial { enum { value = N * Factorial<N-1>::value }; };
template <> struct Factorial<0> { enum { value = 1 } ; };
템플릿 특수화가 없다면, Factorial<4>::value에 대한 참조는 영원히 자신을 재작성하게 되고, 결국 템플릿 버전의 스택 오버플로를 일으키게 됩니다.
멤버 상수 value의 컴파일 타임 평가를 강제하기 위해 열거형을 사용했다는 점에 주목하세요.
이 템플릿이 준비되면, 코드는 Factorial<4>::value를 참조해 컴파일 타임에 계산된 24를 얻을 수 있습니다.
C++ 템플릿 메타프로그래밍에서는 타입을 사용해 구조화된 데이터를 인코딩하고, 특수화를 사용해 패턴 매칭으로 그 데이터를 분해합니다.
예를 들어, Zero 타입과 Succ<Number> 템플릿 타입을 사용해 자연수를 인코딩할 수 있습니다:
struct Zero { enum { value = 0 } ; } ;
template <typename N> struct Succ { enum { value = N::value + 1 } ; } ;
그러면 Succ<Zero>로 인코딩된 값 1에 매칭되는 템플릿을 만들 수 있습니다:
template <typename N> struct MatchOne { enum { value = 0 } ; } ;
template <> struct MatchOne<Succ<Zero> > { enum { value = 1 } ; } ;
그래서 다음 코드는 동작합니다:
cout << MatchOne<Zero >::value << endl; // 출력: 0
cout << MatchOne<Succ<Zero> >::value << endl; // 출력: 1
cout << MatchOne<Succ<Succ<Zero> > >::value << endl; // 출력: 0
튜링 완전성을 증명하려면, C++ 템플릿이 튜링 기계에 의해 구현될 수 있음을 보여야 하고(gcc가 이 부분은 처리합니다), 또한 C++ 템플릿이 튜링 기계를 구현할 수 있음을 보여야 합니다.
λ-계산은(실제로 튜링 기계보다 앞서 나왔습니다) 튜링 완전하다는 것이 잘 알려져 있으므로, 우리가 해야 할 일은 C++ 템플릿이 λ-계산을 구현할 수 있음을 보이는 것뿐입니다.
사실, 이것을 단순한 장난감 연습 이상으로 만들기 위해, 이 평가기는 조건식, 불리언, 리터럴 값도 처리할 수 있습니다.
실제로 이 언어로 약간의 프로그래밍을 할 수도 있습니다.
아래의 주석 달린 코드는 이것이 어떻게 이루어지는지 설명합니다.
이 일을 해내기 위해 C++ 언어의 많은 부분을 활용할 필요는 없습니다.
템플릿을 생성하는 템플릿, 내장된 템플릿, 심지어 템플릿을 인자로 받는 템플릿도 필요하지 않습니다.
우리는 템플릿, 템플릿 특수화, struct, typename, typedef를 사용합니다.
그리고 이것은 주석 포함 겨우 200줄 남짓한 코드입니다.
변수 이름에는 정수를 사용하겠습니다(물론 이에 대한 별칭을 쉽게 제공할 수 있습니다).
프로그램 항을 표현하기 위해 인스턴스화된 템플릿 타입을 사용해야 합니다:
// 익명 함수: template struct Lambda {} ; // 함수 호출/Application: template struct App {} ; // 참조: template struct Ref {} ; // 조건식: template struct If {} ; // 리터럴: template struct Lit {} ;
이름을 값에 매핑하는 환경은 타입 수준의 연결 리스트입니다:
// EmptyEnv는 빈 환경입니다: struct EmptyEnv ;
// Bindings<Name,Value,Env>는 환경 Env를 인코딩하는 타입이며 // Name => Value 바인딩으로 확장됩니다: template <int Name, typename Value, typename Env> struct Binding {} ;
템플릿 메타함수 EnvLookup은 이름과 환경을 받아 값을 산출합니다:
// EnvLookup<Name,Env> :: result는 Env에서 Name의 값을 찾습니다: template <int Name, typename Env> struct EnvLookup {} ;
template <int Name> struct EnvLookup <Name,EmptyEnv> {} ; // 이름을 찾지 못함.
template <int Name, typename Value, typename Env> struct EnvLookup <Name, Binding<Name,Value,Env> > { Value typedef result ; } ;
template <int Name, int Name2, typename Value2, typename Env> struct EnvLookup <Name, Binding<Name2,Value2,Env> > { typename EnvLookup<Name,Env> :: result typedef result ; } ;
EnvLookup은 중요한 관례를 보여 줍니다. 타입 수준 메타함수를 정의할 때 우리는 반환값을 result 필드로 typedef합니다.
result 필드에 접근하면 확장이 강제되고 반환값이 산출됩니다.
물론 템플릿 메타프로그램에서 런타임 "값"은 실제로는 타입입니다:
// 클로저: template struct Closure {} ; // 불리언: struct True {} ; struct False {} ;
마지막으로, eval과 apply를 타입 수준 메타함수로 정의합니다:
// Eval<Exp,Env> :: result는 환경 Env에서 식 Exp의 값입니다. template <typename Exp, typename Env> struct Eval {} ;
// Apply<Proc,Value> :: result는 Proc를 Value에 적용한 값입니다. template <typename Proc, typename Value> struct Apply {} ;
// 리터럴은 자기 자신으로 평가됩니다: template <typename T, typename Env> struct Eval <Lit<T>, Env> { T typedef result ; } ;
// 변수 참조는 현재 환경에서 조회됩니다: template <int Name, typename Env> struct Eval <Ref<Name>, Env> { typename EnvLookup<Name, Env> :: result typedef result ; } ;
// 람다 항은 클로저로 평가됩니다: template <int Name, typename Body, typename Env> struct Eval <Lambda<Name,Body>, Env> { Closure<Lambda<Name, Body>, Env> typedef result ; } ;
// 적용은 함수 식의 값을 인자 식의 값에 적용합니다: template <typename Fun, typename Arg, typename Env> struct Eval<App<Fun, Arg> , Env> { typename Apply<typename Eval<Fun,Env> :: result , typename Eval<Arg,Env> :: result > :: result typedef result ; } ;
// 참 분기: template <typename Then, typename Else, typename Env> struct Eval<If<True,Then,Else>,Env> { typename Eval<Then,Env> :: result typedef result ; } ;
// 거짓 분기: template <typename Then, typename Else, typename Env> struct Eval<If<False,Then,Else>,Env> { typename Eval<Else,Env> :: result typedef result ; } ;
// 조건식을 평가: template <typename Cond, typename Then, typename Else, typename Env> struct Eval<If<Cond,Then,Else>,Env> { typename Eval<If<typename Eval<Cond,Env> :: result, Then, Else>, Env> :: result typedef result ; } ;
// 클로저 내부의 람다 항 본문으로 전이: template <int Name, typename Body, typename Env, typename Value> struct Apply<Closure<Lambda<Name,Body>, Env>, Value> { typename Eval<Body, Binding<Name,Value,Env> > :: result typedef result ; } ;
이제 간단한 템플릿 메타프로그램을 구성하고 실행할 수 있습니다:
// ((lambda (x) x) 2) 테스트: enum { X } ;
int x = Eval<App<Lambda<X,Ref<X> >,Lit<Succ<Succ<Zero> > > >,EmptyEnv> :: result :: value ;
assert(x == 2) ;
// (if #f 0 1) 테스트: int y = Eval<If<Lit<False>,Lit<Zero>,Lit<Succ<Zero> > >,EmptyEnv> :: result :: value ;
assert(y == 1) ;
이 글에서 보여 준 원리 중 일부를 연습해 보고 싶다면, 도전 과제를 하나 제공합니다. 템플릿 메타프로그램으로 덧셈을 구현하는 것입니다.
뼈대 코드를 사용할 수 있습니다.
작동하게 만들려면 Add struct의 특수화 두 개를 만들어야 합니다.
