スポンサーサイト

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

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

 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の状態遷移が違うときサンプルの方法では上手くいきません。かといって、入力記号に結び付けるのも、有限オートマトンと関数を結びつけるのも、本来の意味から考えて間違いだと思います。これは、オブジェクト指向プログラミングでよくあるジレンマです。
 無暗にデータと関数を結びつけると本質が見えなくなります。従って、あえてオブジェクト指向プログラミングらしく実装しない方が良いときもあります。ただし、オブジェクト指向プログラミングで考えるという行為を否定しているのではありません。オブジェクト指向プログラミングで実装したほうがわかりやすいこともあります。
 今回は有限オートマトンしか実装していません。しかしながら、ミーリー型機械、ムーア型機械、チューリングマシン、非決定性有限オートマトンなどの性質を学びたい場合、オブジェクト指向プログラミングにしてみると、各概念の差異と共通点が良く見えてきます。従って、非オブジェクト指向とオブジェクト指向の両方で実装して、学習するとよいと思います。
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。