構造化定理と構造化プログラミングは、似ているけれど同じ話ではない

※本稿は私の理解の整理および備忘用に ChatGPT に書かせた記事です。

TL;DR　ベーム＝ヤコピーニの構造化定理は「表現できるか」の話。ダイクストラの構造化プログラミングは「人間が理解できるか」の話。両者は同じ三つの制御構造にたどり着くが、問題意識はかなり違う。

プログラミング史の入門では、よくこんな説明を見かけます。

「どんなプログラムも、順次・選択・繰り返しの三つで書ける。だから goto は不要で、構造化プログラミングが生まれた」

これは完全な間違いではありません。けれども、少し平らにしすぎた説明でもあります。ベームとヤコピーニの「構造化定理」と、ダイクストラの「構造化プログラミング」は、あとから見るときれいにつながる。しかし出発点は別です。前者はフローチャートや計算能力についての数理的な話で、後者は大きく複雑なプログラムを人間がどう理解し、どう正しさに近づけるかという設計論でした。

この記事では、その違いをざっくばらんに整理します。goto 論争だけでなく、段階的詳細化、階層化、抽象データ型、そしてオブジェクト指向への流れまで、少し寄り道しながらつなげてみます。

まず、構造化定理とは何か

ベーム＝ヤコピーニの論文は、1966年に Communications of the ACM に掲載された Corrado Böhm と Giuseppe Jacopini の “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” です。題名からもわかるように、もともとは「プログラマの作法」を説いたエッセイではなく、フローダイアグラム、チューリング機械、言語の形成規則に関する理論的な論文です。

俗にいう構造化定理は、ざっくり言えば、任意の計算可能な処理を、次のような構造で表せるという主張として広まりました。

  1. 順次：これをして、次にあれをする。
  2. 選択：条件によって、こちらかあちらを選ぶ。
  3. 繰り返し：条件が成り立つ間、同じ処理を繰り返す。

現代のプログラミング言語で言えば、順次実行、if / else、while / for のようなものです。これらの組み合わせだけで、goto を使った任意のフローチャートと同等の計算を表現できる、という理解が一般に「ベーム＝ヤコピーニの定理」として流通しています。

[2026-06-05 追記： 念のため、この「順次・選択・繰り返し」という説明は、後世に広く流通した要約であり、Böhm–Jacopini 論文そのものの定理文をそのまま言い換えたものではありません。Harel は 1980年の "On Folk Theorems" で、Böhm–Jacopini の結果を、補助的な Boolean 変数を許せば任意のフローチャートが、逐次合成・条件分岐・while-do からなる while-program と等価になる、という結果として整理しています。一方、Harel は同論文で、Mills はこの結果を未公刊の講義ノートで “The Structure Theorem” と呼び、多くの聴衆を集めた講義やセミナーで再証明・議論する事を通じ、それが大きく取り上げられることになった最大の功労者の一人と位置付けてもいます。総じて、構造化定理を Böhm–Jacopini に由来するものとして語ること自体には、少なくとも歴史的には一定の妥当性があるとの立場をここではとらせていただきます。Mills に帰さないことにご不満の向きもあるかと思いますが、どうぞあしからずご容赦ください。]

ただし、ここで大事な注意があります。

この定理は「そう変換すれば、プログラムが読みやすくなる」と言っているわけではありません。変換のために、元のプログラムの位置情報を保持する追加変数、いわばプログラムカウンタのようなものを導入すれば、たしかに一つの大きなループと分岐で振る舞いを再現できます。しかし、それはしばしば「構造化されたスパゲティ」になります。goto は消えたが、制御の意味は巨大な状態変数に押し込められただけ、ということが起こるわけです。

だから構造化定理を、実務上の教訓として読むなら、正確にはこう言うのがよいでしょう。

goto なしでも、計算能力の面では困らない。だが、goto を機械的に取り除けば良いプログラムになる、という意味ではない。

この一文が、構造化定理と構造化プログラミングを混同しないための出発点です。

ダイクストラの関心は「表現能力」ではなかった

ダイクストラの有名な書簡 “Go To Statement Considered Harmful” は1968年に Communications of the ACM に掲載されました。もとの投稿タイトルは “A Case Against the Goto Statement” だったと言われていますが、掲載時に現在の有名なタイトルになりました。

