Tuesday, November 27, 2012

Progress in three months

C 嬢は三ヶ月前には一桁の足し算を練習していた.一桁の足し算は良いとしても二桁になるとなかなか難しい.ところが次の週になると同じ問題を一瞥しただけで ``Geht's nicht (できない)'' と投げ出してしまうのだ.それが一ヶ月以上続いた.なかなか難しいなと思った.

私は「数学は言葉であり,人の意思の反映の一つである.というようなことは今はわからなくてもいいけど,でも,式には皆意味があるのだ.3+4はどういう意味なのだろうか.」というような話を毎回した.ある時は図を使って,ある時はブロックを使って話をした.彼女はそんなことよりも宿題の答を教えて欲しいと泣くこともあった.私は「答は重要じゃない.わかったかどうかが重要なのだ.」という話をした.しかし,まあ,彼女にはそれはどうでもいいことで,宿題をしていかないと明日が困るということだった.どうやらこの子の学校の先生は,Hasenschule が宿題を助けてくれることを期待しているらしく,そういう意味では,私は学校の期待に応えない役立たずであった.しかし,私には宿題の答えが書かれているかどうかなどはどうでもよく,この子が一つでも何か理解できるかが重要と思っていた.ある時,この子は私の教室から抜け出して他の先生に宿題を助けてもらっていたこともあった.

この子はもう二年もこんな調子だったそうである.ところが,ここ二三週間の進捗には私は驚いた.先週は私達は三桁の引き算を勉強した.一桁の足し算とは話が違う.802-456 というようなものである.最初彼女は,2 から 6 引くことは``Geht's nicht'' と言ったので,難しいかなと思ったのであるが,彼女は 5 の下に 1 を置いて,12-6は 6 と言ったのだ.私それでは後で困るぞ,と思ってみていた.私は彼女が,
802 - 456 = 800 + 12 - (450 + 6)     ... (1)
のように計算しようとしているのだと思ったのだ.これは,
802 - 456 = 790 + 12 - (450 + 6)     ... (2)
でなくてはいけない.したがって私は彼女が間違えると考えた.しかし,実は彼女は
802 - 456 = 800 + 12 - (450 + 6) - 10  ... (3)
を計算した.これは正しい.実は私は最初彼女がこのように計算していることがわからなくて,何をしているのか教えてもらうのに苦労した.私は (3) の方が難しいのではないかと思ったのだが,これには間違いはない.結局彼女は正しく答えを出した.私は,「それは全く正しいが,(1) の方法はどう思う?」と聞くと,(1)の方が彼女には難しいらしい.確かにこの問題では,1 の位を計算する時に,100 の位が変化する.しかし,(3)では変化しないという良さがある.そこで,残りの問題は彼女の方式で解いてもらった.

こんな引き算の方式があることを私は知らなかった.私は新しいことを教わり,彼女はここまでできるようになった.

昨日はまた,以前やった問題を``Geht's nicht''と投げ出していたのだが,私は彼女が実はできることを知っている.

Saturday, November 24, 2012

Fast lookup child


L 嬢はなまけ癖があるが,それでも時々結構早く課題をこなしてくる.同じ問題を間違える癖がある.たとえば,3+7 を 12 と答える.しかし,聞けば時間はかかるが正しい答えに到達する.ふと気がついたのだが,このスピードでどうしてこの課題をこんなに早く解くのだろうか.そこで私は彼女の横に座ってどうやって解くのか見ることにした.

なんと,彼女は全然計算をしないのだ.彼女は過去にやった問題を次々に探して同じ問題をみつけては答えを写していたのである.それがかなり速い.私よりもずっと速い.道理で同じ問題を間違えるはずである.Bitte nicht angucken! が私が新しく覚えた言葉である.「見てずるをしないこと.」

しかし,彼女のずるの速度はちょっと見物である.これも才能なのかもしれない.この才能を discourage するべきなのか,私にはわからない.でも,計算はできるようになって欲しいので,やっぱり私は今日も Bitte nicht angucken! と彼女に言うのであった.教えるというのは難しい.

Sunday, November 18, 2012

