[表紙へ]
▼ 変更履歴

翻訳:構造化プログラミングを最初に提唱した文書

はじめに

ここでは、 構造化プログラミング 構造化定理 の違いなどを説明した後に世界で最初に「構造化プログラミング(Structured programming)」という言葉を用いた文章 "7.4 STRUCTURED PROGRAMMING"(1969年) の翻訳を掲載します。

NATOソフトウェア工学会議によると、この文章は論文(Paper)ではなくて、研究成果報告書(Working paper)ということになっています。研究成果報告書は、研究の概要や成果を書いたものです。

"7.4 STRUCTURED PROGRAMMING" を書いたダイクストラ博士は、1972年に他の科学者と共同で "Structured programming" という本を出版します。これが構造化プログラミングのバイブルになっています。

目次

  1. 構造化プログラミングと構造化定理の違い
  2. "7.4 STRUCTURED PROGRAMMING" の翻訳について
  3. 【翻訳】7.4 構造化プログラミング
    1. 序文
    2. プログラムの大きさ
    3. プログラムの正しさ
    4. プログラムと計算処理の間の関係
    5. 抽象化データ構造
    6. 真珠をつなげたネックレスとしてのプログラム
    7. 最後に
  4. 構造化プログラミングに関するリンク

構造化プログラミングと構造化定理の違い

筆者がこのページを作成しようと思った動機は、ネット上に「CASIO BASIC は構造化プログラミング可能」という誤りを力説する人がいたからです。 その人は、構造化定理のことを構造化プログラミングだと思っているようです。

CASIO BASIC は、CASIO のプログラミング関数電卓やグラフ電卓に使われているプログラミング言語の通称です(正式な名称はない)。 ローカル変数がなく、グローバル変数も名前1文字のものしか使えない簡易言語です。 ユーザーが関数を定義することはできません。 サブルーチンはあるのですが、呼出元とサブルーチンが同じグローバル変数を共有して使います。

しかし、その人に限らず、構造化プログラミングと構造化定理を混同している人は非常に多いのです。

以下の表を見て下さい。

構造化プログラミングと構造化定理の違い
名称 構造化プログラミング(Structured Programming) 構造化定理(Structure Theorem)
考案者 エドガー・ダイクストラ(Edsger Wybe Dijkstra) ハーラン・ミルズ(Harlan Mills)
発表年 1969年 1970年代初頭
目的 大きなプログラムを書いた時点でプログラムの正しさを証明する。 プログラムから goto文をできるだけ排除する。
手段 ・段階的抽象化(ボトムアップで抽象化)
・段階的詳細化(トップダウンで詳細化)
・抽象化データ構造とその上で動作する抽象化文との共同詳細化(後のオブジェクト指向のクラスに通じる)
・プログラムの階層化
など
プログラムを「順次」「反復」「分岐」によって記述し、goto文をできるだけ排除する。

多くの人が構造化定理のことを構造化プログラミングと混同していますが、上の表のように完全に異なるものです。

ただし、構造化プログラミングの一部として、構造化定理と同様の「goto文よりもできるだけ順次・反復・分岐(+手続き呼出)を使う」が含まれているのは確かです。 しかし、構造化プログラミングにとっては、一部の要素にすぎません(段階的抽象化のために必要とされているだけ)。 構造化プログラミングの目的は「大きなプログラムを書いた時点でプログラムの正しさを証明する」であり、goto文の排除はそのための一部の手段にすぎないのです。

一方、構造化定理は、1966年に発表された 'Böhm-Jacopini theorem'(ベーム-ヤコピーニの定理)というフローチャートのための定理が元になっており、構造化プログラミングの影響を受けて、ハーラン・ミルズがそれを焼き直したものです。 その目的は「プログラムから goto 文をできるだけ排除する」という非常に単純なものです。 「能力の低いプログラマーでも goto文を使わなければ、少しはマシなプログラムが書ける」という程度のことに過ぎません。

