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

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

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

参照用 記事

ストレージの線形代数: 泥臭いデータ操作の洗練された定式化

ここで言うストレージには、「メモリ内の単純な変数、リストやハッシュマップのようなコンテナ・データ構造、ファイルシステム、キー・バリュー・ストア、関係データベースなど」、データを蓄えるモノならなんでも含めます。一般的なストレージに対して、書き込みを行うオペレーションだけを考えます。今回は読み出しは考えません

ストレージと書き込みオペレーションの代数構造が線形代数と類似であることは何度か言及しました。例えば、「モニャドセミナー4の予定:トランザクション計算のフレームワークとか」(2009年7月)より引用:

副作用としての書き込み(メモリ/ストレージの更新)はモノイダル・スタンピング・モナドで定式化して、外部環境の参照(読み取り)は、その双対であるコモノイダル・スタンピング・コモナドを使って定式化します。書き込みのコミット操作は、モノイド作用(線形代数の用語では加群)で定式化します。計算処理の逐次実行は、クライスリ結合、余クライスリ結合、両クライスリ結合となります。

「カテゴリカル・モデリングに向けて」(2009年8月)より引用:

モナド概念を少し拡張すると、バッファフラッシュとかコミットまで取り込むことができます。拡張されたモナド概念をなんと呼ぶか僕は知らないのですが、線形代数加群に対応します(モナド多元環に対応します)。しょうがないのでモナド加群とでも呼ぶことにして; このモナド加群を使うと、モナドが状態空間に作用して、最終的に状態遷移を引き起こすところまで細かく制御できます。

