さいきょうの関数型言語はC++だったのかもしれないという可能性は慎重に検討されねばならない

はじめに

この文章についてあらましを簡単に述べると、まずC++11のstd::unique_ptrについてGCを必要としないコーディングが可能である見通しを説明する。つぎに関数型プログロミングについてマルチスレッド下においてロックが発生しない見通しを説明する。

それをふまえstd::unique_ptrを使った関数型プログラミングを行うためのライブラリであるところのlinear_moveを紹介する。できたてのほやほやだ。その後は理想と現実、夢と挫折について語りぐだぐだに終わる。

追記11/24：これは失敗ということで終了。しかし仕様の変更に合わせ以下に修正・加筆を行う。

std::unique_ptr

C++11の標準ライブラリにはunique_ptrってスマートポインタがある。これは単純ながら実に強力な代物で、やりようによってはGCも明示的なポインタの解放もなしにプログラムを書くことができるんだ。

例えば以下のような関数 foo があったとする。

std::unique_ptr <Hoge> foo (std::unique_ptr <Hoge> && h) {
    return some_cond() ?
        std::move (h) :
        std::unique_ptr <Hoge> (new Hoge (2));
    }
}

全く意味のないコードで申し訳ないんだけど、この関数はクラスHogeのunique_ptrを引数として受け取り、何かの条件に応じてそれをそのまま返すか、または新しいunique_ptrを返すんだ。

これを以下のように呼び出すとする。

std::unique_ptr hoge (new Hoge (1));
std::unique_ptr new_hoge = foo (move(hoge));

ここで変数hogeが保持するHogeインスタンスがfooに渡された後の運命を考えてみる。幸運であればそのまま返されnew_hogeに移る。不運であればfooのスコープから外れたタイミングで破棄される。

new_hogeに移ったHogeインスタンスの運命についても同じことが言える。そのまま上層にreturn moveされれば生き残るし、そうでなければ破棄される。

つまりunique_ptrはスコープの仕組みを巧みに利用していて、必要なインスタンスは生き残り、不要なインスタンスは自動で破棄される仕組みを実現しているんだ。だからゴミが出ない。GCがいらない。しかもほとんどノーコストらしいんだよ。しゅごい。

関数型プログラミング

このunique_ptrを関数型プログラミングで使ったら良さそうだと思わないか？関数型プログラミングでは値を変更しない。値を変更しないってことはマルチスレッドにおいてロックが発生しないってことだろ。ロックってのは値を読み取った後で書き込む前に別のスレッドによって更新されてしまうのを避けるのが目的なんだから。

unique_ptrであれば保持する変数が常に一つだから手続き型プログラミングでもロックが発生しないと思うかもしれないが、アクセスメソッドを通じてそれに対する書き込みや読み込みの要求が外から来ることになるだろうからやっぱり駄目だと思うんだ。

で。もしGCもロックも発生しないなら、それはマルチコアCPUを好き放題にぶん回せるってことだ。俺はそう思ったんだ１週間前に。そしてlinear_moveっていう小さなテンプレートライブラリを書いてみた。ここからが本題だ。

linear_move

名前が気に入っているんだ。linearってのは線形論理からきていて、moveってのはstd::move()からきている。データが関数から関数へと線形に動いていくからlinear_move。なにより速そうだろ語感が。

関数型プログラミングといえばcons-car-cdrのリスト構造だが、速さを重視するなら当然配列だ。だからlinear_moveではstd::vectorを基本データ構造として扱う。こういう感じで書くんだ。

auto hoge =
    fold (uniq<Hoge> (new Hoge (1)),
        [] (uniq<Hoge> && x, uniq<Fuga> && y) {
            int xn = x->get_num();
            int yn = y->get_num();
            x->set_num (xn + yn);
            return move (x);
        },
    filter (
        [] (uniq<Fuga> & fuga) {
            int num = fuga->get_num();
            return
                !(num % 2) ?
                    false:
                !(num % 3) ?
                    false:
                true;
        },
    map (
        [] (uniq<Hoge> && hoge) {
            return uniq<Fuga> (new Fuga (hoge->get_num() * 5));
        },
    progress (1000, uniq <Hoge> (new Hoge(1)),
        [] (uniq<Hoge> & hoge) {
            return uniq <Hoge> (new Hoge (hoge->get_num() + 1));
        }
    ))));
