制御構造

制御構造は、コンピュータ・プログラミング言語、特に手続き型プログラミングや命令型プログラミングにおいて、ループや飛び越しなどといった、手続き中の実行順を順次実行から変化させたり、サブルーチン呼出しやその戻り、などといった制御を行う「文 」などの構造である。

制御構造の種類は言語によって様々だが、典型的には以下のようなものがある。

無条件に実行箇所を移動する
何らかの条件の成立・不成立に従い、ブロックの実行・不実行を選択する
ブロックを繰り返し実行する
ジャンプの一種だが、その続きに戻れるもの
継続
プログラムの停止割り込みとシグナルは制御フローを変化させる別の機構であり、サブルーチンに似ているが、通常は言語内からではなく外部のイベントなどの結果として非同期に発生するものである。自己書き換えコードも副作用によって制御フローを変化させることができる。割り込み的なものを扱うことができるプログラミング言語はいくつかある。自己書き換えをプログラマが明示的に扱えるプログラミング言語はあまりないが、初期化の時だけ特別扱いが必要といったコードの最適化に自己書き換えを利用する、処理系の実装上のテクニックといったようなものもある。機械語において制御構造に相当するのは分岐命令で、通常は連続的にカウントが進められるプログラムカウンタを、不連続に変更する命令である。ほぼ全てのプロセッサは分岐命令を持つ。また、サブルーチン呼出しをサポートする命令を持つプロセッサが多い。全くハードウェアによるサポートが無いと、サブルーチン呼出しに面倒なトリックが必要なことがある。一方で前述のような、ループの処理を直接サポートするような命令を持つプロセッサは、専用命令として積極的に持つものもあるが、一般にはあまり多くなく、特にいわゆるRISCでは避けられる。そのため、コンパイラのコード生成は制御構造からジャンプ命令等を適宜組み合わせたコードを生成するように実装される。

1. 原始的な機能
---------

1.1. ラベル
--------

ラベルとは、コード中の固定の位置を示す何らかのシンボルであり、gotoの飛び先や、breakで抜ける対象として参照される。GCC拡張であるが、void * ポインタの値として扱うこともできる。

行番号は一部の言語でラベルの一種として使われ、負でない整数がソースコードの各テキスト行の先頭に置かれる。行番号を使用する言語では、連続で実行される文には行番号が増えるように行番号を与える必要がある、とBASICしか知らない者は誤解しているが、FORTRANにはそのような制限は無い。BASICで行番号が昇順なのは、テキストの編集にフルスクリーンエディタが一般的ではなかった時代のラインエディタのみによる編集では、行番号に従ってシステムが並べ直してくれたほうが便利だったからであり、「行番号が増えるように行番号を与える必要がある」というのは本末逆転である。例えば BASIC では次のようになっている。

10 LET X = 3 20 PRINT X

CやAdaといった言語のラベルは識別子であり、文の前に書かれ、その直後にコロンが書かれる。例えば C では次のようになる。

Success: printf ;

Algol 60 言語はラベルとして識別子も非負整数も使用可能だが、多くのAlgol系言語では非負整数をラベルとして許容していない。

1.2. goto
---------

//goto// 文は最も典型的な無条件のジャンプである。キーワードとしては大文字だったり小文字だったり空白が入ってgo toだったり、単にgoだったりするが、その構文はだいたいのものが以下のようになっている。

goto //label//

goto 文の実行により、その次に実行する文は、ラベルが示す箇所の直後の文となる。

1.3. サブルーチン
-----------

サブルーチンには、手続き、ルーチン、プロシージャ、関数、メソッドなど様々な名称がある。

1950年代、コンピュータのメモリは非常に小さかったため、サブルーチンの第一の目的はプログラムのサイズを削減することにあった。サブルーチンとして書かれたコードをプログラム内のあちこちから使用することでプログラム全体のコードサイズを削減したのである。現在ではサブルーチンはプログラムを構造化するために使われる。すなわち、特定のアルゴリズムを分離したり、特定のデータにアクセスするメソッドを隠蔽したりする。多数のプログラマが共同でプログラム開発をする場合、サブルーチンはある種のモジュール性を提供し、仕事の分割点の役割も果たす。

