Yoh2さんのトモダチの日記、みんなの日記も見てね。 スラッシュドットのストーリーを選ぶための補助をお願いします。
先日の日記にて、D言語で不動点コンビネータを書いてみたら分かりにくくなったと述べたが、実はこれだけで実現できることに気付いた。
R delegate(TS) fix(R, TS...)(R delegate(R delegate(TS), TS) f)
{
return delegate(TS xs){ return f(fix(f), xs); };
}
ラムダ式をサポートしている版ならこう。
R delegate(TS) fix(R, TS...)(R delegate(R delegate(TS), TS) f)
{
return (TS xs) => f(fix(f), xs);
}
あらやだ分かり易い。
前回の日記のコードはYコンビネータを実装したものだったが、そんなことしなくても、単純に不動点の定義を書き下すだけで済んでしまうわけで。
あ、でも、無名関数の再帰を実現するコードで自らの名前を使ってしまう (fixの定義中でfixを使う) のは反則気味かな？
clang-3.0にて。
// hoge.c
#include <stdio.h>
void func(void)
{
func();
}
int main(void)
{
func();
puts("The code clang generates is so fast.");
return 0;
}
ビルド ＆ 実行。
$ clang -O2 hoge.c
$ ./a.out
The code clang generates is so fast.
わー。すごくはやーい。むげんさいきよびだしをいっしゅんでぬけたぞー……？
[2012-02-06 23:20 誤字訂正]
暇潰しネタ。
関数型言語の世界では、計算機論の基礎のひとつ、不動点コンビネータの実装が頭の体操のための題材になることが多い。
一方、手続型言語ではどうかというと、この関数の実装を行うには、関数を動的に生成して返さなければならないため、古い言語では実装することができなかった。(アーキテクチャ固有のハックをすれば別だけど)
しかし、ラムダ式だのデリゲートだのが使える最近の言語なら手続型でも実装できるはず。
手続型言語で不動点コンビネータを実装すれば、慣れている分、分かりやすかったりしないかな？ と思い、D言語で書いてみた。多引数対応。
R delegate(TS) fix(R, TS...)(R delegate(R delegate(TS), TS) f)
{
class Wrapper(F)
{
public F delegate(Wrapper!(F)) func;
public this(F delegate(Wrapper!(F)) func)
{
this.func = func;
}
}
return delegate R delegate(TS)(Wrapper!(R delegate(TS)) g)
{
return delegate R(TS xs)
{
return f(g.func(g), xs);
};
}(new Wrapper!(R delegate(TS))(delegate R delegate(TS)(Wrapper!(R delegate(TS)) g)
{
return delegate R(TS xs)
{
return f(g.func(g), xs);
};
}));
}
うん。分かりづらい。これならむしろ関数型言語で素直に書いた方が分かりやすいかもorz
せっかくなので使い方の例をいくつか。
// 階乗計算
auto fact = fix(delegate int(int delegate(int) f, int n)
{
if(n <= 0)
{
return 1;
}
else
{
return n * f(n - 1);
}
});
writefln("%s", fact(7)); // 5040
// int配列からdouble配列への写像
auto map = fix(delegate double[](double[] delegate(double delegate(int), int[]) f, double delegate(int) trans, int[] a)
{
if(a.length == 0)
{
return [];
}
else
{
return trans(a[0]) ~ f(trans, a[1 .. $]);
}
});
// 配列の各要素を3で割ったものを得る
writefln("[%s]", map(delegate double(int x){ return x / 3.0; }, [1, 3, 5, 7, 9, 11])); // [0.333333 1 1.66667 2.33333 3 3.66667]
// たらい回し関数 （竹内関数)
auto tak = fix(delegate int(int delegate(int, int, int) f, int x, int y, int z)
{
if(x <= y)
{
return y;
}
else
{
return f(f(x - 1, y, z), f(y - 1, z, x), f(z - 1, x, y));
}
});
writefln("%s", tak(10, 5, 0)); // 10
# 実用性？ 知らん。
先日の日記で、C11を使って擬似的な関数オーバーロードを実現しようとしたが、0引数の場合にうまくいかないということを書いた。
その後GCCの拡張機能を使うと実現できることに気付いたのでここに書く。
なお、C11のみで実現する方法はまだ思い付いていない。
さて、ここで使用した拡張機能は何かというと、可変長引数マクロで、コンマの後に空の__VA_ARGS__を続けた時に__VA_ARGS__の直前のコンマを削除できるという機能。
#define MACRO(...) ほげほげ , ## __VA_ARGS__
のように、コンマと__VA_ARGS__の間に ## を入れると、「MACRO()」と書いた時に__VA_ARGS__直前のコンマが消えて、「ほげほげ」と展開される。
MACRO(a)と書いた場合はコンマが残って「ほげほげ , a」と展開される。
この拡張機能はclang-3.0でも使える。
これを使用して、以前の日記のコードを以下のように変更した。
#include <stdio.h>
// 以下の4つの関数をfunc()マクロで呼び分けたい。
void func0(void)
{
puts("func0()");
}
void func1_i(int x)
{
printf("func1_i(%d)\n", x);
}
void func1_d(double x)
{
printf("func1_d(%f)\n", x);
}
void func2_ii(int x, int y)
{
printf("func2_ii(%d, %d)\n", x, y);
}
// 引数が少ない場合の穴埋め用ダミー。
struct dummy; // 前回の日記では中身も定義していたが不要なことに気付いたので削除。
// 引数があればその引数、なければ (struct dummy *)0 と評価される式を生成。
#define arg1_or_dummy(...) ((struct dummy *)0, ## __VA_ARGS__)
#define func(...) (func_selector_1st(__VA_ARGS__, (struct dummy *)0)(__VA_ARGS__))
#define func_selector_1st(arg1, ...) \
func_selector_2nd(arg1_or_dummy(arg1), __VA_ARGS__)
#define func_selector_2nd(arg1, arg2, ...) \
_Generic((arg1), \
struct dummy *: func0, /* ひとつめがない → 0引数関数 */ \
int : _Generic((arg2), /* ひとつめの型がintで... */ \
struct dummy *: func1_i, /* ふたつめがない → 引数の型が(int) */\
int : func2_ii), /* ふたつめの型がint → 引数の型が(int, int) */ \
double : func1_d) /* ひとつめの型がdouble → 引数の型が(double) */
int main()
{
func();
func(1);
func(1.0);
func(1, 2);
return 0;
}
ここのキモとなるのが、新たに定義したマクロarg1_or_dummy。
可変長マクロとなっているが、0個か1個の引数を取ることを想定しており、「arg1_or_dummy()」と0引数にすると「((struct dummy *)0)」と展開される。
一方、「arg1_or_dummy(exp)」と引数が付くと「((struct dummy *)0, exp)」と展開され、コンマ演算子の定義により、((struct dummy *)0が捨てられて)「exp」と等価になる。
最初の引数についてこれを呼び出してやることによって、0引数のfunc呼び出しについてもめでたく正しい展開がなされて疑似オーバーロードが実現できるという寸法。
今回もclang-3.0で確認しました。
ところで、前回書き忘れたけど、clang-3.0はまだC11対応途中 (そもそもC11が正式に決まる前にリリースされたもの。オプションも-std=c1xとなっている) なので、未実装だったり規格と動作が異なったりする可能性はありますのでご注意を。_Generic周りについては規格通りだと思いますが。
[2012-01-18 13:15追記: GCC拡張機能(clangでも使える)を利用して実現することができました。続・C11で疑似関数オーバーロード (GCC拡張機能使用)を参照して下さい。]
[C/C++規格: 11] C11の新機能 その2 -- 型ジェネリック式から話題を一部引っ越してきました。
C11で型ジェネリックが使えるようになったため、1引数の関数については擬似的に関数オーバーロードを実現するマクロを書けるようになった。
では引数の数が異なるものについてのオーバーロードはというと、_Genericのみで直接行うことはできない。でも、可変長引数マクロと組み合わせればできそうだと思ってコードを考えてみた。
ところが、どうにもうまくいかない。
なお、動作確認にはclang-3.0を使用した。
まず、最初に思い付いたのが以下のコード。
#include <stdio.h>
// 以下の4つの関数をfunc()マクロで呼び分けたい。
void func0(void)
{
puts("func0()");
}
void func1_i(int x)
{
printf("func1_i(%d)\n", x);
}
void func1_d(double x)
{
printf("func1_d(%f)\n", x);
}
void func2_ii(int x, int y)
{
printf("func2_ii(%d, %d)\n", x, y);
}
// 引数が少ない場合の穴埋め用ダミー。
struct dummy{int n;};
#define func(...) (func_selector(__VA_ARGS__, (struct dummy *)0, (struct dummy *)0)(__VA_ARGS__))
#define func_selector(arg1, arg2, ...) \
_Generic((arg1), \
struct dummy: func0, /* ひとつめがない → 0引数関数 */ \
int : _Generic((arg2), /* ひとつめの型がintで... */ \
struct dummy *: func1_i, /* ふたつめがない → 引数の型が(int) */\
int : func2_ii), /* ふたつめの型がint → 引数の型が(int, int) */ \
double : func1_d) /* ひとつめの型がdouble → 引数の型が(double) */
int main()
{
func(); // func_selectorを展開すると _Generic((), ……)となるのでエラー。
func(1);
func(1.0);
func(1, 2);
return 0;
}
この例では、引数の数が1個のものと2個のものではうまく動作するが、引数が0個のものは、「func()」→「func_selector(, (struct dummy *)0, (struct dummy *)0)」→「_Generic((), ……)」となり、「()」なんて式は書けないためコンパイルエラーになってしまう。
ではもう一段マクロを挟んで、0引数関数を特別扱いしたらいいんじゃないかと考えたのが次の例。
マクロ定義部以外は同じなので、マクロ定義部のみ記述。
// 0引数関数かそれ以外かの判別を行う
#define func_selector_1st(...) \
_Generic((int(*)[sizeof(#__VA_ARGS__)])0, /* #__VA_ARGS__ は引数なしなら空文字列 (sizeof(...) == 1) になる */\
int(*)[1] : func0(), /* 引数なし */\
default: func_selector_2nd(__VA_ARGS__, (struct dummy *)0)(__VA_ARGS__)) /* 引数あり */
// 1引数以上の関数の判別
#define func_selector_2nd(arg1, arg2, ...) \
_Generic((arg1), \
int : _Generic((arg2), /* ひとつめの型がintで... */ \
struct dummy *: func1_i, /* ふたつめがない → 引数の型が(int) */\
int : func2_ii), /* ふたつめの型がint → 引数の型が(int, int) */ \
double : func1_d) /* ひとつめの型がdouble → 引数の型が(double) */
func_selector_1st()で0引数とそれ以外を分けるように変更。func_selector_1st()の_Genericで選ばれなかった方は評価されないのでこれで解決、なんて思っていたが、「評価されない」と「翻訳の対象にならない」を混同していたというオチ。
結局、0引数の場合でもfunc_selector_2nd(……)が展開されてしまうため、「_Generic((), ……)」が出現するのは変わらずやっぱりコンパイルエラー。
さて、こうなるともっと発想を変えないといけなそうだけど、さてどうしたらいいものか。
[2012-01-15 10:50変更: 疑似オーバーロードの話が大きくなりすぎたので独立したエントリーにしました。]
スレッド周りと並び、一番興味を持ってたものなので最初に紹介。
# スレッド周りは重いから人に説明できるようになるまで苦労しそう。
■ 型ジェネリック式 (type-generic expression)
書式:
_Generic(制御式, 型名1: 式1, 型名2: 式2……)
※ 型名と式のペア (generic-association) は一組以上必要。
※ 型名は「default」(意味は後述)もあり。
※ 制御式、式nにコンマを含めた式を入れたい時は括弧で囲む。
意味:
直感的には型で分岐するswitch。
結果は制御式に適合する型を持つgeneric-associationの式の値になる。
defaultは他に適合する型がない時に選ばれる。
結果は左辺値やvoidや関数でもOK。つまりこんなこともできる。
int char_count, int_count, double_count, ocher_count;
...
// xの型に対応したカウンタ値をひとつ増やす。
_Generic(x, char: char_count, int: int_count, double: double_count, default: other_count)++;
また、制御式や選ばれなかったgeneric-associationの式は評価されない。
解説:
単体で使っても長々としてうれしくないが、マクロに使うと本領を発揮する。
例えば、C99でC++のオーバーロードのような動作を実現する<tgmath.h>のsinマクロは、C99の範囲だけでは処理系独自の実装を行わないと実現できなかったが、C11では似たようなマクロgeneric_sinを以下の様に定義できる。
(C11の<tgmath.h>のsinマクロの要件を完全に満たしているかどうかは未検証)
#define generic_sin(x) \
(_Generic((x), \
long double: sinl, \
double: sin, \
float: sinf, \
long double _Complex: csinl, \
double _Complex: csin, \
float _Complex: csinf, \
default: sin)(x))
雑感:
基本的な使われ方は解説で書いたような複数の関数の選択なんだろうけど (規格書に書かれている例も関数の選択だった)、他にも面白いことがいろいろとできそう。意味の所に書いた、型によるカウンタの選択とか。
あと、関数が選択できると言っても、これだけではC++のオーバーロードのように、引数の数が違うものまでは選択できない。でも可変長引数マクロと組み合わせればできるかな？えらく面倒になりそうだけど。
[2012-01-15 10:50変更: ここから]
……ということを考えてみたけど、今のところうまくいってない。0引数の場合をどうするかが問題に。
元々はこのエントリーに書いていたけど、大きくなったので引っ越しました。
C11で疑似関数オーバーロード (できてません)を参照。
[2012-01-15 10:50変更: ここまで]
[2012-01-15 11:45追記: リスト項目に対応する日記へのリンクを付けました。これ以降は追記通知なしにリンクを追加していく予定]
そのうちC11の新機能をまとめたサイトとかできそうだけど、自分の勉強も兼ねてつらつらとここで書いてみる。
誤訳珍訳どんとこい。とはいえ、誤解している部分に対してのツッコミは歓迎。
その1と銘打ったけど、続けるかどうかは気分次第。
■ 新機能概要
基本的にISO/IEC 9899:2011 Foreword. 6段落目のリストの訳。適当に意訳したり端折ったり補足してたりします。
次からは上記の順ではなく、説明しやすかったり興味を持ったりした順に書いていくつもり。
# ほぼ自分のmixi日記からの転載。
DENON AH-D2000を買った記念に手持ちのオーバーヘッド型ヘッドホンについてまとめてレビューを書いてみた。
単なる自己満足なので正確性は期待しないで。 プラシーボ効果やら今日の気分やら諸々に支配されていると思うので。
あと、「長所」、「短所」と書いているのは、より正確には「俺が気に入っている」、「俺の好みじゃない」ということ。
毎回「俺～」と書いてると煩いので長所、短所、という表現にしたけど主観入りまくりなので注意。
もひとつ。メインヘッドホンがMDR-CD900ST → HD280Proという遍歴を辿っており、モニター用ヘッドホンの音に慣れてしまったのか、モニター用ヘッドホンについてよく言われる聴き疲れするといったことが自分には感じられない。なのでその辺は評価の対象外。
■ Sennheiser HD280Pro
一番のお気に入りで個人的リファレンス機種。
そのため、他の感想は基本的にこれと較べた場合の相対評価。
とはいえ、完全にフラットではなくカマボコな音であるとは思ってます。
・長所
周波数特性に関してバランスがよい……て、これを標準のバランスだと思っているのでトートロジーでしかないな。
分解能が高く、各パートの音を聞き分けることができる。(モニター用だしね)。
苦手なジャンルがない万能選手。
・短所:
音が軽くてそっけない。
音をみんな拾ってしまうため、ノイズが多い音源では悲惨なことに。
あるゲームの効果音やBGMにことごとく大きめのホワイトノイズが乗っていて残念な気持になったことも。
とはいえ、ノイズ探しがモニター用ヘッドホンの本来の仕事のひとつ。これができなきゃモニター用と言えない。ただ、音楽観賞用としてはマイナスだよね。
■ Sennheiser HD650
やや得手不得手があるものの、ハマるととんでもなくよい音を鳴らしてくれる。この中で一番高いだけある(ぇ
ちょっと低音寄りかな？
・長所:
音場が非常に広く感じられる。残響が付加されるので、音場が広くても、個々のパートがバラバラに鳴っているといった感じはしない。
弦楽器(撥弦、擦弦、打弦問わず)の音が非常に綺麗。
・短所:
テクノなど、音のメリハリが重要な音楽では、付加される残響が裏目に出て締まりが悪くなる。
■ Sony MDR-CD900ST
音制作の業界では長い間標準的な機種らしい。今もかな？
これまたモニター用なので、長所、短所共にHD280Proとほぼ共通。以下異なる所のみ記述。
・長所:
ディストーションギター等の粗めの音が力強い。
・短所:
音場が極端に狭い。
■ DENON AH-D2000
強いて言えば低音寄りな気もしないでもないけどかなりフラット。
AH-D2000が低音寄りなのではなく、HD280Proの低音が弱いだけかも。
買ったばかりなので、エージングで傾向が変わる可能性あり。
・長所:
周波数特性、パート間のまとまり等、とにかくバランスがよい。
パーカッションの音が綺麗。
苦手なジャンルがない万能選手。
・短所:
音の粗がほとんど無く、力強さが感じられない。
その割になぜかホワイトノイズを盛大に拾う。
こんな感じかな。AH-D2000、かなりいい感じです。
他人に伝わるかイマイチ分からない表現はできるだけ避けようとしたけど結局使ってしまった。「力強さ」とか。胡散臭さが増大するというのに。感覚を伝えるって難しい。
# まあ、これは胡散臭くてもいいや、と割り切ってはいるけど。どうせ正確性に自信ないし。
[2012-01-06追記: ここから]
ここで書いたコードの、ロック用の変数をふたつ用意するという例、どこかで見た記憶があったと思ったらBINARY HACKS #94 にあった。
というわけで、参考文献としてO'REILLY BINARY HACKSを挙げておきます。
[2012-01-06追記: ここまで]
C11にメモリフェンス関連の記述が加わったことを機に、ロード/ストア命令の追い越しが発生することで期待通りに動かないプログラム例を考えてみた。が、これでいいんだろうか？
メモリオーダリングは関係ないレース条件があったりしないかな？
一応自環境では、メモリフェンスなし→おかしな挙動、メモリフェンスあり→正常な挙動(に見える) となったけど。
また、gccに-Sオプションを追加して出力されたアセンブリソースを見て、コンパイラレベルでは順序の入れ替えが起きてないことを確認したつもり。
■ 自環境:
OS: Linux (kernel 2.6.37-gentoo-r4 (2.6.37.4相当))
CPU: Opteron 2427
コンパイラ: gcc-4.5.3
オプション: -Wall -O3 -march=native -mtune=native -lpthread
[2012-01-06 02:38追記] 最適化オプションなしの方がおかしな挙動が派手に出るっぽい。
■ 使い方:
引数なしでプログラムを実行 -- メモリフェンス命令を実行しない。
引数あり(何でもいい)でプログラムを実行 -- 要所要所でメモリフェンス命令を実行。
do_something()内のprintf()は実行されたら何か変なことになっている証拠。
■ ソース
※ __sync_synchronize() 関数はメモリフェンス命令を実行するgcc組み込みの関数。
# 長いなぁ
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <signal.h>
#include <stdint.h>
#include <inttypes.h>
int use_sync = 0;
volatile int locks[2] = {0, 0};
volatile unsigned long long num_spins[2] = {0, 0};
volatile unsigned long long num_processes[2] = {0, 0};
volatile int obj = -1;
volatile int done = 0;
/*
* ふたつのスレッドがそれぞれ引数0と1でこの関数を繰り返し呼び続ける。
*/
static void do_something(intptr_t id)
{
int tmp;
unsigned long long local_spins = 0;
/*
* 1. locks[自ID]を1にしてからlocks[他ID]を見る。
* 2. locks[他ID]が0なら次の処理へ進む。(ロード/ストア命令の追い越しがなければ同時にひとつのスレッドしか条件を満たさないはず)
* 3. locks[他ID]が非ゼロならlocks[自ID]一瞬0にして再び1に。そして2に戻る。
*/
locks[id] = 1;
if(use_sync) __sync_synchronize();
while(locks[!id])
{
locks[id] = 0;
if(use_sync) __sync_synchronize();
local_spins++;
locks[id] = 1;
if(use_sync) __sync_synchronize();
}
/* (ロード/ストア命令の追い越しがなければ) 同時にひとつのスレッドしか実行しないはず -- ここから */
num_spins[id] += local_spins;
tmp = obj;
if(tmp != -1)
{
/* (ロード/ストア命令の追い越しがなければ) ここには来ないはず */
printf("thread[%"PRIdPTR"]: obj = %d, locks[0] = %u, locks[1] = %u, local_spins = %llu\n",
id, tmp, locks[0], locks[1], local_spins);
}
obj = id;
if(use_sync) __sync_synchronize();
obj = -1;
if(use_sync) __sync_synchronize();
num_processes[id]++;
locks[id] = 0;
if(use_sync) __sync_synchronize();
/* (ロード/ストア命令の追い越しがなければ) 同時にひとつのスレッドしか実行しないはず -- ここまで */
}
static void *thread_proc(void *arg)
{
intptr_t id = (intptr_t)arg;
printf("thread[%"PRIdPTR"]: start.\n", id);
while(!done)
{
do_something(id);
}
return NULL;
}
/*
* シグナル処理スレッド。
*
* SIGUSR1: 経過確認用に各種カウンタ類を表示。あんまり正確じゃないのは御愛嬌。
* SIGTERM, SIGINT: プログラム終了。
*/
static void *sigthread_proc(void *arg)
{
sigset_t set;
sigemptyset(&set);
sigaddset(&set, SIGUSR1);
sigaddset(&set, SIGTERM);
sigaddset(&set, SIGINT);
for(;;)
{
int sig;
if(sigwait(&set, &sig) == 0)
{
int i;
switch(sig)
{
case SIGUSR1:
for(i = 0; i < 2; i++)
{
printf("locks[%d] = %d, num_spins[%d] = %lld, num_processes[%d] = %lld\n",
i, locks[i], i, num_spins[i], i, num_processes[i]);
}
puts("");
break;
case SIGTERM:
case SIGINT:
done = 1;
break;
default:
break;
}
}
}
return NULL;
}
int main(int argc, char *argv[])
{
pthread_t sigth;
pthread_t ths[2];
intptr_t i;
sigset_t set;
/*
* 何か引数があったらuse_sync = 1 (メモリフェンス命令を使う),
* 引数がなければuse_sync = 0 (メモリフェンス命令を使わない)
*/
use_sync = (argc > 1);
sigemptyset(&set);
sigaddset(&set, SIGUSR1);
sigaddset(&set, SIGTERM);
sigaddset(&set, SIGINT);
pthread_sigmask(SIG_BLOCK, &set, NULL);
pthread_create(&sigth, NULL, &sigthread_proc, NULL);
pthread_detach(sigth);
for(i = 0; i < 2; i++)
{
pthread_create(&ths[i], NULL, &thread_proc, (void *)i);
}
for(i = 0; i < 2; i++)
{
pthread_join(ths[i], NULL);
}
puts("done.");
return 0;
}
しかし、C11での追加機能が使えるようになるのは何時になるんだろう。
明けましておめでとうございます。
今年もよろしくお願いします。
今年の正月は去年と違ってのんびりモード。ふぅ。
去年に引き続きモナー神社に参拝してからおみくじ。
【大吉】 (No.54617) モナー神社
願事 : 思いの儘となる しかしやり過ぎては悪し
待人 : 思う日までに来るべし
失物 : 高き処にあり
旅立 : 行きて吉
商売 : 物の価下がる買うは悪し
学問 : 過信せず行えば成果現る
争事 : 人に頼るは宜しからず
転居 : 騒がずして吉
病気 : 危き様なるも必ず全快す
縁談 : 良縁あり 人に頼んで進めよ
ついでに診断メーカー。
「yoh2」の2012年を漢字二文字で表すと 【 自 滅 】 http://shindanmaker.com/179756
実は大晦日にもやって、そのときは【 絶 望 】だったから見なかったことにしてたんだが (- -;;
あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー