ダイクストラの構造化プログラミングとは

ダイクストラの構造化プログラミングとは

「Structured Programming」という言葉を作ったのは計算機科学者エドガー...ダイクストラであり、1969 年の NATO ソフトウェア工学会議で発表された論文が初出とされている。彼は 2001 年のノートで自分が作り出した「構造化プログラミング」という用語は結局異なる解釈で持ち去られてしまったと述べている。

ダイクストラが提唱した構造化プログラミングは、プログラム正当性検証技術の確立を原点にして構想された数々のプログラム開発理論の複合体である。遅くとも 1967 年からその構想は始められていた。1968 年の goto 文に依存しないシーケンスの制御、1969 年のトップダウン設計、抽象化、モジュール化、共同詳細化から始まり、1972 年には抽象データ構造、情報隠蔽、階層的プログラム構造といった考えも取り上げられていた。1972 年の共著は、ダイクストラの第一章・構造化プログラミングから始まり、オルヨハン・ダールの第三章・階層的プログラム構造で締め括られている。ダールはオブジェクト指向プログラミング言語の草創 Simula67 の開発者である。

1969 年の論文「構造化プログラミング」

1969 年度 NATO ソフトウェア工学会議に寄稿されたこの「Structured Programming」は、プログラム正当性の効率的な検証技術に重点を置き、当時問題視されていたコードサイズの際限なき肥大化によるソフトウェア危機の解決策として従来のボトムアップ設計からトップダウン設計への移行を推奨していた。

論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（program correctness）の立証（demonstration）に必要な労力が指数的に増加して完遂が不可能になるというソフトウェア危機の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。

後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if 文 1 つだけも推論しやすいとしている。しかし、if 文が N 個並んだ場合、そのままでは 2 の N 乗ステップの推論が必要であるとしている。そこで if 文を抽象ステートメントで 1 つずつ置き換える段階的抽象化（step-wise abstraction）により、N に比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（なお、順次、選択、反復のいわゆる制御構造（control structures）に触れているのはこの文節だけである）。この例のように詳細なプログラムを抽象化（abstraction）していくのではなく、逆に抽象的なプログラムから始めて詳細化（refinement）していくというやり方を示している。

共同詳細化（joint-refinement）の概念:
これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを 1 つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が 1 段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。 そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションの労力をかけずに作れるとした。

1972 年の共著「構造化プログラミング」

1972 年の共著「Structured Programming」は計算機科学界の錚々たる三名による三章構成で、第一章はエドガー・ダイクストラの「structured programming」、第二章はアントニー・ホーアの「data structuring」、第三章はオルヨハン・ダールの「hierarchical program structures」となっていた。結びの章の「階層的プログラム構造」を著したダールは Simula67 の開発者である。Simula67 はオブジェクト指向プログラミングの草分けであり、この章名から継承によるクラス階層構造を重視していたことがうかがえる。ダイクストラの構造化プログラミングは、制御構文と構造化定理と構造化設計の影に隠れながらも、Simula67 をモデルにしたオブジェクト指向プログラミング発展の歴史に組み込まれて受け継がれていったと言える。

1983 年に C++を開発したビャーネ・ストロヴストルップは「What Is Object-Oriented Programming?」において、オブジェクト指向を抽象データ構造と階層的プログラム構造の発展形として解説し、同時に Simula67 の言語仕様を紹介している。

ダイクストラ提唱の構造化プログラミングを支持するドナルド・クヌースは、1974 年に自著「Structured Programming with go to Statements」を発表し、その中で goto-less の本質に関する補足と解説を加えている。これは当時の goto 文論争に一つの区切りを付けるものであったが、幅広い認知を得るには到らずに goto 文論争は 1980 年代になっても散発的に繰り広げられた。1970 年代後半からマイコンが普及して BASIC などを扱うパーソナルユーザーが増えると、goto 命令を使わないのが構造化プログラミングといった見解が取り上げられて再び議論が始まるなど、この論争の影響は後年まで根強く残っている。

プログラム正当性検証のための構造化（1967 年のノート）

ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（検証）することも仕事の一つであるという立場を取っていた。プログラムがどんなに巨大化しても良く構造化（well-structured）されていれば、サイズに関係なくその正当性を検証できるというのが彼の信念であった。well-formed formula（論理式）に因んでいる well-structured には、数理論理学の証明論をソースコードにも導入する意図が込められていた。1967 年のノート「Towards Correct Programs」でダイクストラは、良く構造化するための三つのメンタルツール（mental tool）をこのように示している。

• 列挙（enumeration）： 一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業
• 数学的帰納（mathematical induction）： while 文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業
• 抽象（abstraction）： プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作

プログラムが正しいことを確認するには、それを証明しなければならない。テストはプログラムに対する疑いを全て取り除くには不十分であるという意見が上がった。これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた。構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた。理想的にはテストだけに依存せず、プログラムの正しさの証明も与えるべきだと言われている。所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている。ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした。

ダイクストラの後述

ダイクストラは 2001 年のノート「What led to “Notes on Structured Programming”」(構造化プログラミング表記の由来）でこのように述べている。

1968 年の自分は「A case against goto statement」(goto 文への訴え）と題した記事（article）を Communications of the ACM（ACM の機関紙）に投稿したが、当期の刊行を急群編集担当者の意向で投書（letter to the Editor）にされる事になり、更にその担当者独自の考えで「The goto statement considered harmful」(goto 文は有害)という全く新しい題名を付けられた。その担当者とはニクラウス・ヴィルトであった。

また、自分が提唱した構造化プログラミングの本質的内容の普及を好まない某社がハーラン・ミルズの主導で、まるで goto 文を廃止するかのようなプログラミング手法へと矮小化し、構造化プログラミングという用語まで持ち去ってしまった。

私の理解

私の理解は単純明快、例えば、給与明細書作成システムの場合

図―１ システムの構造モデル

インプット
勤務データ

プロセス
給与明細書作成

アウトプット
給与明細書

インプット、プロセス、アウトプットについて順次ブレイクダウンして詳細化していくこと