prepress-tips

形式手法モデル理論アプローチ３

最終更新：2008年10月16日 19:16

Bot(ページ名リンク)

- view

管理者のみ編集可

　perlを使った形式手法モデル理論アプローチのもっと実際的なサンプルを作る。

最終更新日時： 2008/10/16

perlで狼・山羊・キャベツの川渡し再考

Edit

perlで狼・山羊・キャベツの川渡し再考

オブジェクト指向で記述する方がわかりやすくて利便性も高い。
for文で構成した goal_seekerを追加し、若干のバグも修正した。

wgc3.pl

#- このプログラムは ？
#    狼・山羊・キャベツの川渡し問題を perlを使って 形式手法モデル理論アプローチで解く

{
    my $debug = 0; 
    msg( '狼・山羊・キャベツの川渡し問題：', $debug ? '  debug mode' : () );
    $Wgc::debug = $debug; GoalSeeker::type1( Wgc::InitialState() );
    msg( '  finished.', 'push any key' ); `pause`;
    exit( 0 );
}
sub msg { map do { print "$_\x0a"; }, @_; }

#- 問題を goal-seekerで 解く。
#    goal-seekerは 多くの問題に共通に利用できる。
{ package GoalSeeker;

#--  再帰呼出しで構成した goal-seeker  type1

sub type1 {
    my ( $state, $ready, ) = @_;
    $ready || ( $twice = {}, @StateSequence = () );
    ! $twice->{ $state->toString } && $state->constraint || return;
    $state->goal && ( $state->goal_lambda, return );
    $state->lambda();
    $twice->{ $state->toString } = 1; push @StateSequence, $state;
    map do { type1( $_, 1 ); }, map do { $state->Delta( $_ ); }, $state->Actions;
    pop @StateSequence; $twice->{ $state->toString } = undef;
    $state->lambda_back();
}

#--  for文で構成した goal-seeker  type2

sub type2 {
    my ( $initialstate, ) = @_;
    $twice = {}; @StateSequence = (); @StateStack = ();
    @States = ( $initialstate );
    for( my $state; $state = shift @States; backward() ) {
        ! $twice->{ $state->toString } && $state->constraint || next;
        $state->goal && ( $state->goal_lambda, next );
        forward( $state );
        @States = map do { $state->Delta( $_ ); }, $state->Actions;
    }
}
sub forward {
    my ( $state, ) = @_;
    $state->lambda(); $twice->{ $state->toString } = 1;
    push @StateStack, [ @States ]; push @StateSequence, $state;
}
sub backward {
    while( ! @States && @StateStack ) {
        $state = pop @StateSequence; @States = @{pop @StateStack};
        $twice->{ $state->toString } = undef; $state->lambda_back();
    }
}

#--  補助のルーチン  msg
sub msg { main::msg( @_ ); }

1; }

#- 問題を記述する。
#    川の左側を State とする。
{ package Wgc;

BEGIN { $debug = 0 ; @StateSequence = (); }

#--  状態  All, InitialState, FinalState, State, toString

sub All { "fwgc"; } # 全体
sub InitialState { @StateSequence = (); State( All() ); } # 初期状態
sub FinalState { State( "" ); } # ゴールの状態

sub State { # 状態のコンストラクタ
    bless { state => unique( $_[0] ) };
}
sub toString { $_[0]->{state}; }

#--  処理  constraint, goal, goal_lambda, lambda, lambda_back, Actions, Delta

sub constraint { # 守らなくてはいけないこと
    my $left = $_[0]->{state}; my $right = minus( All(), $left );
    $debug && msg( "? c: ".$_[0]->toString ); 
    my $attention = unique( $left =~ /f/ ? $right : $left );
    ! ( $attention =~ /g.*w/ || $attention =~ /c.*g/ );
}
sub goal { # ゴール
    $_[0]->{state} eq FinalState()->{state};
}
sub goal_lambda { # ゴールですること
    msg( "  ".join ' → ', map do { $_->toString; }, @StateSequence, $_[0] );
}
sub lambda { # 新しい状態で実行すること
    push @StateSequence, $_[0];
}
sub lambda_back { # 前の状態に戻す
    pop @StateSequence;
}
sub Actions { # どんなアクションが可能か？
    my $left = $_[0]->{state}; my $right = minus( All(), $left );
    split "", unique( $left =~ /f/ ? $left : $right );
}
sub Delta { # アクションを実行したあとの Stateは？
    my $left = $_[0]->{state}; my $action = "f$_[1]";
    my $r = State( $left =~ /f/ ? minus( $left, $action ) : $left.$action );
    $debug && msg( "* c: ".$_[0]->toString, "  a: $_[1]", "  c: ".$r->toString ); 
    $r;
}

#--  補助のルーチン  unique, minus, msg
sub unique { my $r = ""; for( sort split "", $_[0] ) { $r =~ s/($_|$)/$_/; } $r; }
sub minus { $_[1] ne "" && $_[0] =~ s/[$_[1]]//g; $_[0]; }
sub msg { main::msg( @_ ); }

1; }

Edit

「形式手法モデル理論アプローチ３」をウィキ内検索

人気記事ランキング

最近更新されたページ

急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！

形式手法モデル理論アプローチ ３

perlで 狼・山羊・キャベツの川渡し 再考

更新履歴

形式手法モデル理論アプローチ３

perlで狼・山羊・キャベツの川渡し再考