檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2013-02-16 (土)

スパンの圏の構成に疑問

| 17:32 | スパンの圏の構成に疑問 - 檜山正幸のキマイラ飼育記 を含むブックマーク

Cのなかで、f:X→A, g:X→B の組をスパンと呼び、(A←f-X-g→B) と書きます。fはスパンの左足、gは右足です。スパン (A←f-X-g→B) に対して dom((A←f-X-g→B)) = A, cod((A←f-X-g→B)) = B と定義して、域(dom)がAで余域(cod)がBであるスパンの全体を SPANC(A, B) と書きます。以下、圏Cは了解されているものとして、下付きのCは省略します。

f = (A←f1-X-f2→B), g = (B←g1-Y-g2→C) として、Bのところで余スパン (X-f2→B←g1-Y) を考えます。外の圏Cにはファイバー積(引き戻し)があるとして、余スパン (X-f2→B←g1-Y) に対するファイバー積を (X←x-Z-y→Y) とします。h1 = x;f1, h2 = y;g2 として新しいスパン h = (A←h1-Z-h2→C) を作って、h = f;g だと定義します。

以上のようにして、Cと同じ対象を持つ圏SPANが定義できそうです。しかし、実際には問題があります。

  1. 与えられたf, gに対して、その結合hがup-to-isoでしか決まらない。
  2. 結合律、左右の単位律もup-to-isoの法則となる。
  3. ホムセット SPAN(A, B) が巨大になることがある。

そこで、スパンのあいだに同値関係を入れます。f = (A←f1-X-f2→B) と f' = (A←f'1-X'-f'2→B) が同値だとは:

  1. 同型 i:X→X' がある。
  2. i;f'1 = f1 と i;f'2 = f2 が成立する。

この同値関係を〜として、商集合 Span(A, B) := SPAN(A, B)/〜 を作ります。SPANではなくSpanのなかで考えると、射の結合は一意的に定まり、結合律と単位律もon-the-noseで成立します。

これでめでたく圏Spanが構成できた。ほんとに? C = Set のケースで考えてみましょう。A = B = 1 = 単元集合として、Span(1, 1) を考えます。このホムセットに入るスパンの左右の足は自明なので、スパンのボディである集合だけを考えればいいことになります。つまり、f = (1←f1-X-f2→1) と f' = (1←f'1-X'-f'2→1) が同値だとは:

  • 集合の同型 i:X→X' がある。

これだけです。f 〜 f' とは結局、XとX'の基数が同じことです。よって、Span(1, 1) は基数の全体と同じです。基数の全体って小さかった? 小さくできる?

なんか条件を付けたり細工をして小さくする手もあるでしょうが、次のような圏もどき構造を(安全な範囲で)考えてもいいような気がします。

  • ホムセットが小さいとは限らない。
  • 射の結合はup-to-isoで決まればよい。
  • 結合律、単位律は、up-to-isoで成立すればよい。

ルーリーなどが使っている擬圏(quasi-category)がそのようなものだと思うけど、ホムセットのサイズはハッキリしないなー。

2013-02-07 (木)

関手的データモデル雑感へのメモ

| 17:04 | 関手的データモデル雑感へのメモ - 檜山正幸のキマイラ飼育記 を含むブックマーク

なんか午後から不調。晴れてないと散歩にも出たくないし。「関手的データモデル雑感: 正規形とかジョインとか」を書いてたときに頭に思い浮かんだけど書ききれなかったことをメモしておこう。箇条書きだけど。

  1. ER図は、関係圏Relでだいたい解釈できるだろう。
  2. 関係圏の射は二項関係なので、n項関係は表現できないと思っている人がいるかもしれない。それは間違い。Relではカリー化ができるので、n項関係(n = 0, 1も含む)は二項関係に変換できる。
  3. 集合圏Setと関係圏Relのあいだの“関係”(←日常語)は、スパンの圏をはさむと分かりやすい。スパンを対応(correspondence)と呼ぶ人もいる。
  4. SELECT文のような問い合わせは、スキーマの部分圏とそこからアンビエント圏への関手Qにコンパイルされる。問い合わせの実行と結果とは、関手Qの極限を求めること。(スピヴァックは別な定式化をしている。)
  5. 問い合わせの自由度が欲しいなら、アンビエント圏は有限完備であるのが望ましい。しかしたいていは、有限余完備である必要はない。むしろ、余極限は嫌われているような。
  6. アンビエント圏がトポスなら便利だが、そうじゃなくてもなんとかなる。
  7. トポスじゃないにしても、引き戻しでsubobjectを作る方法は有効だ。
  8. 関係圏とベキ集合モナドのクライスリ圏は同じものだが、この同型性は非常によく使う。
  9. 関係=集合値写像の、全域性(totality)と単葉性(univalence)は大事だ。転置と組み合わせると、単射性と全射性にもなる。
  10. Rel自己同型自己双対(self-dual)なコンパクト閉圏であることが、いろいろと都合のいい性質の背景になっている。

2012-09-05 (水)

インデックス付きクライスリ拡張

| 12:53 | インデックス付きクライスリ拡張 - 檜山正幸のキマイラ飼育記 を含むブックマーク

2012-08-20からの週は、一般化クライスリ構成/クライスリ拡張の話をしていたのですが、一般論は(僕には)無理だろうと書いています。

具体例をたくさん作ると、統一的手法が見えてくる可能性が皆無ではないでしょうが、個別の例を詳しく調べるほうが得策かな、と今は思っています。

今僕が知っている具体例には次があります。

  1. モナドに対するクライスリ圏
  2. モナドに対する余クライスリ圏
  3. モナドに対する両クライスリ圏
  4. メイヤー代数を使った一般化クライスリ圏
  5. 今“考え中”の余代数を使った例

モナドとコモナドの例は、両モナドの特殊な場合とみなせるので、最初の3つは統合できます。メイヤー代数を使った一般化クライスリ圏が両モナドの場合とどう関係するかはよくわかりません。しかし、参照モナドと更新モナドはメイヤー代数を使った構成法に吸収することができます。

具体例のあいだに共通性があるので、それらをまとめておきたいと思います。一般論という程の中身はなくて、単に外枠だけですが、共通の外枠をハッキリさせるだけでも考えやすくなります。

クライスリ拡張

「クライスリ構成」と「クライスリ拡張」は同義で使っていたのですが、ここでは「クライスリ拡張」を使うことにします。構成法は無視して、出来上がった拡張構造だけを問題にするからです。

オリジナルのクライスリ拡張を一般化しても、「もとの圏」と「拡張した圏」という概念は残るので、二者の関係をまとめておきます。もとの圏がC、拡張した圏をKとします。

  1. |C| = |K| 、つまり対象は変わらない。
  2. 関手 J:CK があり、A∈|A| に対して J(A) = A、つまり対象上では恒等(identity on objects)
  3. A, B∈|A| に対して、JA,B:C(A, B)→K(A, B) は、ホムセット間の写像として単射

以上のことは、Jを通して「CKの広い部分圏({broad, wide} subcategory)」とみなしていいことを主張しています。

フレイド圏の場合は、Cがデカルト圏であることを仮定します。Kのほうにもモノイド積(またはプレモノイド積)を仮定するので、モノイド構造に注目するわけです。今は単なる拡張構造に注目しているので、モノイド構造抜きフレイド圏となります。

「モノイド構造抜き」じゃフレイドじゃねー、と思うので、単にクライスリ拡張と呼んでおきます。本来の(モナドによる)クライスリ拡張よりは抽象化/一般化されています。

クライスリ拡張の圏とインデキシング

Cを固定して、Cのクライスリ拡張の全体を考えることにします。

