In the previous installment of Categories for Programmers, Categories Great and Small, I gave a few examples of simple categories. In this installment we’ll work through a more advanced example. If you’re new to the series, here’s the Table of Contents.
Composition of Logs
You’ve seen how to model types and pure functions as a category. I also mentioned that there is a way to model side effects, or non-pure functions, in category theory. Let’s have a look at one such example: functions that log or trace their execution. Something that, in an imperative language, would likely be implemented by mutating some global state, as in:
string logger; bool negate(bool b) { logger += "Not so! "; return !b; }
You know that this is not a pure function, because its memoized version would fail to produce a log. This function has side effects.
In modern programming, we try to stay away from global mutable state as much as possible — if only because of the complications of concurrency. And you would never put code like this in a library.
Fortunately for us, it’s possible to make this function pure. You just have to pass the log explicitly, in and out. Let’s do that by adding a string argument, and pairing regular output with a string that contains the updated log:
pair<bool, string> negate(bool b, string logger) { return make_pair(!b, logger + "Not so! "); }
This function is pure, it has no side effects, it returns the same pair every time it’s called with the same arguments, and it can be memoized if necessary. However, considering the cumulative nature of the log, you’d have to memoize all possible histories that can lead to a given call. There would be a separate memo entry for:
negate(true, "It was the best of times. ");
and
negate(true, "It was the worst of times. ");
and so on.
It’s also not a very good interface for a library function. The callers are free to ignore the string in the return type, so that’s not a huge burden; but they are forced to pass a string as input, which might be inconvenient.
Is there a way to do the same thing less intrusively? Is there a way to separate concerns? In this simple example, the main purpose of the function negate
is to turn one Boolean into another. The logging is secondary. Granted, the message that is logged is specific to the function, but the task of aggregating the messages into one continuous log is a separate concern. We still want the function to produce a string, but we’d like to unburden it from producing a log. So here’s the compromise solution:
pair<bool, string> negate(bool b) { return make_pair(!b, "Not so! "); }
The idea is that the log will be aggregated between function calls.
To see how this can be done, let’s switch to a slightly more realistic example. We have one function from string to string that turns lower case characters to upper case:
string toUpper(string s) { string result; int (*toupperp)(int) = &toupper; // toupper is overloaded transform(begin(s), end(s), back_inserter(result), toupperp); return result; }
and another that splits a string into a vector of strings, breaking it on whitespace boundaries:
vector<string> toWords(string s) { return words(s); }
The actual work is done in the auxiliary function words
:
vector<string> words(string s) { vector<string> result{""}; for (auto i = begin(s); i != end(s); ++i) { if (isspace(*i)) result.push_back(""); else result.back() += *i; } return result; }
We want to modify the functions toUpper
and toWords
so that they piggyback a message string on top of their regular return values.
We will “embellish” the return values of these functions. Let’s do it in a generic way by defining a template Writer
that encapsulates a pair whose first component is a value of arbitrary type A
and the second component is a string:
template<class A> using Writer = pair<A, string>;
Here are the embellished functions:
Writer<string> toUpper(string s) { string result; int (*toupperp)(int) = &toupper; transform(begin(s), end(s), back_inserter(result), toupperp); return make_pair(result, "toUpper "); } Writer<vector<string>> toWords(string s) { return make_pair(words(s), "toWords "); }
We want to compose these two functions into another embellished function that uppercases a string and splits it into words, all the while producing a log of those actions. Here’s how we may do it:
Writer<vector<string>> process(string s) {
auto p1 = toUpper(s);
auto p2 = toWords(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}
We have accomplished our goal: The aggregation of the log is no longer the concern of the individual functions. They produce their own messages, which are then, externally, concatenated into a larger log.
Now imagine a whole program written in this style. It’s a nightmare of repetitive, error-prone code. But we are programmers. We know how to deal with repetitive code: we abstract it! This is, however, not your run of the mill abstraction — we have to abstract function composition itself. But composition is the essence of category theory, so before we write more code, let’s analyze the problem from the categorical point of view.
The Writer Category
The idea of embellishing the return types of a bunch of functions in order to piggyback some additional functionality turns out to be very fruitful. We’ll see many more examples of it. The starting point is our regular category of types and functions. We’ll leave the types as objects, but redefine our morphisms to be the embellished functions.
For instance, suppose that we want to embellish the function isEven
that goes from int
to bool
. We turn it into a morphism that is represented by an embellished function. The important point is that this morphism is still considered an arrow between the objects int
and bool
, even though the embellished function returns a pair:
pair<bool, string> isEven(int n) { return make_pair(n % 2 == 0, "isEven "); }
By the laws of a category, we should be able to compose this morphism with another morphism that goes from the object bool
to whatever. In particular, we should be able to compose it with our earlier negate
:
pair<bool, string> negate(bool b) { return make_pair(!b, "Not so! "); }
Obviously, we cannot compose these two morphisms the same way we compose regular functions, because of the input/output mismatch. Their composition should look more like this:
pair<bool, string> isOdd(int n) { pair<bool, string> p1 = isEven(n); pair<bool, string> p2 = negate(p1.first); return make_pair(p2.first, p1.second + p2.second); }
So here’s the recipe for the composition of two morphisms in this new category we are constructing:
- Execute the embellished function corresponding to the first morphism
- Extract the first component of the result pair and pass it to the embellished function corresponding to the second morphism
- Concatenate the second component (the string) of of the first result and the second component (the string) of the second result
- Return a new pair combining the first component of the final result with the concatenated string.
If we want to abstract this composition as a higher order function in C++, we have to use a template parameterized by three types corresponding to three objects in our category. It should take two embellished functions that are composable according to our rules, and return a third embellished function:
template<class A, class B, class C> function<Writer<C>(A)> compose(function<Writer<B>(A)> m1, function<Writer<C>(B)> m2) { return [m1, m2](A x) { auto p1 = m1(x); auto p2 = m2(p1.first); return make_pair(p2.first, p1.second + p2.second); }; }
Now we can go back to our earlier example and implement the composition of toUpper
and toWords
using this new template:
Writer<vector<string>> process(string s) { return compose<string, string, vector<string>>(toUpper, toWords)(s); }
There is still a lot of noise with the passing of types to the compose
template. This can be avoided as long as you have a C++14-compliant compiler that supports generalized lambda functions with return type deduction (credit for this code goes to Eric Niebler):
auto const compose = [](auto m1, auto m2) { return [m1, m2](auto x) { auto p1 = m1(x); auto p2 = m2(p1.first); return make_pair(p2.first, p1.second + p2.second); }; };
In this new definition, the implementation of process
simplifies to:
Writer<vector<string>> process(string s){ return compose(toUpper, toWords)(s); }
But we are not finished yet. We have defined composition in our new category, but what are the identity morphisms? These are not our regular identity functions! They have to be morphisms from type A back to type A, which means they are embellished functions of the form:
Writer<A> identity(A);
They have to behave like units with respect to composition. If you look at our definition of composition, you’ll see that an identity morphism should pass its argument without change, and only contribute an empty string to the log:
template<class A> Writer<A> identity(A x) { return make_pair(x, ""); }
You can easily convince yourself that the category we have just defined is indeed a legitimate category. In particular, our composition is trivially associative. If you follow what’s happening with the first component of each pair, it’s just a regular function composition, which is associative. The second components are being concatenated, and concatenation is also associative.
An astute reader may notice that it would be easy to generalize this construction to any monoid, not just the string monoid. We would use mappend
inside compose
and mempty
inside identity
(in place of +
and ""
). There really is no reason to limit ourselves to logging just strings. A good library writer should be able to identify the bare minimum of constraints that make the library work — here the logging library’s only requirement is that the log have monoidal properties.
Writer in Haskell
The same thing in Haskell is a little more terse, and we also get a lot more help from the compiler. Let’s start by defining the Writer
type:
type Writer a = (a, String)
Here I’m just defining a type alias, an equivalent of a typedef
(or using
) in C++. The type Writer
is parameterized by a type variable a
and is equivalent to a pair of a
and String
. The syntax for pairs is minimal: just two items in parentheses, separated by a comma.
Our morphisms are functions from an arbitrary type to some Writer
type:
a -> Writer b
We’ll declare the composition as a funny infix operator, sometimes called the “fish”:
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
It’s a function of two arguments, each being a function on its own, and returning a function. The first argument is of the type (a->Writer b)
, the second is (b->Writer c)
, and the result is (a->Writer c)
.
Here’s the definition of this infix operator — the two arguments m1
and m2
appearing on either side of the fishy symbol:
m1 >=> m2 = \x -> let (y, s1) = m1 x (z, s2) = m2 y in (z, s1 ++ s2)
The result is a lambda function of one argument x
. The lambda is written as a backslash — think of it as the Greek letter λ with an amputated leg.
The let
expression lets you declare auxiliary variables. Here the result of the call to m1
is pattern matched to a pair of variables (y, s1)
; and the result of the call to m2
, with the argument y
from the first pattern, is matched to (z, s2)
.
It is common in Haskell to pattern match pairs, rather than use accessors, as we did in C++. Other than that there is a pretty straightforward correspondence between the two implementations.
The overall value of the let
expression is specified in its in
clause: here it’s a pair whose first component is z
and the second component is the concatenation of two strings, s1++s2
.
I will also define the identity morphism for our category, but for reasons that will become clear much later, I will call it return
.
return :: a -> Writer a return x = (x, "")
For completeness, let’s have the Haskell versions of the embellished functions upCase
and toWords
:
upCase :: String -> Writer String upCase s = (map toUpper s, "upCase ")
toWords :: String -> Writer [String] toWords s = (words s, "toWords ")
The function map
corresponds to the C++ transform
. It applies the character function toUpper
to the string s
. The auxiliary function words
is defined in the standard Prelude library.
Finally, the composition of the two functions is accomplished with the help of the fish operator:
process :: String -> Writer [String] process = upCase >=> toWords
Kleisli Categories
You might have guessed that I haven’t invented this category on the spot. It’s an example of the so called Kleisli category — a category based on a monad. We are not ready to discuss monads yet, but I wanted to give you a taste of what they can do. For our limited purposes, a Kleisli category has, as objects, the types of the underlying programming language. Morphisms from type A to type B are functions that go from A to a type derived from B using the particular embellishment. Each Kleisli category defines its own way of composing such morphisms, as well as the identity morphisms with respect to that composition. (Later we’ll see that the imprecise term “embellishment” corresponds to the notion of an endofunctor in a category.)
The particular monad that I used as the basis of the category in this post is called the writer monad and it’s used for logging or tracing the execution of functions. It’s also an example of a more general mechanism for embedding effects in pure computations. You’ve seen previously that we could model programming-language types and functions in the category of sets (disregarding bottoms, as usual). Here we have extended this model to a slightly different category, a category where morphisms are represented by embellished functions, and their composition does more than just pass the output of one function to the input of another. We have one more degree of freedom to play with: the composition itself. It turns out that this is exactly the degree of freedom which makes it possible to give simple denotational semantics to programs that in imperative languages are traditionally implemented using side effects.
Challenge
A function that is not defined for all possible values of its argument is called a partial function. It’s not really a function in the mathematical sense, so it doesn’t fit the standard categorical mold. It can, however, be represented by a function that returns an embellished type optional
:
template<class A> class optional { bool _isValid; A _value; public: optional() : _isValid(false) {} optional(A v) : _isValid(true), _value(v) {} bool isValid() const { return _isValid; } A value() const { return _value; } };
As an example, here’s the implementation of the embellished function safe_root
:
optional<double> safe_root(double x) { if (x >= 0) return optional<double>{sqrt(x)}; else return optional<double>{}; }
Here’s the challenge:
- Construct the Kleisli category for partial functions (define composition and identity).
- Implement the embellished function
safe_reciprocal
that returns a valid reciprocal of its argument, if it’s different from zero. - Compose
safe_root
andsafe_reciprocal
to implementsafe_root_reciprocal
that calculatessqrt(1/x)
whenever possible.
Acknowledgments
I’m grateful to Eric Niebler for reading the draft and providing the clever implementation of compose
that uses advanced features of C++14 to drive type inference. I was able to cut the whole section of old fashioned template magic that did the same thing using type traits. Good riddance! I’m also grateful to Gershom Bazerman for useful comments that helped me clarify some important points.
Next: Products and Coproducts.
Follow @BartoszMilewski
December 24, 2014 at 3:45 pm
Bartosz, Thanks for writing this, I’m following with great interest. Please replace “goest” with “goes”.
December 24, 2014 at 5:36 pm
I realize it’s just being used as an example, but I’ll point out that logging is somewhat of an odd case. When debugging, we often want to cross encapsulation boundaries and preserve side effects. If the function is memoized, it’s often better to log only when there is a cache miss. If the cache is effective, logging on cache hits as well as misses will greatly increase repetition on the log.
Another use for logging might be to understand when functions are being evaluated lazily. In that case, we wouldn’t want reading the log to affect the order in which functions are evaluated or force functions to be evaluated when they otherwise wouldn’t be. Log output can’t be treated as a part of a function’s regular return value when it’s being used to expose non-functional aspects of the program’s implementation.
December 24, 2014 at 8:25 pm
I’m also eagerly following. Jealous that you get to do this from Siena…
December 24, 2014 at 9:33 pm
@Brian: Maybe I should have called it “auditing” rather than “logging.” There are applications where you want to accumulate some data — an audit trail — while you are performing other activities.
December 25, 2014 at 1:41 pm
Great series so far, I really enjoy it!
One question though: Why is it “pair isOdd(int n)”, shouldn’t it rather be “pair isOdd(int n)”.
December 25, 2014 at 4:26 pm
@el kleino: Your angle brackets were removed by wordpress, but I figured out what you meant and fixed it. Thanks!
December 30, 2014 at 12:01 pm
Hello, great post! I’ve still not read through all of it but why does compose must take its parameters as std::function’s? If instead the definition were this:
Then you could use it in the same way of the definition using lambda with the auto parameters.
December 30, 2014 at 5:38 pm
[…] Kleisli Categories […]
December 30, 2014 at 6:51 pm
@tarcisiogr: As far as I can understand, after WordPress mangled your comment (you need to escape all angle brackets, replacing them with
<
), you’re asking about passing function pointers by reference. This will work as long as you only pass functions. It won’t work with function objects and lambdas.December 30, 2014 at 11:06 pm
Indeed, @bartoszmilewski, I can see it now 🙂
January 7, 2015 at 4:21 pm
[…] for Programmers. In the previous installment we discussed how to add logging to pure functions. In this installment, we’ll move our […]
January 8, 2015 at 4:52 am
As a C++ programmer, I really appreciate the C++ examples, which clearly shows the paradigm and gives me a taste of the upcoming monads :-).
January 19, 2015 at 11:53 am
Thank you for writing this, it is very interesting!
This is my hangup right now:
“The important point is that this morphism is still considered an arrow between the objects int and bool, even though the embellished function returns a pair.”
From which perspective is it considered that? If you would draw this category as a graph, would you simply ignore the second part of the pair? How has the solution to the composition itself then anything to do with category theory?
The compose function just seems like hack to me, and maybe it is, but since these kinds of categories have a name, I suspect there is something more to it?
I’m not asking how the code works, I understand that. What I want to know is how it is derived from category theory 🙂
You wrote, “so before we write more code, let’s analyze the problem from the categorical point of view.” But I feel like I got cheated on the categorical analysis.
Thanks again for your work.
January 19, 2015 at 2:04 pm
When you draw a category as a graph, you just have objects and arrows. Now you want to give some interpretation to these objects and arrows. One possibility is to interpret objects as types and arrows as functions. You define composition of arrows as composition of functions and it works: the laws of category are satisfied.
But now I’m creating a new category in which objects are still interpreted as types, but arrows are not functions between these types, but rather those “embellished” functions. I have objects, I have arrows, but how do I compose those arrows? For each type of embellishments, I have to come up with some way of figuring out what arrow is considered a composition of two other composable arrows. Composable means: the object at the end of one arrow is the same as the object at the start of another. The arrow that ends at bool corresponds to a function returning a pair of bool and string. The arrow that starts at bool corresponds to a function that takes a bool. Simple function composition won’t work this time.
But I am free to define the composition of arrows any way I want, as long as it fulfills the laws of category: associativity and identity. So that’s what I do.
Give me any arrow between int and bool, and another between bool and float, and I’ll give you an arrow between int and float. How do I do it? I translate these arrows into embellished functions, and use my fancy composition to get an embellished function back. I translate this embellished function to an arrow and hand it to you.
Now you can write a program by composing those arrows. You design your algorithm in terms of those arrows, not functions. It’s easier, and you don’t have to worry about the plumbing. You get back one final arrow. Translate this arrow into an embellished function and run it.
Tell me if this helps.
January 23, 2015 at 11:10 am
It helps, thank you for your answer! I needed some days for it to sink in.
I think some visuals here would be helpful. The writer category could be visualized with a pig and an arrow to another pig holding a piece of paper. The arrow between them can be composed with itself if the pig holding the paper throws it in a bag and pretends to be the first pig (sneaky pig!). The bag is then opened at the end of composition, and all the pieces of paper together compose the log. (or maybe this is just confusing to everyone except for me)
My understanding of Kleisli categories at this point is that they have a secret trick (like throwing papers in a bag, but it could be anything) that allows an arrow from A -> embellished(C) to be composed with C -> embellished(D).
The secret trick is (I guess) not that important, it should just be whatever is most useful to the programmer (right?). What is more important is that the laws of category are obeyed. (I mean, in the case of writer, composition could be accomplished by just ignoring the log messages all together. I’m guessing there is a name for this, the procrastinator category?)
I’m still curious if it is possible to represent the writer category as a graph, and what that would look like.
Thanks once again 🙂
February 25, 2015 at 5:04 pm
Albin made some good question here, and only after reading Bartosz’ reply it was made clear to me. I just got confused on the fact that in this category the objects are still types, and not those pairs (which is stated in the article itself, but somehow it didn’t sink in…).
April 30, 2015 at 5:48 am
Thanks, I really like this series.
Typo: “It’s nor really”
May 5, 2015 at 12:39 am
Really enjoying this series, but just wanted to give you a heads up that your usage of angle brackets in code samples occasionally renders as HTML tags (e.g. pair<a, b> creates a <a, b> HTML tag instead)
May 5, 2015 at 10:27 am
@ilikebits: I don’t know what happened. I proofread my posts very carefully, so this is unexpected. Something in WordPress must have decided to reformat the tags.
I fixed all the problems I could find. If you see any more, please tell me.
May 5, 2015 at 11:54 am
Unfortunately, it seems like more of my blog posts were affected by this WordPress problem overnight.
May 5, 2015 at 12:04 pm
Fantastic blog. Thank you very much. I am into Haskell and functional programming for months now but felt I need knowledge about its foundations. This is very helpful.
And I like the piggies and the fireworks too 🙂
August 1, 2015 at 7:53 pm
Reblogged this on Human Mathematics.
September 2, 2015 at 8:48 am
Thank you. I really enjoy having a concrete example like this that shows how to apply a very abstract concept. I was able to work through both the example and challenge in F#.
December 10, 2015 at 5:06 am
— Bartosz, the category theory bit of this is lovely, but the haskell bit is hard.
— I keep getting confused by the syntax, and I can’t make it work.
— My best shot is:
type CanFail a = (Value a | Fail)
safe-inv :: Real -> CanFail Real
safe-inv x = if (x=0) Fail else Value (1/x)
safe-sqrt :: Real -> CanFail Real
safe-sqrt x = if x<0 Fail else Value (sqrt x)
— But it won’t compile. “parse error on input `|'”. What’s my misconception?
December 10, 2015 at 11:19 am
John, Yes, it’s hard to learn Haskell syntax, especially when you are getting unhelpful error messages like “parse error”. There are several errors in your code:
–
type
can be used only when you have a single constructor, not two. Usedata
instead.– Don’t put parentheses around data definition.
– You can’t use dashes in variable/function names. They are interpreted as minus signs. You can use camelCase or underscore instead.
–
Real
is not a type (it’s a typeclass). UseDouble
instead.– Comparison for equality is a double equal sign
==
. (Parens are not necessary.)– You need
then
after the condition. (That’s why you don’t need parens.)December 11, 2015 at 8:26 am
Bartosz, thank you ever so much! With your tips and a bit of research I finally got something that seems to work.
I can quite see why you wouldn’t want the answer to your puzzle on your blog, so feel free to delete this comment, but if you think it might be helpful to others struggling with Haskell itself:
December 11, 2015 at 10:31 am
You don’t need to go through the
let
step. It’s simpler to dodirectly. Also, way too many parentheses. Most expressions are simply delimited by keywords (hence
then
andof
) or extend to the end of line or block (e.g., after->
).February 28, 2016 at 6:23 pm
Any where I can check the answers to the exercises?
March 10, 2016 at 9:47 am
Thank you this. I am working through the whole series. I tried to implement the C++ Writer and it all works for me except for the identity.
fails as it cannot infer the template type. This alternative giving the type does work:
The compiler is Clang 3.6 with C++14.
December 15, 2016 at 4:36 pm
The lead up to and including the “between function calls” point really helped me. 🙂
September 15, 2017 at 1:11 pm
I first encountered category theory 30 years ago, when I took a class on it. I didn’t understand what it was good for. I’ve read a bit here and there on the subject since, but didn’t really get it. I heard that it had become important in programming language semantics and type theory, but I didn’t see the connection.
Four posts into “Category Theory for Programmers”, and I’m finally starting to see the relevance to computer science. Thank you very much! Your emphasis on composability provided the missing link for me.
July 4, 2019 at 1:59 am
Thank you for this series, Bartosz!
I tried to translate johnlawrenceaspden’s Haskell example in clojure (I modeled the optional type as a function). If you see this message (activity is pretty old here), have a look at https://pastebin.com/fD4bAtCi
Feedback is more than appreciated.
Thanks again!
December 19, 2019 at 2:46 pm
Hi!
There seem to be too many square brackets in the safe_root example, the return value instantiation should have round brackets instead. At least that’s what the compiler said as I was working through the challenge.
Thank you for your blog!
December 20, 2019 at 1:31 pm
I’m using curly braces initialization in C++.