読者です 読者をやめる 読者になる 読者になる

ボレロ村上 - ENiyGmaA Code

中3女子です。

C++14 時代の constexpr プログラミング作法


この記事は、C++ Advent Calendar 2013 の参加記事です。
前回は 西山信行 さんの記事でした。


まもなく C++14 時代が到来しようとしている。
ただでさえ実用的な言語機能である constexpr が C++14 での制限緩和によって神になろうとしている。


C++11 での constexpr の制限は、必然的に副作用のない関数型プログラミングを強制し、とても興味深いものではあった。
コードの可読性云々は主観によるのでここでは置くが、時には非効率な実装にならざるをえないケースもあったのは事実だ。
C++14 での constexpr は、古典的な実行時処理に慣れた者達にも非常に親しみやすいコードが書けるようになる。


ドラフトの直接的な内容については、すでに自分をはじめ有識者が解説を書いているので、そちらを参照するのが手っ取り早い。

    • constexpr 関数の制限緩和

C++14 constexpr関数の制限緩和 - Faith and Brave - C++で遊ぼう

    • 定数式の条件

N3337 5.19 Constant expressions - ここは匣

C++14 のリテラル型 - ボレロ村上 - ENiyGmaA Code


ではどのように書けるようになるのか、手っ取り早い例を示す。

副作用のないアルゴリズムの実装

Sprout/sprout/algorithm/find.hpp at master · bolero-MURAKAMI/Sprout · GitHub

#include <iterator>
#include <type_traits>
#include <sprout/config.hpp>
#include <sprout/iterator/operation.hpp>
#include <sprout/iterator/type_traits/category.hpp>
#include <sprout/utility/pair/pair.hpp>

namespace sprout {
  namespace detail {
    template<typename RandomAccessIterator, typename T>
    inline SPROUT_CONSTEXPR RandomAccessIterator
    find_impl_ra(
      RandomAccessIterator first, RandomAccessIterator last, T const& value,
      typename std::iterator_traits<RandomAccessIterator>::difference_type pivot, RandomAccessIterator found
      )
    {
      return found != first ? found
        : pivot == 0 ? (*first == value ? first : last)
        : sprout::detail::find_impl_ra(
          sprout::next(first, pivot), last, value,
          (sprout::distance(first, last) - pivot) / 2,
          sprout::detail::find_impl_ra(
            first, sprout::next(first, pivot), value,
            pivot / 2,
            first
            )
          )
        ;
    }
    template<typename RandomAccessIterator, typename T>
    inline SPROUT_CONSTEXPR typename std::enable_if<
      sprout::is_constant_distance_iterator<RandomAccessIterator>::value,
      RandomAccessIterator
    >::type
    find(
      RandomAccessIterator first, RandomAccessIterator last, T const& value,
      std::random_access_iterator_tag*
      )
    {
      return first == last ? last
        : sprout::detail::find_impl_ra(first, last, value, sprout::distance(first, last) / 2, first)
        ;
    }

    template<typename InputIterator, typename T>
    inline SPROUT_CONSTEXPR sprout::pair<InputIterator, bool>
    find_impl_1(
      sprout::pair<InputIterator, bool> const& current,
      InputIterator last, T const& value, typename std::iterator_traits<InputIterator>::difference_type n
      )
    {
      typedef sprout::pair<InputIterator, bool> type;
      return current.second || current.first == last ? current
        : n == 1 ? *current.first == value ? type(current.first, true) : type(sprout::next(current.first), false)
        : sprout::detail::find_impl_1(
          sprout::detail::find_impl_1(
            current,
            last, value, n / 2
            ),
          last, value, n - n / 2
          )
        ;
    }
    template<typename InputIterator, typename T>
    inline SPROUT_CONSTEXPR sprout::pair<InputIterator, bool>
    find_impl(
      sprout::pair<InputIterator, bool> const& current,
      InputIterator last, T const& value, typename std::iterator_traits<InputIterator>::difference_type n
      )
    {
      return current.second || current.first == last ? current
        : sprout::detail::find_impl(
          sprout::detail::find_impl_1(
            current,
            last, value, n
            ),
          last, value, n * 2
          )
        ;
    }
    template<typename InputIterator, typename T>
    inline SPROUT_CONSTEXPR InputIterator
    find(
      InputIterator first, InputIterator last, T const& value,
      std::input_iterator_tag*
      )
    {
      typedef sprout::pair<InputIterator, bool> type;
      return sprout::detail::find_impl(type(first, false), last, value, 1).first;
    }
  }  // namespace detail

