Bjarne 的なるもの

なんとなく first, last だのの algorithm 関数のインターフェースが好きになれなくて、せいぜい vector<T> をベター配列ぐらいでしか使ったことなかったけれど、今頃になって STL で真面目に遊ぶ。 C++0x? Boost? 何それうまいの?

For each 的なるものに ruby とかでブロック (ruby の用語だとイテレータ?) を渡すのに比べて、関数オブジェクトとかはクラスを宣言しなければいけないしめんどくさいなあ的なるものかと思ってたけど、その分、抽象的な処理が何か考える契機にはなるのかな。 ∀x/∃x の関数オブジェクト・ラッパーをさんざ設計してみた後で、それじゃ短絡評価されないじゃんということにやっと気づく連休初日。 なるほど find_if() とか adjacent_find() を使えと。 0x だと無名のラムダ関数的なるものを関数定義中に書けるようになるとか…。 これ以上文法を複雑にしないで。

ファンクショナル (汎関数) はまだしも関数オブジェクトをファンクター (関手) とか呼んでるのがあるのは何か違う気がする。 そういう文脈があるのだろうか。 むしろ for_each() とかの方がファンクター的なるものっぽいのだけれど。 for_each(first, last, f) の代わりに g = for_each(f); g(first, last); とかだともっといいか。 まったく需要なさそうだ。

コンテナの実体の代わりにインデックスをソートしてみるとかに使えそうな関数オブジェクト・ラッパー↓。 長たらしい。 筋は通ってるけど多重継承で同じクラスを継承する極悪っぷりなので、親切なコンパイラのウォーニングは無視する。 なんかこれも別の手段がありそうだ。

#include <functional>
#include <iterator>

