なぜ ranges::accumulate は難しいのか

• 概要: 本稿では accumulate の型制約の妥当性について、STL におけるコンセプトの設計指針を基に考察しています

はじめに

C++20 で範囲ライブラリが導入されたことで、リスト操作が容易に行えるようになりました。個人的に 3 大リスト操作を挙げるとするならば、filter、map (あるいは transform)、fold (あるいは accumulate) が挙がるのではないかと思います。その中で ranges::accumulate だけは C++20 入りを果たしませんでした。

その理由は、単に時間が足りなかったからだとされています^[1]。しかし、それは議論すべき点がなかったという意味ではないようです。実際、ranges::accumulate の代替である ranges::fold が C++23 に向けて採択されるまでに、以下の経緯をたどっています。

• range-v3 で accumulate が実装される (このコミット が最初期の accumulate であるようです)
• P1813 A Concept Design for the Numeric Algorithms が提案される
• P2214 A Plan for C++23 Ranges にて accumulate は不適切であることが示唆される
• P2322 ranges::fold が提案、のちに採択される
  

accumulate は範囲ライブラリの実装経験である range-v3 で実装されており、その型制約は現在以下のようになっています^[2]。この型制約は 最初期 よりコンセプト設計の変更を受けて何度も修正されているものの、骨子は変化していません。

template <class Op, class I1, class I2>
concept indirectly_binary_invocable =
  indirectly_readable<I1> and
  indirectly_readable<I2> and
  copy_constructible<Op> and
  invocable<Op&, iter_value_t<I1>&, iter_value_t<I2>&> and
  invocable<Op&, iter_value_t<I1>&, iter_reference_t<I2>> and
  invocable<Op&, iter_reference_t<I1>, iter_value_t<I2>&> and
  invocable<Op&, iter_reference_t<I1>, iter_reference_t<I2>> and
  invocable<Op&, iter_common_reference_t<I1>, iter_common_reference_t<I2>> and
  common_reference_with<
    invoke_result_t<Op&, iter_value_t<I1>&, iter_value_t<I2>&>,
    invoke_result_t<Op&, iter_value_t<I1>&, iter_reference_t<I2>>,
    invoke_result_t<Op&, iter_reference_t<I1>, iter_value_t<I2>&>,
    invoke_result_t<Op&, iter_reference_t<I1>, iter_reference_t<I2>>>;

template <input_iterator I, sentinel_for<I> S, movable T,
          class Op = plus<>, class Proj = identity>
requires indirectly_binary_invocable<Op&, T*, projected<I, Proj>> and
  assignable_from<T&, indirect_result_t<Op&, T*, projected<I, Proj>>>
constexpr T accumulate(I first, S last, T init, Op op = {}, Proj proj = {});

この型制約でも上手くいくように見えますが、この accumulate は採択されませんでした。

なぜ ranges::accumulate は range-v3 と同様の型制約で採択されなかったのでしょうか。また一方で、ranges::fold はなぜ採択されたのでしょうか。

これらの問いは STL におけるコンセプトの設計と密接な関係がありそうです。そこで本稿ではまず、 STL におけるコンセプトの設計思想について説明します。次にそれに基づいて ranges::accumulate が採択されなかった理由、および ranges::fold が採択された理由の説明を試みます。

本稿は規格関連文書の内容に加え、筆者の考察も含まれます。筆者の不勉強のために、事実とは異なる記述がある可能性があります。お気づきの点がございましたら、コメント頂けますと幸いです。

STL におけるコンセプトの設計

STL においてコンセプトは、一般的なアルゴリズムを記述するための抽象的な型に対する要件と位置付けられています^[3]。一般性のあるコンセプトの設計指針は、コンセプトの粒度という観点から、次の 2 つの方向性が考えられます。