J:CK と J':CK' が2つのクライスリ拡張のとき、関手 Φ:K→K' が、J;Φ = J' を満たすとき、J:CK から J':CK' への準同型とみなしましょう。C上のクライスリ拡張の全体を KlEx(C) とすると、この定義で KlEx(C) は圏になります。圏のサイズが気になるなら、出てくる圏は(適当な宇宙の)小圏と仮定してください。

ΦがJ:CK から J':CK' への射であるとき、単に Φ:KK' in KlEx(C) と書きます。KlEx(C) は圏の圏なので、文字通りの同型はあまり意味がなくて、Φ:KK' と Φ':K'K があって圏同値を与えるとき、KK'は“事実上同じ”とみなします。

Bが圏で、反変関手 H:BCat が次の条件を満たすとき、をインデックス付きクライスリ拡張(indexed Kleisli extension)と呼びます。インデックス付き圏なので、H(-) ではなくて H[-] と表記します。

  1. Bは終対象1を持つ。
  2. H[1] = C
  3. A∈B に対して、H[!A]:H[1]→H[A] はC(H[1]はC)のクライスリ拡張である。
  4. f:A→B in B に対して、H[f]:H[B]→H[A] はクライスリ拡張のあいだの射となる。

基礎に据える圏がBCの2つあるので、「ベースの圏」とか言うとどっちを指すか分かりません。Bインデックスの圏、またはパラメータの圏Cのほうは係数圏とでも呼んで区別することにします。

クライスリ拡張の拡張手

モナドを使ったクライスリ拡張のときは、A→B というクライスリ射は、もとの圏(係数圏)における F(A)→G(B) という射となります。クライスリ射の両端(域と余域)を作る関手の対を拡張手(extender)と呼んでみたのですが、実際には拡張手だけでクライスリ拡張は決まりません。

モナドの場合は、FとGは単なる台関手で、他にモナド構造(乗法と単位)、コモナド構造(余乗法と余単位)、ベックの分配法則などが必要になります。拡張手は、クライスリ拡張を構成する素材の一部に過ぎません。たくさんの素材からクライスリ圏を組み立てるレシピが必要なのです。

というわけで、拡張手は素材なのですが、どのような素材であるかをハッキリさせておきましょう。F, G:CD が関手(の対)で、J:CK がクライスリ拡張であるとき、(F, G) がJの拡張手になっているとは、次が成立していることです。

  • A, B∈|C| に対して、K(A, B) = D(F(A), G(B))。

K(A, B) と D(F(A), G(B)) はホントに等しくなくても系統的な同型があればいいのですが、イコールのほうが話が煩雑にならないでしょう。

実際の例ではたいてい、クライスリ拡張は拡張手を持っているので、拡張手を使って考えるのは有効です。


中身がない枠組みだけの話でしたが、この枠組みがあると具体例が説明しやくなります。次はたぶん具体例を。

2012-08-22 (水)

クライスリ拡張手

| 12:09 | クライスリ拡張手 - 檜山正幸のキマイラ飼育記 を含むブックマーク

昨日の記事「一般化クライスリ構成を探して」の補足。

一般化クライスリ構成でやりたいことは、2つの自己関手F, Gを使って「射」の概念を拡張することです。A→B から F(A)→G(B) に拡張するわけですね。当初僕は、このような (F, G) をモナドと呼んでいました。

なぜかと言うと、Fがコモナド(余モナド)(F, ν, ε) で、Gがモナド (G, μ, η) のケースを考えていたからです。FとGがまったく無関係だとクライスリ結合がうまく定義できないので、σ::FG⇒GF という自然変換があって、これによりベックの分配法則(と類似の法則)が成り立つことを仮定してました。

上記の状況では (F, G) を両モナドと呼ぶのは自然だと思います。しかし、F, Gがモナドやコモナドじゃないこともあるのです。(F, G) がメイヤー代数由来のときがその例です。もはや両モナドと呼ぶのは抵抗があります。あー困った。

(F, G) は、入力(射の域)と出力(射の余域)を拡張するので拡張関手と呼べばいいかな? もっと短くして拡張手(extender)。2つが組になっていることを強調するなら、拡張手対(extender pair)とか両拡張手(di-extender)とか呼べばいいでしょう。一般化クライスリ拡張の文脈であることを明示するには形容詞として「クライスリ」を付ければいいかと。

どうしてこういうモノに名前が要るかというと、クライスリ拡張手を対象とする圏を考える必要があるからです。圏の対象に呼び名がないのはとても不便です。クライスリ拡張手を対象とする圏の射は、クライスリ拡張構造を保つような自然変換です。拡張手の(関手としての)結合は、この圏の非対称モノイド積になるでしょう。

クライスリ拡張手を対象とする圏は、対応するクライスリ圏をインデックス(パラメータ)で束ねた構造を導くので、インデックス付きフレイド圏と似たような議論ができるんじゃないかと期待してます。

一般化クライスリ拡張の例

| 16:51 | 一般化クライスリ拡張の例 - 檜山正幸のキマイラ飼育記 を含むブックマーク

すぐ上の記事の追記みたいなもの。

一般化クライスリ構成/拡張について、次のように書きました(「一般化クライスリ構成を探して」):

いくつかの例を知っていて、ボンヤリした枠組みを想定している状態です。


個別の例を詳しく調べるほうが得策かな、と今は思っています。

具体例をちゃんと確認できたのは2009年7月でした。「両クライスリ圏が構成できた」という記事です。このときの例は両モナドで、出来た拡張圏は両クライスリ圏と呼んでいました。

(F, ν, ε) がコモナド、(G, μ, η) がモナドだとします。f:F(A)→G(B), g:F(B)→G(C) が2つのクライリ射だとして、F(f):F(F(A))→F(G(B)) と G(g):G(F(B))→G(G(C)) が作れます。自然変換 σ:FG⇒GF があるので、σB:F(G(B))→G(F(B)) を使うと、結合 (F(f);σB;G(g)) : F(F(A))→G(G(C)) を作れます。前後に νA と μC をくっ付けると、F(A)→G(C) が出来て、これがクライスリ結合を与えます。

別な例は比較的最近のもので、 メイヤー代数 (V, M) から作るものです。Δ:V→V×V をVの余乗法(対角)、α:V×M→V をMによる右作用(右スカラー乗法)とします。F(A) := V×A、G(B) := M×B とします。クライスリ射 f:F(A)→G(B) に対して F(f) : F(F(A))→F(G(B)) は、V×V×A→V×M×B となります。前に Δ×A、後に α×B を結合したものを f' とします。つまり、f' := (Δ×idA);F(f);(α×idB) 。この状況で、f#g := f';g' としてクライスリ結合が与えられます。

この2つの例を一緒に混ぜて扱えないかな? と考えています。さらに、もうひとつの例も調べているのですが、まだ詰め切れてないので、ハッキリしたら「個別の例」のレパートリーに加えることにします。

[追記]大域参照コモナド、更新モナド、メイヤー代数はたくさん混ぜて一緒に使えそうな感じです。例外モナドやトランザクションとの絡みがあるので単純ではないですけど。実ストレージの更新やトップレベルトランザクションのコミットを考えるとメイヤー加群は必要です。[/追記]

2012-04-09 (月)

メイヤー先生からモナド類似構造へ

| 09:31 | メイヤー先生からモナド類似構造へ - 檜山正幸のキマイラ飼育記 を含むブックマーク

計算モデル: 大域と局所、不純と純粋」において、不純な局所計算モデルには「Command-Query分離された状態遷移系」を採用したいと書きました。Command-Query分離とは、あの偉大なメイヤー先生が提唱している原理です。ストレージIOなどは、メイヤー先生の教えに従ってやりたいのです。

