0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@m_yukio(Yukio Murakami)

構造化プログラミング ― goto論争から段階的詳細化、ループ不変条件まで

0
Posted at

構造化プログラミング ― goto論争から段階的詳細化、ループ不変条件まで

「構造化プログラミング」は、順次・選択・反復の3つの制御構造だけでプログラムを書くこと、あるいはgoto文を使わないこと、と短く説明されることが多い言葉です。この記事では、1960年代末から1970年代にかけての議論を、Böhm–Jacopiniの定理、Dijkstraのgoto批判、Wirthの段階的詳細化、Knuthによるgotoの再評価の順にたどります。あわせて、その考え方が同時代のPascal・C・Modula-2の設計にどう表れ、現在のSwift・Kotlinのコードにどう残っているかをサンプルコードで確かめます。

目次

はじめに

今日、新しく書かれるコードでgoto文を目にすることはほとんどありません。SwiftにもKotlinにもgoto文はありませんし、gotoを持つC言語でも、使われるのはエラー時の後始末などごく限られた場面です。if・while・for・関数呼び出しでプログラムを組み立てることは、いまでは書き方の前提になっています。

一方で、「gotoは禁止」「3つの構造だけを使う」という規則だけを覚えていると、次のような問いには答えにくくなります。

  • 多重ループの途中で抜けるbreakや、関数途中のreturnは構造化に反するのか
  • 例外は構造化プログラミングと両立するのか
  • 制御構造は整っているのに読みにくいコードがあるのはなぜか

先に結論を書いておくと、構造化プログラミングが守ろうとしていたのは、コードを上から読むことで実行時に何が起きるかを推論できる、という性質です。goto文の排除はそのための手段の一つでした。以下の節では、この見方を当時の論文と具体的なコードで確かめていきます。

1. 背景 ― ソフトウェア危機

1960年代に入ると、計算機の性能向上に伴ってソフトウェアの規模が急速に大きくなりました。OSやコンパイラ、業務システムの開発で、納期の大幅な遅延、予算超過、出荷後に見つかる大量の欠陥が繰り返し報告されるようになります。1968年にドイツのガルミッシュで開かれたNATO主催のソフトウェア工学会議では、この状況が「ソフトウェア危機（software crisis）」と呼ばれました（注1）。

当時のプログラムは、アセンブリ言語やFORTRANで、条件分岐と無条件ジャンプを組み合わせて書くのが普通でした。フローチャートで設計し、その矢印をそのままジャンプ命令に置き換えるという作り方です。小さなプログラムならこれで困りませんが、規模が大きくなると矢印が絡み合い、どこからどこへ制御が流れるかを追えなくなります。後に「スパゲッティコード」と呼ばれる状態です。

/* 配列の先頭から、負の値が現れるまでの合計を求める（goto版） */
int sum_until_negative(const int *a, int n) {
    int i = 0, sum = 0;
loop:
    if (i >= n) goto done;
    if (a[i] < 0) goto done;
    sum += a[i];
    i++;
    goto loop;
done:
    return sum;
}

この程度の規模なら読めます。ただ、done に到達する経路が2つあること、loop に戻る経路が1つあることは、ラベルとgotoをすべて目で拾わないとわかりません。ラベルが数十になり、同じラベルへのジャンプがファイルのあちこちにあると、ある行を実行しているときのプログラムの状態を把握しにくくなります。

同じ処理を構造化された形で書くと次のようになります。

int sum_until_negative(const int *a, int n) {
    int sum = 0;
    for (int i = 0; i < n && a[i] >= 0; i++) {
        sum += a[i];
    }
    return sum;
}

ループが終わる条件は for の1行に集まり、ループ本体へ入る経路も出る経路も1つずつです。ラベルを探しに行かずに、上から順に読めば済みます。

2. Böhm–Jacopiniの定理 ― 3つの構造で足りる

構造化プログラミングの理論的な裏付けとしてよく引かれるのが、Corrado Böhm と Giuseppe Jacopini が1966年に発表した論文です（注2）。彼らは、任意のフローチャートで表されるプログラムが、次の3つの組み立て方だけを使ったプログラムに変換できることを示しました。

構造 意味 現代の構文
順次（sequence） 処理Aの後に処理Bを実行する 文の並び
選択（selection） 条件によってAかBのどちらかを実行する if / else、switch
反復（iteration） 条件が成り立つ間Aを繰り返す while、for

