左シフト演算子と未定義動作

指定したビット数だけ下(LSB)からビットが立ったビットマスクを得るために

(1U << bits) - 1

という式を愛用していたのだがはまってしまった。bits == std::numeric_limits::digits つまり全て 1 のマスクにしたい場合、この式は未定義動作をもたらす。14882:2003 5.8/1 には（右シフトも含めて一般に）こうある。

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

そして実際に少なくとも x86 上ではまず期待通り（全て 1）にはならない。x86 アセンブリの左シフト命令はシフト数は 5 ビット分だけ有効である。つまり 32 == 100000(2) は 0 ビットシフトと同じになり結果として上の式は 1 - 1 == 0 となってしまう。

左シフトには他にも未定義動作となる場合があるのだがこの記述にも変遷がある。

14882:1998 と 14882:2003 では以下の通りである。つまり undefined behavior という記述がない。E1 が signed な場合はどうなるのが正しいんだよ、という感じである。恐らく未定義動作を意図していない記述だろう。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]

一方、14882:2011 （多分。自分の参照文書は n3291 なので違う場合もあり得る）では DR854 によりこうなっている。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2 × 2^E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ] one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

int, long int よりも大きな型も想定した記述となっていること、E1 が signed な場合にも記述が明確となり、負の場合には未定義動作となっている。

そして、既に DR1457 が出ており以下のように修正される予定である。

if E1 has a signed type and non-negative value, and E1 × 2^E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

これは、1 << std::numeric_limits::digits のように最大の負数を得るためにビット数-1（=符号ビット分少ないビット数）だけシフト、つまり符号ビットを 1 にするコードを合法にするためである。ただし、これは signed の範囲で表現できない unsigned の値から signed への変換について処理系定義の動作を含む。……しかしだったら signed 全体について全て unsigned にして処理した後 singed に戻すとか規定してしまえばいいじゃないかとも思う。

なお、右シフトについては実質的に記述は変わっておらず(文による表現が式による表現になっただけ)、E1 が負数の場合は処理系定義となっている（以下は n3291 より）。

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

図解 MPL Metafunctions

Boost ライブラリの中でも Boost.MPL は割と食わず嫌いというかなんとなく敬遠している人も多いライブラリのような気がする。MPL = Meta Programming Library ということで「メタプログラミング？黒魔術？」みたいな受け取り方をされているんじゃないかというか、実際には

Boostは一般人が闇に触れずとも闇の力を使える様にするアーティファクトですが、ちょっと使った程度の事では闇に落ちたりしませんから安心してBoostするといいです・ｘ・ （ｯｸｯｸｯｸ ##bot

— 伊藤 兎 (実際にんじん)さん (@USAGI_WRP) 2月 13, 2012

という言にふさわしい、コンパイルタイムメタプログラミングを Sequence、Iterator、Algorithm といったランタイム(実行時：コンパイルタイムの対義語として)の語彙で取り扱えるようにする一般人のためのライブラリである。typename ::type 乱舞になりがちなところと、代入や状態の変更ができず関数型言語的に記述する必要があるところだけ気をつければ難しくない。のだがちょっと自分の中で整理しきれていなかったのが Metafunction 関係である。前回 MPL 用再帰的 equal を書く中で大分整理できたのでまとめてみる。

MPL の Metafunction 関係について包含図を書いてみると以下のようになる。

MPL Metafunctions

Metafunction がランタイム世界での通常の関数にあたる。適用が ::type しないといけないところがちょっと面倒なところだ。Metafunction 以外の Lambda Expression は高階関数にあたるところであり Metafunction Class と Placeholder Expression からなる。Metafunction Class は関数オブジェクト(Functor)にあたると思えばよい。operator() の代わりにメンバテンプレート apply があると考えても良いだろう。さて、ランタイムにおける世界でも毎回毎回関数オブジェクトを書くのは面倒ということで Boost.Lambda や C++11 でのラムダ式がある。これの MPL 版にあたるのが Placeholder Expression だ。良く分からない英語が書いてあるが、placeholder(boost::mpl::_1 等)自身や、テンプレートパラメータのどこかに placeholder ないし Placeholder Expression を含むテンプレートクラスの特殊化(specialization)である。

_1
plus<_, int_<2> >
if_< less<_1, int_<7> >, plus<_1,_2>, _1 >

最後が bind expression である。これは単に bind の特殊化だ。bind はメンバテンプレート apply を持つため必ず Metafunction Class となるが、必ずしも Placeholder Expression とはならない。placeholder なしで bind することも可能だからだ。そのため Placeholder Expression から一部はみ出している。

bind< times<>, int_<2>, int_<2> >

さて、なんとなく Metafunction 族については分かっただろうか。自分もここまでは大体分かっていたのだがそれに作用するもの、具体的に主要なものをあげると apply, lambda, apply_wrap, protect, quote 辺りについて整理ができていなかったので以下に並べてみる。以下の図で青色が引数に取る対象、桃色がある場合はその部分が実際に変換される対象である。

MPL apply

apply は Lambda Expression を引数に取り、その Lambda Expression を適用する(呼び出す)。実際には lambda を適用した後で apply_wrap を呼び出す。では、その lambda と apply_wrap がどうなっているかというと、

