リカバる -- 考え直す

結局僕は、元祖BNF（線形文法）も正規表現もろくにわかってないってことだなぁ。

まーまー、落ち着け、落ち着け。

破綻しているわけではない。なにから何までうまくいってない、ってわけではない。いやむしろ、けっこううまくいっているのだ。今まで調べて事情がわかっている素材を使おう。

1. 絵算、ハイパーグラフ（ペトリネット）表現
2. ウエス（上江州）計算、特に変数を圏にアタッチする手法、v→射。
3. Kleene圏、Conway（Elgot）圏、Kozen圏などの相互関係
4. Free*Cat関手と忘却関手の随伴、対応するモナド
5. ソート付き（あるいは、Kozenの意味で型付き）正規表現
6. 指標Σに対してFunctor(Σ^~, C)がCモデルの圏であること。

KとLを区別しよう

指標（アルファベット）Σの言語圏を、太字を使ってL[Σ]と書く。
L[Σ]は行列圏でああり、L[Σ](n, m)がhom-setとなる。係数半環Kは、K=L[Σ](1, 1)で与えられる。

Aを単なる集合（指標とは思わない）だとして、Aから作った正規列言語全体をL(A)、Aから自由生成したKleene半環をK(A)とする。L(A)とK(A)は、集合として同型だが、別物だ。集合としての同型を過剰に受け止めてはならない。L(A)とK(A)は構造的にはまったく別物だ。 Aを指標だと思ったものをΣとすると；K(A)≒L[Σ](1, 1) とはなる。

回路で考えよう

回路は、入力ポートセットX、出力ポートセットYを持つ。これとは別に、記号素子を含むとすると、その記号素子を実素子や他の回路図で置き換える操作がある。置き換え可能な記号の集合をΣとすると、この回路は Σ, X→Y のようなプロファイルを持つ。Σに対する素子ライブラリ（記号達Σに、実素子や回路が対応している）があれば、置き換えができる。置き換えた後に含まれる記号群はΓとなる（Γが空かもしれない）。

以上の議論で、X, Yの端子（ポート）は識別可能だが、本来名前は持たない。ポートセットに名前を持たせてしまうのが、ウエス計算における変数集合のアタッチだ。このアタッチのテクニックをウエス・トリックと呼んでおく。今まで計算がうまくいってしまったのは、ウエス・トリックが働いていたからだ。

ウエス・トリックでは、名前を持たない端子達X, Yに、Γ、Δという名前をアタッチする。その結果、Σ, X→Yが、Σ, Γ→Δ となり、端子のconnectionがsubstitutionで実行できてしまう。特にXが始対象のときは、Σ→Δとなり、端子のconnectionが忘れられてしまう。

本来、回路のconnectionと、記号に対するライブラリによるsubstitutionは別な操作だったのに、ウエス・トリックにより、回路がライブラリになって、操作がすべてsubsitutionになってしまう。まさにトリックなのだ。

指標圏がクセモノだ

指標圏は最初から二圏だと思わないといけない。0セルは端子（ポート）の集合、1セルは記号素子だ。指標Σ:X→Yは、二部ハイパーグラフ、または境界付きグラフだと思えばよい。この段階で既に、モノイド圏になる。1セルの結合はconnection、またはgluingで与えられる。

問題は2セルなのだ！ X, Yが端子集合だとして、Σ, Γ∈Sign(X, Y)に対して、f::Σ⇒Γ:X→Y が通常はKleisli射で与えられる。最初のステップとしては、基本的な指標射によって、圏Sign(X, Y)を構成する。圏Sign(X, Y)に対して、モナド（自由生成モナドFree*Cat(-)）F_X,Yが決まる。結局、（拡張された）指標射は、f:Σ→F_X,Y(Γ) in Sign(X, Y)という形をしている。必要がなければ、Fの添字は落とすことにする（実際、Fは大域的に、Sign全体で一挙に定義されることが多い）。

ambient category Cを選ぶと、Model(Σ) = Functor(F(Σ), C)となる。Σ:X→Y、Γ:Y→Zのとき、Model(Σ;Γ)がどう記述されるか？ それはこれから考える。

変数とウエス・アタッチメント

指標を境界付きグラフだと思い、ウエス・トリックについて考えてみると、項モナドTerm_Σ(X)に対する新しい定式化／見方が出てくる。

ソート付き変数集合X→Sというのは、実は、対象しかない離散圏Sに対してXをウエス・アタッチすることだと言える。x∈Xに対してsort(x)=s∈Sならば、xとsを同型射で繋ぐことがウエス・アタッチだ。ウエス・アタッチで作られたグラフ（X+Sがノード）は圏とみなせる。つまり、ソート付き変数集合は圏なのだ。

ソートがSである指標Σがあると、Sソート付き変数集合とΣはSで貼り合わせて融合和を作れる。融合和であるグラフΣ∪_SXから作られた自由圏は、最初からウエス構造（変数がアタッチされていること）を持つ。この圏は、ソート付けX→Sによる写像柱をΣにくっつけた形をしている。

上のようにして作った圏（Dとする）は、XとSを対象に含み、Σを部分グラフに含む。この圏Dのなかで、XまたはXから生成された対象から、部分圏Cの対象（S）に至る射を、X-項と呼び、その全体をTerm_Σ(X)と書く。

ウエス・アタッチメントの応用

ウエス・アタッチメントは、いろいろと応用がある。変数（離散圏）ではなくて、２つの圏（またはグラフ）を写像柱のソリッドパイプで繋ぐことができる。

境界付きグラフ達がコボルディズムlikeな圏を作るのだが、実は、圏の圏もコボルディズム圏なのではないか？ 境界付き圏を考えると、圏のgluingが考えられる。境界を固定する関手が2セルを与える。自然変換は3セルだから、三圏の例となる。

• 0セル -- 離散圏
• 1セル -- 境界付き圏
• 2セル -- 関手
• 3セル -- 自然変換

話を戻すと

言語理論を圏論的に扱うなら、自由圏、AbIM enrichment、ω-AbIM enrichmentなどが鍵になる。

注意すべきは、無意識のうちに指標やdenotationが変わっていたり、番号と変数が入れ替わっていたり、connectionがsubstitutionになっていたり、と、知らぬ間にドンドン状況が変わってしまうことだ。状況を整理したり、パラメータを固定しないと、ほんとに混乱する。