データ構造化理論におけるダイクストラ選択
構造化プログラミングの72年書籍版は三部構成
前回
ダイクストラの構造化プログラミングの書籍版は三部構成 - 構造化プログラミングの覚え書きその2 - dhrnameのブログ
1972年に出版された構造化プログラミングは以下のように三部構成である。
今回はこの中で、第二部のデータ構造化序論を取りあげる。制御構造であるダイクストラ選択の型選択演算子(セレクタ, selecter)について見ていこう。なお、この記事は私個人による独自解釈である。
ダイクストラ構造化原理
ダイクストラによれば、データ型の型付けと抽象化 (abstraction) は等価である。また、3パターンの制御構造を使って抽象化が可能となる。これをプログラミングの構造化原理と呼ぶ。
ホーアによれば、抽象化は次の四段階を経る。
- 抽象（抽出のこと)
- 表現
- 操作 (変換のこと)
- 公理化
この記事では主に3段階目の操作について着目する。
データ型の変換
あるデータ型から別のデータ型へ変換する演算子には、次の二つの方式がある。
構成演算子は複数のデータ型から一つのデータ型にまとめることができる。例えば、構造化された型の場合、
<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である。
- xm∈y (ただし、0 < m<= n)ならば、d.xm = 1
- 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について、
- X ⋂ Y = ∅
- 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については、次の条件を満たす。
- Xi ⋂ Xj = ∅ , i ≠ j
- X1 ⋃ X2 ⋃ ... ⋃ Xn = Y
case文の利用方法は二つの集合による直和型と同様である。
参考資料
次回
*1:原文ではwith構文を使っている