// 単項関数ラッパー基底クラス
// 他のラッパー・クラスの基底となり、ラップされる関数オブジェクトを保持する
//  関数オブジェクトの呼び出し  (*this)(-): A → R
// テンプレート引数
//  A   呼び出しと F の引数型               要件 なし
//  R   呼び出しと F の返り値型 (void 可)   要件 なし
//  F   ラップされる関数の型                要件 -(-): F×A → R
//
template<typename A, typename R, typename F>
class  unary_function_wrapper_t  : public std::unary_function<A, R>
    {
    private:
        F  _wrapped_function;   // ラップされる非定数関数: 内部状態を持ち呼び出しで更新するかもしれない
        static R  _constraint_F(F f, A a)  throw ()  { return f(a); }
    public:
        explicit  unary_function_wrapper_t(F wrapped_function = F())  throw ()
            : _wrapped_function(wrapped_function) { R (* c)(F, A) = _constraint_F; }
        F const&  wrapped_function()  const throw ()  { return _wrapped_function; }
        R  operator()(A a)  { return _wrapped_function(a); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って演算を行う
// コンストラクタの引数で A 型シーケンスのポインタまたはイテレータを与え、
// アルゴリズム関数にはその順番を示す I 型インデックスを与える
// 演算はシーケンス上の A 型の値に対して行われるが、
// アルゴリズム関数の操作はインデックスに対して行われる
//  関数オブジェクトの呼び出し  (*this)(-): I → R
// テンプレート引数
//  Aa  配列 (コンテナ) の先頭ポインタ (イテレータ) 要件 -[-]: Aa×I → A
//  R   呼び出しと F の返り値型 (void 可)           要件 なし
//  F   ラップされる関数 (オブジェクト) 型          要件 -(-): F×A → R (基底クラスより)
// 非明示型
//  A   F の引数型                                  要件 なし
//  I   呼び出しの引数型でインデックスとなる型      要件 なし
//
template<typename Aa, typename R, typename F>
class  unary_function_deindexer_t
    : public unary_function_wrapper_t<typename std::iterator_traits<Aa>::value_type, R, F>,
      public std::unary_function<typename std::iterator_traits<Aa>::difference_type, R> // 意図した多重継承
    {
    private:
        typedef typename std::iterator_traits<Aa>::value_type       A;
        typedef typename std::iterator_traits<Aa>::difference_type  I;
        Aa  _values_a;  // A 型配列 (コンテナ) への非定数ポインタ (イテレータ): このクラスの代入を可能にする
        static A  _constraint_Aa(Aa aa, I i)  throw ()  { return aa[i]; }
    public:
        explicit  unary_function_deindexer_t(Aa values_a, F wrapped_function = F())  throw ()
            : unary_function_wrapper_t(wrapped_function), _values_a(values_a)  { A (* c)(Aa, I) = _constraint_Aa; }
        Aa  values_a()  const throw ()  { return _values_a; }
        R  operator()(I i)  { return unary_function_wrapper_t::operator()(_values_a[i]); }
    };

// 2 項関数ラッパー基底クラス
//  関数オブジェクトの呼び出し  (*this)(-,-): A1×A2 → R
// テンプレート引数
//  A1  呼び出しと F の第 1 引数型          要件 なし
//  A2  呼び出しと F の第 2 引数型          要件 なし
//  R   呼び出しと F の返り値型 (void 可)   要件 なし
//  F   ラップされる関数の型                要件 -(-,-): F×A1×A2 → R
//
template<typename A1, typename A2, typename R, typename F>
class  binary_function_wrapper_t
    : public std::binary_function<A1, A2, R>
    {
    private:
        F  _wrapped_function;
        static R  _constraint_F(F f, A1 a1, A2 a2)  throw ()  { return f(a1, a2); }
    public:
        explicit  binary_function_wrapper_t(F wrapped_function = F())  throw ()
            : _wrapped_function(wrapped_function) { R (* c)(F, A1, A2) = _constraint_F; }
        F const&  wrapped_function()  const throw ()  { return _wrapped_function; }
        R  operator()(A1 a1, A2 a2)  { return _wrapped_function(a1, a2); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って演算を行う
//  関数オブジェクトの呼び出し  (*this)(-,-): I×I → R
// テンプレート引数
//  Aa  配列の先頭ポインタ                      要件 -[-]: Aa×I → A
//  R   呼び出しと F の返り値型 (void 可)       要件 なし
//  F   ラップされる関数 (オブジェクト) 型      要件 -(-): F×A×A → R (基底クラスより)
// 非明示型
//  A   F の引数型                              要件 なし
//  I   呼び出しの引数型でインデックスとなる型  要件 なし
//
template<typename Aa, typename R, typename F>
class  binary_function_deindexer_t
    : public binary_function_wrapper_t<typename std::iterator_traits<Aa>::value_type,
                                       typename std::iterator_traits<Aa>::value_type, R, F>,
      public std::binary_function<typename std::iterator_traits<Aa>::value_type,
                                  typename std::iterator_traits<Aa>::value_type, R> // 意図した多重継承
    {
    private:
        typedef typename std::iterator_traits<Aa>::value_type       A;
        typedef typename std::iterator_traits<Aa>::difference_type  I;
        Aa  _values1_a;
        Aa  _values2_a;
        static A  _constraint_Aa(Aa aa, I i)  throw ()  { return aa[i]; }
    public:
        explicit  binary_function_deindexer_t(Aa values_a, F wrapped_function = F())  throw ()
            : binary_function_wrapper_t(wrapped_function), _values1_a(values_a), _values2_a(values_a)
            { A (* c)(Aa, I) = _constraint_Aa; }
        explicit  binary_function_deindexer_t(Aa values1_a, Aa values2_a, F wrapped_function = F())  throw ()
            : binary_function_wrapper_t(wrapped_function), _values1_a(values1_a), _values2_a(values2_a)
            { A (* c)(Aa, I) = _constraint_Aa; }
        Aa  values1_a()  const throw ()  { return _values1_a; }
        Aa  values2_a()  const throw ()  { return _values2_a; }
        R  operator()(I i1, I i2)  { return binary_function_wrapper_t::operator()(_values1_a[i1], _values2_a[i2]); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って比較演算を行う
//  関数オブジェクトの呼び出し  (*this)(-,-): I×I → bool
// テンプレート引数
//  Aa  配列 (コンテナ) の先頭ポインタ (イテレータ) 要件 -[-]: Aa×I → A (基底クラスより)
//  F   ラップされる関数 (オブジェクト) 型          要件 -(-): F×A×A → bool (基底クラスより)
// 非明示型
//  A   F の引数型                                  要件 なし
//  I   呼び出しの引数型でインデックスとなる型      要件 なし
//
template<typename Aa, typename F>
class  comparator_deindexer_t
    : public binary_function_deindexer_t<Aa, bool, F>
    {
    public:
        explicit  comparator_deindexer_t(Aa values_a, F wrapped_comparator = F())  throw ()
            : binary_function_deindexer_t(values_a, wrapped_comparator) {}
        explicit  comparator_deindexer_t(Aa values1_a, Aa values2_a, F wrapped_comparator = F())  throw ()
            : binary_function_deindexer_t(values1_a, values2_a, wrapped_comparator) {}
    };

どういうときに使えそうかというと、例えば、うららかな春の陽気にさそわれて、ふと大量の数ベクトルを大きさの順にソートしたくなったとしよう。 ソートしたいのはベクトルなんだけど、比べたいのはその大きさ。 比較関数で比較の度にいちいち大きさを計算するのはばかばかしい。 そこで、大きさをあらかじめ計算した vector<double> を用意しておいて、0,1,2,...,n−1 に初期化したインデックス vector<size_t> も用意しておいて、比較関数は大きさの vector を参照させて、ソートはインデックスの vector に対して行う。 よくある手法だ (おそらく)。 STL でやると、大きさの代わりに絶対値の 2 乗をとる関数オブジェクトと、0,1,2,... を作るための関数オブジェクト、ついでに出力用関数オブジェクトを用意して：

#include <iostream>
#include <numeric>
#include <cstdlib>

template<typename Ka>
struct  sqabs_t  : public std::unary_function<Ka, typename Ka::value_type>
    {
        typedef typename Ka::value_type K;
        K  operator()(Ka const& ka)  { return std::inner_product(ka.begin(), ka.end(), ka.begin(), K()); }
    };

template<typename K, typename I = size_t>
class  counter_t  : public std::unary_function<K, I>
    {
    private:
        I  _count;
        static I  _constraint_I(I i)  throw ()  { return i ++; }
    public:
        explicit  counter_t(I initial_count = I())  throw ()  : _count(initial_count) { I (* c)(I) = _constraint_I; }
        I  count()  const throw ()  { return _count; }
        I  operator()(K const&)  throw ()  { return _count ++; }
    };

template<typename Ka>
struct  writer_t  : public std::unary_function<Ka, void>
    {
        typedef typename Ka::value_type K;
        void  operator()(Ka const& ka)  const
            {
                std::cout << "( ";
                std::copy(ka.begin(), ka.end(), std::ostream_iterator<K>(std::cout, " "));
                std::cout << ")\n";
            }
    };

そして、本体はこんな風になる：

#include <vector>

typedef double           Kt;
typedef std::vector<Kt>  Kat;
typedef std::vector<Kat> Kaat;
typedef size_t           It;
typedef std::vector<It>  Iat;

// ベクトルが入ったベクトルがあるとしよう
Kaat kaa;
for (size_t i = 0; i < 10; i ++) {
    Kat ka;
    ka.push_back(rand()); ka.push_back(rand()); ka.push_back(rand());
    kaa.push_back(ka);
}

//------

// 各ベクトルの絶対値の 2 乗のベクトルを用意する
Kat aa;  std::transform(kaa.begin(), kaa.end(), back_inserter(aa), sqabs_t<Kat>());

// インデックスを入れるベクトルを用意する
Iat ia;　std::transform(aa.begin(), aa.end(), back_inserter(ia), counter_t<Kt, It>());

// そしてソートする。比較は aa に対して行われ、ソートは ia に対して行う
std::sort(ia.begin(), ia.end(), comparator_deindexer_t<Kat::const_iterator, std::less<Kt> >(aa.begin()));

//------

// ソートされてるかチェック
Iat::iterator p = std::adjacent_find(ia.begin(), ia.end(), comparator_deindexer_t<Kat::const_iterator, std::greater<Kt> >(aa.begin()));
std::cout << ((p == ia.end())? "good job!" : "fiasco!") << std::endl;
// ソート順にもとのベクトルを出力。ia を順に参照し、kaa を出力する
std::for_each(ia.begin(), ia.end(), unary_function_deindexer_t<Kaat::const_iterator, void, writer_t<Kat> >(kaa.begin()));

good job!
( -0.188818 -0.44084 0.137486 )
( 0.364483 0.511704 0.443831 )
( -0.0494095 -0.75396 -0.264382 )
( -0.688894 0.00784326 0.464034 )
( -0.644215 0.634388 -0.0494705 )
( 0.643361 0.164098 -0.617298 )
( 0.810236 0.385784 -0.393902 )
( 0.366375 -0.693533 0.754509 )
( -0.146886 -0.859249 0.933226 )
( -0.705008 0.899167 -0.716849 )

ふふふ、二度と読みたくないコードがまた完成した。 Bjarne 的なのか、Stepanov 的なのか、単にわたし的なのか。

とうふの角

25 度だろうが 7 度だろうが春、つぼみつけすぎのクレマチス。

* * *

コーナー・キューブ、つまり 3 次元空間で x ≥ 0, y ≥ 0, z ≥ 0 みたいな無限に巨大なとうふの 1 つの角を想像する。 この角のあたりを斜めに包丁でスパッと切ると、切り方によっていろんな三角錐ができあがる。 その切片はいろんな形の、すべての、ただし鋭角な三角形。 鈍角はどこにいったのだろう。 切り口が鈍角になるには直方体じゃなく平たくつぶれたとうふじゃないとだめそうだ。 そんなものもはやとうふではない。

飽くまで直方体の無限に大きなとうふがプリズムみたいに透明だとして、切片と真っ直ぐ垂直に向き合うなら、向こう側の 3 つの辺と角が透けて見えるはずだ。 別に切片を下にしてまな板を真上から覗き込んでもいいのだけれど。 そうして見たときの、この角の位置は平面三角形でいうところの「垂心」になっている。 つまり角から切片に垂直に下ろした足もやっぱり垂心なのだ。 透けて見える辺は三角形の頂点から下ろした垂線のはずだ。 なかなか面白いと思ったが、とうふが直方体であることを考えると別にそんなに不思議じゃない。 ちなみに、三角形の「重」心は向こう側の 3 つの辺を共有する直方体の対角線と三角形が交わる点。 これも不思議じゃない。

今度は切片に垂直ではなくとうふの直方体の角の方から [(x, x, x) から] 切片の三角形の射影を眺めると、とうふの角は「フェルマー点」だ。 外心やオイラー線はわかるようでわからない。

さてこうなると鈍角三角形も見つけたい。 鈍角三角形だと垂心が三角形の外にある。 とうふの四面体をどんな風にみたらとうふの角が外にある三角形がありうるだろうかと考えてたら、あったよ鈍角三角形。 透けて見える面に隠れていた。 かくしてみそ汁には三角のとうふが浮くのであった。

意味

情報論と呼ばれるものは、情報を扱いはしない。 ある仮定のもとで情報の量について云々はするが、情報そのものをうまく捉えてはいない。 すべて、表の出る確率がこれこれで裏の確率がこれこれといった確率分布を与えた後で始まる話であり、その表裏がどのような情報であるかについてその先は問えない。 これは公理化された確率論がそもそも確率そのものを扱わず、さまざまな事象に対する確率を与えた後で、その計算方法について示したものであることを引き継いでいる。 このことは、形式論理学が世界との間で論理が意味するものを捨てて、純粋に形式の内に留まることによって成功したのと似ている。 形式と世界とのインターフェースを直視し踏み込もうとすれば、たちまちからみつく茂みに足を取られ居場所を見失ないかねない。でもぼくらが現実にすでにいばらの中にいるかもしれないのに見ないふりをするとすれば、それもあまり居心地のいい話ではない。

情報量と情報との関係も微妙だし、情報の意味が受け手にとって変わってくることもほとんど自明だ。 アラビア文字やモンゴル文字を美しいと思いこそはすれ、ぼくにはほとんどそれ以上にはなりえない。 囲碁のルールは知っていてもぼくには盤面を見てもどちらが優勢かさえわからぬただの白黒の模様だ。 自分自身の X 線写真もぼくにはそれと大差ない。 肺の影とやらがあるかどうは専門の医者に見てもらうしかない。 こうした例は枚挙に暇がないほど挙げることができる。 “Gen.11” はわずか 6 バイトの文字列に過ぎないが、聖書が手元にあれば、創世記 11 章「バベルの塔」の物語を意味しうる。 0, 1 という 1 ビットの区別が何を意味するかは文脈の数、あらゆる yes-no 疑問文の数だけ異なりうる。 ということは結局状況を好きに設定することを認めてしまえば 1 ビットであらゆる情報を意味しうる。 情報は、送り手と受け手が共通に持つもの、言語の知識や暗号の鍵や聖書という本に依存している。 であれば文脈、送り手と受け手とが共通に持つものに相対的に、あるいはそれも含めて情報を定めればよいのだろうか。 しかし共通に持つものをまともに定められそうなのは、はじめからそれを意図したネットワークや通信の規格のようなものだけだろう。 道具が臨機応変に意味するところを変え、捉えがたいのに似て、共通に持つものがどこまで共通なのかは心許ない。

英語で出てくるアルファベットを頻度順に並べると ETAOIN SHRDLU で始まり XZ で終わるとされる。 かつての鋳植機のキーボードの配列。 英語の文章を符号化するとき、アルファベットを 1 バイトずつで表すのではなく、頻度の多い E に頻度の対数に応じた短いビット列を割り当て、Z に長いビット列を割り当てるといった具合にすれば、英語でありさえすればほとんどの場合符号は元のものより短くなる。 イカサマコインが 1 ビット以下であるように、英語の文字ごとの頻度が均一でなく冗長であるからエントロピーはいくらか小さくなるのだ。 しかしこれは最良とは程遠い。 Q の後はほぼ必ず U であったり、S の後はほぼ必ず R でなかったりすることに注目すれば、2 文字目のエントロピーはさらに小さくなる。 3 文字、4 文字と増やしていけばどんどん小さくなっていく。 “When we have shuffled off this mortal ... ,” 英語文化圏の人なら『ハムレット』を読んだことがなくてもこの文に続く次の単語が coil であることはほぼ想像できてしまうのだろう。 ならば「英語文化」に相対的なこの coil の情報量は 1 ビットに満たないはずだ。 この表現自体シェイクスピアが作り出したものだとすると、少なくともその当初はそうではなかったのだろう。 しかしよほど鈍くない限り “mortal coil” という語が辞書に載る前から、それらの単語の微妙なニュアンスを読み取って、その比喩の意味するところは英語文化圏に居さえすれば自然に理解できたはずだ。 一方で、英語を他の文化圏として後から学ばねばならない人間にとっては、「死すべき者たちのコイル」が「人生のしがらみ」といった意味であるとはかなりの情報量がある。

140 バイトで表されるビット列は 2¹¹²⁰ 個、すなわちおよそ 10³³⁷ 個ある。 宇宙の水素原子の数が 10⁸⁰ とすれば、宇宙 10²⁵⁷ 個分ほど。 これを標準的な 2 進数値とみればその中には「7 の 5 の 3 乗乗」や「5 の階乗の階乗」も含まれ、ASCII 文字列と見れば、「“AB” の 70 回の繰り返し」も含まれる。 しかしこうした短い記述が与えられるものはごくごくごく一部に過ぎない。 単純な算術を駆使すれば、半分の 70 バイトまでのビット列は 2⁵⁶¹ ほどしかないのだから、半分以下に圧縮できるものは高々 2⁵⁵⁹ 分の 1, つまり 10¹⁶⁸ 分の 1 程しかない。 わずか 140 文字のビット列のほとんどは圧縮できず、ぼくらはそのほとんどを眼にすることさえない。 一方で全世界での Twitter のつぶやきは 2010 年 3 月現在 100 億、10¹⁰ ほど、ハードディスク一台に収まる。 あらゆる多様な人々のうずまく多様なコイル、加算的に積み上げられたつぶやきですら、この指数的な数の可能性の前ではほとんど無に等しい。 文字通りあらゆる本を納めたボルヘスの『バベルの図書館』に迷い込み一生さまよっても、一行でも意味のある文章に出会うことは絶望的に小さな可能性しか持ち得ない。 広大な空間から消え去りそうなほど小さな「意味」のある文章をより分けているのは何か。 あらゆる可能性からこの《世界》をより分けているのは。

確率論を世界から切り離すことで公理化したコルモゴロフは、またアルゴリズムによって文字列や数値の持つ文脈に寄らない客観的な本当の複雑さを定めようとした。 文字列や数の複雑さはそれを生成できる形式的な記述、すなわちプログラムの最小の長さとして定められる。 究極の圧縮。 どういうプログラム言語、どういう処理系かという文脈はあるが、それは定数分の違いに抑えられる。 しかしその複雑さを求めることはコンピュータにとっては計算不可能な問題であった。 究極の圧縮プログラムは存在してはならない。 そのようなプログラムを認めてしまうと、ある複雑さ以上でそれ自体が最小の記述を与えることになり矛盾する。 ベリーのパラドクス。 圧縮したい文字列より短いすべてのプログラムの生成結果を順に確かめ、文字列と比較して最小の記述を見つけ出そうとしても、それが停止するとは限らない。 停止問題。

完全なランダムノイズは、記述できるような何らの特徴を持たず、それを送ろうとすれば圧縮できず、最大の情報量を持つ。 しかし何も意味しない。 限界まで圧縮された信号はランダムノイズと区別できず、復元プログラムという鍵がないと決して解読はできない。 ある文脈、ある解読プログラムがそれの意味する長い物語を示すかもしれないが、それは文脈次第であらゆるもの、あらゆる可能性でありうる。 ならば何者でもなく何も意味しない。 文脈なしにはランダムさは何の情報も含まないのでなければならない。 しかし完全にそうだろうか。 一昔前のアナログテレビの「砂嵐」の画面はテレビの中の抵抗器の熱雑音によるほとんど完全なランダムパターンだ。 熱という完全な無知であり続ける領域から来た、圧縮できないと同時に何の情報も含んでいないパターン。 しかし、見ているとぼくらはそこにもうごめく線状のパターンを感じる。 何も情報が読み取れないはずのところにさえ、ぼくらの脳の視覚野はパターンを見つけ出そうともがき身もだえている。 この煩悶の中からこそ意味は始まるのではないだろうか。

「意味」と呼ばれるその共通のものが容易に取り出せるぐらいだったなら、形式的意味処理によって知性を模倣できるとした人工知能を作り出すことも何ということもなかったはずだ。 コンピュータがこの世に誕生した瞬間からあったその目論見は正に失敗の歴史でしかなかった。 1960 年代、ウィノグラードのプログラム SHRDLU は積み木の世界であるからこそ成功したかに見えた。 閉じられた箱庭の限定された意味の世界。 何色の積み木が他のどの積み木の上か下か、必要となる意味はそのようなものでしかない。 開かれた世界の意味をこれとして取り出すことはそれと比べるとずっと困難な話だ。 ランダムな可能性の中から意味あるものをうまくより分けなければ計算量は指数的に増大する。 フレーム問題。 ならば、ぼくらは何をやっているのか。 どうやってより分けているのか、本当により分けているのか。 しかし、ぼくが情報の意味の理解を間違っていないと自信を持つとしたら、むしろそれこそ間違っている。 理解に誤解はつきものだし、そうであるようなものでなければならない。

だが理解を相対化して意味などないというのとも違う。 意味がないと思っては、ぼくらの口はただの一言の言葉も発することはない。 昔タモリがやっていたハナモゲラ語ですら意味の境界で戯れるからこそ面白く感じる。 世界が「砂嵐」で、ものがぼくらにとって何がしかの意味を持つものとして現れてこなければ、ぼくらの眼はほとんど何も眼にすることはない。 それと定めることができなくても意味があるかのようにしかぼくらは振る舞えない。 意味があるかのように苦悶しつつ振る舞うこと、その結果として意味の世界が半ば結晶のようにしっかりと、半ばアメーバのように捉えどころなく析出してくる。