脳ざらし紀行

_ 日本 Ruby カンファレンス 2006 〜ああっ Matz さまっ〜

行けるかな?

_ たらいまわし関数の低姿勢停止性

x, y, z のうちの一番大きい値と小さい値の差に関する帰納法を使えば、x, y, z が整数の時には停止性を証明することが出来るような気がします。

<proof>

x = y = z の時(差が0)は停止して

tak x y z = if x <= y then y else if y <= z then z else x 

であることは明らか。

x, y, z の最大と最小の差がN-1であるときに

tak x y z = if x <= y then y else if y <= z then z else x 

であると仮定する。

x, y, z の最大と最小の差がNであると仮定する。

x <= y のときは ok。以下では、x > y とする。

[i] z > x > y のとき。

tak x y z = tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)
          = tak (tak (x-1) y z) z (z-1) (帰納法の仮定より tak (z-1) x y = z-1 )

さて、x = y + 1 なら

tak (x-1) y z = tak y y z 
              = y

なので

tak x y z = tak (y+1) y z 
          = tak y z (z-1)
          = z   

。また x = y + 2 でも

tak (y+2) y z = tak (tak (y+1) y z) z (z-1)
              = tak z z (z-1)
              = z

なので、同様にして

tak (y+k) y z = z

[ii] x >= z >= y のとき。

tak x y z = tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)
          = tak (tak (x-1) y z) z x (帰納法の仮定か[i]の場合に当てはまるので tak (x-1) y z = z)
          = tak z z x
          = z

[iii] x > y > z のとき。

tak x y z = tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)
          = tak (tak (x-1) y z) (tak (y-1) z x) x (帰納法の仮定より tak (x-1) y z = x-1 )
          = tak (x-1) (tak (y-1) z x) x

y = z + 1 のときは

tak (y-1) z x = tak z z x 
              = z

で

tak x y z = tak (x-1) z x ([i]の場合に当てはまるので)
          = x 

y = z + k のときは

tak (y-1) z x = tak (z+k-1) z x ([i]か[ii]の場合に当てはまるので)
              = x

よって、 [i] [ii] [iii] により

 tak x y z =  if x <= y then y else if y <= z then z else x

である。

_ Boost C++ Libraryプログラミング

買った。著者は http://www.kmonos.net/wlog/ の人。世界は狭いね。おもな目的は Boost の線形代数ライブラリ uBlas 。と思ったら、uBlas の説明は2ページしか載っていません!! というのは、立ち読みして知っていたんですが、Boost の他の機能とuBlasを一緒に使えば、もっとプログラミングが楽になりそうなんで。それと、uBlasのコードを理解するのに、Boostの基本的なことを知っておく必要がありそうなんで。

で、唐突に、例えば (max{v1, v2})[i] = max{v1 [i], v2 [i]} のようなベクトル同士の2項演算を新しく定義したい、しかも Expression Template を使って。という場合は、以下のようなコードになる。

namespace boost { namespace numeric { namespace ublas {

  template<class T1, class T2>
  struct scalar_max: public scalar_binary_functor<T1, T2> {
    typedef typename scalar_binary_functor<T1, T2>::argument1_type argument1_type;
    typedef typename scalar_binary_functor<T1, T2>::argument2_type argument2_type;
    typedef typename scalar_binary_functor<T1, T2>::result_type result_type;
    
    static BOOST_UBLAS_INLINE result_type
    apply (argument1_type t1, argument2_type t2) {
      return t1 >= t2 ? t1 : t2;
    }
  };
  
  // (max{v1, v2})[i] = max{v1 [i], v2 [i]}
  template<class E1, class E2>
  BOOST_UBLAS_INLINE
  typename vector_binary_traits<
    E1,
    E2,
    scalar_max<typename E1::value_type, typename E2::value_type>
  >::result_type
  max (const vector_expression<E1> &e1,
       const vector_expression<E2> &e2) {    
    typedef typename vector_binary_traits<
      E1,
      E2,
      scalar_max<typename E1::value_type, typename E2::value_type>
    >::expression_type expression_type;
    
    return expression_type (e1 (), e2 ());
  }

}}}

始めは人間には理解不可能と思われた uBlas のコードだけど、慣れたのか何をやっているかは分かるようになってきた。

_ uBlas のベクトルと行列をお手軽に初期化

istringstream を使う。出力形式と同じ形式の文字列からベクトルと行列を生成することが出来る。

#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <iostream>

int main () {
  using namespace boost::numeric;
  using namespace std;
  
  ublas::vector<double> v;
  istringstream is("[3] (0.1, 2, 2)");
  is >> v;
  
  cout << v << endl;
}

$./a.out 
[3](0.1,2,2)

_ Boost.Numeric.Bindings

uBlas は単純な線形代数の演算しか提供していない。QR分解も出来ないのかよ、とか。そんな人のために、Boost.Numeric.Bindings。線形代数ライブラリとして既に定評のある LAPACK、ATLAS、UMFPAC を uBlas と一緒に使うためのラッパーを提供する。ちぇけら。

boost::bind と名前が微妙にかぶっているので、将来的にはなんか別の名前に変わりそうな気もする。

URL を見ると分かりますが、まだ boost-sandbox で開発されている段階で、boost 本体にはマージされていません。

http://sourceforge.net/projects/boost-sandbox/

_ [C++] f.template

もしくは、『限定子としての template』。メンバ関数テンプレートを使う場合、素直に書くとエラーになっちゃうよ、という話。どういうことかというと、

template<class Hoge>
void
func() {
  Hoge f;
  f.call<double>();
}

というのをgccでコンパイルしたらエラーになる。以下のように書かないといけない。call がメンバ関数テンプレートのつもりで、新たな関数テンプレート func を定義したことを、コンパイラに教えてあげないといけない。

template<class Hoge>
void
func() {
  Hoge f;
  f.template call<double>();
}

こんなの『プログラミング言語C++第3版』のどこにも書いてねー。とか叫んでみたけど、書いてあるらしい。付録Ｃ.13.6。

_ [Ruby] gdbm

簡単な CGI スクリプトを書いていて思ったこと。

GDBM.open(file, mode, GDBM::WRITER)

で、file が他のプロセスからロックされている場合、open はブロックせずに例外を投げちゃうのね。ちょっと使いにくい。CGI なんかだと file をロックしているプロセスはどうせすぐに終了するのだから、ブロックしてくれた方が楽なのに。

と思ったら、もともと libgdbm には gdbm_open でブロックするというオプションがないのか。うーん。

qdbm だとデフォルトでブロックするみたい。

_ http://b.hatena.ne.jp/shinichiro_h/

[後で読まない]、笑った。

_ Angry viewer sends human remains to Japan TV station

The viewer wrote that he had set his video to record the popular "Inu Kami" cartoon.

ロイターにまで。

_ http://scrapsteel.web.infoseek.co.jp/gallery/cg_paro13B.html

うーむ。

http://asame4.web.infoseek.co.jp/animf-n.html

_ ふと、はてなブックマークを使ってみようと

普段はdel.icio.usを使っているのだけど、ふと、はてなブックマークを使ってみようと思って色々弄っていたら、XSS脆弱性を発見した。

報告した。修正された。

これとは関係ないけど、ずっと「はまちゃん」だと思っていたけど、実は「はまちちゃん」だった。