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

C++雑記

受け取ったタイプリストに対し適当な数字を被らないように返す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}の文字が出てきた

C++雑記 VS2013

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

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"と出力される

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

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