Status List for Library Proposals

C++

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3371.html
C++11の次の改訂に向けたライブラリの提案を読んでみた．C++11もろくに知らないのでいろいろ読み間違いがあるかもしれない．

A minimal std::range

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3350.html

Overview

Ranges are ubiquitous in programs that use STL algorithms, but they're always written as adjacent iterator arguments, which makes them hard to use. Several groups have proposed a new set of range concepts that would allow ranges to be passed around as single objects. Two notable examples are the Boost.Range library and Andrei Alexandrescu's range concepts in D.

？？？

そもそもrangeが何なのか良くわからないのでそこから調べた．ということで，boost::rangeのドキュメントがこちら．
http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/index.html

下のコードは，mapから値を取り出していって，偶数だけを，逆順に，targetに追加する．

using namespace boost;
using namespace boost::adaptors;
// Assume that is_even is a predicate that has been implemented elsewhere...
push_back(target, my_map | map_values | filtered(is_even()) | reversed);
Range Concept

RangeとはSTLコンテナーコンセプトに似たコンセプトである．範囲にアクセスするためのイテレータと要素数を持つ．しかし，Rangeはコンテナより少ない要件を持つ．
今のところboost::rangeでは下の3つがサポートされている．

  • standard-like containers
  • std::pair
  • built-in arrays
Range Adapter

Range AdapterはRangeをラップして違うふるまいをする新しいRangeを提供するクラスである．

#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <iostream>
#include <vector>

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed,
             std::ostream_iterator<int>(std::cout) );

このboost::adaptors::reverseはAdopter Generatorと呼ばれる．

演算子|をキモいと思う人は，下のようにも書ける．このコードは，vecの要素を逆順にして，ユニークして，標準出力に出力する．

std::vector<int> vec;
boost::copy( boost::adaptors::unique( boost::adaptors::reverse( vec ) ),
             std::ostream_iterator<int>(std::cout) );

でも，こう書いた方がたぶんきれい．

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed
                 | boost::adaptors::uniqued,
             std::ostream_iterator<int>(std::cout) );
Range Algorithm

Range Alogrithmの最も単純な例としては，2つのイテレータを渡すイテレータベースのアルゴリズムが1つで済むようになる．

#include <boost/range/algorithm.hpp>
#include <vector>

std::vector<int> vec = ...;
boost::sort(vec);  //std::sort(vec.begin(), vec.end());

しかし，戻り値の型が普通のイテレータベースのアルゴリズムとはたいてい異なる．どういうことかというと，boost::sortの戻り値はrangeなので，下のように，別のrangeアルゴリズムにそのまま渡すことが出来る．

boost:unique(boost::sort(vec));

Hashing User-Defined Types in C++1y

ユーザー定義型のハッシュ関数を定義しやすくしようという話．

namespace my_namespace {
  struct OtherType { ... };
  struct MyType {
    OtherType field1;
    int field2;
    char field3[500];
    float field4;  // Does not contribute to equality.
  };
  std::hash_code hash_value(const MyType& val) {
    return std::hash_combine(val.field1,
                             val.field2,
                             val.field3);
  }
}

このhash::combineに似たものはboostにあるけど，C++11には入っていない．

Hashing vs Fingerprinting

標準ライブラリの使い道は，現在のプロセスからしか使われないハッシュテーブルの検索に限る．つまり，異なるプロセスにある2つのオブジェクトのハッシュ値は同じ値を返すとは限らない．あと，ハッシュ値をディスクに保存したり，セキュリティに関連した使い方もすべきでない．

ハッシュテーブルは，std::hash()(object)がそのプログラムの実行中のみ同じ値を返すことを要求する．そのため，標準ライブラリは実装を変更してもいいはずである．しかし，Googleでは，きちんとしたドキュメントなかったこと，ハッシュの実装の変更があまりにまれだったために，開発者がハッシュ値をディスクに保存して，実装の変更により既存のコードが壊れるということがあった．そこで，ハッシュ関数は違うプロセスでは違う値を返すことを提案する．それにより，誤りに早く気付けるようになる．また，ハッシュ値を前もって計算するdenial-of-service攻撃も防ぎやすくなる．

Hashing Ranges

コンテナーなどハッシュ値の計算は以下のようにできるが，hash_combineの中でいちいち初期化が走るので効率的ではない．そこで専用の

hash_code hash_value(const MyType& val) {
  hash_code result = 0;
  for (const auto& v : val) {
    result = hash_combine(result, c);
  }
  return result;
}
Hashing objects as byte arrays

オブジェクトをバイト列としてみなすと高速に計算可能．ただしパディングがないことが条件．

LTL式からBuchiオートマトンへの変換

読んだ論文についてメモ．

1.Fast LTL to Buchi Automata Translation

  • LTL -> Alternating Buchi Automata -> Generalized Buchi Automata -> Buchi Automata

ABAからGBAへの変換はABAがvery weakという性質を持つために可能らしい．
各ステップでオートマトンのサイズを小さくするために単純な簡約を行なっている．
この論文の実装はLTL2BAというツールとして公開されている．

2.Efficient Buchi Automata from LTL Formulae

  • LTL -> GBA -> BA

オートマトンのサイズを小さくするために，単純な式の書き換え，式を分解してDNFにした後ヒューリスティックに式を小さくする（0-1 ILPになるらしいけど謎），オートマトンを生成後単純化を行う，という３つのことをやっている．
オートマトンの単純化として，

  • direct simulation relation, reverse simulation relationを使って等価な状態を消す
  • GBAにおいて，受理条件が満たされるような強連結成分(fair SCC)に到達できないような状態を全て消す
  • GBAがweakなら，BAへの変換が単純にできる

3.Constructing Automata from Temporal Logic Formulas : A Tutorial

  • LTL -> GBA -> BA

オートマトンの各状態がtemporal formulaだけでなくリテラルも持つような構成法．チュートリアルだけあって，証明もわかりやすい．式の分解は集合的な手続きになっている．
リテラルを状態ではなく遷移に持たせることについても最後に少し書いてある．
GBAからBAへの変換は，１のものよりシンプル．

4.An Automata-Theoretic Approach to Linear Temporal Logic

  • LTL -> ABA -> BA

効率は良くない．LTLからBAへの変換以外にも色々と基本的なことが書かれている．
Nondeterministic BAとDeterministic BAの表現力の違い，NBAからRabin Automatonへの変換，NBAの空判定と充足可能性，Relaizability problemをRabin Tree Automatonの空判定として解く．
VardiさんのAn Automata-Theoretic Approachシリーズは他にもあるようなので勉強のために読みたい．