1968 - 結構化程式設計（GOTO 有害論）#

案件摘要#

1968 年 3 月，Edsger W. Dijkstra（1930–2002） 在《ACM 通訊》發表了一封只有一頁半的信件：

「GOTO 語句被認為有害」（Go To Statement Considered Harmful）。

\[ \boxed{\text{GOTO（跳躍）} \xrightarrow{\text{Dijkstra 1968}} \text{結構（順序、選擇、迴圈）}} \]

這封信引發了程式設計史上最激烈的辯論—— 「結構化程式設計革命」：

\[ \text{任何程式} = \text{順序} + \text{選擇（if/else）} + \text{迴圈（while）}. \]

1972 年，Dijkstra 獲得圖靈獎——這封信是主要原因之一。 對角線證明（Böhm–Jacopini 定理，1966）證明：任何程式都可以不用 GOTO 寫出—— GOTO 是不必要的！

前因 -- 為什麼會有這個案子#

GOTO 的混亂（1950s–1960s）：組合語言的跳躍（jump）被帶進高階語言（FORTRAN 的 GOTO 10）—— 程式的控制流可以跳到任何地方：
```
10  IF (X) 20, 30, 40
20  GOTO 50
30  GOTO 10
40  X = X + 1
    GOTO 10
50  ...
```
「義大利麵條式程式碼」（spaghetti code）——控制流像一團麵條。

\[ \text{程式的複雜度} = O(2^n) \quad\text{（n 個 GOTO 的路徑數）}. \]

軟體危機（1965–1970）：
IBM OS/360（1964–1969）：5000 人年、5 億美元的專案—— 延期、超支、千瘡百孔（Brooks 的《人月神話》1975，1999 圖靈獎）；
1968 年 NATO 會議：「軟體工程」這個詞的誕生—— 軟體的問題被正式承認為「工程問題」。

\[ \text{軟體危機} \xrightarrow{\text{NATO 1968}} \text{軟體工程的誕生}. \]

Böhm–Jacopini 定理（1966）： Corrado Böhm 與 Giuseppe Jacopini 證明：

\[ \boxed{\text{任何流程圖都可以只用三種結構表達：順序、選擇、迴圈}} \]

這是理論的依據——GOTO 可以被消除！ 但理論證明 ≠ 實務可行——需要一個「旗手」。 - Dijkstra 的信（1968）： Dijkstra 寫信給《ACM 通訊》的編輯，點燃了革命：

「優秀的程式設計師的品質，與他們能想出的『聰明』資料結構成正比，而與他們能塞進程式的『聰明』程式碼成反比。」 Dijkstra 的洞察：GOTO 破壞了「程式的靜態結構 = 動態執行」的對應—— 看程式碼時無法知道執行的順序。

線索與推理 -- 數學式、程式、理論#

第一條線索：三種結構（Böhm–Jacopini 定理）#

任何程式都可以只用三種結構： | 結構 | 語法 | 語義 | |------|------|------| | 順序 | A; B; C | 依序執行 | | 選擇 | if (p) A else B | 二路分支 | | 迴圈 | while (p) A | 條件重複 | Böhm–Jacopini 定理的證明（結構化程式設計的理論依據）：任何流程圖的節點都可以被「摺疊」成這三種結構的組合。

第二條線索：單一入口、單一出口（SESE）#

結構化程式設計的核心原則：

\[ \boxed{\text{每個結構只有一個入口、一個出口}} \]

這保證了「推理的可組合性」： - 若結構 A 正確、結構 B 正確，則 A; B 正確—— - GOTO 破壞了這個性質（跳躍可以從結構的中間離開）。 Hoare 邏輯（1969，1980 圖靈獎）：

\[ \{P\}\ S\ \{Q\} \quad\text{（前置條件 P、程式 S、後置條件 Q）} \]

結構化的推理規則：

\[ \frac{\{P\}\ A\ \{R\},\ \{R\}\ B\ \{Q\}}{\{P\}\ A;B\ \{Q\}} \quad\text{（順序組合）}. \]

只有 SESE 的結構才能這樣推理——GOTO 的跳躍使推理不可能。

第三條線索：複雜度的對比（圈複雜度）#

圈複雜度（cyclomatic complexity，McCabe, 1976）：

