컴파일 타임에 정수 정렬하기(with TMP)

본 글은 Github 갤러리에서 진행한 주간 문제풀이: 컴파일 타임 소팅의 솔루션 제작 과정 및 설명입니다.



문제의 접근 방법은 다음과 같습니다.


  1. non-type variadic template을 사용해 타입으로 임의 길이의 정수 배열을 구현
template< int X, int... Xs >
struct Arr {
    static constexpr int head = X;
    using Tail = Arr< Xs... >;
    template< int Y >
    using Push_back = Arr< X, Xs..., Y >;
};

template< int X >
struct Arr< X > {
    static constexpr int head = X;
    using Tail = int; // 비어있는 배열은 int로 표현
    template< int Y >
    using Push_back = Arr< X, Y >;
};

배열의 원소가 한 개 있는 경우와 두 개 이상 있는 경우로 나누어 구현했습니다. head를 사용해 첫 번째 원소에 접근하고, Tail을 사용해 첫 번째 원소를 제외한 배열에 접근할 수 있습니다. Push_back으로 원소를 추가할 수 있습니다.


  1. 배열의 Add 연산을 구현
template< typename T1, typename T2 >
struct Add {
    using Result = typename Add< typename T1::template Push_back< T2::head >, typename T2::Tail >::Result;
};

template<>
struct Add< int, int > {
    using Result = int;
};

template< typename T2 >
struct Add< int, T2 > {
    using Result = T2;
};

template< typename T1 >
struct Add< T1, int > {
    using Result = T1;
};

Add 연산은 피연산자 두 개가 각각 빈 배열(int)인지, 그렇지 않은지에 따라 네 가지로 나누어 구현했습니다. Result를 사용해 결과에 접근합니다.

다음과 같이 사용할 수 있습니다.

Add< Arr< 1, 2 >, Arr< 3, 4 > >::Result // Arr< 1, 2, 3, 4 >

  1. 배열의 Filter 연산을 구현
template< template< int > typename F, typename T, typename Enable = void >
struct Filter {
    using Result = int;
};

template< template< int > typename F, typename T >
struct Filter< F, T, typename std::enable_if_t< !std::is_same< T, int >::value && F< T::head >::value > > {
    using Result = typename Add< Arr< T::head >, typename Filter< F, typename T::Tail >::Result >::Result;
};

template< template< int > typename F, typename T >
struct Filter< F, T, typename std::enable_if_t< !std::is_same< T, int >::value && !F< T::head >::value > > {
    using Result = typename Filter< F, typename T::Tail >::Result;
};

Filter의 대상이 빈 배열인지, 비지 않았고 첫 원소가 조건을 만족하는지, 비지 않았고 첫 원소가 조건을 만족하지 않는지에 따라 세 가지로 나누어 구현했습니다. 조건자 타입은 정수를 템플릿 인자로 받아 static 멤버인 value를 사용해 인자가 조건을 만족하는지 표현해야 합니다. Result를 사용해 결과에 접근합니다.

다음과 같이 사용할 수 있습니다.

template< int N >
struct Test {
    static constexpr bool value = N % 2;
};

Filter< Test, Arr< 1, 2, 3, 4, 5, 6 > >::Result // Arr< 1, 3, 5 >

  1. Cmp 클래스를 구현
template< int X, typename C >
struct Cmp {
    template< int Y >
    struct Less {
        static constexpr bool value = C()(Y, X);
    };

    template< int Y >
    struct Equal {
        static constexpr bool value = !C()(X, Y) && !C()(Y, X);
    };

    template< int Y >
    struct Greater {
        static constexpr bool value = C()(X, Y);
    };
};

커스텀 비교자 타입을 받아 <, =, >연산을 구현해 주는 Cmp 클래스를 만듭니다.

다음과 같이 사용할 수 있습니다.

template< int X >
using Lc = typename Cmp< 5, std::greater< int > >::template Less< X >;
Filter< Lc, Arr< 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 > >::Result // Arr< 6, 7, 8, 9 >

  1. 퀵소트를 구현
template< typename T, typename C = std::less< int > >
struct Sort {
    template< int X >
    using Lc = typename Cmp< T::head, C >::template Less   < X >;
    using Ls = typename Sort< typename Filter< Lc, T >::Result, C >::Result;

    template< int X >
    using Ec = typename Cmp< T::head, C >::template Equal  < X >;
    using Es = typename Filter< Ec, T >::Result;

