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に幻想を抱くな」という呟きは肝に銘じておこうと思う

Boost.mpl11を読んだ

C++

ldionne/mpl11 · GitHub

自分の大雑把な理解。間違ってたら指摘してもらいたい

mpl11は基本的に遅延評価である。ゆえに極力計算しない

Boxed typesとは多くのメタ関数やtype_wrap などT::typeとできる型のことである

mpl11のメタ関数は基本的にboxed typeを引数に要求する
遅延評価のため、また記法の簡易化のためである

using F=Metafunc<Box>;//このタイミングではまだなにも評価されていない
using a=F::type;//このタイミングでBox::typeを呼び出し、遅延評価される

これはListでも例外ではない。List::typeは自身の型を返す

List<int>::type;//==List<int>

というのは

F<Box>type;
F<List<char,int>>::type;

この二つをList版Box版と作り分けるのはよくない
ゆえにListはboxed typesであり、自身の型を返す

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

Lifted metafunctions

T::apply<...>

と出来る型Tのことである
mpl11では直接従来のメタ関数、つまりテンプレートテンプレートパラメータを扱わない
メタ関数もタイプリスト等mpl11の恩恵を受けることができる
関数オブジェクトのようなものである

ちなみにこれもboxed typesであり自身の型を返す



type class

C++的なclassとは関係ない。Haskellの型クラスのことである
C++風にいうとtraitとかコンセプトとかそんな感じ

例えばC++11なタイプリストとC++03時代のModernC++Designに載ってるタイプリストがあるとして、この二つでは当然先頭の要素を返す関数headの実装は異なる

template<class...T>
struct List;//C++11

template<class Head,class Tail>
struct cons;//c++03

これをtraitsを使って実装するのがtype classである

headを実装する型はhead_implのように実装する形名は*_implで統一するらしい




mpl_datatypeについて
実装とかで使う

mpl時代のIteratorについて
つらいのでやめた


monoid ,Functor, Monadoについて
型クラスである。要するにtraitsである。恐れることはない
例えばMaybe(boost::optional的なもの)はFunctorであり、Monadoである
functorはfmapを定義する
fmapはfunctorと関数を取る関数であり
fmapはmaybeであればmaybeがnothing(無効値)であればnothingを
有効値であれば関数を適用して返す
モナドはそれを連鎖できるようにした感じ

私がvisitorパターンが嫌いな理由

C++雑記

私には昔から、GOFのデザインパターンというものを学習したときからどうにも『そり』が合わないデザインパターンがあった
visitorパターンである

別に理解できなかったわけではない。使えないわけでもない。実際何度か使う場面もあった
だが、思いだすたび、必要になるたび、私は考えるのだ
「こいつは何かが腐っている!!」

先日、ついに啓示を得た。オラクルだ。
そして私はついに、visitorパターンが嫌いな理由を理解した。理解してしまった

神は私の耳元でこうささやいた
「お前はvisitorパターンの名前が一番嫌いなんだよ」


visitorパターンのギミックはこうだ
１：accepterさんは仮想メンバ関数でvisitorパターンを受け入れる
２：visitorさんは、*thisを受け取る。この時*thisは仮想メンバ関数のものなので派生クラス型になる
３：適切な関数が呼ばれる

という具合だ。ふむ、visitorパターンはいいパターンだ。結婚したい

しかし、私は気づいてしまった。ここで注目されるべきはAcceptさんの努力であり、安全に行われたダウンキャスト的効果である
少なくとも私はそう考えている。注目すべきはVisitorではない

私がそう考えるに至ったコードは以下のようなものだ

apply(a, make_overload([](SubA){}, [](SubB){}));

Visitorクラスは滅びた。しかしそれでもacceptは必要だ。ゆえに本当に必要なのはAccepterの方だ
故にAccepterさんの功績を讃えAccepterパターンと呼んで差し上げるのが少なくともVisitorより適切であると強く感じるのだ

ちなみにこのコードはvariantによって実装されている

C++11なvariantを大雑把に実装した

C++