3つの構造はどれも入口が1つ、出口が1つのブロックになっていて、ブロックの中身にまた同じ3つの構造を入れ子にできます。

順次             選択                    反復

  ↓                ↓                      ↓
[ A ]          < 条件 >              ┌→ < 条件 > ─偽─┐
  ↓            真↓    ↓偽            │     ↓真        │
[ B ]          [ A ]  [ B ]          │   [ A ]        │
  ↓              ↓    ↓              └─────┘          │
                 └─┬──┘                               ↓
                   ↓

入口と出口が1つずつなので、あるブロックを外側から見るときは、中身を知らなくても「上から入って下から出る1つの処理」として扱えます。5節の段階的詳細化も、6節の正しさの論証も、この性質を土台にしています。

3. 定理が教えないこと ― プログラムカウンタ変数による変換

Böhm–Jacopiniの定理は「変換できる」ことを示した存在定理です。変換の仕方を具体的に見ると、変換後のプログラムが読みやすくなるとは限らないことがわかります。

変換の基本的なアイデアは、元のプログラムのどの地点にいるかを表す変数を1つ用意し、全体を1つのループと選択で包むことです。次のgotoを含むプログラムを考えます。

/* gotoで書かれた元のプログラム（ユークリッドの互除法） */
int gcd(int a, int b) {
L1: if (b == 0) goto L3;
L2: { int t = a % b; a = b; b = t; } goto L1;
L3: return a;
}

これを、ラベルの番号を変数 pc に持たせる形に機械的に書き換えると次のようになります。

int gcd(int a, int b) {
    int pc = 1;
    while (pc != 0) {
        switch (pc) {
        case 1:
            pc = (b == 0) ? 3 : 2;
            break;
        case 2: {
            int t = a % b; a = b; b = t;
            pc = 1;
            break;
        }
        case 3:
            pc = 0;
            break;
        }
    }
    return a;
}

gotoは1つも残っておらず、使っているのは while と switch と代入だけです。形式的には順次・選択・反復の3つの構造で書けています。しかし制御の流れは pc という変数の値に移っただけで、どこからどこへ移るかを追う手間は元のgoto版と変わりません。

互除法を素直に書けば次の形になります。

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

「b が0でない間、(a, b) を (b, a mod b) で置き換える」という互除法の定義が、そのままコードの形になっています。3つの構造だけで書けているかどうかよりも、コードの構造が解いている問題の構造に沿っているかどうかが、読みやすさを左右します。

4. Dijkstraのgoto批判 ― プログラムの「座標」

1968年3月、Edsger W. Dijkstra は Communications of the ACM 誌に短い投書を載せます。編集者の Niklaus Wirth が付けた題は "Go To Statement Considered Harmful"（goto文は有害と考えられる）でした（注3）。この題は後に「〜 considered harmful」という言い回しの定型になりましたが、投書の中身は題から受ける印象よりも慎重です。

Dijkstraはまず、プログラマが本当に関心を持つのはソースコードそのものより、実行時に起きる過程のほうだと指摘します。人間は静的な関係を把握するのは得意でも、時間とともに変化する過程を思い描くのは苦手です。そのため、コードと実行過程の対応はできるだけ単純にしておく必要がある、というのが出発点です。

その対応を測る道具として、Dijkstraは実行の進み具合を表す「座標」を考えます。

  • 文の並びだけでできたプログラムなら、コード上の位置（いま何行目か）を指すだけで、実行がどこまで進んだかを特定できる
  • 手続き呼び出しが加わると、呼び出しの入れ子の列（現在のコールスタックに相当）を合わせれば特定できる
  • 繰り返しが加わると、さらに各ループの「何回目か」を表すカウンタを加えれば特定できる

構造化された制御構造だけを使っている限り、コード上の位置・呼び出しの列・ループカウンタという、プログラムの外側から定義できる座標で実行状態を言い表せます。変数の値の意味も、「1節の sum_until_negative で、ループの3回目の繰り返しを終えたとき、sum は先頭3要素の合計である」のように説明できます。

goto文を自由に使うと、ある行に到達したときにどの経路を通ってきたのかがコードから決まりません。そのため実行の進み具合を記述する座標が見つからなくなる、というのがDijkstraの主張です。問題にしているのはgotoという命令の存在よりも、無制限に使ったときに理解の手がかりが失われることです。

