計算機科学のための圏論

Haskell という関数型言語がある。 数学的には, monad とそれに関連した Kleisli category を用いている点が興味深い。

Kleisli category というのは, いつ誰が考えた概念かわからないが, Haskell の実装の中で重要な位置を占めているようである。Leinster の [Lei] では, Kleisli category の定義については, Mac Lane の [Mac98] のIV.5を見るように書かれている。

  • Kleisli category [Kle65]

arXiv で Kleisli category を検索してみたが, 3編の論文しか引っかからなかった。その内 Golubtsov と Moskaliuk の [GM] は information transfer への応用を扱ったものである。 Information transfer を category の言葉で表わしたとき, その多くは Kleisli category にある構造を入れたものみなすことができるようである。

David Spivak は, データベースのモデルとして, category と functor の言葉が有用であると主張している。[Spia; Spib; Spi12] など。他にも category theory をデータベースに使うことを考えている人はいるようである。 Majkic [Majb; Maja] など。

圏より基本的な構造として, quiver やその向きを忘れた graph がある。フローチャートを decorated quiver として考えたものとして, Dana Scott の [Sco71] がある。 Manin [Man13] は, computer science に現われるこのようなグラフと量子力学の Feynman diagram の類似性に着目し, 量子力学での renormalization を用いて computer science に現われる無限を renormalize しようとしている。

\(\lambda \)-calculus の一般化を考える際にも圏論的な構造が使われている。 Voevodsky は, “homotopy \(\lambda \)-calculus” という概念を考えているし, differential \(\lambda \)-category という一般化も考えられている。Manzyuk の [Man] とそこに挙げられている文献を見るとよい。

また, 計算機科学と関連の深い分野として数理論理学があるが, そこでは category と functor の言葉が重要な役割を果している。

Coecke と Grefenstette と Sadrzadeh [CGS] によると, 言語学におけるモデルで category と functor の言葉を使ったものもあるらしい。 それによると, Lambek が色々考えているようである。例えば, この論文など。

References

[CGS]

Bob Coecke, Edward Grefenstette, and Mehrnoosh Sadrzadeh. Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus. arXiv: 1302.0393.

[GM]

P. V. Golubtsov and S. S. Moskaliuk. Method of Additional Structures on the Objects of a Monoidal Kleisli Category as a Background for Information Transformers Theory. arXiv: math-ph/0211067.

[Kle65]

H. Kleisli. “Every standard construction is induced by a pair of adjoint functors”. In: Proc. Amer. Math. Soc. 16 (1965), pp. 544–546.

[Lei]

Tom Leinster. Homotopy Algebras for Operads. arXiv: math/0002180.

[Mac98]

Saunders Mac Lane. Categories for the working mathematician. Second. Vol. 5. Graduate Texts in Mathematics. New York: Springer-Verlag, 1998, pp. xii+314. isbn: 0-387-98403-8.

[Maja]

Zoran Majkic. Data Base Mappings and Monads: (Co)Induction. arXiv: 1102.4769.

[Majb]

Zoran Majkic. DB Category: Denotational Semantics for View-based Database Mappings. arXiv: 1103.0248.

[Man]

Oleksandr Manzyuk. Tangent bundles in differential lambda-categories. arXiv: 1202.0411.

[Man13]

Yuri I. Manin. “Renormalization and computation I: motivation and background”. In: OPERADS 2009. Vol. 26. Sémin. Congr. Soc. Math. France, Paris, 2013, pp. 181–222. arXiv: 0904.4921.

[Sco71]

Dana Scott. “The lattice of flow diagrams”. In: Symposium on Semantics of Algorithmic Languages. Lecture Notes in Mathematics, Vol. 188. Springer, Berlin, 1971, pp. 311–366.

[Spia]

David I. Spivak. Simplicial Databases. arXiv: 0904.2012.

[Spib]

David I. Spivak. Table manipulation in simplicial databases. arXiv: 1003.2682.

[Spi12]

David I. Spivak. “Functorial data migration”. In: Inform. and Comput. 217 (2012), pp. 31–51. arXiv: 1009.1166. url: http://dx.doi.org/10.1016/j.ic.2012.05.001.