2010-11-30

C++のINVOKEの仕様

std::funcitonやstd::bindは、20.8.2 Requirements [func.require]で定義されているINVOKEの仕様に従う。つまり、メンバー関数やデータメンバーも扱える。

struct Foo
{
    void f() { }
    int x ;
} ;

int main()
{
    Foo foo ;
    // メンバー関数
    std::function< void ( Foo & ) > f( &Foo::f ) ;
    f( foo ) ; // foo.f() と同じ

    // データメンバー
    std::function< int & ( Foo & ) > x( &Foo::x ) ;
    x( foo ) = 0 ; // foo.x = 0 と同じ
}

もしかして、意外と知られていないのだろうか。

hidingに黄信号

ひょっとしたら削除されるかもしれない。それはそれで、教える手間が省けて、こちらとしても都合がいいのだが。

hidingを正しく教育するのは、至難の業である。

しかし、やはりoverrideはあるのにhidingがないというのは、片手落ちの感がある。

常用漢字表

常用漢字表

まあ、いろいろ紆余曲折があったようだが、(どっかのアホが俺とか糞などという漢字は野蛮であるから含めるべきではないとも主張したと聞いているが)、だいぶマシになったのではないかと思う。

とめ、はね、はらいなどの、表記の些細な違いは、区別する必要がないと明記してあるのもよい。本来、それは些細な違いなのだ。小学校などでは、いまだに教科書体にそって正しいとめはねはらいを書かなければならないなどと教育しているのだろうか。嘆かわしいことだ。

アメリカは5度、核爆しかかった

5 times we almost nuked ourselves by accident
アメリカは5度被曝しかけた : ギズモード・ジャパン

被曝は違うような気がするんだけどなぁ。

陰謀論的なことを言えば、まだ明らかにされていない事故がたくさんありそうな気もするけれど。

2010-11-29

std::functionのtargetの使い方

こういうことができる。

void f() { std::cout << "f" << std::endl ; }
void g() { std::cout << "g" << std::endl ; }

int main()
{
    std::function< void ( void ) > func( &f ) ;
    func() ; // f

    *func.target< void (*)(void) >() = &g ;
    func() ; // g
}

誰が使うんだろう。

追記:これだけだと、誤解を招きそうなので、以下のコードを補足しておく。

void f() { std::cout << "f" << std::endl ; }
void g() { std::cout << "g" << std::endl ; }
struct h { void operator ()(void){} ; } ;

int main()
{
    std::function< void ( void ) > func( &f ) ;
    func() ; // f

    *func.target< void (*)(void) >() = &g ;
    func() ; // g

    func = h() ;
    // 実行時エラー、型が合わない
    *func.target< void (*)(void) >() = &g ;
}

一応、std::function経由で呼び出すには、格納されている型を実行時に判断しなければならない。そのため、すでに格納されている型が分かっているのならば、中身を取り出すことで、そのような実行時チェックを、中身を取り出す際の一回で済ませることができる。これは、変更をしないと保証できるstd::functionのオブイェクトに対し、何百万回もoperator ()を呼び出す際に、有効であろう。そんなケースはあまりないと思うが。

void f( std::function < int (int) > f )
{
    // 1000000回の実行時チェックが必要
    for ( int i = 0 ; i != 1000000 ; ++i )
    {
        f(i) ;
    }
}

void g( std::function < int (int) > f )
{
    // fには関数ポインターが入っていると分かっている
    auto func = *f.target< int (*)(int) >() ;
    // 実行時チェックはいらない
    for ( int i = 0 ; i != 1000000 ; ++i )
    {
        func(i) ;
    }
}

もちろん、関数gを以下のように呼び出した場合、実行時エラーになる。

struct Foo { int operator ()(int) const { return 0 ; } } ;

int main()
{
    f( Foo() ) ; // OK
    g( Foo() )  ; // エラー
}

targetは危険である。規格を読んでstd::functionを実装した者でない限り、targetを使ってはいけない。つまり、私は使う資格がある。使いたいとは思わないが。

なぜならば、gは仮引数fの中身の型が、関数ポインターであることを前提にしているからである。

もっともつまらない日は1954年の4月11日

Computer identifies the most boring day in history - Telegraph
Cambridge Computer IDs World's Most Boring Day - Slashdot
「歴史的出来事が最も少なかった日」は1954年4月11日 - スラッシュドット・ジャパン

ケンブリッジ大学の学者によれば、史上最もつまらなかった日は、1954年の4月11日である。

この日は、世界的に特筆すべき出来事もおきていないし、有名人も一人しか生まれていないとのこと。

std::functionの真に正しい実装

だいぶ前の記事では、target()の意味を勘違いしていた。void *へのキャストが出てくるので、おかしいと思ったのだ。しかし、std::functionのtargetって誰が使うんだ、これ。


namespace hito {

class bad_function_call : public std::exception
{
public:
    bad_function_call() {}
    virtual char const * what() const throw()
    {
        return "bad function call exception" ;
    }
} ;

template < typename > class function ;// primary template.

template < typename R, typename ... ArgTypes >
class function< R ( ArgTypes... ) >
{
public :
    typedef R result_type ;

private :

    struct holder_base
    {
        virtual ~holder_base() {}
        virtual holder_base * clone() const = 0 ;
        virtual std::type_info const & target_type() const = 0 ;

        virtual result_type invoke( ArgTypes... ) = 0 ;
    } ;

    template < typename F >
    struct holder : public holder_base
    {
    public :
        holder(F f) : f( f )
        { }
        virtual ~holder() { }

