構造化プログラミングの覚え書き

はじめに

　自分用の備忘録としてここに書き記しておく。注意点として、この記事は独自解釈である。

　構造化プログラミングとは、1968年から1972年にかけて、ダイクストラが提唱して、ホーアとダールとウィルトが体系化した科学理論である。

　この理論は、情報隠蔽(inforamtion hiding)のパルナス、抽象データ型（Abstarct Data Type)とCLU言語のリズコフ、契約による設計（Design by Contract）とEiffel言語のバートランド・メイヤーズ、C++言語のストラウストラップなど、数多くの科学者に大きな影響を与えた。情報技術に革命をもたらした科学理論なのである。

背景

　構造化プログラミングの目的は、「プロセス同士でやりとりするメッセージ」を実装することである。

　まず、重要な説明として、セマフォ (semaphore)はオランダ語と英語で意味が異なる。英語のセマフォは鉄道用語の「腕木式信号機」を指すが、オランダ語では、「バケツリレー方式のメッセージ送信機」を意味する。ナポレオン時代にフランスが、オランダのアムステルダムに3本の腕木を操作して手旗信号のようにメッセージを送信する施設を置いたのが語源である。よって、オランダ人のダイクストラが言うセマフォとは「バケツリレー方式のメッセージ送信」のことである。

　1965年、ダイクストラは「Communications of ACM vol.8」において、メッセージ (message)の概念を提唱した。

　翌年、66年、NATOの会合で、彼は「協調逐次プロセス (Cooperationg Sequential Process)」というタイトルの講義をおこない、メッセージをgoto文を使った擬似コードで実装した。

　同年、同じ会合でダールが「クラス」の概念を提唱した。彼は、ホーアのレコードクラス (Record Class)と区別するため、「対象クラス（Object Class)」と名付けて、翌年の67年にSIMULA67言語で実装した。ダイクストラの「メッセージ」とダールの「クラス」は66年の同じ会合で唱えられたことを強調しておく。

　後に、ホーアが78年に、「Communicating Sequential Processes (CSP)」というダイクストラ・メッセージの講義をもじった論文を発表した。この論文の中で、ダイクストラが出題した「食事する哲学者の問題」と、ダールの「対象クラス」を紹介した。

　ダイクストラのメッセージを使えば、食事する哲学者の問題は容易に解決する。「お先にどうぞ (After you)」と賢い哲学者たちはメッセージを出して、お互いに譲り合えばよい。他者に対してではなく、自分に対して、「止まれ」の命令を出せばよいのだ。もし「待ち (wait)」の間にメッセージを受け取ったら、哲学者は食べ始める。

　68年にダイクストラは、マルチプログラミング「T.H.E」の研究によって、ダイクストラ階層構造化 (Hierarchy Structure)を発見した。この構造化は、トップダウン方式とボトムアップ方式があり、同じくマルチプログラミングの研究をしていたパルナスに影響を与えた。

　また、ダイクストラは「食事する哲学者の問題」が構造化プログラミングを使っても解けることを知っていた。

　なぜならば、さかのぼって1962年、「クリティカルセクションでの競合が起きない並列プログラミングは、3パターンの制御構造『連接』、『選択』、『繰り返し』から構成される」ことを数学者デッカーの証明にもとづいてダイクストラは発見していたからである。

原理

　経験上、クリティカルセクションでの競合が起きない並列計算の正しさ (correctness)は自明である。よって、我々が並列プログラミングの正しさを知覚するのは、プログラミング文法のわかりやすさを通じてである。

　この「文法のわかりやすさ」については、次の4つの原理を前提とするときに、成り立つ性質と考えるべきである。

構造化原理

制御構造「連接」、「選択」、「繰り返し」の連なりは、順序を守るかぎり、ダイクストラ不変量 (不変条件, invariant)が成り立つ超限帰納法であり、抽象化 (abstraction) ができる
抽象化とデータ型の型付けは等価である
段階的な洗練 (ソースコードを段階的に詳細に書いては、そのコードを捨てていく賽の河原の石積み方式の開発手法。step-wise refinement)はダイクストラ階層 (一筆書き、hierarchy)を構築する
ダイクストラ階層は、2台以上のつながった物理的な機械の上に、複数の数珠つなぎでつながった仮想的な機械を構築させる

　1，2で言う「抽象化」とはホーアの抽象化である。彼は「構造化プログラミング　第二部　データ構造化序論 (Notes on Data Structuring)」で抽象化について、次のように述べている。