「コンピュータ系実務者のための双対性(概略)」には、ストレージ更新(書き込み)と線形代数との対応表を載せています。このような対応は以前から意識はしていたのですが、エフイチ(一元体F1攻略のためにコンヌ&コンサニ(その他たくさんの人々)により定式化された足し算なし線形代数がうまく使えるようです。「エフイチのための道具立てが、計算科学/ソフトウェア工学にも有意義なんじゃないの」ということは「コンヌの挑戦とプログラムの代数」にも書きましたが、ストレージの線形代数はその実例です。

ストレージの操作は、技術者/プログラマにとってお馴染みの日常的行為です。線形代数を知っていれば*1、その知識を使ってストレージ操作の代数構造を把握することが出来るでしょう。

内容:

  1. 全体像と簡単な例
  2. 基礎となる可換モノイド
  3. ゼロの解釈
  4. 書き込みオペレーションのモノイド
  5. ストレージ状態空間と作用
  6. 代数構造のまとめと加群
  7. 自明な加群
  8. おわりに

全体像と簡単な例

まず全体の雰囲気をつかむために、「コンピュータ系実務者のための双対性(概略)」の表を、言葉使いを少し変えて*2再掲します。

ストレージ操作 線形代数
書き込みオペレーションのモノイド スカラーの体/多元環*3
ストレージ ベクトル空間/加群
書き込みオペレーション スカラー
オペレーションの連接 スカラーどおしの乗法
コミット ベクトルとスカラーの乗法
何もしないオペレーション スカラーの 1
矛盾を引き起こすオペレーション スカラーの 0
矛盾した(回復不可能な)状態 ゼロベクトル

以下、書き込みというのは、CRUD操作のうちの Create, Update, Delete のことだとします。CUDの全てが揃っていることは要求しません。Readを含めないところが本質的制約です。

ストレージに書き込みをする基本オペレーションの集合をΣとします。大文字シグマを選んだ理由は次のとおり。

  1. 形式言語理論では、言語のアルファベットをΣと書く習慣がある。基本オペレーションの集合は、自由モノイドの生成元集合という意味でアルファベットに他ならない。
  2. インスティチューション理論では、指標をΣと書く習慣がある。基本オペレーションの集合は指標と解釈できる。

実例を出しましょう。単純な整数変数をオブジェクトに仕立てたものをvとします。vは整数値を蓄えることができるのでストレージです。ただしvは、値がバインドされてない状態と、壊れてしまった状態を持つとします。vへの値の代入には、v.set(2) のようなsetメソッドを使い、値を未定義にするには v.unset() とします。vを壊す操作は v.destroy() とします。便宜上、何もしない操作(no operation)を v.nop() としましょう。

すると、ストレージvへの基本オペレーションの集合Σは次のようになります。

  • Σ = {nop(), destroy(), unset(), set(0), set(1), set(-1), set(2), set(-2), ....}

ストレージvの状態の集合は {undefined, 0, 1, -1, 2, -2, ..., bottom} です。undefinedは値が未定義の状態、bottom(どん底)はdestroyされた後の状態です。

ここから先、この簡単な例を説明に使います。ファイルシステムやデータベースのような本格的なストレージではどうなるか? それは皆さん考えてみてください。

基礎となる可換モノイド

通常の線形代数の基本概念達が、足し算なしの状況ではそれぞれ何に対応するか? 「いわゆる「一元体」の正体をちゃんと考えてみる」の表を引用しましょう。

足し算がある場合 足し算がない場合
アーベル群(乗法)
可換モノイド
多元環 (algebra) モノイド
加群 モノイド作用付き集合
アーベル群(加法) 集合

この表の「足し算がない場合」の欄では、吸収元(absorbing element)が考慮されてません。モノイドの演算を掛け算で書くなら、吸収元とはゼロのことです。

  • aが吸収元 ⇔ (任意のxに対して x×a = a×x = a)

以下、モノイドの吸収元は0で表し、ゼロと呼びます。ゼロ(吸収元)付きの場合を表に加えると:

足し算がある場合 足し算がない場合 ゼロ付きの場合
アーベル群(乗法) 0以外は逆元を持つゼロ付き可換モノイド
可換モノイド ゼロ付き可換モノイド
多元環 (algebra) モノイド ゼロ付きモノイド
加群 モノイド作用付き集合 ゼロ付きモノイド作用付きゼロ付き集合
アーベル群(加法) 集合 ゼロ(基点、ボトム)付き集合

ストレージの線形代数は、足し算なし線形代数の一種です。普通の線形代数(足し算あり線形代数)の基礎体(base field)にあたる代数系として、次のような掛け算「×」を備えた二元モノイド {0, 1} を使います。

× 0 1
0 0 0
1 0 1

{0, 1} から 0 を除くと {1} で、これはアーベル群です(自明ですけど)。以下、ゼロ付き可換モノイドとしての {0, 1} を B で表します。baseとbooleanから、B としました。

「コンヌの挑戦とプログラムの代数」では、Bに含まれる2つの要素を hang, skip、演算は逐次実行「;」としてもいいと述べました。

; hang skip
hang hang hang
skip hang skip

今回の実例では、hang, skip ではなくて、destroy, nop にしています。名前・記号なんてどうでもよくて、演算の構造が問題なのです。

  • B = ({0, 1}, ×, 1)
  • B = ({hang, skip}, ;, skip)
  • B = ({destroy, nop}, ・, nop)

どれでも同じです。名前・記号はなにか適当に決めた上で、Bを“基礎となるゼロ付き可換モノイド”として使います。

ゼロの解釈

「0」という記号で書くゼロには、ゼロ付きモノイドの要素であるゼロ操作と、ゼロ付き集合の要素であるゼロ状態があります。操作と状態が出てくるのは、計算/ソフトウェアの話だからです。

ゼロ状態は、ハング、クラッシュ、暴走、死んだ、壊れた、パニックのようなことです。要するに最悪の事態を表します。仕様ではまったく保証してない操作をした後の状態とも考えられます。例えば、開放してしまったメモリへの書き込みをしたとかです。開放してしまったメモリへの書き込みの直後に劇的な破滅は起こりませんが、もはや何が起こるか予測できない、不気味な状態になります。過激なクラッシュではないけど、やっぱり最悪の事態です。

ゼロ状態を引き起こすような操作がゼロ操作です。操作の逐次実行を掛け算記号で表すなら、0×x = x×0 = 0 、これは次のように解釈できます。

  • いったんゼロ操作をすると、その後で何をしようとゼロ状態から抜け出せない。
  • ゼロ操作の前に何をしてようがそれに関係なく、ゼロ操作は確実にゼロ状態を引き起こす。

ゼロ操作とゼロ状態、恐ろしいですね。

書き込みオペレーションのモノイド

以下、モノイドはすべてゼロ付きだと仮定して、いちいち「ゼロ付き」とは書きません。

Σが基本オペレーションの集合だとして、Σのオペレーションを有限個並べた(連接した)列の全体をΣ*とします。Σ*の連接演算は「・」で表します。εを空列とすれば、(Σ*, ・, ε)は自由モノイドですが、destoryやnopのような特別なオペレーションが前もって入っているときは、Σ*に細工をして、うまいことモノイドMを作ります。

ΣからMを作るやり方は気にしなくていいです。とりあえず「うまいこと作る」ということで*4。M(Σ*を多少加工したかもしれないが、ほぼΣ*)は、連接演算「・」と単位元「1」、ゼロ「0」でモノイド(ゼロ付きです)となりました*5

整数変数オブジェクトvの例で考えることにして、Σから作ったMの要素は、メソッド呼び出しの列になります。これを、[set(2), nop(), set(-1)] のようなリストで表現しましょう。演算「・」はリストの連接になります。[set(2), nop(), set(-1)]・[unset(), destroy()] = [set(2), nop(), set(-1)], unset(), destroy()] です。

