このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

ワイヤリング図とケリー/マックレーン・グラフ

応用圏論〈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〉の例です。

ケリー/マックレーン・グラフは、上段、下段にプラス・マイナスの符号が並んでいて、符号のあいだを有向辺〈エッジ〉で結んでいます。次のルールがあります。

  1. 上段の符号どうしを辺で結ぶときは、辺はプラスからマイナスに向かう。
  2. 下段の符号どうしを辺で結ぶときは、辺はマイナスからプラスに向かう。
  3. 上段の符号から下段の符号へと辺で結ぶときは、辺はプラスからプラスに向かう。
  4. 下段の符号から上段の符号へと辺で結ぶときは、辺はマイナスからマイナスに向かう。

ワイヤリング図からケリー/マックレーン・グラフへ

次のワイヤリング図を考えましょう。内側に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`$ が得られます。

したがって、ワイヤリング図のノード(キャンバス含む)とワイヤリングの情報は次のモノ達にエンコードされます。

  1. $`n + 1`$ 個の極性付き集合達 $`A_0, A_1, \cdots, A_n`$
  2. ワイヤリング関数
    $`w : A_0^- + A_1^+ + \cdots + A_n^+ \to A_0^+ + A_1^- + \cdots + A_n^-`$

この定式化では、ワイヤーの分岐〈コピー〉や消失〈破棄〉や明示的な交差〈スワップ〉などを表現していません。が、それらを導入するのは容易です。また、シンプルなワイヤリングだけでも多くのことが出来ます。