構造化定理
1970年代にIBMの研究員ハーラン・ミルズは、自身の構造化プログラミングにおいて、構造化されたプログラム(structured program)と呼ばれるものを基本的なプログラム{順次(sequence)、選択(ifthenelse)、反復(whiledo)}の組み合わせたものとして定義した。基本プログラムの中には任意の分岐を作り出し複雑な制御構造をもたらすgoto文は含まれないが、そのgoto文を除いて任意のプログラムが構成できることを正当化する根拠がこの構造化定理(the structure theorem)である。
この定理はコラド・ベーム(Corrado Böhm)とジュゼッペ・ヤコピーニ(Giuseppe Jacopini)による1966年の論文に起源を持つと言われる。ベーム-ヤコピーニの論文は「その技巧的様式が原因で、論文は詳細に読まれるよりも明らかにより頻繁に引用されている」と評されることもあるものの、構造化プログラミングの支持者とともに「万人向けの評判」を享受した。
ベーム-ヤコピーニの定理の直接的応用は、構造化チャートに導入されている余分なローカル変数(訳注:ループ途中脱出用のフラグのことだろうか?)といくつかの重複コードという結果になったのかもしれない。後者の問題は、この状況で loop and a half problem と呼ばれている(訳注:なぜ後者の問題なのかは英語版に書かれていない)。Pascal はこれらの問題の両方に影響されており、エリック・S・ロバーツ(英語版)(Eric S. Roberts)によって引用された経験的研究に従っている。学生プログラマーであるロバーツは、いくつかの単純な問題(配列の中から1つの要素を検索する機能も含む)のために Pascal で適切な解法を公式化することに困難を感じた。ロバーツによって引用されたヘンリー・シャピロ(Henry Shapiro)による1980年の研究は、Pascal が提供する制御構造だけを使うと、適切な解法を得られた課題は20%だけだった。一方、ループの途中に return を書くことを許せば、この問題のために不適切なコードを書く課題は存在しなかった。
1973年、S.ラオ・コサラジュ(英語版)(S. Rao Kosaraju)は、任意の深さで multi-level break (多重ループから複数階層を一気に脱出できる break)を使えるようにすれば、構造化プログラミングにおいて余分な変数の追加を回避できることを証明した。さらにコサラジュは「プログラムの厳密な階層が存在する。
ここで T ( x → , y ) = 1 {\displaystyle T({\vec {x}},y)=1} となる y {\displaystyle y} が存在しないとき、右辺は未定義と解釈する。
原始再帰的関数はループプログラムによって計算可能であることが知られている。ループプログラムは、基本的な算術演算、大小比較、条件分岐(if-then-else)、(変数によってループ回数を指定する)計数ループ、からなる言語であり、ジャンプ命令(goto文)やbreak文のような機構を含まない。したがって、ループプログラムで記述されるアルゴリズムは構造化定理の求める条件を満たしている。
したがって、 f {\displaystyle f} を計算するには、次のような手続きを踏めばよい。
ここで、T と U を計算する箇所は、構造化定理の条件を満たすようなアルゴリズムに置き換えられる。したがって f {\displaystyle f} もまた構造化定理を満たすアルゴリズムによって計算可能である。