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

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

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

［参照用 記事］

メイヤー代数／メイヤー加群の圏

雑記／備忘

メイヤー代数の全体に、適切な準同型を定義して追加すると圏になること、また、メイヤー代数の圏の上にメイヤー加群のインデックス付き圏も定義可能なことをザッと説明します。

内容：

はじめに

メイヤー先生が提唱する「Command-Query分離された状態遷移系」の代数的な定式化はだいぶ以前から考えていたのですが、なんと呼べばいいかウジウジと悩んでいました。思い切って（勝手ながら）メイヤー代数と呼ぶことにしました（「メイヤー代数、メイヤー指標、メイヤーオートマトン」）。これで話がしやすくなりました。名前がないモノについて語るのは困難（ときに不可能）ですからね。

メイヤー代数の、僕にとっての主たる用途は、ファイルシステムやデータベース、メモリキャッシュなどのストレージシステムの定式化です。ストレージシステムはクライアント／サーバー型で、メイヤー代数はクライアント部分を記述します*1。ストレージサーバーまで含めた全体はメイヤーオートマトン（メイヤー加群）を使い記述します。アプリケーションプログラムから見える構造はメイヤー代数までで、メイヤーオートマトンは隠蔽されます。メイヤーオートマトンの知識を持つのは、ストレージのクライアント（サーバーへのリクエスタ）だけです。

メイヤー代数は、圏Cのなかで定義されます。この圏Cを背景圏と呼ぶことにします。背景圏を変えることによって、計算の部分性（無限走行）、例外、非決定性などを扱う（あるいは扱わない）ことができます。コンピューティングとは直接は関係のない圏、例えば実数体R上のベクトル空間の圏VectRを背景圏に選ぶこともできます。

メイヤー代数の背景圏としてどんな性質が必要でしょうか？ モノイドやコモノイドを定義したいので、圏Cはモノイド圏である必要があります。双代数法則の記述には対称性が必要です。よって、Cは対称モノイド圏となります。しかし、大域的な対称性の代わりに個別の対称性（台対象の入れ替え操作）があればいいので、非対称モノイド圏内でもメイヤー代数は定義可能です。例えば、自己関手圏内でメイヤー代数（関手的メイヤー代数）を定義できます。

非対称モノイド圏のなかのメイヤー代数の定義は複雑になるので、ここでは背景圏Cを対称モノイド圏だと仮定します。つまり、任意の対象X, Yに関して、入れ替え操作 σX,Y:X×Y→Y×X がいつでも自由に使えます。

それで問題は、背景圏Cのなかのメイヤー代数を全部寄せ集めて圏を作ることです。この圏（ができたとして）MeyerAlg(C) と書きましょう。メイヤー代数自体の定義は既にあるので、2つの（2つが同じでもいい）メイヤー代数のあいだの射を定義して、圏の公理を満たすことを確かめればいいわけです。

メイヤー代数の定義（復習）

背景圏を対称モノイド圏 C = (C, I, ×, σ) だとして、メイヤー代数の構成要素は次のものです（「メイヤー先生からモナド類似構造へ」参照）。

  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

適当に記号の乱用をしないと面倒でたまりません。M = (M, e, m, !, Δ) のように書き、各種の演算／余演算は同じ記号で表します。

メイヤー代数は、(M, V) という組で、Mは双モノイド、Vはコモノイド、さらにM（のモノイド部分）がVに作用している構造を持ちます。メイヤー代数特有の法則は、作用（スカラー乗法）aに関する双代数法則で、iは I×I→I in C の同型射として：

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

この法則は、双モノイドを定義する法則と形は同じですが、台対象としてMとVが混じっている点が異なります。作用aやその他の演算／余演算のストレージにおける意味は「メイヤー代数、メイヤー指標、メイヤーオートマトン」にまとめてあります。より基本的なことは「ストレージの線形代数： 泥臭いデータ操作の洗練された定式化」に書いてあります。

メイヤー代数の準同型の定義

メイヤー代数は双モノイドMとコモノイドVの組なので、(M, V)→(N, W) という準同型は、双モノイド射 f:M→N とコモノイド射 g:V→W の組、と考えそうですが（僕もそう考えた）、これだとちょっと使いにくいようです。

しばらく試行錯誤してみて、gの向きを逆にしました； g:W→V 。つまり、圏 MeyerAlg(C) の (M, V)→(N, W) という射は、双モノイド射 f:M→N とコモノイド射 g:W→V （向きに注意！）の組です。向きを逆転させた理由は後で説明するとして、f, gに関する条件を記します。まずは、

  • f:M→N は双モノイド射である。
  • g:W→V はコモノイド射である。

これだけではメイヤー代数の準同型（圏MeyerAlg(C)の射）にはなりません。作用（スカラー乗法）に関する条件が必要です。