        virtual holder_base * clone() const
        {
            return allocate_holder( f ) ;
        }

        virtual std::type_info const & target_type() const
        {
            return typeid( F ) ;
        }

        virtual result_type invoke( ArgTypes... args )
        {
            return f( std::forward<ArgTypes>(args)... ) ;
        }

        F f ;
    } ;

    template < typename holder_R, typename T, typename ... Types >
    struct member_holder : public holder_base
    {
    public :
        member_holder( holder_R (T::* const f)( Types... ) )
            : f(f)
        { }
        virtual ~member_holder() {}

        virtual holder_base * clone() const
        {
            return allocate_holder( f ) ;
        }

        virtual std::type_info const & target_type() const
        {
            return typeid( f ) ;
        }

        result_type invoke_impl( T t1, Types... args )
        {
            return (t1.*f)( std::forward<Types>(args)... ) ;
        }

        result_type invoke_impl( T * t1, Types... args )
        {
            return ((*t1).*f)( std::forward<Types>(args)... ) ;
        }

        virtual result_type invoke( ArgTypes ... args )
        {
            return invoke_impl( std::forward<ArgTypes>(args)... ) ;
        }

        holder_R (T::* f)( Types...) ;
    } ;

    template < typename T, typename DATA >
    struct data_member_holder : holder_base
    {
    public :
        data_member_holder( DATA T::* const f )
            : f( f )
        { }

        virtual ~data_member_holder() { }

        virtual holder_base * clone() const
        {
            return allocate_holder( f ) ;
        }

        virtual std::type_info const & target_type() const
        {
            return typeid( f ) ;
        }

        result_type invoke_impl( T & t1 )
        {
            return t1.*f ;
        }

        result_type invoke_impl( T * const t1 )
        {
            return (*t1).*f ;
        }

        virtual result_type invoke( ArgTypes ... args )
        {
            return invoke_impl( args... ) ;
        }

        DATA T::* f ;
    } ;

    holder_base * ptr ;

private :

    template < typename F >
    struct make_holder_type
    {
        typedef holder < F > type ;
    } ;
    template < typename holder_R, typename T, typename ... Types >
    struct make_holder_type< holder_R (T::*)( Types... ) >
    {
        typedef member_holder<holder_R, T, Types...> type ;
    } ;

    template < typename T, typename DATA >
    struct make_holder_type< DATA T::* >
    {
        typedef data_member_holder<T, DATA> type ;
    } ;

    template < typename F >
    static holder_base * allocate_holder(F f)
    {
        typedef typename make_holder_type<F>::type type ;
        return new type( f ) ;
    }

    void deallocate_holder()
    {
        delete ptr ;
        ptr = nullptr ;
    }

    holder_base * clone() const
    {
        if ( ptr != nullptr )
            return ptr->clone() ;
        else
            return nullptr ;
    }
    
public :

    explicit function() : ptr( nullptr )  { }
    function( std::nullptr_t ) : ptr( nullptr ) { }

    function( function const & init_expr ) 
        : ptr( init_expr.clone() )
    { }

    function( function && init_expr )
        : ptr( init_expr.ptr )
    {
        init_expr.ptr = nullptr ;
    }

    template < typename F >
    function( F f )
        : ptr( allocate_holder( f ) )
    { }


    function & operator = ( function const & assign_expr )
    {
        if ( this == &assign_expr )
            return *this ;

        deallocate_holder() ;
        this->ptr = assign_expr.clone() ;

        return *this ;
    }

    function & operator = ( function && assign_expr )
    {
        if ( this == &assign_expr )
            return *this ;

        deallocate_holder() ;
        this->ptr = assign_expr.ptr ;
        assign_expr.ptr = nullptr ;

        return *this ;
    }

    function & operator = ( std::nullptr_t )
    {
        deallocate_holder() ;
        return *this ;
    }

    template < typename F >
    function & operator = ( F f )
    {
        delete ptr ;
        ptr = allocate_holder( f ) ;
    }

    ~function()
    {
        deallocate_holder() ;
    }

    void swap( function & arg )
    {
        std::swap( this->ptr, arg.ptr ) ;
    }
    
    explicit operator bool() const
    {
        return bool( ptr != nullptr ) ;
    }

    result_type operator () ( ArgTypes... args ) const
    {
        if ( ptr != nullptr)
            return ptr->invoke( std::forward<ArgTypes>(args)... ) ;
        else
            throw bad_function_call() ;
    }


    std::type_info const & target_type() const
    {
        if ( ptr != nullptr )
            return ptr->target_type() ;
        else
            return typeid( void ) ;
    }

    template < typename T >
    T * target()
    {
        if ( target_type() != typeid(T) )
            return nullptr ;

        typedef typename make_holder_type<T>::type type ;
        auto actual_ptr = static_cast< type * >( ptr ) ;
        return &actual_ptr->f ;
        
    }

    template < typename T >
    T const * target() const
    {
        if ( target_type() != typeid(T) )
            return nullptr ;

        typedef typename make_holder_type<T>::type type ;
        auto actual_ptr = static_cast< type * >( ptr ) ;
        return &actual_ptr->f ;
    }

} ;

}

2010-11-28

多重継承はC++の用語として不適切

C++の規格上、派生と継承は、明確に区別するべきであることはすでに述べた。

本の虫: abstract classで知らなかったこと、付記、派生と継承の違い

ところで、「多重継承」という言葉がある。これは、Multiple Inheritance(複数の継承)という言葉の一般的な訳語である。多重継承は、実はC++には相応しくない言葉である。クラスは派生(derive)するものであって、継承(inherit)するものではないからである。