5. 段階的詳細化 ― 上から順に分解する

Niklaus Wirth は1971年の論文で、「段階的詳細化（stepwise refinement）」という設計手順を示しました（注4）。8クイーン問題を題材に、プログラムを一度に書き下すのではなく、抽象的な記述から始めて少しずつ具体的にしていく過程を記録したものです。

各段階で行うのは、ある抽象的な処理を、より具体的な処理の組み合わせに置き換えることです。組み合わせ方には順次・選択・反復を使います。どのブロックも入口と出口が1つなので、あるブロックの中身を詳細化しても、周りのプログラムには影響しません。

テキスト中の単語の出現回数を数え、多い順に上位N件を返す処理で、段階的詳細化をたどってみます。

第0段階

テキスト中の単語を出現回数の多い順に上位N件返す

第1段階（順次に分解）

1. テキストを単語の列に分割する
2. 単語ごとに出現回数を数える
3. 出現回数の多い順に並べる
4. 先頭からN件を取り出す

第2段階（各ステップを詳細化）

1. テキストを単語の列に分割する
   - 大文字・小文字の違いを無視するため、全体を小文字にする
   - 英字以外の文字を区切りとして分割する
2. 単語ごとに出現回数を数える
   - 空の対応表を用意する
   - 単語の列の各要素について（反復）
       対応表のその単語の値に1を足す
3. 出現回数の多い順に並べる
   - 回数が異なれば回数の多い順、同じなら単語の辞書順（選択）
4. 先頭からN件を取り出す

ここまで来れば、各行はそのままコードにできます。

func topWords(in text: String, limit n: Int) -> [(word: String, count: Int)] {
    let words = splitIntoWords(text)
    let counts = countOccurrences(words)
    return Array(sortByFrequency(counts).prefix(n))
}

func splitIntoWords(_ text: String) -> [String] {
    text.lowercased()
        .split(whereSeparator: { !$0.isLetter })
        .map(String.init)
}

func countOccurrences(_ words: [String]) -> [String: Int] {
    var counts: [String: Int] = [:]
    for word in words {
        counts[word, default: 0] += 1
    }
    return counts
}

func sortByFrequency(_ counts: [String: Int]) -> [(word: String, count: Int)] {
    counts
        .map { (word: $0.key, count: $0.value) }
        .sorted { $0.count != $1.count ? $0.count > $1.count : $0.word < $1.word }
}

topWords は第1段階の記述をほぼそのまま写したものです。最初に topWords だけを読めば全体の流れがわかり、詳細が必要になったところだけ下の関数を読めば済みます。

Wirthはこの論文で、詳細化の各段階で複数の選択肢を比較し、その判断を記録しておくことの重要性も述べています。上の例では「単語の区切りをどう定義するか」を第2段階で決めています。数字も単語に含めたいといった要件の変更があれば、見直すのはこの判断と splitIntoWords だけです。

6. 正しさの論証としての構造化 ― 列挙・帰納・抽象

1972年、Ole-Johan Dahl、Edsger W. Dijkstra、C. A. R. Hoare の3人による論文集『Structured Programming』が出版されます（注5）。構造化プログラミングという言葉はこの本で広く知られるようになりました。中心にあるのはDijkstraの「Notes on Structured Programming」です。

Dijkstraはここで、テストではプログラムの正しさを示せないと繰り返し述べています。テストはバグの存在を示すことはできても、バグがないことは示せない、という有名な一文もこの文脈で書かれたものです。入力の組み合わせは膨大なので、正しさは実行して確かめるのではなく、コードから論証する必要がある、という立場です。

そのうえでDijkstraは、論証に使える推論の型を3つ挙げ、それぞれを制御構造に対応させています。

推論の型 対応する構造 論証の仕方
列挙（enumeration） 順次・選択 各文の効果を順に追う。選択なら場合ごとに分けて追う
数学的帰納法（mathematical induction） 反復 繰り返しの1回分について性質が保たれることを示す
抽象（abstraction） 手続き 手続きの中身ではなく、仕様（何をするか）だけを使って呼び出し側を確かめる

順次・選択・反復・手続き呼び出しには、それぞれ対応する推論の型があります。任意のgotoで組まれた制御には、対応する型がありません。2節の3つの構造に限定する理由を、表現力ではなく推論のしやすさから説明したのがこの整理です。

