スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

オブジェクトの非正規化

 オブジェクト指向で有限オートマトンを表現してみるで、オブジェクト指向プログラミングでよくある問題について書きました。むろん頻繁に発生するこの問題は、解決方法もあります。今回はその手法について解説します。それと、学習方法の補足説明をします。
 オブジェクト指向で有限オートマトンを表現してみるで指摘した問題点は、型システムに依存した考え方をすることにより発生する問題です。これは、オブジェクト指向初心者にありがちな間違いです。初心者は定義をそのままオブジェクトにしがちです。定義をそのまま型として表現すると、この様なプログラムを書いてしまいます。
 解決する方法は簡単です。ちゃんと、オブジェクト指向分析と、オブジェクト指向設計をすることです。分析と設計を正しく行えば、硬直したプログラムは作りません。何故ならば、分析を通して本質を見極め、設計を通して賢いオブジェクトを考えるからです。これから、簡単な分析と設計をしてみます。
 有限オートマトンを分析すると、各集合{ Q, Σ, δ, q0, F }と出力との関係が大事です。また、今回の目的を考えると、「有限オートマトンを学習すること」です。従って、{ Q, Σ, δ, q0, F }は必ず指定する方式にする必要があります。そうしないと、有限オートマトンの学習に抜けが生じる恐れがあります。
 次に設計をします。オブジェクト指向設計は、適切に実装できるようにオブジェクトを考える段階です。オブジェクトの実装方法を検討すると、この要件で有限オートマトンの各状態を型として扱うのはやりすぎだと思います。何故ならば、実装が面倒ですし、細部に気を取られて有限オートマトンの概念を覚えるという本題が有耶無耶になる恐れがあるからです。状態オブジェクトを工夫し、各状態はインスタンスとして扱うのが適切だと考えられます。状態遷移関数については、状態オブジェクト・オートマトンオブジェクト・入力オブジェクトのどれにも依存しない形が良いでしょう。従って、柔軟性も考慮し別のオブジェクトとして扱うのがベストです。なお、私は概念を型に当てはめる考える事をオブジェクトの正規化、逆に型にしないでインスタンスで対応することをオブジェクトの非正規化と呼んでいます。
 簡単ながら、これで分析と設計が終わったので、その結果を踏まえて実装してみます。

using System;
using System.Collections.Generic;
using System.Linq;

//有限オートマトン( FA : finite automaton )
class Fa<StateT, InputT, ValueT>
    where StateT : FaState<ValueT>
{
    //FAの定義に必要なフィールド
    private IEnumerable<StateT> _stateSet;
    private IEnumerable<InputT> _inputSet;
    private Converter<StateT, InputT, ValueT> _stateTransition;
    private StateT _firstState;
    private IEnumerable<StateT> _lastStateSet;

    //現在の状態を覚えておく必要がある
    private StateT _currentState;

    //受理
    public bool IsAccept
    {
        get
        {
            return this._lastStateSet.Contains( this._currentState );
        }
    }

    //FAの定義( Q, Σ, δ, q0, F )でインスタンスを生成する
    public Fa(
        IEnumerable<StateT> stateSet,
        IEnumerable<InputT> inputSet,
        Converter<StateT, InputT, ValueT> stateTransition,
        StateT firstState,
        IEnumerable<StateT> lastStateSet )
    {
        this._stateSet = stateSet;
        this._inputSet = inputSet;
        this._stateTransition = stateTransition;
        this._firstState = firstState;
        this._lastStateSet = lastStateSet;

        this._currentState = firstState;
    }

    //記号1つを指定して現在の状態を遷移させる
    public bool StateTransition( InputT input )
    {
        if ( !this._inputSet.Contains( input ) )
            throw new ArgumentException( 
                input + "は想定外です" );
        this._currentState =
            this._stateTransition.NextState( 
                this._currentState, input );
        return this.IsAccept;
    }
}

//オートマトンの状態を表わす抽象オブジェクト
class FaState<T>
{
    //状態の識別子
    private int _id;
    public int ID
    {
        get { return _id; }
    }

