構造化プログラム定理：制御構造の基本原理

中核となる制御構造

この定理は、より小さな計算上の作業（しばしばサブプログラムまたはモジュールと呼ばれる。サブプログラムも参照）を組み合わせて、より大きな作業を構成するための標準的な3つの方法を示す。これらは構造化されたコードの構成要素である。

• 順次：あるコード片を実行し、続いて別のコード片を順番に実行する。
• 選択：条件に基づいて、代替となるコード片の間から一つを選ぶ（if/then/else）。
• 反復：条件が満たされるまでコード片を繰り返す（whileやforなどのループ）。

これらの構造だけを用いても、本来は任意の跳躍命令やgoto文で実装される計算可能な振る舞いを、プログラムはすべて表現できる。この等価性こそが定理によって形式化される内容であり、制御フローの標準形を与える。

歴史と理論的背景

一般にコラド・ベームとジュゼッペ・ヤコピニに帰されるこの成果は、1966年に発表され、計算に関するそれ以前の数学的研究と密接に結び付いている。これはアルゴリズムの形式的記述、およびスティーヴン・クリーネの研究に関連する考え方を含む再帰理論の成果など、標準形に関する結果を基礎としている。またこの定理は、当時のプログラムの記述・表現方法に影響を及ぼしたフォン・ノイマン型アーキテクチャのような初期コンピュータ・アーキテクチャという実用的背景にも位置付けられる。

含意と限界

存在定理として、この定理はgoto形式の跳躍が表現力のためには必要ではないことを示す。すなわち、順次・選択・反復を提供する高水準言語は、任意の跳躍を持つ言語とチューリング等価である。実際には、跳躍を除去する変換には追加の変数の導入やコードの複製が必要になる場合があり、証明で用いられる直接的な変換が、実際のプログラムにおいて常に最も読みやすく効率的とは限らない。こうした技術的な留保は、この定理が構造化プログラミングを支持する一方で、書き換えたすべての版があらゆる文脈で望ましいと主張するものではないことを意味する。

実用上の重要性と遺産

この定理はプログラミング言語の設計と、より広いプログラミングのコミュニティに影響を与え、1960年代後半から1970年代にかけての構造化プログラミング運動や、無制限なgotoの使用に対するエドガー・ダイクストラの批判のような影響力ある立場に寄与した。その永続的な価値は概念的なものである。すなわち、どの基本的制御形式が十分であるかを明確にし、教育とコーディング・スタイルを導き、コンパイラ設計およびプログラム検証技法に情報を与える。

関連事項

変種や後続の研究では、単一入口・単一出口の構造、構造化フローチャート、例外・コルーチン・継続などの機能と構造化制御との相互作用が検討されている。理解しやすい解説と歴史的背景については、この主題、およびソフトウェア工学理論における役割を扱う入門書や概説を参照されたい（項目、参考文献、背景）。