この短い文章でダイクストラが問題にしたのは、goto が「計算能力として必要かどうか」ではありません。彼の関心は、静的なプログラム本文と、時間の中で進行する実行過程との対応を、人間がどれだけ単純に追えるかでした。

プログラムは紙や画面の上では静的なテキストです。しかし実行時には、命令が時間順に進み、変数の値が変わり、条件によって道筋が分かれます。人間は静的な関係を把握するのは比較的得意ですが、複雑に時間発展する過程を頭の中で追うのは苦手です。だからこそ、プログラムの形と実行過程の対応をなるべく単純にする必要がある。ダイクストラの goto 批判は、この認知上の問題から出ています。

goto は、実行の現在地をどこへでも飛ばせます。自由である一方、その自由は「この行に来たとき、どういう経路で来たのか」「この変数はどんな条件を満たしているはずなのか」を追いにくくします。条件分岐やループなら、入り口と出口、成立している条件、ループ不変条件などを比較的局所的に考えられます。無制限なジャンプは、その局所性を壊しやすい。

ここが、ベーム＝ヤコピーニの定理との違いです。

  • 構造化定理：任意の制御フローは、理論上、構造化された構成に変換できる。
  • ダイクストラ：最初から、人間が理解し、正しさを論じられる構造としてプログラムを組み立てるべきだ。

片方は「後からでも表現できるか」の話。もう片方は「最初からどう考えるべきか」の話です。

では、ダイクストラはベーム＝ヤコピーニをどう見ていたのか

ここは少し慎重に書いたほうがよいところです。

「ダイクストラはベーム＝ヤコピーニの構造化定理を根拠に goto を追放した」と説明されることがあります。しかし、ダイクストラ自身の主張を読むと、それは言い過ぎです。彼の 1969年の “Notes on Structured Programming” は、構造化定理を土台にして議論を組み立てた文書ではありません。目次を見ても、「人間には多くのことはできない」「プログラムを理解する」「正しさの証明」「段階的なプログラム構成」といった、人間の知的限界と設計方法への関心が前面に出ています。

とはいえ、「ダイクストラは構造化定理と無関係だった」とまで言うのも単純化しすぎです。両者が同じ三つの制御構造、すなわち順次・選択・繰り返しに収束しているのは事実です。後世の教育や実務では、構造化定理が「goto なしでも十分に書ける」という安心材料になり、ダイクストラ流の構造化プログラミングとセットで語られるようになりました。

したがって、いちばん自然な整理はこうです。

ベーム＝ヤコピーニとダイクストラは、同じような制御構造に着目した。しかし、ベーム＝ヤコピーニは表現能力の側から、ダイクストラは人間の理解と正当性の側から、別々の道を歩いてそこへ到達した。

この整理なら、両者を無理に対立させる必要も、無理に一体化する必要もありません。

「goto を使わない」だけが構造化プログラミングではない

構造化プログラミングという言葉は、しばしば「goto を使わず、順次・選択・繰り返しで書くこと」と説明されます。入門的にはそれで十分です。しかし、ダイクストラの関心をそこだけに閉じ込めると、本丸を見落とします。

ダイクストラにとって重要だったのは、巨大なプログラムを人間の頭で扱える大きさに分解することでした。三つの制御構造は、そのための末端の道具です。より大きな話としては、次の三つが重要です。

1. 段階的詳細化、または段階的なプログラム構成

大きな問題をいきなりコードにしない。まず抽象的な処理として書く。次に、その抽象的な一行を、もう少し具体的な数行へ分解する。さらに必要なら分解する。そうして、最終的に実行可能なコードへ降りていく。

これが、いわゆる段階的詳細化です。厳密に言えば “stepwise refinement” という言葉を広く有名にしたのはニクラウス・ヴィルトの 1971年の論文ですが、ダイクストラの “Notes on Structured Programming” にも “step-wise program composition” という形で同じ問題意識がはっきり現れています。

ポイントは、抽象度を一気に混ぜないことです。

たとえば、請求書を処理するプログラムを書くとします。いきなり「CSVの3列目を int に変換し、丸め誤差に注意して……」から始めると、業務上の意味と実装上の都合が混ざります。まずは、