しかし、構造化プログラミングと構造化定理が混同されてしまったのです。 名前が似ている(英語でも似ている)上に構造化定理の方が簡単で効果もそれなりにあったからでしょうか。

さらに構造化プログラミングが未完成な理論だったというのもあるでしょう。 その目的が 「大きなプログラムを書いた時点でプログラムの正しさを証明する」 という途方もないものです。 おそらく、その目的は実現不可能だったでしょう。
しかし、構造化プログラミングが提案した手段(上表参照)は今では当然のこととなっており、その実質的なソフトウェア工学への影響は構造化定理をはるかに越えていると言えるでしょう。

ここまで読めば、「CASIO BASIC は構造化プログラミング可能」と力説する人がおかしいことに気がつくでしょう。 CASIO BASIC は、プログラムの階層化ができません。抽象化データ構造も作れません。 構造化プログラミングを実現するには、少なくともC言語程度の機能が必要です(できれば、オブジェクト指向言語を使うべき)。

ただし、CASIO BASIC は、構造化定理を満たしているかもしれません。 しかし、CASIO BASIC は、過去機種との互換性を保つせいか goto文(あるいは、それに類する命令)を積極的に排除していません。

▲このページの先頭へ

"7.4 STRUCTURED PROGRAMMING" の翻訳文について

下記リンクの書類の "7.4 STRUCTURED PROGRAMMING"(P65〜P68)が、ダイクストラ博士の構造化プログラミングの研究成果報告書(Working paper)です。
ダイクストラ博士はこの文章で初めて「構造化プログラミング(Structured programming)」という言葉を使いました。

SOFTWARE ENGINEERING TECHNIQUES
Report on a conference sponsored by the NATO SCIENCE COMMITTEE
Rome, Italy, 27th to 31st October 1969

(上の直接リンクが嫌な場合、下のページの右の冊子をダウンロードする)
The NATO Software Engineering Conferences (ニューカッスル大学)

このPDF書類は、1969年8月27日〜8月31日にイタリアのローマで開催されたNATOソフトウェア工学会議(The NATO Software Engineering Conferences)のレポートです。 この会議を主催したのは、NATO科学委員会(NATO SCIENCE COMMITTEE)であり、現在は NATO Science for Peace and Security(平和と安全のためのNATOの科学)と合流して消滅しています。

上のPDF書類は原典をテキストデータ化してページ配置を変更したものです。 それなのに目次(CONTENTS)のページ番号が修正されていないので、目次のページ番号と実際のページ番号がずれてしまっています。 そのため、本文中に 85 (背景が黒の数値)のような数値が印刷されており、それが原典のページ番号を示しています。 さらにこの書類の2ページ目に書かれているようにOCRで読み取ったものを修正したものなので、多少の誤字が含まれている可能性があります。

ネット上に何故か翻訳された文章もないようなので、自分で翻訳しました。すでに同文章の翻訳があれば申し訳ございません。 筆者の英語力で翻訳するには難しい文章でした。翻訳が下手だと思われた時はご容赦ください。 原文を尊重して意訳は最小限にしています。ほぼ直訳なので、分かり難いところは [1-1] のような訳注を付けています。

多少の誤訳もあるでしょうが、構造化プログラミングが構造化定理とは完全な別物ということは理解できるでしょう。
(以下の翻訳文を読むにはコンピューター工学の知識が必要です)

▲このページの先頭へ

【翻訳】7.4 構造化プログラミング

7.4 構造化プログラミング

E.W. ダイクストラ著

序文

この研究成果報告書(Working paper)は、去年著者が行ったプログラミング実験の中で得られた経験と洞察について報告する。 主な疑問は、我々のプログラミング能力を一桁増やすことが可能かどうか。そして、そのためにどのような技法(精神的、組織的または機械的な技法)をプログラム構築の過程において適用できるのかということであった。 そのプログラミング実験はこれらの疑問に光を当てるために行われた。

プログラムの大きさ

