構造化定理における「入口」「出口」と言った言葉の解釈について

Question

「１つの入口から１つの出口に向かうプログラムであれば、「順次」「選択」「繰り返し」の３つの基本構造とその組み合わせだけで、どのような処理も記述できる」とする構造化定理というものがあります．

ここでふと疑問に思ったのですが，ここで言う「入口」「出口」とはなんのことでしょうか？

改めて考えたときに，私のぼんやりとした入口・出口のイメージではむしろ入口・出口が複数あるコードと言うのが想像できず，また調べてもよく分かりませんでした．
本当は解釈の違いを正すためにもここで私の解釈を説明すべきなのでしょうが，如何せんぼんやりとしていて言語に落とし込めず．．．

私は主にJavaを書いて来たので，そうしたバックボーンもあるかもしれません．
些細なことでも良いのでご回答いただけますと幸いです．

Answer 1

アセンブラだと、入り口が複数というのは、簡単にできますし、昔は珍しくなかったと思います。
（例えば、プログラムサイズの制約がきつい場合には多用することになるかと思います）

明確な、関数とかメソッドという囲まれたものがないと、そういうことになります。

VBとかじゃないオリジナルのBASICだと、このあたりはアセンブラと同様です。

古いCOBOLだと、１つのコンパイル単位の中に、他の言語で言う関数(やメソッド)が書けませんでした。
「ラベルXの文から、ラベルYの文まで実行して戻ってこい」という命令がその代わりになります。
当然、その範囲が重なることもあり得ます。
（ラベルが、A、B、C、D と並んでいたとして、「ラベルAからCまで実行してこい」「ラベルBからDまで実行してこい」の2つの処理があるかも）

また、古いFortranだと、サブルーチン・関数の途中に、別の入り口を作るENTRY 名前(仮引数)という文もありました。

出口が複数というのは、関数等からの出口が複数あるというのは普通でしょう。
あと、関数というまとまりじゃなくて、構造の話で言うと、ループの出口も複数あったりします。
Cの例ですが、

for(i=0; i<N; i++){
    if(x[i]==a) break;
    ・・・・
}

だと、breakによる出口と、i<Nじゃなくなった時の出口と、２つの出口があります。

Answer 2

この場合の「入り口」「出口」とは、ある実行処理の実行始めの部分と、実行を終了して終わる（抜ける）部分を指します。「構造化定理」をwikipediaであたり、「入口」と「出口」の出処を探ってみると、
構造化定理 - wikipedia日本語版
Structured program theorem - wikipedia 英語版
「入口」に相当する英単語は「entry path」、出口に相当する英単語は「exit path」です。冗長に直訳すれば、それぞれ「入場の為の通り道、「退場の為の通り道」でしょうか。恐らく質問者さんにとっては、相変わらず分かりづらい単語でしょうね。

私自身はCOBOLと言うプログラミング言語に明るくないのでその例を除かせてもらいますが、古くから使われているアセンブリ言語などでは、分岐や繰り返しの構造は、ある「ラベル（≒アドレス）」へのジャンプによって実現しています。また、ある処理を始めるにあたり、呼び出し元によって複数の実行開始位置から実行することができます。これらを「入口」と呼ぶことができるでしょうし、処理を終わって脱出するときも、終了条件を満たしたら即、飛びたいラベルへジャンプするので、これらを「出口」と呼ぶこともできます。また、そんな構造を持つことが可能です。

Javaでは処理の単位は大きくは「メソッド」であり、あるクラスのメソッドからあるクラスのメソッドの「途中」へ飛び込むような無作法はできません。メソッドの途中でreturn文を書き、ひとつのメソッド中に複数のreturn文、あるいはエラーによってはthrowを書くことでその時点で複数の「出口」と言って言えないこともありませんが、そのメソッドを呼び出す上位から見れば、単一の出口です。そんなことからJavaから「複数の入口と出口」を連想するのは、難しいのでしょう。

