Blog Dice

Advent of Code in C++ Template Metaprogramming

Nelson Elhage

C++テンプレートメタプログラミングで解くAdvent of Code

原文は Nelson Elhage により に公開されました。 このブログを購読する

この12月、ふと出来心が芽生えて、コンパイル時のC++メタプログラミングだけでAdvent of Codeを何日分解けるか試してみることにした。

執筆時点で2日分を解いたところだが、これ以上進められるかはわからない。とはいえ、昨日時点では1日できればいいと思っていたし、そこからさらに、最初の挑戦のあとにもう無理だろうと思っていたより先まで進んでいる。まあ、なるようになるだろう。

とはいえ、Day 1はちょっとした解説を書くには十分面白かった。コードはGitHubで公開しているが、ここでもDay 1について注釈付きで詳しく見ていこう。

基本的な型

まずはコンパイル時に使える基本的なlist型を定義し、値を型システムに持ち上げるためのliteral<v>も用意する。constexprは簡単になりすぎるので使わないことにしたが、基本的な算術演算やコンパイル時整数、真偽値は使ってもよいことにした。

template <typename... Elts>
struct list {};

template <auto v>
struct literal {
    constexpr static auto value = v;
};

前置き：入力の読み込み

理想を言えば、最大限ピュアにするために新しいC++23の#embedディレクティブで入力を読み込みたいところだが、執筆時点では対応しているコンパイラを見つけるのが難しそうだった。そこでxxd -iを使ったポリフィルに頼ることにした。xxd -i < input.txt > input.iを実行し、#includeと可変長テンプレートを使って入力を取り込む。入力ファイルの指定にはプリプロセッサのちょっとしたトリックを使って、-Dコンパイラフラグで渡すようにする。

template <auto... Elt>
struct read_input {
    using type = list<literal<char(Elt)>...>;
};

#define _QUOTED(x) #x
#define QUOTED(x) _QUOTED(x)

#ifndef INPUT
// Default value to keep my IDE environment happy
#define INPUT /dev/null
#endif

using problem = read_input<
#include QUOTED(INPUT)
>::type;

畳み込み（fold）

C++のテンプレートメタプログラミングはかなり関数型言語的なので、リストに対して定義する主要な操作がfoldになるのは自然なことだ。これは比較的定番の構成である。

template <template<typename, typename> typename Fn,
    typename Init, typename List>
struct fold {};

template <template<typename, typename> typename Fn,
    typename Init>
struct fold<Fn, Init, list<>> {
    using type = Init;
};

template <template<typename, typename> typename Fn,
          typename Init, typename El1, typename... Elts>
struct fold<Fn, Init, list<El1, Elts...>> {
    using type = fold<
        Fn,
        typename Fn<Init, El1>::type,
        list<Elts...>>::type;
};

その他のヘルパー

もう少しヘルパーを導入すれば、Part 1の準備はほぼ整う。nilという番兵、基本的なif条件分岐、そして引数のうち最初にnilでないものを返すor_else関数を追加する。

struct nil;

template <typename T>
struct is_nil { using type = literal<false>; };

template <>
struct is_nil<nil> { using type = literal<true>; };

template <typename Cond, typename Then, typename Else>
struct if_else {};

template <typename Then, typename Else>
struct if_else<literal<true>, Then, Else> { using type = Then; };

template <typename Then, typename Else>
struct if_else<literal<false>, Then, Else> { using type = Else; };

template <typename L, typename R>
struct or_else { using type = L; };

template <typename R>
struct or_else<nil, R> { using type = R; };

Part 1

Advent of Codeをやっていない人向けに問題を簡単におさらいしておくと、入力ファイルの各行について、その行に含まれる最初と最後の数字を見つけ、それらを連結して2桁の数（「キャリブレーション値」）を作り、ファイル内のすべてのキャリブレーション値の合計を出力する必要がある。

効率を考えて、入力全体に対する1回のfoldでこれを実装する。処理を進めながら、(これまでの合計、現在の行の最初の数字、行内で最後に見た数字)というタプルで状態を管理していく。

template <typename Accum, typename FirstDigit, typename LastDigit>
struct State {
    using accum = Accum;
    using first = FirstDigit;
    using last = LastDigit;
};