私が心から心配していることは、本質的に大きいプログラムに存在している。 「本質的に大きい」とは、プログラムがその課題の複雑さゆえに大きくなっていることを意味しており、爆発して大きくなったプログラム(不適切な知識、不幸な決断、問題の不十分な理解、その他による)とは対照的である。 事実、現実的な理由から、私の実験は今までのところかなり小さなプログラムで実行しなければならなかった。 そのことが深刻な難しさを示していた。 私は明確に大きさの問題を扱うこと、そして(未だに非常に高価な [1-1] )実験よりもむしろ分析・観察・熟考によってできるだけ多くの結果を見つけ出そうとすることによって、それを克服しようと試みてきた。

そうすることで、どうやら実現するために学ぶ必要がある多くの下位目標 [1-2] を発見した(やり方を知らない下位目標であれば、我々は学ぶ必要がある)。

[1-1] 当時(1969年)のコンピューターは非常に高価で大型だった。そのため、現在のように気軽に使えるものではなく、実験には多くの費用がかかったことだろう。
[1-2] 構造化プログラミングを実現する手段のことと思われる。

もしもある大きなプログラムが N 個の「プログラム部品」から構成されており、N が非常に大きいならば、個々の部品の信頼性レベルは例外的に高い必要がある。もしも個々の部品が正しく動作する確率 "p" で表現できるならば、大きな N に対してプログラム全体の機能が正しく動作する確率は

P = p N [1-3]

を超えることは厳密にはありえない。P が 0 よりもはるかに大きいならば、p は 1 にほぼ等しくなければならない [1-4]。 部品を組み合わせてより大きな部品を組み立てて、大きな部品からプログラム全体が構成されていても何の解決にもならない。

p (N/2) * p (N/2) は、それでも p N に等しいのだ! [1-5]

結果として、プログラムの正しさ(信用できるレベル)の問題は、私の主な懸念の1つであった。

[1-3] 原文は P = P N となっていたが、誤植であろう。
[1-4] 例えば、個々の部品が正しく動作する確率 p = 0.99999 だとしても部品点数 N = 10,000 だとしたらプログラム全体の機能が正しく動作する確率 P = p N ≒ 0.905 ≒ 90.5 % に過ぎない。大きなプログラムにおいて、p が1に極端に近くないと、P は信頼できる数値にならない。
[1-5] 部品点数 N のプログラムを単純に半分に分割して2つの部品に分けると、個々の部品が正しく動作する確率は p (N/2) になるが、2つを合体すると、P = p (N/2) * p (N/2) = p N なので、同じことになる。

十分説得力のある方法でプログラムの正しさを証明するために必要とされる労力(それが知的にせよ実験的にせよ)は、プログラムの長さ(均等かつ大雑把に測定される [1-6])に比例するよりも速く増大することはないのかもしれない(労力の増大速度は多少大雑把に測定される [1-7])。 もしも、例えば、N 個のプログラムの部品(それら1つ1つは正しいと仮定される)からなるプログラム全体の正しい構成の検証に関わっている労働者が N に従って指数的にさらに増大するならば、我々は敗北を認めた方がいい。 あらゆる大きなプログラムは多くの異なるバージョンの中のそのバージョンの存続期間の間に存在する。 その結果、大きなプログラムを構成する場合、単一のプログラムに関心をそれほど持つことはない。 しかし、関連するプログラムの全集団に関心を持たないといけない。全集団には、同じ課題のための代わりになるプログラムや類似の課題のための類似のプログラムを含んでいる。 それゆえに1つのプログラムは全集団の1つのメンバーとして考えられ、理解されるべきである [1-8]。 プログラムは部品から構築されるべきなので、この集団の様々なメンバーは部品を共有し、共有された部品の正しさの証明を共有するだけでなく、共有された下位構造の正しさの証明も共有することになる [1-9]。

