多相再帰とconstexpr if

2021年12月11日

この記事はC++ Advent Calendar 2021の11日目の記事です。

本記事では（疑似的な）多相再帰をC++で実装する方法についてご紹介します。必要な予備知識はC++の基本的な文法のみで、constexpr ifを知っていて多相再帰とやらにどう使うのか知りたい方や、多相再帰を知っていてC++でどう実装するのか興味がある方、どちらもよく知らないものの何となく記事を開いてみた方も読んで頂ける内容になっています。

注意

本記事のコードはコンパイル時計算をヘビーに使うため、LSPやコンパイルをかけるとCPUやメモリを多く消費しますので、手元で試すときはご注意ください。また、コードはg++ 10.3.0で-std=c++20フラグをつけてコンパイルできることを確認しています。

多相再帰をご存じの方へ

本記事の多相再帰の実装では再帰の深さが一定数を超えるとランタイムエラーを吐きます。この振る舞い自体は普通の再帰関数と同じですが、この点で理論的な意味での真の多相再帰にはなっていません。また、C++のtemplateによるpolymorphismはtemplate specializationやconstexpr ifの存在によりad hoc polymorphismに近く、本記事では実装を型引数によって変えるのでこのad hoc性を積極的に使っています。この二点をご了承ください。

多相再帰とは

多相再帰(polymorphic recursion)関数とは、再帰的なテンプレート関数で、再帰の度に型引数が変化するものです。「再帰の度に型引数が変化する」とはどういうことかを理解するために例を見ていきます。まず、多相再帰でない再帰的なテンプレート関数です。

#include <cstddef>

template <typename T>
struct ListNode;
template <typename T>
using List = ListNode<T>*;

// 連結リスト
template <typename T>
struct ListNode {
  T elem;
  List<T> next;
};

// 再帰関数
template <typename T>int listSize(List<T> lis) {  if (lis) {
    return 1 + listSize<T>(lis->next);  } else {
    return 0;
  }
}

List<T>は型Tの要素をもつ連結リストで、テンプレート関数listSize<T>は連結リストのサイズを計算する再帰関数です。このように連結リストのサイズを再帰で計算するのは時間的効率として最適ではありませんが、教科書的なやり方です。

このlistSize<T>は多相再帰関数ではありませんが、これを少しひねった次の関数powerListSize<T>は多相再帰関数になります。

#include <cstddef>
#include <utility>

template <typename T>
using Double = std::pair<T,T>;
template <typename T>
struct PowerNode;
template <typename T>
using PowerList = PowerNode<T>*;

// ノード内の要素の型が変化する連結リスト
template <typename T>
struct PowerNode {
  T elem;
  PowerList<Double<T>> next;};

// 多相再帰関数
template <typename T>int powerListSize(PowerList<T> lis) {  if (lis) {
    return 1 + 2 * powerListSize<Double<T>>(lis->next);  } else {
    return 0;
  }
}

PowerList<T>はnextで連結リストをたどっていく度に、ノード内の要素数が2倍になるやや特殊なデータ構造です。 PowerList<T>内の型Tの要素の数を計算するpowerListSize<T>は、listSize<T>と同様に再帰関数になりますが、再帰の型引数がDouble<T>になっていることが重要で、これが「再帰の度に型引数が変化する」例になっています。この型引数の変化は、lis->nextの型がPowerList<Double<T>>になっており、データ構造の構成要素であるノードの型が異なることに直接の原因があります。

ここで、関数の話をしていたのにいつの間にかデータ構造の話が入ってきて紛らわしいと感じる方もいるかもしれませんが、PowerList<T>のように多相再帰的な構造を持つデータ構造を扱おうとするとしばしば多相再帰関数が出てくるため、本記事ではそのような文脈で話を進めます。

powerListSize<T>はlistSize<T>を単に拡張したものなので一見そのまま動きそうですが、実はコンパイルは通りません。例えば、

// 注意：コンパイラやLSPにかけるとCPUやメモリを多く消費します
#include <iostream>
int main() {
  PowerList<int> pl;
  std::cout << powerListSize(pl) << std::endl;
}

として、標準出力に0が出力されるかどうか見てみようとすると、コンパイルがいつまで待っていても完了しません。電気代を無駄にする前に、なぜコンパイルが通らないのか考えてみましょう。

結論としては、これはC++がコンパイル時に必要なテンプレート関数を全て生成（インスタンス化）しようとするためです。listSize<T>の場合はインスタンス化しなければならないテンプレート関数は１つだけでしたが、powerListSize<T>の場合は再帰の度に型引数が変化するため、インスタンス化しなければならないテンプレート関数は、

powerListSize<T>
powerListSize<Double<T>>
powerListSize<Double<Double<T>>>
powerListSize<Double<Double<Double<T>>>>
...

と無限個存在します。これらを全て生成しようとするのでコンパイルが終わらなかったわけです。

この理由は至極まっとうで、静的型付け言語の宿命にも思えます。実行時に現れ得る全ての型はコンパイル時に分かっていなければなりません。一方で、多相再帰の性質上、引数型の数は発散してしまいます。（注：多相再帰の全ての場合でそうなるわけではなく、例えば再帰の度に二つの型を行き来するだけならテンプレート関数は二つしか生成されませんが、自分がOkasakiの教科書で見たことのある多相再帰の応用例ではテンプレート関数は無限に生成されます。）C++では多相再帰は使えないのでしょうか？

折衷案：constexpr if

