神と腹痛と科学

諸君お気づきであろうか？神や真理というのは病める時も健やかな時も我々の理と無関係に在るのである

先日腹痛に見舞われた。正露丸の瓶は空であった
幸い自宅であったため好きなだけトイレの住人と化すことはできたのだが、私は襲い来る痛みの波をただただ耐えるほかなかったのである

腹痛というのは内臓痛であり、外傷などによって引き起こされる痛みとはプロセスが異なる。格闘家でも腹痛は耐え難い痛みであると聞く。つまりとても痛い

正露丸はない。科学は私を見放した
私は腹部を出来る限り温め、チャント*1を唱え、神に祈った

するとだんだんと腹痛が引いていくではないか
私は精神を持ち直た。神のことは忘れた

これでも私は一応科学を修めた人間である。ゆえに似非科学というのは鼻で笑うような対象であると考えている

しかし、もしも腹痛下、トイレにたまたま「おなかに効くお地蔵」がいたらどうしただろうか
多分拝んだと思う。拝み倒したと思う。現に神に祈ったし

今回は腹痛であったが、これがもし癌であったら私はどうしたであろうか

療法(正露丸)は尽きた。そしてがんが治る水なる怪しげなものを売りつける輩が来た
恐らく私はその水をがぶ飲みするだろう。私は腹痛で神に祈る人間である。私はその似非科学を使うだろう。普段であれば鼻で笑ったその水を

そんな時も神や科学と言ったものは、私とは無関係に在る
病める時は科学を忘れ神に祈り、健やかな時は神を忘れ科学を信じ。

もしかすると、そんな私を神や科学はどこかで見下ろしているかもしれない。それはさすがに自意識過剰か

私という人間は痛いだ熱いだ苦しいだで真理というものを容易に失うが、それでも科学や神は在って
私という人間は病める時の言うことはあてにならず、ゆえに健やかな時も言うことはあてにならず、私という人間と無関係に神や科学はあるのです

当たり前のようであたりまえな話

*1:ｲﾀｲﾉｲﾀｲﾉﾄﾝﾃﾞｲｹ

constexpr で テンプレートメタプログラミング

この記事はC++ AdventCalendar2014 6日目の記事になります

祝C++14!!祝C++14!!祝C++14!!祝C++14!!

C++14においてconstexprの大幅な規制緩和が制定された
これによりconstexprにおいてforなどループ文の記述が可能になった

一方そのころTMPは

残念ながらテンプレート用for文が入ることはなかった
しかしTMPはfor文を必要としている。forは力だ。力はいい。持ちすぎて困ることはない

そしてTMPにかなり近いところにいるconstexprは今、for文を持っている。これを利用しない手はない

constexprを用いたフィルターメタ関数の実装

template<class tList,template<class>class Pred>
struct filter
{
    static const std::size_t N=tList::size;
    template<std::size_t...Idxs>
    static constexpr sprout::pair<std::size_t,sprout::array<std::size_t ,N>> impl(std::index_sequence<Idxs...>)
    {
        sprout::array<bool ,N> v{{(Pred<at<tList,Idxs>>{}())...}};
        sprout::array<std::size_t ,N>idx{{Idxs...}};
	std::size_t k=0;
	for(std::size_t i=0;i<N;++i)
	{
		if(v[idx[i]])
		{
			idx[k]=idx[i];
			++k;
		}
	}
         return {k,idx};
    }
    static constexpr auto res=impl(std::make_index_sequence<N>{});
    template<std::size_t...Idxs>
    static constexpr List<at<tList,res.second[Idxs]>...> impl2(std::index_sequence<Idxs...>){return {};}

    using type=decltype(impl2(std::make_index_sequence<res.first>{}));
};

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

Impl は必要な型のインデックス配列とその長さを返す
impl2は結果の長さと同じ長さのindex_sequence→残す型のインデックス→残す型に変換していきタイプリストにする

結果、タイプリストと評価用メタ関数を受け取り、タイプリストを返すメタ関数を作ることができた

せっかくだからバブルソートも書いてみた
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
比較するときにis_base_ofを使うような場合は使えないが実用上問題はないだろう*1