[1-6] 原文は "(measured in an equally loose sense)" であり、意味がよく分からなかった。「大雑把な測定だが、測定箇所が違っても大雑把さの程度は均等」ということだろうか?プログラムは同じ動作をするものでも書き方で長さが変わるので、プログラムの長さを正確に測定することは確かに難しい。
[1-7] 原文は "(measured in some loose sense)" であった。「プログラムの正しさを証明するために必要とされる労力が増大する速度」を正確に測定するのは確かに難しいだろう。
[1-8] 1つのプログラムは多くのバージョンの1つに過ぎない。ダイクストラ博士は、プログラムがバージョンによって変化していく様子を観察し、部品の共有やプログラムの階層化という考えに至ったのだろう。
[1-9] 「共有された下位構造の正しさの証明も共有する」とは、プログラムの階層化の利点を述べていると思われる。

プログラムの正しさ

プログラムの正しさの成立条件 [2-1] は、このプログラムによって引き起こされるかもしれない計算処理の正味の影響についての成立条件である。 そのような成立条件がどのようにすれば正しいとすることができるのかを検証するために、私は以下の結論に至った。

[2-1] 「成立条件」は原文において "assertion" である。コンピューターの世界では「表明」と訳することが多い。しかし、分かり難いので「成立条件」とした。この後も同様に訳す。
  1. 異なる入力の数、すなわち、その成立条件に必要な異なる計算処理の数があまりにも途方もないくらい多いので、標本抽出による正しさの証明 [2-2] はその疑問の完全に範囲外にある。 プログラムの検証はバグの存在を示すために使われてきたが、バグが存在しないことを示すことは決してありえない! それゆえにプログラムの正しさの証明は、プログラムテキストのみに依存するべきである。
    [2-2] 「標本抽出による正しさの証明」とはデバッグのことであろう。デバッグは試験項目だけを確認したというだけでプログラムの正しさの証明には絶対にならない。そのため、ダイクストラ博士はプログラムテキストを作成した段階で正しさを証明するべきだと主張しているのである。実際にそのようなことが可能かどうかは疑問であるが、理想として述べているのであろう。
  2. 多くの人々がプログラムの正しさは証明可能であることを示してきた。 非常に形式的な正しさの証明が与えられてきた。さらに正しさの証明は「通常のプログラム」のために与えられてきた。すなわち、証明の手続きを念頭に入れて記述されていないプログラムである。 予想通り、その繰返しがあるプログラムの例は、かなり小規模なプログラムを前提としている(そして、そのことを誰も批難しない)。それゆえに対策を講じない限り、検証に参加する労働者の数はプログラムの大きさに伴って爆発的に増大することになるかもしれない [2-3]。
    [2-3] 当時(1969年頃)のプログラムの正しさの証明は小規模なプログラムだけに対して行われてきたので、プログラムが大きくなるとそれらの証明は何の役にも立たないということであろう。
  3. それゆえに私の関心を「与えられたプログラムの正しさをどのようにして証明するのか?」という疑問に集中させてこなかった。しかし、「どのようなプログラム構造に対して、過剰な労働者を使わずに正しさの証明を与えることができるのか?たとえプログラムが大きくなっても」という疑問、それに続いて「そのような良く構造化されたプログラム(well-structured program)を与えられた課題に対してどのように作るのか?」という疑問については私の関心を集中させている。 そのような(全ての存在し得るプログラムの集合の部分集合としての)「良く構造化されたプログラム」に注目するという私の意欲は、プログラミングに必要な条件を満たす良く構造化された部分集合 [2-4] を発見できるという私の信念に基づいている。すなわち、それぞれのプログラミング可能な課題に対して、この部分集合は十分現実的なプログラムを含んでいる。
    [2-4] 「良く構造化された部分集合」は「(全ての存在し得るプログラムの集合の部分集合としての)良く構造化されたプログラム」のことであろう。
  4. 「プログラムの正しさの問題に対する構成手法」と私が呼んでいるこれは、さらなる一歩を進ませることができる。 それは、どのようなプログラム構造が証明可能性の視点から見て魅力的なのかという一般論に制限されない。 多くの特殊で非常に困難なプログラミングの課題において、計算処理のある分類が一定の必要条件を満たすであろうことをどのようにして証明できるのかということを分析することによって、私はついにあるプログラムを構築することに成功した。 その証明に必要な条件から、そのプログラムが得られたのだ [2-5]。
    [2-5] プログラムの正しさの証明に必要な条件を分析によって見つけ出し、それらの条件を満たすようにプログラムを作成したということだろう。

