Forthix - Categorical Coding with Forthic

Last time, we touched on solving coding problems and hinted at what it means to solve problems in general. A good place to start is with something simple. Suppose we wanted to solve $x + 7 = 12$. I know you know how to do this, but if you think about it slowly and carefully, you’ll realize that the essential operation is finding the inverse of $\mathbin{+} 7$ and applying it to both sides of the equation. For this case, the inverse is $\mathbin{-} 7$. Applying this to the left side gives us $x$; applying this to the right side gives us $5$, which is the solution.

Finding an inverse is the key to solving any kind of problem. This applies to arithmetic problems. It applies to solving systems of equations (where the key is finding the inverse of a matrix). It applies to solving optimization problems from Operations Research. It applies to solving differential equations and solving problems from process control theory (with one proviso that we’ll discuss in more detail later). I’ll go even further and say that finding inverses applies to solving any type of coding problem.

What is an inverse?

In the case of $\mathbin{+} 7$, the inverse is $\mathbin{-} 7$ because when we compose these transformations, we get $\mathbin{+} 0$, which is the identity transformation for addition. The identity transformation is important for solving problems because it allows us to isolate the thing we want to solve for, in this case $x$ because $x + 7 - 7 = x + 0 = x$. In the case of addition, $\mathbin{+} 0$ is the identity transformation for every number. In general, however, each object in a category will have its own identity transformation. Recall from our first post that the identity transformation for an object starts from an object and returns to that same object such that we can insert any number of identity transformations before or after that object in a sequence of transformations without affecting the result.

Inverses imply something very strong

We can view our $x + 7 = 12$ example as consisting of an object $x$ and an object $12$ with a morphism $\mathbin{+} 7$ between them:

We’ve already shown that there’s an inverse transformation:

Since adding and subtracting numbers is something we can write in code, this diagram also fits into our Coding Category. By definition, the transformations mean that given $x$, we can write the code to compute $12$ and that given $12$, we can write the code to compute $x$. In some sense (in a very deep sense), $x$ and $12$ contain the “same information” because given one, we can compute the other. This is actually a general property for all categories: if an inverse transformation exists between two objects, they can be treated as the “same” thing. Intuitively, if you had either of these objects, you could produce the other at will using one of the inverse transformations.

Invertible objects are also called “isomorphic” (same shape). You can see this clearly if you consider the Set Category (objects are sets and morphisms are functions between sets). If we have two sets, the only way we can construct an inverse is if both sets have the same number of elements and the function between them maps elements 1-to-1. In this case, we can find the inverse function by just reversing the direction of the mapping. Invertible sets must have the same number of elements, and thus the “same shape”.

Closing Thoughts

There’s something elegant and beautiful about viewing the solution of problems as the finding of inverses. While we’ve really only examined this in our addition example, this idea applies in general to many kinds of problems, perhaps all problems. There’s something deeply correct about invertible objects being “the same” and having the “same information” in some sense. Invertible objects aren’t identical but they are literally interchangeable via a transformation in the Coding and Forthic categories.

What happens if objects aren’t invertible? In this case, there’s an imbalance in the information between the objects and something is “missing”. In our Coding and Forthic categories, there isn’t a way to compute one of these objects (perhaps both) from the other. Fortunately, we can get around this by viewing things in terms of “adjoints”. More on that in our next post.