用 C++ 樣板元程式設計解 Advent of Code
原文由 Nelson Elhage 于 發布，訂閱此部落格
今年十二月，我那股無端作祟的衝動突然發作，決定試試看能完全用編譯期的 C++ 元程式設計解出 Advent of Code 的幾天題目。
寫這篇文章時，我已經解了兩天，也不確定還能不能繼續下去。不過，這已經比我昨天預期的多了一天，而昨天的預期又比我第一次嘗試後以為能撐到的進度更遠。所以就再看看吧。
話雖如此，第一天的題目本身就夠有趣，值得寫一篇短文分享。你可以在 GitHub 上找到程式碼，不過這裡也會帶你逐步解析第一天的解法！
基本型別
我們先定義一個基本的編譯期 list 型別，也會用到 literal<v> 來把值提升到型別系統中。我決定捨棄 constexpr，因為那樣太簡單了，不過還是允許自己使用基本的算術運算以及編譯期的整數和布林值。
template <typename... Elts>
struct list {};
template <auto v>
struct literal {
constexpr static auto value = v;
};前言：讀取輸入
理想上，我會想用新的 C++23 #embed 指令來讀取輸入，以追求極致的純粹；但寫這篇文章時，似乎很難找到支援它的編譯器。因此，我退而求其次，用 xxd -i 做了一個 polyfill。我們可以執行 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;摺疊
C++ 樣板元程式設計在很大程度上就是一種函數式語言，因此我們在 list 上定義的主要操作自然就是 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;
};其他輔助工具
我們再引入幾個輔助工具，就差不多準備好進入第一部分了。我們會加入一個 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; };第一部分
如果你沒有參加 Advent of Code，這裡快速回顧一下題目：對於輸入檔中的每一行，我們需要找出該行中的第一個和最後一個數字，然後將它們串成一個兩位數（即「校準值」），並輸出檔案中所有校準值的總和。
為了效率，我們會用對輸入做一次 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;
};其中一個比較 tricky 的地方是，為了讓外層的 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 需要對輸入中的每個字元進行遞迴，而提供的測試輸入超過 20,000 個字元！我們可以照建議嘗試調大 -ftemplate-depth；在我的機器上，用夠大的數值的確可以讓程式編譯過，但 clang 會發出關於堆疊容量的可怕警告，而且速度非常慢——編譯要花 90 秒以上。
我們需要不同的方法。
優化 fold
這裡的問題相當根本；遞迴樣板展開基本上就是樣板元程式設計中唯一可用的手段。不過，事實證明我們還有一招可用。
list<> 是一個可變樣板，這意味著我們可以把它的全部內容當作 C++ 參數包來操作。只要能讓參數保持為參數包的形式，就能在編譯器內部走相對快速的路徑，效率高得多。
仔細研讀上述 cppreference 頁面後，我們注意到 C++17 加入了「摺疊表示式」——一種將參數包轉換為對其摺疊使用者自選運算子的表示式的方法！這跟我們想做的事驚人地相似，只不過它是在值的層級上運作，使用值層級的運算子。
然而，事實證明只要巧妙運用 auto、decltype 和一個包裝結構，這完全不成問題——我們可以建構出在摺疊表示式型別檢查過程中執行型別層級運算的型別。
編譯器仍然得處理一個層層嵌套的巨大表示式，但在我的測試中，這比 20,000 層深的樣板要有效率得多：
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 的值。有了這個，我們就能利用該轉譯將 list 的元素展開成一個摺疊表示式，並用 decltype 取得輸出的型別。在整個過程中，完全不會產生任何程式碼——更不會——天哪！——真的去執行它。
而且這真的可行！有了這個 fold 實作，上述第一部分的解法在我的 M1 Air 上大約一秒內就能編譯完成，並給出正確答案！
$ 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第二部分
在第二部分中，數字現在也可能是用英文拼出來的——seven82683 的校準值是「73」。
我們先引入一個小小的抽象。在 fold 中處理換行雖然可行，但有點麻煩。我們可以寫一個輔助工具，把按換行分割的邏輯抽象掉，讓我們只需關注個別的行。
這個介面將會是一個針對行的 fold，而不是例如具體化出一個 list-of-lists；以這種串流方式保持處理對於效能非常重要。這個輔助工具本身也是 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;
};有了這個之後，我們需要在單一行內計算校準值……
手動編譯狀態機
我們將再度對每一行使用單一次 fold 來實作校準值的計算。
為了匹配各種可能的數字，我們會維護一個有限狀態機匹配器，並為每個 <狀態、字元> 配對撰寫轉移規則——這本質上就是某些正則表示式實作在底層會產生的 DFA。我們會用至今已看到的「相關」子字串來命名狀態；舉例來說，Sseve 表示我們剛剛看到了「seve」；在這種情況下，如果遇到 n，就表示我們找到了數字 7。
請注意，許多數字的拼寫中包含的字母也可能是另一個數字開頭的字母，我們需要在轉移中處理這些情況；例如，如果我們處於 Sseve 狀態並看到 i，就需要轉移到 Sei，因為我們可能正在處理字串「seveight」而需要處理其中的 eight。幸好，沒有任何兩個數字有更複雜的重疊，所以狀態機仍然相對簡單。
我們先從狀態定義開始，用 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; };我們還沒定義何時算是「匹配」成功，或匹配成功時該做什麼；事實證明，對於這個問題，將「成功匹配」定義為與狀態轉移分開的函式，會讓兩個函式都簡單得多。用比較技術性的說法，我們實質上是在為這個匹配器實作電機工程師所說的 Mealy 狀態機。
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 個特化，不過我覺得這個版本雖然有點冗長，卻更直觀一些。）
有了這些型別，我們現在就可以用跟第一部分非常相似的 fold 來計算單一行的校準值。與之前相比，我們不再需要追蹤整體的累加器——我們會用 fold_lines 把它推到外層迴圈——但我們仍需要保留匹配器的狀態，因此我們的狀態類別看起來非常相似：
template <typename MatchState, typename First, typename Last>
struct CalibrationState {
using state = MatchState;
using first = First;
using last = Last;
};要推進一個元素，我們會計算輸出狀態以及匹配到的數字（如果有的話）。我們也會用一些輔助工具來簡化「第一個／最後看到的數字」的計算：
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;成功了！而且在我的筆電上，編譯「只」花了約 1.5 秒！
結論
過去我也零星做過一些 C++ 樣板元程式設計——例如，我曾寫過一個用 C++ 寫的簡單 x86 組譯器——但這是我第一次真正接觸 C++17 的樣板元程式設計，也是第一次真正一頭栽進深水區。
而且，我以前就聽過這種說法，但在實際解完這個問題之後……老實說，我得承認現代 C++ 樣板已經算是一種相當堪用的函數式程式語言，甚至還有些不錯的特性！而發現摺疊表示式這個技巧時更是讓我驚喜，它甚至讓相對有效率的 list 處理成為可能。
我……還不確定接下來會再解幾天，或還會寫多少 C++，但我最後還滿享受這次練習的！
留言
登入後參與討論