プログラムと計算処理の間の関係

実行可能な計算処理(時とともに進化する [3-1])についての成立条件がどのようにして静的なプログラムテキストから作られるのかを調査したところ、様々なプログラムの動作手順からの段階的抽象化 [3-2] を可能にするために厳格で順序付けられた規律に忠実であることが重要であると私は結論づけた。 特に逐次処理コンピューターのためのプログラムがコンピューター言語の基本的な記号の直線的な連続 [3-3] として表現されるとき、ラベルの付いた箇所への転送制御文 [3-4] よりもむしろ、実行順序は二者択一的、条件的、そして反復的な節と手続き呼び出し [3-5] によって制御されるべきである。

[3-1] 時が経ってコンピューターが進化すると、計算できることも進化する。
[3-2] 段階的抽象化とは、プログラムテキストから意味のあるまとまりを見つけて、それを括り出して一つの抽象的なまとまりにすること(抽象化)を繰り返すことである。抽象化を繰り返すので、抽象的なまとまりが段階的に構築される。C言語で言えば、プログラムの一部を関数にしてまとめることと同様である。C言語で関数化を繰り返せば、自然に関数の関係が段階的になるだろう。
[3-3] プログラムは直線ではないように見えるが、テキストエディタが改行コードを考慮して表示しているからそう見えるだけであって、テキストデータ自体は直線的なデータである。
[3-4] 「ラベルの付いた箇所への転送制御文」とは、goto文のことである。この文書において、goto文に触れるのはここだけである。
[3-5] この箇所は後に「順次、反復、分岐、そして手続き呼び出し」に整理される。

局所的な順序 [3-6] からの段階的抽象化のために必要なことは、以下の実例によっておそらく最も確信的に示される。

[3-6] 「プログラムの一部(局所)の動作順序」という意味であろう。後述のプログラム(3)のようにプログラムの一部を抽象化することを繰り返して、後述のプログラム(1)のように縮小できる。

形式(1)の「展開された(stretched)」プログラムを考えてみよう。

S 1 ; S 2 ; . . .; S N (1)

そして、個々の文 S j を実行した正味の影響が与えられているとき、プログラム(1)の正しさを立証する(すなわち、連続した N の行動の正味の影響の累計が、プログラム(1)によって実行される計算処理に課された要求を満たすということを立証する)ことが理論上 N の手順を必要とするという測定の決まり事を導入しよう。

形式(2)の文について、

if B then S 1 else S 2 (2)

ここで再び、構成する文 S 1 と S 2 の実行による正味の影響が与えられているとする。 プログラム(2)の正味の影響を立証することが、理論上2つの手順を必要とするという測定の決まり事を導入する。 換言すると、Bが真の場合とBが偽の場合があるということである。

さて、形式(3)のプログラムを考えてみよう。

if B 1 then S 11 else S 12 ;
if B 2 then S 21 else S 22 ;
.
.
.
if B N then S N1 else S N2 (3)

二者択一の文(if文)を理解するために二者択一の文毎に2つの手順を必要とするという測定の決まり事に従う [3-7]。 すなわち、以下の文の正味の影響を立証するということである。

if B i then S i1 else S i2

この文の正味の影響は、抽象化文 S 1 を実行したときの正味の影響と等価である [3-8]。 このような二者択一の文が N あるとすると、プログラム(3)をプログラム(1)の形式に縮小するために 2N の手順を必要とする。 プログラム(1)を理解するために N の手順が必要であり、全部で 3N の手順が必要である [3-9]。

