Boost.Context による単純なファイバー

C++ Boost

いわゆる非対称コルーチン。C++03/11 両対応。
https://gist.github.com/3684731
簡単な使い方。

#include <iorate/fiber.hpp>

int main()
{
    iorate::fiber f([]
    {
        for (auto const c : "Hello, world!\n")
        {
            std::cout << c;
            iorate::fiber::yield();
        }
    });

    while (f.alive())
    {
        f.resume();
    }
}

Boost.Context は trunk に入った当初は高レベル API を提供していたのですが、ある時を境にばっさり削除されてしまったという経緯があります（Boost.Contextの怒涛の変更 - にゃははー に詳しい）。おかげで Boost.Context でググって出てくる記事の多くは今では動かないコードだったり…。
まあ高レベル API は Boost.Coroutine あたりが Context ベースで書き直されて入ると思うので、もう少しの辛抱だと思います。

可変長引数を扱う手段として Fusion を使う

C++ Boost

Variadic Template による可変長引数 ...args は f(args)... で f(a1), ..., f(aN) に展開できますが

template <class ...Args>
void fg(Args ...args)
{
    f(g(args)...); // f(g(a1), ..., g(aN))
}

少し込み入ったことをする場合は、引数を Boost.Fusion の列にまとめてから操作することができます
例えば (a1, ..., aN) => a1 + ... + aN という関数を書きたい場合

namespace fusion = boost::fusion;
using namespace boost::phoenix::placeholders;

template <class A1, class ...Args>
auto plus(A1 const &a1, Args const &...args)
 -> decltype(fusion::fold(fusion::vector_tie(args...), a1, _1 + _2))
{
    return fusion::fold(fusion::vector_tie(args...), a1, _1 + _2);
}

fusion::fold を使い、演算子 (+) と初期値 a1 で列 [a2, ..., aN] を畳み込んでいます
（引数の無駄なコピーを防ぐためには *_tie を使うと良いでしょう）
Perfect forwarding を行いたい場合は PP に頼ることになるかもしれませんが
http://ideone.com/sUOIn
あまり書きたくありませんね

Iteratee で progress_display を書いてみた

Haskell

Iteratee を始めようと思いこちらを読んでいたのですが，
Lazy I/O must go! - Iteratee: 列挙ベースのI/O - 純粋関数型雑記帳
気になるフレーズが．

streamToFile "hoge" `enumPair` throbber とすることにより、ファイル書き込みに簡単に進捗表示をつけることができるようになります。その他、時間のかかるような処理にプログレスバー表示を取り付けたりするのも簡単です。

http://d.hatena.ne.jp/tanakh/20100824#p1

進捗表示？プログレスバー表示？
…
…
…
それは progress_display ではありませんか？
※ progress_display について

書いてみた

Iteratee like なパッケージとしては，見た目に分かりやすかった enumerator を使いました．
Progress.hs

module Boost.Progress (progressDisplay) where

progressDisplay :: MonadIO m
  => Integer -- expected count
  -> Handle  -- output handle
  -> String  -- leading strings
  -> String
  -> String
  -> Iteratee a m ()

progressDisplay に適当なパラメータを与え，他の Iteratee に zip して使います．
Main.hs

import Control.Exception
import Control.Monad.IO.Class
import qualified Data.Enumerator as E
import qualified Data.Enumerator.List as EL
import System.IO
import Boost.Progress

streamToHandle :: MonadIO m => Handle -> E.Iteratee Char m ()
streamToHandle h = E.continue go
  where
    go E.EOF = E.yield () E.EOF
    go (E.Chunks xs) = do
      liftIO $ hPutStr h xs
      E.continue go

main :: IO ((), ())
main = bracket (openFile "hoge" WriteMode) hClose $ \h ->
  E.run_ $
  E.enumList 64 (replicate 1000000 '\NUL') E.$$
  streamToHandle h `EL.zip` progressDisplay 1000000 stdout "\n" "" ""

出力

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************

実装

boost::progress_display の実装に合わせています．
Progress.hs

module Boost.Progress (progressDisplay) where

import Control.Monad
import Control.Monad.IO.Class
import qualified Data.Enumerator as E
import System.IO

