“The essential virtue of category theory is as a discipline for making definitions, and making definitions is the programmer’s main task in life.”
From Computational Category Theory
Where else you can find me
In addition to this blog, you can find me on Twitter and Google+. I occasionally blog at Symbolism, though that site is mostly a paste bin for the DailySymbol Twitter account.
I’ll be speaking at the Snow Unix Event in The Netherlands in a couple weeks and I plan to go to Germany in September. I’ve made a couple trips to California this year and it looks like I’ll be flying out there more often. And of course you can always find me in Houston. If you’d like to meet in person, please let me know.
Posted in Uncategorized
Don’t be a technical masochist
There’s an old joke from Henny Youngman:
I told the doctor I broke my leg in two places. He told me to quit going to those places.
Sometimes tech choices are that easy: if something is too hard, stop doing it. A great deal of pain comes from using a tool outside its intended use, and often that’s avoidable.
For example, when regular expressions get too hard, I stop using regular expressions and write a little procedural code. Or when Python is too slow, I try some simple ways of speeding it up, and if that’s not good enough I switch from Python to C++. If something is too hard to do in Windows, I’ll do it in Linux, and vice versa.
Sometimes there’s not a better tool available and you just have to slog through with what you have. And sometimes you don’t have the freedom to use a better tool even though one is available. But a lot of technical pain is self-imposed. If you keep breaking your leg somewhere, stop going there.
Intuitionistic logic in Gilbert and Sullivan
In a recent preprint, Philip Wadler introduces intuitionistic logic using the comic opera The Gondoliers.
In Gilbert and Sullivan’s The Gondoliers, Casilda is told that as an infant she was married to the heir of the King of Batavia, but that due to a mix-up no one knows which of two individuals, Marco or Giuseppe, is the heir. Alarmed, she wails “Then do you mean to say that I am married to one of two gondoliers, but it is impossible to say which?” To which the response is “Without any doubt of any kind whatever.”
… Intuitionists … insist that a proof of A∨B must show which of A or B holds, and hence they would reject the claim that Casilda is married to Marco or Giuseppe until one of the two was identified as her husband. Perhaps Gilbert and Sullivan anticipated intuitionism, for their story’s outcome is that the heir turns out to be a third individual, Luiz, with whom Casilda is, conveniently, already in love.
On replacing calculus with statistics
Russ Roberts had this to say about the proposal to replacing the calculus requirement with statistics for students.
Statistics is in many ways much more useful for most students than calculus. The problem is, to teach it well is extraordinarily difficult. It’s very easy to teach a horrible statistics class where you spit back the definitions of mean and median. But you become dangerous because you think you know something about data when in fact it’s kind of subtle.
A little knowledge is a dangerous thing, more so for statistics than calculus.
This reminds me of a quote by Stephen Senn:
Statistics: A subject which most statisticians find difficult but in which nearly all physicians are expert.
Related: Elementary statistics book recommendation
Nomenclatural abomination
David Hogg calls conventional statistical notation a “nomenclatural abomination”:
The terminology used throughout this document enormously overloads the symbol p(). That is, we are using, in each line of this discussion, the function p() to mean something different; its meaning is set by the letters used in its arguments. That is a nomenclatural abomination. I apologize, and encourage my readers to do things that aren’t so ambiguous (like maybe add informative subscripts), but it is so standard in our business that I won’t change (for now).
I found this terribly confusing when I started doing statistics. The meaning is not explicit in the notation but implicit in the conventions surrounding its use, conventions that were foreign to me since I was trained in mathematics and came to statistics later. When I would use letters like f and g for functions collaborators would say “I don’t know what you’re talking about.” Neither did I understand what they were talking about since they used one letter for everything.
Monads are hard because …
Here’s a nice quip from Luke Gorrie on Twitter:
Monads are hard because there are so many bad monad tutorials getting in the way of finally finding Wadler’s nice paper.
Here’s the paper by Philip Wadler that I expect Luke Gorrie had in mind: Monads for functional programming.
Here’s the key line from Wadler’s paper:
Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit.
That’s the problem monads solve: they let you leave implicit some of the repetitive code otherwise required by functional programming. That simple but critical point left out of many monad tutorials.
Dan Piponi wrote a blog post You Could Have Invented Monads! (And Maybe You Already Have) very much in the spirit of Wadler’s paper. He starts with the example of adding logging to a set of functions. You could have every function return not just the return value that you’re interested in but also the updated state of the log. This quickly gets messy. For example, suppose your basic math functions write to an error log if you call them with illegal arguments. That means your square root function, for example, has to take as input not just a real number but also the state of the error log before it was called. Monads give you a way of effectively doing the same thing, but conceptually separating the code that takes square roots from the code that maintains the error log.
As for “so many bad monad tutorials,” see Brent Yorgey on the monad tutorial fallacy.
By the way, this post is not Yet Another Monad Tutorial. It’s simply an advertisement for the tutorials by Philip Wadler and Dan Piponi.
Log semiring
Here’s a strange way to do arithmetic on the real numbers.
First, we’ll need to include +∞ and -∞ with the reals.
We define the new addition of two elements x and y to be -log (exp(-x) + exp(-y) ).
We define the new multiplication to be ordinary addition. (!)
In this new arithmetic +∞ is the additive identity and 0 is the multiplicative identity.
This new algebraic structure is called the log semiring. It’s called a semiring because it satisfies all the properties of a ring except that elements don’t necessarily have additive inverses. We’ll get into the details of the definition below.
***
Let’s put a subscript S on everything associated with our semiring in order to distinguish them from their more familiar counterparts. Then we can summarize the definitions above as
- a +S b = -log (exp(-a) + exp(-b) )
- a *S b = a + b
- 0S = +∞
- 1S = 0
Note that if we define
f(a, b) = a +S b
then
f(a, b) = -g(-a, -b)
where g(a, b) is the soft maximum of a and b.
***
Finally, we list the axioms of a semiring. Note that these equations all hold when we interpret +, *, 0, and 1 in the context of S, i.e. we imagine that each has a subscript S and is as defined above.
- (a + b) + c = a + (b + c)
- 0 + a = a + 0 = a
- a + b = b + a
- (a * b) * c = a * (b * c)
- 1 * a = a * 1 = a
- a * (b + c) = (a * b) + (a * c)
- (a + b) * c = (a * c) + (b * c)
- 0 * a = a * 0 = 0
Each of these follows immediately from writing out the definitions.
Do the stars go up or down?
The thing that sparked my interest in category theory was a remark from Ted Odell regarding the dual of a linear transformation. As I recall, he said something like “There’s a reason the star goes up instead of down” and mumbled something about category theory. I took it he didn’t think highly of category theory, but my interest was piqued. Read more ›
Writing down an unwritten language
In this post I interview Greg Greenlaw, a friend of mine who served as a missionary to the Nakui tribe in Papua New Guinea and developed their writing system. (Nakui is pronounced like “knock we.”)
JC: When you went to PNG to learn Nakui was there any writing system?
GG: No, they had no way of writing words or numbers. They had names for only seven numbers — that was the extent of their counting system — but they could coordinate meetings more than a few days future by tying an equal number of knots in two vines. Each party would take a vine with them and loosen a knot each morning until they counted down to the appointed time — like and advent calendar, but without numbers!
Imaginary gold, silver, bronze, …
The previous post gave a relationship between the imaginary unit i and the golden ration. This post highlights a comment to that post explaining that the relationship generalizes to generalizations of the golden ratio.
GlennF pointed out that taking the larger root of the equation
defines the golden ratio when n = 1, the silver ratio when n = 2, etc. φn is also the continued fraction made entirely of n‘s.
With this definition, we have
Imaginary gold
This morning Andrew Stacey posted a beautiful identity I’d never seen before relating the golden ratio ϕ and the imaginary unit i:
Here’s a proof:
By De Moivre’s formula,
and so
Related posts:
Golden ratio and special angles
Golden strings and the rabbit ratio
Mental callouses
In describing writing his second book, Tom Leinster says
… I’m older and, I hope, more able to cope with stress: just as carpenters get calloused hands that make them insensitive to small abrasions, I like to imagine that academics get calloused minds that allow them not to be bothered by small stresses and strains.
Mental callouses are an interesting metaphor. Without the context above, “calloused minds” would have a negative connotation. We say people are calloused or insensitive if they are unconcerned for other people, but Leinster is writing of people unperturbed by distractions.
You could read the quote above as implying that only academics develop mental discipline, though I’m sure that’s not what was intended. Leinster is writing a personal post about the process of writing books. He’s an academic, and so he speaks of academics.
Not only do carpenters become more tolerant of minor abrasions, they also become better at avoiding them. I’m not sure that I’m becoming more tolerant of stress and distractions as I get older, but I do think I’m getting a little better at anticipating and avoiding stress and distractions.
Categories, Birds, and Frogs
Freeman Dyson divided mathematicians into birds and frogs in his essay by that title.
Some mathematicians are birds, others are frogs. Birds fly high in the air and survey broad vistas of mathematics out to the far horizon. They delight in concepts that unify our thinking and bring together diverse problems from different parts of the landscape. Frogs live in the mud below and see only the flowers that grow nearby. They delight in the details of particular objects, and they solve problems one at a time.
It’s an interesting metaphor. Like all metaphors it has its limits and Dyson discusses that. Some people are somewhere between a bird and a frog, whatever kind of creature that would be, and some alternate between being birds and frogs.
The other day I thought about Dyson’s classification and wondered whether category theorists would be birds or frogs. At first category theory seems avian, looking for grand patterns across mathematics. But as you wander further in, it seems more batrachian, absorbed in drawing little boxes and arrows.
I find it interesting that category theory can profound or trivial, depending on your perspective.
The motivations and applications are profound. Category theory has been called “metamathematics” because it formalizes analogies between diverse areas of math. But basic category theory itself is very close to its axioms. The path from first principles to common definitions and theorems in category theory is much shorter than, say, the path from the definition of the real numbers to the fundamental theorem of calculus.
(This diagram quantifies the last claim to some extent: the graph of concept dependencies in category theory is more wide than deep, and not that deep. Unfortunately I don’t have a similar diagram for calculus.)
Related post: Concepts, explosions, and developments
“Conventional” is relative
I found this line from Software Foundations amusing:
… we can ask Coq to “extract,” from a Definition, a program in some other, more conventional, programming language (OCaml, Scheme, or Haskell) with a high-performance compiler.
Most programmers would hardly consider OCaml, Scheme, or Haskell “conventional” programming languages, but they are conventional relative to Coq. As the authors said, these languages are “more conventional,” not “conventional.”
I don’t mean to imply anything negative about OCaml, Scheme, or Haskell. They have their strengths — I briefly mentioned the advantages of Haskell just yesterday — but they’re odd birds from the perspective of the large majority of programmers who work in C-like languages.