using empty_state = State<literal<0>, nil, nil>;

foldで使う関数は、シンプルなルールで状態を進めていく。

  • 文字が改行なら、その行のキャリブレーション値を計算してアキュムレータに加算し、行ごとの状態をリセットする。
  • 文字が数字なら、「最後の数字」を無条件にこの数字で更新する
    • さらに、この行でまだ数字を見ていなければ「最初の数字」も更新する。

これらはいずれも既存のヘルパーを素直に応用したものだ。

template <typename T>
using as_digit = if_else<
    literal<T::value >= '0' && T::value <= '9'>,
    literal<T::value - '0'>,
    nil>;

template <typename In, typename Char>
struct Fn {
    using digit = as_digit<Char>::type;

    struct IfNewline {
        using type = State<
            literal<In::accum::value + 10 * In::first::value + In::last::value>,
            nil,
            nil>;
    };

    using type = if_else<
        literal<Char::value == '\n'>,
        IfNewline,
        if_else<
            typename is_nil<digit>::type,
            In,
            typename if_else<
                typename is_nil<typename In::first>::type,
                State<typename In::accum, digit, digit>,
                State<typename In::accum, typename In::first, digit>
                >::type
            >>::type::type;
};

ひとつ工夫が必要なのは、外側のif_elseを遅延評価にするために、引数ではなくその結果に対して::typeを評価している点だ。これにより、コンパイラは実際に選択された分岐（then側かelse側）のみを評価するようになる。

試してみる

利便性のために、結果を出力する部分だけは少しだけ実行時の動作を許容する。

int main() {
    using answer = solve<problem>::type;
    printf("%d\n", answer::value);
}

これで、問題文に含まれている最初のテストケースを検証できる。

$ xxd -i < test.txt > test.i && \
  c++ -DINPUT=test.i -std=c++20 part1.cc -o out/part1 && \
  out/part1
142

しかし実際の入力で試すと、問題が発生する。

$ xxd -i < input.txt > input.i && \
  c++ -DINPUT=input.i -std=c++20 part1.cc -o out/part1 && \
  out/part1

part1.cc:8:1: fatal error: recursive template instantiation exceeded maximum depth of 1024
using as_digit = if_else<
 [cut C++ template spew]

part1.cc:8:1: note: use -ftemplate-depth=N to increase recursive template instantiation depth

根本的な問題は、foldが入力の1文字ごとに再帰する必要があるのに、実際の入力は2万文字を超えていることだ。エラーメッセージの提案どおり-ftemplate-depthを増やしてみることはできる。私の環境でも十分大きな値を指定すればコンパイルはできるのだが、clangがスタック容量について恐ろしげな警告を出し、しかも非常に遅く、コンパイルに90秒以上かかる。

別のアプローチが必要だ。

foldの最適化

ここでの問題はかなり根本的で、再帰的なテンプレート展開はテンプレートメタプログラミングにおけるほぼ唯一の手段だからだ。ただ、実はまだ一手残されている。

list<>は可変長テンプレートなので、その中身全体をC++のパラメータパックとして操作できる。引数をパラメータパックのまま保てる限り、コンパイラ内部の比較的高速なパスを利用でき、はるかに効率的に処理できる。

上記のcppreferenceのページを読み込むと、C++17で「fold expression（畳み込み式）」が追加されたことに気づく。これはパラメータパックを、任意に選んだ演算子で畳み込んだ式に展開する方法だ。これは我々がやろうとしていることと不気味なほど似ているが、こちらは値レベルの演算子を使った値レベルの操作である。

しかし、autoとdecltype、そしてラッパー構造体をうまく使えば、これは問題にならない。fold expressionの型チェックの過程で、型レベルの計算を実行する型を構築できるのだ。

コンパイラは依然として巨大にネストした式を処理しなければならないが、私のテストでは、2万段のテンプレート再帰よりもはるかに効率的だった。

template<template<typename, typename> typename Fn>
struct fold_helper {
    template <typename T>
    struct F {
        using type = T;

        template <typename R>
        auto operator<<(F<R>) {
            return F<typename Fn<T, R>::type>{};
        };
    };
};

template <template<typename, typename> typename Fn,
          typename Init, typename... Elts>