サブルーチンに引数があればさらに便利になる。多くのプログラミング言語には平方根を求めるサブルーチンが組み込まれており、引数として平方根を求めたい数を与えることができる。

プログラミング言語によっては再帰呼び出しが可能である。つまり、サブルーチンが直接的あるいは間接的に自分自身を呼び出すことができる。クイックソートや木構造を探索するアルゴリズムなどは再帰を使った方が素直に表現できる。

サブルーチンを使用すると、引数の受け渡し、サブルーチン呼び出し、コールスタック処理、サブルーチンからの復帰などのオーバヘッドによりプログラム性能が若干低下する。実際のオーバヘッドはハードウェアおよびソフトウェアのアーキテクチャに依存する。コンパイラによってはインライン展開を効果的に使用してオーバヘッドの低減を図るものもある。

プログラミング言語によってはサブルーチンの物理的な最後尾に到達しないとサブルーチンから復帰できない方式のものもある。他の言語には return や exit 文がある。これはサブルーチンの最後尾への分岐と等価であり、制御構造を複雑化するものではない。必要に応じて複数のそれらの文をサブルーチン内に置くことができる。

2. 必要最小限の構造化制御フロー
-----------------

1966年、Böhm と Jacopini は Communications of the ACM 誌で論文を発表し、goto を使って書かれたプログラムが選択  とループ  のみを使って goto を使わずに書き換えられることを示した。後に彼らは選択もループで置き換え可能であることを示した。

非常に良く誤解されているが、そのような書き換えが可能という事実は、単に「機械語で書けば何でも書ける」という事実と同程度の意味しかなく、それが望ましいということは全く意味しない。理論的にはコンピュータは一種類の命令、たとえば「subtract one number from another and branch if the result is negative」さえあれば何でもできるが全く実用的ではなく、実際のコンピュータは多数の命令を備えているということと類似している。

Böhm と Jacopini の論文は全てのプログラムから goto 文を無くすことができることを示した。

また、他の研究により入り口と出口がそれぞれひとつになっている制御構造が他の構造よりも理解し易いということが示された。特にそのような制御構造はプログラムの任意の箇所に制御構造を乱すことなく挿入可能な点が有利とされた。

しかし実は、「理論に従ってgoto 文を無くしたプログラム」が「理解し易い」ものであるか否かは不明であり、実際のところ全くそのようにはならないのであるdate=2020年7月。

3. 構造化された制御要素
-------------

以下ではなぜかキーワードに変にこだわっているが、そういった字句にこだわるのではなく、構文として総合的に捉えれば、たいしてこだわる意味はない。この節冒頭に挙げたリンク先の各記事を参照。

終了キーワードがない言語 Algol 60、C、C++、Haskell、Java、Pascal、Perl、PHP、PL/I、Python、PowerShellなど。この種の言語は文の並びをひとまとめにする何らかの方法を持っている。
Algol 60、Pascal: begin ... end
C、C++、Java、Perl、PHP、PowerShell: 中括弧を使用 { ... }
PL/1: DO ... END
Python: インデントのレベルを使用
Haskell: インデントのレベルか中括弧を使用でき、それらを自由に混合可能 終了キーワードがある言語 Ada、Algol 68、Modula-2、Fortran 77、Visual Basic など。終了キーワードはいくつかの種類がある。
Ada、Fortran 90: 終了キーワードは end + 空白 + 開始キーワード。例えば、if ... end if, loop ... end loop
Algol 68: 開始キーワードを逆に綴る。例えば、if ... fi, case ... esac
Fortran 77: 終了キーワードは end + 開始キーワード。例えば IF ... ENDIF, DO ... ENDDO
Modula-2: 開始キーワードに関わらず常に END という終了キーワードを使う。
Visual Basic: 制御構造毎に固有の終了キーワード。If ... End If; For ... Next; Do ... Loop; While ... Wend

4. 選択
-----

4.1. if-then-
-------------------

条件式と条件付き実行は、条件節の評価結果の真偽によって異なる式やブロックを選択実行する。