[3-7] if文で実行される文は1つだけであるが、if文を理解するために2つの選択肢を理解する必要があるということ。
[3-8] この文は S i1 または S i2 のどちらか1つだけを実行するので、正味の影響は S 1 と等しい。
[3-9] 前述のように1つの if文を理解するには2つの手順が必要という仮定なので、if文が N 個あれば、理解するのに 2N の手順が必要になる。理解すれば、プログラム(1)に縮小できる(抽象化できる)。さらに縮小後のプログラム(1)も理解しないといけないので、N の手順が必要。合計で 2N + N = 3N になる。しかし、訳者はこれを極論と思っている。その理由は後述する。

もしも我々が抽象化文 S i の導入を拒否し、文 S ij の実行を使ってプログラム(3)を直接的に理解しようとしたならば、プログラム(3)のような計算処理は、S ij のような文を N 実行したときの累計の影響であり、それを理解するためにそれ自体が N の手順を要求するだろう。 Sij を使ってアルゴリズムを理解しようと試みることは、プログラム(3)全体を通して 2 N [3-8] の異なる経路決定を区別しなければならないことを暗示する。そして、理論上 N*2 N [3-9] の手順をもたらすのだ! [3-10]

[3-8] 原文は 2N となっているが、2 N の誤植であろう。
[3-9] 原文は N*2N となっているが、N*2 N の誤植であろう。

[3-10]
前述のようにダイクストラ博士はプログラム(3)をプログラム(1)に抽象化するときに理解する手順は 3N で済むとしている。それが正しいならば、抽象化文の導入によって理解する手順が N*2 N から 3N へ大幅に短縮できることになる。
しかし、 この理論は極論である。 この理論は、1つの if 文を1つの抽象化文 S i に変換することによって、複数の抽象化文が相互作用しないことが前提になっている。しかし、現実には、複数の抽象化文が相互作用することもあるはずである。その場合、抽象化に必要な理解の手順は 3N より多くなる。ただし、複数の抽象化文がほとんど相互作用しないこともありえるので、プログラム全体で見ると理解の手順が N*2 N より少なくなる。つまり、抽象化文の導入による理解の手順は

3N < 抽象化文の導入による理解の手順 < N*2 N

となるのであるが、ダイクストラ博士は最も有利な 3N だけを強調している。
あくまでも「説明のために単純化された例」ということかもしれないが、実際のプログラムの抽象化はこのような一行毎にできる単純なものではないことが多い。実際は抽象化する前のプログラムを分析し、その中から1つの意味のあるまとまりになる複数の文を括り出してからそれを1つの抽象化文にしないといけない。
とは言え、抽象化文を導入することによって導入前よりは理解の手順が減り、変更・改良・保守も容易になることは間違いない。 この例は極論ではあるが、抽象化文が重要であることは間違いないのである。

私は以上の計算が抽象化文 S i の導入の必要性を説得力をもって実証していると信じている。 私の構成手法のある1つの特徴は、与えられたプログラム(3)を抽象化プログラム(1)へ縮小することではなく、抽象化プログラム(1)から始めることである [3-11]。

[3-11] 段階的抽象化の反語である 「段階的詳細化」 のことである。プログラムの設計は抽象的なものから始めて段階的に詳細化していくということである。

抽象化データ構造

もしもプログラムを構成する文の正味の影響の定義が十分扱い難い [4-1] ものであれば、適当な数の抽象化文から構成されているプログラムを再び理解することは、莫大な作業になる。 このことは適切な 抽象化データ構造 の導入によって克服することができる。 その状況は、使用されている実装上の数値表現について考えずに整数における ALGOL プログラムの動作を理解することができる [4-2] ことと非常に類似している。 唯一の違いは、プログラマーが自分自身で概念(「既製」の整数と類似)とその概念上の動作(「既製」の数値演算と類似)を考案することである。

[4-1] 文の実行によって出力されるデータが複雑で扱い難いということ。
[4-2] ALGOL のような高級言語の場合、整数変数の内部構造を知らなくても整数変数を扱えるということ。

