2007年01月23日
川俣晶の縁側PCホビイズムtotal 3218 count

【テスト文書】知力勝負! goto文類似構文を全て封じた構造化パズル・プログラミング!!

Written By: 川俣 晶連絡先

 PCホビイズムメーリングリストには、既にいくつかの文書を送信しています。

 この文書は、一般性のある読み物なので、オータムマガジンにも掲載しておきます。

 PCホビイズム(メーリングリスト含む)に関しては、PCホビイズム暫定ポータルをご覧ください。

以下本文 §

 以下は、PCホビイズムにおける「面白さのお裾分け」の実践テストとして書かれた文書です。

知力勝負! goto文類似構文を全て封じた構造化パズル・プログラミング!!

概要:

構造化プログラミングとは、本来『1つの入り口と1つの出口を持つようなプログラムは、「順次・反復・分岐」の3つの基本的な論理構造によって記述できる』というものですが、それを字義通りに守ってプログラムを書くのは知力勝負になって、パズル的な面白さがあるっす。

対象読者:

プログラミングに興味のある人

書いた人:

川俣晶 (autumn@piedey.co.jp)

● 構造化プログラミングとは

 WikiPediaより引用します。

ダイクストラは、大規模化したプログラムを効率よく記述しプログラム設計上のミスが起こりづらいようにするための方法論を検討した。その結果1960年代後半に、次の構造化定理を証明し、構造化プログラミングを提唱した。

・構造化定理

1つの入り口と1つの出口を持つようなプログラムは、「順次・反復・分岐」の3つの基本的な論理構造によって記述できる

・構造化プログラミングの構成要素

順次 -- 順接、順構造とも。プログラムに記された順に、逐次処理を行なっていく。プログラムの記述とコンピュータの動作経過が一致するプログラム構造。

反復 -- 一定の条件が満たされている間処理を繰り返す。

分岐 -- ある条件が成立するなら処理Aを、そうでなければ処理Bを行なう。

以上三つの論理構造を元にして、サブルーチンに機能を抽象化する。

「サブルーチン」とは不変契約をみたす関数や手続き、すなわち「同じ値を渡せば常に同じ結果が得られる」 ことを満たすような部分処理を指す。

※ ここで「同じ値を渡せば常に同じ結果が得られる」というサブルーチンの制約は考えないでおこう。これを言い出すと、乱数を返すサブルーチンや、キーボードから入力するサブルーチンは作れなくなってしまう。ちなみに、ここでの目的はプログラミングを題材にした面白いパズルゲームを提唱することであり、正しい構造化プログラミングの実践ではない。そのような目的に沿った解釈の変更はあり得る。

● だが、これだけでは上手く書けない

 今時の実用プログラム言語では、上記のルールは完全に守られていない。

 ループの中途脱出を行うbreak文のような構文は必須のものとされているし、途中で実行を打ち切ってしまうreturn文のような構文もあって出口は1つとは限らない。

 では、break文やreturn文を封印して、より本来の構造化プログラミングを目指すと何が起こるだろうか。

 それは、初期の構造化プログラミング言語を使った経験のある人ならお分かりだろう。工夫を凝らすことで確かに意図した機能は書けるのだが、それは本質的に素直な

分かりやすいコードにはならないのである。

 それどころか、コードの分かりやすさという以前に、どう書けば良いかすら分からず、頭を捻ることも珍しくなかった。

 それだけ厳しい制約だったといえる。

 だが、その制約をゲームのルールと考えたらどうだろうか。

 成果を出すことを目的とせず、困難なハードルと知力勝負を行うことを目的とした頭脳スポーツとしてなら、これは面白い体験になるかもしれない。

● ルール

 暫定的にCによるルールのみ以下に示す。

・関数の定義に対して適用する

・goto文封印

・ループ脱出のbreak文封印

・continue文封印

・値を返す関数の最後に書く1つを除き、return文封印

