次の方法で共有



October 2017

Volume 32 Number 10

C++ - C++ でのアルゴリズムからコルーチンまで

Kenny Kerr

C++ 標準ライブラリには、iota という興味深いアルゴリズムがあります。名前も気になりますが、面白い機能も備えています。iota は、ギリシャ語のアルファベットの 1 文字の呼称です。一般に、この単語は微小 (最小ではありません) と訳され、多くの場合否定的に用いられます。また、その由来は、新約聖書のマタイの福音書からの引用です。この微小という概念は、iota アルゴリズムの機能を指しています。このアルゴリズムは、少量ずつ増やしながら範囲に値を設定します。その際、初期値を格納後、その範囲が埋まるまで値を増加します。つまり、次のようになります。

#include <numeric>

int main()
{
  int range[10];
  // Range: Random missile launch codes

  std::iota(std::begin(range), std::end(range), 0);
  // Range: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
}

C++ の開発者は、多くの場合、For ループをむき出しで使用するのではなく、アルゴリズムに置き換えることを求められます。iota アルゴリズムは、明らかに C や C++ のすべての開発者が例外なく何千回も記述してきた For ループの役割を果たします。C++ 標準ライブラリの実装は、次のようなものになると想像できます。

namespace std
{
  template <typename Iterator, typename Type>
  void iota(Iterator first, Iterator last, Type value)
  {
    for (; first != last; ++first, ++value)
    {
      *first = value;
    }
  }
}

やはり、このようなコードはレビューしたくないでしょう。当然、ライブラリの開発者なら話は別です。iota アルゴリズムによって、For ループを記述せずに済むのはすばらしいことです。ですが、実際に使ったことはありません。通常、話の流れは次のようになります。値の範囲が必要になります。これは基本的な作業なので、コンピューター サイエンスにはこれを行う標準アルゴリズムがあると考えます。bit.ly/2i5WZRc のリストを見直し、iota を見つけます。これには値を埋める範囲が必要なようです。では、最も簡単な範囲を正しく理解するため、以下のように For ループを使って値を出力します。

#include <numeric>
#include <stdio.h>

int main()
{
  int range[10];
  std::iota(std::begin(range), std::end(range), 0);

  for (int i : range)
  {
    printf("%d\n", i);
  }
}

正直に言って、このコードで気に入ったのは、範囲に基づく For ループだけです。問題は、範囲を必要としないうえに、避けたいと考えていることです。反復する範囲を保持するためだけにコンテナーを作成しなければならない状況は求めていません。もっと多くの値が必要になるとしたらどうなるでしょう。それなら、自身で For ループを作成する方が良いと考えられます。

#include <stdio.h>

int main()
{
  for (int i = 0; i != 10; ++i)
  {
    printf("%d\n", i);
  }
}

そのうえ、入力するコードも少なくなります。ただし、コンテナーを必要としないで、範囲に基づく For ループになんらかの形で値の範囲を生成できる iota に似た関数があれば、話は別です。最近 Python 言語に関する書籍を読んでいると、この言語には range という組み込み関数があることに気付きました。上記と同じプログラムを Python で記述すると、以下のようになります。

for i in range(0, 10):
  print(i)

このインデントには注意が必要です。Python 言語では、インデントで複合ステートメントを表します。Python の名前の由来は、毒を持たないヘビの名前ではなく、英国のあるコメディだと書かれていました。著者が冗談で書いたとは思えません。それはさておき、上記のコードの簡潔さには目を見張るものがあります。間違いなく、C++ でこのやり方を実現できます。これこそ、iota アルゴリズムに望む機能です。実際、求めているのは以下のような範囲アルゴリズムです。

template <typename T>
generator<T> range(T first, T last)
{
  return{ ... };
}

int main()
{
  for (int i : range(0, 10))
  {
    printf("%d\n", i);
  }
}

このような関数は記憶にありません。したがってビルドすることになります。まず、おおよそのアルゴリズムを作ります。テスト用のベースラインとして機能する信頼性の高いアルゴリズムです。このような場合は、C++ 標準の vector コンテナーが便利です。

#include <vector>

