A Categorical Model of State Transformations in Programming Languages

M. Kohútová; W. Steingartner; S. Novotný

doi:10.2478/jamsi-2026-0004

.blurhash-client-img { display: none !important; }

A Categorical Model of State Transformations in Programming Languages

Journal of Applied Mathematics, Statistics and Informatics

Volume 22 (2026): Issue 1 (May 2026)

By: M. Kohútová, W. Steingartner and S. Novotný

Open Access

|Jun 2026

Abstract

Formal semantics of programming languages represents a basic formal method connecting theoretical foundations of computer science with the development of reliable software. It allows for rigorous analysis of the correctness and properties of programs independently of the implementation. When formulating it, it is necessary to respect the principles of the programming paradigm, which determines the basic abstractions of the language. At the same time, there are unifying formalisms that allow for systematic comparison of semantic definitions across paradigms. Category theory represents one of the most important such approaches. We formalize this perspective by introducing a general categorical model of state transformations and show how different programming paradigms can be uniformly represented and related within this framework via structure-preserving mappings.

References

Awodey, S. 2010. Category Theory, 2 ed. Oxford Logic Guides, vol. 52. Oxford University Press, Oxford.
Search in Google Scholar Back to article
Baez, J., Li, X., Libkind, S., Osgood, N. D., and Patterson, E. 2023. Compositional modeling with stock and flow diagrams. Electronic Proceedings in Theoretical Computer Science 380, 77–96.
Search in Google Scholar Back to article
Barr, M. and Wells, C. 1990. Category Theory for Computing Science. Prentice-Hall, Inc., USA.
Search in Google Scholar Back to article
Bradley, T.-D., Terilla, J., and Vlassopoulos, Y. 2022. An enriched category theory of language: From syntax to semantics. La Matematica 1, 2, 551–580.
Search in Google Scholar Back to article
Cook, S. A. and Reckhow, R. A. 1973. Time-bounded random access machines. Journal of Computer and System Sciences 7, 4, 354–375.
Search in Google Scholar Back to article
Diskin, Z. and Kadish, B. 2003. Variable set semantics for keyed generalized sketches: Formal semantics for object identity and abstract syntax for conceptual modeling. Data & Knowledge Engineering 47, 1, 1–59.
Search in Google Scholar Back to article
Fiore, M. P., P, G. D., and Turi, D. 1999. Abstract syntax and variable binding. In Proceedings of the 14th Symposium on Logic in Computer Science (LICS 1999). IEEE Computer Society Press, Trento, Italy, 193–202.
Search in Google Scholar Back to article
Harper, R. 2016. Practical Foundations for Programming Languages, 2 ed. Cambridge University Press, Cambridge.
Search in Google Scholar Back to article
Hoare, C. A. R. 1969. An axiomatic basis for computer programming. Communications of the ACM 12, 10, 576–580.
Search in Google Scholar Back to article
Jacobs, B. 1999. Categorical Logic and Type Theory. Studies in Logic and the Foundations of Mathematics, vol. 141. North Holland, Elsevier, Amsterdam, The Netherlands.
Search in Google Scholar Back to article
Lawvere, F. W. 1963. Functorial semantics of algebraic theories. Proceedings of the National Academy of Sciences of the United States of America 50, 5, 869–872.
Search in Google Scholar Back to article
Mac Lane, S. 1998. Categories for the Working Mathematician, 2 ed. Graduate Texts in Mathematics, vol. 5. Springer, New York.
Search in Google Scholar Back to article
Mihelič, J., Steingartner, W., and Novitzká, V. 2021. A denotational semantics of a concatenative/compositional programming language. Acta Polytechnica Hungarica 18, 4, 231–250.
Search in Google Scholar Back to article
Milewski, B. 2021. Category Theory for Programmers. Blurb, San Francisco, CA.
Search in Google Scholar Back to article
Moggi, E. 1989. Computational lambda-calculus and monads. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS 1989). IEEE Computer Society Press, Pacific Grove, CA, USA, 14–23.
Search in Google Scholar Back to article
Mordecai, Y., Fairbanks, J. P., and Crawley, E. F. 2021. Category-theoretic formulation of the model-based systems architecting cognitive-computational cycle. Applied Sciences 11, 4, 1945.
Search in Google Scholar Back to article
Novitzká, V., Perháˇ, J., and Steingartner, W. 2019. Categorical approach to denotational and operational semantics. IPSI Transactions on Internet Research 15, 2, 45–51.
Search in Google Scholar Back to article
Pierce, B. C. 2002. Types and Programming Languages. MIT Press, Cambridge, MA.
Search in Google Scholar Back to article
Plotkin, G. 1981. A Structural Approach to Operational Semantics. Tech. rep., Computer Science Department, Aarhus University.
Search in Google Scholar Back to article
Plotkin, G. D. and Pretnar, M. 2013. Handling algebraic effects. Logical Methods in Computer Science 9, 4:23, 1–36.
Search in Google Scholar Back to article
Riley, M. et al. 2021. Category theory in computer science: Recent trends and applications. Bibliographic data unverified; replace with exact source before final submission.
Search in Google Scholar Back to article
Schmidt, D. A. 1986. Denotational Semantics: A Methodology for Language Development. William C. Brown Publishers, USA.
Search in Google Scholar Back to article
Scott, D. S. 1970. Outline of a mathematical theory of computation. In Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems. Department of Electrical Engineering, Princeton University, Princeton, NJ, 169–176.
Search in Google Scholar Back to article
Spivak, D. I. 2014. Category Theory for the Sciences. MIT Press, Cambridge, MA.
Search in Google Scholar Back to article
Steingartner, W. 2025. Perspectives of semantic modeling in categories. Journal of King Saud University Computer and Information Sciences 37, 19.
Search in Google Scholar Back to article
Steingartner, W. and Novitzká, V. 2017. Categorical semantics of programming languages. In Selected Topics in Contemporary Mathematical Modeling, A. Z. Grzybowski, Ed. 331. Publishing Office of Czestochowa University of Technology, Czestochowa, Poland, Chapter 11, 167–192. Series Monograph.
Search in Google Scholar Back to article
Steingartner, W., Novitzká, V., Bačíková, M., and Korečko, Š. 2017. New approach to categorical semantics for procedural languages. Computing and Informatics 36, 6, 1385–1414.
Search in Google Scholar Back to article
Steingartner, W., Novitzká, V., and Schreiner, W. 2024. Proof of equivalence of semantic methods for a selected domain-specific language. Journal of Applied Mathematics and Computational Mechanics 23, 2, 79–92.
Search in Google Scholar Back to article
Steingartner, W. and Schreiner, W. 2025. Executable Semantics for Teaching Concatenative Stack-Based DSLs: The Case of StackLang. In New Trends in Database and Information Systems, ADBIS 2025 Short Papers, Doctoral Consortium and Tutorials, Tampere, Finland, September 23-26, 2025, Proceedings, P. K. Chrysanthis, K. Nørvåg, K. Stefanidis, Z. Zhang, E. Quintarelli, and E. Zumpano, Eds. Communications in Computer and Information Science (CCIS), vol. 2676. Springer, Cham, Switzerland, 248–263.
Search in Google Scholar Back to article
Stoy, J. E. 1977. Denotational semantics : the Scott-Strachey approach to programming language theory. Series in Computer Science, No. 1. MIT Press, Cambridge, MA.
Search in Google Scholar Back to article
Tennent, R. D. 1986. Functor-category semantics of programming languages and logics. In Category Theory and Computer Programming, D. Pitt, S. Abramsky, A. Poigné, and D. Rydeheard, Eds. Lecture Notes in Computer Science, vol. 240. Springer, Berlin, Heidelberg, 206–224.
Search in Google Scholar Back to article
Winskel, G. 1993. The Formal Semantics of Programming Languages: An Introduction. Foundations of Computing. MIT Press, Cambridge, MA.
Search in Google Scholar Back to article
Zhao, H., Chen, Y., and Fu, X. 2023. Comparison of machine learning based on category theory. Journal of Web Engineering 22, 1, 41–54.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/jamsi-2026-0004 | Journal eISSN: 1339-0015 | Journal ISSN: 1336-9180

Journal RSS Feed

Language: English

Page range: 67 - 80

Published on: Jun 6, 2026

Published by: University of Ss. Cyril and Methodius in Trnava

In partnership with: Paradigm Publishing Services

Keywords:

General Terms: Category Theory,

Denotational Semantics,

Formal Semantics,

State-Based Models,

Domain-Specific Languages,

Imperative Languages,

Stack-Based Languages

Related subjects:

Mathematics,

Applied mathematics

© 2026 M. Kohútová, W. Steingartner, S. Novotný, published by University of Ss. Cyril and Methodius in Trnava
This work is licensed under the Creative Commons Attribution 4.0 License.

Volume 22 (2026): Issue 1 (May 2026)