    //状態が保持する値
    private T _value;
    public T Value
    {
        get { return _value; }
    }

    //IDと値は必須とする
    public FaState( int id, T value )
    {
        this._id = id;
        this._value = value;
    }

    //等価性を判定する
    public override bool Equals( object obj )
    {
        FaState<T> other = obj as FaState<T>;
        if ( other == null ) return false;
        if ( this.ID != other.ID ) return false;
        if ( !this.Value.Equals( other.Value ) ) return false;
        return true;
    }

    //本題と関係ないのでハッシュコードはいい加減にしている
    public override int GetHashCode()
    {
        return ( 
                this.ID.ToString() + 
                this.Value.ToString() 
            ).GetHashCode();
    }
}

//状態遷移関数の役割を果たすオブジェクト
abstract class Converter<StateT, InputT, ValueT>
{
    //次の状態を取得
    public abstract StateT NextState(
        StateT state, InputT input );
}

//サンプルに特化した状態遷移関数の定義
class SampleConvertoer 
    : Converter<FaState<int>, int, int>
{
    public override FaState<int> NextState( 
        FaState<int> state, int input )
    {
        if ( input == 0 )
            return new FaState<int>( state.ID, state.Value );
        if ( input == 100 )
            return new FaState<int>(
                state.ID + 1,
                state.Value + input );
        throw new ArgumentException(
            String.Format( "状態:{0}と入力値{1}の組み合わせは想定外です。",
               state, input ) );
    }
}

class Sample
{
    static void Main()
    {
        //300円の商品を扱う機械
        Console.WriteLine( "300円の商品を扱う機械の状態遷移" );
        Test( new FaState<int>( 3, 300 ) );
        Console.WriteLine( );

        //400円の商品を扱う機会
        Console.WriteLine( "400円の商品を扱う機械の状態遷移" );
        Test( new FaState<int>( 4, 400 ) );
        Console.WriteLine( );
    }

    static void Test( FaState<int> maxValue )
    {
        //自動販売機の有限オートマトンを用意する
        Fa<FaState<int>, int, int> obj = Init( maxValue );

        //100円投入してみる
        int input = 100;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

        //もう100円投入
        input = 100;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

        //投入したふりをしてみる
        input = 0;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

        //もう100円を投入
        input = 100;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

    }

    static Fa<FaState<int>, int, int> Init( 
        FaState<int> lastValue )
    {
        //機械が取りうる状態
        var state = new FaState<int>[ ] { 
            new FaState<int>( 0, 0 ), 
            new FaState<int>( 1, 100 ),
            new FaState<int>( 2, 200 ),
            new FaState<int>( 3, 300 )
        };

        //入力できる記号
        var input = new int[ ] { 0, 100 };

        //状態遷移関数
        SampleConvertoer convert = new SampleConvertoer( );

        //初期状態
        var first = new FaState<int>( 0, 0 );

        //最終状態
        var last = new FaState<int>[ ] { lastValue };

        //作成( FA = { Q, Σ, δ, q0, F } )
        return new Fa<FaState<int>, int, int>( 
            state, input, convert, first, last );
    }
}

オブジェクト指向で有限オートマトンを表現してみるのサンプルと比べると、随分とすっきりして、有限オートマトンの定義が分かりやすくなったと思います。
 この記事を読んだ人の中には、随分と面倒だと思った人が居る事でしょう。ですが、実際のところは、全然面倒ではありません。慣れれば一瞬でできる事です。私は慣れているので、今回紹介したプログラムのイメージが直接瞬時に出てきます。ブログに書くときは、間違ったプログラムを逆算して書きました。ちょっと考えて本を読んでいる程度なので、全然負担に感じません。感覚的には小説を読むとき、風景などをイメージしながら読んでいると同じです。こうやって改めて文章で読むと、難解に感じるでしょうが、読書家ならば普通にしている事なので簡単です。おなかつ、学習効果も高いので、落ち着いて専門書を読むときに試してみてください。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

