VS2013で遭遇した最悪なバグ

C++雑記 VS2013

自分が遭遇した最悪なバグを書いておこうと思う

型破壊バグ
std::cout << typeid(BreakType).name();//struct ??::??と出力される

//error C2133:サイズが不明です
//error C2512:コンストラクタがない
BreakType c;

上記のように壊れた型が発生する

初代ポケモンのケツバンを感じる
壊れた型をstd::is_sameすると「定数式ではない」と言われたりするが、結構コンパイルをすり抜けるのでツライ

この壊れた型は以下のようにして発生させた

template<class ...T>
struct List{};

template<class...T>
List<typename T::type...> break_f(List<T...>);

using BreakType = decltype(break_f(List<std::true_type, std::true_type>{}));

VSでテンプレート引数に::typeするのとパラメータパック展開するのはなぜかバグってエラーになる。が上記のとおり関数の宣言内だとなぜか通ったりする

しかし、通った結果が型破壊バグなのでパラメータパック展開とT::typeを組み合わせるのはやめよう
回避するにはT::typeを返すメタ関数Fを作り使うことだと思う
List:::type...>

宣言する順番で結果が変わるバグ
std::cout << logic<List1>::type::value;//1
std::cout << logic<List2>::type::value;//0

std::cout << logic<List2>::type::value;//1
std::cout << logic<List1>::type::value;//0

なぜか宣言する順番で結果が変わるバグ
このバグが現れるまで個人的最強最悪バグは上記の型破壊バグが有していた
だがこのバグは恐ろしく静かで、しかも意味不明なバグでありキンブオブ最悪バグとなった

このバグはallを実装するときに発生した

template<class list>
class logic
{
	template<class...T>
	static std::true_type impl(List<std::integral_constant<T, 1>...>);
	static std::false_type impl(...);
public:
	using type = decltype(impl(list{}));
};
using List1 = List<std::true_type, std::true_type>;
using List2 = List<std::true_type>;

このプログラムは正常に動けばどちらも1を返すべきである。しかしなぜか後に評価された方は0を返す。理由は不明


回避法は(そもそも遭遇しないと思うが)別の実装法をすることである

メタ関数の高階関数

C++



まず言葉の説明から

メタ関数

テンプレート引数として型を受け取り::typeで結果を返す型のこと
More C++ Idioms/メタ関数(Metafunction) - Wikibooks

例えばstd::add_pointer

std::add_pointer<int>::type//int*
高階関数

ハイオーダー関数
関数を受け取ったり、関数を返す関数のこと
高階関数 - Wikipedia
c++でいうとany_ofとか



で、メタ関数の高階関数とはメタ関数を受け取る高階関数のことである

例えばリストとメタ関数を受け取りリストの各要素に関数を実行して返す関数mapを愚直に実装しようとすると以下のようになる

template<class,template<class>class>
struct map;//ダミーの定義

template<class...T,template<class>class F>
struct map<List<T...>,F>
{
    using type=List<typename F<T>::type...>;
}

分かりやすい

ところでこの愚直なmapの実相にはテンプレートテンプレートパラメータが出てくる
テンプレートテンプレートパラメータにはいくつか問題がある

必要なタイプが多い、キモい、いろいろあるがとりあえずメタ関数で返すことができない

メタ関数のbindやカリー化はかなり有用であるがbindやカリー化は関数を返す関数である
しかしメタ関数はテンプレートテンプレートパラメータは返せない
これは結構問題だ

そこでメタ関数を普通の型に丸めるという方法が考案さえた
そして高階関数はこの丸められた型を受け取り使用するという方法を取るという方法を用いるようになった

丸められたメタ関数はこんな具合だ

struct F
{
    template<class...T>
    struct apply
    {
        using type=/**/;
    };
};

このようにapplyというメタ関数を持つ感じになる
考え方はテンプレート関数のoperator()()をもつクラスと同じだ

struct hoge
{
    template<class T>
    operator()(T x)
    {}
}

そしてこのクラスを

typename F::apply<a,b,c>::type;

として実行する
実用としてはメタ関数(applyとか)を作って

typename apply<F,a,b,c>::type;  //==F::apply<a,b,c>::type;

のように使われる


しかし上記の丸められたスタイルの関数は普通は作るのも使うのもだるい

たとえばif_

if_<a,b,c>;        //いつもの目に優しいメタ関数
apply<if_,a,b,c>;  //丸められたスタイル

