A Categorical View of Programming

The purpose of this document is to outline my thoughts on how programming works on a fundamental level. These insights have taken shape over several years, mostly driven by thinking that there must be a better way of doing things, then spending hours of my free time searching for. As a consequence, this document is a sort of synthesis of several ideas from computer science and mathematics developed over countless years by several brilliant people, with a few of my own ideas mixed in on the future of the industry.

My views here are influenced by several others in the field whose blog posts, lecture videos, papers, and repositories have influenced my views. I can't list all of them since I wasn't tracking them before now, so I'm certain I've missed some of them. I'm certain there's many more people working on related problems who I've never heard about, or other aspects of computer science I've never heard of; if anyone has any insight there I'd much appreciate some references.

Motivations

The Act of Programming

Levels of Programming

Most of the time spent physically writing code (in implementation) is spent doing some combination of the following:

Moving data from one location to another.
Building structured data.
Accessing some component in structured data.
Updating some component in structured data.
Interpreting structured data.
Parsing data

The closest prerequisite to the code is building up a mental model of the data and the execution flow, which comes from some combination of the following (dependent on the project):

Reading the documentation.
Looking up examples.
Experimenting with the data to see what actually works and what doesn't.
Reading the source code of the dependencies.

The next prerequisite up from that is designing a system that solves the problem you're working on, which requires some combination of the following:

Knowledge of design patterns.
Knowledge of what is and isn't possible at this time regardless of programming language and dependencies of choice.
Knowledge of what is and isn't difficult to do in your programming language and dependencies of choice.
Knowledge of component problems and the existing solutions to those.
Knowledge of when to choose one solution or design pattern over another.

The final prerequisite is actually knowing the problem you want to solve, which requires the following:

Specification of the problem at hand.
Domain knowlege, which can be of arbitrary complexity.

Potential Problems

Each stage has it's own problems that can arise over time:

Implementation
- It doesn't run fast enough.
- It isn't memory efficient enough.
- It isn't flexible enough for what the user wants to do.
- It doesn't give the correct result.
- Something that was thought to be correct and consistent breaks when a dependency is updated, either introducing a new bug or fixing one where the implementation depended on incorrect behavior.
Mental Model
- Subtlely incorrect model of execution flow.
- Documentation being non-existant, out of date, or outright wrong.
- Dependencies behaving inconsistently because each dependency (and all their transitive dependencies up the tree) have their own versions of these problems.
- Something that was thought to be stable and consistent turns out to be inconsistent in very specific cases.
Design
- Missing information on what design patterns are available, requiring either research to obtain that knowledge or ad-hoc attempts at solving it brute force through implementation.
- Missing knowledge of what isn't possible, leading to wasting time either researching a solution, or worse, trying to build a solution to an impossible problem from scratch.
- Missing knowledge of what is difficult and what is easy to do, leading down paths that can take far longer to implement and yield a worse solution than a simpler one.
- Forcing a particular solution or design pattern to solve a problem it doesn't actually solve, making a real solution even more difficult to implement.
Knowing the problem
- Inconsistent or conflicting requirements for the solution.
- Vague specification of the problem at hand.
- Missing domain knowledge, which can happen whenever:
  - The client assumes the implementer has all of the prerequisite domain knowledge.
  - The client assumes the implementer knows where to access the prerequisite domain knowledge.
  - The client only has partial domain knowledge themselves.
- Domain knowledge and best practices change over time.
- Requirements change over time.
- Processes change over time.

Relationships Between Levels

These levels are typically seen as hierarchical, but the truth is that none of them exist in a vacuum:

The implementation influences the mental model providing feedback on what will and will not work, while the mental model influences what gets tried for implementation.
The mental model influences design because the design has to be encoded into the mental model, while the design influences the mental model as the problem must be broken down into manageable chunks.
The implementation influences the design because some designs are simply not as efficient as others, while the design dictates the overall structure of the program.
The design influences knowledge of the problem because it will eventually force a thorough exploration of the solution space (which in turn requires thorough knowledge of the problem), and knowledge of the problem influences the design because as more knowledge is gained more designs can be ruled out and it may require more scaleable designs or the invention of entirely new designs.
The mental model influences knowledge of the problem by forcing the consideration of different possibilities, while knowledge of the problem influences what those possibilities are that the mental model must encode.
The implementation influences knowledge of the problem by opening up new possibilities due to the structure of the program (ie. more flexible implementations allow for a greater scope, prompting to consult whether or not that greater scope can be encountered in the context of the problem), and knowledge of the problem influences the overall direction the implementation must go.