progressDisplay :: MonadIO m
  => Integer -- expected count
  -> Handle  -- output handle
  -> String  -- leading strings
  -> String
  -> String
  -> E.Iteratee a m ()
progressDisplay n h s1 s2 s3 = start >> E.continue (go 0 0)
  where
    expcnt = if n <= 0 then 1 else n
    start = liftIO $ do
      hPutStrLn h $
        s1 ++ "0%   10   20   30   40   50   60   70   80   90   100%\n" ++
        s2 ++ "|----|----|----|----|----|----|----|----|----|----|"
      hFlush h
      hPutStr h s3
    go _ _ E.EOF = E.yield () E.EOF
    go cnt tic (E.Chunks xs) = do
      let
        cnt' = cnt + fromIntegral (length xs)
        tic' = floor (fromIntegral cnt' / fromIntegral expcnt * 50)
      liftIO $ do
        replicateM_ (tic' - tic) $ do
          hPutChar h '*'
          hFlush h
        when (cnt' == expcnt) $ do
          hPutStrLn h "*"
          hFlush h
      if (cnt' < expcnt) then
        E.continue (go cnt' tic')
      else
        E.yield () E.EOF

まとめ

遅くなりましたが，progress_display の追悼記事ということにします．
簡単に並置合成できるという Iteratee の利点も少し分かったような気がしますね．

Boost.Context でジェネレータを作る

C++ Boost

知らないうちに Boost.Context が trunk 入りしていたので，それを使って Python のジェネレータのようなものを作る CRTP クラスを書いてみました．
generator.hpp
メンバ関数 generate を実装するとジェネレータを作り上げてくれます．ジェネレータは，遅延評価される range として振る舞います．
以下の例はフィボナッチ数列を返すジェネレータを作るものです．

#include <iostream>
#include <tuple>
#include "generator.hpp"

struct fib
  : iorate::generator<fib, int>
{
    int max;

    explicit fib(int max)
      : max(max)
    {}

    template <class Context>
    void generate(Context &ctx) const
    {
        int a = 0, b = 1;
        while (a < max)
        {
            yield(a, ctx);
            std::tie(a, b) = std::make_tuple(b, a + b);
        }
    }
};

int main()
{
    for (int i : fib(100)) std::cout << i << ' ';
    // 0 1 1 2 3 5 8 13 21 34 55 89 
}

yield ベースの列挙を自然に書けていると思います．
Boost.Context は夢が広がりますね．

Boost.Context を GCC 4.8.0 20110302 で使うときの問題

上の例は GCC 4.6.1 (i686-pc-mingw32) + Boost Trunk 77256 で動作を確認しましたが，GCC 4.8.0 20120302 だと列挙を中断した場合に std::terminate() で終了してしまいます．
再現条件を探したところ，std::shared_ptr に指定したデリータ内で，完了していないコンテキストの unwind_stack() を呼び出す場合に（典型的には，std::shared_ptr<context> を使っている場合に起こります），std::terminate() が呼び出されるようです*1．

#include <memory>
#include <boost/context/all.hpp>
#include <boost/shared_ptr.hpp>

using namespace boost::contexts;

context ctx;

void f()
{
    ctx.suspend();
}

int main()
{
    ctx = context(f, default_stacksize(), no_stack_unwind, return_to_caller);
    ctx.start();

    // OK
    // ctx.unwind_stack();

    // std::terminate() is called at context_base.hpp:176
    std::shared_ptr<void>(nullptr, [](void *) { ctx.unwind_stack(); });

    // OK
    // boost::shared_ptr<void>(static_cast<void *>(nullptr), [](void *) { ctx.unwind_stack(); });
}

std::shared_ptr の排他制御が関係しているのかなと思いますが，よく分かりません．GCC のリリース版でも同じ問題が存在していれば，もう少し調べてみようと思います．

*1:スタック巻き戻しのために forced_unwind 例外が投げられる時点で呼ばれます．

ラムダ式でムーブキャプチャ

C++

ラムダ式での変数のキャプチャはコピーまたは参照で行いますが，ムーブするための標準的な方法はありません．

std::unique_ptr<int> p(new int(23));

auto f = [std::move(p)] { std::cout << *p << '\n'; }; // こんな書き方はない

どうしても変数 p をムーブしたい場合には，別の変数 p_ を用意して，p_ がコピーキャプチャされたときに p がムーブされるようにする方法があります．以下にそのためのクラステンプレート move_capture を示します．

#include <cassert>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

template <class T>
struct move_capture
{
private:
    bool has_obj;
    union { T *ptr; T obj; };

public:
    move_capture(T &t) noexcept
      : has_obj(false), ptr(std::addressof(t))
    {}

    move_capture(move_capture const &x)
    {
        construct(x);
    }

    move_capture(move_capture &&x)
      : has_obj(x.has_obj)
    {
        if (x.has_obj)
            ::new(std::addressof(obj)) T(std::move(x.obj));
        else
            ptr = x.ptr;
    }

    move_capture &operator=(move_capture const &) = delete;

    ~move_capture()
    {
        if (has_obj)
            obj.~T();
    }

    T &get() noexcept
    {
        assert(has_obj);
        return obj;
    }

    T const &get() const noexcept
    {
        assert(has_obj);
        return obj;
    }

private:
    template <class U, typename std::enable_if<std::is_copy_constructible<U>::value>::type * = nullptr>
    void construct(move_capture<U> const &x)
    {
        has_obj = true;
        if (x.has_obj)
            ::new(std::addressof(obj)) T(x.obj);
        else
            ::new(std::addressof(obj)) T(std::move(*x.ptr));
    }

    template <class U, typename std::enable_if<!std::is_copy_constructible<U>::value>::type * = nullptr>
    void construct(move_capture<U> const &x)
    {
        assert(!x.has_obj);
        has_obj = true;
        ::new(std::addressof(obj)) T(std::move(*x.ptr));
    }
};

template <class T>
inline move_capture<T> make_move_capture(T &t)
{
    return move_capture<T>(t);
}

使い方としては，make_move_capture で p から p_ を作り，それをコピーキャプチャします．

// ポインタの参照先を表示する関数テンプレート
template <class P>
void print(P const &p)
{
    if (p)
        std::cout << *p << '\n';
    else
        std::cout << "null\n";
}

void example()
{
    std::unique_ptr<int> p(new int(23));

    auto p_ = make_move_capture(p);
    print(p); // 23

    auto f = [p_]
    {
        // 元の変数の値にアクセスするときは .get() を使う
        print(p_.get());
    };
    print(p); // null
    f(); // 23

    auto g = std::move(f);
    f(); // null
    g(); // 23
}

もっとも，どうしてもムーブキャプチャしなければならない場面はそんなにないと思います．

Boost.Phoenix で range-based for

C++ Boost

phx::for_each より楽に使えるものをと．
https://gist.github.com/1540409

void revival_example()
{
    using boost::phoenix::arg_names::_1;
    using boost::phoenix::arg_names::_2;
    using boost::phoenix::local_names::_x;

    int array[5] = { 1, 2, 3, 4, 5 };

    /*
    for (int &x : array)
        x *= 2;
    */
    ranged(_x, _1)
    [
        _x *= _2
    ]
    (array, 2);

    int const result[5] = { 2, 4, 6, 8, 10 };
    BOOST_CHECK(boost::equal(array, result));
}

内部では iterator を回しながら phx::let にぶん投げているだけです．

std::common_type の問題点

C++
SFINAE に使えない

http://d.hatena.ne.jp/gintenlabo/20110420/1303288950
メタプログラミングをする上で不便ですね．

必ずしも「引数の型全てが変換される型」を返すとは限らない
struct A
{
    A(int) {}
    
    template <class T>
    A(T) = delete;
};

char c = '$';
std::common_type<char, int, A>::type a = c;
// エラー，delete されたコンストラクタの呼び出し

std::common_type の特殊化では対応できません (しきれません)．

あいまいな特殊化をしている

c++ - Partial specialization of variadic templates - Stack Overflow
14.8.2.5/9 に照らし合わせると，引数2つの特殊化があいまいになってしまいます．

std::common_type<char, int>::type i = c; // エラー，あいまい

規格の defect でしょうか．

Reference を返す場合がある

「や」の字: 【C++11】 decltype, conditional operator, そして common_type
これも defect のような気がしますね．

ではどうすべきか

あんまり使わないのがいいんじゃないでしょうか．