オブジェクト指向で有限オートマトンを表現してみる

 1つ前の記事を読んで、オブジェクト指向プログラミングで、オートマトンを実装したらどうなるかについて気になった人が居るかと思います。また、オブジェクト指向プログラミングをしない方がよいと誤解した人が居るかもしれません。そこで今回は、オブジェクト指向プログラミングで有限オートマトンを実装する話題について書きます。
 早速ですが、よりオブジェクト指向プログラミングらしく、かつ素直に、有限オートマトンを実装した例を挙げます。

using System;
using System.Collections.Generic;
using System.Linq;

//有限オートマトン( FaOo : finite automaton )のオブジェクト指向版。
class FaOo<StateT, InputT>
    where StateT : FaState<InputT>
{
    //型システムにより必要なフィールドが減少する
    private StateT _firstState;
    private IEnumerable<StateT> _lastStateSet;
    private StateT _currentState;

    //受理
    public bool IsAccept
    {
        get
        {
            return this._lastStateSet.Contains( 
                this._currentState );
        }
    }

    //FaOoの定義( q0, F )でインスタンスを生成する
    //残りの( Q, Σ, δ )は型システムに任せている
    public FaOo(
        StateT firstState,
        IEnumerable<StateT> lastStateSet )
    {
        this._firstState = firstState;
        this._lastStateSet = lastStateSet;
        this._currentState = firstState;
    }

    //記号1つを指定して現在の状態を遷移させる
    public bool StateTransition( InputT input )
    {
        this._currentState =
            ( StateT ) this._currentState.NextState( input );
        return this.IsAccept;
    }
}


enum Coin
{
    Zero,  //硬貨投入なし
    One //100円硬貨一枚
}


//オートマトンの状態を表わす抽象オブジェクト
abstract class FaState<T>
{
    //次の状態を取得
    public abstract FaState<T> NextState( T input );

    public override bool Equals( object obj )
    {
        if ( this.GetType( ) == obj.GetType( ) ) return true;
        return false;
    }
}

abstract class SampleState : FaState<Coin> { }

class StateZero : SampleState
{
    public override FaState<Coin> NextState( Coin input )
    {
        if ( input == Coin.Zero ) return new StateZero( );
        return new StateOne( );
    }
}

class StateOne : SampleState
{
    public override FaState<Coin> NextState( Coin input )
    {
        if ( input == Coin.Zero ) return new StateOne( );
        return new StateTwo( );
    }
}

class StateTwo : SampleState
{
    public override FaState<Coin> NextState( Coin input )
    {
        if ( input == Coin.Zero ) return new StateTwo( );
        return new StateThree( );
    }
}

class StateThree : SampleState
{
    public override FaState<Coin> NextState( Coin input )
    {
        if ( input == Coin.Zero ) return new StateThree( );
        return new StateOne( );
    }
}

class Sample
{
    static void Main()
    {
        //自動販売機の有限オートマトンを用意する
        FaOo<SampleState, Coin> obj = Init( );

        //メッセージ変換用関数
        Func<Coin, string> GetString =
            ( Coin x ) => {
                if ( x == Coin.Zero ) return "0";
                return "100";
            };

        //100円投入してみる
        Coin input = Coin.One;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            GetString( input ),
            obj.StateTransition( input ) );

        //もう100円投入
        input = Coin.One;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            GetString( input ),
            obj.StateTransition( input ) );

        //投入したふりをしてみる
        input = Coin.Zero;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            GetString( input ),
            obj.StateTransition( input ) );

        //もう100円を投入
        input = Coin.One;
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            GetString( input ),
            obj.StateTransition( input ) );
    }

    static FaOo<SampleState, Coin> Init()
    {
        //最終状態
        var last = new SampleState[ ] { 
            ( SampleState ) new StateThree( ) };

        //作成( FA = { Q, Σ, δ, q0, F } )
        //※型システムにより簡潔化されている
        return new FaOo<SampleState, Coin>( 
            new StateZero( ), last );
    }
}

