dhrnameのブログ

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

構造化プログラミングに関わった人たちの出身国をWikipediaで調べてみた

構造化プログラミングに関係する科学者たちの出身国

はじめに

　この記事では、Wikipediaを使って、構造化プログラミングの関係者たちの出身国を調べた。Wikipediaの記事が出典不明だった場合、国名の後ろに?（疑問符）を付けておく

　また、敬称は略す。国家名は略称を用いる

出身国一覧

エドガー・ウィベ・ダイクストラ (出身国：オランダ）

　「メッセージ」を1965年に提唱*1。翌年、NATO国際会議において「Cooperating Sequential Processes」と題する報告書でメッセージを解説*2。68年にトップダウン方式とボトムアップ方式の『階層』を提唱

*3

　その後、60年代後半から『構造化プログラミング』と題する研究報告を毎年会議に提出。その中で「抽象データ構造」を提唱。72年に書籍として出版

オーレ＝ヨハン・ダール （出身国：ノルウェー）

　66年にNATO国際会議において「オブジェクトクラス」を提唱。翌年、SIMULA67言語でオブジェクトクラスを実装

　72年には書籍『構造化プログラミング』においてオブジェクトクラスやインスタンスやサブクラスを、SIMULA67を使って解説

チャールズ・アントニー・リチャード・ ホーア（出身国：イギリス）

　「構造化プログラミング」の影響を受けた『データ構造化』を70年に提唱。その理論と「抽象化」を解説した「データ構造化序論」は72年の書籍『構造化プログラミング』第二部に所収。また、『構造化プログラミング』第三部において、ダールのオブジェクトクラスとダイクストラの階層を結びつけた

　78年に「Communication Sequential Processes」を発表して、ダイクストラとダールの研究を紹介

ニクラウス・ヴィルト （出身国：スイス*4）

　ホーアとダイクストラの議論を経て、70年に「段階的洗練」を提唱。その論文は72年『構造化プログラミング』第一部に所収。

　70年にデータ構造化をサポートしたPASCAL言語をリリース。

デイビッド・ロージ・パーナス（出身国：カナダ?）

　ダイクストラの階層研究を元に「情報隠蔽」を提唱。また、構造化プログラミング研究を元に「モジュール化」を提唱

ピーター・ナウア（出身国：デンマーク）

　「作用（アクション）」と「クラスター」を69年に提唱。後に72年『構造化プログラミング』でダイクストラがアクションの概念を引用する。FortrunⅡ言語やAlgol60言語の開発者。BNFと略されるバッカス・ナウア記法で有名

バーバラ・リスコフ（出身国：アメリカ）

　ダイクストラの構造化プログラミングの影響を受けた*5「抽象データ型」を提唱。クラスター(Cluster)をサポートしたCLU言語を75年にリリース

Theodorus・Jozef・デッカー (Dirk・デッカー。出身国：オランダ）

　59年、自身が発見したクリティカルセクション競合問題の解決法とその正しさを、ダイクストラへ示す。このことが構造化プログラミングやメッセージのアイデアへとつながった*6

クリステン・二ゴール(ニガードとも表記。出身国：ノルウェー)

　60年に、「離散事象ネットワーク」を提唱。67年にはSIMULA67言語をリリース。その後、72年にホーアたちにより、『構造化プログラミング』で離散事象シミュレーションの解説が載る

参考資料

Wikipediaはリンクを略する。

*1:「 Solution of a problem in concurrent programming control」(E. W. Dijkstra著、 『Communications of the ACM』 Volume 8 Issue 9 1965年9月)

*2:「E.W.Dijkstra Archive: Cooperating sequential processes (EWD 123)」(E. W. Dijkstra　著、transcribed by Nick James and Ham Richards、revised Tue, 4 Dec 2007） https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html　閲覧日2020年6月16日

*3:「The Structure of the "THE"-Multiprogramming」(Edsger W. Dijkstra　著、Technological University, Eindhoven, The Netherlands、1968年5月)　

https://doi.org/10.1145/800001.811672

https://klevas.mif.vu.lt/~liutauras/books/Dijkstra%20-%20The%20structure%20of%20the%20THE%20multiprogramming%20system.pdf　閲覧日2020年3月19日

*4:「Niklaus Wirth was born in February 1934 in Winterthur, Switzerland」 Niklaus Wirth (閲覧日2023年4月7日)より引用

*5:リスコフは次のように述べている「I gave a talk [Liskov, 1973a] on abstract data types at a workshop on Programming Languages and
Operating Systems held in Savannah on April 9-12, l973. This talk merged the ideas of structured
programming and modularity」(「A History of CLU」
Barbara Liskov著、April l992　

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-561.pdf

より引用

*6:

E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)

と、

EWD35 translated. About the sequentiality of process descriptions

構造化プログラミングの歴史年表をまとめてみた

はじめに

ダイクストラの「構造化プログラミング」について歴史を年表としてまとめてみた。

技術革新は基礎研究の積み重ねによるものだ。このことをもっと理解してもらいたいという考えが、この年表をつくった私の動機である。(初版2023/02/02)

注意事項として、

  • 年表の正確さは保証できない
  • 年表に関する質問は一切受け付けない
  • 事実を裏付ける当事者のヒアリング調査はやっていない
  • 内容が後日修正されることがある
  • 引用は自由、ただし、それで発生する問題について責任は持たない

年表 (1957年～1978年)

1957年、ジャクソンが「待ち行列ネットワーク（待ち行列*1網、queueing network)」を提唱

1958年、コンウェイが「コルーチン (コルティン、共進譜、coroutine)」を提唱*2

同年、ダイクストラが学位論文「Communication with an Automatic Computer (自動機械での通信）」*3を発表

1959年、デッカーがダイクストラに対して、クリティカルセクション競合問題に関する解決法の正しさを証明*4

1960年、ナウアたちがプログラミング言語「ALGOL60」をリリース

同年、ニゴールがヨーロッパの学会で「離散事象ネットワーク*5（discrete event network)」のアイデアを発表

1965年、二ゴールとダールがプログラミング言語「SIMULA Ⅰ」をリリース。その言語で「new構文」と「疑似並列 (quasi-parallel)」を使ってコルーチンを実装

同年、ホーアが「レコードクラス(record class)」*6を提唱

同年、ダイクストラが「ダイクストラ・メッセージ(message)」を提唱。これはデッカーのアイデアに基づく。メッセージをプロセス同士でやりとりして、譲り合う仕組みを紹介*7

1966年、ダイクストラがNATO（北大西洋条約機構）主催のSummer School(Vilard-de-Lans)で「 Cooperating sequential processes（協調する逐次プロセス）」を報告。同報告書でダイクストラ・メッセージを使った「セマフォ(semaphores)」*8を提唱*9

同年、ダールがSummer School(Vilard-de-Lans)で「オブジェクトクラス(対象クラス、object class)」を提唱。これはレコードクラスを参考にしている*10

1967年、ダールとニゴールがプログラミング言語「SIMULA67」をリリース。オブジェクトクラスとメソッド*11とコルーチンとnew構文などを実装

同年、科学者たちがヨーロッパの学会で「virtual quantity」を提唱。「SIMULA67」で値呼び(call by value)だったメソッドの接頭語に「virtual」を付けることで名前呼び(call by name)にすることが可能となった

同年、フロイドが「Assigning Meanings to Programs」を発表

1968年、ダールとニゴールが論文「Class And SubClass Declaration」を発表。SIMULA67の「オブジェクト(対象、object)」やクラス、「サブクラス(部分クラス、subclass)」の概念を解説

同年、ダイクストラがトップダウン方式とボトムアップ方式の「階層構造 (hierarchical structure)」を提唱*12

1969年8月、ダイクストラがNATOの国際会合において、「構造化プログラミング」と題する研究報告の中で「 抽象データ構造 (abstract data structure)」を提唱。以降、毎年異なる内容の「構造化プログラミング」を報告し始める (原典1)

同年、ダイクストラが国際会合(ローマ）で「構造化プログラミング」を報告(原典2)。複数の物理機械の上に、複数の仮想機械たちがつながった階層モデルをつくる「洗練(refinement)」を解説

同年、ナウアが「アクション(作用、action)」と「クラスター(cluster)」を提唱

同年8月、ホーアが「An axiomatic basis for computer programming」*13を発表。これはフロイドのアイデアに基づく

1970年、ウィルトがプログラミング言語「PASCAL」をリリース。レコードと「ポインタ(pointer)」と「動的アロケータ(動的割付け、dynamic allocator)」を実装

同年、ホーアが論文「データ構造化序論」を発表 (原典3)。構造化プログラミングを数学理論で解説

同年、ダールがNATO主催のSummer School(Marktoberdorf)でSIMULA67について講義 (原典4)

1971年、ウィルトが「段階的洗練(step-wise refinement)」を提唱 (原典5)。これはダイクストラの洗練に基づく

同年、ホーアが「不変量 (invariant)」*14をプログラミングの正当性証明に導入*15

1972年、ダイクストラ、ホーア、ダールの三人が「構造化プログラミング」の書籍を出版。クラスの連接(継承)と抽象概念のダイクストラ階層構造を結びつける 。

「構造化プログラミング」書籍版の主な特徴
  1. 原典1～5をコピー加筆したもの
  2. 制御構造の3パターン「分解(decomposition)」と不変量を用いた証明の関連付け
  3. 抽象化とデータ型の関連付け (制御構造の3パターンをデータ構造化に見いだす）
  4. SIMULA67言語の解説
  5. クラスの連接（継承）とダイクストラ階層構造の関連付け
  6. クラスプログラミングによるダイクストラ法 (Leeのアルゴリズム)の実装
  7. オブジェクトクラスとコルーチンを通じて離散事象シミュレーションとセマフォの関連性を指摘

同年、パーナスが「モジュール化(modularization)」と「情報隠蔽(information hiding)」による分解をダイクストラ階層構造と関連付ける*16

1973年、リスコフが自身の論文で「抽象データ型(abstract data type)」を提唱。これは構造化プログラミングに基づく

1975年、サイエンス社が「構造化プログラミング」の邦訳版を日本で出版。これは1972年の書籍版を翻訳したもの

1978年、ホーアがダイクストラの研究とダールのクラスを紹介した論文「Communication Sequential Process（通信逐次プロセス 、通称、CSP)」を発表

訂正など

追記(2023年4月1日)

Algol Wの記述に誤りがあったので、削除

追記(2023年2月25日)

1972年のパルナス関連を年表へ追加。そのほか、「構造化プログラミング」でコルーチンが紹介されていることに触れる記述を年表へ追加

追記(2023年4月8日)

文中の「パルナス」の表記を「パーナス」に変更

*1:英語では、queueing、あるいは、waiting-line

*2:『KUNUTH The Art of Computer Programming 基本算法/基礎概念』(D.E.Knuth 著、廣瀬健 訳、サイエンス社、1989年9月) p.240

*3: (2) p.242

*4:

E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)

*5:離散事象ネットワークのモデルは待ち行列ネットワークであり、「中継点（station)」間を客が移動するネットワーク構造である。中継点には「待ち行列部 (queuing part)」と「サービス部 (service part)」が備わっている。後に「ネットワーク」の文言が外される

*6:「RECORD HANDLING」（C. A. R. Hoare著、Elliott Bros. (London) Ltd.　1965年7月） https://archive.computerhistory.org/resources/text/algol/ACM_Algol_bulletin/1061032/p39-hoare.pdf　閲覧日2020年1月25日

*7:「 Solution of a problem in concurrent programming control」(E. W. Dijkstra著、 『Communications of the ACM』 Volume 8 Issue 9 1965年9月)

*8:注意点として、セマフォには2種類の意味がある。一つは、三本の腕木を使って手旗信号のように通信する機械(主にフランス語、オランダ語）と、もう一つは、一本の腕木を操作して赤青を切り替える鉄道の腕木式信号機(主に英語）

*9:「E.W.Dijkstra Archive: Cooperating sequential processes (EWD 123)」(E. W. Dijkstra　著、transcribed by Nick James and Ham Richards、revised Tue, 4 Dec 2007） https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html　閲覧日2020年6月16日

*10:「The Birth of Object Orientation: the Simula Languages∗」(Ole-Johan Dahl　著、2001年6月pp.3-4）https://www.mn.uio.no/ifi/english/about/ole-johan-dahl/bibliography/the-birth-of-object-orientation-the-simula-languages.pdf　閲覧日2020年11月5日

*11:メソッドは当時、手続きの遠隔識別((remote identification)と呼ばれていた

*12:「The Structure of the "THE"-Multiprogramming」(Edsger W. Dijkstra　著、Technological University, Eindhoven, The Netherlands、1968年5月)　

https://doi.org/10.1145/800001.811672

https://klevas.mif.vu.lt/~liutauras/books/Dijkstra%20-%20The%20structure%20of%20the%20THE%20multiprogramming%20system.pdf　閲覧日2020年3月19日

*13:「An axiomatic basis for computer programming」C. A. R. Hoare著、 Communications of the ACM Volume 12 Issue 10、Oct. 1969 https://dl.acm.org/doi/10.1145/363235.363259

*14:「不変量」あるいは「不変式」は数学用語。不変条件とは訳さない

*15:「Proof of a program: FIND」 C. A. R. Hoare著、Communications of the ACM Volume 14< Issue 1 Jan. 1971 pp 39–45 https://doi.org/10.1145/362452.362489

*16:「On the Criteria To Be Used in Decomposing Systems into Modules」D.L. Parnas著、Communications of the ACM Volume 15 Number 12、December 1972

https://dl.acm.org/doi/pdf/10.1145/361598.361623

goto文+if文=while文、ただし、オブジェクトでgoto文は有害

goto文+if文=while文、ただし、オブジェクトでgoto文は有害

用語について

以下、「オブジェクト (対象、object)」、「クラス (class)」、「サブクラス (部分クラス、subclass)」、「インスタンス (実例、instance)」、「this」、「new」は1972年版の構造化プログラミングの定義に従う。かっこ内の訳は75年の日本語版*1訳者の武市正人氏による。

準備：goto文とif文とwhile文

goto文について

goto文はジャンプ文であり、指定した名前のラベル文にジャンプすることができる。例えば、以下のような擬似コードでは、Lのラベルが付いた行へ計算が移動する。...の部分はコードが実行されない。

goto L;

...

L: a = x + 1;

if文とwhile文について

詳しい説明を省いて、疑似コードだけを書いていく。if文は条件分岐であり、while文は反復である。

i = 0;

if ( i < 1) {

    a = i + 1;

}

while ( i < 1 ) {

    a = i +1;

    i = i+1;

}

while文の構成について

while文の構成を見てみると、条件式Xが成立する限り、{}で閉じられた中の文が実行される。これはif文と同じ構成に見える。

while (X) { ... }

if (X) { ... }

実際に、if文は一度だけ実行されるwhile文である。以下の擬似コード中のA && Bは「A かつ B」を意味する。AとBの式少なくともどちらか一方でも偽ならば、A && B = 偽である。Aが真であれば、あるいは、そのときにかぎり、Bが判定される。

i = 0;

while (X && i<1) {

    //一度だけ実行される

    i = i + 1;

}

上のコードはif (X) { ... }に相当する。

さて、とあるコードYを繰り返したいときはgoto文を使って、以下のようにすれば良い。

L: Y;

goto L;

このとき、Yは何度も繰り返される。

ここで、繰り返すgoto文へif文を組み合わせてみよう。

L: if (X) {

    Y;

    goto L;

}

このようにすれば、条件式Xが成り立つかぎり、Yはずっと繰り返される。ところがXが偽と判定されるやいなや、if文の中のgoto文は実行されず、繰り返しは停止する。

つまり、上記のコードは以下のwhile文と同じ動きをしているのである。

while (X) {

    Y;

}

goto文+if文をダイクストラは1967年まで好んで使っていた。

オブジェクトクラスの登場（SIMULA67言語、1967年）

オブジェクトクラスの連接

1967年、SIMULA67言語がリリースされた。この言語には画期的な技術が使われている。

特に、技術者たちが現在「継承 (inherit)」と呼んでいるクラスの「連接 (concatnation)」は、重要な技術である。ダイクストラたちは、72年版の構造化プログラミングでSIMULA67言語と連接を紹介している。

二つのクラスPとSについて、連接している疑似コード*2を次のように書ける。なお、クラスPを「前接クラス (Prefix Class)」、Sをサブクラスと呼ぶ。

class P() {

    x = 0;

    int procedure y() {

      return x;

    }

}

 

class P, S(){

    int procedure z() {

      return x+1;

    }

}

obj :- new S();

obj.y();  // 0を返す

obj.z()  // 1を返す

obj.y()のようにドットを使って内部の手続き(procedure)や変数にアクセスする識別子を遠隔識別(remote identtifier)という。SIMULA67では、遠隔識別を使ってobj.x = 10;も可能である。これを構造化プログラミングでは「カルテシアン積(直積)のダイクストラ選択」とみなす。

連接機能により、前接クラスPの変数xは、サブクラスSでも利用可能である。

インスタンスと再帰関数

構造化プログラミングにおけるインスタンスの定義から、クラスとnew生成は再帰関数*3を一回だけ実行したものと同等である。

例えば、以下のコードで、再帰関数Rが最初の一回目を実行したとき、変数xは永続的に0の値を保ち続けるのである。

procedure R() {

    x = 0;

    R();

}

上記のコードでは、一週目の x = 0はメモリ上で持続する。しかし、現実には変数xはスタックに積まれて、外部からアクセスできない。

手続きの連接

この変数xを使うためには、複数の手続き同士、あるいはブロック同士で連接し、選出するのがよい。すなわち、ブロックAとB同士が連接しているのだとすると、

A:{

    x = 0;

}

A, B:{

    x = x + 1;

}

B.x; // 1を返す

また、手続きPAと手続きPBが連接しているのだとすると、以下のコードのようになる。

procedure PA:{

    x = 0;

}

procedure PA, PB:{

    x = x + 1;

}

PB(); // xは1となる

ここで、注意してもらいたいのは、PAとPBの順序がひっくりかえることはありえないということである。かならずPA->PBの順を守る必要がある。この順序を守る必要性については、この記事では詳しく触れない。

実際には、手続き型プログラミングにおいて、手続きとブロックの連接は不可能である。そこで、72年に構造化プログラミングで紹介したクラスプログラミングが必要となる。

オブジェクトとgoto文

さて、オブジェクトを作成するときに、クラス内部でgoto文を活用するとどうなるだろうか。実際に連接したクラスAとB内をgoto文でジャンプするようにしてみよう。わかりやすくするためにコードの右端には行番号を付けてある。

1:  class A() {

2:     x = 0;

3:     int procedure y() {

4:       return x;

5:     }

6:     goto L;

7:  }

 

8:  class A, B(){

9:      L: x = 0;

10:    int procedure z() {

11:        return x+1;

12:    }

13: }

14: obj :- new B();

15: obj.y();  // ?

16: obj.z()  // ?

このコードから言えることは、obj:-new A();を実行したとしてもクラスBの内部で計算が実行されうる。なぜなら、6行目のgoto L;でクラスB内部にある9行目にジャンプしてしまうからだ。クラスAはクラスBに依存してしまっており、他のクラスとの連接は不可能である。たとえば、

class A {... goto L;}

class B {L:x=0;}

class A, C {...}

obj :- new C();

クラスAと連接するクラスCは成立しない。クラスA内部のgoto文がクラスBへジャンプさせてしまうからである。

よって、オブジェクトを扱う場合、goto文は有害である。

*1:「構造化プログラミング」（ダイクストラ/ホーア/ダール　共著、　野下/川合/武市　共訳、サイエンス社、1975年8月）

*2:SIMULA67言語では、{...}はbegin...endで記述し、return文はP:=12のように手続き文の名前Pを変数代入として使う

*3:原始的帰納的関数とは異なる

データ構造化における抽象化の定義 - 構造化プログラミングにおける覚え書きその5

データ構造化における抽象化の定義

前回

オブジェクトクラス同士でのダイクストラ連接 - 構造化プログラミングの覚え書きその4 - dhrnameのブログ

ホーアの「データ構造化序論」

　75年に翻訳され出版された『構造化プログラミング』*1の第二部で、ホーアは「データ構造化序論」を執筆した。ホーアによれば、ダイクストラとウィルトの助言に従って、この論を書いた。その論に従い、「抽象（abstraction)」、あるいは、「抽象化」について定義していこう。

抽象化の四段階

　一般に、抽象は、人間の思考の上で重要な役割をになう。それ以上に、プログラミングとは深い関係がある。「データ構造化序論」の中で、ホーアは抽象について次のように述べた。

複雑な現象を理解してゆく過程において、人間の理解力の助けとなる最も強力な道具は抽象（abstraction)である。（中略）抽象の過程は4つの段階に要約される。
　（1）抽象：　現実界の多くの対象物や状態が共通に持っている性質にもっぱら着目し、相互間の差異は無視することの決定
　（2）表現：　抽象された概念を表現する記号集合の選択。これらは情報交換の手段として用いられる
　（3）操作：　記号によって表現されたものの変換に関する規則で、現実界における類似操作の効果を予測する手段となる
　（4）公理化：　現実界から抽象された各種性質の厳密な記述。この性質は、現実界における操作と、それを表現する記号上での操作とが、共通に持っているものである。
（「構造化プログラミング」97，98ページより引用）

第一段階「抽象 (抽出）」

　まず、第一段階として、現実に起きている事がらについて、その共通点に着目する。共通点以外の違いを無視して考えることは、複雑な現象を理解する手助けとなる。これはけっして難しい作業ではなく、我々の日常作業でも見られるだろう。

　例としては、お金を数えるときに、その金額に着目すれば、お札や硬貨の重さや材質を気にする必要はないのである。ただし、先の引用では、「抽象」となっているが、「抽象の第一段階が抽象」と言うよりも、むしろ「抽象 (abstraction)の第一段階が抽出 (abstract)」と言ったほうがよい。先ほどの例で、我々は貨幣から金額という共通点を抽出したのである。そこで、今後、抽出と呼ぶことにする。

第二段階「表現」

　続けて、第二段階では、現実世界に起きている事がら、あるいは自分の考えを表現したいとき、その表現 (representation)によって指し示す情報を明らかにするのである。第一段階における共通する性質を表現するとき、その指し示したいものを「抽象概念（abstract concept)」と呼ぶ。

　人類が後世に記録を残すときに発明した手段は文字である。文字は発話、あるいは、書かかれた記号を通じて、情報を交換する。しかし、日常で使う文字は誤解を与えることがあるので、抽象概念の表現は、厳密な定義が求められるもの、例えば、数学や論理学で使われる記号がもっぱら選ばれるだろう。確かに、100円という金額の表現はアラビア数字の「1」、「０」、「0」の十進法が使われる。我々は、「いっぱい」や「少ない」というあいまいな表現を除くのである。

第三段階「操作」

　第三段階となると、表現を操作していく。ここで、操作そのものについて注意しなければならない。例えば、天気予報の図で、雨雲を動かしているのは現実の世界の雲ではなく、データ上のことである。雨ごいをしているわけではなく、データを変えさせて、雨雲の動きを再現していることから現実の動きを予測している。すなわち、データを変換した結果が現実に影響を与えるわけではないのである。

　こうしたデータから別のデータへの転換は、ある法則に従う。天気予報の例でいえば、物理法則によって、我々は現実の天候の移り変わりを予測することができる。その転換に使われる規則が操作なのである。

第四段階「公理化」

　最後に、第四段階においては、表現とその操作を実際に記述することになる。この公理化 (axiomatization)の目的について、ホーアは「（これらの公理が現実界を正確に記述しているという条件の下で）表現物の操作によって得られる結果が、現実界にもきちんと適用できると言うことを、厳密に証明する」（98ページ）ことであると述べている。

　あるいは、公理 (axiom)が「今日のプログラミング作業につきものの混同や誤りを減少させ、プログラムおよびプログラム手法の文書化と解説を容易ならしめることも可能」（100ページ）だと期待を寄せた。

　すなわち、ホーアによれば、表現と操作を記述した、第四段階目の公理化で、特定のプログラムが正しいのかどうかを調査できるというのである。

抽象の例

　理解を深めるために、抽象の例を挙げてみよう。まず、お金を数える例でいくと、1円玉を1枚数えるとき、
1(円玉）を1（枚）
とカッコの中に書かれた違いは無視して、1という共通の性質を取り出すことができる。

　さて、ホーアは抽象概念の例として「数 (number)」を挙げた。先ほどはお金であったが、現実において、昔の人が最初に数えたのは自然界にあるような石ころや、木の枝であったと考えられる。どのような木の種類であるかは無視して、枝が何本あるかを数えていくとき、それを記録する必要がある。

　第一段階で抽出された数を表現するために、人が使用したのは数字という記号の集まりであった。当初は木の棒を表現する簡単なものであったと言われる。ローマ数字では縦の棒を引いて、Ⅰ、Ⅱ、Ⅲと書いていく。漢数字では横の棒を引いて、一、二、三と書いていく。しかしながら、4、５、6...と数を多くしていくと、この二種類のやり方では不便である。時代が下り、ゼロが発明されると、1、2、3と、簡単な書き方ができるアラビア数字と、十進法の方式で数を表現するようになった。

　第三段階の操作において、数は和という演算をする。例えば、1 + 1のように計算をして、1を加えて別の数をはじき出そうと言うのである。この段階において、数の性質について厳密な定義が求められる。

　そこから、次の段階に移ると、peanoの公理が現れた。この公理は人工のお金であろうと、自然界の石や木の枝であろうと、現実における数を厳密に定義することができるのである。確かに、節の冒頭の「数える」という行為は、第三段階の和という操作と一致する。

結論

　このように、抽象化を4段階の「抽出 -> 表現 -> 操作 -> 公理化」に分けて考えていくと、現実の世界への理解が容易となる。ダイクストラ構造化原理において、この抽象化と型付けは等価である。この原理がデータ構造化の支柱となるだろう。

次回

ダイクストラ不変量とクラスの抽象化 - (構造化プログラミングの覚え書き その6) - dhrnameのブログ

*1:『構造化プログラミング』ダイクストラ/ホーア/ダール　共著、　野下/川合/武市　共訳、サイエンス社、1975年8月）

オブジェクトクラス同士でのダイクストラ連接 - 構造化プログラミングの覚え書きその4

この記事について

前回

データ構造化理論の型選択演算子によるダイクストラ選択 - 構造化プログラミングの覚え書きその3 - dhrname’s diary

　今回は構造化プログラミングで触れられているオブジェクトクラス同士のダイクストラ連接について考察を加える。なお、この記事は私個人による独自解釈である。

　「オブジェクト(対象, object)」、「クラス(class)」、「インスタンス(実例, instance)」、「サブクラス(部分クラス, subclass)」「new構文」の定義は1975年に日本で出版された「構造化プログラミング(ダイクストラ、ホーア、ダール共著、野下、川合、武市共訳、サイエンス社）」に従う。

　ダイクストラ構造化原理によれば、「3パターンの制御構造による抽象化 = 型付け」である。その3つのパターンのうち、今回はダイクストラ連接について考える。第三部のクラスプログラミングの考え方を見ていこう。

オブジェクトクラスの連接

クラス構文

今、次のようなクラス構文を使って、クラスAをつくる。このコードはSIMULA67言語の構文に似たものである。

class A()

begin

   int x := 0;

    procedure f()

    begin

    end

end

インスタンス

このクラスAをインスタンスaとして生成するためには、以下のようなnew構文を使った生成子(generator)を用いる。

Ref(A) a :- new A();

コード中の変数 a はインスタンス変数である。なお、Ref(A)はデータ型の宣言であり、型Aへの参照(reference)を意味する。

インスタンスは以下のような再帰関数と同じく、無限に繰り返されるときに、永続する変数に似ている。

procedure A()

begin

  int x := 0;

  A();

end

この再帰関数によって無限に宣言される変数xは、永遠に寿命を迎えることがなく、メモリ上に生き続ける。従って、メモリの節約のためには、ガベージコレクションを使い、積み上げられたスタックをどこかのタイミングで解放してやるのが良い。

ダイクストラ選択によるアクセス

内部の手続き、つまり、procedure fにアクセスするためには、インスタンスとホーア・データ構造化を用いて、ダイクストラ選択（選出）をするとよい。

Ref(A) a:- new A();

a.x;

a.f();

この入れ子になっている内部の変数xや手続きfをダイクストラ選択する方法をSIMULA言語では遠隔識別(remote identifire)と呼ぶ。ホーアとウィルトはその遠隔識別を選択子(selecttive)と呼んだ。*1

続けて、同様にクラスBをつくって、クラスAと連接させる。このとき、クラスAは前接クラス(prefix class)と呼ばれる。

A, class B()

begin

  procedure g()

  begin

    g := x;

  end

end

Ref(B) b :- new B();

b.g();

このとき、選択子b.g()は、前接クラスAの内部変数xの値0を返す。前接クラスAに対して、クラスBは部分クラスを形成する。

内部変数xは局所変数であるので、クラスを使わないコード、例えば、

begin

  int x := 0;

end

x := 10;

というように書けば、ブロック外部からのアクセスエラーとなる。すなわち、情報隠蔽は常に成立している。

情報隠蔽された局所変数xへ外部からアクセスする方法は、「クラス同士のダイクストラ連接」、「インスタンスへのダイクストラ選択」によるものである。また、そのときに限って、隠蔽されていた情報が外部へ公開される。

つまり、言い換えれば、構造化プログラミングは情報隠蔽されていた変数、手続きを外部へと公開する手段なのである。

次回

データ構造化における抽象化の定義 - 構造化プログラミングにおける覚え書きその5 - dhrnameのブログ

*1:詳しくは冒頭で示した構造化プログラミングの第二部「データ構造化序論( Notes on Data Structuring)」を参照せよ

データ構造化理論の型選択演算子によるダイクストラ選択 - 構造化プログラミングの覚え書きその3

データ構造化理論におけるダイクストラ選択

構造化プログラミングの72年書籍版は三部構成

前回

ダイクストラの構造化プログラミングの書籍版は三部構成 - 構造化プログラミングの覚え書きその2 - dhrnameのブログ

 

　1972年に出版された構造化プログラミングは以下のように三部構成である。

  1. ダイクストラの構造化原理（原理）
  2. ホーアのデータ構造化（理論）
  3. ダールのクラスプログラミングとコルーチン（実践）

　今回はこの中で、第二部のデータ構造化序論を取りあげる。制御構造であるダイクストラ選択の型選択演算子(セレクタ, selecter)について見ていこう。なお、この記事は私個人による独自解釈である。

ダイクストラ構造化原理

　ダイクストラによれば、データ型の型付けと抽象化 (abstraction) は等価である。また、3パターンの制御構造を使って抽象化が可能となる。これをプログラミングの構造化原理と呼ぶ。

　ホーアによれば、抽象化は次の四段階を経る。

  1. 抽象（抽出のこと)
  2. 表現
  3. 操作 (変換のこと)
  4. 公理化

　この記事では主に3段階目の操作について着目する。

データ型の変換

　あるデータ型から別のデータ型へ変換する演算子には、次の二つの方式がある。

  1. 構成演算子 (コンストラクタ, constructor)
  2. 選択演算子 (セレクタ, selector)

　構成演算子は複数のデータ型から一つのデータ型にまとめることができる。例えば、構造化された型の場合、

<X, Y> -> X × Y

などのように、nタプルからただ一つのデータを変換できる。

　逆に、選択演算子は一つにまとまったデータ型の中から、ある一つのデータ型を選び出すことができる。

　この記事では、この選択演算子をもっぱら考えることにしよう。

配列の型選択演算子

　構造化プログラミングにおいて配列は写像である。0を含む自然数集合の有限部分集合を定義域とし、ユーザが指定した集合を値域とみなす。その値域から一つの要素を選出するには、一般に、以下のような[]を使った型選択演算子を使う。

array[i];

　この配列は次のような写像Fを意味する。自然数集合の有限部分集合Xとユーザが指定した集合Yについて、

F: X -> Y (ただし、i∈X, array[i]∈Y)

　また、

array[i] = 12;

であるときに、以下のようなダイクストラ選択（選出）が可能となる。

F: X -> Y (ただし、i∈X, 12∈Y) 

直積型の型選択演算子

　構造化プログラミングにおいて、ドット(.)を使った記法で直積型の選択演算子を表現できる。ユーザが指定した集合XとYについて、X×Yであるような直積cについて、

c.x;

c.y;

　また、

c.x := 12;

c.y := 15;

　これは以下のように直積のx成分、y成分からダイクストラ選択（選出）をする射影pr_x(c)、pr_y(c)である。

添数集合{x, y}をΛとおくと、pr_λ(c), λ∈Λとして、

pr_x(c): X×Y -> X  (ただし、c.x∈X, 12∈X)

pr_y(c): X×Y -> Y  (ただし、c.y∈Y、15∈Y)

 すなわち、それぞれ直積型から一つの型を選び出しているのである。

べき集合型の型選択演算子

　べき集合型は二つの直積型である。よって、型選択子は直積型で使われるものと同じである。すなわち、集合Xに対するべき集合P(X)について、仮にx1, x2, ...xnを Xの元とすると、P(X)の元y（すなわちy∈P(X), y⊂X)に対して、次のような条件が成り立つ直積型dである。

  1. xm∈y (ただし、0 < m<= n)ならば、d.xm = 1
  2. xm∉y (ただし、0 < m<= n)ならば、d.xm = 0

　例えば、X={a, b, c}であるときに、P(X){ ∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} }であるから、二つの直積型c, dの選択演算子を使って、

c.x1 = a

c.x2 = b

c.x3 = c

d.x1 = 0

d.x2 = 1

d.x3 = 1

はP(X)の元 {b, c}を表す。他のP(X)の元も同様である。

直和型の型選択子

　構造化プログラミングにおいて、直和型の選択演算子はホーアcase文 *1である。簡単のため、二つの集合の直和について考える。ユーザが指定する集合XとYとuについて、

  1. X ⋂ Y = ∅
  2. X ⋃ Y = u

これらの条件を満たす直和型uに対して、

case u of

 X: u.x;

 Y: u.y;

end

 

　例えば、ユーザが指定した文字列からなるString集合と数値からなるNumber集合の直和型snについて、

case sn of

 String: sn.i = "12";

 Number: sn.i = sn.i + 12; 

end

　このcase文は、Number集合が空集合で、String集合が空集合でないとき、sn = {"12"....}である。

　一方で、sn  = {2, 12, 15...}であるとき、

case sn of

 Number: sn.i = sn.i + 12; 

 String: sn.i = "12";

end

　これはsn = {3, 13, 15....}の結果を生じさせる。

　複数の集合による直和型Yについては、次の条件を満たす。

  1. Xi ⋂ Xj = ∅ , i ≠ j
  2. X1 ⋃ X2 ⋃ ... ⋃ Xn = Y

case文の利用方法は二つの集合による直和型と同様である。

参考資料

  1. 「構造化プログラミング」（ダイクストラ/ホーア/ダール　共著、　野下/川合/武市　共訳、サイエンス社、1975年8月）
  2. 「集合・位相入門」(松坂和夫 著、岩波書店, 2017年7月）

次回

dhrname.hatenablog.com

*1:原文ではwith構文を使っている