IF..GOTO 非構造化言語に見られる形式で、典型的な機械語命令をそのまま言語に持ってきたものである。条件が真なら指定されたラベルへジャンプ  する。 IF..THEN.. ジャンプに限らず、単純な文や入れ子になったブロックを THEN というキーワードの後に置くことができる。構造化された形式である。 IF..THEN..ELSE.. 上と同じだが、条件が偽の場合の動作も記述できる。これが最も一般的な形式で、様々なバリエーションがある。終了キーワード ENDIF が必要な場合とそうでない場合がある。C言語やそこからの派生言語では終了キーワードは不要で、'then' に相当するキーワードも不要なことが多いが、その場合は条件式を括弧で囲む必要がある。

4.1.1. elseif
-------------

「宙ぶらりんelse問題」も関係するのだが、文法の設計によっては、 IF cond THEN ... ELSE IF cond THEN ... ELSE IF cond THEN ... FI FI FI のように、「複数の場合に対する場合分け」の単純な多分岐であるにもかかわらず、どんどんネストが深くなるような書き方をせざるをえない場合がある。これは ELSEIF のようなキーワードの導入で解決できる。elseif, elsif, elif など言語によるバリエーションが多いので、テキストエディタによるリアルタイムなシンタックスハイライトが非常に有効である。言語によっては else if という「2語から成るキーワードのようなもの」という設計のものもある。

あまり一般的でないバリエーションとして、以下のような例がある。

FORTRANなどの一部の言語では、3方向の分岐を扱う「算術IF文」があり、数値を正か、ゼロか、負か判定して処理を分岐させる。
多くの関数型言語などではif文が関数や式として実装されており、そのようなifは評価した式の結果を返す。
一部の言語ではif文が演算子の様に実装されており、例えばC言語の条件演算子がある。
PerlではC言語風の if だけでなく、when と unless や、コードの後に条件式が来る if がある。
Smalltalkでは言語組込みの機能としてではなく、ifTrue と ifFalse というメッセージに手続き引数を与えることで、条件付き実行ができる。一般論として、関数の引数を積極評価してしまう言語では、条件実行のようなものを関数にできない。遅延評価のような機構が何かあれば、条件実行を特に言語機能にしなくても、引数を遅延評価する関数によって、条件実行もできる。

4.2. パターンマッチング
--------------

ここではOCamlの例を挙げる。

match fruit with| "apple" -> cook pie| "coconut" -> cook dango_mochi| "banana" -> mix;;

4.3. switchとcase
----------------

switch文は、指定された値を指定された定数群と比較し、最初に一致した定数に従ってその後の処理を決定するものである。一般にどの定数とも一致しなかった場合を想定したデフォルト動作を 'else' や 'otherwise' などとして用意しておく。ルックアップテーブルなどを使ったコンパイラ最適化が可能である。動的プログラミング言語では比較対象が定数式である必要はなく、パターンマッチに拡張することが可能である。例えば下記のシェルスクリプトの例で '*)' は任意の文字列にマッチングする正規表現を使ってデフォルト動作を指定している。SQLの decode のように、関数のような見た目のものもある。



5. ループ
------

ループはソースコード上で1回だけ書かれた文の並びを連続して複数回実行することである。ループの「中」のコードは指定回数実行されるか、指定されたコレクションの各要素に対応して実行されるか、何らかの条件が成立するまで繰り返し実行される。無限に繰り返されることもある。

SchemeやHaskellのような関数型言語では、ループより再帰呼び出しや不動点コンビネータを使用してプログラミングするのが普通である。末尾再帰は再帰呼び出しの特殊ケースであり、容易にループに変換できる。

5.1. カウント制御ループ
--------------

指定された回数だけブロックを繰り返すループである。本来、その回数だけを指定するなどもっと抽象化されているべきであるが、「ループ変数」などを指定するなど煩雑さがともなっているものが多い。以下の例で N が 1 より小さい場合、ループ本体は全く実行されない。カウントは多くの場合増える方向だけでなく減る方向にも設定可能で、1回に増える量も 1 以外に設定できることが多い。

FOR I = 1 TO N for I := 1 to N do begin xxx xxx NEXT I end;

DO I = 1,N for  { xxx xxx END DO }