ここで、やたらと使いづらいことに目を瞑ってPowerList<T>を実際に使うときのことを考えてみます。通常の連結リストと同じように、実行時にどんどんノードを追加していくことを考えましょう。ノードを追加する回数は所詮有限なので、現実的にはどんなにPowerList<T>の中身の要素数が多くなっても有限回nextを繰り返したらNULLにたどり着きます。NULLにたどり着くと、

template <typename T>
int powerListSize(PowerList<T> lis) {
  if (lis) {
    return 1 + 2 * powerListSize<Double<T>>(lis->next);
  } else {    return 0;  }}

のelseブランチに到達して再帰が終わります。つまり、コンパイル時に生成される無限のpowerListSize達のうち実行時に使われるものは有限個で、コンパイラは無駄な仕事をしようとしていることになります。

ここで折衷案としてconstexpr ifが出てきます。PowerList<T>の要素の数は、NULLにたどり着くまでの再帰の深さをnとして2^n-1個なので、10^6個の要素を収納することになっても再帰の深さは20回で十分です。実行時にそれ以上の再帰が走ったらランタイムエラーを吐くように修正してみましょう。まず、準備としてネストしたDouble型を一般的な形で表現します。

template <size_t I,typename T> 
struct DoubleDepthN {
  template<typename... Args>
  using type_each = typename DoubleDepthN<I-1, T>::template type<T, Args...>;

  template<typename... Args> 
  using type = Double<type_each<Args...>>;
};

template <typename T> 
struct DoubleDepthN<0, T> {
    template <typename... Args>
    using type = T;
};

template <size_t I,typename T>  
using NestedDouble = typename DoubleDepthN<I,T>::template type<>;

コードは複雑ですが、ここでは実装の詳細は重要ではありません。NestedDouble<I,T>が以下のようにネストしたDouble型として振る舞うことが重要になってきます。

NestedDouble<0, T> = T
NestedDouble<1, T> = Double<T>
NestedDouble<2, T> = Double<Double<T>>
NestedDouble<3, T> = Double<Double<Double<T>>>
...

これを使って、以下のようにpowerListSize<T>を修正します。

#include <stdexcept>
#include <type_traits>

constexpr size_t cutoff = 20;
template <typename T, typename BaseT>
int powerListSize(PowerList<T> lis) {
  if constexpr (std::is_same_v<T, NestedDouble<cutoff, BaseT>>) {    throw std::runtime_error("cutoff exceeded!");    return int {};  } else {
    if (lis) {
      return 1 + 2 * powerListSize<Double<T>, BaseT>(lis->next);
    } else {
      return 0;
    }
  }
}

int main() {
  PowerNode<int> headNode {1, NULL};
  PowerNode<NestedDouble<1, int>> nextNode {{2,3}, NULL};
  PowerNode<NestedDouble<2, int>> nextNextNode {{{4,5}, {6,7}}, NULL};
  PowerList<int> head = &headNode;
  head->next = &nextNode;
  head->next->next = &nextNextNode;
  int size = powerListSize<int, int>(head);  std::cout << size << std::endl; // 7
}

ここで、if constexprの部分で、「型TがNestedDouble<cutoff, BaseT>と同じ場合は以下の実装を使う」という条件分岐が入ります。この箇所の実装でランタイムエラーを投げて明示的に再帰を打ち切ることでコンパイルがちゃんと通り、powerListSize<T>は実行時の再帰の深さが20を超えなければ要素数を返し、超えたらランタイムエラーが投げられるようになります。

多相再帰が使えると何が嬉しいのか？

ここまでで、constexpr ifを使うと多相再帰が実装できて、PowerList<T>といった型引数が再帰の度に異なるデータ構造に対する操作が行えるようになりました。では、そのようなデータ構造が使えて何がうれしいのでしょうか。ここで、PowerList<T>を表す連結リストの図を90度回転してみます。

こう見ると、このデータ構造は全ての葉の深さが等しい完全二分木になっていることがわかります。通常木構造は以下のようにポインタで作り、このようなデータ構造を完全二分木として使いたい場合、操作の前後で二分木の完全性が保たれることはメンバ関数の実装者が担保しなければなりません。

template <typename T>
struct TreeNode;
template <typename T>
using Tree = TreeNode<T>*;

// 二分木
template <typename T>
struct TreeNode {
  T elem;
  Tree<T> left, right;
};

一方で、多相再帰によって定義した二分木は、型の定義により常に完全二分木です。このように、型に対する再帰によりデータ構造のinvariantが型レベルで保証されることが多相再帰の一つの利点です。多相再帰のこのようなデータ構造の実装者のミスを減らすという利点についてはWikipediaの記事やChris Okasakiの教科書に記述があります。

まとめ

本記事ではC++での（疑似的な）多相再帰の実装についてご紹介しました。紹介したコードはいかにも扱いづらそうに見えるかもしれませんが、テンプレートクラスに（多相再帰な）メンバ関数を定義して抽象データ型として扱ってやれば、実装の詳細であるところの内部の型などは利用者は意識する必要がなくなります。そちらの詳細についてはこちらのポストを、データ構造における実装例についてはOkasakiの教科書のデータ構造の一部をC++で実装したこちらのレポジトリのAlt Binary Random Access ListやImplicit Queueをご参照ください。（どちらも手前味噌ですが…）

まだこの実装が現実でどれだけ有用かはわかっておらず、「クマが踊っているからすごい」というだけ感はありますが、少なくとも多相再帰で自然に表現できるデータ構造を思いついた方が、C++でそれを実装したい場合には役に立つのではないかと思います。