抽象の過程は4つの段階に要約される。
　（1）抽象：　現実界の多くの対象物や状態が共通に持っている性質にもっぱら着目し、相互間の差異は無視することの決定
　（2）表現：　抽象された概念を表現する記号集合の選択。これらは情報交換の手段として用いられる
　（3）操作：　記号によって表現されたものの変換に関する規則で、現実界における類似操作の効果を予測する手段となる
　（4）公理化：　現実界から抽象された各種性質の厳密な記述。この性質は、現実界における操作と、それを表現する記号上での操作とが、共通に持っているものである。

（「構造化プログラミング　第二部　データ構造化序論 (Notes on Data Structuring)」ダイクストラ、ホーア、ダール共著、野下、河合、武市共訳、サイエンス社、1975年、97，98ページより引用）

　この抽象化の第三段階「操作」において、ホーアはダイクストラが指摘する制御構造と対応付けできると主張した。

　ダイクストラ階層は「第三部　階層データ構造」でクラスプログラミングに応用できる。ピラミッド型のトップダウン方式と、逆ピラミッド型のボトムアップ方式があるが、いずれも、漫画やアニメ表現のような雷のような形となるだろう。

応用

手続き（procedure)

1960年に仕様が発表されたAlgol60 言語には、FortranⅡの関数を拡張させた形式で、次のような特徴が見られる。

関数は入れ子にできる
関数はブロックの中に入れ子にできる
関数の内部で初めて宣言された変数や引数は、外部からアクセスできないプライベート変数である
関数は別の関数の引数として渡せる
関数の値は返してもよいし、返さなくてもよい
再帰呼び出し機構を備えている
この関数を手続き (procedure)と呼ぶ

C言語に似た擬似コードで手続き型プログラミングを書いてみよう。

手続き型プログラミング（擬似コード）

{
int x = 0;
{
int y= 1;
int f (int n) {
int g (int m) {
return n+m+x+y;
}
return g(12);
}
printf("%d\n", f(10) ); // 23を出力
}
}

クラスプログラミング

　さて、構造化プログラミング第三部階層データ構造では、ダール、ホーア、ダイクストラたちが、対象（オブジェクト、object)、クラス (class)、実例（インスタンス、instance)、this、部分クラス(サブクラス、subclass)、new構文を次のように触れている。

特殊な実例(instance)が集まったクラス(class)なのである。いい換えると、動的システムに現れる現象を、現象のクラスとしてひとまとめにし、それぞれのクラスをプログラム部分として記述しようというのである。

（「構造化プログラミング」199ページより引用）

存在し続けるブロックの実例のもとになる手続きをクラス(class)という。そして、その実例をそのクラスの対象(object)という。

（「構造化プログラミング」202ページより引用）

G5 :- new Gauss(5); G7 :- new Gauss(7);
……
G5.integral(F, A, B) …… G7.integral(F, A, B) ……（中略）手続き integralが対象の外部から何度も使われることを想定している。

（「構造化プログラミング」207ページより引用）

find: if x = val then this tree
（中略）
findの本体の中に現れる表現
　this tree
は、そのときに扱っている節、すなわち所属物 find の、この特定の実例を所有している参照を値としようとするものである。たとえば、Xの手続き find が関数呼び出し
　X.find(x)
で呼び出され、X.val = xであると、関数の値はX自身を指す参照値である。

（「構造化プログラミング」218ページより引用）

"truck", "bus", "car"は、クラスvehicleの部分クラス(subclass)と考えてよいであろう。

（「構造化プログラミング」228ページより引用）

　一般にクラスは手続きの拡張である。