多くのプログラミング言語では、カウント制御ループでは整数のみが使われる。浮動小数点数はハードウェアの制限により精度に限界がある。従って次のようなループでは、for X := 0.1 step 0.1 to 1.0 do 繰り返し回数が9回の場合と10回の場合がある。これは丸め誤差やハードウェアやコンパイラの違いによって変わってくる。さらに言えば、Xに繰り返し加算すると丸め誤差が累積していき、想定した数列である 0.1, 0.2, 0.3, ..., 1.0 からかけ離れていくことがありうる。

5.2. 条件制御ループ
------------

条件が指定されており、その式を評価した結果が真であればループを繰り返す。条件のテストがループの先頭にある場合と最後にある場合がある。前者の場合、ループ本体を全く実行しないことがありうるが、後者の場合は少なくとも1回はループ本体を実行する。

DO WHILE  repeat xxx xxx END DO until test;

while  { do xxx xxx } while ;

コントロールブレイクは通常のループ内で値の変化を検出する手段として使われ、値のグループの処理のトリガーとなる。ループ内で変化する値をキーで監視し、可変な値に関連したグループイベント処理へとプログラムのフローを変換する。

DO UNTIL  IF new-zipcode <> current-zipcode display_tally

current-zipcode = new-zipcode zipcount = 0 ENDIF

zipcount++ LOOP

5.3. コレクション制御ループ
----------------

一部のプログラミング言語では、明示的に配列や集合やコレクションの全要素に対応してループを回すことができる。

someCollection do: [:eachElement |xxx].

for Item in Collection do begin xxx end;

foreach  { xxx }

foreach someArray { xxx }

foreach  { xxx }

Collection coll; for  {}

foreach  { xxx }

$someCollection | ForEach-Object { $_ }

forall 

5.4. 汎用の繰り返し
------------

C言語の for 文や Common Lisp の do のような汎用性の高い繰り返し要素を使えば、前述の各種ループもその他のループも実現できる。例えば、複数のコレクションを並列に回したりできる。もっとも、個別のループ構造がある場合、そちらを使った方がコードの目的をより明確に表現できるとも言える。

5.5. 無限ループ
----------

場合によっては無限にループする方がプログラムに適していることもあるし、何らかのエラーが発生するまでループするという場合もある。実際、イベント駆動型プログラムはイベント制御ループを永遠に回り続け、プロセスが操作者によって終了させられたときだけループを停止する。

ただし一般には、無限ループはプログラミングのミスで発生する。すなわち、ループ終了条件がループ内で全く発生しないことが原因で意図しない無限ループとなる。

5.6. 次の繰り返しへの継続
---------------

ループ途中でループ処理を中断してループの先頭に戻り、次の繰り返しを開始したい場合がある。言語によってはこれを実現する continue とか skip、next といった文を用意している。その効果は最も内側のループ本体の実行を途中で止め、そのループの次の繰り返しを最初から行う。もしそのときの実行が最後の繰り返しであった場合、ループそのものを早期に終了させるのと同じことになる。

5.7. 現在の繰り返しの再実行
----------------

Perl や Ruby といった一部の言語では redo 文によって現在の繰り返しを先頭から再実行することができる。

5.8. ループの再実行
------------

Ruby では、retry 文でループ全体を最初から再実行することができる。

5.9. ループからの早期脱出
---------------

カウント制御型ループを使って配列上のデータを検索している際に、必要な要素を見つけたら即座にループから抜け出したいという状況がありうる。プログラミング言語によっては break とか exit、last といった文を用意していて、現在のループを即座に抜けてそのループの直後の文に制御を転送する機能を持っている。サブルーチン内のループで return を使えば、入れ子になったループからも脱出することになる。多次元配列を入れ子になったループで検索している場合、若干複雑になる。

以下の例はAdaを使ったものである。Ada は「ループからの早期脱出」と「途中にテストのあるループ」の両方をサポートしている。どちらもよく似ているが、コードを比較すればその違いがわかる。いずれにしても、汎用の制御構造であるif文との組み合わせによるものか、専用の制御構造によるものか、という違いでしかない。

with Ada.Text IO; with Ada.Integer Text IO;