  // 25.2.5 Find
  //
  //  recursion depth:
  //    O(log N)
  //
  template<typename InputIterator, typename T>
  inline SPROUT_CONSTEXPR InputIterator
  find(InputIterator first, InputIterator last, T const& value) {
    typedef typename std::iterator_traits<InputIterator>::iterator_category* category;
    return sprout::detail::find(first, last, value, category());
  }
}  // namespace sprout

これは Sprout C++ Libraries による constexpr find アルゴリズムの実装である。
見てのとおり非常に長い。


C++14 限定ならば、以下のように書ける。

template<typename InputIterator, typename T>
constexpr InputIterator
find(InputIterator first, InputIterator last, T const& value) {
  for (; first != last; ++first)
    if (*first == value) {
      return first;
    }
  return last;
}

これは、C++03 時代からの古典的な実行時処理の記述と全く変わらない。
上記のコードは C++14 ならば constexpr 関数としてコンパイル時にも実行時にも使うことができる。


なぜ C++11 版の実装ではこんなに長くなるのか?


なぜならば、長いほうが実装するのが楽しいからだ。
縛りプレイの楽しみである。
言語的制約をテクニックでかいくぐる過剰に複雑なコードは黒魔術めいたアトモスフィアを孕んで、宗教的恍惚にも似たエクスタシーにわれわれを導く。
C++er という人種はそのような快感に脳を灼かれたジャンキーにして狂信の徒なのである。
というのはもちろん半分冗談であって、実際的な理由は以下。

  • インクリメントなどの副作用のある操作は C++11 では非定数式のため、イテレータ操作の別なインタフェースを用意する必要がある。
  • コンパイラの実装定義の再帰深度の制限(推奨値:512)があるため、再帰のオーダーを抑えるために index_tuple倍分再帰 などのイディオムを駆使する必要がある。

といった理由が挙げられる。


C++14 では副作用もループ構文も扱えることから、こうした問題を考える必要は(C++14 が前提なら)無くなる。


こうなると、もはや C++14 constexpr で出来ないことを挙げたほうが早いだろうので、そうする。

C++14 constexpr で不可能であること

実用上の問題になるだろうことをざっくり挙げる。

  • I/O
  • 動的メモリ(new/delete)
  • 例外処理(try-catch)
  • RAII(デストラクタを使った後処理)
  • ラムダ式


まあ妥当と言ったところだろう。
C++11 からすれば、むしろ「これだけなのか」といった感想だ。
このほか、制御構文の中で goto だけが許可されないなどといったこともあるが、大きな問題ではないので省略する。
ところで、ラムダ式が定数式でないのは諸般の事情があるので仕方ないとは思うけれど、
何でも標準化委員会内で日本のメンバから「ラムダ式が定数式であると SFINAE に悪用される」との反対意見が出たとの話を耳にした。
これについては甚だ遺憾であり、何をか言わんや、腹を切って死ぬべきであろう。


例外処理と RAII に関しては、例外安全絡みの問題が生ずるので、後でくわしく述べる。


また、constexpr 関数やクラスの実装においていくつか些細な注意点がある。

C++14 constexpr での注意点

  • ローカル変数は宣言と同時に初期化しなければならない。
  • トリビアルコンストラクタは、すべての非 static データメンバを明示的に初期化しなければならない。

これらは、処理系依存な未初期化値を扱えないようにするための仕様である。

  • 副作用を及ぼすオブジェクトは、定数式評価内で寿命が開始されたものでなければならない。
constexpr int& twice(int& x) {
  x += x; // 副作用
  return x;
}

constexpr int f() {
  int x = 10;
  return twice(x);
}
constexpr int y = f(); // OK. "f()" の中だけで副作用は完結している。

struct X { static int x; };
int X::x = 10;
constexpr int g() {
  return twice(X::x);
}
constexpr int z = g(); // error! "g()" の外側に副作用が及んでいる。

この仕様によって、副作用の制限緩和があっても定数式評価の中で副作用は完結するため、評価の前後で全体として副作用を持たないという一貫性が保持される。

糞仕様の改善によって、このような苦労 をせずとも普通のアクセッサが書けるようになる。
もし暗黙の const 修飾をあてにしたコードを書いていたら、今から明示的に const を付けるべきである。

ただし、トリビアル代入演算子は暗黙で constexpr 指定されない。(この問題は報告済みなので、仕様確定までに修正されるかもしれない)

  • ポインタ同士の比較、減算ができるようになった。

