フロー・ダイアグラムの束 − Dana Scottの論文紹介

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2013年 作成　舟越　和己

　ここでは、束と完備束がソフトウェアの世界でどのように構成されるかについての具体的イメージを把握するため、少し長くなるが１つの例としてフロー・ダイアグラムを取り上げる。この内容はDana Scottの下記の論文の概要紹介である；

　　Dana Scott: The lattice of flow diagrams（フロー・ダイアグラムの束） (1970)

１．フロー・ダイアグラムの表現

　直感的に、フロー・ダイアグラムは非常にラフに描けば下の図１のようになる。

　　　　

　　ここには、入力情報が流れる入口点と、出力が出ていく出口点がある。

　このとき図の”ブラックボックス”の中はどうなるかという疑問がある。

　　・このボックスの中はこれ以上分解できない原子演算を表しているかもしれないし、他のダイアグラム

　　 との合成であるかもしれない。

次に、このボックスの中のタイプを以降の図２から見ていく。

�@最も単純な例は如何なるダイアグラムとの組合せもないものである。これは下の図２の”矢印”である。

　　　　

　このような矢印のみに流れる情報は全く変換されない； したがって、これを恒等関数(identity function)で表す。

�A自明でない合成例の一つは下の図３に示されている。これは、積(product)と呼ばれ、この組合せに

　おいて、最初のボックスの出力は２番目のボックスの入力を与えている。

　　　　

�Bダイアグラムにおいて、スイッチは下の図４のように表現される。

　　　　

�Cスイッチの各矢印にボックスが付けられ、それらのボックスの出力が一緒になるとき（下の図５）、これを（２つのボックスの）和(sum)と呼ぶ

　　　　

　以上の説明の中で、和と積はフローダイアグラムの基本的な合成演算である。すなわち、これらの組合せで大きなダイアグラムが作られる。

ところで、これまでループの話が出てきていないが、ループは後で登場することになる（この理由は後で明確になる。これは完備性と密接に関係している）。

　ここで、フローダイアグラムを代数的に表現するために、いくつかの表記を説明する；

　 ・スイッチはb₀, b₁, b₂,・・・,

　 ・ボックスはf₀, f₁, f₂,・・・,

　 ・ダイアグラムはd₀, d₁, d₂,・・・

　ここで、b: Boolean又はbinary、f: functions、d: diagramsを意味する。ボックスは情報上の関数を表すので"f"が使用される。ダイアグラムはスイッチ、ボックスを合成したものである。

また、恒等ダイアグラムは Iで表す。

　これらの表記を使用してダイアグラムの和、積を表現すると次のようになる；

dとd'が２つのダイアグラムのとき、その積は