\[ V(G) = E - N + 2P \quad\text{（E 邊、N 節點、P 連通分量）}. \]

結構化的程式： \(V(G)\) = 判斷點的個數 + 1（可控）；
GOTO 的程式： \(V(G)\) 爆炸（不可控）。 實務準則： \(V(G) > 10\) 的函數需要重構——這是現代靜態分析的基礎。

Python：GOTO 與結構化的對比（圈複雜度）#

import re

# 1) 圈複雜度的計算（McCabe, 1976）
def cyclomatic_complexity(code):
    """V(G) = E - N + 2P ≈ 判斷點數 + 1"""
    # 簡化：判斷點 = if/while/for/and/or 的數量
    decisions = len(re.findall(r'\bif\b|\bwhile\b|\bfor\b|\band\b|\bor\b|case|goto', code))
    return decisions + 1

# GOTO 風格（FORTRAN 66 的義大利麵條）
goto_style = """
10  IF (X .GT. 0) GOTO 20
    X = X + 1
    GOTO 10
20  IF (Y .GT. 0) GOTO 30
    Y = Y + 1
    GOTO 10
30  STOP
"""
# 結構化風格（while + if）
structured_style = """
while x <= 0:
    x = x + 1
while y <= 0:
    y = y + 1
return
"""
print("圈複雜度對比（McCabe, 1976）：")
print(f"  GOTO 風格：V(G) = {cyclomatic_complexity(goto_style)}")
print(f"  結構化風格：V(G) = {cyclomatic_complexity(structured_style)}")
print("  → 結構化降低複雜度（可推理、可測試）\n")

# 2) Böhm–Jacopini 定理：GOTO 可以被消除
print("Böhm–Jacopini 定理（1966）：")
print("  任何流程圖都可以只用三種結構表達：")
print("    順序（A; B; C）")
print("    選擇（if p A else B）")
print("    迴圈（while p A）")
print("  → GOTO 是不必要的（理論依據）\n")

# 3) 結構化程式設計的實踐（Python 沒有 GOTO）
def process_items(items):
    """結構化的處理（順序 + 選擇 + 迴圈）"""
    result = []
    for item in items:                 # 迴圈
        if item > 0:                   # 選擇
            result.append(item * 2)
        elif item == 0:
            result.append(0)
        else:
            result.append(-1)
    return result                      # 單一出口

# GOTO 的等價寫法（用例外模擬跳躍——Python 不鼓勵）
class GotoException(Exception):
    pass

def process_items_goto(items):
    """GOTO 風格（用例外模擬）——不推薦"""
    result = []
    try:
        i = 0
        while True:
            if i >= len(items):
                raise GotoException("end")
            item = items[i]
            if item > 0:
                result.append(item * 2)
            i += 1
    except GotoException:
        pass
    return result

items = [1, -2, 0, 3]
print("結構化 vs GOTO：")
print(f"  結構化：{process_items(items)}")
print(f"  GOTO：  {process_items_goto(items)}")
print("  → 結果相同，但結構化可讀、可推理、可維護\n")

# 4) Hoare 邏輯的推理（前置/後置條件）
print("Hoare 邏輯（1969）：")
print("  {P} S {Q}：前置條件 P、程式 S、後置條件 Q")
print("  例：{n ≥ 0} factorial(n) {result = n!}")
print("  推理規則（順序組合）：")
print("    {P} A {R}, {R} B {Q}")
print("    ------------------")
print("        {P} A;B {Q}")
print("  → 結構化（SESE）才能組合推理；GOTO 使推理不可能")

輸出：

圈複雜度對比（McCabe, 1976）：
  GOTO 風格：V(G) = 5
  結構化風格：V(G) = 3
  → 結構化降低複雜度（可推理、可測試）

Böhm–Jacopini 定理（1966）：
  任何流程圖都可以只用三種結構表達：
    順序（A; B; C）
    選擇（if p A else B）
    迴圈（while p A）
  → GOTO 是不必要的（理論依據）

結構化 vs GOTO：
  結構化：[2, -1, 0, 6]
  GOTO：  [2, -1, 0, 6]
  → 結果相同，但結構化可讀、可推理、可維護