An astute reader will notice that there are actually parallels to this in any profession, meaning that this is actually the core of what experience is: how much of this knowledge has someone already accumulated, and how can they apply it in a different context.

Back to the case of programming, a developer must have at least some understanding of each level before they can even begin working on an implementation. Almost all first implementations are guaranteed not to work exactly as planned, sometimes in obvious ways (eg. failing to compile or run at all), sometimes in subtle but limited magnitude ways (eg. failing to send an overnight email the day of a time zone change), and sometimes in subtle but potentially catostrophic ways (eg. off by 1 errors corrupting some records in a database table but not others, with no way to consistently detect which is which).

As far as I'm aware, there's no real scientific study analyzing the frequency of these errors or their magnitude, so for the purpose of this document I'm effectively going to consider them to be probabilistic where less experienced developers are more likely to make errors than senior developers. This is important because people will make mistakes which sometimes wind up in production, which will ultimately cause the start of this process all over again with this new problem. This ultimately means the following:

Mistakes can compound, forcing more cycles through the process than anticipated.
An entirely different solution must be implemented.

There are also the additional constraints of time and budget, which can result in cutting corners in areas they really shouldn't be cut. Ultimately this practice will just cause even more time and money to be spent fixing what should have been correct in the first place.

The kicker is that all of this is before you do anything actually interesting with it (ie. your business logic, and why your building the system in the first place).

Errors and Exploits

Building a system incorrectly gives rise to errors, some of them program errors, others logic errors, but all of them give rise to flaws in the system. These flaws can range in size:

This isn't even close to the number of medium to high profile bugs and exploits over the years, nor is it even close to some of the most severe ones. The points I want to get across here are the following:

There is no real way to find and fix all mistakes and bugs in any given program, since some of these have existed for several years. Testing helps to mitigate the possibilities, but it can only show the presence of bugs, not their absence.
- The closest we have to proving the absence of bugs to my knowledge is proof assistants and dependently typed languages like Coq, Agda, and Idris, but in general with any Turing complete language it isn't possible to determine the total absence of bugs for any arbitrary program.
The causes of these issues at first glance are varied but they all tend to be rather innocuous:
- Something can't be found.
- Performing a basic optimization to check if something is currently loaded or not.
- Reusing an existing component.
- Displaying incorrect messages to the user.
- Automatic updates are sent out, and someone obtained unauthorized access to the update server compromising it.
- Displaying all information, even when only some of it is necessary.
- Providing a convenient way of referencing something else and automatically loading it.
- Using a third party service.
- Suspected drive-by download and social engineering.
- A content update that caused a mismatch in input count.
- Allegedly outsourcing site development, with a lack of proper review.
- Hardware optimizations.
- Assuming arguments are at least a minimum size and writing to it.
The effects when a bug is encountered or an exploit is realized do not correlate to the human perceived relevance of its cause. In other words, each of these could be considered a minor issue in isolation until it actually occurs, where it could suddenly turn disastrous.
The frequency of these issues is increasing, not decreasing.
A lot of these are caused by some combination of the following:
- Dependencies written by someone else existing in a larger system.
- Part of the program being written by someone who doesn't actually understand all of the details about something.
- Unwritten assumptions.
- Unknown dependencies.
- Unknown limitations.
Software is ultimately becoming more complex and more interconnected over time, which will only trend upward.

One of the biggest unwritten assumptions in software development is that it is the responsibility of the programmer to fully understand exactly what the machine is doing at all times and from all perspectives. Based on the evidence above, this mindset is ultimately harmful, unsustainable, and quite frankly impossible to uphold. Ultimately this is because:

It's simply not possible to predict all the ways the code you write today will be used now and in the future.
Turing completeness is everywhere, where the more complex the system is, the higher probability it is that the system is Turing complete.
Systems are becoming more complex, both internally (dependencies) and externally (integrations with other systems).
The field itself is enormous, it's not just "writing a program that works" anymore, it's "writing a program that works AND is always available AND is secure from known threats AND is easy to use AND is always accessible to everyone AND integrates with external services AND..."
- I want to elaborate that my problem isn't that these things shouldn't be there, it's that these fields are both very wide and deep in content and knowledge: building up the prerequisite knowledge to do everything in the best possible way would require decades of work, let alone building such a system.
Programming is not done in isolation anymore: even in cases where something is written entirely by one person, they still rely on dependencies and transient dependencies written by others, sometimes written years ago by someone who may no longer be around.
- This is actually the most important point in this regard: every additional developer is an additional node in the network, with some knowledge redundencies, some knowledge impedence mismatch, and some knowledge gaps.
As programming work becomes more interconnected, the complexity is going to increase exponentially.
Generative AI is all the rage now, which means some people will use it for programming. I guarantee that not every line of code generated in this manner will be reviewed, and because these AIs are really good at generating a lot of content but not so good at generating well formed programs/fragments free of errors, all of these problems will become exacerbated in the future.