struct fold<Fn, Init, list<Elts...>> {
    template <typename T>
    using F = fold_helper<Fn>::template F<T>;

    using type = decltype((F<Init>{} << ... << F<Elts>{}))::type;
};

構造体fold_helper<Fn>::Fは、我々の型レベルの関数を式レベルの演算子で評価できる形に変換する。式fold_helper<Fn>::F<A>{} << fold_helper<Fn>::F<B>{}はFn<A, B>::type型の値として評価される。これができれば、リストの要素をその変換を使ってfold expressionに展開し、decltypeで出力の型を取得できる。どの段階でも実際にコードが生成されたり、ましてや（恐ろしいことに）実行されたりすることはない。

そしてこれはうまくいく！このfoldの実装なら、上記のPart 1の解法は私のM1 Airで約1秒でコンパイルでき、正しい答えを返してくれる！

$ xxd -i < input.txt > input.i && \
  time c++ -fbracket-depth=25000 -DINPUT=input.i -std=c++20 \
    part1.cc -o out/part1 && \
  out/part1
c++ -fbracket-depth=25000 -DINPUT=input.i -std=c++20 part1.cc -o out/part1  1.10s user 0.06s system 101% cpu 1.141 total
54390

Part 2

Part 2では、数字は綴りでも表されるようになる。たとえばseven82683のキャリブレーション値は「73」になる。

まずはちょっとした抽象化を導入しよう。fold内で改行を扱う方法は機能したが、少し面倒だった。改行での分割を抽象化し、個々の行だけを考えれば済むようにするヘルパーを書くことにする。

インターフェースは、たとえばリストのリストを実体化するのではなく、行に対するfoldという形にする。このように処理をストリーミングし続けることは、パフォーマンス上非常に重要だ。このヘルパー自体も、foldを素直に応用したものに過ぎない。

template <typename Head, typename Tail>
struct pair {
    using head = Head;
    using tail = Tail;
};

template <template<typename, typename> typename Fn, typename Delim>
struct fold_lines_f {
    template <typename In, typename Elt>
    struct F{
        using type = pair<
            typename append<typename In::head, Elt>::type,
            typename In::tail
            >;
    };

    template <typename A>
    struct F<A, Delim>{
        using type = pair<
            list<>,
            typename Fn<typename A::tail, typename A::head>::type
            >;
    };
};

template<template<typename, typename> typename Fn,
         typename Init, typename L,
         typename Delim = literal<'\n'>>
struct fold_lines {
    using type = fold<
        fold_lines_f<Fn, Delim>::template F,
        pair<list<>, Init>,
        L>::type::tail;
};

これができたので、あとは1行の中でキャリブレーション値を計算する必要がある……

手作業で状態機械をコンパイルする

ここでも、各行に対する1回のfoldでキャリブレーションを実装する。

取りうるすべての数字にマッチするために、有限状態機械によるマッチャーを用意し、<状態, 文字>の各ペアについて遷移規則を書いていく。これは本質的に、一部の正規表現実装が内部で生成するDFAと同じものだ。状態の名前は、これまでに見た「関連する」部分文字列で付ける。たとえばSseveは直前に「seve」を見たことを意味し、この状態でnが来れば数字の7を見つけたことになる。

多くの数字の綴りには、別の数字の先頭にもなりうる文字が含まれているため、遷移ではそれを考慮する必要がある。たとえば状態Sseveでiを見た場合、文字列が「seveight」かもしれずeightを処理する必要があるので、Seiに遷移しなければならない。幸い、2つの数字の綴りがより複雑に重なるケースはないので、状態機械は比較的シンプルに収まる。

まずは状態の定義から始めよう。S0は「関連する接頭辞なし」を意味するものとする。

struct S0 {};

// one
struct So {};
struct Son {};
// two
struct St {};
struct Stw {};
// three
struct Sth {};
struct Sthr {};
struct Sthre {};
// four
struct Sf {};
struct Sfo {};
struct Sfou {};
// five
struct Sfi {};
struct Sfiv {};
// six
struct Ss {};
struct Ssi {};
// seven
struct Sse {};
struct Ssev {};
struct Sseve {};
// eight
struct Se {};
struct Sei {};
struct Seig {};
struct Seigh {};
// nine
struct Sn {};
struct Sni {};
struct Snin {};