入力を読む
請求項目を検証する
税額を計算する
請求書を出力する

という抽象的な構造を置く。次に「税額を計算する」をさらに分ける。最後に、丸め処理やフォーマットの詳細へ降りる。こうすれば、人間は常に一つの抽象度で考えられます。

2. 正しさを後から探すのではなく、作りながら保つ

ダイクストラは、テストを軽視したわけではありません。しかし、テストだけで正しさを保証できるとは考えていませんでした。テストはバグの存在を示せても、一般にはバグの不在を示せないからです。

そこで重要になるのが、プログラムを書きながら「ここでは何が成り立っているはずか」を意識する態度です。ループならループ不変条件、関数なら事前条件と事後条件、モジュールなら外部に約束する仕様。構造化された制御フローは、こうした論理的な足場を置きやすくします。

goto が嫌われた核心もここにあります。どこからでも飛び込める場所では、「ここに来た時点で何が必ず成り立つか」を言いにくい。逆に、入口と出口が明確なブロックなら、そのブロック単位で正しさを考えやすい。

3. 階層化と抽象化

ダイクストラの業績として、1968年の THE multiprogramming system も重要です。このシステムは、活動を複数の逐次プロセスに分け、それらを階層的なレベルに配置しました。論文の要旨でも、各階層で一つ以上の独立した抽象が実装され、その階層構造が設計の論理的健全性と実装の正しさの検証に重要だった、と述べられています。

ここでのポイントは、単に「整理整頓されたOS」という話ではありません。下位の詳細を上位から隠し、上位は下位が提供する抽象だけを使う。つまり、システムを一度に全部理解しなくてもよいようにする仕組みです。

これは、構造化プログラミングのもう一つの顔です。制御フローを構造化するだけでなく、システムそのものを抽象度の違う層に分ける。人間が一度に扱う必要のある情報量を減らす。その意味で、構造化プログラミングの核心は「抽象化」だと言ってよいと思います。

コラム：break や return は悪なのか？

構造化定理を素朴に受け取ると、「ループは単一入口・単一出口でなければならない」「途中の break や return も避けるべきだ」という厳格な流儀に行きがちです。実際、教育用の言語や古典的なプログラミング作法では、そのような純粋主義が強かった時期もあります。

しかし現代の実務では、早期 return や break がむしろ可読性を高める場面も多いです。

def find_user(users, user_id):
    for user in users:
        if user.id == user_id:
            return user
    return None

これを「出口が二つあるから悪い」と機械的に非難しても、あまり得るものはありません。大事なのは、制御の意味が局所的に理解できるか、条件が明確か、読み手が実行過程を追えるかです。

つまり、構造化プログラミングを「三つの構文だけを使う宗教」として読むより、「人間が理解できる単位に制御と状態を閉じ込める技法」と読むほうが、現代のコードにもよく効きます。

ミルズらが、理論と実務をつないだ

構造化プログラミングが広まる過程では、Harlan D. Mills らの役割も大きいです。ダイクストラの議論は、かなり哲学的で、数学的で、実務家にとってはそのまま導入しにくい面がありました。ミルズらは、構造化プログラミングを企業や教育の現場で使える方法論として整理し、数学的基礎、設計法、テスト、文書化といった文脈へ広げました。

ここでベーム＝ヤコピーニの構造化定理は、実務上の説得材料として強く働きました。「goto をやめても計算能力は落ちない」という定理は、構造化プログラミングを普及させるうえで便利な旗印だったからです。

ただし、ここでも注意が必要です。理論があるから実務が自動的に成功するわけではありません。定理が保証するのは表現能力であって、よい設計ではありません。よい設計は、問題の分解、命名、抽象化、データの隠蔽、検証しやすさといった別の努力によって生まれます。

リスコフと抽象データ型へのバトン

ここから少し横道にそれますが、構造化プログラミングを「抽象化の歴史」として見るなら、バーバラ・リスコフの抽象データ型（ADT）にも触れたくなります。

リスコフは、1970年代前半にデータ抽象の概念を発展させ、CLU という言語の設計につなげました。彼女自身の “A History of CLU” では、1972年ごろにモジュール性やカプセル化の議論から、データ型とモジュールを結びつける考えへ進んだことが説明されています。抽象データ型とは、オブジェクトの表現を隠し、外部からは定められた操作だけを通じて扱えるようにする考え方です。

