応用圏論〈ACT -- Applied Category Theory〉で頻繁に使用されるワイヤリング図は、ケリー/マックレーン・グラフとして表現できます。ケリー/マックレーン・グラフを経由すれば、ワイヤリングの関数による表現も自然に感じるでしょう。
この記事は、以下の2つの記事への補遺のようなものです。
内容:
ワイヤリング図とポート
次の図は、スピヴァック〈David I. Spivak〉のスライド "Wiring diagrams and state machines" からコピーしたものです。
これは、簡単なワイヤリング図〈wiring diagram〉です。内側の箱 X は単なる穴かもしれないし、中身が詰まったナニカかもしれません。外側の箱 Y はワイヤリング図を描いている環境であるキャンバスです。矢印のついた線がワイヤーです。
スピヴァックは内部のノードもキャンバスも箱〈四角形〉で描いてますが、形状は何だっていいので、ここでは円や楕円でノード〈キャンバス含む〉を描くことにします。ノードには、ワイヤーが出入りする場所があります。それをポート〈port〉と呼びます。以下の図は、ノードとノードに付随したポートを描いたものです。
ポートには、名前(またはID)、色(または型)、極性(または方向)が付いています。名前〈ID〉は個々のポートを識別する印で、ここでは通し番号を使っています。今回、ワイヤーの色〈型〉は考えません。すべてのワイヤーは同じ色〈型 | 種類〉だとします。極性は、ワイヤーがノードに入り込む〈incomming〉か/出ていく〈outgoing〉かを識別します。矢印を見れば分かりますが、オレンジ色のプラス・マイナスでも出入りの区別をしています。マイナスが入り込むポート、プラスが出ていくポートです。
ワイヤリング図は、ワイヤーにラベル付けしない(正確には単一のラベルしかない)ストリング図です。ストリング図とポートのより詳しいことは「ストリング図のテキスト化: ボックス&ポート方式」に書いてあります。
ケリー/マックレーン・グラフ
次の図は、チェン〈Eugenia Cheng〉の論文 "A relationship between trees and Kelly-Mac Lane graphs" からコピーしたものです。
これは、ケリー/マックレーン・グラフ〈Kelly-Mac Lane graph〉の例です。
ケリー/マックレーン・グラフは、上段、下段にプラス・マイナスの符号が並んでいて、符号のあいだを有向辺〈エッジ〉で結んでいます。次のルールがあります。
- 上段の符号どうしを辺で結ぶときは、辺はプラスからマイナスに向かう。
- 下段の符号どうしを辺で結ぶときは、辺はマイナスからプラスに向かう。
- 上段の符号から下段の符号へと辺で結ぶときは、辺はプラスからプラスに向かう。
- 下段の符号から上段の符号へと辺で結ぶときは、辺はマイナスからマイナスに向かう。
ワイヤリング図からケリー/マックレーン・グラフへ
次のワイヤリング図を考えましょう。内側に3つのノードがあり、1, 2, 3 と番号が付いています。外側のマルはキャンバスで、0 と番号付けしています。オレンジ色のプラス・マイナスはポートの極性です。ワイヤーに矢印を描いていませんが、極性〈符号〉があるのでワイヤーの向きは分かります。ポートの名前〈ID〉も書いてませんが、左から右へと通し番号が付いているものとします。
上のワイヤリング図は、以下のケリー/マックレーン・グラフに翻訳できます。
翻訳の方法の詳細は述べませんが、この一例からでもおおよその見当はつくでしょう。
極性付き集合
今までの例では、ノードのポートには通し番号を付けていました。が、ポートの名前は何でもいいので、有限集合 $`A`$ でノードのポートを名付けることにします。ノードのポートの集合と有限集合 $`A`$ は1:1対応し、特定の対応(名付け)が固定されています。
集合 $`A`$ 上の関数 $`s:A \to \{+, -\}`$ を考えます。この関数がポートの極性を表現します。$`(A, s)`$ を極性付き集合〈polarized set〉(または符号付き集合〈signed set〉)と呼びます。記号の乱用で、極性付き集合を $`A = (A, s)`$ とも書きます。
極性付き集合を $`A = (A^-, A^+)`$ と書くこともあります。ここで:
$`\quad A^- = \{x\in A \mid s(x) = - \}\\
\quad A^+ = \{x\in A \mid s(x) = + \}`$
ワイヤリング図のとあるノードのポート達と、集合 $`A`$ のあいだの1:1対応〈名付け〉を固定しているとき、ポート達の極性は集合 $`A`$ の極性付け $`s:A \to \{+, -\}`$ に反映されます。
ワイヤリング図の内部のノードには $`1, 2, \cdots, n`$ と通し番号を付けて、キャンバスは $`0`$ 番としましょう。各ノードのポート達を、$`A_1, A_2, \cdots, A_n, A_0`$ という集合で名付けして、ポート極性により各集合は極性付き集合とします。すると、$`n + 1`$ 個の極性付き集合が得られます。
$`n + 1`$ 個の極性付き集合達は、ワイヤリング図の内部ノードおよびキャンバスに付いているすべてのポート達の極性情報〈方向情報〉を持っています。しかし、ワイヤーの繋ぎ方〈配線 | ワイヤリング〉は分かりません。
ワイヤリング関数
ワイヤリング〈配線〉の情報は、次のような全単射関数 $`w`$ で与えることができます。
$`\quad w :
A_0^- + A_1^+ + \cdots + A_n^+ \to
A_0^+ + A_1^- + \cdots + A_n^-
%`$
ケリー/マックレーン・グラフの有向辺を、関数の“mapsto矢印”だと解釈すれば $`w`$ が得られます。
したがって、ワイヤリング図のノード(キャンバス含む)とワイヤリングの情報は次のモノ達にエンコードされます。
- $`n + 1`$ 個の極性付き集合達 $`A_0, A_1, \cdots, A_n`$
- ワイヤリング関数
$`w : A_0^- + A_1^+ + \cdots + A_n^+ \to A_0^+ + A_1^- + \cdots + A_n^-`$
この定式化では、ワイヤーの分岐〈コピー〉や消失〈破棄〉や明示的な交差〈スワップ〉などを表現していません。が、それらを導入するのは容易です。また、シンプルなワイヤリングだけでも多くのことが出来ます。