抽象の例として、5節の topWords を考えます。topWords が正しいことを確かめるとき、countOccurrences の中身を読む必要はありません。「単語の列を受け取り、各単語の出現回数の対応表を返す」という仕様だけを前提に topWords を確かめ、countOccurrences が仕様を満たすかどうかは別に確かめれば済みます。

7. ループ不変条件 ― 反復を帰納法で読む

反復を帰納法で論証するときに使うのが「ループ不変条件（loop invariant）」です。ループの各回の開始時点で必ず成り立っている条件のことで、C. A. R. Hoare が1969年に提案した公理的意味論（Hoare論理）で中心的な役割を果たします（注6）。

ループの正しさは、次の3点を示すことで論証できます。

  1. 初期化: ループに入る直前に不変条件が成り立つ
  2. 維持: 不変条件とループ条件が成り立つ状態からループ本体を1回実行すると、再び不変条件が成り立つ
  3. 終了: ループが終わったとき（ループ条件が偽になったとき）、不変条件とループ条件の否定から、求める結果が導ける

これに加えて、ある整数値が毎回厳密に減少し、かつ下限を持つことを示せば、ループが必ず停止することもわかります。

二分探索で確かめてみます。

/// 昇順に並んだ配列 a から key の位置を返す。見つからなければ nil
func binarySearch(_ a: [Int], _ key: Int) -> Int? {
    var lo = 0
    var hi = a.count
    // 不変条件: key が a に含まれるなら、その位置は lo..<hi の範囲にある
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if a[mid] < key {
            lo = mid + 1    // a[0...mid] はすべて key 未満なので範囲から外せる
        } else if a[mid] > key {
            hi = mid        // a[mid...] はすべて key より大きいので範囲から外せる
        } else {
            return mid
        }
    }
    // lo == hi で範囲が空。不変条件より key は a に含まれない
    return nil
}
  • 初期化: lo = 0、hi = a.count なので範囲は配列全体であり、不変条件は自明に成り立つ
  • 維持: a[mid] < key のとき、配列が昇順なので a[0...mid] に key はない。lo = mid + 1 としても不変条件は崩れない。a[mid] > key の場合も同様。等しい場合はその時点で正しい答えを返す
  • 終了: ループを抜けるのは lo >= hi、実際には lo == hi のときで、範囲が空になる。不変条件と合わせると、key は配列に含まれない
  • 停止: hi - lo は非負の整数で、どの分岐でも厳密に減る（lo <= mid < hi なので）。したがって有限回でループは終わる

この論証が成り立つのは、ループの入口が1つで、本体の終わりから条件判定に戻る経路も1つだからです。ループ本体の途中へ外から飛び込めると「各回の開始時点」がはっきりせず、不変条件を置く場所が決まりません。

不変条件はコメントとして書いておくだけでも役に立ちます。二分探索は境界の扱い（hi を含むか含まないか、mid か mid + 1 か）で間違えやすいアルゴリズムですが、不変条件が書いてあれば、各代入が条件を保つかどうかを1行ずつ確認できます。

8. 単一入口・単一出口

Dijkstraの議論を設計上の規則にしたものが「単一入口・単一出口（single entry, single exit）」の原則です。制御構造でも手続きでも、入口は1つ、出口も1つにしておく、という規則です。

前節で見たように、入口が1つであることはループ不変条件を置くための前提になります。これは現在のほとんどの言語で自然に守られています。ループや関数の途中へ外から飛び込む手段がないからです。議論が分かれるのは出口のほうです。

厳密に単一出口を守ると、途中で処理を打ち切りたい場合に、フラグ変数を持ち回るか、条件の入れ子を深くする必要が出てきます。2次元配列から値を探す例で比べてみます。

/* 単一出口を厳密に守った版：フラグ変数で外側のループも止める */
int find(int grid[ROWS][COLS], int target, int *row, int *col) {
    int found = 0;
    for (int r = 0; r < ROWS && !found; r++) {
        for (int c = 0; c < COLS && !found; c++) {
            if (grid[r][c] == target) {
                *row = r;
                *col = c;
                found = 1;
            }
        }
    }
    return found;
}

/* 見つかった時点で関数を抜ける版 */
int find(int grid[ROWS][COLS], int target, int *row, int *col) {
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            if (grid[r][c] == target) {
                *row = r;
                *col = c;
                return 1;
            }
        }
    }
    return 0;
}