1. コンセプトをできる限り大きくする。すなわち要件の多いコンセプトをごく少数のみ用意する

   • 例: イテレータは random access iterator のみ
   • 利点: コンセプトの意味が単純となる。ユーザが使用しやすくなる
   • 欠点: 要件が過剰となる。アルゴリズムの実装において決して使用されない操作による要件が入る。その結果、有意義なクラスが要件を満たさない場面が生じる

2. コンセプトを可能な限り小さくする。すなわち要件の少ないコンセプトを多数用意する

   • 例: HasPlus, HasMinus, HasComma, ...
     (C++0x に向けて考案され、削除されたコンセプトはこの形でした^[4])
   • 利点: アルゴリズムの要件が限界まで緩和される。その結果、可能な限り多くのクラスがアルゴリズムを利用できるようになる
   • 欠点: 要件の意味が不明確となる。アルゴリズムの中心的な要件が伝わらなくなる

STL は両者の中間に位置しています。すなわち複数のクラスに適用可能な普遍的なアルゴリズムを提供しつつも、各コンセプトから意味が失われないコンセプト設計を目指しています。

コンセプトの指針

上述の目的を達成するために、STL はコンセプトに強い指針を与えています。それは端的に

$$Concepts = Constraints + Axioms$$

と表されます。

ここで Constraints とは、コンパイル時に検査することのできる構文要件 (syntatic requirements) を表します。一方 Axioms とは、実行時に検査することのできる意味要件 (semantic requirements) を意味します。STL は、コンセプトは構文要件と意味要件の両方を有する要件であると定めています。

コンセプトを意味のある一般的な要件にするために、STL はとりわけ以下の 2 点に注意して設計を行なっています。

1. コンセプトに必要な操作をすべて含める^[5]
2. コンセプトに有意義な意味論をもたせる^[6]

よくない例

template <class T>
concept Subtractable = requires(T a, T b) {
  a - b;
};

• 理由: 制約が小さすぎるため、有意義な意味論を持たせることができない。その結果、Subtractable コンセプトのみ満たすクラスにおいて十分一般性のあるアルゴリズムを提供することができない
• 修正案 (一例):
  a, b を T 型のオブジェクトとして、
  • 次の構文要件を追加する: +a, -a, a += b, a -= b, a + b
  • 次の意味要件を追加する: +a == a, (a -= b) == a += (-b), a + b == (a += b), a - b == a + (-b)

  template <class T>
  concept Subtractable = requires(T a, T b) {
    +a;
    -a;
    a += b;
    a -= b;
    a + b;
    a - b;
  } /* and axioms(T a, T b) {
    +a == a;
    (a -= b) == (a += (-b));
    a + b == (a += b);
    a - b == a + (-b);
  } */;
  

STL のコンセプトの例 1: random access iterator^[7]

template <class I>
  concept random_access_iterator =
    bidirectional_iterator<I> and
    derived_from<ITER_CONCEPT(I), random_access_iterator_tag> and
    totally_ordered<I> and
    sized_sentinel_for<I, I> and
    requires(I i, const I j, const iter_difference_t<I> n) {
      { i += n } -> same_as<I&>;
      { j +  n } -> same_as<I>;
      { n +  j } -> same_as<I>;
      { i -= n } -> same_as<I&>;
      { j -  n } -> same_as<I>;
      {  j[n]  } -> same_as<iter_reference_t<I>>;
    };

• 意味要件 (一部):
  i, j を I 型のオブジェクト、 n を iter_difference_t<I> 型のオブジェクトとして、

  i + n == (i += n);
  n + i == i + n;
  (i -= n) == (i += (-n));
  i - n == i + (-n);
  i[n] == *(i + n);
  if j - i == n, i + n == j;
  

STL のコンセプトの例 2: view^[8]

template <class T>
  concept view =
    range<T> and movable<T> and enable_view<T>;

• 意味要件:
  • T は $O(1)$ でムーブ構築可能
  • T のムーブ代入の計算量は破棄とムーブ構築の複合操作と同等かそれ以下
  • $M$ 要素保持する T を $N$ 回コピーまたはムーブしたオブジェクトは、$O(N + M)$ で破棄可能
  • T はコピー構築不能か、$O(1)$ でコピー構築可能
  • T はコピー不能か、コピー代入の計算量が破棄とコピー構築の複合操作と同等かそれ以下