次に遷移規則を定義できる。ワイルドカードを多用し、部分特殊化の相対的な具体性に頼って正しい規則が選ばれるようにする。

他のどの規則にもマッチしなければ、S0に戻る。

template <typename St, typename El>
struct next_state { using type = S0; };

そして、どの数字の先頭文字かを見つけ、かつより具体的な規則がマッチしなかった場合は、そのまま対応する状態へ直接遷移できる。

// Initial letters
template<typename S> struct next_state<S, literal<'o'>> { using type = So; };
template<typename S> struct next_state<S, literal<'t'>> { using type = St; };
template<typename S> struct next_state<S, literal<'f'>> { using type = Sf; };
template<typename S> struct next_state<S, literal<'s'>> { using type = Ss; };
template<typename S> struct next_state<S, literal<'e'>> { using type = Se; };
template<typename S> struct next_state<S, literal<'n'>> { using type = Sn; };

それから規則の内部や規則間の遷移を定義する。そのほとんどは単純で、例えば(So, 'n') → Sonといった具合だが、別の数字のマッチングの「途中」に飛び込む可能性があるものには注意が必要だ。

// one
template<> struct next_state<So,    literal<'n'>> { using type = Son; };
template<> struct next_state<Son,   literal<'e'>> { using type = Se; };
template<> struct next_state<Son,   literal<'i'>> { using type = Sni; };
// two
template<> struct next_state<St,    literal<'w'>> { using type = Stw; };
// three
template<> struct next_state<St,    literal<'h'>> { using type = Sth; };
template<> struct next_state<Sth,   literal<'r'>> { using type = Sthr; };
template<> struct next_state<Sthr,  literal<'e'>> { using type = Sthre; };
template<> struct next_state<Sthre, literal<'i'>> { using type = Sei; };
// four
template<> struct next_state<Sf,    literal<'o'>> { using type = Sfo; };
template<> struct next_state<Sfo,   literal<'u'>> { using type = Sfou; };
template<> struct next_state<Sfo,   literal<'n'>> { using type = Son; };
// five
template<> struct next_state<Sf,    literal<'i'>> { using type = Sfi; };
template<> struct next_state<Sfi,   literal<'v'>> { using type = Sfiv; };
// six
template<> struct next_state<Ss,    literal<'i'>> { using type = Ssi; };
// seven
template<> struct next_state<Ss,    literal<'e'>> { using type = Sse; };
template<> struct next_state<Sse,   literal<'v'>> { using type = Ssev; };
template<> struct next_state<Sse,   literal<'i'>> { using type = Sei; };
template<> struct next_state<Ssev,  literal<'e'>> { using type = Sseve; };
template<> struct next_state<Sseve, literal<'i'>> { using type = Sei; };
// eight
template<> struct next_state<Se,    literal<'i'>> { using type = Sei; };
template<> struct next_state<Sei,   literal<'g'>> { using type = Seig; };
template<> struct next_state<Seig,  literal<'h'>> { using type = Seigh; };
// nine
template<> struct next_state<Sn,    literal<'i'>> { using type = Sni; };
template<> struct next_state<Sni,   literal<'n'>> { using type = Snin; };

まだ「マッチ」したのがいつなのか、あるいはマッチしたときに何をすべきかを定義していない。この問題では、「マッチ成功」を状態遷移とは別の関数として定義する方が、どちらの関数もずっとシンプルになることがわかる。技術的に言えば、このマッチャーで実装しているのは、電気工学でいうミーリー型状態機械に相当するものだ。

match_digit関数はnext_stateと似たシグネチャ — state, input → digit | nil — を持ち、特定の位置でどの数字（もしあれば）がマッチしたかを教えてくれる。

template <typename State, typename El>
struct match_digit { using type = nil; };