　　　　　　　　　　　(d ; d')

　で表す（図３参照）。この場合、表示の順序は図３のように「左−右」の順となる。

　また、和は下記で表す（図５参照）。

　　　　　　　　　　　(b_j→d, d')

この表記ルールにより、図６のダイアグラムは下記で表される；

　(b₀→ (f₀ ; (f₁ ; (b₁→ f₃, f₄))), (f₂ ; (b₂→ f₄, f₅)))

　　　　

　次の小節では、ダイアグラムの代わりに和や積の演算の適用を繰り返すことにより、f_iとb_jから生成される式について議論する。

２．フロー・ダイアグラムの束の構築

　まず初めに、２つのダイアグラムd,d'間の半順序関係⊆を次のように定義する；

　　　・d'がdの属性（注）を全て含むとき、d⊆ d'であるとする。

　　　　（注）dのエレメント及びd内の関係

　また、２つのダイアグラムd,d'間に d⊆ d'の関係があるとき、dはd'を近似するという。あるいは、

dはd'の不完全な部分(incomplete parts)とも言う。

　極端な場合として、全てのダイアグラムの近似となる最も粗いダイアグラムとして⊥（ボトム）がある。ダイアグラムでは、⊥（ボトム）はその内容が未定の”空”のボックスである。この”空”のボックスは図７に示すようにダイアグラムの一部として表現されることがある。図７の表現は下記のようになる；

　　　　　　　　(b₀→ (f₀ ;⊥), (f₁ ; (b₁→ f₂, I )))

　　　　

　　この小節の目的は、”原子”シンボルから出発しフロー・ダイアグラムを束の構造として組み立てていくことである。ここで、”原子”シンボル（フロー・ダイアグラムにおいてこれ以上分解できないシンボル）とは、

　　　　　⊥, f₀, f₁,・・・・, f_n,・・・, I,Τ　

であり、これらを出発点にして、フロー・ダイアグラムの積と和

　　　　　　　　(d ; d')、(b_j→d, d')

及び、

　　　　　　　束論の（⊆,∪,∩）

を使用して全ての組合せを構成していくことである。これを以下、順を追って説明する。

（１）原子シンボルの束

　束の最初の部分は、原子シンボル f₀, f₁,・・・・, f_n,・・・及び Iに対応する。i≠jならばf_iとf_jは異なるので原子シンボル f₀, f₁,・・・・, f_n,・・・は下の図８のように束の各要素として表現すればよい。

この束の図において半順序は上昇するラインにより表現されている；

　　　　

　　　　　　図８　原子シンボルの束

　この場合、より弱い（小さい）エレメントは下で、より強い（大きい）エレメントは上である。

（２）２つの束の和

　データ・フローの束を構築する上でお互いに交わらないエレメントを持つ２つの束の和を考える。

すなわち、D, D'を半順序⊆,⊆'を持つ束とし、DとD'を一緒にして統合された束D+D'を作りたい。

これは、２つの半順序関係の”和(union)"により組立てられた２つの集合の和(union)に過ぎない。しかし、この和には最大元も最小元がないので束ではない。

　そこで、Τ ,Τ'と⊥,⊥'を各々DとD'の最大元と最小元とするとき、各々の最大元と最小元は等しい（すなわち、Τ =Τ',⊥ =⊥'）とすることによりD+D'は束となる。束の和を形成するこのプロセスは図１３に描かれている。

　　　　

（３）フロー・ダイアグラムの最初の束

　原子シンボル f₀, f₁,・・・・, f_n,・・・及び Iに対応するフロー・ダイアグラムの最初の束は、束の和を使用して

　　　　　　　　　　　　　　D₀ = F + { I }

と表現される。Fのエレメントはf₀, f₁,・・・・, f_n,・・・であるが、各エレメントf_iを束{ I }と同型な束{ f_i }と考えると、

　　　　　　　　　　　F={ f₀ }+{ f₁ }+・・・+{ f_n}・・・

　と表現できる。従って、D₀ = F + { I }のエレメントは、下記となる；

　　　　

（４）ダイアグラムの積と和

　　DとD'はそのエレメントが”ダイアグラム”を表す束とする。ダイアグラムの積を考えるとき、積の半順序と呼ばれるD*D'上の半順序が下記のように定義される；

　　　　任意のd₀, d₁∈ Dとd'₀, d'₁∈ D'に対して、

　　　　(d₀ ; d'₀)⊆ (d₁ ; d'₁)　⇔　d₀⊆ d₁かつd'₀⊆ d'₁

　ここで、積(d₀ ; d'₀)の表記に代わりに抽象的に順序付けられた組の表記として<d₀ ; d'₀>を使用する。したがって、DとD'の積は

　　　　　　　　　　D*D'={<d ; d'> | d∈ D, d'∈ D' }

　となる。D*D'の最大と最小のエレメントは<Τ ;Τ'>と<⊥ ;⊥'>。

一方、ダイアグラムの和(b_j→d, d')は下記の束のエレメントである；

　　　　　　　　　B*D*D' = {<b_j, d, d'> | b_j∈B, d∈D, d'∈D' }

（５）積と和から作るフロー・ダイアグラムの束

　次に、D₀ = F + { I }からダイアグラムの積と和を使用して次の段階のダイアグラムD₁を下記のように構成する；

　　　　　　　　　D₁= D₀ + (D₀* D₀) + (B*D₀*D₀)

　これのエレメントは下記のようになる；

　　　　

　明らかに、D₁は非常に短いダイアグラムしかエレメントに含んでいない。より大きなダイアグラムを得るためには、式の合成を進めなければならない。

これはさらに複雑な束を下記の漸化式で構成していく；

　　　　　　　　　　D_n+1= D₀ + (D_n* D_n) + (B*D_n*D_n)

このとき、{ D_n }は単調増加である。

　上記のようにして構成されたダイアグラム{ D_n }の全体は、半順序関係（⊆）に関して束を構成する。このイメージを次に図示する。

　　　　

　この図は、ボトム（⊥）から出発して単純なダイアグラムの集合D₀からD₁、D₂とフロー・ダイアグラムの束の階層が構築され複雑なフロー・ダイアグラムが出来ていくことを表現している。

　各階層間のエレメントに半順序の関係（⊆）がある。これを見ると分かるように、D₁のエレメントのネストの深さは1,　D₂のエレメントのネストの深さは2である。同様に、束D_nのエレメントのネストの深さは高々nとなる。

　ここで、上位の階層のエレメントはすぐ下の階層のエレメントの積と和から生成される；（下記は積と和の例）

　　　　

これらの考察の結果として、{ D_n }の和集合

　　　　　　　　　　　　　∪D_n　（n=0から∞）

を考えると、これは束であるが完備束ではない。この和集合のエレメントは２つのモード（積と和）により原子ダイアグラムから生成される有限（注）の全ての組合せである。

　　(注）∪D_nの任意の要素をdとすると、d∈D_n0となる有限のn0∈Nが存在する。

　　　　　すなわち、∪D_n要素は有限の積と和の組合せである。

ここで、無限ループなどの有限でない処理はどのようにして構成すればよいか、という問題が生じる。

これに対しては、次のように有理数を完備化して実数が構成された手法のアナロジーで構成される。

　有理数の世界：Q　　　　　　　⇔　　有限の積と和の組合せから構成されるダイアグラムの世界：∪D_n

　　↓（コーシー）完備化　　　 　　　　　　　　　　↓（束の）完備化　

　実数の世界：R　　 　　　　　⇔　　無限ループなどの有限でない処理を含むダイアグラムの世界：D_∞

　∪D_nの完備化を行なう前に、準備として次に「有理数の完備化」を簡単に説明する。

３．有理数の完備化

　たとえば、A={x | 0≦x, x2≦2}という集合を考える。これはすべての要素が、x≦2を満たすので有界（上界）である。しかし、有理数のなかでは、この上界は最小元を持たない。一方、これが実数の中でなら、上界は（２の平方根という）最小元を持ち、これが集合の上限となる。 この違いを完備(completeness)という。

　きちんと定義するなら次のようになる。

（１）完備とは？

　集合Aのすべての部分集合が、上に有界ならば上限を持ち、下に有界ならば下限をもつとき、集合Aは完備あるいは順序完備（注）であるという。 　（注）条件を緩めて半順序でもよい。

　（例）実数の閉区間 [0, 1]は≦の順序の下で完備であるが、半開区間 [0, 1)は完備ではない。

　　　　理由：１に収束する[0, 1)内の任意の無限列が上限を持たないため。

（２）完備化とは？

　・完備でない集合を完備な集合にすることを完備化という。

（３）完備化の方法

　実は完備化の方法は一つではない。以下ではその一つであるコーシー完備化を説明するが、デデキントの切断による完備化などほかにも完備化の方法はある。

（注）Augustin Louis Cauchy(1789年- 1857年）は、フランスの数学者。他に天文学、光学、流体力学などへの貢献も多い。

　　　　

（４）コーシー列

　収束する数列は、どんどん差が縮まっていく性質を持っている。　これはε-δ論法で厳密に書くことができるが、ここではそういう数列をコーシー列ということだけ覚えておく。

　有理数から無理数へつなげていくためには、何か無限に関わる操作をしなければならない。なぜならば、有限回の操作を行ったのでは、それはまた有理数になってしまうからである。

　そこで、有理数に対する操作の繰り返しとして数列を考える。

例えば、下記の数列{a_n}を考える；

　　　　　　　　a₁=2, a_n+1=(a_n²+2)/(2*a_n)　　・・・（１）

これをいくつか計算してみると、

　　　　　a₂=(2²+2)/(2*2)=6/4=3/2

　　　　　　a₃=((3/2)²+2)/(2*(3/2))=17/12

　　　　　　a₄=((17/12)²+2)/(2*(17/12)0=577/408

これは、２から始まって加減乗除だけで計算しているので、どの項も有理数のままである。 また、この数列は、どんどん差が縮まっていく性質を持っているのでコーシー列となる。

この数列は収束する値があるとすれば、その値αは

　　　　　　　 a_n+1= a_n=α　　　

を満たすような数になる。この場合、上記(1)式はα=(α²+2)/(2*α)となり、α²=2からα=2の平方根（無理数）となる。

以上のように有理数の列があったとき、それがコーシー列になっていて極限をもっていたとしても、その極限がまた有理数の範囲に収まるとは限らない。つまり、完備ではない。

　そこで、有理数のコーシー列の極限値を全て有理数に付け加えれば、その集合はコーシー完備になる。これが実数である。（注）

　（注）同じ実数に収束するような異なる有理数列が存在するので、それらを1対1に対応させるために、

　　　　厳密にはコーシー列そのものに同値関係を導入し、それの商集合として実数を定義する。）

こうして、有理数から実数を作ることができる。一般にコーシー列がその集合の中で収束するように拡大することを「（コーシー）完備化」という。

　フロー・ダイアグラムの束の完備化も上記と同様に、束の単調増大するエレメントのコーシー列に相当するものを束に付加することで行なう。

４．フロー・ダイアグラムの束の完備化

　簡単な例でループのダイアグラムを考える；

下記の一次方程式を漸化式で解くと、

　　　　　　X＝X/2 + 1　・・・・�@�@

まず、�@を漸化式で表現する；

　　　　　　　X_n+1=X_n/2 + 1・・・�A�A

�AをX₀=0から出発して順次値を求めていくと、

　　　X₁=X₀/2+1=1　　　X₂=X₁/2+1=1/2+1=3/2=1.5

　　　X₃=X₂/2+1=3/4+1=7/4=1.75 X4=X3/2+1=7/8+1=15/8=1.875

　　　・・・→　X_∞=2

これをフロー・ダイアグラムで表現すると、下記のようなループ処理になる。

　　　　

このループ処理を展開して表現すると、下記のようになる。

　　　　

上記から、単調増大して収束するダイアグラムのシーケンス{d_n}が得られる；

　　d₀⊆d₁⊆d₂⊆・・・⊆d_n⊆・・・→ d

したがって上記ループ処理は {d_n}の極限dとなる。

ここまでの議論から、　

　　・有理数のコーシー列の極限としての実数と、

　　・単調増大する積と和のダイアグラム列の極限としての無限ループ処理

には完備性という視点から類似性があることが分かった。

　　　　

　以上から、積と和から構成されるダイアグラムの束∪D_nに対して、∪D_nに属するダイアグラムの収束列{d_n}の極限を全て追加することにより、∪D_nの完備化D_∞が実現できる。

　これは、有理数のコーシー列から実数を定義することと同様な手法である。

　次にフロー・ダイアグラムの完備化について見ていく。

５．近似写像ψ

　フロー・ダイアグラムの束において、単調増大するエレメントのコーシー列に相当するものを作るために、「ダイアグラムの近似列と近似写像ψ」を考える。

　・束D_nのエレメントは高々nの”深さ”のダイアグラムである。

　　より正確には、それらは高々nレベルの２つのモード（積と和）の合成のネストにより生成することから

　　得られる。これはD_n+1のエレメントがD_nのエレメントにより近似されるということを示唆している。

　・今、D₀とD₁を考える。　D₁の要素をdとするとき、D₀⊆ D₁なのでd∈D₀またはd∈(D₁- D₀)。　

　　したがって、

　　　(i) d∈D₀ならば、これはD₁の要素d自身なのでベスト近似となる：ψ₀ (d) = d

　　　(ii) d∈(D₁ - D₀)ならば、dはD₀のエレメントでは合成できないので、dのD₀での近似は

　　　　　⊥しかない。

言い換えると、d∈D₁に対してD₀のエレメントによるdのベスト

　 近似ψ₀ (d)を対応させる写像

　　　　　　　　　　　　　　　　　　　　ψ₀ : D₁→D₀　

　　を定義することができた； ここで、d∈D₁に対して、

　　　　

が成立する。

次にD_n+2とD_n+1を考え、

　 d∈D_n+2に対してD_n+1のエレメントによるdのベスト近似ψ_n+1(d)を対応させる写像

　　　　　　　　　　　　ψ_n+1: D_n+2→D_n+1

を定義したい。

D_n+2とD_n+1については、下記が成り立つことを思い出して欲しい；

　　　　　　　D_n+2= D₀ + (D_n+1* D_n+1) + (B*D_n+1*D_n+1)

したがって、ψ_n+1とψ_nの間には次の関係が成立する（これは束の構成図からも自明）；

　　　　

この写像を図示すると下記のようになる；

　　　　

　写像ψ_n: D_n+1→D_nは容易に図示できる。図１４に２つのダイアグラムが与えられている：

最初のダイアグラムはD₃に属し、二番目のダイアグラムは最初のダイアグラムにψ₂を適用した結果である。図１４の下のダイアグラムには少し曖昧な部分がある（⊥の部分）； この曖昧さはダイアグラムに対して式を選んだときに取り除かれる。

　　　　

■参考に、D_n+1からD_nへの近似写像ψ_nを有理数列で考えてみる；

　　 　　a₁=2, a_n+1=(a_n²+2)/(2*a_n)　　これをいくつか計算してみると、

　　　　　a₂=(2²+2)/(2*2)=6/4=3/2　　a₃=((3/2)²+2)/2*(3/2)=17/12

　　　　　　a₄=((17/12)²+2)/2*(17/12)=577/408　・・・・

　　a_nに対し、写像ψ_n(a_n+1)=a_n　が定義される。

　　　（例）ψ₁(a₂)=a₁⇔ψ₁(3/2)=2　ψ₂(a₃)=a₂⇔ψ₂(17/12)=3/2

　　　　　　　ψ₃(a₄)=a₃⇔ψ₃(577/408)=17/1

６．有向集合と極限

（１）有向集合

　部分集合X⊆Dは、Xの全ての有限部分集合Xが（⊆に関して）Xに属する上限を持つとき、有向(directed)であると言われる。これを任意のペアx, y∈Xに適用すると、x∪y⊆zとなるz∈Xが存在しなければならないことを意味する。有向集合の明らかな例はω鎖(ω-Chain)である；

　　　　　　　 x₀⊆ x₁⊆・・・・⊆ x_n⊆・・・

すなわち、単調増大する列である。

（２）有向集合の極限

　有向集合の極限は、∪Xである。

　ω鎖の場合、極限（結合）を下記で表す；

　　　　　　　　∪x_n　（n=0から∞）　　

　　　　

７．フロー・ダイアグラムの完備化

　以上の準備をして{ D_n }の和集合∪D_n（n=0から∞）を考える。

これは束であるが、∪D_nのエレメントから成る有向集合（注）の極限（コーシー列に相当）を考えることにより、この完備化D_∞を求める。

　　（注）これはω鎖で考えて良い。

　(A) D_∞が ∪D_n（n=0から∞）の完備化であると仮定すると、「任意のd∈D_∞に対してψ_n(d_n+1)=d_nを

　　　満たす有向集合（注）d₀⊆d₁⊆d₂・・d_n⊆d_n+1・・が存在し、d=∪d_n（n=0から∞）となる。」

　　（注）これはω鎖で考えて良い。

　(B)逆に、ψ_n(d_n+1)=d_nを満たす有向集合d₀⊆d₁⊆d₂・・d_n⊆d_n+1・・　(d_n∈D_n)が存在するならば、

　　　d=∪d_n（n=0から∞）はD_∞のエレメントとなる。

　　　したがって、dが∪D_nの完備化D_∞のエレメントになることと、　

　　　ψ_n(d_n+1)=d_nを満たす有向集合(注) d₀⊆d₁⊆d₂・・d_n⊆d_n+1・・　(d_n∈D_n)が存在し、d=∪dn

　　　（n=0から∞）となることは同値である。

■参考に、D_∞からD_nへの近似写像ψ_∞nを実数と有理数の関係

　 で考えてみる；

　　　　a₁=2, a_n+1=(a_n²+2)/(2*a_n)　　　　これをいくつか計算してみると、

　　　　a₂=(2²+2)/(2*2)=6/4=3/2　　a₃=((3/2)²+2)/2*(3/2)=17/12

　　　　a₄=((17/12)²+2)/2*(17/12)=577/408　

　　　　　・・・・

　　　　　a_∞ = 2の平方根（実数）

　　a_∞ に対し、写像

　　　　　　　　　ψ_∞n(a_∞)=a_n　

　　が定義される。すなわち、{ψ_∞n(a_∞)}という有理数から成るコーシー列が作られる；

　　ψ_∞1(a_∞)≦ψ_∞2(a_∞)≦・・・・ψ_∞n(a_∞)≦・・・・→ a_∞ = 2の平方根（実数）

８．ループと他の無限ダイアグラム

（１）ループのダイアグラム例

　　図１７は循環のフロー、いわゆるwhile-loopを持つフロー・ダイアグラムの最も良く知られた構成である。これはプログラミング言語　の非常に基本的な概念を表現している。直感的に、図１７の表記は最も単純なものの一つである。一方、図１８のような無限の分岐の繰り返しも循環の例である。

　　　　

　　　　

（２）ループのダイアグラムの関数表現

　図１７のループ処理は、情報が入力され(b₀により）検査される。　ここで、もし検査により正ならば、情報は(f₀により）変換され、ループによる再帰により再び検査に戻される。検査が正の間は再帰が続くことになる。やがて繰り返された変換の累積結果は負の検査結果を生じる。

　以上のことは、いくつかのシンボルを使うと分かり易くなる。判断（分岐）に対してb₀,変換に対してf₀というシンボルを使用する。最初の判断と変換の後、ダイアグラムはそれ自身を繰返す。

この単純なパターンは下記のようなシンボルで容易に表現できる；

　　　　　　　　　　　d = ( b₀　→ ( f₀ ; d ), I )

言い換えると、負(negative)で判断（分岐）を脱出する。一方、もし正(positive)ならば、同じ手順でf0を合成する。したがって、ダイアグラムはそれ自身を部分として含む（再帰処理である）。

　このダイアグラムdは実際にフロー・ダイアグラムの完備束D_∞に存在するだろうか？これを確かめるために、下記の式により定義された関数Φ:D_∞→D_∞を考える：

　　　　　　　　　　Φ(x) = ( b₀　→ ( f₀; x ), I )

　関数Φはダイアグラムの単調増加関数である（注1）。（タルスキの不動点定理（注2）より）完備束D_∞から完備束D_∞への全ての連続関数は不動点を持つ。このケースでは、我々はもちろん最小の不動点dを要求する；　　　　　　　　　　　d =Φ(d)

（注1）d_n⊆d_n+1とすると、(f₀；d_n)⊆(f₀；d_n+1)より、Φ(d_n) =( b₀→(f₀；d_n), I)⊆( b₀→(f₀；d_n+1), I)

　　　　　=Φ(d_n+1)したがって、Φは単調増加関数である。

（注2）不動点定理　　f : D→Dを完備束Dで定義されDに値を持つ単調関数とする。このときFは最小不動点p=f(p)を持ち、p=∩{x∈D : f(x)⊆x}となる。

９．まとめ

１．フロー・ダイアグラムはその積と和から束∪D_nを構成することが分かった。

２．近似写像ψにより束∪D_nの完備化D_∞を構成することができた。

３．フロー・ダイアグラムの完備束D_∞をベースにすることにより、（タルスキの不動点定理を適用することで）回帰プログラムの不動点の存在を示すことができた。すなわち、Scottの「フロー・ダイアグラムの束」は、プログラムの不動点意味論の土台を提示している。