view コンセプトは意味要件が重要であり、構文要件を満たすがコンセプトを満たさない型も少なくありません。そのため view コンセプトを満たすには、view_base の継承もしくは enable_view の特殊化によって、明示的に view であることを示す必要があります。

template <class T>
  inline constexpr bool enable_view =
    derived_from<T, view_base> or _is-derived-from-view-interface_<T>;

range-v3 の accumulate の問題点

ここまでで STL におけるコンセプトの設計指針を見てきました。それではなぜ ranges::accumulate は range-v3 と同様の型制約で採択されなかったのでしょうか。その理由は accumulate という操作が加法と密接に関係している点にあります。

• accumulate というメソッド名
• <numeric> ヘッダにて提供されてきたという歴史的経緯
• 二項演算子を表す関数オブジェクトのデフォルト型が std::plus<> であること

以上を考慮すると、accumulate には数値計算アルゴリズムと同様の要件を課すのが自然であると考えられます。ここで STL における数値計算アルゴリズムの要件とは、以下の 2 つの要件を指しています。

1. 被演算子の型 T, U が共通型であること

   common_with<T, U>
   

2. 演算子の型 Op が T と U の 4 つの組み合わせで呼び出し可能であること (以下 四方呼び出し可能 と書くことにします)

   invocable<Op, T, T> and invocable<Op, U, U> and
   invocable<Op, T, U> and invocable<Op, U, T>
   

STL の数値計算アルゴリズム要件の背景

これらの要件は数学的な代数構造の定義に由来すると考えられます。代数構造の定義では、二項演算子の始域および終域は、一致することが前提となっています。

• 例: $G$ を集合、$\ast: G\times G\to G$ を $G$ 上の二項演算子とする。このとき組 $(G, \ast)$ が群 (group) であるとは...

しかし、数値計算においては異なる型同士の計算にも意味をもたせることができ、時に有用です^[9]。

• 例: 精度の異なる浮動小数点数型間の計算

異なる型同士の計算を許可しつつも、数学的な代数構造の定義と矛盾しないために、STL の数値計算アルゴリズムでは被演算子の型が共通型であることを要求していると思われます。

• 例: atan2, pow, hypot, fmax, fmin, fdim, fma, gcd, lcm など

accumulate の要件を修正した場合の課題

以上の数値計算アルゴリズムのもつ背景を踏まえると、accumulate の型制約は以下のように修正されます^[10]。

template <class Op, class T, class U>
concept magma =
  common_with<T, U> and
  regular_invocable<Op, T, T> and
  regular_invocable<Op, U, U> and
  regular_invocable<Op, T, U> and
  regular_invocable<Op, U, T> and
  common_with<invoke_result_t<Op&, T, U>, T> and
  common_with<invoke_result_t<Op&, T, U>, U> and
  same_as<invoke_result_t<Op&, T, U>, invoke_result_t<Op&, U, T>>;

template <class Op, class I1, class I2, class O>
concept indirect_magma =
  indirectly_readable<I1> and
  indirectly_readable<I2> and
  indirectly_writable<O, indirect_result_t<Op&, I1, I2>> and
  magma<Op&, iter_value_t<I1>&, iter_value_t<I2>&> and
  magma<Op&, iter_value_t<I1>&, iter_reference_t<I2>&> and
  magma<Op&, iter_reference_t<I1>, iter_value_t<I2>&> and
  magma<Op&, iter_reference_t<I1>, iter_reference_t<I2>> and
  magma<Op&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

template <input_iterator I, sentinel_for<I> S, movable T, class Proj = identity,
          indirect_magma<const T*, projected<I, Proj>, T*> Op = plus<>>
constexpr accumulate_result<I, T>
accumulate(I first, S last, T init, Op op = {}, Proj proj = {});