template <> struct match_digit<Son,   literal<'e'>> { using type = literal<1>; };
template <> struct match_digit<Stw,   literal<'o'>> { using type = literal<2>; };
template <> struct match_digit<Sthre, literal<'e'>> { using type = literal<3>; };
template <> struct match_digit<Sfou,  literal<'r'>> { using type = literal<4>; };
template <> struct match_digit<Sfiv,  literal<'e'>> { using type = literal<5>; };
template <> struct match_digit<Ssi,   literal<'x'>> { using type = literal<6>; };
template <> struct match_digit<Sseve, literal<'n'>> { using type = literal<7>; };
template <> struct match_digit<Seigh, literal<'t'>> { using type = literal<8>; };
template <> struct match_digit<Snin,  literal<'e'>> { using type = literal<9>; };

template<typename S> struct match_digit<S, literal<'0'>> { using type = literal<0>; };
template<typename S> struct match_digit<S, literal<'1'>> { using type = literal<1>; };
template<typename S> struct match_digit<S, literal<'2'>> { using type = literal<2>; };
template<typename S> struct match_digit<S, literal<'3'>> { using type = literal<3>; };
template<typename S> struct match_digit<S, literal<'4'>> { using type = literal<4>; };
template<typename S> struct match_digit<S, literal<'5'>> { using type = literal<5>; };
template<typename S> struct match_digit<S, literal<'6'>> { using type = literal<6>; };
template<typename S> struct match_digit<S, literal<'7'>> { using type = literal<7>; };
template<typename S> struct match_digit<S, literal<'8'>> { using type = literal<8>; };
template<typename S> struct match_digit<S, literal<'9'>> { using type = literal<9>; };

（最後の10個の特殊化は、プライマリ定義内の条件分岐で置き換えることもできるが、多少冗長でもこちらの方がわかりやすいと思う）。

これらの型が揃えば、Part 1とよく似たfoldで1行分のキャリブレーション値を計算できる。Part 1との違いは、全体のアキュムレータを追う必要がなくなったことだ（それはfold_linesで外側のループに任せる）。代わりにマッチャーの状態を保持する必要があるので、状態クラスはよく似た形になる。

template <typename MatchState, typename First, typename Last>
struct CalibrationState {
    using state = MatchState;
    using first = First;
    using last = Last;
};

1要素進める際には、出力状態と（あれば）マッチした数字を計算する。「最初／最後に見た数字」の計算を簡単にするために、先ほどのヘルパーも活用する。

template <typename State, typename El>
struct LineF {
    using new_state = next_state<typename State::state, El>::type;
    using digit = match_digit<typename State::state, El>::type;

    using type = CalibrationState<
        new_state,
        typename or_else<typename State::first, digit>::type,
        typename or_else<digit, typename State::last>::type
        >;
};

fold用の関数ができれば、キャリブレーション値の計算は簡単だ。

template<typename Line>
struct calibration {
    using acc = fold<LineF, CalibrationState<S0, nil, nil>, Line>::type;
    using type = literal<acc::first::value*10 + acc::last::value>;
};

簡単なテストケースを書くこともできる。C++のテンプレートメタプログラミングはインラインテストのサポートが素晴らしい。

static_assert(is_same<
              typename calibration<typename read_input<
              's', 'e', 'v', 'e', 'n', '8', '2', '6', '8', '3'
              >::type>::type,
              literal<73>>::value);

すべてを組み合わせる

行に対するfoldはキャリブレーション値の単純な合計であり、ここまで来ればほぼ自明だ。

template<typename State, typename Line>
struct Fn {
    using lineval = calibration<Line>::type;

    using type = literal<State::value + lineval::value>;
};

using answer = fold_lines<Fn, literal<0>, problem>::type;

うまくいった！しかも私のノートPCでもコンパイルはわずか約1.5秒で済む！

おわりに

私は過去にもあちこちでC++のテンプレートメタプログラミングを少しばかりやってきた。たとえばC++用のシンプルなx86アセンブラを書いたこともあるが、C++17のTMPに本格的に取り組み、どっぷり深みにはまったのは今回が初めてだった。

そして、こういう感想は以前にも聞いたことがあったが、この問題に取り組んでみて……正直、現代のC++テンプレートはなかなかイケてる関数型プログラミング言語だと言わざるを得ない。ちょっとした嬉しい機能まで備えている！そして、比較的効率的なリスト処理さえ可能にするfold expressionのトリックを発見できたのは嬉しい驚きだった。

あと何日分やるのか、この先どれだけC++を書くことになるのかは……まだわからないが、結局のところとても楽しめた！

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。

コメント