C++14 からは、ポインタ同士の比較や減算が定数式になった。
例えば以下のようなコードが書ける。

constexpr int a[10] = {};
constexpr auto dist = (a + 10) - (a + 0);
constexpr auto rel = (a + 10) > (a + 0);


ただし、同じ配列内の要素を指すポインタのように比較関係が明確なものではなく、無関係なポインタ同士の場合は ill-formed である。

constexpr int x = {};
constexpr int y = dist
constexpr auto dist = &y - &x;
constexpr auto rel = &y > &x;


C++11 でも、Sprout を使って以下のようにポインタ同士の距離を求めることはできた。

constexpr int a[10] = {};
constexpr auto dist = sprout::distance((a + 0), (a + 10));

しかしその実装は、ポインタを始端から終端まで一つずつカウントアップしていくという(BidirectionalIterator と同じ扱いの)非効率なものであった。
また、ポインタ同士の大小を確かめる方法は原理的に不可能であった。
つまり C++11 の定数式におけるポインタは、RandomAccessIterator の要件を満たすことが出来なかったわけだ。
C++14 からは、晴れてポインタを RandomAccessIterator として扱うことが出来るようになった。

Sprout/sprout/iterator/distance.hpp at master · bolero-MURAKAMI/Sprout · GitHub
もちろん、C++11 と C++14 双方でコンパイル可能なコードを書きたい場合は Sprout を使うべきである。

副作用のあるアルゴリズムの実装

最初に挙げた find のように副作用のないアルゴリズムは、インタフェースを変えずに C++11 constexpr の制約を満たすように実装することができる。
では、副作用のあるものはどうか?

template<typename Container>
constexpr Container
reverse(Container const& cont);

Sprout/sprout/algorithm/fixed/reverse.hpp at master · bolero-MURAKAMI/Sprout · GitHub


実装の詳細は省略するが、副作用のあるアルゴリズムは例えばこのように、
「コンテナを引数に取り、処理結果で再構築したコンテナを返す」というような副作用のない形にする必要があった。
すなわち、要素を一つだけ変更するといったわずかの処理でもコンテナ丸ごと再構築する必要があり、非効率だった。

template<typename BidirectionalIterator>
inline SPROUT_CXX14_CONSTEXPR void
reverse(BidirectionalIterator first, BidirectionalIterator last) {
  for (; first != last && first != --last; ++first) {
    sprout::iter_swap(first, last);
  }
}

Sprout/sprout/algorithm/cxx14/reverse.hpp at master · bolero-MURAKAMI/Sprout · GitHub


C++14 では、もちろんインタフェースもそのまま非常に簡単に実装することができる。


ここまで C++14 での constexpr の進歩を述べてきたが、今度は問題点に触れてみる。

標準ライブラリの問題


C++ 標準ライブラリの constexpr 対応はそれなりに進んでいる。
いるが、未だ不十分である。
現在 constexpr 指定されているものは C++11 constexpr の要件を満たすものであり、ほとんど C++14 の仕様に基づいてはいない。


また、規格で constexpr 指定されていないものを標準ライブラリの実装が独自に constexpr 指定することは明示的に禁止されることとなった。
C++標準ライブラリの非常に劣った実装が規格によって強制される - ボレロ村上 - ENiyGmaA Code


そのため、標準ライブラリの副作用のある関数やすべてのアルゴリズムは、constexpr 関数の実装のために使うことはできない。
もしあなたがconstexpr 関数の実装で様々なアルゴリズムを使いたい場合は、Sprout C++ Libraries を使えばよい。

例外安全性の問題

まず、可変長リストについて取り上げておく。
当然ながら C++14 であっても constexpr で動的メモリを扱うことはできない。
にも関わらず可変長リストは実装可能だ。リンクリストである。
しかしながら、使用するには非常に奇妙な制約があるので注意されたし。

#include <sprout/forward_clist.hpp>
#include <sprout/array.hpp>
#include <sprout/numeric.hpp>

constexpr int f() {
  int result = 0;
  auto li = sprout::forward_clist<int>();
  {
    decltype(li)::item it{ 10 };
    li.push_front(it);
    // li : { 10 }
    {
      sprout::array<decltype(li)::item, 5> its{{ 100, 200, 300, 400, 500 }};
      li.insert_after(li.begin(), its.begin(), its.end());
      // li : { 10, 100, 200, 300, 400, 500 }

      result = sprout::accumulate(li.begin(), li.end(), 0);

      li.unlink(its.begin(), its.end());
      // li : { 10 }
    }
    li.unlink(it);
    // li : {  }
  }
  return result;
}