詳細を知りたくない bug: どうやって global static destructor を二度呼ぶのか

Abstract

ACM の Kode Vicious コラムは私の好きなコラムの一つである.(e.g., http://doi.acm.org/10.1145/1364782.1364791) プログラマとして働いていると時に彼の血圧を上昇させるバグに出会う.今回のバグは global な staticconstructor と destructor が二回呼ばれるというバグである.

Contents

私は global な static object を作ることを基本的に避ける.static なobject はいくつかの副作用があるからである.特に C++ ではどのようにそれらが呼ば れ るかはプログラマの制御下にない.ではなぜ私はこんなバグにあうのか,それは私の書いたコードではないからである.しかし仕事であるからには文句ばかりも言っていられない.

今回デバッグしていてわかったのは,ある static object の destructor が二回呼ばれていることである.私はそんなことが可能であることを知らなかった.C++ では static object は main が呼ばれる前に construt され,main が終了 した後に destruct され,それらの call の回数はコンパイラが一度だけに保 証 するはずだからである.

しかし,どのように binary を作成するかによっては以下のようにして二度呼ぶことが可能である.アイデアは dlopen を使う以下のようなものである.
  1. main のある application に static object A を link する.
  2. static object A のある shared library S を作成する.
  3. main は S を動的に load し,unload する.
あとは詳細である.コードの例を示す.
  •  example_factory.h は shared library 内部にあって application 側で利用する IExample_class を作成する factory IExample_factoryの宣言である.
  •  example_factory_impl.h, example_factory_impl.cpp は shared library 内部にあり機能を提供する.ここに static object がある.
  •  factory_interface.cpp は shared library へのアクセスポイントを提供する.
  •  call_static_destructor_twice.cpp が shared library を利用する application である.
このコードだけでは実は global static destructor を二度呼ぶには足りない.次のように shared library と application を生成する必要がある.

build script

#!/bin/bash -x
#
# How to call the static destructor twice.
# Copyright (C) 2012 Hitoshi
#

# create a shared lib.
LIB_SRC="factory_interface.cpp example_factory_impl.cpp"
LIB_OBJ="factory_interface.o   example_factory_impl.o"

g++ -g -Wall -fPIC -c ${LIB_SRC}
g++ -shared -Wl,-soname,libexample_factory.so -o libexample_factory.so ${LIB_OBJ}

# create an application that dynamically loads the shared lib.
APP_SRC="call_static_destructor_twice.cpp"
APP_OBJ="call_static_destructor_twice.o"

#
# correct build
#
# g++ -g -rdynamic -o test_example ${APP_SRC} -ldl

#
# evil build. The same symbol, but two static objects are constructed
# and destructed. If these objects looks up a system wide global
# resource and delete twice, you have a difficult bug.
#
g++ -g -o test_example ${APP_SRC} -ldl example_factory_impl.o


Evil build にあるように,static global object のある object を link する.このようなことをすること自体が間違いであるのだが,実際にこのような bugが build system にまぎれこんでしまったのである.このようなバグはとてもデバッグが難しい.

このコードを evil build で生成すると,実行結果は以下のようになる.実験環境は Kubuntu 12.04, g++ 4.6.3 である.static の destructor が二度呼ばれている.この destructor が system wide な global な resource に access していた場合,crash on exit ということになる.


% ./test_example
Example_class::Example_class()
info: loading [./libexample_factory.so]...
Example_class::Example_class()
info: library [./libexample_factory.so] has loaded.
Example_factory::Example_factory()
info: new IExample_class.
Example_class::Example_class()
Example_class::~Example_class(): I am created by new_example_class().
info: unloading [./libexample_factory.so]...
Example_class::~Example_class(): I am static since not changed.
info: library [./libexample_factory.so] has been unloaded.
Example_class::~Example_class(): I am static since not changed.


FILE example_factory.h


// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory_h
/// \brief an example interface class.

#ifndef EXAMPLE_FACTORY_H
#define EXAMPLE_FACTORY_H

#include 

//----------------------------------------------------------------------
/// Example class interface. This is created by the IExample_factory.
///
class IExample_class
{
public:
    /// default constructor
    IExample_class()
    {
        // empty. This is needed since app only know this and the
        // constructor can not be pure virtual.
    }
    /// destructor
    virtual ~IExample_class()
    {
        // empty. This is needed since app only know this and the
        // destructor can not be pure virtual.
    };
    /// print out message
    virtual void print() const = 0;

private:
    // members

private:
    /// copy constructor. prohibit until proved useful.
    IExample_class(IExample_class const & rhs);
    /// operator=. prohibit until proved useful.
    IExample_class const & operator=(IExample_class const & rhs);
};

//----------------------------------------------------------------------
/// Example factory interface. The factory of all the shared library
/// objects.
class IExample_factory
{
public:
    /// default constructor
    IExample_factory()
    {
        // empty. This is needed since app only know this and the
        // constructor can not be pure virtual.
    }
    /// destructor
    virtual ~IExample_factory()
    {
        // empty. This is needed since app only know this and the
        // destructor can not be pure virtual.
    }
    /// print out message
    virtual void print() const = 0;

    /// new IExample instance
    virtual IExample_class * new_example_class() = 0;
    /// delete IExample instance
    virtual void delete_example_class(IExample_class * p_iec) = 0;

private:
    /// copy constructor. prohibit until proved useful.
    IExample_factory(IExample_factory const & rhs);
    /// operator=. prohibit until proved useful.
    IExample_factory const & operator=(IExample_factory const & rhs);
};
//----------------------------------------------------------------------
#endif // #ifndef EXAMPLE_FACTORY_H


FILE example_factory_impl.h

// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory_impl.h
/// \brief an example class. Print a message when destruct.

#include "example_factory.h"
#include 

//----------------------------------------------------------------------
/// Example class implementation.
///
class Example_class : public IExample_class
{
public:
    /// default constructor
    Example_class();
    /// destructor
    virtual ~Example_class();
    /// print out message
    virtual void print() const;
public:
    /// set message
    /// \param[in] mes message for print().
    void set_message(std::string const & mes);
private:
    // message
    std::string m_mes;
private:
    /// copy constructor. prohibit until proved useful.
    Example_class(Example_class const & rhs);
    /// operator=. prohibit until proved useful.
    Example_class const & operator=(Example_class const & rhs);
};
//----------------------------------------------------------------------
/// Example factory implementation. The factory of all the shared
/// library objects.
///
class Example_factory : public IExample_factory
{
public:
    /// default constructor
    Example_factory();
    /// destructor
    virtual ~Example_factory();
    /// print out message
    virtual void print() const;
    /// new Example instance
    virtual IExample_class * new_example_class();
    /// delete Example instance
    virtual void delete_example_class(IExample_class * p_iec);

private:
    /// copy constructor. prohibit until proved useful.
    Example_factory(Example_factory const & rhs);
    /// operator=. prohibit until proved useful.
    Example_factory const & operator=(Example_factory const & rhs);
};
//----------------------------------------------------------------------


FILE example_factory_impl.cpp



// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory.cpp
/// \brief an example class. Print a message when destruct.

#include "example_factory_impl.h"

#include 

//----------------------------------------------------------------------
// default constructor
Example_class::Example_class()
    :
    m_mes("I am static since not changed.")
{
    std::cout << "Example_class::Example_class()" << std::endl;
}
//----------------------------------------------------------------------
// destructor
Example_class::~Example_class()
{
    std::cout << "Example_class::~Example_class(): " << m_mes << std::endl;
}
//----------------------------------------------------------------------
// print out message
void Example_class::print() const
{
    std::cout << "Example_class::print(): " << m_mes << std::endl;
}
//----------------------------------------------------------------------
// set message
void Example_class::set_message(std::string const & mes)
{
    m_mes = mes;
}
//======================================================================
// default constructor
Example_factory::Example_factory()
{
    std::cout << "Example_factory::Example_factory()" << std::endl;
}
//----------------------------------------------------------------------
// destructor
Example_factory::~Example_factory()
{
    std::cout << "Example_factory::~Example_factory(): " << std::endl;
}
//----------------------------------------------------------------------
// print out message
void Example_factory::print() const
{
    std::cout << "Example_factory::print() is called." << std::endl;
}
//----------------------------------------------------------------------
// new Example_class
IExample_class * Example_factory::new_example_class()
{
    Example_class * p_iec = new Example_class();
    p_iec->set_message("I am created by new_example_class().");
    return p_iec;
}
//----------------------------------------------------------------------
// create b
void Example_factory::delete_example_class(IExample_class * p_ec)
{
    delete p_ec;
}
//----------------------------------------------------------------------
// Static global object!
Example_class an_example_class;
//----------------------------------------------------------------------


FILE factory_interface.cpp



// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file factory_interface.cpp
/// \brief dynamically loaded class factory

#include "example_factory_impl.h"

//======================================================================
/// singleton for dynamic shared lib object tracking
class Shared_lib_object_tracker
{
public:
    /// get the instance
    /// \return example factory
    static IExample_factory * instance()
    {
        if(G_p_example_factory == 0){
            G_p_example_factory = new Example_factory();
        }
        return G_p_example_factory;
    }
    /// peek the instance
    /// \return example factory, may 0 if not yet accessed.
    static IExample_factory * peek_instance()
    {
        return G_p_example_factory;
    }
    /// delete the singleton.
    static void delete_instance()
    {
        if(G_p_example_factory != 0){
            delete G_p_example_factory;
            G_p_example_factory = 0;
        }
    }
private:
    // singleton instance
    static IExample_factory * G_p_example_factory;
private:
    /// default constructor
    Shared_lib_object_tracker()
    {
        // empty
    }
private:
    /// copy constructor. prohibit until proved useful.
    Shared_lib_object_tracker(Shared_lib_object_tracker const &);
    /// operator=. prohibit until proved useful.
    Shared_lib_object_tracker const & operator=(Shared_lib_object_tracker const &);
};

// singleton instance
IExample_factory * Shared_lib_object_tracker::G_p_example_factory = 0;

//======================================================================
extern "C"
IExample_factory * shared_lib_factory()
{
    if(Shared_lib_object_tracker::peek_instance() != 0){
        std::cerr << "Double call of the shared_lib_factory." << std::endl;
        return 0;
    }
    return Shared_lib_object_tracker::instance();
}
//======================================================================


FILE call_static_destructor_twice.cpp


//----------------------------------------------------------------------
// An example code for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
//----------------------------------------------------------------------
/// \file call_static_destructor_twice.cpp
/// \brief how to call static destructor twice

#include 
#include 
#include 
#include 

#include "example_factory.h"

// globals for open and close
static void * G_p_handle = 0;
char const * const G_p_lib_name = "./libexample_factory.so";

//----------------------------------------------------------------------
/// load shared library
IExample_factory * load_library()
{
    fprintf(stdout, "info: loading [%s]...\n", G_p_lib_name);
    G_p_handle = dlopen(G_p_lib_name, RTLD_LAZY | RTLD_DEEPBIND);
    if(G_p_handle == 0){
        // iostream seems has some static. Avoid to use it here.
        fprintf(stderr, "error: null handle: %s\n", dlerror());
        return 0;
    }

    void * p_symbol = dlsym(G_p_handle, "shared_lib_factory");
    if (p_symbol == 0) {
        fprintf(stderr, "error: symbol: %s\n", dlerror());
        return NULL;
    }

    typedef IExample_factory* (Factory_func());
    Factory_func * factory = (Factory_func*)p_symbol;

    fprintf(stdout, "info: library [%s] has loaded.\n", G_p_lib_name);

    return factory();
}

//----------------------------------------------------------------------
/// unload shared library
bool unload_library()
{
    fprintf(stdout, "info: unloading [%s]...\n", G_p_lib_name);
    assert(G_p_handle != 0);

    int result = dlclose(G_p_handle);
    if(result != 0){
        fprintf(stderr, "error: unload library: %s\n", dlerror());
    }

    // unload check can only be done by reload with RTLD_NOLOAD, see
    // the manual.
    void* handle = dlopen(G_p_lib_name, RTLD_LAZY | RTLD_NOLOAD | RTLD_DEEPBIND);
    if(handle != 0){
        fprintf(stderr, "error: Failed to unload %s\n", G_p_lib_name);
    }
    else{
        fprintf(stdout, "info: library [%s] has been unloaded.\n", G_p_lib_name);
    }
    return (handle == 0);
}

//----------------------------------------------------------------------
void dynamic_loading()
{
    // load
    IExample_factory * p_factory = load_library();
    fprintf(stdout, "info: new IExample_class.\n");

    IExample_class *p_exp = p_factory->new_example_class();
    // p_exp->print();
    p_factory->delete_example_class(p_exp);

    // unload
    unload_library();
}
//----------------------------------------------------------------------
int main()
{
    dynamic_loading();
    return 0;
}
//----------------------------------------------------------------------

Sunday, November 4, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (付録 A)


付録 A: Matrix とは何か


グラフを記述するのに matrix を使った.ところで matrix とはなんだろうか.簡単に言えば,matrix は数を並べた表である.

通常,いくつもの数を並べたものはやはりいくつもの数を並べたものである.たとえば,以下のようないくつかの都市の距離の表を考えてみる.

\begin{eqnarray*}
  \begin{array}{lrrr}
   & \mbox{東京}   &  \mbox{Berlin} &  \mbox{Auckland} \\
   \mbox{東京}     & 0     &    8940 &   8811    \\
   \mbox{Berlin}   & 8940  &       0 &  17742    \\
   \mbox{Auckland} & 8811  &   17742 &      0
  \end{array}
\end{eqnarray*}

マトリックス(matrix) は数をこのように行と列で並べた表である.日本語では「行列」という.しかし数学ではこの表を一つのかたまりとみる.時にこの表を,奇妙なことかもしれないが,一つの数のように扱うのである.一つの数のように扱うというのは,数と同様に matrix の間での演算があるということである.たとえば,matrix 間での足し算やかけ算というものを考える.それには数の 0 に相当する matrix や,数の 1 に相当する matrix が存在するということである.めんどうくさがりやの数学者は多数の数の間の関係をいちいち書くということに飽きて,ある数のまとまりの関係が一つの関係でおさまることを発見した.それを一つの対象 --- matrix --- として考えることで,様々な関係を簡潔に示すことができることを見い出したのである.

ここで matrix の用語を少し述べよう.matrix には「行」と「列」がある.matrix が 3 列,4 行の表である場合,\(3\times 4\) の matrix であるという.matrix を構成するそれぞれの数のことを matrix の「要素」という.各要素はこの行と列を使って指定することができる.二番目の列,三番目の行にある要素は,要素の添字を使って指定することができる.たとえば matrix \(A\) の 2列 3行目の要素は,\(a_{2,3}\) である.

先程示した距離の表(東京, Berlin, Auckland 間の距離)を matrix \(A_d\)として書くと以下のようになる.
\begin{eqnarray*}
 A_{d} =
 \left[
  \begin{array}{ccc}
   0     &    8940 &   8811    \\
   8940  &       0 &  17742    \\
   8811  &   17742 &      0
  \end{array}
  \right]
\end{eqnarray*}

ここで簡単な操作を例としてほどこしてみよう.次のようなベクトル \(v_{1}\)と \(v_{2}\) を考える.
\begin{eqnarray*}
 v_{1} = \left[
  \begin{array}{c}
   1\\
   0\\
   0
  \end{array}
  \right]
\end{eqnarray*}
\begin{eqnarray*}
 v_{2} = \left[
  \begin{array}{c}
   0\\
   1\\
   1
  \end{array}
  \right]
\end{eqnarray*}

このベクトル \(v_{1}\) と \(v_{2}\) はこの距離 matrix の例に関しては特定の意味を持っている.意味をふまえて,仮に,\(v_{1}\) を ``東京までベクトル'' そして,\(v_{2}\) ベクトルを ``東京までと Auckland までベクトル'' と呼ぶことにしよう.なぜなら,もし読者が \(A_{d} v_1\)というかけ算をご存知ならこれの意味がおわかりになるだろう.この計算の結果は,以下のようになる.
\begin{eqnarray*}
 A_{d} v_{1} =
  \left[
   \begin{array}{c}
    0    \\
    8940 \\
    8811
   \end{array}
  \right]
  \begin{array}{ll}
   \cdots \mbox{東京}     & \mbox{to 東京} \\
   \cdots \mbox{Berin}    & \mbox{to 東京} \\
   \cdots \mbox{Auckland} & \mbox{to 東京} \\
  \end{array}
\end{eqnarray*}
それぞれのベクトルの要素が「東京までの距離」を示している.東京から東京は動いていないので 0 である.次の例,\(A_{d} v_{2}\) は以下のようになる.
\begin{eqnarray*}
 A_{d} v_{2} =
  \left[
   \begin{array}{c}
    17751 \\
    17742 \\
    17742
   \end{array}
  \right]
  % \begin{array}{c}
  %  T \rightarrow Berlin + Tokyo \rightarrow Auckland \\
  %  B \rightarrow Belrin + Berlin   \rightarrow Auckland \\
  %  A \rightarrow Tokyo  + Auckland \rightarrow Auckland
  % \end{array}
\end{eqnarray*}
それぞれのベクトルの要素は以下の距離となる.
\begin{eqnarray*}
 \begin{array}{c}
  \mbox{東京} \rightarrow \mbox{Berlin} + \mbox{東京} \rightarrow \mbox{Auckland} \\
  \mbox{Berlin} \rightarrow \mbox{Belrin} + \mbox{Berlin}   \rightarrow \mbox{Auckland} \\
  \mbox{Auckland} \rightarrow \mbox{Berlin}  + \mbox{Auckland} \rightarrow \mbox{Auckland.}
 \end{array}
\end{eqnarray*}
同じ都市にいる場合,その距離は 0 であるから,この計算結果は以下のように簡単化できる.
\begin{eqnarray*}
 \begin{array}{l}
  \mbox{東京} \rightarrow \mbox{Berlin} + \mbox{東京} \rightarrow \mbox{Auckland} \\
  \mbox{Berlin}   \rightarrow \mbox{Auckland} \\
  \mbox{Auckland} \rightarrow \mbox{Berlin.}
 \end{array}
\end{eqnarray*}

読者はこれらの結果が正しくなることを確かめられるとよい.

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (7)


隣接行列

行列は数を二次元のます目上に並べた表である.ある規則で数を並べると,それがグラフを示すことと同じことになるので,ここで述べる.つまり動機はグラフを記述することにある.そのようにグラフを表現する方法の一つとして隣接行列がある.ここでその定義を述べておこう.行列に関して簡単な紹介を付録 A に記しておく.さらに行列に関して知りたい読者には文献[7]を参照して欲しい.

Definition: 隣接行列は N 個の点を持つグラフを表現するものであり,\(N \times N\) の大きさを持つ.ここで,点\(i\) と点 \(j\) 間に有向辺がある場合,行列の成分 \(a_{i,j}\) を \(1\) とし,辺がない場合には\(0\) とする.

これだけである.つまり隣接する点(= 辺で接続されている点)の要素を 1,そうでない要素を 0 とするような行列を隣接行列と呼ぶ.

例として人間関係のグラフを考え,好きか嫌いかの関係を隣接行列で示そう.好きという関係がある場合には点の間に辺を置くとここでは決める.嫌いな場合に辺を置くとしても良いが,私は嫌いな関係よりも好きな関係を知りたいので,今回は好きな関係とする.注意して欲しいのはこういう部分は私が勝手に決めることができるということである.これは事実とかではなくて,問題を解こうとしている人が矛盾が起きない限り,勝手に決めることができる.もし私が,「定義する」とか「仮定する」とか「と,考えてみよう」と言ったら,それは私が決めたことであって,読者には賛成してもらいたいと思っている.もし読者が賛成しない場合,その後の議論は意味をなさない.

次回は Alice に登場してもらって好き嫌いグラフを書いてみることにする.

文献

[7] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition,'' Wellesley-Cambridge Press, 2009