抽象化プログラム(すなわち、 抽象化データ構造上で動作する抽象化文 から構成されている)の詳細化において、我々は 「共同詳細化」 という現象を観察することになる。 定められた型の抽象化データ構造に対して信頼できる表現は、新しいデータ構造(おそらく未だにかなり抽象的ではあるが)を使って決められる [4-3]。 この設計決定の直接の結論は、「新しいデータ構造が独自の抽象化データ構造を表現するために決定されたという観点から、独自の抽象化データ上で動作する抽象化文は、新しいデータ構造上で機能するアルゴリズム詳細化を使って再定義されなければならない」ということである [4-4]。 そのようなデータ構造と関連する文との共同詳細化 [4-5] は、プログラムテキストの分離した1単位であるべきである。それは(自立した)設計決定の直接の結論を具体化したものであり、それ自体がプログラム変更のために交換できる自然な一単位である。 それは私が「真珠」と呼ぶまでに育てたものの一例である。

[4-3] 「抽象化データ構造」は、その名の通り抽象的なものであり、「新しいデータ構造」はより具体的なものである。
[4-4] 新しいデータ構造は抽象化データ構造を詳細化したものである。そのため、抽象化データ構造上で動作する抽象化文も詳細化する必要があるということ。「共同詳細化」という言葉はここから来ている。
[4-5]
「データ構造と関連する文との共同詳細化」( 抽象化データ構造 抽象化データ構造上で動作する抽象化文 との共同詳細化)は、今で言うオブジェクト指向のクラスに近い考えだった。クラスはメンバでデータを定義し、メソッドでデータを扱う動作を定義するからである。つまり、「メンバ ≒ 抽象化データ構造」「メソッド ≒ 抽象化データ構造上で動作する抽象化文」ということである。
当時(1969年)はシミュレーション言語 SIMULA 67 がすでにあったので、クラスの概念はあったが、SIMULA 独自の概念として扱われていた。オブジェクト指向の概念はまだ存在しなかった。

真珠をつなげたネックレスとしてのプログラム

私は真珠の整然とした集合である「ネックレス」[5-1] としてプログラムをみなすまでに成長した。 最も上にある真珠は最も抽象的な形式でプログラムを記述する。それより下の全ての真珠において、それらの真珠の上で使われた1つ以上の概念は、それより下の真珠で説明される(詳細化される)という概念を使って説明される(詳細化される)。 一方、最も下にある真珠はついに標準インターフェース(=機械)[5-2] を使って説明されなければならないことを説明している。 その真珠は自然な単位のプログラムモジュールであるように見える。

[5-1] ここで言うネックレスは、円形に繋がったものではない。ネックレスの結合部を外して真下に垂らしたものである。それによって階層化を説明している。
[5-2] ここで言う標準インターフェースはハードウェアとソフトウェアの間のインターフェースのことである。現代において、標準インターフェースと言えば、周辺機器のインターフェースのことになってしまうことが多い。

それぞれの真珠は特定の設計決定(または、場合によっては、元の課題の特定の一面)を具体化しているので、それはプログラムの変更(または、場合によっては、課題の変更に対するプログラムの適応)において交換できる自然な単位である。

真珠とネックレスは、ネックレスの上半分から構成される「不完全なプログラム」に明確な状態を与える。 適切な機械 [5-3] (ネックレスの下半分が適切な機械の実行可能な実装を提供する)によって実行されることは、完全なプログラムと見なすことができる。 そのようなものとして、ネックレスの上半分の正しさは、下半分の選択に関わらずに確立されることができる。

[5-3] ここで言う「適切な機械」(suitable machine)とは、「ハードウェア+OS」のことと思われる。今でも IBM PC/AT互換機+Windows OS のことを「Windowsマシン」と称することと一緒。OS もプログラムなので、真珠のネックレスの下半分ということになっているのだろう。