しかしこの accmulate の型制約は、以下のような有用な操作を不許可としてしまっています。

• 不許可の例 1: Word count

  int word_count(const vector<string>& words) {
    return ranges::accumulate(words, 0, [](int accum, const string& str) {
      return accum + (str == "word");
    });
  }
  

  この例は projection を用いることで accmulate の型制約を満たす形に書き換えることができます。一方、次の例はそのような書き換えはできません。

• 不許可の例 2: Reverse string

  string reverse_str(const string& str) {
    return ranges::accumulate(str, string{}, [](auto&& str, char c) {
      return c + forward<decltype(str)>(str);
    });
  }
  

これら不許可な例の存在は、accumulate をこれらの操作を包含するより一般的な形で再定義すべきであることを示唆しています。

fold の改善点

そこで accumulate は、型制約はほぼ range-v3 のもののまま、fold として改めて定義されました。fold の型制約は以下のように定められています^[11]。

template <class Op, class T, class I, class U>
concept _indirectly-binary-left-foldable-impl_ = // 説明専用
  movable<T> and
  movable<U> and
  convertible_to<T, U> and
  invocable<Op&, U, iter_reference_t<I>> and
  assignable_from<U&, invoke_result_t<Op&, U, iter_reference_t<I>>>;

template <class Op, class T, class I>
concept _indirectly-binary-left-foldable_ = // 説明専用
  copy_constructible<Op> and
  indirectly_readable<I> and
  invocable<Op&, T, iter_reference_t<I>> and
  convertible_to<
    invoke_result_t<Op&, T, iter_reference_t<I>>,
    decay_t<invoke_result_t<Op&, T, iter_reference_t<I>>>> and
  _indirectly-binary-left-foldable-impl_<
    Op, T, I, decay_t<invoke_result_t<Op&, T, iter_reference_t<I>>>>;

template <input_iterator I, sentinel_for<I> S, class T,
          _indirectly-binary-left-foldable_<T, I> Op>
constexpr auto fold_left(I first, S last, T init, Op op);

• 改善点:
  • fold という名称に変更され、Op のデフォルト型が削除された
    → アルゴリズムを加法という文脈から切り離した
  • 被演算子の型が共通型であること、および演算子の型が 四方呼び出し可能 であることを要求しなくなった
    → 上記の例を含めたより一般的なアルゴリズムへと進化した
  • 戻り値の型が T から decay_t<invoke_result_t<Op&, T, iter_reference_t<I>>> に変更された
    → assignable_from の意味要件 (代入後は代入したオブジェクトと値が一致する^[12]) を満たす範囲が拡大された

範囲比較アルゴリズムとの類似

accumulate と fold の差異は、被演算子の型が共通型であること、および演算子の型が 四方呼び出し可能 であることを、アルゴリズムの要件に含めるか否かにありました。一方このような議論は、C++20 に向けた範囲比較アルゴリズムの検討において、すでに行われていました。

• P1716R3 ranges compare algorithm are over-constrained
• 対象となったアルゴリズム: find{,_end,_first_of}, adjacent_find, count, mismatch, equal, search{,_n}, replace{,_copy}, remove{,_copy}

これらのアルゴリズムは当初 relation<Pred&, T, U> で型制約されており、四方呼び出し可能 であることが要求されていました。しかし要件が過剰であると判断され、型制約が predicate<Pred&, T, U> に緩和されました。

template <class F, class... Args>
  concept predicate =
    regular_invocable<F, Args...> and
    _boolean-testable_<invoke_result_t<F, Args...>>;

template <class R, class T, class U>
  concept relation =
    predicate<R, T, T> and predicate<R, U, U> and
    predicate<R, T, U> and predicate<R, U, T>;

また STL には異なる 2 つの型が等値比較可能であることを表すコンセプトとして、equality_comparable_with が用意されています。このコンセプトは 2 つの型が共通型であることを要求します。一方、equality_comparable_with を用いて制約された STL のアルゴリズムは、本稿執筆時の Working Draft (N4917) にはありません。