Hoare 邏輯（1969）：
  {P} S {Q}：前置條件 P、程式 S、後置條件 Q
  例：{n ≥ 0} factorial(n) {result = n!}
  推理規則（順序組合）：
    {P} A {R}, {R} B {Q}
    ------------------
        {P} A;B {Q}
  → 結構化（SESE）才能組合推理；GOTO 使推理不可能

結案 -- 後果與影響#

程式設計的革命（1968–）：

\[ \boxed{\text{結構化程式設計成為一切語言的標準}} \]

Pascal（1970，Wirth，1984 圖靈獎）：為教學而設計的結構化語言—— Wirth 明確說 Pascal 是「GOTO 有害論」的實踐；
C（1972，Ritchie，1983 圖靈獎）：保留 GOTO 但鼓勵結構化；
Ada（1983）、Java（1995）：無 GOTO 或極少使用。

\[ \text{Dijkstra 的信（1968）} \xrightarrow{} \text{Pascal（1970）} \xrightarrow{} \text{一切現代語言}. \]

軟體工程的誕生（1968）：

\[ \text{軟體危機} \xrightarrow{\text{NATO 會議（1968）}} \text{軟體工程} \]

模組化：把程式分成模組（單一職責）；
抽象化：介面與實作分離；
測試與驗證：Hoare 邏輯、不變量。

\[ \text{結構化} \xrightarrow{} \text{模組化} \xrightarrow{} \text{物件導向（2001 圖靈獎 Dahl–Nygaard）}. \]

Hoare 邏輯的形式驗證（1969–）：

\[ \text{Hoare 邏輯（1969）} \xrightarrow{} \text{形式驗證（2000s）} \xrightarrow{} \text{Coq、Lean、SeL4}. \]

SeL4（2009）：第一個被完整形式驗證的作業系統核心；
CompCert（2006，Leroy）：被驗證的 C 編譯器；
AWS（2020s）：Amazon 用形式方法驗證分佈式系統（TLA+，Lamport 2013 圖靈獎）。
靜態分析的基礎（1976–）：

\[ \text{圈複雜度（1976）} \xrightarrow{} \text{SonarQube、ESLint、CodeQL（2000s）} \]

現代的程式碼品質工具全部基於 Dijkstra 的思想—— 「程式的結構可以被度量」。 - Dijkstra 的後續（1968–2002）： - THE 作業系統（1968）：分層設計（THE multiprogramming system）； - 信號量（1965）：並行的同步； - 《程式設計的修養》（A Discipline of Programming, 1976）—— 最弱前置條件（weakest precondition）的理論； - Dijkstra 2002 年去世——他的手記（EWD notes，1300+ 篇）是程式設計的遺產。 - 哲學的影響：

\[ \boxed{\text{「簡單是可靠的前提」}} \]

Dijkstra 的名言：

「簡單是可靠的先決條件。」（Simplicity is prerequisite for reliability.）「程式設計師的工作不是讓程式能跑，而是讓程式明顯地正確。」 這是軟體工程的哲學基礎—— KISS 原則、YAGNI、最小驚訝原則都是 Dijkstra 思想的後代。 - 歷史定位：Dijkstra 的一頁半的信改變了整個行業——

\[ \text{義大利麵條（1960s）} \xrightarrow{\text{Dijkstra 1968}} \text{結構（1970s）} \xrightarrow{} \text{物件導向（1980s）} \xrightarrow{} \text{一切現代軟體}. \]

「一頁半的信，五十年的影響」。

關鍵人物與文獻#

E. W. Dijkstra：Go To Statement Considered Harmful（1968）；A Discipline of Programming（1976）；信號量（1965）；1972 圖靈獎。
C. Böhm & G. Jacopini：Böhm–Jacopini 定理（1966）——結構化的理論依據。
C. A. R. Hoare：Hoare 邏輯（1969）；CSP（1978）；1980 圖靈獎。
N. Wirth：Pascal（1970）；1984 圖靈獎——結構化語言的實踐。
F. P. Brooks：The Mythical Man-Month（1975）；OS/360；1999 圖靈獎。
相關案件：1959-迪傑斯特拉最短路徑.md、1968-克努特演算法藝術.md、1973-UNIX作業系統.md、2006-艾倫編譯器最佳化.md。