・forやwhileの条件式の中でカンマ演算子は使わない (実質的に式の中に複雑な処理を納めることができてしまうため)

・無限ループによって、終わることがない関数はルール違反と見なす (出口は1つであって、0個は許されない)

● 遊び方

・手頃なCのソースコードを探し、上記のルールに従い書き換えてみる

・上記のルールを適用すると書き換えが困難な関数やプログラムのソースコードを探してきて、構造化プレイヤーに挑戦する

・既に書き換えが完了しているソースコードに、よりエレガントな別の書き換えがないか、模索する

・挑戦や成果は、PCホビイズムメーリングリストを通じて、広く知らしめる

● 例1

書き換え前: (break文がある)

void sample()

{

    for(;;)

    {

        長い処理1

        if( 条件式 ) break;

        長い処理2

    }

}

書き換え後の一例: (break文がない)

void sample()

{

    int flag = 1;

    do

    {

        長い処理1

        if( 条件式 )

        {

            flag = 0;

        }

        else

        {

            長い処理2

        }

    } while(flag)

}

※ フラグ変数を導入すれば書き換えはできるが、単なるループ制御だけで変数が増えるのは美しくない。このサンプルソースでは具体的に示されない長い処理1/2や条件式が具体的に示される事例では、それらを工夫してフラグ変数抜きで同等の機能を実現できないだろうか? いずれにしても、まずは書き換えるべきソースコードを探してくることから開始だ!

● 例2

書き換え前: (出口が4つある)

void sample()

{

    if( 条件式1 ) return;

    長い処理1

    if( 条件式2 ) return;

    長い処理2

    if( 条件式3 ) return;

    長い処理3

}

※ 答えは無し。一般論としての書き換えと、個別のソースコードごとの最適な書き換えがあり得る。

● 例3

書き換え前: (goto文がある, 出口が2つある)

void sample()

{

    if( 条件式1 ) goto error;

    長い処理1

    if( 条件式2 ) goto error;

    長い処理2

    if( 条件式3 ) goto error;

    長い処理3

    return;

error:

    エラー処理

}

※ これも答えは無し。同様に、一般論としての書き換えと、個別のソースコードごとの最適な書き換えがあり得る。

● ヒント

 役に立つかどうか分からないが、ヒントだけ。特定の条件の時に実行させたくないコードがあるにも関わらず綺麗に記述できない場合の対処方法のアイデア。

・無害なコード

 そのコードが実行されても何の害も発生させない方法を模索する。(例: 足し算がどうしても避けられないなら、そのケースだけ足す数を0にする方法を考えてみる)

・打ち消し

 意図しない打ち消し可能な処理が実行されてしまう場合は、後から打ち消しのコードを実行させることで、実行されてしまうことを許容する。(例: して欲しくないXOR論理演算が行われる場合は、あとからもう1回余計なXOR演算を行うことで、本来意図した値に戻せる。足し算の場合は、引き算で本来意図した値に戻せる)

終わり

Facebook

このコンテンツを書いた川俣 晶へメッセージを送る

[メッセージ送信フォームを利用する]

メッセージ送信フォームを利用することで、川俣 晶に対してメッセージを送ることができます。

この機能は、100%確実に川俣 晶へメッセージを伝達するものではなく、また、確実に川俣 晶よりの返事を得られるものではないことにご注意ください。

このコンテンツへトラックバックするためのURL

http://mag.autumn.org/tb.aspx/20070123151146
サイトの表紙【PCホビイズム】の表紙【PCホビイズム】のコンテンツ全リスト 【PCホビイズム】の入手全リスト 【PCホビイズム】のRSS1.0形式の情報このサイトの全キーワードリスト 印刷用ページ

管理者: 川俣 晶連絡先

Powered by MagSite2 Version 0.34 (Alpha-Test) Copyright (c) 2004-2018 Pie Dey.Co.,Ltd.