型安全printfなど構文解析が必要な所作もconstexprを用いて実装可能だ*2

このようにconstexprを使い頭皮に優しい、もしかしたらコンパイラにも優しいTMPが可能になる

まとめ

このように今まで型を必要としていた分野、今までゴリゴリとTMPしていた分野でもconstexprを用いることができる。やるやらない出来る出来ないは別としてゴリゴリと型を用いるプログラミングをする際は頭の片隅に入れておくべきである

なおこれらのコードはClangでしか動かない
各コンパイラ、とくにMS社の蒼いコンパイラには頑張ってもらいたい

C++ Advent Calendar 2014 - Qiita

明日はh_hiro_ さんです
よろしくお願いします

おまけ。

値と型、そして未来

2014年現在 型安全printfは実用上マクロ(SPROUT_TYPES_STRING_TYPEDEFなど)に頼る必要がある

printf(MACRO("%d%d%d"),a,b,c)

値を型に用意に変換する構文がないのだ。マクロを使わない場合ラムダ式内で構造体を作って云々

[]{struct hoge{constexpr auto operator()(){return "%d%d%d";}};return hoge{};}()

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

もしくは

mpl_string<'%','d','%','d','%','d'>{}

非常に残念な感じだ

残念な感じなので未来に願いを託そう
まず文字列ユーザー定義リテラル
すごいユーザ定義リテラルたのしく遊ぼう - ボレロ村上 - ENiyGmaA Code
の一番下に載っているヤツだ

これはmpl_stringの構築を容易にする構文だ
mpl_stringからconstexprな文字列に変換するのは容易なのでコレがあれば型printfつらい問題は解決する

もう一つの可能性はラムダ式だ。ラムダ式がデフォルトコンストラクタを持ち、constexprになれば、つまり

[]{return "%d%d%d";}

が

struct _
{
	constexpr auto operator()()const{return "%d%d%d";}
}

を生成するようになれば,ラムダ式はintegral_constant的な関数とみなせるようになる
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
なぜラムダ式がconstexprではないかというと
本の虫: もしlambda式がconstexprだったら

という経緯があるためである
逆にいうとコンセプトが入った段階でラムダ式がconstexpr化する可能性も無きにしも非ず、かもしれない

*1:その場合はバイトニックソートとか使おう

*2:面倒なので実装しないが

デジゲー博で頒布したはるはあけぼのの不具合について

デジゲー博で頒布したゲームにいくつか不具合が見つかりました
申し訳ありません

お手数ですが以下のファイルの中身をすべてゲームのフォルダにコピーしてください。同じ名前のものは置き換えてください。
https://www.dropbox.com/sh/p7foxjuvncedu8p/AAAi6brXT5eeWW5ql0Xi67Hka?dl=0

本日(11/16)開催のデジゲー博に参加します。C-02a TXT.TXTです。

ゲームが出来たてほやほやなので取り急ぎ告知と宣伝
自爆しちゃう系STG「はるはあけぼの、我は弾丸」を頒布します
C-02a　です

■おはなし
およそ50年ほど前、地球温暖化対策として植林したバイオ植物が思いのほか育ちすぎてしまいました
元気な植物たちは盛んに求愛します。花粉被害が凄まじいです
時の大国は安価で小さな機械を量産し花粉を駆除することにしました
その、安価で小さな機械があなたです
さあ死にましょう。お仕事です

■操作説明
[矢印キー] :移動 /移動します
[zキー] :ショット /弾を撃ちます
[xキー] :自爆 /押すと自爆準備に入ります。ボタンを離すか一定時間経つと自爆します
[cキー] :母艦移動 /復帰時の開始地点を移動します

標準ライブラリに重複した型を取り除くuniqueifyが入るかもしれないっていうからuniqueの実装について

本の虫: 2014-10-pre-Urbanaのレビュー: N4142-N4149
曰く重複した型を取り除くuniqueify が追加されるかもらしい
そこで実装の話

俺俺ライブラリOTMPよりunique

uniqueはタイプリストを受け取り重複した型を取り除き返す

    unique_t<List<char,int,long,int>>;//List<char,int,long>