template <typename T>
std::vector<T> range(T first, T last)
{
  std::vector<T> values;

  while (first != last)
  {
    values.push_back(first++);
  }

  return values;
}

こうした作業は、最初にコンテナーをビルドしない理由を示したり、コンテナーの大きさがどの程度の大きさになるかを考えるのに効果があります。でも、上下限が必要なのはなぜでしょう。それは、この範囲ジェネレーターの出力と、もっと効率の良い別のジェネレーターを簡単に比較できるためです。その結果、もっと効率の良いジェネレーターの作成がそれほど難しくないことがわかります。図 1 をご覧ください。

図 1 従来型のジェネレーター

template <typename T>
struct generator
{
  T first;
  T last;

  struct iterator{ ... };

  iterator begin()
  {
    return{ first };
  }

  iterator end()
  {
    return{ last };
  }
};

template <typename T>
generator<T> range(T first, T last)
{
  return{ first, last };
}

この関数 range は、単純に上記と同じ境界値のペアで初期化されるジェネレーターを作成します。さらに、このジェネレーターはそれらの値を使用して、定型的なメンバー関数 begin と end を通じで軽量のイテレーターを生成します。これで面倒な部分の大半が、定型のイテレーター実装に吐き出されます。イテレーターは、単純に特定の値を保持し、必要に応じてその値を増加することができます。また、自身を標準アルゴリズムにするため、一連の型エイリアスの提供も必要です。厳密に言えば、これは単純な範囲に基づく For ループには不要です。ですが、将来に備えて含めておくと便利です。

template <typename T>
struct generator
{
  struct iterator
  {
    T value;

    using iterator_category = std::input_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T const*;
    using reference = T const&;

イテレーターをインクリメントする場合は、基になる値を増やすだけです。ポストインクリメント式は削除しても問題ありません。

iterator& operator++()
{
  ++value;
  return *this;
}

iterator operator++(int) = delete;

イテレーターが提供する機能で、もう 1 つ同等に重要な機能は比較です。範囲に基づく For ループはこれを使用して、範囲の終わりに達したかどうかを判断します。

bool operator==(iterator const& other) const
{
  return value == other.value;
}

bool operator!=(iterator const& other) const
{
  return !(*this == other);
}

最後に、範囲に基づく For ループはイテレーターを逆参照して、範囲内の現在値を返します。メンバー呼び出し演算子は、範囲に基づく For ループには必要ないため削除できますが、削除すると、他のアルゴリズムに使用できるジェネレーターの実用性を不必要に狭めてしまいます。

T const& operator*() const
{
  return value;
}

T const* operator->() const
{
  return std::addressof(value);
}

ジェネレーターと、関連する関数 range は、単純なプリミティブではなく、数字のようなオブジェクトと共に使用されます。その場合、数字のようなオブジェクトを operator& オーバーロードを使って操作する場合は、ヘルパーの addressof も使用できます。必要なのはこれで全部です。これで、関数 range が想定どおり機能するようになります。

template <typename T>
generator<T> range(T first, T last)
{
  return{ first, last };
}

int main()
{
  for (int i : range(0, 10))
  {
    printf("%d\n", i);
  }
}

当然、あまり柔軟性はありません。こうして目指す iota を作成しましたが、実用化するには、発想を転換してコルーチンを採用することになります。コルーチンを使用すれば、任意の種類のジェネレーターを非常に簡潔に記述でき、作成する範囲の種類ごとにジェネレーター クラス テンプレートを新しく作成する必要もなくなります。もう 1 つジェネレーターを作成し、必要に応じて異なるシーケンスを生成するために、一連の range に似た関数を用意すればよいものとします。これは、コルーチンによって実現できます。ジェネレーターに本来の iota を生成する知識を埋め込むのではなく、その知識を関数 range 内部に直接埋め込んで、プロデューサーとコンシューマーをつなぐ役割を果たすジェネレーター クラス テンプレートを 1 つ用意します。やってみましょう。

最初に、coroutine_handle クラス テンプレートの定義を含む coroutine ヘッダーをインクルードします。

#include <experimental/coroutine>

coroutine_handle を使用して、ジェネレーターがコルーチンによって表現されるステート マシンを操作できるようにします。これは、範囲に基づく For ループ (この場合は他のあらゆるループも含む) がデータを利用するプッシュモデルではなくプルモデルを生成するようコルーチンの経過を指示できるようにするために、必要に応じてクエリして再開します。ある意味、このジェネレーターは 図 1 の従来型のジェネレーターに似ています。大きな違いは、値を直接更新するのではなく、コルーチンを単に細かく進めている点です。図 2 に概要を示します。

図 2 コルーチン ジェネレーター

template <typename T>
struct generator
{
  struct promise_type{ ... };