template <class T, class U>
  concept _weakly-equality-comparable-with_ = // 説明専用
    requires(const remove_reference_t<T>& t,
             const remove_reference_t<U>& u) {
      { t == u } -> _boolean-testable_;
      { t != u } -> _boolean-testable_;
      { u == t } -> _boolean-testable_;
      { u != t } -> _boolean-testable_;
    };

template <class T, class U>
concept equality_comparable_with =
  std::equality_comparable<T> and
  std::equality_comparable<U> and
  std::common_reference_with<
    const std::remove_reference_t<T>&,
    const std::remove_reference_t<U>&> and
  std::equality_comparable<
    std::common_reference_t<
      const std::remove_reference_t<T>&,
      const std::remove_reference_t<U>&>> and
    _weakly-equality-comparable-with_<T, U>;

この定義は C++23 に向けた提案 P2404R3 Move-only types for equality_comparable_with, totally_ordered_with, and three_way_comparable_with にて変更が加えられましたが、本稿では反映できていません。

範囲比較アルゴリズムの型制約と、fold の型制約の類似点は以下の表のようにまとめられます。範囲比較アルゴリズムで採択された変更を考慮すると、accumulate から fold への移行は、前例を踏襲した進化といえそうです。

	範囲比較アルゴリズム	fold
❌ 不採用	relation<Pred&, T, U> equality_comparable_with 共通型・四方呼び出し可能 を要求する	magma 共通型・四方呼び出し可能 を要求する
✅ 採用	indirect_­binary_­predicate<Pred&, T, U> 上記を要求しない	_indirectly-binary-left-foldable_<Op&, T, U> 上記を要求しない

おわりに

本稿では accumulate の型制約の妥当性について検討しました。その結果、accumulate は数値型の加法と密接に関係したアルゴリズムと解釈できるため、range-v3 の型制約では妥当ではないことが考えられました。その背景として STL のコンセプトの設計指針、すなわち

• コンセプトは普遍性と有意義な意味論の両者をあわせもつ
• $Concepts = Constraints + Axioms$

の存在があることがわかりました。

本稿ではコンセプト (Concepts) と制約 (Constraints) を意味要件の有無の観点から明確に区別して説明しました。しかし規格ではこの意味での制約 (Constraints) という語は現れません。一方、コンセプトの構文要件を満たす場合は「コンセプトを満たす」、コンセプトの構文要件と意味要件の両方を満たす場合は「コンセプトのモデルとなる」と区別して表現されており、コンセプト (Concepts) と制約 (Constraints) の区別は消失したわけではなさそうです。このような移行がコンセプトにおける意味要件の扱いにどのような変化をもたらしたかについては、調査中です。

主要な参考文献

• Design of Concept Libraries for C++
• P1813R0 A Concept Design for the Numeric Algorithms
• P2214R0 A Plan for C++23 Ranges
• P2322R6 ranges::fold
• P1716R3 ranges compare algorithm are over-constrained

脚注

1. Why didn't accumulate make it into Ranges for C++20? - Stack Overflow

2. range-v3/accumulate.hpp at master · ericniebler/range-v3

3. Design of Concept Libraries for C++

4. N2914 - Working Draft, Standard for Programming Language C++

5. T.21: Require a complete set of operations for a concept 翻訳は C++ Core Guidelines タイトル日本語訳 - Qiita/tetsurom を参考にしました

6. T.20: Avoid “concepts” without meaningful semantics 翻訳は C++ Core Guidelines タイトル日本語訳 - Qiita/tetsurom を参考にしました

7. [iterator.concept.random.access]

8. [range.view]

9. P1673R9 A free function linear algebra interface based on the BLAS/11.7.4. Generalizing associativity helps little

10. P1813R0 A Concept Design for the Numeric Algorithms

11. P2322R6 ranges::fold

12. [concept.assignable]/1.5