この例で、単位元1は空リスト [] でも表現できるし、[nop(), nop()] のようなnop()だけのリストでも表現できます。基礎モノイドBは、Mに埋め込まれています。もっと正確に言えば、1 |→ [], 0 |→ [destory()] という対応が存在します。

書き込みオペレーションのモノイドMは、ストレージ操作API呼び出しの履歴、またはキューの集合だと理解するとよいでしょう。演算「・」は、履歴またはキューの時間順の連接です。

ストレージ状態空間と作用

基本オペレーションの集合Σは、ストレージ操作APIの仕様を与えます。Σから作ったモノイドMの要素は、API呼び出しの時系列を表し、履歴またはキューと解釈できます。しかしまだ、実際のストレージは登場してません。ストレージ自体は、「状態空間と作用」として定義されます。

Sをストレージの状態空間とします。整数変数オブジェクトvなら、S = {undefined, 0, 1, -1, 2, -2, ..., bottom} です。Sはどんな集合でもかまいませんが、ゼロ状態は特定されているとします。整数変数オブジェクトの場合はbottomがゼロ状態なので、0 = bottom です。

以下では、混乱を避けるため、モノイドMの要素をα、βなどのギリシャ文字小文字、状態空間Sの要素をx, yなどのローマ文字小文字とします。ゼロ操作もゼロ状態も0で表しますが、文脈で区別してください。(整数値の0もあるから少し混乱しそうですが、全部区別して書くのも欝陶しい。)

さて、x∈S と α∈M に対して、x*α という二項演算「*」を導入します。二項演算とは言っても、左は状態、右はオペレーション列です。演算「*」は、線形代数の(右からの)スカラー乗法に対応します。ここでは(右からの)作用(action)と呼びます。右からの作用にしたのは理由があって、結合律が素直に書けるようにです。次が作用に関する結合律、単位律、零律*6です。

  1. x*(α・β) = (x*α)*β
  2. x*1 = x
  3. x*0 = 0

作用 x*α は、オートマトンで言えば遷移関数 δ(x, α) のことです。つまり、状態xのときに、オペレーション(の記号)αを受け取って遷移する先が x*α です*7。結合律は、「オペレーション列を連接した後で作用させても、作用を順次に適用しても結果は変わらない」ことを主張しています。

代数構造のまとめと加群

今まで述べたことをまとめておきます。