メタプログラミングをすればもっと短くなりますが、慣れていない人は読みにくいと思い、今回は愚直にプログラミングしました。以上のようにして、オブジェクト指向で有限オートマトンを実装してみると、新しいことがわかります。
 まず感じたのは、型システムのありがたさです。型システムにより、コンストラクタに指定する情報が減り、なおかつ、人間の入力ミスを減らすことができます。おまけに、ただの文字列よりも理解しやすいです。
 次に感じたのは、一度に知るべき情報が減るという事です。状態をオブジェクト化することにより、一度に考える状態遷移の数を減らせます。何故ならば、1つの状態オブジェクトを実装するときに、次の状態オブジェクトは何かを考えるだけでプログラミングできます。むろん、それは逆に言うと、一度に物事を考えない事も意味します。それで、思わぬ状態遷移の設計見落としが生じるかもしれません。ですがその短所は、設計とテストをすれば防げると思います。
 最後に感じたのは、余計な関数とデータの結合が生じる事です。オブジェクト指向プログラミングは、データと関数をセットで考えます。しかしながら、有限オートマトンは本来、状態と状態遷移関数を強く束縛して考えないと思います。何故ならば、たまたま同じ状態を使用する、オートマトンAとBがあったとします。このAとBの状態遷移が違うときサンプルの方法では上手くいきません。かといって、入力記号に結び付けるのも、有限オートマトンと関数を結びつけるのも、本来の意味から考えて間違いだと思います。これは、オブジェクト指向プログラミングでよくあるジレンマです。
 無暗にデータと関数を結びつけると本質が見えなくなります。従って、あえてオブジェクト指向プログラミングらしく実装しない方が良いときもあります。ただし、オブジェクト指向プログラミングで考えるという行為を否定しているのではありません。オブジェクト指向プログラミングで実装したほうがわかりやすいこともあります。
 今回は有限オートマトンしか実装していません。しかしながら、ミーリー型機械、ムーア型機械、チューリングマシン、非決定性有限オートマトンなどの性質を学びたい場合、オブジェクト指向プログラミングにしてみると、各概念の差異と共通点が良く見えてきます。従って、非オブジェクト指向とオブジェクト指向の両方で実装して、学習するとよいと思います。

テーマ : プログラミング
ジャンル : コンピュータ

オブジェクト指向プログラミングが奏でるレガシーコードとテストコードの輪舞曲

 オブジェクト指向プログラミングの利点は色々ありますが、今回はテストとの関係を書きます。オブジェクト指向プログラミングはテストを手助けします。
 オブジェクト指向言語のリファクタリングはしやすいが、非オブジェクト指向言語のリファクタリングがやりにくいとよく言われます。この原因は色々ありますが、テストがやり難いというのが大きな要因です。テストもなしにリファクタリングするなんて自殺行為です。考えられません。それ故に、醜いコードが放置されます。非オブジェクト指向言語で書かれたプログラムを保守する人は大変です。
 こんな時は、オブジェクト指向プログラミングを自分でするしかありません。だからといって、コンパイラがしている事を自分でするのも面倒です。「関数テーブルを作ってそれを呼び出す様にする」なんて事を、テストもなしにするのは自殺行為です。私はWindowsAPIプログラミングで多用しましたが、テストも書いていました。しかしテストが無いレガシーな状況で、それをするのは危険であり避けなればなりません。もっと簡単に出来る方法があります。表現を変えて考え方を使用すればいいのです。
 オブジェクト指向プログラミングの原点を、今一度考えてみましょう。オブジェクト指向プログラミングの核は、データ構造と関数の関係が逆転している点にあります。そこに注目すれば自ずと道は開けます。一番需要があるC言語の例を書きます。
 C言語の場合、重要なのはヘッダーファイルです。従って、ヘッダーファイルのリファクタリングをします。ヘッダーファイルならば、間違ってもコンパイラが手助けしてくれます。具体的には、ヘッダーファイル内の宣言を、データ構造視点で書き変えます。例えば、foo構造体を使用する関数群を、ひとつのヘッダーファイルに移動します。そして、コンパイルすれば、ヘッダーファイルの変更場所をコンパイラが教えてくれます。後は修正するだけです。
 ヘッダーファイルがデータ構造を基準でまとまっていれば、オブジェクト指向プログラミングの感覚でテストを出来ます。では、特別なデータ構造(構造体)を使用していないプログラムはどうすればいいのでしょうか?それについては、ちょっと難しいですがオブジェクト指向設計の考えを適用します。具体的には、パラメーターをよく観察して、新しい構造体を定義します。そして、関数の定義を変えます。最後にヘッダーファイルを変えれば、リファクタリングの準備が出来ます。リファクタリングの準備が出来たらこっちのものです。いくらでもリファクタリングの技法を応用できます。
 先に紹介したリファクタリング技法を私は、ヘッダーファイルの細分化と呼んでいます。じゃあ逆はあるのとかと思った人は鋭いです。ヘッダーファイルの統合化も考えています。こちらの技法は正しく逆で、関数を大まかに分類してから、ヘッダーファイルを構成します。次に、そのヘッダーファイルを参照させます。こうしておけば、後でヘッダーファイルをリファクタリングしても影響が少なくなります。
 今回紹介したC言語のリファクタリングテクニックは万能ではありません。しかし、便利なテクニックです。以上の様に、オブジェクト指向プログラミングは、オブジェクト指向プログラミング機能を持った言語に頼る概念ではありません。オブジェクト指向の概念をよく理解していれば、いかようにも応用できます。オブジェクト指向プログラミングを、言語の機能として捉えるのではなく、概念として習得しましょう。そうすれば、レガシーコードを前にしても恐れる必要がなくなります。