上のほうがシンプルだ
if_を実装する側もいちいちラッパしたりapply書いたりするのはだるい

なので普段使いはいつものきれいなメタ関数を使い、高階関数を用いるときのみ丸めたメタ関数を使うことにした

そして何とかきれいなメタ関数から丸めたメタ関数に変換する機構が必要なので
このブログの冒頭で中三女子氏が言っていたquoteが作られることになった*1
この機構はたぶんこんな感じの実装だ

template<template<class...>class F>
struct quote
{
    template<class...T>
    struct apply
        :F<T...>
    {};
};

この機構のおかげで高階メタ関数を気軽に使うことができるようになった

map<list,bind<quote<if_>,arg<0>,void*,void>>;
//List<true_type,false_type>→List<void*,void>

しかしてまだ問題がある
std::is_sameのような::value返す系メタ関数だ
一般にメタ関数というのは::typeを返す。しかしis_sameはintegral_constantを継承する
有効なtypeを持たない。ここでquoteを用いるとapplyは::typeを返す関数ではなくなり高階関数が求めるメタ関数性を失ってしまう。よってこういうメタ関数用のquoteが必要である
それが中三女史氏が言っていたselfになる
おそらくselfの実装はこんな感じだろう

template<template<class...>class F>
struct self
{
    template<class...T>
    struct apply
    {
        using type=F<T...>;
    };
};

quoteとちょっと違うがまあこんな感じだろう
これで晴れて::valueを返す型を返す関数ができた
is_XXX系メタ関数はfilter関数などで活躍するのでselfもfilterにおいて活躍するであろう

filter<list,self<std::is_pointer>>


140819 selfについて追記

中三女史のコメントを見てもらうと分かるがstd::integral_constantは自身を返す::typeを持っている
なんか長い間すごい勘違いしてたよ
integral_constant、true_type、false_type (C++11) - cpprefjp - C++ Library Reference

でintegral_constanから継承されるis_sameは::typeを持つのでselfを使う理由にはならない

いつ使うのか?というのは例えば

self<List>

のような場合らしい
そういえば俺俺ライブラリで、高階関数に渡す用にmake_Listって関数を作ってた記憶がある

またselfとquoteを一つのquoteにまとめてメンバの所持で処理を分岐させるとSFINAEフレンドリでトンチンカンなことをする可能性があるという

quote<T>::apply<int>::type//T::typeがあるならT<int>::type、無いならT<int>

SFINAEフレンドリとは例えばcommon_typeなどで適合する型がなかったときコンパイルエラーで落とすのではなくて::typeをそもそも作らないようにしてSFINAEで弾けるようにしよう。という考えらしい

これをselfごっちゃなquoteにぶち込むとSFINAEフレンドリによってcommon_type::typeが返されるかもしれないし、common_typeが返されるかもしれない。結果としてトンチンカンなことになる

apply<quote<common_type>,a,b,c>::type 
//適当な型かもしれないしcommon_type<a,b,c>かもしれない

よってselfとquoteは分けられるべきである、とのことらしい

*1:俺俺MPLであるOTMPではliftとして実装されている。mpl11でもliftだった気がする

「脱アルゴリズム宣言」読書ノート

雑記

この話で出てくる「アルゴリズム」「脱アルゴリズム」という単語について

ここでいうアルゴリズムとは命令型言語的なアルゴリズムを指している
なので必要に応じて「アルゴリズム」という単語を「(命令型言語的)アルゴリズム」と脳内正規表現マッシーンっで置換してもらいたい
ここでそもそもアルゴリズムとは何か？という問題については言及しない。絶対しない

ちなみにもちろん関数型言語にもアルゴリズムはある。

Swiftで脱アルゴリズム！iOS開発を関数型（宣言型）プログラミングへパラダイムシフトしてみる【脱アルゴリズム宣言①】 - Qiita

この章は関数型と手続型の違いについて、および関数型の入り口について話している

まずApple言語のSwiftの諸々について書いてある
要約するとSwiftはモダンらしい。ここは別にどうでもいい。どうせ次の章では出てこない