後者は関数の出口が2つありますが、読みやすさは変わらないか、むしろ読みやすくなっています。found というフラグは問題の構造から来たものではなく、単一出口の規則を守るためだけに導入された変数で、ループ条件にも余分な項を加えています。程度は小さいものの、3節の pc 変数と同じく、制御の情報をデータに移す変形です。

関数途中の return は、制御の移り先が言語の規則で決まっています（呼び出し元へ戻る）。任意のラベルへ飛べるgotoと違い、読む側が飛び先を探す必要がありません。このため早期リターンやループの break は、構造化プログラミングの考え方と両立する「構造化された脱出」として扱われることが多くなっています（11節）。

9. Knuthの再評価 ― gotoを使った構造化プログラミング

Dijkstraの投書以降、goto文の是非は長い論争になりました。その中で論点を整理し直したのが、Donald E. Knuth の1974年の論文 "Structured Programming with go to Statements" です（注7）。

Knuthはこの論文で、gotoを使わずに書くとかえって不自然になったり効率が落ちたりする例を多数集めて検討しています。多重ループからの脱出、エラー時の後始末、探索ループで「見つかった場合」と「見つからなかった場合」で後続処理が分かれるケースなどです。そのうえで、構造化プログラミングで重要なのはgotoの有無ではなく、プログラムの構造を理解しやすく保つことだと結論づけています。

Knuthが挙げたgotoの使いどころの多くは、後に言語機能として取り込まれました。多重ループからの脱出はラベル付き break に、エラー時の後始末は例外や defer になっています。gotoを使いたくなる典型的な場面ごとに、飛び先が言語の規則で決まる専用の構文が用意されたことになります（注8）。

C言語には今もgotoがあり、エラー時の後始末に使う次のような書き方は広く使われています。

int process(const char *path) {
    int rc = -1;
    FILE *fp = NULL;
    char *buf = NULL;

    fp = fopen(path, "r");
    if (fp == NULL) goto out;

    buf = malloc(BUF_SIZE);
    if (buf == NULL) goto out;

    if (read_records(fp, buf) != 0) goto out;

    rc = 0;
out:
    free(buf);
    if (fp != NULL) fclose(fp);
    return rc;
}

gotoはすべて前方の同じラベル out に飛び、後方へのジャンプはありません。関数の出口が out: の1か所に集まるので、資源の解放漏れが起きにくくなります。エラーチェックのたびに解放処理を書く版や、if の入れ子を深くする版と比べると、こちらのほうが構造がはっきりしています。

10. 言語への反映 ― PascalとC

ここまでの議論は、1970年代に設計された言語にも反映されています。同じ時期に登場したPascalとCは、制御構造については似た道具立てを持ちながら、関数の途中で抜ける手段の扱いが異なります。

Pascal

Pascalは、Wirthが設計し1970年に最初のコンパイラが動いた言語です（注9）。Algol 60の流れを汲み、Wirthと Hoare が1966年にまとめたAlgol Wを下敷きにしています。while・repeat・for・if・case という構造化された制御構造と、レコードや列挙型などのデータ型の定義をそろえ、構造化プログラミングを教えるための言語として大学教育で広く使われました。

Pascalにもgoto文はあります。ただしラベルは数字で、あらかじめ宣言しておく必要があります。一方で、標準Pascalには break・continue・return がありません。関数の戻り値は関数名への代入で設定し、関数は必ず末尾まで実行されて戻ります。8節の単一出口が、gotoを使わない限り言語の仕様として守られる形です。

配列から値を探す関数は、次のようにフラグ変数を使って書くのが一般的でした。

type
  IntArray = array[1..100] of integer;

{ a[1..n] から key を探し、見つかった位置を返す。なければ 0 }
function IndexOf(var a: IntArray; n, key: integer): integer;
var
  i: integer;
  found: boolean;
begin
  i := 1;
  found := false;
  while (i <= n) and not found do
    if a[i] = key then
      found := true
    else
      i := i + 1;
  if found then
    IndexOf := i
  else
    IndexOf := 0
end;

ループ条件を (i <= n) and (a[i] <> key) とまとめずにフラグを使っているのには理由があります。標準Pascalの and は短絡評価を保証していないので、i が n を超えた時点でも a[i] が評価され、範囲外の参照になるおそれがあるからです。

