計算機科学のための圏論

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

• Wikipedia の記述

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

• Kleisli category [Kle65]

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

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

Spivak は [Spia] で lens という構造を考えているが, これもデータベースの理論で登場した概念のようである。

• lens

Foster ら [Fos+07] により導入されたようであるが, Spivak 以外にも, Clarke ら [Cla20; Cla21; Cho+22; Cla] が圏論的構造を調べている。

圏より基本的な構造として, 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 [CGS13] によると, 言語学におけるモデルで category と functor の言葉を使ったものもあるらしい。 それによると, Lambek が色々考えているようである。例えば, この論文など。

最近でも, differential category などの新しい圏論的構造が導入されている。

• differential category

References

[CGS13]

Bob Coecke, Edward Grefenstette, and Mehrnoosh Sadrzadeh. “Lambek vs. Lambek: functorial vector space semantics and string diagrams for Lambek calculus”. In: Ann. Pure Appl. Logic 164.11 (2013), pp. 1079–1100. arXiv: 1302 . 0393. url: https://doi.org/10.1016/j.apal.2013.05.009.

[Cho+22]

Emma Chollet et al. “Limits and colimits in a category of lenses”. In: Proceedings of the Fourth International Conference on Applied Category Theory 2021. Vol. 372. Electron. Proc. Theor. Comput. Sci. (EPTCS). EPTCS, [place of publication not identified], 2022, pp. 164–177. arXiv: 2105.05422.

[Cla]

Bryce Clarke. Delta lenses as coalgebras for a comonad. arXiv: 2108. 00390.

[Cla20]

Bryce Clarke. “Internal lenses as functors and cofunctors”. In: Proceedings—Applied Category Theory 2019. Vol. 323. Electron. Proc. Theor. Comput. Sci. (EPTCS). EPTCS, [place of publication not identified], 2020, pp. 183–195. arXiv: 2009 . 06835. url: https://doi.org/10.4204/EPTCS.323.13.

[Cla21]

Bryce Clarke. “A diagrammatic approach to symmetric lenses”. In: Proceedings of the 3rd Annual International Applied Category Theory Conference 2020. Vol. 333. Electron. Proc. Theor. Comput. Sci. (EPTCS). EPTCS, [place of publication not identified], 2021, pp. 79–91. arXiv: 2101.10481. url: https://doi.org/10.4204/EPTCS.333.6.

[Fos+07]

J. Foster, Michael Greenwald, Jonathan Moore, Benjamin Pierce, and Alan Schmitt. “Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem”. In: ACM Transactions on Programming Languages and Systems (TOPLAS) 29.3 (2007), p. 17. url: hal:http://hal.archives-ouvertes.fr/inria-00484971/en/;%20http://hal.archives-ouvertes.fr/docs/00/48/49/71/PDF/lenses-toplas-final.pdf.

[GM02]

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”. In: Hadronic J. 25.2 (2002), pp. 179–237. 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. Generalized Lens Categories via functors \(\mathcal {C}^{\rm op}\to \mathsf {Cat}\). arXiv: 1908.02202.

[Spib]

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

[Spic]

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.