次に命令型(手続き型)と宣言型(関数型)のコードの違いについて記している
手続型とは要するにC言語childrenなどのことを指す言葉である
いわゆるフローチャートとかそういう感じの、一般によく使われるプログラミング言語のパラダイム(種類）だ。この手続型という思想はアセンブラやマシン語からきている

対し関数型とは古いところだとLISP大先生、最近だとHaskellなどを指す言葉である
関数型という思想は数学からきている*1

関数型の利点は数学的な問題をかなり数学的な記法で解くことができることだ
当然数学的な問題は数学に近い記法のほうが直観的だ

ここで出てくる*2reduceは2引数を取る関数を受け取り

sum(sum(sum(sum(1,2),3),4),5)

のようにしてくれる優れものである

私も

range({1,2,3,4,5}).resuce(add)

のようなコードを美しいと思う。関数型は美しいです。reduceイエーイ

JavaScript - 関数リアクティブプログラミング（FRP）で分断された2つの世界を繋ぐ【脱アルゴリズム宣言②】 - Qiita

いつの間にかJavaScriptの記事になったが気にしない。気にしてはいけない

ここでいう「分断された2つの世界」というのは「数学世界」と「物理世界」のことらしい
「物理世界」というのはつまり現実のことである
現実というものには時間があり空間があり、そしてそのどれもが実質有限である
対し数学というのは時間も空間も無限にある前提で構築する*3

FRPとは
よく言うのがエクセルとか。入力値の変化によって出力値が自動で変わったり
これは関数型が入力に対し出力が変わらないことを利用している


Swift - 関数型（宣言型）プログラミングで無限をコーディングする「遅延評価」のわかりやすい解説【脱アルゴリズム宣言③】 - Qiita

一応、成り行き上Swiftのタグをつけていますが、実質JavaScript/node.jsの記事になっています。

はい

「アルゴリズム」というバズワード、言葉の定義について

はい
遅延評価について
遅延評価とは可能な限り評価を遅らせることを指す
例えばリストAの各要素に+5をしたリストBがあるとする

auto B=A.map([](int n){return n+5;});

この時まだ各要素に+5する必要はない。まだ使わない

for(auto x:B)print(x);

のように使う必要になるまで計算するのを遅延しても何ら問題ない

遅延評価を用いる利点は

  1. 即時評価だとAの要素数分のメモリが必要になる
  2. 即時評価だと仮にAが何らかの方法で無限リストが実装されている場合、Bは無限長さになりパンクする
  3. もしかしたら全部の要素評価する必要はないかもしれない

などなど

記事にも書いてある通り遅延評価を用いると無限リストが使える
この辺はC++でも採用されている。詳しくはBOOST.rangeを見てほしい
そろそろ来るといわれ続けているrangeV3ではさらに無限の扱いが用意になるだろう
例えば素数1000個欲しい場合

make_natural_list()//1,2,3...という無限リストを作る
.filter(isPrime)//そこから素数のみ抜きだす
.take(1000)//そこから先頭1000個とる

となる。こういう問題の時無限リストを扱えると強い


時空プログラミングのほうも読もうと思ったけどもう疲れたよ

*1:宣言型==関数型ではない。prolog大先生がいる

*2:Haskellで言うところのfold。C++でいうとstd::accumulateが近いかもしれない

*3:リーマン巡回問題とか応用数学の類はここでは忘れてくれ

c++11constexprでコンパイル時バイトニックソートを大雑把に実装した

C++

ネタではなく非常に強力であり実用的なソートである
//コード
bitonic_sort.hpp
//実行結果
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

ちなみに一部コードは
C++11 constexprでマージソート - ここは匣
から借りてきた




バイトニックソートとはマージソートの亜種であり、マージソート以上に並列実行に特化したソートアルゴリズムである
ギミックが美しい。とても美しい。ミニマルを感じる

おおまかな動きはここを見てほしい
バイトニックソート - 高速化プログラミング
詳しいアルゴリズムはここを見てほしい
Bitonic sort

バイトニックソートは再起オーダーO((log N)^2)で実装することができる
これはもはやconstexprするしかない。するべきである
O((log N)^2)というのは実用上十二分に使える数値である。1024要素あっても100*Kだ

O((log N)^2)というオーダーはマージ処理を可能な限り一つの関数で行うことによって実装されている
constexprでも並列実行は有益であるといえる

c=pow(2,k)のとき、n xor cはn + c*((n/c) mod 2 ? -1:1)と等しいらしい

C++雑記

解説

c == pow(2,k) == (1<<k)
n + c*((n/c) mod 2 ? -1:1)
→ n + c*((n/(1<<k)) mod 2 ? -1:1)
→ n + c*((n>>k)mod 2?-1:1)
→ n + c*([nのk番bitが立っているか]?-1:1)
→ [nのk番が立っているか] ? n-c :n+c
→ [nのk番が立っているか]? [nのk番を折る] :[nのk番を立てる]
→ n^c

constexprで無限リスト作った

C++

こんな感じ

struct Func
{
    constexpr int operator()(int i)const
    {
        return i+1;
    }
};
make_recurrence_list(0,Func{});//0,1,2,3,4...

無限だから長さを求めようとすると無限ループ起こしてコンパイラが死ぬ
単方向リストだから巻き戻しもできない
かいててラムダ式がconstexprだったらなぁとか考えた

gist
https://gist.github.com/Fuyutsubaki/a17eec9fb0735baaff92

wandbox
http://melpon.org/wandbox/permlink/Q1e32fdki75pTbmt


これの当初の使い方の予定はマージ関数の実装に使う予定であった

({},{1,3},{2,6})//result,left1,left2

このようなタプルを作り

({},{1,3},{2,6})
→({1},{3},{2,6})
→({1,2},{3},{6})
→({1,2,3},{},{6})
→({1,2,3,6},{},{})

のような関数を作り

find_if(make_recurrence_list(init,Func{}),is_empty_left)

のようにすれば自身は一度も倍分再帰を書くことなくマージ関数をO(logN)再起実装できる

マージ関数のみならず、無限リストとfindを組み合わせることにより幅広い再起関数を再起を用いずに書き直すことができるであろう

ちなみにこの方法、どうもメモリをドカ食いするとの話も出ている
コンパイル時マージソートの話｜どっかのゆとりのチラシの裏

だがイテレータを使う方法は自分でもイケてると思う
実際実装するのはもういいよ。他の人が実装してくれたし

ドワンゴC++勉強会 #1に行ってきた

C++雑記

タイトルの通りである
ドワンゴC++勉強会 #1 - connpass

constexpr関数はコンパイル時処理。これはいい。実行時が霞んで見える。CPUの嬌声が聞こえてきそうだ

*1
発表者：ボレロ村上氏
資料：http://www.slideshare.net/GenyaMurakami/onstexprcpu*2
内容は(いつも通り)constexprについて
今回はどちらかというとC++14以降の話が増えた気がする。そして圧倒的constexpr押し

constexprはもともとコンパイル時処理と実行時処理の隔てりをなくそうという思想のもとに作られたものであったがC++11の実装であると実用上かなり厳しいものがあった
C++14ではforや一時変数等の規制が緩和されるので(ネタではなく)かなり実用的になるだろう
そして型プログラマーは新しい道具を手に入れさぞ喜ぶであろう

ただC++14でも17でもどうしても実装上の関係でconxtexprにするのが不向きな関数が出てくる
その時のために実行時とコンパイル時の実装を分けるようなis_constexprのようなコンパイラマジックによって作られた関数が必要になるという話もあった
uncaught_exceptionのような関数もあることだし私も必要だと思う

ちなみにこの発表は予定を15分から20分ほどオーバーした

The Define and Expansion of CPP Macro

発表者：でちまる氏
資料：Define and expansion of cpp macro

実はでちまる氏ではなくでちまる氏の兄という設定らしいのででちまる氏の兄氏と呼ぶのが正解である。難しいことはよくわからないが本人がそういうのだからそうなのだろう

内容はマクロ。というか魔黒
魔黒が用いられるのはTMPもconstexprも取りこぼした領域である
そして魔黒は暗黒技術であり使うべきでないと自分は認識している
使うべきではないが見ていて大変楽しい技術でもある

魔黒のちからで実質的に文字列の置換と結合しかできないマクロでループしたり足し算したりとやりたい放題するモヒカンも真っ青な発表であった
ちなみにでちまる氏、当日エクストリーム資料作成をしていたらしい。自分の記憶では発表のトップバッターはでちまる氏だった気がする。モヒカンも真っ青である

C++の歴史

発表者：江添亮

EzoeRyou/cpp-history · GitHub
の加筆版。そのうち資料も公開されるだろう。GPLで
加筆と言ってもこの資料はおよそ半年前に作られたものでありそうそう大きく歴史が変わったわけではなく純粋なC++の歴史に関する話はおおむねこの資料でケリがつく

今回加筆されていたのは主に政治が絡むC++の話である
いろいろあって日本のC++委員会がこれでイインカイという状況であるという話である
詳しくはそのうち公開される資料を見てほしい


LT

templateを依存型っぽく使ってみる

発表者：南山まさかず@東京 (minamiyama1994) on Twitter
資料：#dwangocpp #1 templateを依存型っぽく使ってみる - Google スライド

依存型というのは例えば[0,100]の範囲のintger型を作ってそれ以外の値は代入できないようにしよう、とか[0,100]+[-10,10]->[-10,110]とかそういう話らしい
それをtemplateでやれないかという話
ちなみにこの発表は５分ほどで終わった気がする

constexprで使えるイディオム

発表者：抹茶ココア (fimbul11) on Twitter
資料：constexpr idioms
constexprのidiomに関する発表
自分のすごく青いコンパイラではconstexprは(完全には)使えないがこれらのテクニックはTMPでも役立つ
自分の記憶では型mapについてのときにいちばん反応があった気がする
value_atは標準入りするらしくコンパイラマジックで再起・計算量O(1)になるかもしれないみたいな話を江添さんと話していた

Cocos2dxの闇

発表者：ぽんこつ@MyFleetGirls開発中 (ponkotuy) on Twitter
資料：https://dl.dropboxusercontent.com/u/629338/pdf/Cocos2dx.pdf

正確にはcocos2dx ver2の闇
ツライというはなし。実際聞いててつらい。なにがCCobjectだ。なんて現実だ
最後にUnity(C#)とかVer3使いたいという話に
「いや、UnityC#もつらい」とか「V3もつらい」とか聞こえてきて辛い
何が正義だ*3

C++初心者書がC++11でparserを書いてみた話

発表者：かるぱねるら (karupanerura) on Twitter

曰く会場に潜り込むためにLTに申し込んだらしい。曰く8年近くC++触ってなかったらしい
チョットデキル勢じゃなかった
ちなみにLispパーサは完成しなかったらしい。そのうち完成するだろう

valgrindは実行時メモリチェッカー。これはいい。コンパイル時チェックは結局頼りにならない。メモリの悲鳴が聞こえてきそうだ

発表者：ψ（プサイ） (tikal) on Twitter
資料：
valgrindは実行時メモリチェッカー。これはいい。コンパイル時チェックは結局頼りにならない。メモリの悲鳴が聞こえてきそうだ
この時期SwiftがHotだったことが分かるタイトル
ちなみに自分はappendに関する記事(SwiftのArrayがヤバイ - Qiita)を見てswiftを見限った。言語に美しさだけを求めるならLispでもやればいいじゃない

実行時メモリチェッカーvalgrindに関する発表。嵐のような熱い発表であった
江添さんいわく最後に持ってきてよかったと
メモリリークやメモリ破壊などをチェックしてくれるツールらしい


ニコ生について

会場がドワンゴなのでニコ生を用いた配信も行われた
ちなみに自分は見ていない。会場にいたからね
途中機材が壊れたりしたらしいがよく知らない

自分の予想としては今回の参加希望者が190人ほどだったのでもしかしたら5,600人来るかなと思っていたのだが噂によると4000人以上来たらしい
が、聞いた話によると#defineって何という視聴者も多かった、とか
ニコ生にドワンゴの名が冠された放送があったので寄った人が多かったのでは?とか
そういう話を私は聞いた

確かに今回の勉強会は初学者には厳しいというか回れ右ともいえる
ちょっと日々の運動不足解消にとスポーツジムを覗いてみたら生卵飲んでるマッチョと目があった気分だ
勉強会の説明に「江添とでちまるとボレロ村上の闇の共演」と書いてある時点で闇だし
3人の発表だとconstexprがフェーズとしては一番遅いというアレだし
cocos2dxで「やったぁ!!実行時処理だ!!」って話が出るし
迷い込んでしまった人にはご愁傷様としか言いようがない
でもC++頑張ってほしい

まとめ

  • 非実行時処理は割とおなか一杯になったかもしれない
  • ニコ生は予想以上に人を集めたらしい

*1:このタイトルはAppleがswift発表した際にとある人が歓喜のあまり 「Swiftの関数はHaskell風。これはいい。マシン語が透けて見える。CPUの歓声が聞こえてきそうだ 」 と歓喜した事がもとになっている。どうせあと２週間後には元ネタなんて忘れてるので一応記しておく

*2:心底どうでもいいがこのURL、constexprの最初のCが抜けている

*3:「いや、最近はよくなってきた」という話も聞いた。何が本当かは使ってないのでわからないが「Unityに幻想を抱くな」という呟きは肝に銘じておこうと思う