    template< int X >
    using Gc = typename Cmp< T::head, C >::template Greater< X >;
    using Gs = typename Sort< typename Filter< Gc, T >::Result, C >::Result;

    using Result = typename Add< typename Add< Ls, Es >::Result, Gs >::Result;
};

template< typename C >
struct Sort< int, C > {
    using Result = int;
};

정렬 대상이 빈 배열인지, 그렇지 않은지에 따라 두 가지로 나누어 구현했습니다. Result를 사용해 결과에 접근합니다.

다음과 같이 사용할 수 있습니다.

Sort< Arr< 6, 5, 0, 2, 7, 9, 4, 1, 8, 3 > >::Result // Arr< 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 >

  1. 출력
auto main() -> int {
    Sort< Arr< 6, 5, 0, 2, 7, 9, 4, 1, 8, 3 >, std::less   < int > >::Result l = 0;
    Sort< Arr< 6, 5, 0, 2, 7, 9, 4, 1, 8, 3 >, std::greater< int > >::Result g = 0;
    return 0;
}

컴파일에 실패하되 에러 메시지로 타입 정보를 띄우는 가장 쉬운 방법 중 하나는 unconvertable한 값을 대입하는 것입니다. 구체적인 에러 메시지는 컴파일러마다 다르겠지만, 제 컴파일러(GCC 9.1)는 다음과 같은 메시지를 출력합니다. 성공입니다!

main.cpp: In function ‘int main()’:
main.cpp:4:82: error: conversion from ‘int’ to non-scalar type ‘Sort<Arr<6, 5, 0, 2, 7, 9, 4, 1, 8, 3>, std::less<int> >::Result’ {aka ‘Arr<0, 1, 2, 3, 4, 5, 6, 7, 8, 9>’} requested
    4 |     Sort< Arr< 6, 5, 0, 2, 7, 9, 4, 1, 8, 3 >, std::less   < int > >::Result l = 0;
      |                                                                                  ^
main.cpp:5:82: error: conversion from ‘int’ to non-scalar type ‘Sort<Arr<6, 5, 0, 2, 7, 9, 4, 1, 8, 3>, std::greater<int> >::Result’ {aka ‘Arr<9, 8, 7, 6, 5, 4, 3, 2, 1, 0>’} requested
    5 |     Sort< Arr< 6, 5, 0, 2, 7, 9, 4, 1, 8, 3 >, std::greater< int > >::Result g = 0;
      |

전체 코드는 제 깃헙에서 확인하실 수 있습니다.

2 Likes

와! 흑마법 !

잘모르니까 지나가겠읍니다.

1 Like

이런건 보면 어찌어찌 이해는 하겠는데 작성을 못하겠네요 허허

1 Like

프로그래밍을 처음 배우는 사람한테 TMP만 가르치고싶다…

멋지군요.
컴파일 시간은 어느 정도 걸리는지 궁금하네요.

1 Like

컴파일 타임에 정렬 ?!
마치 …

1 Like

emable_ifis_same 같은 템플릿 레벨 연산자는 특수한 내장 함수인가요 아니면 사용자 수준에서도 직접 작성할 수는 있는 구조인가요

1 Like

작성 가능합니다. SFINAE로 찾아보세용

2 Likes

마지막에 에러로 띄우는게 너무심쿵이에요

1 Like

왜 이토록 힘들게 해야 하는거죠

1 Like

Just for fun… :joy:

:joy::joy:

(define-syntax ct-sort
    (er-macro-transformer
         (lambda (arg rename compare)
		     (import (chicken sort))
		     (+ (sort! (eval (cadr arg)) <)))))

(ct-sort #(6 1 5 9 2 7 3 4 8))
root@goorm:/workspace/PL# csc compile-time-sort.scm

Error: (+) during expansion of (ct-sort ...) - bad argument type - not a number: #(1 2 3 4 5 6 7 8 9)

        Call history:

        <syntax>          (##core#begin (ct-sort #(1 2 3 4 5 6 7 8 9)))
        <syntax>          (ct-sort #(1 2 3 4 5 6 7 8 9))
        <eval>    (##sys#load-library (##core#quote data-structures))
        <eval>    (+ (sort! (eval (cadr arg)) <))
        <eval>    (sort! (eval (cadr arg)) <)
        <eval>    (eval (cadr arg))
        <eval>    (cadr arg)    <--

Error: shell command terminated with non-zero exit status 17920: '/usr/local/bin/chicken' 'compile-time-sort.scm' -output-file 'compile-time-sort.c'
1 Like