テーマ : プログラミング
ジャンル : コンピュータ

オブジェクト指向プログラミングは逆転の発想から生まれた

 オブジェクト指向プログラミングの見どころは、やはり逆転の発想にあります。その発想を知る事により、オブジェクト指向プログラミングの神髄が分かると思います。その発想を知るには時代背景から知る必要があります。
 オブジェクト指向プログラミングが生まれる前には、構造化プログラミングの時代でした。構造化プログラミングは、関数(機能)を視点においてプログラミングをしていました。C言語でプログラミングしてみると、その世界が体験できます。

#include 

struct Foo
{
    int value;
};

void Add( struct Foo* a, struct Foo b )
{
    a->value += b.value;
}

int main()
{
    struct Foo a, b;
    a.value = 1;
    b.value = 2;
    printf( "加算前の値;%d\n", a.value );
    Add( &a, b );
    printf( "加算後の値;%d\n", a.value );
    return 0;
}

Add関数にFoo構造体を渡して計算しています。これは関数(機能)を主眼に置いているので、関数視点のプログラミングです(※関数型プログラミングの話しではありません)この時代の構造化プログラミングは、データと関数が別々のものでした。従って大規模になると、大量のデータと関数が必要になり、管理と集団作業が難しい状態でした。
 今度は、C++によるオブジェクト指向プログラミングの例を見てみましょう。

#include <iostream>

class Foo
{
private:
    int value;
public:
    void SetValue( int value ) 
    {
        this->value = value;
    }
    int GetValue()  const
    {
        return this->value;
    }
    void Add( Foo b )
    {
        this->value += b.value;
    }
};

int main()
{
    Foo a, b;
    a.SetValue( 1 );
    b.SetValue( 2 );
    std::cout << "加算前の値;" << a.GetValue() << std::endl;
    a.Add( b );
    std::cout << "加算前の値;" << a.GetValue() << std::endl;
    return 0;
}

今度はデータの方に注目して、プログラミングをしている事が分かると思います。変数を自由に触れないので、プログラムの行数が増えます。ですが、変数に直接触る事による弊害の方が多いので問題になりません。また、関数がデータに付属しており、管理と集団作業が構造化プログラミングよりも簡単になりました。
 以上の様に、視点を変えると新しいものが見える事があります。関数とデータの立場を逆転した事により、新しいプログラミングパラダイムが生まれました。オブジェクト指向プログラミング見れば、見方を変える事は大変重要だという事が分かります。また歴史を知っておけば、よりプログラミングが面白くなると思います。

テーマ : プログラミング
ジャンル : コンピュータ

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。