規格ではどうなっているかというと、Multiple base classes(複数の基本クラス)となっている。規格の文章は多重継承という言葉を使っていない。ただし、注記として、「複数の基本クラスを使うことは、しばしば多重継承と呼ばれている」などと書いてある。つまり、通称として多重継承という言葉が一般的であるということに言及しているのだ。

また、すでに書いている参考書の文章を見なおしたところ、なんと、派生と書くべきところで継承という言葉を使っている箇所があまりにも多数あった。これはまずい。

「DerivedクラスはBaseを継承しているから~」とか、「継承クラス」とか、「publicで継承」などと使っている。どうやら無意識に使っていたらしい。

現実世界では、派生と継承は、明確に使い分けられていない。一体どのように参考書を書けばいいのだろうか。もし、厳密に言葉を使い分けるとすると、やや見慣れない文章になってしまう。というのも、派生という単語を動詞として用いる場合は、「Derivedクラスは、Baseクラスから派生されている」というように、必ず受身で使わなければならないからだ。あるいは、「Derivedクラスは、Baseクラスの派生クラスである」などのように、名詞として使わなければならない。すでに書いた文章を修正しているが、どうも派生という言葉を厳密に正しく使うのは、たまに違和感を覚える。

思うに、自然言語は、規格の文章ほど厳密でなくてもいいということなのだろう。規格の文章では、同じ意味を表す用語が複数あるのは、混乱を招くだけである。しかし、自然言語では、同じ意味を表す言葉がひとつしかないというのは、むしろ稀である。ニュースピークなどという言語は、いかに共産主義がはびころうとも、決して根付くことはないであろう。この点は、一安心だ。

2010-11-27

ネット薬物詐欺「S売ります」で塩送った

ネット薬物詐欺「S売ります」で塩送った - 社会ニュース : nikkansports.com

違法薬物売買用のネット掲示板を多数開設したとして、覚せい剤取締法違反(営利目的譲渡ほう助)で兵庫県警薬物銃器対策課に逮捕、起訴された無職男(36)が調べに対し、自身も偽密売情報を書き込み、1500万円近く稼いだと供述していることが26日、分かった。覚せい剤の購入希望者には塩を、大麻には茶葉を郵送していたといい、まさに「偽違法薬物詐欺」といった手口。ただ“被害者”が名乗り出にくいためか、詐欺容疑での立件はされていない状態という。

しかし、実際Sの注文者に対しては塩を、クサに対しては茶葉を郵送。その結果「1500万円近く稼いだ」と話したという。

これは天才だ。しかも、詐欺では現在のところ立件できず、単に掲示板を解説したことによる幇助罪だけとは。1500万稼いだとあるので、おそらく、脱税も入るのかもしれない。

abstract classで知らなかったこと、付記、派生と継承の違い

以下のコードはwell-formedである。

struct Non_abstract { virtual void f() { } } ; 
struct Abstract : Non_abstract { void f() = 0 ; } ;

abstractクラスは、abstractクラスではないクラスから派生されることができる。その際、pure virtual functionではないvirtual functionを、pure virtual functionとしてオーバーライドすることができる。

これが何の役に立つのか分からない。ただ、pure virtual functionがあればabstract classであるなどという、あまり文法的に美しくないC++の仕様からすると、わざわざこの挙動を禁止する理由が見当たらなかったのだろうか。

ところで、今まで私は、派生と継承の違いを明確に理解していなかった。実際、この二つの言葉は、一般に、あまり区別されていないように思う。では、C++の規格ではどうなのか。

まず、派生というのは、derivedの訳語である。継承というのは、inheritedの訳語である。

規格では、あるクラスは、基本クラスから派生される(be derived from)という表現を用いている。個人的に、受身の表現は分かりにくい。例えば、「DerivedクラスはBaseクラスから派生されている(The Derived class is derived from the Base class.)」といえば、以下のようなコードを意味する。

struct Base { } ;
struct Derived : Base { } ;

ところで、このような場合、俗に、「DerivedはBaseを継承している」などと言われることもある。これは、規格に照らし合わせると、誤りである。継承という言葉は、クラスの派生関係には用いられない。C++では、クラスに対して、継承という言葉を用いるのは誤りである。