If not changed, this mindset will keep programming exactly where it is and where it has been for the past 50 years: reinventing the same patterns and mistakes over and over again. The solution to this is of course finding a better way to manage this complexity: instead of relying on human responsibility (which is falliable at the best of times let alone the worst), designing a system that abstracts over the complexities of programming.

But what would such a system look like? To find this out, we need to understand the core of what programming actually is.

TODO: Expand on this

The paradoxes of programming

Reuse vs. Robust

TODO: Relocate this

Additionally, we live in a world where the success of any given service is defined by how many services it integrates and how well it does so, with each of those systems having their own tech stack and the unknowable number of errors that could happen with them. With the rise of generative AI, companies are looking to integrate it more into code production, and though it has been trained on more information than anyone could possibly consume in one hundred lifetimes let alone a single one, it is prone to "hallucinations," which can produce incorrect code, or even worse, technically correct code with gaping security flaws in it.

There are also many who would take advantage of these flaws, some of them rather benign (someone exploiting a game for a speedrun), some of them outright malicious (exploiting an online system to obtain contact and financial information), and some of them seemingly fine until they suddenly aren't (a developer doing a neat trick dependent on a bug in a dependency to implement a feature, only for that bug to be fixed which breaks the downstream implementation). And with the break neck speed everything progresses at in tech, it is impossible for everyone to keep up.

Mindset

The core idea I want to focus on is the essence of programming and finding a universal way to structure and organize programs, and from there automate more of the process of building programs than ever before.

This may seem impossible with the vast quantity of programming languages and frameworks out there, but at its core programming has roots in mathematics, meaning that any universal way of constructing and manipulating programs will ultimately be rooted in the foundations of mathematics, of which I think the branch of Category Theory makes an excellent candidate.

Programming Language(s)

As I want to focus on a universal way to construct and manipulate programs, this solution must work for any given programming language. General purpose programming languages have the property of undecidability as a consequence of Turing completeness, while several systems based on Category Theory are provably decidable and are therefore not Turing complete.

Ultimately there are some constructs that general purpose programming languages allow that will not be reproducible in a system based purely on Category Theory. Likewise, any program constructed to conform completely to concepts from Category Theory will, assuming correct implementation, not be Turing complete. This is actually a good thing, because the additional constraints make the output of such a program deterministic and prevents cases of arbitrary code execution.

Ultimately I want to focus on the general concepts behind programming, rather than any particular language or implementation. When programming languages are brought up, I primarily want to demonstrate what the concept looks like under a particular paradigm.

Libraries and Frameworks

As with programming languages, I want to focus on the nature of programming itself rather than any particular library or implementation. The difference between these that I want to note is that frameworks tend to implement other execution models than those natively supported by the host programming language, so libraries can be viewed as similar to an embedded domain specific language.

Foundations

I want to quickly review some of the foundational concepts in computer science and mathematics before delving into the meat of what I envision, as any attempts to progress the field must eventually address these anyway.

Execution Models

Eventually all programs must execute in accordance with some sort of semantics, called an execution model. There are several possible execution models, though at this time the most targeted by general purpose programming languages are variants of the Von Neumann architecture, which has the following properties:

Variables as memory addresses
One instruction is processed at a time
Data must be marshaled between storage and processing

This model initially arose as a hardware architecture to allow reprogrammable machines, although many programming languages use it as a base execution model even when they're targeting a custom virtual machine (the most common being stack based virtual machines). However, this model has many problems, as noted by John Backus in his 1977 ACM Turing Award lecture.. I want to take a moment to point out the age of this document, at the time of this writing it is 47 years old, and many of the flaws mentioned therein about programming languages at the time are still valid today, and the solutions proposed are remarkably similar to the changes that are slowly trickling into mainstream programming languages. The point I want to make here is that these ideas aren't anything new, they've been around for a long time.

In any case, one particular artifact of this model that I have noticed is the difference between referential equality and object equality, with most languages opting for the default equality operator, ==, to mean referential equality (ie. for non-primitive types they are only recognized as equal when they refer to the same object in memory), simply because it's easier. Ultimately, I believe this leads to some combination of the following:

Non-standardized equality comparisons (eg. == vs isEqual() vs. equals() depending on language and dependency choices)
Manual comparison of all the components of a non-primitive type
Primitive obsession
Inconsistencies in the codebase when more than one developer is involved, when development takes years to complete, or during ongoing maintenance caused by the above issues