この処理は「二つのユニークなリストL Rを受け取り、RからLの中に含まれているものを除いたリストをLの結合させ返す」メタ関数unique_concatと2分割統治するfoldがあれば実装できる

    template<class L,class R>
    unique_concat=concat<L,
        remove_if<
            R,
            rcarry<lift<is_in>,to_set<L>>
        >>
    fold<map<List,self<List>>,unique_concat>

unique_concatのイメージ
(char,int,long),(long,char,void)
(char,int,long),(void)
(char,int,long,void)

畳み込みのイメージ
(char,int,lomg,int,long,char,void)
こーして(map< List,self< List>>)
( (char),(int),(lomg),(int),(long),(char),(void))

foldで二分木にして処理して
[[[(char),(int)],[(long),(int)]],[(long),(char),(void)]]
unique_concatで畳み込んでいく
[[(char,int),(lomg,int)],[(long,char),(void)]]
[(char,int,long),(long,char,void)]
[(char,int,long,void)]

unique_concatについてはis_inで検索しやすいように集合に直しておくと良い(to_set< L>)
O(1)で要素を探すことができるのでO(n^2)だったunique_concatがO(N)になる

集合に実装については要素をすべてwrapして多重継承
検索時にはis_base_ofすればいいだろう

/*こんなイメージ。実際は同じ型があった時対策でもうちょっと色々ある*/
template<class...T>
struct set:wrap<T>...{};

LocalTypeHashというかKeyにかぶりがあってもコンパイルを通す型mapの種

受け取ったタイプリストに対し適当な数字を被らないように返すLocalTypeHashメタ関数を作りたい

using TypeHash=makeTypeHash<List<char,int void>>;

TypeHash::apply<char>//0
TypeHash::apply<int>//1
TypeHash::apply<void>//2

こんな感じ

しかして型が被った場合どうなるだろう

この場合このままだと環境によって違う動きをすることになるだろう。未定義動作である
あるコンパイラは不明瞭だと言い動かないし、あるコンパイラは小さいほうの数値を返すし、あるコンパイラは大きい数値を返すであろう。くそぅくそぅ

……という内容の記事を今年の5月ごろ書いた
規格的にヤバそうな限定type_hashメタ関数を作ったけどGCCで動かないし、別の実装とかも考えたけどそれもダメくさいしもうだめだ - TXT.TXT

この問題を解決するのにuniqueを使っている
しかしuniqueという動作は結構重い。そこでuniqueを使わない方法を考えてみた

local_type_hash

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

検索時まず一番最初のAの中から探す
テンプレート関数とオーバーロード関数があるがオーバーロードのほうが呼び出し優先順位が高いのでまずオーバーロード関数の中からマッチする関数の検索が始まる
もしもAの中でかぶりがある場合より継承が低いレイヤー、つまりリストの左の方が優先される
オーバーロードの中でマッチする関数が見つからない場合、呼び出し優先度が低いテンプレート関数が呼び出され次のAに移る
以降繰り返し

この方法だと再起深度はO(√N)に抑えられるだろう。1024でも32*Kなので大丈夫(たぶん)

VS2013で破綻した型の名前を出力してたら{ctor}の文字が出てきた

タイトルで話が完結している

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

	template<class...T>
	std::true_type length_impl(List<T...>);

	template<class T>
	struct wrap{ using type = T; };

	template<class T>
	using identity = typename wrap<T>::type;

	template<class list>
	using length = identity<decltype(length_impl(list{}))>;

	struct test
	{
		using type = length<List<char, int>>;
	};
}
int main() {
	using namespace minibug;
	std::cout << typeid(test::type::type::type).name();
}

実行結果は以下のようになった

?AVtest:type:type:{ctor}:

???
一般に"{ctor}"という文字が型名を出力してる時に出てくることはない
例えばhogeというクラスを作れば"hoge"となるし
この場合であれば"std::integral_constant"とか出力されるのが妥当であろう
{ctor}とはどう考えてもコンパイラ内部で用いられてるコンストラクタを表す名前である
当然typeidで出てくることは一般的にない。hoge::hoge()だって"hoge"と出力される

いったいどういう経緯でこれが表に出てきてしまったのかは不明だが、この型は間違いなく腐っている