July 16, 2005

ロボットのプログラム

よく読む機械屋大学生さんのブログにロボットのプログラムで『switch~caseで条件分岐を書いてうまくいかない』という記事が書いてあったので、それについて思うことがあるので語ってみようと思います。

結論からいうと、ロボットみたいな分岐の多いプログラムはifやswitchをできるだけ少なくしたほうが資産価値が高いコードだと思います。とりうる分岐が多くなるごとにifやswitchが入っていると、後から読んでわけのわからんコードが増産されることになります。悲惨な場合はifやswitchがあるのに関わらず、関数や定数使わずコードに1とか2とかがベタ書きしてあるプログラムの場合で、そんなコードは捨てたくなります。

(方法論については続きをどうぞ)

ifやswitchを使わないでどうやって分岐を書くの?、ということですが、それにはオートマトン(状態遷移マシン)というものを使います。より具体的には関数ポインタとリスト構造を駆使して書きます。C言語で例を示してみたいと思います。

例えば

void some_branch(){
    switch(state_value)
        case CASE_1:
            /* some_op1 */
            break;
        case CASE_2:
            /* some_op2 */
            break;
        case CASE_3:
            /* some_op3 */
            break;
    }
}
という分岐があったとします。
これは以下のように書き換えることができます。
typedef struct state_t{
    void (*op)();
    int (**condition_functions)(struct state_t *current);
    int next_states_size;
    struct state_t **next_states;
} state_t;

int case1(state_t *current){/* return CASE1? */}
int case2(state_t *current){/* return CASE2? */}
int case3(state_t *current){/* return CASE3? */}

void op0(){/* do OP0 */}
void op1(){/* do OP1 */}
void op2(){/* do OP2 */}
void op3(){/* do OP3 */}

state_t state0, state1, state2, state3;

void make_transition(){
    static state_t *NEXT_STATES0[] = {&state1, &state2, &state3};
    static int (*CONDITIONS_STATE0[])(state_t *) = {case1, case2, case3};
    state0.op = op0;
    state0.next_states_size = 3;
    state0.next_states = NEXT_STATES0;
    state0.condition_functions = CONDITIONS_STATE0;

    /* Please code state1,2,3 like state0 */
}


state_t *transit(state_t *current){

    /* Next state transition */
    int i;
    for(i = 0; i < current->next_states_size; i++){
        if((*(current->condition_functions + i))(current)){
            current = *(current->next_states + i);
            break;
        }
    }

    /* Do some operation */
    current->op();

    return current;
}

void transition_driver{
    make_transition();

    state_t *current = &state0;
    while(TRUE){current = transit(current);}
}

表現としては冗長ですが、make_transitionのところを少し書き換えるだけで、簡単にコードを更新することかできます。また条件式や動作についても再利用することが可能です。エラーを防ぐ、また柔軟にプログラムの更新に対して対応するためにも、似たようなコードは一箇所に集めることが重要ではないかと思います。(サンプルプログラム)

細かい話をすると、このやり方ではNFAになってしまうので、効率はあがりません。速度が重要視されるならDFAに変換してから使うのがいいと思います。あとは自分でこのようなものを書くとシンドイので、状態遷移をテキストで書いて、LexやYaccを使う(LexやYaccの紹介)のが得策かもしれません。

ロボットだけでなく、CGIのような画面遷移がたくさんあるようなプログラムでのこの手法は有効だと思います。

16:37 fenrir が投稿 : 固定リンク | | このエントリーを含むはてなブックマーク | この記事をdel.icio.usでブックマーク | トラックバック
このエントリーのトラックバックURL: http://fenrir.naruoka.org/mt/mt-tb.cgi/409
コメント
コメントする









名前、アドレスを登録しますか?
(次回以降コメント入力が楽になります)
  • 匿名でのコメントは受け付けておりません。
  • 名前(ハンドル名可)とメールアドレスは必ず入力してください。
  • メールアドレスを表示されたくないときはURLも必ず記入してください。
  • コメント欄でHTMLタグは使用できません。
  • コメント本文に日本語(全角文字)がある程度多く含まれている必要があります。
  • コメント欄内のURLと思われる文字列は自動的にリンクに変換されます。