  using handle_type = std::experimental::coroutine_handle<promise_type>;

  handle_type handle{ nullptr };

  struct iterator{ ... };

  iterator begin()
  {
    ...
    handle.resume();
    ...
  }

  iterator end()
  {
    return nullptr;
  }
};

ここからもう少し進化させます。範囲に基づく For ループが外部ジェネレーターを操作できるようにするイテレーターだけでなく、コルーチン内部からジェネレーターを操作できるようにする promise_type もあります。まず、ある程度の準備を行います。以前取り上げましたが、値を生成する関数はジェネレーターを直接返すのではなく、開発者が co_yield ステートメントを使用して、コルーチンからジェネレーターを経由し、呼び出し元サイトに値を返すことができます。最もシンプルなジェネレーターを考えます。

generator<int> one_two_three()
{
  co_yield 1;
  co_yield 2;
  co_yield 3;
}

開発者がコルーチンの戻り値の型を明示的に作成していないのがわかります。これは、C++ コンパイラが上記のコードで表されるステート マシンをつなぎ合わせる際に行います。原則的に、C++ コンパイラは promise_type を探し、それを使用して論理コルーチン フレームを作成します。多くの場合、コルーチン フレームは、C++ コンパイラがコードの最適化を完了した後に消失します。何にせよ、promise_type は呼び出し元に返されるジェネレーターの初期化に使用されます。promise_type があるため、以下のようにコルーチンを表すハンドル (handle) を取得して、ジェネレーターを外部から操作できるようになります。

generator(promise_type& promise) :
  handle(handle_type::from_promise(promise))
{
}

当然、coroutine_handle は非常に低レベルな構造体です。開発者は、アクティブなコルーチン内でステート マシンが誤って破損するジェネレーターを保持したいとは思いません。その解決策として、移動のセマンティクスを実装して、コピーを禁止します。コードは以下のようになります。先頭を既定のコンストラクターにし、特殊なコピー メンバーは明示的に削除しています。

generator() = default;
generator(generator const&) = delete;
generator &operator=(generator const&) = delete;

次に、コルーチンの handle 値を単純に転送することで、移動のセマンティクスを実装し、2 つのジェネレーターが動作中の同じコルーチンをポイントしないようにします (図 3 参照)。

図 3 移動セマンティクスの実装

generator(generator&& other) : handle(other.handle)
{
  other.handle = nullptr;
}

generator &operator=(generator&& other)
{
  if (this != &other)
  {
    handle = other.handle;
    other.handle = nullptr;
  }

  return *this;
}

ここで、コルーチンが外部から駆動されるという事実を考慮すると、ジェネレーターにはコルーチンを破棄する役割もあることに注意が必要です。

~generator()
{
  if (handle)
  {
    handle.destroy();
  }
}

これは実際に promise_type での final_suspend の結果に大きく関係しますが、ここでは取り上げません。今回は参考程度に留めます。ここからは、ジェネレーターの promise_type について見ていきます。promise_type は、C++ コンパイラがコルーチン フレーム用に行ったすべての割り当てが含まれるように、任意の状態を保管するのに便利な場所です。ジェネレーターは軽量のオブジェクトにすぎないため、必要に応じて簡単に移動し、その状態を逆参照できます。実際に、コルーチン内部から呼び出し元に伝える必要がある情報は 2 つしかありません。1 つは出力値、もう 1 つはスローされた可能性のある任意の例外です。

#include <variant>

template <typename T>
struct generator
{
  struct promise_type
  {
    std::variant<T const*, std::exception_ptr> value;

必ずというわけではありませんが、Visual C++ では exception_ptr の実装の負荷がやや高いため、ここでは exception_ptr オブジェクトを std::optional 内にラップしています。空の exception_ptr であっても、構築と破棄の両方で CRT を呼び出します。これを必要に応じて内部にラップすることで、オーバーヘッドがうまく回避されます。前述のように、現在値と exception_ptr は相互に排他的なので、より正確な状態モデルではバリアントを使用して、そのいずれかを保持します。現在値は、コルーチン内部で生成された値へのポインターです。コルーチンは値を読み取っている間は中断し、生成される一時オブジェクトはどれも、値がコルーチン外部で利用されている間安全に保存されるため、この方法は安全です。

コルーチンが最初に呼び出し元に戻るとき、コルーチンは戻り値を生成するよう promise_type に求めます。ジェネレーターは promise_type への参照を指定することで構築されるため、以下のように参照を返すだけです。

promise_type& get_return_object()
{
  return *this;
}

ジェネレーターを生成するコルーチンは、同時実行可能な一般的なコルーチンではなく、多くの場合、コルーチンの有効期間と実行を指示するジェネレーターにすぎません。そのため、ここではジェネレーターがコルーチンの各ステップを制御できるようにコルーチンを最初に中断しなければならないことを C++ コンパイラに指示しています。

std::experimental::suspend_always initial_suspend()
{
  return {};
}

同様に、戻り時にはコルーチン自体を自動的に破棄するのではなく、コルーチンを中断するよう指示します。

std::experimental::suspend_always final_suspend()
{
  return {};
}

これにより、コルーチン完了後も、コルーチン フレーム内で割り当てられた promise_type を使って、コルーチンの状態をクエリできるようになります。これは、失敗時に exception_ptr を読み取ったり、コルーチンが完了したことを把握するためにも不可欠です。コルーチンの終了時に自身を自動的に破棄すると、promise_type はもちろん、coroutine_handle をクエリすることができず、最後の中断ポイントでコルーチンの再開呼び出しが必要になります。これで、生成する値のキャプチャが非常に簡単になります。

std::experimental::suspend_always yield_value(T const& other)
{
  value = std::addressof(other);
  return {};
}

ここでも、便利な addressof ヘルパーを使用します。promise_type は、関数 return_void または return_value を用意することも必要です。今回の例では使用していませんが、co_yield は実際のところ co_await の抽象化にすぎないことを示しています。

void return_void()
{
}

これについては後ほど詳しく説明します。次に、開発者が何を間違えたかを特定しやすくするために、誤用を防ぐ対策を施します。値を生成するジェネレーターは、コルーチンが完了しないかぎり、値を読み取れないことを意味します。コルーチンが co_await 式を含んでいると、値が存在する前に中断する可能性があり、その事実を呼び出し元に伝える手段もありません。そのため、以下のように、開発者が co_await ステートメントを記述できないようにします。

template <typename Expression>
Expression&& await_transform(Expression&& expression)
{
  static_assert(sizeof(expression) == 0, 
    "co_await is not supported in coroutines of type generator");
  return std::forward<Expression>(expression);
}

promise_type をラップすると、スローされる可能性のあるすべての例外をキャッチする必要があるだけです。C++ コンパイラは、promise_type の unhandled_exception メンバーが確実に呼び出されるようにします。

void unhandled_exception()
{
  value = std::current_exception();
}

さらに、実装の便宜を考え、適切なコンテキストで必要に応じて例外を再スローする手軽な関数を用意します。

void rethrow_if_failed()
{
  if (value.index() == 1)
  {
    std::rethrow_exception(std::get<1>(value));
  }
}

promise_type についてはこれで十分でしょう。これで、機能するジェネレーターが準備できました。ですが、ここで簡単なイテレーターを追加して、ジェネレーターを範囲を基にする For ループから簡単に動作させることができるようにします。先ほど説明したように、イテレーターには、標準アルゴリズムにそれ自体を記述できるようにする、定型のエイリアスがあります。ただし、イテレーターは coroutine_handle を保持するだけです。

struct iterator
{
  using iterator_category = std::input_iterator_tag;
  using value_type = T;
  using difference_type = ptrdiff_t;
  using pointer = T const*;
  using reference = T const&;