標準Pascalには分割コンパイルの仕組みもありませんでした。プログラム全体を1つのファイルに書く前提で、大きなプログラムを部品に分けるには、後の処理系がそれぞれ独自に追加した unit などの拡張に頼ることになります。この不足を言語の側で埋めようとしたのが、12節で触れるModula-2です。

C

C言語は、Dennis Ritchie がベル研究所で1972年ごろに開発した言語です（注10）。BCPLとBの流れを汲むシステム記述用の言語で、1973年にはUnixのカーネルがCで書き直されました。構造化プログラミングを広めるために作られた言語ではありませんが、if・while・for・do・switch という構造化された制御構造を備えています。

Pascalと大きく違うのは、break・continue・return を持ち、goto文も残したことです。同じ探索はCでは次のように書けます。

/* a[0..n-1] から key を探し、見つかった位置を返す。なければ -1 */
int index_of(const int *a, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

フラグ変数は不要で、見つかった時点で関数を抜けます。Cの && と || は短絡評価が保証されているので、i < n && a[i] != key のような条件も安全に書けます。

Cの break は1重のループしか抜けられず、ラベル付き break はありません。そのため多重ループからの脱出や、9節のエラー時の後始末には、今もgotoが使われます。Pascalが単一出口を言語の規則にしたのに対し、Cは構造化された脱出をいくつか用意したうえで、残りの場面はgotoに任せた、という違いです。

モジュール化についても、Cは言語の機能を持たず、慣習で対応しています。ファイル単位で分割コンパイルし、ヘッダファイルに公開する宣言を書き、ファイルの外に見せない関数や変数には static を付けます。ヘッダと実装が食い違ってもコンパイラが必ず検出するわけではなく、どこまで隠すかはプログラマの規律に委ねられています。

11. 現代の言語に残る「構造化された脱出」

SwiftやKotlinにgoto文はありませんが、9節で見たgotoの使いどころには、それぞれ専用の構文があります。どれも飛び先がコードから一意に決まります。

ラベル付きbreak / continue

8節の多重ループからの脱出は、ラベル付き break で書けます。

var position: (row: Int, col: Int)? = nil
search: for (r, row) in grid.enumerated() {
    for (c, value) in row.enumerated() {
        if value == target {
            position = (r, c)
            break search
        }
    }
}

var position: Pair<Int, Int>? = null
search@ for ((r, row) in grid.withIndex()) {
    for ((c, value) in row.withIndex()) {
        if (value == target) {
            position = r to c
            break@search
        }
    }
}

飛び先は「search というラベルが付いたループの直後」に限られ、ループの途中に飛び込むことはできません。

早期リターンとguard

Swiftの guard は、条件が満たされない場合に必ずスコープを抜けることをコンパイラが保証する構文です。

func parseAge(_ text: String) -> Int? {
    guard let value = Int(text) else { return nil }
    guard (0...150).contains(value) else { return nil }
    return value
}

前提条件のチェックを関数の先頭に並べ、本来の処理を入れ子の外に置けます。guard より下の行では前提条件が成り立っていることがコードの形から読み取れ、6節の論証でもそれを前提として使えます。

deferによる後始末

9節のCの後始末パターンは、Swiftでは defer で書けます。

func process(path: String) throws {
    guard let fp = fopen(path, "r") else { throw ProcessError.cannotOpen }
    defer { fclose(fp) }

    let buf = UnsafeMutablePointer<CChar>.allocate(capacity: bufferSize)
    defer { buf.deallocate() }

    try readRecords(fp, buf)
}

defer に書いた処理は、スコープをどの経路で抜けても（正常終了でも throw でも）実行されます。Cで out: ラベルとgotoを使って組み立てていた構造を、言語が保証してくれます。Kotlinでは use 関数や try/finally が同じ役割を担います。

例外

例外は呼び出しの階層をまたいで制御を移す仕組みで、構造化プログラミングとの関係はほかの構文より込み入っています。飛び先（対応する catch）は実行時に決まり、関数のコードだけからはわかりません。ただし飛び先は「呼び出しの列をさかのぼって最初に見つかるハンドラ」という規則で決まるので、4節の座標（呼び出しの列）の上で記述できます。

Swiftでは、例外を投げうる関数に throws を、呼び出し箇所に try を書く必要があります。制御が途中で抜けうる箇所がコード上に印として残るので、関数を上から読むときにそこで抜ける可能性に気づけます。

12. 構造化プログラミングの後に来たもの ― モジュールとModula-2

構造化プログラミングが主に扱ったのは、手続きの内部で制御の流れをどう組み立てるかでした。プログラムがさらに大きくなると、関心は手続きやデータをどう分割して組み合わせるかに移っていきます。

1972年に David L. Parnas が発表した論文 "On the Criteria To Be Used in Decomposing Systems into Modules" は、その転換点の一つです（注11）。Parnasは、変更されやすい設計判断を1つのモジュールの中に隠すようにシステムを分割すべきだと主張しました。処理の手順に沿った分割と比べ、変更の影響が狭い範囲に収まるという考え方で、情報隠蔽（information hiding）と呼ばれています。

5節の段階的詳細化は処理の流れに沿って上から分解していく手法なので、Parnasの基準とは分割の軸が違います。実際の設計では両方を使います。処理の流れは段階的に詳細化し、単語の区切り方やデータの保存形式のような変更されやすい判断は、モジュールの内側に閉じ込めます。

この考え方を言語の仕組みとして取り込んだ例が、Wirthが1978年に報告をまとめたModula-2です（注12）。Pascalを土台に、10節で見た分割コンパイルの欠如を補う形で設計されています。

Modula-2では、モジュールを定義モジュール（DEFINITION MODULE）と実装モジュール（IMPLEMENTATION MODULE）の2つに分けて書きます。定義モジュールには外部に公開する型と手続きの宣言だけを書き、実装モジュールに中身を書きます。型の名前だけを公開して構造を隠す不透明型（opaque type）も使えます。

DEFINITION MODULE Stacks;
  TYPE Stack;                          (* 不透明型：中身の構造は公開しない *)
  PROCEDURE Create(): Stack;
  PROCEDURE Push(s: Stack; x: INTEGER);
  PROCEDURE Pop(s: Stack): INTEGER;
  PROCEDURE IsEmpty(s: Stack): BOOLEAN;
END Stacks.

利用する側は FROM Stacks IMPORT Stack, Create, Push, Pop; のように必要な名前を明示して取り込みます。Stack が配列で実装されているのか連結リストで実装されているのかは、利用する側からは見えません。実装を差し替えても定義モジュールが変わらなければ、利用する側を書き換える必要はありません。Parnasの言う「変更されやすい設計判断を隠す」を、コンパイラが検査できる形にしたものです。Cのヘッダファイルと static による慣習的な分割と比べると、違いがはっきりします。

制御構造の面では、Modula-2はgoto文を廃止しました。代わりに、LOOP 文から抜ける EXIT と、手続きから抜ける RETURN を用意しています。11節で見た「構造化された脱出」だけを残し、任意のジャンプは持たないという設計です。Pascalの単一出口とCのgotoの中間にあたります。

その後、抽象データ型、オブジェクト指向、関数型プログラミングといった考え方が広まりました。オブジェクトのメソッドの中身は構造化された制御構造で書かれますし、関数型言語の再帰や高階関数は、反復と抽象を別の形で表現したものと見ることもできます。

同じ流れの中で、構造化設計（Edward Yourdon・Larry Constantine）や構造化分析（Tom DeMarco）も1970年代後半に体系化されました。これらは構造化プログラミングの考え方を設計・分析の工程に広げたもので、モジュール間の結合度・凝集度による設計評価や、データフロー図による分析手法を指します。名前は似ていますが、扱う対象はコードの制御構造ではなく、システム全体の分割の仕方です。

まとめ

  • Böhm–Jacopiniの定理は、順次・選択・反復の3つで表現力が足りることを示したが、変換結果が読みやすくなることまでは保証しない
  • Dijkstraのgoto批判は、構造化された制御構造ならコード上の位置・呼び出しの列・ループカウンタで実行状態を記述できるのに対し、無制限のgotoではそれができなくなる、という議論だった
  • Wirthの段階的詳細化は、入口と出口が1つのブロックを入れ子にしながら、抽象的な記述から具体的なコードへ少しずつ降りていく設計手順である
  • 「Notes on Structured Programming」は、制御構造を列挙・帰納・抽象という推論の型に対応させた。ループ不変条件は、反復を帰納法で確かめるための道具になる
  • Knuthは、構造がはっきりしていればgotoを使ってもよいと整理した。gotoの典型的な使いどころは、後にラベル付きbreak・早期リターン・defer・例外といった専用の構文に置き換えられた
  • 言語の設計にも違いが表れている。Pascalは途中で抜ける構文を持たず単一出口を守らせ、Cは break・return に加えてgotoも残した。Modula-2はgotoを廃止して EXIT・RETURN だけを残し、定義モジュールと実装モジュールの分離で情報隠蔽を言語に取り込んだ

breakや早期リターンを使ってよいか迷ったときは、飛び先がコードから一意に決まるか、その地点で成り立っている条件を説明できるか、を確認すると判断しやすくなります。

注釈

  1. Peter Naur・Brian Randell 編, "Software Engineering: Report on a Conference Sponsored by the NATO Science Committee"（1969年）。1968年10月にガルミッシュで開かれた会議の報告書で、「ソフトウェア工学（software engineering）」という言葉を意図的に掲げた会議として知られる。
  2. Corrado Böhm・Giuseppe Jacopini, "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules"（Communications of the ACM, 1966年5月）。任意のフローチャートが、合成・選択・反復のみで構成されたものに変換できることを示した。変換には補助的な真偽値変数の導入が必要になる。
  3. Edsger W. Dijkstra, "Go To Statement Considered Harmful"（Communications of the ACM, 1968年3月、Letters to the Editor）。Dijkstraが付けた原題は "A Case against the GO TO Statement" で、掲載時の題は編集者のNiklaus Wirthによる。
  4. Niklaus Wirth, "Program Development by Stepwise Refinement"（Communications of the ACM, 1971年4月）。8クイーン問題を題材に、抽象的な記述を段階的に詳細化していく設計過程を示した。
  5. O.-J. Dahl・E. W. Dijkstra・C. A. R. Hoare, "Structured Programming"（Academic Press, 1972年）。Dijkstra "Notes on Structured Programming"、Hoare "Notes on Data Structuring"、Dahl・Hoare "Hierarchical Program Structures" の3編を収める。
  6. C. A. R. Hoare, "An Axiomatic Basis for Computer Programming"（Communications of the ACM, 1969年10月）。事前条件・プログラム・事後条件の三つ組 {P} S {Q} によってプログラムの意味を公理的に定める枠組みを示した。反復の規則でループ不変条件が使われる。
  7. Donald E. Knuth, "Structured Programming with go to Statements"（Computing Surveys, 1974年12月）。gotoを含むプログラムと含まないプログラムを多数比較し、構造化の本質は制御構造の理解しやすさにあると論じた。効率に関する議論の中で、「早すぎる最適化は諸悪の根源」という一節が登場することでも知られる。
  8. S. Rao Kosaraju, "Analysis of Structured Programs"（Journal of Computer and System Sciences, 1974年）。補助変数を導入せずに変換できるプログラムの範囲を調べ、多段のループ脱出（何重のループを抜けるかを指定できるbreak）を許すと表現できるプログラムの範囲が広がることを示した。
  9. Niklaus Wirth, "The Programming Language Pascal"（Acta Informatica, 1971年）。Pascalの言語報告。教育用の言語としての設計方針は、Wirthの著書 "Algorithms + Data Structures = Programs"（Prentice-Hall, 1976年）でも具体例とともに示されている。
  10. Dennis M. Ritchie, "The Development of the C Language"（ACM SIGPLAN Notices, 1993年3月、HOPL-II）。BCPL・BからCに至る経緯と、Unixの書き直しとの関係をRitchie自身が述べている。言語仕様の最初のまとまった解説は Brian W. Kernighan・Dennis M. Ritchie, "The C Programming Language"（Prentice-Hall, 1978年）。
  11. David L. Parnas, "On the Criteria To Be Used in Decomposing Systems into Modules"（Communications of the ACM, 1972年12月）。処理手順による分割と、設計判断を隠蔽する分割を同じシステムで比較し、後者が変更に強いことを示した。
  12. Niklaus Wirth, "Programming in Modula-2"（Springer-Verlag, 1982年）。Modula-2の解説書で、言語報告を収録している。Modula-2は1975年のModulaの後継として設計され、ETHのワークステーションLilithのシステム記述にも使われた。

参考資料

構造化プログラミング ― goto論争から段階的詳細化、ループ不変条件まで

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?