アセンブリ言語が分かりづらければ、BASICと言うプログラミング言語について軽く調べてみるとイメージがつき易くなるかもしれません。BASICと名がつくプログラミング言語は多いですが、よく目にするVisual Basicではなく、昔ながらの行番号指向のBASICがそれです。GOSUBと言うサブルーチン（Javaで言うメソッド）への分岐を除いて、基本的に行番号を指定して分岐（ジャンプ）します。無用心にプログラムすると、すぐに複数の入口と出口が頻出する、いわゆる「スパゲティプログラム」と化します。

Answer 3

「構造化定理」は知りませんが、おそらく古い文献などで
みられたのではないでしょうか？

その昔は GO TO 文でコード内をとびまわるような
プログラムがままあったようで、それに対する
指標として提唱されたのが構造化プログラミングですね。
※個人の解釈です。

そういう意味では無秩序なプログラミングに対して
入口や出口という概念を適用してそのような定理を
定義している、というはなしではないでしょうか。

Answer 4

多分具体的な例でないと考えにくいと思うので、いくつか例示します。
例によって独自解釈なので注意してください。

Javaで構造化が完全でない例

private void method()
{
	while(...) {
		...
		if (cond1) {
			return 1; // A
		}
		if (cond2) {
			return 2; // B
		}
		...
	}
	return 0; // C
}

出口A,B,Cの3つあり、while{}内に興味がなくて読み飛ばすと、returnは常に0と誤解してしまいます。

Javaで構造化が完全な例

private void method()
{
	int result = 0;
	while(...) {
		...
		if (cond1) {
			result = 1; // A
			break;
		}
		if (cond2) {
			result = 2; // B
			break;
		}
		...
	}
	return result; // C
}

出口がCだけになり、while{}内に興味がなければ読み飛ばすことが出来、必ずresultが返ることが分かります。

C言語で非構造化の例

gotoでラベルジャンプできる言語だと、もっと大胆に行ったり戻ったりできるので、制御構造の{}自体が意味をなさなくなります。

void func() {
start:
	while (...) {
		...
cont1:
		if (cond1) {
			goto start;
		}
		if (cond2) {
			goto error1;
		}
	}
	goto cont2:

error1:
	...
	goto cont1;

cont2:
	return 0;
}

こうなってしまうと、全部のコードを読まないと全体の制御構造が分からなくなります。
このため、gotoを多用する非構造化なプログラミングスタイルは忌み嫌われる傾向にあります。

最後に

個人的には例外機構のない言語で、エラー処理のために統一された使い方をされてるラベルジャンプは好きです。ただ現実的には多くの言語で、ラベルジャンプはそんなに見かけないと思います。あえて挙げればCOBOLやDBのストアードプログラムとかで、たまに見る程度、かなぁ。

Comments

[dameo]

アセンブラなどはラベルありきの言語ですが、最近出番が少なくて短めになる上に、せいぜい他の言語の中でinlineで出現する傾向が強かったりするので、かえってラベルジャンプを見かけなくなりました。
ガッツリ書けば必要になりますけど...

Answer 5

こんにちは。

入り口はエントリーポイント（≒関数の先頭）、出口はreturn文と考えて概ね合っていると思います。

そして、複数のreturn文は複数の出口と言えると思います。
複数の入り口は分かりにくいですね。普通の関数は入り口は１つしかありませんので。
複数の関数で構成され、それらの関数が呼び出し関係にあるモジュールをここで言う「プログラム」として解釈すれば解りやすいかも知れません。そのモジュールを使う際に呼び出す複数の関数は複数の入り口に該当すると言えるでしょう。

しかし、そもそも構造化の反対の概念は、フローチャートやアセンブラのような処理の流れですから、入り口や出口はいくらでも自由に作れます。

Answer 6

COBOLはオブジェクト指向の思想が生まれる前に作られた言語なので、カプセル化やブロックの概念がかなり希薄で、関数(COBOLではサブルーチンと言ったり)の入り口(エントリー・ポイントとか言ったかも？メーカーやコンパイラによって機能や言い方が違う)が複数あったり、関数の出口のreturn が複数ヶ所あったりします。

あまり気にするようなことではないです。