モノイドから得られるモナドを特徴付けるには? (よくワカリマセン)」において、モナドFが、モノイドMによる掛け算関手(スタンピング関手)になっていることを判定できたらいいな、と書きました。モノイド閉圏で考えるなら、自己関手Fの随伴関手が内部ホム関手(自己豊饒化)の意味で表現可能なとき、Fが掛け算関手になっているようです。この問題を双対化して、コモナドGがコモノイドVの掛け算関手で表現されるかどうか? を考えることもできます。

ストレージの線形代数: 泥臭いデータ操作の洗練された定式化」では、ファイルシステムやデータベースに対する書き込み操作が、モノイドとその上の加群とみなせることを説明しました。

これらの話は実は関連していまして、メイヤー先生の「Command-Query分離された状態遷移系」を作用圏フレイド圏の枠組みで使えないか、というのが問題意識です。メイヤー先生の「Command-Query分離された状態遷移系」に対応する代数構造を考えることができます*1。その代数構造を、基礎となる圏の自己関手圏に埋め込むことができます。すると、モナド類似物になります。モナド類似物はいっぱいあるので、そのなかで「Command-Query分離された状態遷移系」から作られたものを特定できるといいな、と思うのです。それができないにしても、メイヤー先生の教えを圏論的に考えるのは興味深い話です。

内容:

  1. 前提となること
  2. 対称モノイド圏のなかのメイヤー代数
  3. 自己関手上のメイヤー構造
  4. メイヤー代数上の加群とアイレンベルク/ムーア圏
  5. ストレージのクライアント/サーバー・モデル

前提となること

まだなんだか曖昧模糊とした話なんですが、とりあえずは、メイヤー先生の「Command-Query分離された状態遷移系」に対応する代数系をスケッチしておきます。メイヤー代数とかメイヤー構造とか呼ぶことにします*2

対称モノイド圏内のモノイド、余モノイド(コモノイド)、双モノイドの概念は前提とします。次の過去記事を参照してください。

モナドは自己関手圏のなかのモノイドとなります。この事については:

モノイドと余モノイドは双対な概念ですが、自己関手圏のなかの余モノイド(コモノイド)がコモナドです。もちろん、モナドとコモナドは双対な概念です。モナド/コモナドの双対性については:

一番簡単で一番重要なコモノイドは対角コモノイドです。対角コモノイドの掛け算関手によりコモナドが作れます。対角コモナドですね。メイヤー構造として使うコモノイド/コモナドは対角コモノイド/コモナドです。対角コモノイドは、物理や計算科学における観測の“古典性”を表現しているようです。

対称モノイド圏のなかのメイヤー代数

さて、メイヤー代数の定義をザッと述べましょう。以下、記号の乱用をして、台対象とその上の代数系に同じ記号を使う(意図的混同をしている)ので注意してください。

メイヤー代数は、群やモノイドのような単ソート代数ではなくて、ベクトル空間や加群のような多ソート代数です。背景となる対称モノイド圏Cのなかの2つの対象M, Vを取ります。気持ちとしては、MがCommand(更新操作)のモノイド、VがQuery(観測操作)のコモノイドを表します。MとVは無関係ではなく、ある法則により制約されて整合性を持ちます。

Mは、(M, e, m) というモノイド構造を持ちます。さらにMは、Commandの複製に相当する余モノイド構造を持ち、これは (M, !, Δ) とします。!が余単位、Δが余乗法(余積)です。!, Δ は対角コモノイドを意識した記号ですね。全体として (M, e, m, !, Δ) は双モノイドとなっています。つまり、次の図で表される双代数法則(双モノイド法則)を満たします。(より詳しくは「ホップ代数の法則達の絵」)

今後Mは双モノイドと考えますが、Mのモノイド部分に注目するときは、Mmon と書くことにします。Mmon は、双モノイドMに、コモノイド構造を忘れる忘却関手を作用させたものです。

もうひとつVという代数系を考えます。こちらは余モノイドです。V = (V, !, Δ) と書きましょう。同じ記号 !, Δ を使ってますが、これはV上の余単位と余乗法です。余モノイドVの余モノイド構造を忘れてCの対象とみなしたものを Vobj と書きます。

双モノイドMと余モノイドVの組み合わせがメイヤー代数となるには、さらに次の構造と法則が追加されます。

  1. VobjがMmon上の加群となるように、スカラー乗法 a:V×M→V in C が与えられている。
  2. スカラー乗法aに関する双代数法則が成立する。

aが右乗法の形になってますが、左乗法でもかまいません。VがM上の片側加群になっていれば左右は問いません(ただし、どっちかに固定する)。

スカラー乗法aに関する双代数法則とは次の法則です。×はCのモノイド積、Iはモノイド単位対象、σは対称、iは I×I→I の同型とします。

  1. a;Δ = (Δ×Δ);(id×σ×id);(a×a)
  2. a;! = (!×!);i

二番目は、「データを捨ててしまうなら事前に何をやっても関係ない」といった内容で、特に問題なく成立します(たいていは)。一番目はけっこう実現が難しい条件で、Commandによる更新で「Queryによる観測結果」がどう変わるかを事前に予測可能であることを主張しています。「リモートストレージへの変更を、ローカルキャッシュ上で完全にシミュレートできる」ということです。

自己関手上のメイヤー構造

対称モノイド圏C内のメイヤー代数の構成要素は次のようになります。

  1. 対象M
  2. 単位 e:I→M
  3. 乗法 m:M×M→M
  4. 余単位 !:M→I
  5. 余乗法 Δ:M→M×M
  6. 対象V
  7. 余単位 !:V→I
  8. 余乗法 Δ:V→V×V
  9. スカラー乗法(作用) a:V×M→V

同じ記号を使ってますが、余単位、余乗法は2つずつあります。法則性としては、Mが双モノイド、Vが余モノイド(コモノイド)、スカラー乗法aによりVがM右加群、そしてaに関する双代数法則です。これらの法則は圏の可換図式を使って記述できるので、メイヤー代数の概念は任意の対称モノイド圏の上で定義可能です。

では、圏Cの自己関手の圏 E := End(C) の上でメイヤー代数を定義可能でしょうか? 残念ながらそのままではうまくいきません。圏Eには対称性がないので、双代数法則が記述できないのです。よって、「Mが双モノイドであること」や「aに関する双代数法則」などが意味を持ちません。

モノイド圏の対称性σは、圏全体に渡って大域的に定義された自然変換(同値) σX,Y:X×Y→Y×X です。非対象なモノイド圏では、そのような大域的な自然変換は取れません。しかし、個別のX、Yを取ったとき、XとYをスワップする自然変換 X×Y→Y×X なら選べる可能性があります。つまり、対称性を圏全体の構造として持つのではなくて、個々の代数系ごとの局所的/個別的な対称性として定義します。

局所対称性を定義に含めると、先の構成要素に加えて、M×M→M×M と V×M→M×V というスワップ射が増えて、これを使って双代数法則を記述します。この方法を使って、E内のメイヤー代数=自己関手上のメイヤー構造を定義できます。その構成要素は次のようになります。

  1. 自己関手 F:CC
  2. 単位自然変換 η:Id⇒F
  3. 乗法自然変換 μ:FF⇒F
  4. 余単位自然変換 ε:F⇒Id
  5. 余乗法自然変換 δ:F⇒FF
  6. スワップ自然変換 γ:FF⇒FF
  7. 自己関手 G:CC
  8. 余単位自然変換 ε:G⇒Id
  9. 余乗法自然変換 δ:G⇒GG
  10. スカラー乗法(作用)自然変換 α:GF⇒G
  11. スワップ自然変換 β:GF⇒FG

スワップ自然変換 γ:FF⇒FF を使うことにより、Fが双モナド(圏E内の双モノイド)であることを記述できます。β:GF⇒FG を使うと、αに関する双代数法則を記述できます。γやβは、ベックの法則の公理を満たすことを要求します。