基本書き込みオペレーションの集合Σから作った書き込みオペレーションのモノイド M = (M, ・, 1, 0) は次の性質を持ちます。α, β, γ∈M として:

  1. (α・β)・γ = α・(β・γ)
  2. 1・α = α・1 = α
  3. 0・α = α・0 = 0
  4. 基礎モノイドBからのモノイド射 B→M がある。
  5. ΣからMへの自然な写像 Σ→M がある。(a |→ [a] で与えられます。)

書き込みオペレーションのモノイドMは、ストレージ状態空間Sに演算「*」により作用します。x∈S、α, β∈M として:

  1. x*(α・β) = (x*α)*β
  2. x*1 = x
  3. x*0 = 0

以上のような性質を持つMとSの組み合わせ (M, S) を加群と呼びます。「加群」は線形代数の用語ですが、適当な言葉が見当たらない(あったら教えてください)ので、そのまま借用します。「SはM上の加群である」と言うこともあります。単なる集合としてのMとSではなくて、モノイド演算と作用による代数構造も込めて加群と呼ぶことに注意してください。

同じMとSに対して、複数の加群構造が入ることがあります。その例を次節で紹介します。

自明な加群

Sが基礎モノイドBの上の加群だとすると、その作用は一意的に決まってしまいます。B = {0, 1} ですが、x*1 と x*0 は単位律と零律で縛られているので、自由に決めることはできません。つまり、ゼロ付き集合Sが与えられると、自動的かつ一意的にB上の加群構造が決まります。

Bとは限らない一般のモノイドMでは、状態空間Sの加群構造が複数作れます。今、MがSに「・」で作用している状況(つまり、SがM上の加群)を考えます。別な(正確には、おそらくは別な)作用「#」を次のように定義します。

  • αが0でないなら x#α = x
  • x#0 = 0

「#」が、結合律、単位律、零律を満たすのはすぐに分かります。この作用「#」を自明な作用と呼びます。基礎モノイドB上では自明な作用しかありませんでした。一般のモノイドMでは、自明でない作用も存在するので、複数の作用(=複数の加群構造)を同時に利用できます。

普通の線形代数では、同時に複数の作用(スカラー乗法)を考えることはあまりないのですが、ストレージの線形代数では、コミット作用とキャンセル作用を同時に考えるのは普通のことです。

おわりに

これでだいたい、書き込みオペレーションとストレージの話を、多元環(代数)と加群の議論に並行して進める準備ができました。直和、テンソル積、ベース(係数モノイド)の取り替えなどの線形代数の概念を、ストレージに対しても同様に定義できます。バッファリング、トランザクションAPIエミュレーション、複合ストレージ、オペレーション例外の捕捉などを、線形代数の概念(とモノイドの性質)で説明することができます。

今までの議論は、ゼロ付き集合の圏(基点付き集合の圏)におけるモノイドと加群として理解できるので、圏論との相性が良い定式化になっています。圏論的な手法を利用する可能性も広がります。今回は足し算なしの状況で考えましたが、ベキ等な足し算を入れても面白いでしょう。

このような枠組みが突飛な発想に結びつくことは少ないと思いますが、設計や実装の堅実な背景にはなると思います。

*1:ベクトルや行列の計算技巧は一切不要で、多元環(代数)上の加群の定義を知っていることが重要です。

*2:「更新→書き込み、モナド→モノイド、リクエスト→オペレーション」と変えました。今回はモナドではなくてモノイドのレベルで話をします。

*3:僕は古風な用語「多元環」を使ってますが、「代数」が最近のメジャーな言葉です。

*4:「Σには、1や0を表す特殊なオペレーションを入れない」と約束しておけば、M = (Σ* + {0}) とすれば済みます。話を簡単にしたいなら、この方法がいいかもしれません。

*5:理論上は、モノイドMがΣから作られる必要性はありません。抽象的なモノイドMをいきなり与えても問題ありません。が、現実的には生成元の集合ΣをもとにMを作ると思います。

*6:吸収律と呼ぼうかと思ってたのですが、吸収律は束の公理にあるので、零律にします。

*7:ストレージもオートマトンも状態遷移系の一種です。状態遷移系は、多元環とその表現加群の類似として扱えます。