MPL lambda

lambda は任意の型を引数に取るが、その内 Placeholder Expression を Metafunction Class に変換する。他はそのままである。

MPL apply_wrap

そして、apply_wrap は Metafunction Class の呼び出しである。実際には ::apply<...> と同等だ。なので、apply は lambda により全て Metafunction Class に変換した後、apply_wrap で呼び出すことになる。

MPL protect

protect は Metafunction Class を受け取るが bind expression しか変換しない。リファレンスマニュアルの例だが以下のように bind 時の placeholder の置き換えを抑止する。protect なしだと入れ子の bind 中の _1, _2 まで置き換えられているが、protect をかけると置き換えされない。

struct f
{
    template< typename T1, typename T2 > struct apply
    {
        typedef T2 type;
    };
};

typedef bind< quote3<if_>,_1,_2,bind<f,_1,_2> > b1;
typedef bind< quote3<if_>,_1,_2,protect< bind<f,_1,_2> > > b2;

typedef apply_wrap2< b1,false_,char >::type r1;
typedef apply_wrap2< b2,false_,char >::type r2;

BOOST_MPL_ASSERT(( is_same<r1,char> ));
BOOST_MPL_ASSERT(( is_same<r2,protect< bind<f,_1,_2> > > ));

MPL quote

最後に上の protect の例でも使われていた quote である。これは Metafunction を Metafunction Class に変換する。引数の数を指定する必要があり、その際デフォルトパラメータの部分も数えなければならないし、変換された Metafunction Class には全引数を渡してやらなくてはならない。bind 等と併用するくらいなら Placeholder Expression + lambda の方が楽かもしれない。

まとめ

どうだろうか。少しでも理解の助けになっただろうか？現実的には以下のルールに従っていれば大体問題ないと思われる。

• 高階関数を受け取る場合は Lambda Expression を受け取ることにする
  • 適用(呼び出し)する場合は apply を使う
  • 高階関数として「そのまま」渡したい場合は lambda をかける(protect をかけた状態になる。実際 lambda は Lambda Expression に対しては protect<bind<...> > になる)
• 高階関数として Metafunction を渡したい場合は quote をかける

Boost.MPL 用再帰的 equal

Boost.MPL の Sequence はその特性上 is_same を使いにくい。例えば

BOOST_MPL_ASSERT((
 boost::is_same<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

は通らない。push_front した結果は list ではなくなっているからだ。このため Boost.MPL には equal というアルゴリズムが用意されている。

BOOST_MPL_ASSERT((
 boost::mpl::equal<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

equal は Sequence の種類を気にせずその「要素」が一致しているかを判別するためこれは通る。通るのだが、equal は最上位の Sequence だけしか考慮してくれないため多次元の Sequence だとうまくいかない。equal の第 3 引数は要素を比較する際の Predicate であるため次元に合わせて equal を渡してやればいいのだが割と面倒である。

// bind base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::bind<
   boost::mpl::quote3<boost::mpl::equal>,
   boost::mpl::_1,
   boost::mpl::_2,
   boost::mpl::protect<
    boost::mpl::bind<
     boost::mpl::quote2<boost::is_same>,
     boost::mpl::_1,
     boost::mpl::_2
    >
   >
  >
 >));
// lambda base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::lambda<
   boost::mpl::equal<
    boost::mpl::_1,
    boost::mpl::_2,
    boost::mpl::lambda<
     boost::is_same<
      boost::mpl::_1,
      boost::mpl::_2
     >
    >::type
   >
  >::type
 >));

やってることは同じである。というか bind base の方は実質 lambda を展開した結果になっている。二次元でこれだとそれ以上だと絶望しそうだ。ということで再帰的な equal を書いてみた。

template<typename Arg1, typename Arg2, typename Pred = boost::is_same<boost::mpl::_1, boost::mpl::_2> >
struct equal_deep
{
 typedef typename boost::mpl::eval_if<
  boost::mpl::and_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
  boost::mpl::equal<Arg1, Arg2, equal_deep<boost::mpl::_1, boost::mpl::_2, typename boost::mpl::lambda<Pred>::type> >,
  boost::mpl::eval_if<
   boost::mpl::or_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
   boost::mpl::false_,
   boost::mpl::apply<Pred, Arg1, Arg2>
  >
 >::type type;
};
BOOST_MPL_ASSERT((
 equal_deep<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
 >));

やっていることはそれほど難しくない。引数が両方 Sequence である時には equal に対して自分自身(equal_deep)を渡して再帰し、両方が Sequence でない時には渡された Predicate を呼び出す。自分が MPL Metafunction 関係をちゃんと把握していなかったので lambda かけるところと apply で迷ったぐらいである。7 行目の eval_if は if_ だと is_same の場合は大丈夫だが Sequence に対して呼び出せない Predicate (equal_to 等) を渡した場合にコンパイルエラーになるため eval_if でなければならない。また、nullary Metafunction を受け付ける部分は typename ::type を付けずに不要なインスタンス化を避けている。

これを書く際にせっかくなので一度 MPL Metafunction 系について整理してみたのだが以下次号。