これで、非対称モノイド圏E(= End(C))内のメイヤー代数が定義できます。複雑そうですか? ストレージ操作のモデルを作ろうと思うとまーコンナモンですよ、そんなに簡単にはできないんです。

ベースとなる圏C内のメイヤー代数(M, V)があれば、F(X) := X×M、G(X) = X×V として、その他諸々の自然変換を定義すれば、2つの自己関手F, Gを台とするメイヤー構造を構成できます。この構成は、圏C内のメイヤー代数の圏(ちゃんと定義してませんが)から圏E内のメイヤー代数の圏への埋め込みとなるものです。圏CSetのような具体的な圏に取れば、メイヤー代数と「Command-Query分離された状態遷移系」(のクライアント部分)は事実上同じものなので、自己関手上のメイヤー構造の例はすぐに作れます。

メイヤー代数上の加群とアイレンベルク/ムーア圏

C上のモナド F = (F, η, μ) が、圏C内のモノイドMを使って F(X) := X×M と(関手の同値の意味で)書けるとき、モナドFの代数 a:F(A)→A in C は、a: A×M→A なので、M右加群となります。加群の左右は気にしないことにして、単にM加群と呼びましょう。

モナドFに対するF代数の圏 Alg(F) はアイレンベルク/ムーア圏に他なりません。一方で、モノイドMに対する加群の圏 Module(M) は、モナドに言及せずに構成できます。F(X) := X×M のとき、この2つの圏 Alg(F) と Module(M) は圏同値になります。

以上の事実と同じことがメイヤー代数に関しても成立しているように思えます。自己関手の対(F, G)上のメイヤー構造はモナド類似物(monad-like entity)であり、アイレンベルク/ムーア構成と類似の方法が使えそうです。メイヤー代数(M, V)上の加群はハッキリ定義できるので、加群の圏 Module(M, V) を構成できます。メイヤー構造を持つモナド類似物のアイレンベルク/ムーア類似圏は、メイヤー代数上の加群の圏とたぶん圏同値でしょう。

C内のメイヤー代数より、非対称モノイド圏E(= End(C))に持ち上げたメイヤー構造を考えたいのは、モナドの相対化やインデックス付け(パラメトライズ)と似たことをメイヤー構造に対しても行えるとうれしいからです。

ストレージのクライアント/サーバー・モデル

不純な計算のなかで実務上一番よく使うのはおそらく副作用(主作用?)で、副作用のなかで最も重要なのはストレージIOでしょう。

ストレージサービスが、サーバーとクライアントで与えられるとして、キャッシュ付きのクライアントの定式化がメイヤー代数です。クライアントとサーバーを一緒に考えると加群の構造を持ちます(この事情の背景は「ストレージの線形代数: 泥臭いデータ操作の洗練された定式化」参照)。メイヤー代数の定義に含まれる双代数法則は、クライアント側キャッシュの整合性の条件です。

Command-Query分離された状態遷移系、メイヤー代数、自己関手上のメイヤー構造、メイヤー代数上の加群などの関係がハッキリすれば、トランザクションや排他制御の話を含めて*3ストレージの扱い方がもう少しわかるんじゃないかなー、と期待してます。いまのところ、期待に過ぎませんが。

*1:実際は、インターフェースと実装、クライアントとサーバーなどにより、何種類かの代数構造が出現します。

*2:メイヤー代数/メイヤー構造は、状態遷移系のインターフェース部/クライアント部の定式化です。

*3:ひとつのモノイド(多元環)上のたくさんの加群を考えるのは普通ですが、ひとつの加群(の台)にたくさんのモノイドを考えることはあまりしません。せいぜい2つのモノイド作用を持つ両側加群(双加群)くらいです。トランザクションや排他制御の話が代数化しにくいのは、多数のモノイドが作用する加群の議論が不足しているせいかもしれません。

ksks 2012/04/19 21:04 メイヤー代数 (M, V) に関して, V は M-module のなす monoidal category におけるコモノイドであるようですね。
これはホップ代数の分野などで module coalgebra とか呼ばれているものですが、こういったものが計算科学の文脈で自然に現れるということ、非常に興味深く拝見させていただきました。

