Confluence and Church-Rosser

Okay, I'm back to post about confluence and the Church-Rosser property, as I threatened yesterday. This is a complaint about something I found very annoying when I was in graduate school; it's related to yesterday's complaint about type-1 and type-2 errors in statistics, but slightly different in that it's not about names for two things that don't help you know which names which, but rather about two names that one is supposed to keep straight even though they both name the same thing.

In lambda-calculi, and other rewriting systems with which I am less familiar, one defines a reduction relation on terms that is supposed to capture the idea of a single step of computation or simplification, like replacing "2+3" with "5". (These are expressions of arithmetic, not lambda-calculus, but never mind. I'll use arithmetic expressions again below.) Reduction relations are almost never reflexive (that would be zero steps of computation), transitive (more than one step) or symmetric (counting a backward step as a forward step), but it does make sense to look at the notion of "equivalence" that comes from thinking of things as equivalent if one can be reduced to the other. The equivalence relation induced by reduction, called conversion or convertibility, is the reflexive, symmetric, transitive closure of reduction -- which is to say that two terms are convertible if one can be transformed into the other by a sequence of zero or more steps each of which is a reduction either forwards or backwards. So, if "2+3" reduces to "5" and "9-4" also reduces to "5", the expressions "2+3" and "9-4" are convertible and we can think of them as having the same meaning.

In general, if A reduces in zero or more steps to B, and C also reduces in zero or more steps to B, then we can say that B is a "common reduct" of A and C. Clearly, any two terms with a common reduct are by definition convertible. The question is, do any two convertible terms have a common reduct?

[Why is this question important? Among other reasons, because if so, and you have two terms that you can show do not have a common reduct, you will know they are not convertible. Otherwise, it would be hard to be sure.]

In the lambda-calculus, the answer is yes. This fact was proven by Church and Rosser in 1936 and is called the Church-Rosser Theorem. For rewrite systems other than the untyped lambda-calculus, the answer obviously depends on what the reduction relation actually is. A reduction relation for which any two convertible terms have a common reduct can be said to have the Church-Rosser property.

OK. It turns out that the key to proving the Church-Rosser property, at least for the lambda calculus, is to prove the following: If there is more than one way to reduce a term A, say to B1 or to B2, in zero or more steps, then there exists some term C such that both B1 and B2 can be reduced in zero or more steps to C. More generally, we can say: any two terms with a common "source" also have a common reduct. So if two different people are trying to reduce A and their paths ever diverge, taking one to B1 and the other to B2, then it doesn't really matter because they will eventually "flow back together" at C. This property is called confluence.

So here's where I have a problem. It turns out that the property I refer to as CR above (convertible terms have a common reduct) and the property I just called confluence (terms with a common source have a common reduct) are equivalent. (The CR->confluence direction is obvious, as any terms with a common source are convertible; the proof of other direction left as an exercise. Hint: induction on the number of steps in the conversion.) Because they're equivalent, it's always hard to know whether I have the names the right way around. I was pretty sure this is the way I learned them in grad school, and it's consistent with MathWorld's definitions of confluence and Church-Rosser, but Wikipedia has it differently, as does at least one legitimate book I looked in while writing this.

What's my point? The point is that I resent having had to devote precious brain cells to remembering which is which of two different ways to say the same goddamn thing. It seems like a pretty small thing and not worth bothering to resent, but there it is.

Arbitrary Names

Language Log is a treasure trove. Every time I dive into its archives I find something old, but new to me, that is interesting.

In 2004, Geoffrey Pullum discussed his refusal to learn which business model for massage is called incall and which is called outcall, on the grounds that the names are utterly unhelpful and "if I can't see how it follows by some sort of linguistic principles, I will just forget it again." Later that same day, Christopher Potts pointed out that similar problems exist with ordering food "in" or "out", pushing an appointment "up" or "back", and (my favorite) identifying the root of a tree structure as maximal or minimal in the dominance relation. (Potts also says that "linguists draw their trees upside down, with the root at the top of the page" which of course is right-side up to computer scientists like me, as long as we're talking about trees as an abstract graph structure rather than about trees, the plants.)

I love reading this kind of LL post, because some of these are the kind of things about language, especially technical language, that drive me crazy.

Example: Statistics textbooks classify the ways a statistical test can go wrong as "type 1 errors" and "type 2 errors". (Or maybe they use Roman numerals. The point, namely that these names are stupid, is the same.) I have an old book (actually, a new copy of a Dover edition of an old text) that calls them "errors of the first kind" and "errors of the second kind". Now, one of these kinds of errors is when your test tells you two things are different when they're really the same, and the other is when the test tells you they are the same when they're really different. Like Pullum, I absolutely refuse to even try to remember which is which. And also like Pullum, I anticipate that many people reading this statement would respond to it by trying to tell me anyway: the fact that I don't know is not the point; the point is that the meanings of these technical terms are arbitrary, reflecting nothing about the events they describe but depending instead on what order some founding father of statistics happened to think of them in.

So what do I suggest? Well, in many contexts, like testing people for diseases or testing drugs for treatment effects or identifying spam or whatever, the terms "false positive" and "false negative" are transparent and work perfectly well. In other cases, where the designation of outcomes as "positive" and "negative" is not obvious, the statistics literature provides the terms "rejection error" and "acceptance error", referring to rejection or acceptance of the null hypothesis; which hypothesis is null is an unambiguous technical fact about the statistical method being used.

Interestingly, there are tons of these arbitrary namings in mathematics, and I don't object to all of them. I don't really care, for example, about the fact that one kind of function is called a homomorphism and another very different kind of function is called a homeomorphism, even though (as far as I can tell) there's no way to look at those words and determine from their structures which means what. But in this case, and many others, there's a good reason not to mind: a homomorphism is a function you study in algebra, and a homeomorphism is one you study in topology. So while if you're reading this paragraph as a nonmathematician and seeing these terms for the first time I could forgive you for being confused, the average mathematician probably learned the definitions of those two words in separate classes, probably separate semesters of undergraduate math. They're probably conceptually separate enough that no one who cares about either thing can possibly be confused.

Similarly, before I studied Euclidean geometry in ninth grade, I could never remember which kind of pair of angles was called complementary and which was called supplementary. (To be truthful, it's now been long enough that I will have to go look them up before I can finish this paragraph.) (Okay, looked it up. And guess what? I had it right.) There's an episode of the Cosby Show where Cockroach, complaining to Dr. Huxtable about having to study for a math test, says "I couldn't care less about complementary and supplementary angles." If he meant he didn't want to learn which word meant which thing, and Mrs. Westlake had organized her syllabus such that the two definitions were on the same pop quiz, then I can't say I blame him. But when I took geometry, the notion of a straight angle was introduced a whole week or two before that of a right angle. I'm not sure why that was, but it had the pleasant effect of letting us talk about supplementary angles for quite a while before we had to know about complementary angles. By the time we had to learn the second word, we were comfortable enough with the first word that they didn't interfere. (At least not for me. My classmates might not have agreed.) The difference between the classroom experience and the, well, call it the "dictionary experience" was impressive to me even then.

And don't get me started on confluence and the Church-Rosser property. Because I've spent so much time on these two examples that I'll have to save that one for later.