procedure Print_Squares is X : Integer; begin Read_Data : loop Ada.Integer Text IO.Get; exit Read_Data when X = 0; Ada.Text IO.Put ; Ada.Text IO.New_Line; end loop Read_Data; end Print_Squares;<WtXmlEndTag />

Python は break でループを早期脱出したか否かに依存して、実行されるブロックを指定できる。以下はその例である。

for n in set_of_numbers: if isprime: print "Set contains a prime number" break else: print "Set did not contain any prime numbers"

Python では for 文も while 文もこのような else 節を使うことができる。else 節は早期脱出が発生しなかったときのみ実行される。

5.10. ループ変化条件とループ不変条件
---------------------

ループ変化条件とループ不変条件は、ループの正しさを表すのに使われる。

現実的には、ループ変化条件とは非負の初期値を持つ整数式である。変化条件はループを回るたびに減少しなければならないが、正しいループ実行の間は負の値になってはならない。ループ変化条件はループが終了するであろうことを保証するのに使われる。

ループ不変条件は、ループを回る前と各反復において真でなければならない表明である。すなわち、ループが正しく終了するには終了条件とループ不変条件が共に真でなければならない。ループ不変条件は、ループ実行中にループの具体的属性を監視するのに使われる。

Eiffelなどのプログラミング言語でループ変化条件とループ不変条件がサポートされている。Javaではアドオンである Java Modeling Language  という仕様で同様のものをサポートしている。

5.11. サブ言語としてのループ
-----------------

一部のLISP方言では、ループを記述するための幅広いサブ言語を提供している。初期の例としては Interlisp の Conversional Lisp がある。Common Lisp の loop マクロもそのようなサブ言語になっている。

5.12. ループ機能の比較表
---------------



6. 構造化非局所制御フロー
--------------

多くのプログラミング言語、特に動的なプログラミングスタイルを指向した言語では、「非局所制御フロー」の構造を持っている。これを使うと実行の流れは現在のコンテキストから離れ、事前に定義された場所から続行される。「条件」、「例外」、「継続」の3種類の典型的な非局所制御構造がある。

6.1. 条件
-------

PL/I は標準で22種類の条件をサポートし、これを発生させ、ON //condition// action; で解釈することができる。プログラマは独自の条件を定義することもできる。

構造無しの IF 文のように action にはひとつの文しか書けないので、多くの場合 GOTO 文を使って制御フローを継続する必要がある。

しかし、実装によってはこれは空間と時間を無視できないくらい浪費する。多くのプログラマは条件を使わないようコードを書くことが多かった。

典型的な文法例:

ON //condition// GOTO //label//

6.2. 例外
-------

最近の言語はGOTO文を使用せずに例外処理を行う構造化された制御構造を備えている。