2つの繋がった真珠の間を切って切口を作ることができる。その切口は、切口より下のネックレスの部分によって提供される機械の説明書 [5-4] であり、切口よりも上のネックレスの部分によって表現されるプログラムによって使用される。 この説明書はネックレスの2つの部分の間のインターフェースとして役立つ。 この形式のインターフェースは命令と命令の間のインターフェースとしてのデータの表現 [5-5] を考えるよりも役立つと思われる。 特にプログラムの適応のために要求される組合せの自由を確保するためにさらに役に立つ。

[5-4] この文章において、機械=「ハードウェア+OS」なので、実際には OS の API の説明書と思われる。
[5-5]
「命令と命令の間のインターフェースとしてデータの表現」(data representation as an interface between operations)とは、グローバル変数のことと思われる。昔はローカル変数や関数がない言語(アセンブリ言語、FORTRAN 66 など)が多かったため、引数の受渡しをグローバル変数で行うことが多かった。つまり、グローバル変数がインターフェースであった。グローバル変数を使ったインターフェースはプログラムを複雑化してしまうので、ダイクストラ博士は「切口」に例えたインターフェースを推奨しているのである。「切口」は今で言うところの関数呼出やメソッドコールに相当するものであろう。当時の言語でも ALGOL と SIMULA は「切口」が使えた。

今述べた組合せの自由は、関わっている労働者をソフトウェア集団のメンバーの数に比例して増やさずにソフトウェア集団の一部としての一つのプログラム、あるいは「多くの(潜在的な)バージョンの中の」一つのプログラムを作成することができる唯一の方法に思える。 そのソフトウェア集団は、ヒモを通してネックレスにすることができる真珠のコレクションの中から選んだ真珠で作ったネックレスの集合になる [5-6]。

[5-6] 階層構造のおかげで階層を組み合わせることによって様々なプログラムを作れることを真珠のネックレスに例えている。

最後に

ネックレスの中の真珠は、「最上部から底辺まで」と言う厳密な論理的順序を持つ。 この順序は、それらが設計された(時間的)順序とは根本的に異なるかもしれないことを強調させていただきたい。

関連するプログラムのある分類の大量のメンバーをできるだけ完全に相互に対応付けしようとしたとき [6-1] 、真珠がプログラムのモジュールとしての存在であることが明らかになってきた。 この対応付けに関わる抽象化作業 [6-2] は、正しさの証明に従事する知的労働者の数を減らすために使われること [6-3] と同じことであることが判明する [6-4](結果論としては驚くべきことではない!)。 このことはとても励みになる。

[6-1] 原文は "when I tried to map upon each other as completely as possible, the numerous members of a class of related programs" であり、特に "map upon each other" の意味が良くわからないので、このように訳した。おそらくは、プログラム同士を比較・対応付けているときに階層的なプログラムのモジュール(真珠)を思いついたということだろう。
[6-2] 原文は "The abstraction process involved in this mapping" である。「プログラムを真珠として抽象化する作業」のことと思われる。
[6-3] 前節の「(真珠の)組合せの自由」のことと思われる。
[6-4] 前節の「(真珠の)組合せの自由」の場合、事前に真珠を作ってから設計を行う。一方、この節では、すでに存在するプログラムを真珠に抽象化するらしいので、設計手順は逆になる。しかし、結果的に同じことになるということだろう。

私が以前言ったように、プログラミングの実験は相対的に小さなプログラムで実行されてきた。 私的には、そのプログラミングの実験が本当に大きなプログラムのより信頼性の高い構成を実現する方法を見せてくれると固く信じている。 けれども、私は未だに「本当に大きなプログラム」についての実験的証拠を持っていないことを強調したい。 今までに得た実験的証拠は、私が試した大きさのプログラムに限れば、プログラムを構成する能力が増大することを示している。 私はそれを試みたのであるが、誰かが大人数の雇用を望むときに必要とされるようなプログラム開発の必要条件をほとんど認識していないと感じている。 私は中国陸軍式の手法 [6-5] の経験がないし、その長所についても確信していない。

[6-5] 中国陸軍式の手法=人海戦術
▲このページの先頭へ
▲このページの先頭へ

[表紙へ]