constexpr auto x = f();
static_assert(x == 1510, "");

まず、リンクリストのノードはスタック上に無ければならず、つまりローカル変数として定義しなければならない。
またデストラクタでリンクを解放といった処理を書けないので、手動でリンクを解放してやる必要がある。
こんなもの使いたくはないと思うだろうが、とにかく可変長リストは実装可能なのだ。


ここで着目してもらいたいのは、ローカル変数への参照をオブジェクトに持たせている点だ。

constexpr void f(sprout::forward_clist<int>& li) {
  decltype(li)::item it{ 10 };
  li.push_front(it); // リンク
  /* 何か処理... */
  li.unlink(it); // リンク解放
}

このようなコードがあったとしよう。
仮に、/* 何か処理... */ の部分で例外が投げられたとしたらどうなるか。
コンパイル時の定数式評価であればその時点でコンパイルエラーになる。


しかし実行時であれば例外はそのまま呼出元に伝播する。
その結果、リンク解放の部分は実行されず、呼出元で li はすでに破棄されたローカル変数への参照を持ち続けることになる。
したがって、上記の関数は例外安全の基本保障(basic guarantee)を満たさない。


こうした関数を例外安全にするには、通常ならコンテナのコピーをとっておいてそちらに変更操作を行う。
しかしながら、このリンクリストの保持する各要素の実体はスタック上にあって、コンテナ自体がオブジェクトの実体を保持できないからコピーも不可だ。
また、すでに述べたように例外処理や RAII で何らかの巻き戻し処理を書くことも出来ない。
よって、この constexpr 関数を例外安全にするのは不可能である。


このような奇妙なリンクリストに限らず、ローカル変数への参照を扱うような場合には同じことが起きうる。
(なお、C++11 constexpr ではそもそもローカル変数を扱えないのでこの問題とは無縁)
問題は、constexpr 関数であるがゆえに例外安全に出来ないケースが存在することである。
読者諸賢はこんなコードを書かないように留意されたし。

コンパイラ

パフォーマンスについては検証が十分でないのでここでは言及を避ける。
というのも、現在 C++14 constexpr を十分に実装しているのは clang 3.4, 3.5(いずれも trunk)のみであり、
その clang も未だ致命的なバグが残っているため、十分な検証に足るコードを書くことが出来ないからだ。


いっぽう GCCC++14 実装では clang に遅れるが、C++11 constexpr について言えばより完成度は高い。
そういえば VC++ なる C++ に若干似たコンパイラも最近の CTP で constexpr を実装したそうだが、constexpr コンストラクタを定義できないため十分にはほど遠い。
残念ながらやはり VC++ は滅ぶべきであると考える次第と言わざるをえない。


まともな各 C++ コンパイラC++14 constexpr の実装が十分に完全なものになれば、より高速なコンパイルレイトレーシングなどの実装も可能になるだろうことは予想できる。

まとめ

C++14 での constexpr は、いくつか注意点があるものの、概ね非常に直観的に書くことが出来るようになった。


もはや、再帰深度に悩み苦しむことはない。
もはや、計算途中の値に名前を付けるためだけに実装関数を分ける必要はない。
コンパイル時処理は抽象マシンの動作として定義され、関数呼び出しの置換(function invocation substitution)の煩わしいルールには別れを告げた。


あなたの開発環境が constexpr を使える環境にあるならば、是非とも constexpr を使ってはどうだろうか。
何も最初から constexpr な実装を考える必要はない。
たとえばすでに書かれた関数に、そのまま constexpr を指定できるかどうかを考えてみるところから始めてもよい。


余計な副作用が紛れ込んではいないか?
goto に頼った制御をしていないか?
むやみにグローバル変数に依存してはいないか?
コンパイル時にできることをわざわざ実行時にやっていないか?
そうしたコードのブラッシュアップのきっかけにでもなればよい。


もちろん、純粋にどこまでコンパイル時にできるかを追求して楽しむのもよい。
コンパイル時にできることが増えるということは、それだけプログラミングの自由度が増えるということだ。
そうした中から有用なイディオムが生まれるというのも、これまで実際に起きてきたことである。


願わくは、あなたの C++ ライフがよりいっそう楽しく有意義なものにならんことを。


そして次回は hira_kuni_45 さんの記事です。
よろしくお願いします!