m-hiyamam-hiyama 2012/04/20 10:27 ksさん、
> メイヤー代数 (M, V) に関して, V は M-module のなす monoidal category におけるコモノイドであるようですね。
はい、そうなります。
M-modulesのコモノイドの圏の対象Vを固定して、V上のスライス圏を作ると、メイヤー代数(M, V)上のメイヤー加群の圏になります。
> これはホップ代数の分野などで module coalgebra とか呼ばれているものですが、
そうなんですか。僕は、ホップ代数関係のプロパーな話はよく知りません(^^;。
> こういったものが計算科学の文脈で自然に現れるということ、
とても不思議に感じるんですが、なんかの必然性があって当たり前のことなのかもしれません。
背景は謎ですが、現象としてはプログラミング上の概念がストレートに代数的概念に対応するので驚きます。

2011-09-06 (火)

緩関手、反緩関手、強関手、厳密関手とか、おぼえられねー

| 12:32 | 緩関手、反緩関手、強関手、厳密関手とか、おぼえられねー - 檜山正幸のキマイラ飼育記 を含むブックマーク

厳密(strict)とは限らない一般的モノイド圏って、一貫性条件があるので定義がそもそもヤヤコシイです。モノイド圏のあいだの構造を保つ関手はモノイド関手(monoidal functor)ですが、これがまた何種類もあってメンドクサイ。自然変換の向きで呼び名が変わったりするので、分類がおぼえられない。コジツケでもいいから、うまい覚え方がないかなー。おぼえられそうにないので、後で参照するためのメモを書いておこう、っと。

関手の種類であるlax, oplaxには決まった訳語もないようなので、とりあえず「緩」「反緩」としておきます。strong, strictは、比較的定着している「強」「厳密」を使います。

C, Dがモノイド圏として、モノイド積は□、単位対象はIで表すことにします(適宜、記号の乱用をします)。CからDへの緩モノイド関手(lax monoidal functor)は次の構成要素からなります。

  1. モノイド構造を忘れたC,D(単なる圏)のあいだの関手 F:CD
  2. 自然変換 Φ::F(-)□F(-)⇒F(-□-):C×CD
  3. 射 ΦI:I→F(I) in D

関手Fを、Φcatと置いて、Φ = (Φcat, Φ, ΦI) と書くことにします。構成要素である Φcat, Φ, ΦI はそれぞれ、台の圏(underlying category)、モノイド積、モノイド単位の対応付けと変換の操作です。

これらの構成要素が満たすべき条件として、五角形の可換図式が1つと三角形の可換図式が2つあります。可換図式をそのまま描くのは手間なので、射の経路を別々に書き下して「どっちの経路を通っても同じ」というスタイルで条件を記述することにします。

えっ、なに、外出する時間? そうですか。続きはまた後で。 続きをこの下に書きます(2011-09-07)。

モノイド圏におけるup-to-isoの計算法則を与える構造自然同型を α, λ, ρ とします。

  1. αA,B,C:(A□B)□C→A□(B□C)
  2. λA:I□A→A
  3. ρA:A□I→A

それぞれ、結合律、左単位律、右単位律の記述となっています。これらは全部同型射なので、逆射が存在します。

  1. αA,B,C-1:A□(B□C)→(A□B)□C
  2. λA-1:A→I□A
  3. ρA-1:A→A□I

手始めに、緩モノイド関手の五角可換図式に対応する法則を書き下してみます。入れ子の括弧を見やすくするために、関手Fと対象Aの適用をF(A)ではなくて、FA または F[A] と書くことにします。F := Φcat, Φ := Φ, φ := ΦI という別名も使います。

緩モノイド関手の結合律に関する一貫性

緩モノイド関手では、FA□(FB□FC)→F[(A□B)□C] という変形を考えます。変形には、結合律同型(associator)αと自然変換 Φ = Φ を使います。

一番目の変形の経路は次です。


  FA□(FB□FC)
 ------------- FA□ΦB,C
  FA□F[B□C]
 ------------- ΦA,B□C
  F[A□(B□C)]
 ------------- F[α-1]
  F[(A□B)□C]

そして、二番目の経路は次。


  FA□(FB□FC)
 ------------- α-1
  (FA□FB)□FC
 ------------- ΦA,B□FC
  F[A□B]□FC
 ------------- ΦA□B,C
  F[(A□B)□C]

以上の2つの経路を使った変形が、モノイド圏D内の同一の射:FA□(FB□FC)→F[(A□B)□C] を与えるという主張が、結合律に関する一貫性です。

緩モノイド関手の左単位律に関する一貫性

結合律のときと同様なので、I□FA→F[I□A] の2つの経路だけを書きます。

一番目:


  I□FA
 ------- λ
   FA
 ------- F[λ-1]
 F[I□A]

二番目:


  I□FA
 ------- φ□FA
 FI□FA
 ------- ΦI,A
 F[I□A]

右単位律に関する一貫性もまったく同様なので省略します。FA□I→F[A□I] を考えてください。

反緩モノイド関手と双対性

緩モノイド関手と反緩モノイド関手は、ある種の双対になっています。構成要素である自然変換、射の向きが逆です。Ψ = (Ψcat, Ψ, ΨI) = (G, Ψ, ψ) が反緩モノイド関手だとは次のことです。

  1. モノイド構造を忘れたC,D(単なる圏)のあいだの関手 G:CD
  2. 自然変換 Ψ::F(-□-)⇒F(-)□F(-):C×CD
  3. 射 ΨI:F(I)→I in D

結合律、左単位律、右単位律という計算法則の一貫性を考えるときの向きも逆になります。

  • 結合律 F[(A□B)□C]→FA□(FB□FC)
  • 左単位律 F[I□A]→I□FA
  • 右単位律 F[A□I]→FA□I

緩(lax)と反緩(oplax)は、単に矢印の向きが逆転するだけで、どちらがより基本的ということはありません。それで当然に、どっちが緩で、どっちが反緩かの説得的基準はなく、「おぼえられねー」のです。

特に必然性がない(あるか?)連想なのですが、I□FA→F[I□A] は、テンソル強度(tensorial strength)と同じ形です。テンソル強度は、A□FB → F[A□B] という射として定義されます。余強度(costrength)の形は、F[A□B]→FA□B です。テンソル強度/余強度では、積(モノイド積、テンソル積)が関手の中に入り込む方向が正順で、積が関手の外に出て行く方向が逆順になっています。

緩モノイド関手と反緩モノイド関手でも、モノイド積が関手の中に入り込む方向がlaxで、モノイド積が関手の外に出て行く方向がoplaxなので、強度のときと同じ、と言えなくもありません。これをヒントにしておぼえられるかなー?

強モノイド関手と厳密モノイド関手

強モノイド関手とは、緩モノイド関手の定義で登場するΦとΦIがそれぞれ、自然同型と同型射となっているものです。一貫性を与える射が同型射(可逆射)になるので、もう矢印の向きを気にする必要はありません。強モノイド関手の双対の反強モノイド関手という概念は、強モノイド関手と同じになります。

厳密モノイド関手は、強モノイド関手における同型射が恒等射になったものです。up-to-isoではなくてon-the-noseで等式が成立するので、普通の当式変形が気兼ねなく使えます。

なお、形容詞なしで単にモノイド関手と言った場合は、強モノイド関手を意味することが多いようです。

モノイド圏の圏

関手圏のような高階の概念を使うと、見通しがよくなることがあります。モノイド圏の議論をするときも、モノイド圏を対象にして、なんらかの種類のモノイド関手を射とする圏を考えほうが有利なときもあります。そのときは、なんらかの種類のモノイド自然変換も考えて2-圏として、ベースのモノイド積から入れた構造も一緒に考えます。

高階でいろいろな構造を備えた複雑な圏ができますが、探しているモノがそういう圏に生息している可能性があれば、構成して調べてみるしかないですね。

2010-10-20 (水)

絵算で見る「カザネスク/ステファネスク/ハイランド/長谷川の定理」

| 17:48 | 絵算で見る「カザネスク/ステファネスク/ハイランド/長谷川の定理」 - 檜山正幸のキマイラ飼育記 を含むブックマーク

必要があって、今日の午前中スターバックスで絵算。長谷川真人(はせがわ・まさひと)さん等による定理を確認しただけですが、なんか疲れましたねー。

なんに必要か?とか背景とかは全部割愛。スンマセン。以下に予備知識あるいは関連するエントリー。

トレース、ダガー、スター

C = (C, +, 0, σ) を対称モノイド圏として、対称なモノイド積+(足し算の形に書きました)に関してトレースTrもあるとします。つまり、(C, +, 0, σ, Tr) がトレース付き対称モノイド圏です*1

f:A+X→B+X に対して、Tr(f) = TrA,BX(f) :A→B となります。トレースについて今は説明しませんが、次のような公理で特徴付けられます。

  1. バニッシング(アクション性)
  2. タイトニング(自然性)
  3. スライディング
  4. スーパーポージング*2(強度性*3
  5. ヤンキング

fのトレースTr(f)を、f とも書くことにします。

さらに、圏Cには余対角∇があるとします。この状況で、f:X→A+X のエルゴット(Calvin C. Elgot)のダガー f:X→A は次のように定義されます。

  • f := [∇;f]

[追記]以下で「クリーネスター」と書いているところは、スターじゃなくてプラス、つまり1回以上の繰り返しでした。*を+に直すとダガー†と区別が付きにくいので、*>0 と訂正することにします。また、クリーネプラスって用語も一般的じゃないので、クリーネスター(1回以上)としておきます。絵の方はそのままです。[/追記]

Cに対角Δもあると、f:A→A のクリーネスター(1回以上) f*>0:A→A も定義できます。

  • f*>0 := [f;Δ] = [∇;(f;Δ)]

トレース()からエルゴットダガー()、エルゴットダガーからクリーネスター(1回以上)(*>0)が定義できます。これは逆も成立します。

  1. 単位iと余対角∇を持つ対称モノイド圏では、トレースとエルゴットダガーは1:1に対応する。
  2. 上の条件に加えて、余単位!と対角Δを持つ対称モノイド圏では、エルゴットダガーとクリーネスター(1回以上)は1:1に対応する。

単位iと余対角∇を持つ対称モノイド圏とは余デカルト圏のことで、余単位!と対角Δを持つ対称モノイド圏とはデカルト圏のことです。単位、余対角、余単位、対角を全部備えていて、さらに若干の条件を満たす圏は双デカルト圏で、すべての対象が双モノイド(双代数)構造を持ちます。これらの概念・用語を使えば、上の命題は次のように言い換えられます。

  1. 余デカルト圏では、トレースとエルゴットダガーは1:1に対応する。
  2. 双デカルト圏では、エルゴットダガーとクリーネスター(1回以上)は1:1に対応する。

余デカルト圏の双対はデカルト圏で、エルゴットダガーの双対はコンウェイダガーとも呼ばれる不動点演算子です。トレースは自己双対的な概念なので、トレースの双対はトレースです。よって次が成立します。

  • デカルト圏では、トレースとコンウェイダガー(不動点演算子)は1:1に対応する。

このような事実は、1980年代末にカザネスク/ステファネスク(Cazanescu, Stefanescu)により認識されていました。ハイランド(Hyland)も同じことを述べているようです。一般的かつ完全な記述は、長谷川真人(はせがわ・まさひと)さんにより与えられました。

絵算

f := [∇;f] と f*>0 := [f;Δ] に対して、逆向きの公式を絵で与えます。

  1. 定義:f := [∇;f]
  2. 逆向き:f := (A+iX);[(f+iA);(B+σX,A)]
  3. 定義:f*>0 := [f;Δ]
  4. 逆向き: f := (iA+X);[(!A+X);f]*>0;(A+!X)

赤い斜線は打ち消し線で、打ち消された部分はナカッタコトにされます。ほんとに消してしまうと、自明な絵になります。

定義:f := [∇;f]

逆向き:f := (A+iX);[(f+iA);(B+σX,A)]

定義:f*>0 := [f;Δ]

逆向き: f := (iA+X);[(!A+X);f]*>0;(A+!X)

*1:比較的最近の用語法では、形容詞を連ねるのはやめて、トレース付き圏(traced category)のように簡略に呼ぶようです。

*2:スーパーポージングは歴史的な用語法で、いまでは相応しい呼び名ではありません。

*3:テンソル強度とみなせる、ということです。

内海内海 2010/10/20 15:29 >檜山の顔とCaty猫の絵
もの凄く個人的な評価ですけど(^_^;)前に見た写真での檜山さんに似ているのは次男さんの絵の方ですね。目元の感じが似ていると思います。catyの方はピッタリですね。これならサンリオからも抗議は絶対こないでしょうし(^^)

m-hiyamam-hiyama 2010/10/20 16:35 内海さん
> 目元の感じが似ていると思います。
額と眉毛までは長男も次男も同じように描いてますね。目元は長男が眠たげ、次男は目覚めている感じで、まー実際こんな感じかな。

> これならサンリオからも抗議は絶対こないでしょう
そうです。そこが問題だったのです。ちなみに、この猫はドラえもんが入っていて、宇宙から来たロボットという設定です。

tanabetanabe 2010/10/22 06:55 妙に惹かれる味のある絵ですね。

下にあるクリーネスターなんかの絵と
タッチとか、ヘタウマの物悲しさだとか、
なんだか共通したものを感じます。
同じ人が描いたと言われても疑わないでしょうね。
絵心も遺伝するのでしょうか。

m-hiyamam-hiyama 2010/10/22 09:46 tanabeさん、
> 下にあるクリーネスターなんかの絵と
そこと比較しますか、
> タッチとか、ヘタウマの物悲しさだとか、
> なんだか共通したものを感じます。
クリーネスターの絵がヘタウマですか?
けっこう描き慣れているのでヘタじゃないと思っているんだけどなあ。

> 同じ人が描いたと言われても疑わないでしょうね。
> 絵心も遺伝するのでしょうか。
確かに、字も含めて誰が書いたのか不明なことはあります。
see http://d.hatena.ne.jp/m-hiyama/20071207/1196994636

2010-07-07 (水)

モノイドだけで作る幾何空間 準備編

| 09:56 | モノイドだけで作る幾何空間 準備編 - 檜山正幸のキマイラ飼育記 を含むブックマーク

お断り:続きはいつになるか分かりません。この準備編だけで終わる可能性もありますね ^^;

コンヌとコンサニの論文 "Characteristic 1, entropy and the absolute point" ( http://www.alainconnes.org/docs/Jamifine.pdf)を拾い読みすると、次のようなメッセージがあるように思えます。

  • 掛け算があれば、足し算はなくてもいいんじゃないか

今まで可換環が担っていた役割を、吸収元付き可換モノイド(commutative monoid with absorbing element)で代用することがかなりの程度できるようです。ただし、足し算は冗長な概念だったということではなくて、足し算がない世界も存在し得るということです。そして足し算がない世界は、足し算がある世界とは様相が一変します。エキゾチックを超えてミステリアスな世界のようです*1

以下では、モノイド演算は常に掛け算(乗法)とみなし、その吸収元をゼロと呼びます。足し算は考えないので、ゼロは足し算の中立元(単位元)ではなくて、掛け算により次のように特徴付けられる元です。

  • 任意のxに対して、x・0 = 0・x = 0

ゼロ付き可換モノイドの圏をCMoZ(Commutative Monoid with Zero から)と書くことにします。CMoZの射は、f(0) = 0 となるモノイド準同型です。(コンヌ/コンサニは、CMoZではなくMoという記法を使っています。)

ここでは、コンヌ/コンサ二に沿って、ゼロ付き可換モノイド概念だけから幾何空間(geometric space)を構成します。「空間」という言葉はやたらに色々な場面で使われるので、本来の幾何学的な空間を幾何空間と呼びます。幾何空間とは位相空間であって、座標や関数環(の類似)の概念を持つものです。デカルトの意味での解析幾何の対象物と言ってもいいかもしれません。

まだ定義はしていませんが、幾何空間の圏をGSと書きます。モノイドがベースなので、モノイド幾何空間または幾何モノイド空間(monoidal geometric space, geometric monoidal space)と呼ぶのが正式ですが、モノイド・ベースだと了解されているなら単に幾何空間とします。モノイド空間とは限らない場合は、「一般の幾何空間」と呼ぶことにします。

幾何空間の圏GSの性質をチャンと記述する能力も気力も僕にはないので、CMoZからGSへの関手 Spec:CMoZGS の具体的構成だけを述べます。Specは反変関手で、充満埋込みとなります。つまり、CMoZの反対圏は、GSの部分圏と同一視可能です。関手Specは、素スペクトル関手ですが、環の素スペクトル関手とほとんど同じように構成できます。

関手Specの構成だけでも色々と作業があるので、今回は枠組みの準備です。

一般の幾何空間のアブストラクトナンセンスな定義

Cは圏で、その部分圏Lが与えられているとします。C=(可換環の圏)、L=(局所環の圏)が典型的な例です。圏Cの対象は、空間の上に棲んでいる関数達の集合を表現するモノです。部分圏Lの対象は特に、1点での関数芽の集合を表現するのに適したモノ、Lの射は1点の周辺の対応を記述するモノですね。茎や芽の概念を定義するために、圏Cでは、有向系(directed family of objects)の極限が取れる必要があります。

さて、(X, S)が(C, L)に値を持つ幾何空間であるとは:

  1. Xは位相空間である。Xを、幾何空間の台空間(underlying (topological) space)と呼ぶ。
  2. SはX上の層である。Sを、幾何空間の構造層(structure sheaf)と呼ぶ。
  3. Xの点xにおける茎Sxは、部分圏Lの対象となる。

最後の条件は局所性(locality)条件と呼びます。Cの部分圏Lに属する対象は、空間の1点の状況を記述する目的のモノで、局所対象と呼びます。局所性条件は、空間の各点が実際に局所対象で記述できるということです。

C=(可換環の圏)、L=(局所環の圏)であるときが、通常の代数幾何のセッティングです。これ以外の状況を一般的に定義してもナンセンスな感じですが、可換環以外の例が少なくとも1つ(モノイドのケース)がある*2ので、一般的な定義を与えておきます。

位相空間Xの開集合の全体を順序集合とみなしたモノをOpen(X)とします。Open(X)は圏でもあり、X上の構造層とは、圏Open(X)上の反変関手です。f:X→Y が連続写像だとすると、f-1は、Open(Y)→Open(X) という関手を定義します。関手とみなしたf-1を前結合(pre-compose)することにより、X上の層からY上の層を誘導できます。この方法でSから作ったY上の層 f-1;S :Open(Y)→C を、fによりSを押し出した層といい、f*S と書きます。f, f-1, f*と、矢印の方向がめまぐるしく入れ替わるので注意してください。

[追記]層の準同型Ψの向きが逆でした。取り消し線で訂正しますが、可換図式は置き換えてあります。[/追記]

(X, S)と(Y, T)が(C, L)に値を持つ幾何空間のとき、準同型ψ:(X, S)→(Y, T) とは、位相空間のあいだの連続写像 f:X→Y と、Y上の層の準同型 Ψ:f*S→T T→f*S の組です。つまり、ψ = (f, Ψ) です。ここで、層の準同型は、層を関手とみなしての自然変換で与えられます。

Ψを具体的に記述してみましょう。U, V をYの開集合で、V⊆U とします。自然変換Ψの成分は、ΨU:S(f-1(U)) → T(U) T(U) → S(f-1(U)) というCの射です。ρ'U,V:S(f-1(U))→S(f-1(V))、ρU,V:T(U)→T(V) は層の制限射です。Ψは自然変換なので、次の可換性を満たします。


     T(U) -----ρU,V ---> T(V)
       |                    |
      ΨU                  ΨV
       |                    |
       v                    v
   S(f-1(U)) --ρ'U,V --> S(f-1(V))

ψ = (f, Ψ):(X, S)→(Y, T) が幾何空間の準同型であるには、次の局所性条件が必要です。

  • Yの点yにおける茎のあいだの対応Ψy:(f*S)y→Ty Ty→(f*S)y は、部分圏Lの射である。

モノイド・ベースの幾何空間

上の一般的な幾何空間の定義では、(C, L)がパラメータになっていました。(C, L)を具体化します。

  • ベースとなる圏Cとして、CMoZを採用する。つまり、可換な掛け算ができて、0を持つような代数系とその準同型の圏です。
  • Cの部分圏Lとして、対象はCMoZと同じで、可逆元の逆像がちょうど可逆元になるような準同型(後述)からなる圏をとる。

二番目の条件は次の意味です; f:M→N がCMoZの射だとして、M×, N×を可逆元の集合だとします。掛け算の単位1は可逆元なので、M×, N×は空ではありません。fが局所射だとは次が成立することです。

  • f-1(N×) = M×

可換モノイドの圏では、特に局所モノイドは定義されません(すべての可換モノイドが局所モノイドであると考えてよい*3)。一方、局所射はかなり厳しい条件で定義されます。CMoZの局所性の定義がなんでこうなっているのか、僕はよく分からないのですが、「点」の概念のひとつの表現らしいです。

足し算と掛け算

ここまでの話は、やたらに一般的な枠組みを準備しただけで、「足し算が不要」とか「掛け算だけ」の内容には踏み込んでいません。「掛け算だけでOK」を実質的に示すには、可換な掛け算(とゼロ)だけを持つモノイドM(CMoZの対象)から、幾何空間 Spec(M) を実際に作る必要があります。Spec は関手になっていて、CMoZGSに(反変的に)埋め込みます。

これが事実なら、可換モノイドは必ず何らかの幾何空間なのだ(控えめに言えば、「何らかの幾何空間から派生するものだ」)と言えます。


[追記]

GSは、グロタンディーク構成の良い例になっていますので、そのことを補足します。

位相空間X上の「圏Cに値をとる層」の圏をShf[X]とします。圏のベキ(指数)DCを[C, D]とも書くことにすれば、Shf[X] = ([Open(X), C]の適当な部分圏)です。連続写像 f:X→Y があると、層の押し出しは、f*:Shf[X]→Shf[Y] という関手を定義します。この状況は、(関手の反変・共変の違いを無視すれば)Shf[-] が位相空間の圏Topをベース圏とするインデックス付き圏(indexed category)であることを意味します。幾何空間の圏は、このようなインデックス付き圏から作ったグロタンディーク構成になっています。(「インデックス付き圏のグロタンディーク構成」を参照。)

[/追記]

*1:足し算がベキ等である世界はエキゾチック(専門用語としてエキゾチックと呼ぶ)ですが、(仮称)“真実の標数1”の世界にはさらに我々の直感を裏切る現象があるみたい。

*2:Cとして可換バナッハ環の圏をとると、ゲルファンドの理論になりそうです。

*3:モノイドでは、極大イデアルが常に1つしかないのです。これは、空間に「点らしい点」は1個しかないことを意味するみたいで、モノスゴク不思議な感じがします。

2009-12-03 (木)

圏論的Caty:ミニパイプライン

| 10:12 | 圏論的Caty:ミニパイプライン - 檜山正幸のキマイラ飼育記 を含むブックマーク

テンプレートの修飾子(モディファイア)とかフィルターとか呼ばれる機構の詳細仕様を詰めないままになってんですが、Catyスクリプトと同じモデルでいいや、と思いました。以下の記述は大ざっぱ、絵算を補ってください -- 色付き絵算とても良い練習問題

モデルとなる圏

Catyスクリプトと同様に、直積と直和を持ち、モナド類(モナド、コモナド、両モナド、それらの変形)をいくらでも作れる圏を背景に考えます。いくつか(任意個数だけど)の変数の値を保持する状態空間Vと、2つの例外クラスE, Fを固定します。

状態空間Vは、単一代入変数の集まりとします。精密に定式化するなら、問い合わせ余加群(readするAPI)と単一代入モノイドが作用する更新加群(updateするAPI)とかを使うけど、面倒なので、f:V×A→V×B という形の写像(背景圏の射)を使うことにします。fは、メインストリーム入出力 A→B 以外にVを読み、それを変更(要するに代入の副作用)した結果も返すとします。

Eは捕捉不可能例外のクラス(型)、Fは捕捉可能例外のクラス。例外クラスが2つある点は、通常Catyスクリプトより複雑です。

メインストリーム入出力が A→B である射は、f:V×A → E + F + V×B で表現され、適当な一般化クライスリ結合により一般化クライスリ圏を作ります。

例外ハンドリング

例外 E + F のうち、Fは捕捉可能です。例外ハンドラは、V×F → E + F + V×B という形の写像です。通常の射とまったく同じ形ですが、メインストリーム入力の型が例外型Fになっています。

例外ハンドラ h:V×F → E + F + V×B があるとき、H(f):E + F + V×B → E + F + V×B を次のように定義します。

  • H(h) := (E + h + V×B);α;[∇ + F + ∇']

めんどくさそうですが、絵算で描けば、Hは簡単なラッピング変換です。記号をだいぶ略記しているので説明すると:

  1. E + h + V×B の、EとV×Bは idE, idV×B のことで、+ は写像の直和です。
  2. したがって、E + h + V×B : E + F + V×B → E + (E + F + V×B) + V×B
  3. αは、E + (E + F + V×B) + V×B と (E + E) + F + (V×B + V×B) の同型を与える写像です。
  4. ∇はEの余対角、∇'はV×Bの余対角の略記。
  5. したがって、∇:E + E → E, ∇' : V×B + V×B → V×B

fがクライスリ圏の射、gがもとの圏の射のとき、fを元の圏に戻して考えた射とgが結合可能なとき、その結合を {f}g と書きましょう。f:V×A → E + F + V×B であり、h:V×F → E + F + V×B のとき、fとH(h)に関して {f}H(h) が作れます。([追記]← 少しウソが入っている、最後の追記を参照[/追記]

  • {f}H(h) : V×A → E + F + V×B

上記のごときプロファイルを持つ f, h に関して、{f}H(h) を例外処理コードと考えます。fがtryスコープで実行され、捕捉可能例外はすべてhに流されて、hの結果は再びメインスリトームに戻されます。端的に言えば、fが失敗したときhが代行してパイプラインを修復します。

事例

図式順結合の構文はパイプ記号「|」を使います。

  • 変数集合Vの利用例: {$article|noescape|nl2br}

noescapeは、データ処理は何もしないので、メインストリームでは恒等射です。しかし、変数の集合V内のエスケープ処理を「する/しない」のフラグを「しない」にセットします。パイプラインの最後で暗黙に起動されるレンダラーがこのフラグを参照します。

  • 例外処理の利用例: {$greeting||defautl:"hello"|toupper}

例外ハンドリングのところは便宜上「||」で示しました。実際の構文では同じ「|」で代用すると思います。パラメータはコロン「:」で区切ります。

変数参照 $greeting が Undefined例外(捕捉可能)を投げた*1ときは、例外ハンドラdefaultで処理され、パイプラインは継続します。$greetingが正常値を出力すれば、defaultはスキップされます。例外処理のtryスコープが明示されてませんが、「||」より左側が自動的にtryスコープになると思ってください。

恩恵

Smartyの修飾子とDjangoテンプレートのフィルターは、これで説明が付くでしょう。変数の読み書きと例外のthrow/catchができるので、ある程度のことはできます。Catyスクリプトの場合と同様に、型宣言が事前にあるなら、パイプラインの型安全性のチェックがだいたい静的にできます。フィルタープラグインの仕様も、このモデルに基づけばハッキリと記述できます。

[追記]

実際に絵算してみたら、結果は同じなんですが、途中は違ってました。fの実行の前に、Vをコピーしておかないと、fがVを壊してしまうかも知れません。で、Vを事前にコピーして、fが成功したときはコピーを捨てることにします。直積を右にまとめるため、V×A じゃなくて A×V を使います。また、# は足し算ですが、# の左は例外データ型、右は正常データ型とします。

上から下に処理や解釈が流れるとして、だいたい次のよう。

     A×V (入り口)
  ----------------------
    A×ΔV (Vをコピーする)
  ----------------------
    f×V (fの実行;バックアップしたVはそのまま)
  ----------------------
  (E + F # B×V)×V (fの実行結果)
  ----------------------
  (E + 0 # F + B×V)×V (例外を捕捉した)
  ----------------------
   E + 0 # (F + B×V)×V (分合律で掛け算を展開した)
  ----------------------
   E + 0 # F×V + B×V×V (分配律で掛け算を展開した)
  ----------------------
   E + 0 # F×V + B×V (右端のVを捨てた;fの成功ケース)
  ----------------------
   E + 0 # h + B×V (例外ハンドラーhの実行;fの失敗ケース)
  ----------------------
   E + 0 + (E + F # B×V) + B×V (hの実行結果)
  -------------------------------
  (E + E) + F # (B×V) + (B×V) (まとめ直すとこうなる)
  -------------------------------
     ∇ + F # ∇' (余対角の実行;場合分けの合流)
  ----------------------
    E + F # B×V (出口)

実際には、事前にVをコピー(バックアップ)しなくても、「失敗のときでもVを壊さないでね」とかの規約とモラルでなんとかなるような気がします。

[/追記]

*1:実装言語の例外が重いときは、ほんとの例外の代わりにアプリケーションレベルの規約を用いたほうがいいでしょう。

2009-09-04 (金)

分配法則を与える同型

| 17:04 | 分配法則を与える同型 - 檜山正幸のキマイラ飼育記 を含むブックマーク

「Catyとデカルト分配圏」より:

[追記]以下の記述で、間違いと説明不足がありました。とりあえず、「(b=> object {α: A, β: B} | c=> object {α: A, γ: C})」と書いてあったところを「(object {α: A, β: B} | object {α: A, γ: C})」に直しました。これで理屈の上のツジツマはあいます。が、実際には「(@b object {α: A, β: B} | @c object {α: A, γ: C})」じゃないと、実装上は不都合があります。そのへんの説明は長くなるので別な機会にします。[/追記]

こんな話に興味がある人はあんまりいない(つうか、説明がされてないから興味の持ちようがない)と思いますが。自分用メモとして。

分配法則をJSONの世界で考える

圏の分配法則の成立は、次の同型の存在で保証されます。

  • A×(B + C) → A×B + A×C (右からの分配法則もあります)

A, B, C は型だとして、デカルト積(直積)「×」はJSONのオブジェクト構成により、デカルト和(直和、余積)「+」は接頭辞(タグ)による場合分けで与えられるとします。そうすると、分配法則のJSON版は、次の3つの型のあいだに同型があることを意味します。

  1. object {α: A, δ: (b=>B | c=>C)}
  2. (object {α: A, β: B} | object {α: A, γ: C})
  3. (@b object {α: A, β: B} | @c object {α: A, γ: C})

1番目の型(JSONデータ領域)を2番目の型に移すスクリプトは次で与えられます。

[
  {getv α >: α},
  getv δ | {b=> {cat >:β}, c=> {cat >:γ}}
] | merge

ここで、catはUNIXのcatコマンドにちなんだ命名ですが、普通に考えると、何もしないコマンドにcatって名前もひどいもんだ、と思うので、pass にします。圏論風のidでもいいけど、「ユーザーID」とかと勘違いされそうだし。

pass を使って書き換えると:

[
  {getv α >: α},
  getv δ | {b=> {pass >:β}, c=> {pass >:γ}}
] | merge

Catyスクリプト構文や基本コマンド名は、これからもフラフラ変わるかもしれません(Kuwataさん、ごめんね)。

さて、(object {α: A, β: B} | object {α: A, γ: C}) という型は、「|」を直和と解釈すれば、集合論や圏論の観点からは特に問題ありませんが、プログラムによる処理では扱いにくいので、直和成分(direct summand)を区別するタグを付けて、(@b object {α: A, β: B} | @c object {α: A, γ: C}) としたいのです。

出力の一番外側にタグを付けるので、puttコマンドを最後に呼ぶことになります。putt b または putt c です。どっちを呼ぶかの情報を伝達する必要があります。いくつかの伝達方法が考えられるので、それについて述べます。

変数を使う

「set 名前 値」というコマンドで変数に値をセットできるとします。なにも珍しいことはないですよね。でも、setコマンドは、passコマンド(旧catコマンド)と同じように、入力をそのまま出力に流すとします。副作用として、変数のセットをするわけですね。セットした変数値は $名前 で参照できるとしましょう。

以上の仮定のもとで:

[
  {getv α >: α},
  getv δ | {b=> {set tag b >:β}, c=> {set tag c >:γ}}
] | merge | putt $tag

こうすると、次のどちらかのデータが出力されることになります。

  • @b object {α: A, β: B}
  • @c object {α: A, γ: C}

タグを直接操作する

タグが、実際は "$tag" という名前のプロパティにより実現されているという内部事情を使えば、次のようにも書けます。

[
  {getv α >: α},
  {getv δ | {b=> {pass >:β}, c=> {pass >:γ}},
  {getv δ | getv "$tag" >:"$tag"}
] | merge

見た目が醜いので、一見スジが悪そうですが、お化粧すれば悪い方法ではありません。型推論の観点からは、一番扱いやすい気がします。

単純JSONパス式を使って分岐する

もともと、タグによる分岐の構文は dispatch {tag1=> pipeline1, tag2=> pipeline2} のように、予約語dispatchを伴っていました。このdispatchを復活させましょう。ただし、dispatch (単純JSONパス式) という形で、単純パス式が指すデータのタグを見て分岐するとします。

すると、次のように書けます。

dispatch (δ) {
  b=> {getv α >:α, getv δ >:β} | putt b,
  c=> {getv α >:α, getv δ >:γ} | putt c
}

この方式のいいところは、(書き方によっては)出力されるJSONオブジェクトに近い形式で書けることです。

dispatch (δ) {
  b=> @b {α: getv α, β: getv δ},
  c=> @c {α: getv α, γ: getv δ}
}