std::cout << hoge->get_num() << std::endl;

またもや全く無意味なコードで申し訳ないが、見た感じ何やってるかは大体分かるだろ？注意を要するのは、データは下から上に上がっていくってことだ。鮭の遡上と似てるな。鮭が川に上り始めたらもう海にはいないわけだろ？データが物っぽくなるんだ。

まず一番下のprogressってので1000個のHogeインスタンスを生成している。ここではメモリリークや不要なデータコピーが発生しないことを確認するためにHogeのuniq_ptrを生成しているが、別にint値でもいいんだ。

次がおなじみのmap関数。Fuga型のデータを返していることに注意してくれ。あとそれを受け取ったfilterがreturnしているところだが、もちろんnum % 2 && num % 3でいい。ここでは条件演算子をつなげてLISPのcond式みたいにできますよってことを見せたかったんだ。

最後の fold ってのはmap-reduceでいうところのreduceに相当するやつだ。Fuga型の配列を一つのHoge型のデータに畳み込んでいるんだが、注目してほしいのはx->set_num()ってところで破壊的なデータ操作を行っていることだ。

上述のように関数型プログラミングってのはデータの変更をしない。だからこの操作は他の関数型プログラミングならアウトなんだ。しかし思い出してほしいのは、unique_ptrってのは引数に渡した後は呼び出し側ではもう使えないってことだ。生きてるのか死んでるのか分からないんだから、死んだものとして扱わなければならない。

newってのは呼び出すのは実に簡単だが、裏ではOS様がとても苦労をなさっているそうなんだ。実メモリやら仮想メモリやらキャッシュメモリやらで色々大変らしいんだ。だからここではxを一度死んで生き返ったものと見なし粛々と再利用している。

まあこれはあれだ。プラクティカルでプラグマティックなあれだよ。

追記11/24：上書きするオブジェクトが他を参照している場合にその参照先を書き換えてしまう危険がある。

クイックソート

気を取り直し定番のクイックソートを実装してみよう。できるだけ関数型プログラミングにこだわりwhileやifなどの制御構文は用いない。

template <class T, class F>
std::vector<T> quick_sort (F && f, std::vector<T> && vec) {
    struct {
        F & f;
        std::vector<T> loop (std::vector<T> & vec) {
            return !vec.size() ?
                move (vec):
                let ([&] () {
                    T tail = std::move (vec [vec.size() - 1]);
                    auto ass =
                        assort (2,
                            [&] (T & elem) {
                                return this->f (elem, tail);
                            },
                            take (vec.size() - 1, move (vec)));
                    return combine (
                        append (std::move (tail), loop (ass [1])),
                        loop (ass [0]));
                });
        }
    } self = {f};
    return self.loop (vec);
}

なが！ちなみに Haskell 先生のは

quicksort [] = []
quicksort (x : xs) =
    let
        smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in
        quicksort smallerOrEqual ++ x ++ quicksort larger

うーん簡潔にして明快…。

エラトステネスのふるい

やばい飽きてきた。次もおなじみのアレ。

std::vector<Hoge> eratosthenes (int x)
{
    using hoge_vector = std::vector<Hoge>;
    auto s_vec = progress (x - 1, Hoge (x),
        [] (Hoge & pre) {
            return Hoge (pre.get_num() - 1);
        });
    auto p_vec = hoge_vector {};
    struct {
        int end;
        hoge_vector loop (hoge_vector & s_vec, hoge_vector & p_vec) {
            auto & head = s_vec [s_vec.size() - 1];
            return head.get_num() >= end ?
                reverse (combine (move (s_vec), reverse (move (p_vec)))):
                let ([&] () {
                    int head_num = head.get_num();
                    auto new_pvec = append (std::move (head), move (p_vec));
                    auto new_svec =
                        filter (
                            [&] (Hoge & hoge) {
                                return hoge.get_num() % head_num;
                            },
                        take (s_vec.size() -1, move (s_vec))
                        );
                    return loop (new_svec, new_pvec);
                });
        }
    } self = {(int)sqrt(x) + 1};
    return self.loop (s_vec, p_vec);
}