The root of my problem with the above is that this ultimately comes down to attempting to satisfy two different and sometimes conflicting motivations when building software: performance vs. abstraction. On one hand, you need the notion of referential equality when working on the lower abstraction levels, particularly when optimizing. On the other hand, you need the notion of object equality whenever you're attempting to perform some complex domain-specific logic, or whenever you're building a higher abstraction level. Problems arise when you mix these two notions, for example:

You think you're working on one
Junior developers don't know the difference between the different notions of equality, and just use the most well known and convenient one (typically ==).
You're refactoring an existing system to be more abstract (eg. == -> equals()).
You're optimizing an existing abstract system (eg. equals() -> == for internal operations).

To clarify, the bigger problem here is that the notion of referential equality exists as an artifact of the underlying execution model, in this case the Von Neumann architecture. This means, ultimately, that the underlying execution model is a leaky abstraction, one that most mainstream programming languages fall victim to because there is no structured and language enforced way to enforce the separation between different abstraction layers. Without such structure and a way to enforce it, there can be no true separation of an algorithm and its implementation (at least not without a ton of engineering work, which may very well be infeasible for a given project).

One last point I want to bring up here is that this problem will exist regardless of the underlying execution model. We don't live in an ideal world, and we have to make trade offs to deal with constraints, the underlying execution model and the hardware it runs on just being one example of this. There are alternative models that could be used, and hardware that could efficiently handle them, though existing programs that push the boundaries of performance may very well be incredibly inefficient running on that hardware. This is what I mean by true separation of an algorithm and an implementation: the algorithm is what happens on an abstract level (what you are doing), and the implementation is what runs under a given execution model (how you are doing it).