  handle_type handle;

イテレーターのインクリメントは、ジェネレーターがコルーチンと相互作用する主要ポイントになるため、シンプルな iota イテレーターよりはやや複雑です。イテレーターをインクリメントすることは、そのイテレーターが有効で、実際にインクリメントされる可能性があることを示します。"end" イテレーターは nullptr ハンドルを保持するため、以下のようにイテレーターの比較演算子を提供できます。

bool operator==(iterator const& other) const
{
  return handle == other.handle;
}

bool operator!=(iterator const& other) const
{
  return !(*this == other);
}

これが有効なイテレーターだとすると、まずコルーチンを再開し、実行して次の値を生成します。その後、この実行によってコルーチンが終了したかどうかをチェックする必要があります。コルーチンが終了している場合、コルーチン内部で発生した可能性のある例外を伝達します。

iterator &operator++()
{
  handle.resume();

  if (handle.done())
  {
    promise_type& promise = handle.promise();
    handle = nullptr;
    promise.rethrow_if_failed();
  }

  return *this;
}

iterator operator++(int) = delete;

それ以外の場合、イテレーターは最後まで達したと見なされ、ハンドルは end イテレーターと正しく比較されるようにクリアされます。予期しない動作を引き起こす可能性があるため、最後の中断ポイントでコルーチンを誤って再開させないよう、キャッチできなかった例外をスローする前にコルーチンのハンドルをクリアする必要があります。ジェネレーターのメンバー関数 begin はほぼ同じロジックを実行し、最初の中断ポイントより前にスローされる例外を常に伝達できるようにします。

iterator begin()
{
  if (!handle)
  {
    return nullptr;
  }

  handle.resume();

  if (handle.done())
  {
    handle.promise().rethrow_if_failed();
    return nullptr;
  }

  return handle;
}

大きな違いは、この begin は、コルーチンのハンドルを保持するジェネレーターのメンバーであるため、コルーチンのハンドルをクリアしてはいけない点です。最後に、promise_type 内に保存された現在値への参照を返すことで、イテレーターの逆参照を非常に簡単に実装することができます。

T const& operator*() const
{
  return *std::get<0>(handle.promise().value);
}

T const* operator->() const
{
  return std::addressof(operator*());
}

これで終わりです。一般化したジェネレーターを使用して、さまざまな生成シーケンスを生み出す、あらゆる方法のアルゴリズムを作成できるようになります。図 4 に、今回の示唆に富んだ範囲ジェネレーターの全容を示します。

図 4 示唆に富んだ範囲ジェネレーター

template <typename T>
generator<int> range(T first, T last)
{
  while (first != last)
  {
    co_yield first++;
  }
}

int main()
{
  for (int i : range(0, 10))
  {
    printf("%d\n", i);
  }
}

範囲を限定する必要はあるでしょうか。今回はプル モデルを採用したため、必要十分な範囲を呼び出し元が決めることができます (図 5 参照)。

図 5 制限のないジェネレーター

template <typename T>
generator<int> range(T first)
{
  while (true)
  {
    co_yield first++;
  }
}

int main()
{
  for (int i : range(0))
  {
    printf("%d\n", i);

    if (...)
    {
      break;
    }
  }
}

可能性は無限です。当然、ジェネレーターとコルーチンはもっと奥深いもので、ここではさわり程度しか紹介していません。次回は、C++ のコルーチンについて詳しく取り上げます。今回取り上げたサンプルの完全版は、Compiler Explorer (godbolt.org/g/NXHBZR、英語) で確認できます。


Kenny Kerr は、著者であり、システム プログラマーであり、C++/WinRT の生みの親でもあります。彼は Microsoft の Windows チームに所属するエンジニアでもあり、Windows における C++ の未来を形作り、開発者が美しく高パフォーマンスなアプリやコンポーネントを、非常に簡単に開発できるよう取り組んでいます。

この記事のレビューに協力してくれた技術スタッフの Gor Nishanov に心より感謝いたします。


この記事について MSDN マガジン フォーラムで議論する