On Understanding Code -- The Algebraic Structure and Interpretation of Computer Programs

What is the meaning of a computer program? As a naive approach, we can run the compiled code and see what it does. A more informed answer would involve looking at the machine code that the reference compiler generates. Ultimately, we want a precise mathematical definition of the semantics of a programming language.

In this talk, we will discuss a special case of denotational (and functorial) semantics. We assign abstract algebraic structures to language features. In particular, we use typed semigroups (semigroupoids/semicategories) to represent computation. This choice is due to the existence of hierarchical decomposition algorithms for these objects. The payoff is a detail-on-demand modular structure facilitating abstraction - the hallmarks of a cognitive tool for understanding. Decomposing a programming language implies the possibility of semi-automated systematic ways of understanding all the programs written in that language. To realize this enormous benefit, we need a special language. We revived and adapted to our purposes a mostly forgotten concatenative functional language originally designed for philosophical purposes. The main idea in the Joy programming language is that the syntactic concatenation of tokens has a morphism into the semantic composition of functions. In the Con-Cat language, we extended this idea to connect it with algebraic automata theory, most notably with the Krohn-Rhodes theory of decompositions. This project is an application of the morphic theory of understanding presented at IOCPh 2025.

By mathematizing the process of understanding computer programs, we aim to maintain and deepen our human knowledge about computation.
Imagining computational processes initiated by formal language expressions is an epistemological challenge. With the progress of agentic AI coding, overcoming this difficulty becomes crucial for retaining human agency.

Links and References

https://codeberg.org/egri-nagy/con-cat - The Git repository of the developed programming language. Documentation also includes a mirror of the unpublished papers on the Joy programming language.

Abelson, H., Sussman, G. J., Sussman, J. (1996). Structure and Interpretation of Computer Programs, Second Edition. MIT Press. - The legendary Lisp programming textbook that put emphasis on the core ideas. The subtitle of this talk is a homage to this book and an indication of our algebraic approach.