あーこりゃだみだ。ちなみにこれでも最適化コンパイルすると結構いい線いく。

追記11/24：テストして判明したが今まで掲載していたコードには誤りがあった。

ref_ptr ポインタ

気を取り直し最後の気力を振り絞りこれだけは伝えておかねばならぬことがある。実際のプログラミングにおいては実データが消されては困る場合が多々あるのじゃ。

たとえば俺が大好きなTVゲーム（遊ぶ方）においては画面外のオブジェクトは描画に際し不要なので刈り取る。これはカリングというそうな。

しかしその時点では画面外にあって刈り取られたオブジェクトも次の時点では画面内に入ってくるかもしれないから、データの実体を削除してはならない。

そういう場合のためにref_ptrというポインタのクラスを用意した。これはポインタをプライベートで隠蔽しているだけのクラスだが、実体を消さずにあたかもunique_ptrのように振る舞い各処理を行えるのだ。

auto hoges (
    progress (10, uniq <Hoge> (new Hoge(1)),
        [] (uniq<Hoge> & hoge) {
            int num = hoge->get_fuga()->get_num();
            return uniq <Hoge> (new Hoge (num * 2));
        }));
std::cout << hoges << std::endl;
auto refs (
    take (2,
    group (3,
    take (8,
    reverse (
    refdup (hoges)
    )))));

std::cout << refs << std::endl;
std::cout << refs[0][0]->get_num() << std::endl;
std::cout << hoges << std::endl;

refdupというやつでhogesの参照コピーを作っている。色々やってもhogesの実体は残っているので安心というわけ。まあひょっとしたらすでに標準ライブラリの中にあるかもな。

追記11/24：std::ref()とはまた異なるものだった。

マルチスレッド

ここまで読んでくれたひとありがとう。最後にお伝えしたいのは、現状俺のPC上ではこれはマルチスレッドでスケールしないということなんだ。

追記11/24：以下削除。マルチスレッドではどうやってもスケールしなかった。スレッドプールを使ってみたり、ベクターの要素をunique_ptrではなく値にしてみたりしたがどれもうまくいかなかった。

末尾再帰

擬似的な末尾再帰を行うloopという関数を用意した。

auto ret = loop (std::make_tuple (true, 1),
    [] (std::tuple<bool, int> && arg) {
        int num = std::get<1> (arg) + 1;
        return std::make_tuple (num < 5, num);
    });
return std::get<1> (ret); # 5

引数兼戻り値としてタプルを用い、１番目の要素が真の間はループを続ける。本来の末尾再帰は通常の再帰呼び出しよりも高速に動作するが、このloopはほぼ同じ速度だった。スタックを消費しないというところだけが取り柄だ。

クラスか構造体か

よくよく考えてみるとstd::vectorはヒープ上にバッファを確保するのであり、その要素がunique_ptrである必要はあまりない。そうする必要があるのは継承で多態をやりたい場合くらいじゃないか。

std::vectorの要素をクラスの値にする場合にはムーブコンストラクタとムーブ代入演算子というものを定義しなければならない。

Fuga(Fuga && self) noexcept
: num (std::move (self.num))
    { life_cnt++; };
Fuga & operator = (Fuga && self)
    { num = std::move(self.num); return *this; }

注意が必要なのは noexcept というやつで、これがないとpush_backのときにコピーコンストラクタが呼ばれてしまう。

しかしおすすめはC言語風にstructを使うことだ。

struct number { int num; };
number n = {1};

そうすれば自動でムーブコンストラクタやムーブ代入演算子が用意されるみたいだからだ。

終わりに

マルチスレッドでスケールしなかったことで俺の気分は萎え萎えMAXでありゆえにこれで仕舞いとする。

ドキュメントも用意できなかったが、現状アップロードしているmain.cppでは通り一遍のおざなりな単体テストをやっているのでそれを見てもらえれば使い方が分かるかもしれない。

まあしかしいくつか追加したい関数もあり、今後も気が向いたら何か更新するかもしれない。もし何か意見や質問があったらコメント欄に書き込んでくれ。良くしたもので、そうすると俺にメールで通知が届くのだ。