ここで、ダイクストラからリスコフへ一本の直線を引きすぎると危険です。リスコフの仕事には、モジュール性、Simula、Parnas、Strachey らを含む複数の流れが合流しています。しかし、構造化プログラミングが重視した「抽象度を分ける」「実装の詳細を隠す」「小さな単位で正しさを考える」という問題意識は、抽象データ型や後のオブジェクト指向とよく響き合います。

ざっくり言えば、流れはこう見えます。

  • 構造化定理：制御フローは、順次・選択・繰り返しで表現できる。
  • 構造化プログラミング：人間が理解できるように、制御と処理を構造化する。
  • 階層化・モジュール化：システムを抽象度の違う単位に分ける。
  • 抽象データ型：データ表現と操作をひとまとまりにし、表現を隠す。
  • オブジェクト指向：データと振る舞い、インターフェース、カプセル化、多相性などを言語機構として発展させる。

もちろん、オブジェクト指向の源流は Simula やケイなどにもあり、ADT だけから生まれたわけではありません。それでも、リスコフのデータ抽象が現代のプログラミング言語に与えた影響は大きく、構造化プログラミングの「抽象化の作法」をデータ側へ深めた重要な流れとして見ることができます。

まとめ：三つの構造は出発点であって、ゴールではない

構造化定理と構造化プログラミングの関係は、次のようにまとめると見通しがよくなります。

ベーム＝ヤコピーニの構造化定理は、goto を含む任意の制御フローを、理論上、構造化された形で表現できることを示しました。これは「goto がなければ計算できない」という不安を取り除くうえで重要でした。

一方、ダイクストラの構造化プログラミングは、もっと実践的で、もっと認知的な問題を扱っていました。人間の頭は小さい。複雑な時間的過程をそのまま追うのは難しい。だからプログラムは、理解できる単位、証明できる単位、抽象化できる単位へ分けて構成しなければならない。

両者は同じ「順次・選択・繰り返し」という美しい三点に触れます。しかし、そこに至る道は違います。

  • ベーム＝ヤコピーニは、数学の側から「表現できる」と言った。
  • ダイクストラは、設計の側から「理解できるように作れ」と言った。
  • ミルズらは、その二つを実務の方法論として広めた。
  • リスコフらは、抽象化をデータとモジュールの側へ発展させた。

そう考えると、構造化プログラミングは単なる「goto 禁止運動」ではありません。むしろ、現代のソフトウェア開発に今も残る、かなり根深い問いを投げかけています。

私たちは、プログラムを機械に実行させるためだけでなく、人間が理解し続けるために、どのように構造化すべきなのか。

この問いは、関数型プログラミングでも、オブジェクト指向でも、マイクロサービスでも、巨大なフロントエンドでも、いまだに形を変えて現れます。だから構造化プログラミングの話は、古典ではあっても、古びてはいないのだと思います。

事実確認メモ

  • Böhm と Jacopini の論文は 1966年、Communications of the ACM 9巻5号、366–371ページに掲載された “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules”。構造化定理はこの論文に由来するものとして広く知られている。
  • ダイクストラの “Go To Statement Considered Harmful” は 1968年、Communications of the ACM 11巻3号、147–148ページに掲載された書簡。主眼は、goto の有無そのものより、プログラム本文と実行過程の対応を人間が理解できるかにある。
  • “Notes on Structured Programming” は 1969年に書かれ、1970年に Eindhoven のレポートとして出た後、Dahl、Dijkstra、Hoare の Structured Programming（1972年）にも収録された。構造化定理を中心にした文書ではなく、プログラム理解、正当性、段階的な構成が主題である。
  • THE multiprogramming system は 1968年の論文で発表され、階層構造と抽象化が設計・実装の検証に重要だったと説明されている。
  • Liskov の “A History of CLU” は、データ抽象が1970年代前半のモジュール性・構造化プログラミングの議論と結びつき、CLU の設計へつながった経緯を説明している。ただし、抽象データ型やオブジェクト指向をダイクストラだけからの「直系」と言い切るのは強すぎる。

参考文献・資料