try { xxx1 // この中のどこかで以下を使用する xxx2 // throw someValue; xxx3 } catch  { // someClass の場合をキャッチ actionForSomeClass } catch  { // someType の場合をキャッチ actionForSomeType } catch  { // 既にキャッチされていない任意の値をキャッチ actionForAnythingElse }

任意の catch 節が上記の例では使用されている。D言語、Java、C#、Python では try 構造に finally 節を追加することができる。try 部分を離れる際にはどういう理由であっても必ず finally 節が実行されることが保証されている。これは処理を終了する際に何らかの高価な資源を解放しなければならない場合に便利である。

FileStream stream = new FileStream ; // C# の例 try { return ProcessStuff; // 例外を発生する可能性がある } finally { stream. Close; }

この例は非常に一般的であり、C# ではこのための特別な構文がある。

using ) { return ProcessStuff; // 例外を発生する可能性がある }

上記の例の using ブロックを離れるとき、コンパイラが自動的に stm オブジェクトを解放する。Pythonの with 文やRubyの File.open へのブロック引数も同様の効果がある。

このような言語はいずれも標準の例外を定義し、それらがどのような状況で発生するかを定義している。ユーザーは独自の例外を発生させることもできる。

特定の throw にマッチする catch がない場合、マッチする catch が見つかるまで入れ子構造を遡り、サブルーチン呼び出しを遡る。メインプログラムまで遡っても対応する catch がない場合、プログラムは適切なエラーメッセージを出力して停止する。

AppleScript スクリプト言語 は "try" ブロックにいくつかの情報を提供する。

try set myNumber to myNumber / 0 on error e number n from f to t partial result pr if  then display dialog "You must not do that" end try

6.3. 継続
-------

6.4. 非局所制御フローの比較表
-----------------



7. 提案された制御構造
------------

ドナルド・クヌースは1974年の論文 "Structured Programming with go to Statements" でそれまでの制御構造でカバーされていない2種類の状況を提示し、それを実現する制御構造を例示した。他にも以下に示すような提案がある。

7.1. 途中にテストのあるループ
-----------------

これは1972年にダールが提案した。

loop loop xxx1 read;while test; while not atEndOfFile; xxx2 write;repeat; repeat;

もし //xxx1// が省略されたら、テストが先頭にあるループとなる。もし //xxx2// が省略されたら、テストが最後尾にあるループとなる。//while// が省略されれば無限ループとなる。このような一種類の制御構造で、必要な多くのタイプのループのパターンを表現できることが示されたことから、以降の言語ではこのような汎用性の高いループ構造を持つものもある。ありうべき派生としてループ内に複数の while テストを配置することを許すことが考えられるが、その場合は後述の exitwhen の方が適切である。

一般に、任意のループ構造と、条件分岐とbreakを組み合わせて、同様のプログラムを書ける。

while  { xxx1if break xxx2 }

Adaでは、上記のループ構造の代替として標準の無限ループ内で exit when節を使うことで同様の制御構造を実現できる。

with Ada.Text_IO; with Ada.Integer_Text_IO;

procedure Print_Squares is X : Integer; begin Read_Data : loop Ada.Integer_Text_IO.Get; exit Read_Data when X = 0; Ada.Text IO.Put ; Ada.Text IO.New_Line; end loop Read_Data; end Print_Squares;<WtXmlEndTag />

ループの命名は必須ではないが、ループの入れ子で外側のループまで脱出させることができる。

7.2. 複数早期脱出と入れ子ループからの脱出
-----------------------

これは 1974年、Zahn が提案した。ここではそれを若干修正したものを示す。

exitwhen EventA or EventB or EventC; xxxexits EventA: actionA EventB: actionB EventC: actionCendexit;

exitwhen は //xxx// 内で発生しうるイベントを指定するのに使い、イベントはイベント名を文として使用すると発生する。イベントが発生すると対応するアクションが実行され、その後 endexit 後の処理に移る。この制御構造はある状況を識別する部分と、その状況でとるべきアクションを明確に区別することができる。

exitwhen は C++ 言語の try/catch 構造と概念的によく似ているが、サブルーチン呼び出しを超えたり任意の値を渡したりしないので、より効率的と思われる。また、コンパイラは指定されたイベントが全て発生する可能性があり、それらにアクションが対応しているかどうかをチェックできる。

以下の単純な例は2次元配列から特定の要素を取り出すものである。

exitwhen found or missing;for I := 1 to N dofor J := 1 to M doif table[I,J] = target then found; missing;exits found: print ; missing: print ;endexit;

7.3. COMEFROM
-------------

Datamation誌に掲載された記事で、R. Lawrence Clark は COME FROM 文を提案し、面白い例をいくつか提示した。それ自体は「GO TO論争に寄与する」と称したジョークであるが、ジャーゴンファイルの記事が指摘しているように、たとえばFortranのDO文は「そこで指定した行番号のある行からそこに飛ぶ」という一種のCOMEFROMであることなど、制御構造の問題に面白い視点を与えるものではある。setjmp/longjmpと関連させた指摘もある。

COMEFROM文はINTERCALという難解プログラミング言語に実装された。

8. 脚注
-----

9. 参考文献
-------

Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961.

10. 関連項目
--------

分岐命令
goto文
サブルーチン
イベントループ
再帰呼び出し
スパゲティプログラム
構造化プログラミング
関数型プログラミング
制御抽象化
制御フローグラフ
コルーチン
循環的複雑度
フローチャート

11. 外部リンク
---------

[1]
[2]
[3]
[4]