Below is a list (albeit incomplete I'm sure) of alternative execution models, some of them Turing complete (and therefore potential general computer architectures in the future) and others not (either specialized computer architectures or VM targets):

Petri nets (not Turing complete)
- Extended Petri nets are the Turing complete variants.
Rules engines
Rewrite logic can be either Turing complete or incomplete.
Untyped Lambda calculus (Turing complete)
- Typed Lambda calculus includes both Turing complete and incomplete variants.
Formal logic (Turing complete)
- Also see the Curry-Howard correspondence (proofs as programs).
S-expressions (Turing complete)
Combinatory logic (Turing complete)
Actor model (Turing complete)
Graph execution
Cellular Automata can be either Turing complete or incomplete.
Finite State Machines (not Turing complete)
Pushdown automata typically not Turing complete, but employing multiple stacks can make one Turing complete.

Type Theory

Algebraic Data Types (ADTs)

Product Types

Sum Types

Dependent Types

Category Theory

Isomorphisms

Functors

Natural Transformations

Algebraic Structures

Monoids

Monads

Categorical Representations of ADTs

Categorical Product

Categorical Coproduct (Sum)

Recursive Categories

Recursive Definition

Instance

The Yoneda Lemma

Programming From a Categorical Lens

Type Category

Polymorphism

Dependency Categories

Module Dependency

Data Dependency

Data Flow Category

Semantics Category

Syntax Category

Execution Categories

Static or Compile Time Category

Runtime Category

The Act of Programming

Graph Traversal

Refactoring Category (Isomorphism + Functor)

A Categorical Model For Programming

Isomorphism Categories (Abstract Data Types)

Homset Morphisms (Morphisms Between Abstract Data Types)

Relating Back to Programming Paradigms

Procedural

Object Oriented

Design Patterns

Functional

Logic

A Potential Future for Programming

Abstract Algorithm Categories

Implementation Categories

Compilation Categories

Abstract Algorithm -> Implementation Functors

Implementation -> Abstract Algorithm Functors

Optimization Categories

Graph Pathfinding

Automated Graph Traversal

Implementation Selection

Automated Optimization

Category <-> Code Isomorphism

Code Generation From Categories

Category Generation From Code

Online Categorical Repository/Database

Partial Library Useage

Function Level Versioning

Static Paths for Consistent Builds

Universal Standardized Security Updates

Universal Optimization Updates

Graphical Composition of Data and Algorithms

Why Generative AI Is Not Enough

Existing Tools and Resources

Below is a work in progress list of tools and resources I have found that can be useful in implementing such a system, either directly or serving as inspiration.

I haven't had time to properly read or test all of these myself, and a good portion of them I've only made it partway through, so this is more of an exercise in getting an idea of what already exists in this area and tracking the topics I'm at least aware of for future reference. I'll be expanding on this list as I find links and papers I've downloaded on my laptop and phone.

Open Source

JetBrains Meta Programming System (MPS) - A programming language workbench for designing domain specific languages. Allows direct manipulation of the Abstract Syntax Tree through projectional editors, with some examples being plain text and diagrams. Allows code generation targeting other languages.
- Implementation (bootstrapping)
Maude - A reflective programming language based on equational reasoning and rewriting logic. Comes with several proof and verification tools that have been applied in several domains.
- C++ implementation
A Categorical Programming Language (by Tatsuya Hagino - 1987) - Paper that outlines a Categorical Specification Language, Categorical Data Types, and lastly a Categorical Programming Language.
- Interpreter written in Haskell
Categorical Databases and CQL - A data schema and language designed with applied category theory for moving data from one location to another.
- Java implementation
- Haskell implementation
CHARITY - A categorical programming language based on strong categorical datatypes, allowing both inductive datatypes and coinductive datatypes.
- C implementation (now archived)
- OCaml implementation
Flat - A compact binary data format based on choice and sequence operators. Acts as a primitive for serializing algebraic data types, but lacks the ability to distinguish between different types of the same shape.
- Specification paper
正名/ZM/Zhèng Míng - Algebraic data type serialization and deserialization built as a layer on top of Flat. Allows detection between different types with the same shape, though it doesn't have any built-in types (all types must be explicitly defined, including primitives), type definitions cannot be mutually recursive, and it doesn't support serialization of higher kinded types.
- Specification paper
Type Oriented Protocol - Networking layer on top of 正名/ZM/Zhèng Míng and Flat. Allows the construction of type channels to send and receive binary representations of algebraic data types across a network.
- Specification paper
Idris - Purely functional programming language with dependent types. Supports multiple code-generation backends, compiling to Chez Scheme by default but supports targeting other languages such as Racket, JavaScript, C, and allowing custom code-generation backends.
- Implementation (bootstrapping)
Agda - Another dependently typed programming language that can also be used as a proof assistant. Like Idris, it supports multiple code-generation backends, namely GHC and JavaScript.
- Haskell + Agda implementation
Coq - Mathematical proof assistant and functional programming language.
- OCaml + Coq implementation
DisCoPy - Python toolkit for implementing string diagrams.
- Python implementation
- Docs
Lawvere - A categorical programming language with effects that offers an interpreter written in Haskell, an experimental compiler targeting JavaScript, and another compiler targeting a Categorical Abstract Machine.
- Of interest, all data is modeled as arrows (equivalent to functions), with primitives starting from the unit type.
Apache TinkerPop™ - Graph computing framework supporting several graph databases and multiple programming languages.
- Java implmentation
Enso - A hybrid programming language aiming to support both textual and visual representations.
Hydra - A DSL for program generation based on algebraic property graphs. The objective appears similar to the perspective of this document.
EdgeDB - Markets itself as a graph-relational database that attempts to combine the best aspects of relational databases and graph databases while fixing the composability problems of SQL via sets.
- Python implementation
Program Transformation Wiki - A huge repository of resources on program transformation.
nLab - The wiki to go for category theory, type theory, topology, and many other topics in mathematics and science.
- Of particular interest is the computational trilogy page, which posits that the domains of computation, formal logic, and ∞-category theory are three different perspectives of the foundations of mathematics.
Programming Language Theory λΠ - An aggregation list of resources on learning topics in theoretical computer science.
Category Theory for Programmers Blog - Bartosz Milewski
- Unofficial PDF version
- YouTube Lectures
From design patterns to category theory - An excellent series of articles by Mark Seemann relating patterns from Object Oriented Programming to concepts in Category Theory.
Wikifunctions - A new project by the Wikimedia Foundation, its purpose is to provide an open repository of executable functions open for anyone to compose and run.
- List of all currently available functions.

Closed Source

DMS® Software Reengineering Toolkit™ - Multi-language compatible code analysis and transformation tool allowing source-to-source transformation.
- Although it is closed source, there are several resources on that page and other pages on the site that are open, including a bibliography page with many additional links.
Waylay Rules Engine -
- Article explaining the reasons for the engine, linking to several articles on the subject and the documentation.
Matterbeam - Abstracted ETL-like application designed to separate data producers from consumers, using an immutable data stream where producers can publish to a generic store and consumers read from that generic store. Every operation is a transformation, with intermediate steps stored in the data store as well, so it effectively works as an abstracted state monad layered overtop of data sources.
- Whitepaper explaining the motivation and architecture.

Unknown Status

Cation Language - Either not public or under development, and based on the beta subdomain likely won't be for a while. It does link to data type algebra docs for Strict types, which appears to be a work in progress specification for strict encoding for algebraic data types.