variant test
variant
C++11仕様だから２０個以上の要素が詰め込めるよ!!COOLCATって感じだ
コンストラクタとデストラクタ、あとapplyだけ実装してある
以下にget関数の簡易な実装を示す

template<class T>
struct Get
{
	T operator()(const T&x)const
	{
		return x;
	}
	template<class U>
	T operator()(U&x)const
	{
		throw "F**K!!";
		return *(T*)nullptr;
	}
};
int main()
{
	using v = variant<char, std::string, int>;
	const auto x = v{ std::string("ABC") };
	std::cout << variant_apply<std::string>(Get<std::string>{}, x );
}

variant_applyはどんな数でも引数にとれる
こういうことも可能

//int variant variant double
variant_apply<std::string>(Func{}, 0, x, y ,3.14);

variant型を見つけ出し勝手に内部でwhichしてどうこうする

applyのコンパイル時計算量はO(N0*N1*...*Nn)≒O(N^n)だけどまぁ諦めろ

VS使いだけどwandboxでconstexpr二分木fold関数作った

C++雑記

グィスト
constexpr binary fold

実際に(静的に)実行したものはこちら
wandbox
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

二分木foldとは文字通り二分木で畳み込み関数である
binary_fold(plus{},1,2,3,4,5)は以下のように解決される

((1 + 2) + (3  + (4 + 5)))

foldlやfoldrに比べて再起深度を抑える働きがある
メタプロをしていてこの関数(のTMP版)がよく働くのでなんとなくconstexpr版も作ってみた
ちなみに私のコンパイラはVSなので動かない
動くかもしれないがsproutはVSサポートしてないので試す気もない

tuple操作ライブラリ「tupleple」

C++

ギッハッハブ
Fuyutsubaki/tupleple · GitHub

タプルプルプルタプルプル
ご意見もらえると喜びます

できること一覧

  • at

N番目の要素にアクセスする

  • apply

タプルに関数を適用する

view

おおむね元要素へのアクセスのインデックスを架け替えてるだけである
基本的に遅延評価で、要素にアクセスできて、ムーブできる


  • cat

繋げる

using namespace tupleple;
auto a = std::make_tuple(1, 2);
auto b = std::make_tuple(std::make_unique<int>(42), 'B');
auto c = std::make_tuple(std::string(":-)"), std::string(":-|"));
auto p = view::cat(a, std::move(b), c) | at<2>();//unique_ptr<int>(42)
  • take / drop

先頭N個を拾ったり落としたりする

auto tuple = std::make_tuple(1, std::make_unique<int>(2), 3);
auto x = std::move(tuple) | view::drop<1>();
auto i = at<0>(std::move(x));//unique_ptr<int>(2)
  • filter

条件に合うものだけを残す

auto r = std::make_tuple(false, "ABC", 3.14, 42);
auto c = r | view::filter_if<std::is_integral>();
std::cout << (c | at<1>());
  • map

各要素に関数を適用する

auto r = std::make_tuple(3.5, 1, 3.14, 1.414);
auto c = r | view::map([](double d){return d * 2; });
auto d = c | at<2>();//6.28
  • reverse

順序を逆転させる

auto x = std::make_tuple(1, 2, 3, 4) | view::reverse() | at<0>();
  • zip

複数のタプルをくっつける

auto t1 = std::make_tuple(1, 2, 3);
auto t2 = std::make_tuple('A', 'B', 'C');
auto t3 = std::make_tuple(std::make_unique<int>(42), true, false);

auto result = tupleple::view::zip(t1, t2, std::move(t3));
auto c1 = std::move(result) | at<0>();
auto r = std::move(c1) | at<2>();	//unique_ptr 42

algorithm

  • binary_fold

二分木畳み込み。右でも左でもない

struct plus
{
	template<class L,class R>
	auto operator()(L l,R r)const
	->decltype(l+r)
	{
	return l+r;
	}
};

int main()
{
	using namespace tupleple;
	auto t = std::make_tuple(1, 1.4f, 31.4, 18L);
	auto x = algorithm::binary_fold(t, plus());
}
  • for_each

全要素をなめる。順序が乱れない

type_list

タイプリスト処理。タプルとタイプリストは切っても切り離せない

utility

いろいろ