準備として、f:M→N を使ってWをN加群とみなしましょう。WをN加群とみなした作用（スカラー乗法）をa'とすると、a':W×M→W は次のように定義します。

  • a' := (idW×f);a

このa'により、WはモノイドM（コモノイド構造は忘れる）上の加群となります。M上の2つの加群 (W, M, a')、(V, M, a) を考えて、gは次の条件を満たすとします。

  • g:W→V はM加群の準同型射となっている。

記号を節約するために、f = (f*:M→N, f*:W→V)、または f:(M, V)→(N, W) のように書くことにします。

メイヤー代数の圏と加群の圏

(M, V)、(N, W)、(L, U) がメイヤー代数で、f = (f*:M→N, f*:W→V):(M, V)→(N, W) と g = (g*:N→L, g*:U→W):(N, W)→(L, U) がメイヤー代数の準同型のとき、結合 f;g の定義はほぼ自明でしょう。

  • (f;g)* := f*;g* : M→L
  • (f;g)* := g*;f* : U→V

f;g が再びメイヤー代数の準同型射になることを確認する必要がありますが、特に難しことはありません。恒等射は、もちろん (idM, idV) で与えられます。

f*:W→V の向きがf*と逆なのは、加群の“引き戻し”がうまく定義できるようにです。メイヤー代数の準同型射の定義のなかで既に登場してるのですが、(N, W)上の加群Bを、(M, V)上の加群とみなすことを、加群の引き戻し、あるいは係数域の取り替えといいます。プログラミングでは、異なるインターフェース／プロトコルに対するアダプター／コンバーターになります。

Bが、(N, W)上の加群であるとは、作用（スカラー乗法）α:B×N→B と余作用（スカラー余乗法）δ:B→B×W があることです。このとき、f:(M, V)→(N, W)による引き戻し加群は次のように定義できます。

  1. α':B×M→B を α' := (idB×f*);α と定義する。
  2. δ':B→B×V を δ' := δ;(idB×f*) と定義する。

fによる引き戻しにより作られた(M, V)加群を f#B と書くことにします。

詳細は割愛しますが、メイヤー代数(M, V)上の加群の全体は圏をなすので、それを Module(M, V) と書くことにします。すると、メイヤー代数の射 f:(M, V)→(N, W) から誘導されたf#は、加群の圏のあいだの関手 f#:Module(N, W)→Module(M, V) となります。

圏MeyerAlg(C)上の対象（メイヤー代数ですね）(M, V)ごとに、圏 Module(M, V) が“生えている”構造になるので、メイヤー加群（メイヤーオートマトン）の全体はインデックス付き圏（indexed category）となります。もちろん、グロタンディーク構成により単一の圏（とファイバー構造）に直すことができます。

メイヤー代数の準同型の実例

コンピューティングとは別な例をだします。

Vを平面だとします。平面の点とその2次元座標 (x, y) を同一視します。Mは平面の平行移動 move(u, v) の全体とします。MのVへの作用を中置演算子・で表すとして、(x, y)・move(u, v) := (x + u, y + v) で定義します。Mは平行移動の順次合成でモノイド、コモノイド構造は対角と単元集合（一点）への自明な射で定義します。要するに2次元アフィン空間です。

同様に、Wは3次元空間、点とその3次元座標 (x, y, z) を同一視します。Nは3次元空間の平行移動 move(u, v, w) の全体とします。

f*:M→N は、 move(u, v)|→move(u, v, 0) と定義します。平面内の移動を、z座標を変えない空間内の移動にマップしています。f*:W→V は、(x, y, z)|→(x, y) という射影です。

f = (f*, f*) は2次元アフィン空間と3次元アフィン空間のあいだの構造を保つ写像になっています。ただし、通常のアフィン空間準同型とは違います。空間も平行移動群も埋め込むのではなくて、空間は射影しています。

メイヤー代数／メイヤー加群の守備範囲

メイヤー代数は、メイヤー先生の「Command-Query分離の原則」から出発しています。実際、Command-Query分離がされてないような状態遷移系はメイヤー代数／メイヤー加群でうまく表現できません。また、キャッシュのハンドリングが不十分なストレージ・クライアントもメイヤー代数の法則を満たしません。

頑張って「Command-Query分離の原則」を守るように作った状態遷移系／ストレージシステムだけがメイヤー代数／メイヤー加群で定式化できるのです。実際のところ、「Command-Query分離の原則」を守るのは難しいことがあるので、メイヤー代数／メイヤー加群よりゆるい構造が必要だとも感じます。でも、「Command-Query分離の原則」は色々な恩恵があるので、それを守るように頑張る価値はあると思います。

*1:クライアントとサーバーが別れてないシステムも、退化した形態として定式化できます。