コード(1), 再帰呼び出し機構を使った手続き、Algol60言語 (1960年リリース）

procedure hoge (x); int x;
begin
  procedure method(); begin...end
  method();
  hoge(x);
end

コード(2)、クラス、SIMULA67 (1967年リリース）

class Hoge (x); int x;
begin
    procedure method(); begin...end
end

ref(Hoge) hoge :- new Hoge(12);
hoge.x := 10;
hoge.method();

　コード中の変数 x はhoge手続きであっても、Hogeクラスであっても、寿命の来ない永続するプライベート変数である。

　コード(1)では、手続きの中に、同じ名前の手続きを呼び出すことで再帰呼び出し機構をサポートしている。コード(2)と同様に、メモリのヒープ領域にスタックを動的割り付け（動的アロケータ、dynamic alocator)して、プログラムが終了するまで、変数xが寿命を迎えることはない。

new構文

hoge :- new Hoge(12);

というnew構文を使ったコードでは、Hogeクラスから実例（インスタンス）であるhoge変数を作り出す。1972年に出版された構造化プログラミングでは、この実例こそ対象（オブジェクト）であると主張している。これはSIMULA開発者の二ゴールが主張するクラス = オブジェクト説と矛盾はしないが、後世の技術者たちに混乱を巻き起こした。

遠隔識別(remote identifier)

hoge.x;

hoge.x := 10;
hoge.method();

　このコードを構造化プログラミング第三部では、遠隔識別と呼んでいる。このように、SIMULA67言語において、ドット記法を使って、クラス内部の変数や関数にアクセスできる機能がある。

ダイクストラ選択

　先ほど示したhoge.xのような、ドット値を用い、クラスの属性物として、クラスのプライベート変数の値をパブリック変数にする方法を、遠隔識別と呼ぶ。また、この遠隔識別はダイクストラ選択による書き換えである。

　ホーアによれば、構造化法である直積(カルテジアン積、Cartesian product *1 )型の操作法として、成分値の選択や選択的な書き換えが挙げられる。

　例えば、次に示す直積型の複素数(complex)型宣言があったとしよう。

type complex = {
        realpart: real;
        imagepart: real
}

　このとき「x.imagpart: = 0」のように、「代入文の左辺に成分を書いて表す」（123ページより引用）のである。このようにすれば、real × real -> real、0 ∈ imagepartとするダイクストラ選択（選出）が可能となる。

ダイクストラ連接

　ダイクストラ連接は複文(compound statement) かクラスの連接を用いる。

直積型（構造化プログラミング第二部で紹介されたデータ構造化）

a: {
     x: 12;
     y: true;
     z: 0.1;
}

a.x; // 12
a.y; // true
a.z; // 0.1

手続き型プログラミング（複文でダイクストラ連接をしているもの。第一部で紹介）

a: {
     x;
     y;
     z;
     n: {
        x = 12;
        y = true;
     };
     m: {
        z = 0.1;
     };
     n();
     m();
}

クラスプログラミング（クラスの連接でダイクストラ連接しているもの。第三部で紹介）

a: {
     x: 12;
     y: true;
     n: {
     };
}
b < a: {
    z;
    m: {
       z = 0.1;
    };
}

x = new b();
x.m();
x.x; // 12
x.y; // true
x.z; // 0.1

　これら三つのコードはすべて、変数x,y,zに対してメモリの上では同じ内部表現であり、機械が判別することはできない。手続き型プログラミングだけ、メモリを解放するタイミングが早いのである。文法のわかりやすさにより、我々はこのコードが正しいことを知ることができる。

　このとき、2台以上の接続された物理的な機械が同一のメモリを共有していたと仮定しよう。ダイクストラ連接の順序がgoto文であべこべにならなければ、共有メモリの内部表現は変数xとyとzで固定される。それゆえに、互いに競合することはない。ここからメッセージを実装するには、コルーチン (コルティン、coroutine)と半コルーチン（半コルティン、semicoroutine)の実装が必要となる。

ダイクストラ繰り返し

　ダイクストラ繰り返しとは、もっぱらwhile文を用いて表現される。クラスのような再帰データ型の操作法は、while文の繰り返しによって行われる。そのため、クラスとnew構文による動的割り付け (動的アロケータ、dynamic allocator) はダイクストラ反復に対応づけられる。

　この再帰（帰納）と繰り返しというアイデアは、きわめてややこしい事態を引き起こす。だが、もし、構造化プログラミングのクラスを型なしラムダ計算で実装すれば、それはβ正規形を持たないラムダ式となるだろう。この話題は別の機会で考えていきたいので、ひとまず、ここで筆を置くことにする。

さいごに

　いわゆるgoto文論争は構造化プログラミングの本が1972年に出版されたことにより終決した。

　つまり、C言語では（ファイルやモジュールをまたがない）goto文は無害であるが、C++言語では有害なのである。

無害となる例 (C言語）

int f() {
   goto error;
}

error: //エラー処理

有害となる例（連接の順序があべこべになりダイクストラ階層構造化を破壊するC++言語)

class Hoge() {
     Hoge() {
         goto L1;
     }
}

class SubHoge(): public hoge {
     SubHoge() {
         L1: ...
     }
}

　この教訓をさいごに書いておくことで、この論争は決着が着いたとみなそう。

次回

dhrname.hatenablog.com

*1:構造化プログラミングの訳者である川合氏は、Cartesian productを「直積」と訳しているので、それに従うことにした

dhrnameのブログ

プログラミング関連を語るよ