では、継承とは何か。規格では、基本クラスのメンバーは、派生クラスに、継承される(be inherited by)という表現を用いている。例えば、「Baseクラスのメンバー関数fは、Derivedクラスに、継承されている(The Base class's member function f is inherited by the Derived class)」といえば、以下のようなコードを意味する。

struct Base { void f() ; } ;
struct Derived : Base { } ;

派生の場合と同じく、このような場合に、「Baseクラスのメンバー関数fはDerivedクラスに派生されている」というのは誤りである。このような言葉は、聞いたことがない。思うに、継承という言葉は、派生クラスに対する基本クラスという意味を表す際に、受身にならずに使えるため、クラスの派生関係にも使われてしまったのだろう。

まとめると、クラスは派生するものである。クラスのメンバーは継承するものである。用語は正しく使わねばならない。

2010-11-26

アダム・サヴェッジ、12インチのカミソリを旅客機に持ち込む

僕はいつも、かばんにガラクタを詰め込んでる。いつも、飛行機に乗る前には、かならず鞄の中のガラクタを確認するんだ。中には危険だと思われるものもあるかもしれないし、手に入れるのが難しいガラクタなんかもあるからね。ただし、今日はそういうことするの忘れたんだ。

で、空港に行ってセキュリティチェック受けたんだけどさ、全身スキャナーを通るわけだ。全身スキャナーってのは、なんかチンポ縮む気がしたけどね。で、奴らはこんなものを見逃してたんだよ。12インチのスチール製のカミソリ。おい、どういうこったよ、これ。やつら俺のガラクタを漁っておきながら、こんなものを見逃したんだぜ。ちっぽけなガラクタに文句つけておきながら、これは見逃すってのかい。

こんなもの持ってもう一度飛行機乗るわけにもいかんしなぁ。誰か欲しくない?

Old New Thing:戦うプログラム

What if two programs did this? Practical exam - The Old New Thing - Site Home - MSDN Blogs

このブログを読んだことのない顧客が、次のような質問をしてきた。

我社のアプリをあらゆるウィンドウの上に表示したいのです。たとえ、他のウインドウがtopmostスタイルを使っていたとしてもです。我社のアプリは、 WM_KILLFOCUSとWM_PAINTメッセージで、topmostに設定し、SetWindowPosでウインドウを一番上に引き上げています。その後、念のためSetForegroundWindowも呼び出しています

結果を申しますと、我社のアプリと他のアプリが競合して、お互い一番上に表示させようとし続けます。どうも、他のアプリも同じような仕組みを使っているらしいのです。また、あるアプリなどは、我社の仕組みを打ち負かし、我社のアプリの上に表示されます。(そのアプリは他社のものなので、どうしようもできないのです)

我社は今、すべてのウインドウに対するすべてのメッセージをフックするためのDLLを書いていて、さらに[ここに書くべき価値もない馬鹿げたトリック]もする予定です。しかし、今の実装では、フックした他のアプリをクラッシュさせてしまうのです。我社は、タイマーを使ってSetWindowPosを周期的に呼び出すことも検討しているのですが、それは非効率的だと思うのです。

この顧客はWhat if two programs did this?のような思考実験すらできないようだ。思考実験のかわりに、実際に実験してしまうとは驚きだ。実験結果は、ただ予想通りというしかない。二つのプログラムがお互いに、一番上になろうとして戦うのである。誰も勝てはしない。皆負ける。とくに、最大の敗者はユーザーである。

ときどき、なぜこんなバカなことをする人間がプログラミングをできるのか、本気で考え込んでしまう。

2010-11-25

Old New Thing: 自前のメール鯖なんて使うわけないだろ

But who's going to set up their own email server? - The Old New Thing - Site Home - MSDN Blogs

昔、まだマイクロソフトのメアドが!を含んでいた頃、マイクロソフト社員の給与明細や保険などの社員情報をオンラインで閲覧、更新するための内部ツールが開発された。ペーパーレス会社へようこそ!

僕の友人は、ツールの説明に、奇妙な一文があるのに気がついた。「プログラムを実行する前に、メールサーバーにログオンした状態にしてください」

「妙だな」と友人は思った。「メールサーバーに接続するのに、何の意味があるんだ。このツールはメールを使わないじゃないか」

友人はたまたま、マイクロソフトのメール製品のテスターであったため、ある実験を試みた。友人は自前のメールサーバーを立ち上げ、billgという名前のアカウントを作った。そして、そのメールサーバーに接続した状態で、ツールを走らせた。

ようこそ、ビルゲイツ様。あなたの社員情報の一覧です。

「おいおい」と友人。「こいつァ、ひでぇ、セキュリティホールだな」。ツールはどうやら、メールサーバーに、「ヘイ、お前は誰としてログインしているんだい?」と訪ねているようであった。その答えは、ツールを実行している者であるという前提である。サーバーは何でもいいのだ。

友人は人事部の部長にメールを送り、この問題を知らせた。「このツールをすぐに利用停止すべきだ。誰でも、他人の個人情報を閲覧できるセキュリティホールがある」と。

人事部の部長からの返事は、あっけからんとしていた。「こちらの開発者が言うには、ツールはセキュアである。どうぞお気軽に社員情報をオンラインで更新してください」

この返事にムカついたため、友人はメールサーバーに新たなアカウントを作成した。人事部の部長と同じ名前のアカウントである。そののち、友人は別のメールを送った。

「貴殿の先の決定を御一考下さるべく申し上げます。貴殿の基本給はXXXドルであり、細君の名前はYyyyであります。ところで、ご子息の十歳の誕生日まで、ちょうど、あと一週間と相成りました。まさに来月であります。」

即座に返信が来た。「この問題を調査中です」

その後すぐに、ツールは、「メンテナンス」という理由で取り下げられた。

2010-11-24

hidingという概念は難しい

struct Base
{
    virtual void f( int ) ;
    virtual void f( float ) ;
} ;

struct Derived explicit : Base
{
    void f( int ) override new ;
} ;

Derived::f(int)には、overrideとnewが両方必要である。virtual関数であるBase::f(int)をオーバーライドしているので、overrideが必要になる。また、Base::f(float)という名前を隠しているので、newが必要になる。どちらが欠けても、コンパイルエラーになる。

ちなみに、派生クラスでベースチェック(explicitキーワード)を使う場合、基本クラスはうかつにメンバーを追加できなくなる。なぜならば、メンバーを追加するということは、派生クラスの前提を変えるということなのだから。

struct Base
{
    virtual void f( int ) ;
} ;

struct Derived explicit : Base
{
    void f( int ) override;
} ;

このようなクラスがあったとして、もし、Baseクラスに、fという名前のオーバーロード関数を付け加えた場合、Derivedクラスの方も、修正しなければならなくなる。

もちろん、これは当然である。そのための明示的なベースチェック機能なのだから。

2010-11-20

平方根のアルゴリズム

平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。

日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。

ここで使うのは、バビロニア人の方法(Babylonian method)と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。

√Sに対して、

  1. 任意の正の整数を初期値X0と定める(できるだけ平方根に近い値が望ましい)
  2. Xn+1を、Xnと S / Xnの平均値とする(平均値は相加平均で求める)
  3. 必要な精度が得られるまで、ステップ2を繰り返す

では、さっそく手動で計算してみよう。今、√123を求めたいとする。

上のアルゴリズムに当てはめると、S = 123である。x0は、とりあえず1とする。すると

x1 = ( x0 + 123 / x0 ) / 2 = ( 1 + 123 / 1 ) / 2 = 62
x2 = ( 62 + 123 / 62 ) / 2 = 31.9919
x3 = 17.9183
x4 = 12.3914
x5 = 11.1588
x6 = 11.0905

たったの6回の計算で、それなりの精度の平方根を求められる。

さて、これをコードに落としこむ際に、初期値をどう決めるかという問題がある。アルゴリズム的には、正の整数でさえあれば、正しい答えは出る。しかし、ここで条件分岐などを用いて複雑な方法で初期値を決めてしまっては、本末転倒である。大抵のsqrtの実装では、できるだけ簡単な値が選ばれる。たとえば、Sの二分の一など。次に、何度ステップを繰り返すかということであるが、これは、そもそも浮動小数点数の性質からして、値を正確に表すことができないので、単に、前回の値を比較するという方法を取る。つまり、値を比較して差がわからなければ、もうそれ以上ステップを踏む必要がないということである。

namespace hito {

double sqrt( double s )
{
    double x = s / 2.0 ; // Is there any better way to determine initial value?
    double last_x = 0.0 ; // the value one before the last step

    while ( x != last_x ) // until the difference is not significant
    { // apply Babylonian method step
        last_x = x ;
        x = (x + s / x) / 2.0 ;
    }
    
    return x ;
}

}

さて、この関数をconstexpr関数にするのは、簡単である。単に副作用をなくし、ループを再帰で置き換えればいいのだ。

namespace hito
{
    constexpr double sqrt_impl( double s, double x, double last )
    {
        return x != last ? sqrt_impl( s, (x + s / x) / 2.0, x ) : x ;
    }

    constexpr double sqrt( double s )
    {
        return sqrt_impl( s, s / 2.0, 0.0 ) ;
    }
}

ただし、コンパイル時に平方根を計算したい需要がそれほどあるとも思われない。

さらに詳しく知りたい人のために、有益なサイトを挙げておく。

根本的な計算方法は、Wikipediaに詳しく載っている。

Methods of computing square roots - Wikipedia, the free encyclopedia

具体的なコードで読みたいという人のためには、C++によるコード集もある。ちなみに、この記事は素晴らしい出来で、各アルゴリズムの出典まで明記している。

Best Square Root Method - Algorithm - Function (Precision VS Speed) - CodeProject

予想していた通り、浮動小数点数の内部表現をあてにしたビット演算のトリックがかなりある。中でも興味深いのは、謎のマジックナンバーで減算した後、手動のニュートン法を二回分行うコードである。噂によると、Quake 3を開発した伝説のゲームプログラマー、John Carmackによって発明されたのだと言われている。

2010-11-17

gccにconstexprが実装された

GCC 4.6に、constexprが実装された。constexprについては、特に難しいことはない。単に、関数やクラスを、コンパイル時定数にできるというだけの話である。ともかく、せっかくなので使ってみる。この機能は、細々と解説するより、実際にコードを示したほうが分かりやすいであろう。

まずは、constexprな変数である。

int main()
{
    constexpr int a = 0 ; // OK

    int value = 0 ;
    constexpr int b = value ; // エラー
    const int c = value ; // OK
} 

constexpr指定された変数は、必ずコンパイル時定数になる。変数の初期化子は、定数式でなければならない。constとの違いは、constはコンパイル時定数でなくてもよいのである。constは、初期化子が定数式の場合、定数式になる。そうでない場合、単にconst修飾しているにすぎない。

次に、コンパイル時の数値計算をしてみよう。ここでは、べき乗の計算をすることにする。問題を簡単にするため、指数は正の整数とする。これを、constexpr関数で実装してみる。

constexpr double power( double x, unsigned int y )
{
    return y == 1 ? x : x * power( x, y - 1 ) ;
}

int main()
{
    // 定数式
    constexpr double a = power( 2, 32 ) ;
    // 定数式ではない
    double x = 2 ; unsigned int y = 32 ;
    double b = power( x, y ) ;
}

これは、非常に簡単なconstexprの例である。ご覧のように、constexpr関数は、通常の関数と全く同じように使える。実引数が定数式の場合のみ、結果も定数式となる。実引数が定数式でなければ、コンパイル時ではなく、実行時に、通常通りの関数が呼ばれる。これは、全く同じ内容のconstexpr版と通常版の関数を書く必要がないようにするための仕様である。

constexpr関数の本体は、必ず、{ return expression ; }の形でなければならない。つまり、constexpr関数の本体には、たったひとつのreturn文しか書けない。したがって、条件分岐にはcondition expressionを使い、ループには再帰を使わなければならない。もちろん、constexprを使おうなどと考えているプログラマは、すでに一流のメタプログラマであろうから、再帰には全く抵抗がない。したがって、これは問題にならないといえる。

しかし、constexpr関数の目的は、コンパイル時のべき乗や平方根、三角関数などといった、複雑な数値計算ではない。constexprの目的は、むしろ、もっと簡単な計算にある。重要なのは、constexpr関数の呼び出しは定数式なので、定数式を期待している場所に書けるということである。

さっそく、定数式が必要な場所で使ってみよう。

constexpr int twice( int value ) { return value * 2 ; }

template < int N > struct Foo { } ;

int main()
{
    constexpr int a = twice( 1 ) ;
    int b[ twice( 2 ) ] ;
    Foo< twice( 3 ) > foo ;
}

twiceとは、単に引数を二倍して返すだけの単純な関数である。ここでは、constexpr指定された変数の初期化子、配列の要素数、非型テンプレート実引数で、twice関数を使っている。これらはすべて、well-formedである。

constexpr関数は、数値絡みのプリプロセッサーによるマクロを、完全に置き換えることができる。プリプロセッサーは根本的に邪悪である。いやしくもC++プログラマたるものは、#defineと打つたびに恥じ入るべきである。思うに、プリプロセッサーには、中毒性があるのではないかと思う。現に、私の知るある奇人などは、寝る間も惜しんでプリプロセッサーメタプログラミングに打ち込んでいるそうである。私は何度も。プリプロセッサーは体に悪いからやめた方がいいと忠告したのだが、まるで聞き入れる様子がない。

話がそれた。constexprの真の威力は、まだこれからである。変数をconstexpr指定できるということは、すでに述べた。では、constexpr指定できる型とは何か。それは、「リテラル型」と呼ばれるものである。リテラル型には、三種類ある。まず、intやdouble、ポインターなどといった、スカラー型がある。スカラー型はリテラル型である。次に、リテラル型の配列は、リテラル型である。

ところで、C++には、言語組み込みの文法とユーザー定義のコードとを、なるべく一致させるという理念がある。だから、クラスは通常の変数と同じ文法で宣言できるし、演算子はオーバーロードできるようになっている。また、C++では、初期化リストも取り入れられた。とすれば、クラスも、コンパイル時定数になれてしかるべきではなかろうか。

リテラル型の最後の種類は、ある特別な条件を満たしたクラスである。具体的には、以下の条件を満たす必要がある。

  • trivialなコピーコンストラクターを持つこと
  • 非trivialなムーブコンストラクターを持たないこと
  • trivialなデストラクターをもつこと
  • trivialなデフォルトコンストラクターか、コピーでもムーブでもないconstexprコンストラクターを持つこと
  • 非staticデータメンバーと基本クラスは、すべてリテラル型であること

C++0xでは、コンストラクターをconstexpr指定できるのである。これにより、クラスがリテラル型になる。

具体例を示そう。以下はコンパイル時定数として使用可能なクラスである。

class Integer
{
private :
    int value ;

public :
    constexpr Integer() : value() { }
    constexpr Integer( int value ) : value(value) { }

    constexpr operator int() { return value ; }
} ;

int main()
{
    constexpr Integer size = 5 ; // コンパイル時定数

    int x[size] ; // Integer::operator int()が呼ばれる

    Integer object ; // 通常の実行時オブジェクト
    int y[object] ; // エラー
}

Integer型のオブジェクトsizeは、constexpr指定子が使われているので、コンパイル時定数である。また、int型への変換関数を持っている。したがって、int型の定数式を使えるところでは、どこでも使うことができる。一方、objectは、constexprが書かれていないので、通常のオブジェクトである。

もちろん、Integerにpublicな非staticデータメンバーを追加すれば、そのままクラス外部からでも定数式として使うことができるし、その他の非staticメンバー関数も、constexpr指定できる。

リテラル型のクラスは、夢が広がる機能である。

ところで、ひとつ夢のある話をしよう。constexpr関数の本体の中身は、たったひとつのreturn文でなければならないということは、すでに述べた。ということは、条件分岐をする場合、condition expressionと再帰を使わなければならないのであろうか。実は、もう一つ方法がある。リテラル型の配列型はリテラル型である。ということは、その配列は、constexpr関数の中から使えるのである。また、ポインターはリテラル型である。constexpr関数は、ポインター経由で呼び出すこともできる。すなわち、以下のようなコードが書けるのである。

namespace detail {
    // 演算モードの実装
    constexpr int plus_impl( int x, int y ) { return x + y ; }
    constexpr int minus_impl( int x, int y ) { return x - y ; }
    constexpr int mul_impl( int x, int y ) { return x * y ; }
    constexpr int div_impl( int x, int y ) { return x / y ; }
    // 演算モードのテーブル
    constexpr int (*table[])(int, int) = { &plus_impl, &minus_impl, &mul_impl, &div_impl } ;
}
// 演算モードのためのenum
enum struct Mode { plus, minus, mul, div } ;
// ユーザーへのAPI
constexpr int compute( Mode mode, int x, int y )
{
    return detail::table[ static_cast<int>(mode) ](x, y) ;
}

int main()
{
    constexpr int value = compute( Mode::minus, 1, 1 ) ;
}

やっていることは、古典的なジャンプテーブルである。ただし、このジャンプテーブルは、コンパイル時に行われるという点が、少し変わっている。

訂正:誤って階乗としていたところを、べき乗に訂正。指数を正の整数に限定。

2010-11-16

ようやく3x5と5x3に対するまともな意見が読めた

404 Blog Not Found:3x5=5x3

あれはどう考えても国語の問題に過ぎない。数学に国語を持ち込むというのは全く理解出来ない。

そもそも、小学校で習う整数や小数同士の乗算は、交換法則がなりたつように定義されているはずである。A*B=B*Aが成り立つはずである。それで順序を変えて間違っているというのであれば、そのいわゆる小学校数学の定義を示して欲しいものだ。まさか定義に、皿の枚数だの、りんごの個数だのを持ち込むつもりだろうか。つまり、その数学の定義は、日本語に依存しなければ定義できないということなのだろうか。

そして、この教育が行き着く先は、間違いなく、

ほとんどの子は、自ら正解を探すのではなく、教師に答えを求めるようになる。それは教師に答え合わせしてもらわないと安心できないところまで続く。

となるであろう。憂うべきかな。

しかし、みんなbikesheddingが好きなようだ。というのも、この手の問題は、実に議論しやすいからだ。なぜなら、およそ小学校を卒業した者ならば、一桁の整数の乗算はできる。だから誰もが口を出したがるのだろう。

2010-11-15

C++0xにすごい変更が来た

Batavia会議は、だいぶ興味深いことになった。詳しくは、正式なNのペーパーが出てから解説するが、とにかく、非常に重要な項目をふたつだけ解説する。

まず、attributeによって提供されていた多くのクラスのメンバーに関する機能は、キーワードを与えられた。これは、言語機能は、特別な文法を与えるに値するという思想からである。会議でコンセンサスの得られた文法は以下の通りである。

struct Base
{
   virtual void f() { }
   int x ;
} ;

struct Derived final explicit : Base
{
   virtual void f() override { }
   int x new ;
} ;

機能はattributeで提供されていたものと全く変わらないので、説明は省く。変更点としては、base_checkのかわりにexplicitを使い、hidingのかわりにnewを使うことになった。newは違和感を覚えるかもしれないが、色々考慮した挙句、こうなった。

ちなみに、C++0xでは、メンバーの宣言にinitializerを記述できるので、その場合、以下のようになるだろう。

int x new = 0 ;

どうも初心者を混乱させそうな気がする。

これらのキーワードは本物のキーワードではない。文脈依存キーワード(contextual keyword)と呼ぶべきものである。つまり、ある場所においてだけ、キーワードとして扱われるのである。これにより、finalやoverrideといったidentifierを使うことができる。これは、下位互換性を保つための処置である。これらのキーワードが出現する場所は、識別子をかけない場所なので、実装は可能である。contextual keywordは、すでにC#で使われており、実績がある。

つぎに、暗黙のコピーコンストラクターという問題がある。このブログを読んでいる読者なら、David Abrahamsの、N3153: Implicit Move Must Go(暗黙のムーブ爆発しろ)というペーパーは、とっくに読んでいることであろう。また、Bjarne Stroustrupの、N3174: To move or not to move(ムブるべきかムブらざるべきか。それが問題じゃ)というペーパーも、すでに熟読しているはずである。

Daveが暗黙のムーブは深刻な互換性の問題を引き起こすからやめるべきだと主張したのに対し、Bjarneは、暗黙のコピーでも問題は同じだと主張した。激戦の結果、Bjarneが勝った。

これは非常に大事なことなので、特別に大きなフォントで書いておく。

暗黙のコピーコンストラクターは、ユーザー定義のデストラクタがある場合、生成される。この挙動はdeprecatedである。

非常に大事なことなので、もう一度書いておく。

暗黙のコピーコンストラクターは、ユーザー定義のデストラクタがある場合、生成される。この挙動はdeprecatedである。

つまり、以下のような意味である。

struct X
{
    ~X() { } // ユーザー定義のデストラクター
} ;

int main()
{
    X a ;
    X b = a ; // 警告! deprecated!
}

クラスXには、暗黙のコピーコンストラクターが生成される。ただし、この挙動はdeprecatedである。将来的には、規格から削除されるかもしれない。上記のようなコードを書いてはいけない。

ではどうするか。もちろん、ユーザー定義のコピーコンストラクターを書くこともできる。しかし、もし暗黙のコピーコンストラクターの挙動で問題がないのならば、explicitly-defaultedにすることもできる。

struct X
{
    X( X const & ) = default ; // 明示的なデフォルト化
    ~X() { } // ユーザー定義のデストラクター
} ;

int main()
{
    X a ; X b ;
    a = b ; // 正しいコード
}

したがって、正しいC++プログラマーは、ユーザー定義のデストラクターがある場合には、暗黙のコピーコンストラクターは生成されないものと考えるべきである。その機能はdeprecatedである。deprecatedな機能は使うべきではない。

ちなみに、暗黙のコピーコンストラクターは、ユーザー定義のムーブコンストラクターや、ムーブ代入演算子がある場合にも生成されるが、これも同じ理由でdeprecatedである。

マクスウェルの悪魔、召喚さる

中央大学 | ニュース | 世界初「情報をエネルギーへ変換することに成功」理工学部教授 宗行 英朗と助教 鳥谷部 祥一が記者会見を行いました

召喚というか、むしろ悪魔を実装したというべきなのか。

学生運動に参加していた人間がVIPに現れていたらしい

学生運動やってた元過激派左翼の団塊だけど質問ある? : TRTR(・Д・;)

これは興味深い。

学生運動というものは、いまから四十年ぐらい前の話である。私は、どうしてもこの学生運動というものが、理解出来ない。もちろん、当時の記録はある。どのような暴動が行われたとか、そういう記録は残っている。しかし、何故そんなことをしたのかという理由が、全く理解出来ない。アカの主張は、眉にツバをつけなくても、あきらかにトンデモなのだが、一体何が彼らをそこまで駆り立てたのか。

これは、その時代に生きていなかった人間には、理解出来ないのだろう。

2010-11-14

Nvidia、チップセット事業から撤退

Nvidia: We Are Not Building Chipsets Anymore - X-bit labs

IntelとAMDのCPUに対するチップセットの開発をやめるそうだ。つまりこれで、サードパーティ製のチップセットというのは、存在しなくなる。

もはや、チップセットの性能を云々する時代でもないのか。そもそも、昔はマザーボードといえば、本当に各ハードをまとめる板のようなものだった。今や、ほぼすべてのマザボが、サウンドやUSBやLAN程度は、当然のごとくに搭載している。

しかし、これからはどうなるのだろう。さらに現在のチップセットの機能を、CPU側に統合する方向に進化していくのだろうか。そうなると、最終的には、ひとつのチップで、現在で言うところのCPUもGPUもチップセットもすべて搭載するようになるのだろうか。今はまだ、そのような製品は、組み込みのような分野でしか実用化されていない。

面白い雑学動画をいくつか

カカオ豆からチョコをつくってみた:ハムスター速報 - ライブドアブログ

これは気合が入っている。

カカオ豆からココアを作る動画。

映画の音響ができるまで。

2010-11-13

パーフェクトPHPが発売されたらしい

Togetter - 「書籍『パーフェクトPHP』の中身が本当にパーフェクトらしい(※ただし自社推薦含む) レッドブル24本とセットでどうぞ!」

Twitterによると、パーフェクトな出来らしい。こちらも頑張らなくては。

それにしても、今開催されているBatavia会議の状況が気になる。まさか今頃、ADLに変更が来るとは思わなかった。また、base checkingをattributeにするかcontextual keywordにするかで揉めている。noexcept(auto)も提案されている。

何と時代錯誤なことよ

日本政府とNHK、インターネット回線の受信料の義務化へ:ハムスター速報 - ライブドアブログ

ドイツの国営放送が信じがたい。住みたくない国だ。

2010-11-10

耳嚢

しばらく宇治拾遺物語集を書見せるに、右書を読み終わるによって、今は、耳嚢をぞ読みける。書見なる言葉は、いつごろより使われるやうになつたものか知らず。林太郎君の笑うところの言葉なり。

耳嚢は、当時の世上の話を集めたるものにして、およそ二百年前の文なり。根岸鎮衛(1737-1815)奉行が書きたり。

ともかく、耳嚢の文章は、非常に簡単で読みやすい。私が持っているのは、岩波文庫の第二版なので、当時の校訂者である柳田國男の言葉が、巻頭に載せてある。そのなかで、「わずかに125年しかたっていないのに、もうそのままでは読めない」などと書いてある。根岸の死んだ年は、ちょうど今から225年前にあたる。とすれば、柳田國男と現在とは、100年の隔たりがある。ところで、柳田國男の文章も、現代では、もうそのままでは読めない文章である。

柳田國男は、当時(225年前)は、談話と文章の距離が、今(125年前)よりよっぽど近かったのではないかと書いている。もちろん、耳嚢の文章は、口語とは異なるが、それでも、今(125年前)の語尾だけ見た目だけの言文一致よりは、よほど優れていたのではないかと書いている。興味深いことだ。

2010-11-08

体温が上がると体がかゆくなる

私は物心ついたころから、体温が上がると体がかゆくなるという症状に悩まされている。どのような状況で起こるかというと、強力な冷房のきいた場所から暑い場所に移動したとき、熱い食べ物を食べたとき、風呂に入ったとき、急激な運動、などである。思うに、体温の急な上昇が問題ではないかと思う。

ところが、どうも今年の冬は、さらにひどくなっている。最近、寒くなったので、当然厚着をして出かけているのだが、10分ほど普通に歩いただけで、全身かゆくてたまらなくなる。かといって、外套を着ないわけにも行かない。普通に歩くだけでも体温は上がるのは当然なのだが、昔はここまでひどくはなかった。

かゆみは10分ほどもすれば収まるため、それほど日常生活に支障はないものの、今年は格別に頻度が高い。どうしたことだろう。一度医者にでも相談するべきなのだろうか。

2010-11-07

OldNewThing:時刻合わせの際、日付が違っていると失敗する理由

Why does the Win32 Time service require the date to be correct before it will set the time? - The Old New Thing - Site Home - MSDN Blogs

時刻同期の際に、日付が違っていると、処理は失敗し、次のようなエラーメッセージが返ってくる。「Windowsは時刻をtime.windows.comと同期させる際に、エラーが発生しました。セキュリティ上の理由により、Windowsは時刻を同期できません。理由は、日付が違っているためです。日付を修正して再試行してください」。セキュリティ上のリスクとは何だ?

まず、問題を解決したい人は、エラーメッセージに従うことだ。日付を正しく設定して、再試行すべきである。もし、それでも失敗する場合、時間をある程度近い値に設定すべきである。時刻がある程度近くなれば、timeサーバーと正常にやり取りできる。

閑話休題(それはさておき)、ここでいう、セキュリティ上のリスクとは何か。

一見すると、サーバー側が、時刻があまりにも間違って設定されているクライアントを弾いているように見える。しかし、事実は逆である。クライアントが、悪意のあるtimeサーバーの攻撃を防いでいるのである。

ケルベロス認証プロトコルは、お互いが同じ時刻を使っていることを前提としている。(多少の誤差は許容範囲だが)。もし、攻撃者が、例えばDNS poisoningなどで、クライアントの時刻を、悪意あるサーバーと同期させた場合、攻撃者は不正な時刻(大抵は過去の時刻)を用いて、次の攻撃の足がかりにすることができる。

Windows Timeサービスのデフォルトの設定では、15時間以上も違っている日付を拒否するようになっている。このKB記事に従えば、設定を変更することもできる。なお、このKB記事が、本文執筆の主要なソースとなっている。