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


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.

* * *

For daily tweets on algebra and other math, follow @AlgebraFact on Twitter.

AlgebraFact logo

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.

At the time I could think of two examples of functors that I cared about, one involving fundamental groups and one involving linear operators. The former puts the star down and the latter puts the star up.

If X and Y are topological spaces and f is a continuous function between X and Y, then f induces a map f* between the π1(X) and π1(Y), the fundamental groups of X and Y. The star goes down.

If X and Y are linear spaces and T is a continuous linear transformation between X and Y, then T* induces a map Y* between the Y*, the dual spaces of Y and X. The stars go up.

What was this arcane knowledge that Ted Odell obliquely referred to? It’s that by convention, stars go downstairs for covariant functors (like that between fundamental groups) and upstairs for contravariant functors (like that between dual spaces).

Covariant means that the induced maps go in the same direction as the original maps. Notice above that f goes from X to Y and f* goes from π1(X) to π1(Y). The X and Y are in the same order, hence covariant, going in the same direction.

Contravariant means that the induces maps go in the opposite direction as the original maps. Notice that T goes from X to Y, but T* goes from  Y* to X*, the order of X and Y is reversed, hence contravariant, going in opposite directions.

The fundamental group is defined in terms of paths in a space, i.e. functions from an interval into a a space. The dual of a vector space is defined in terms of linear functions from that space to real numbers. Functors defined in terms of functions from a fixed space (like the unit interval) into the space you’re interested in are covariant. Functors defined in terms of functions from the space you’re interested into a fixed space (like the reals) are contravariant.

Another example of stars going up or down comes from differential geometry. A function f from Rn to Rm induces a map f* from the tangent space Rnp to Rmf(p). Star downstairs, n and m appearing in the same order. The analogous map on differential forms, however, is f*, star upstairs, and goes in the opposite direction. (At least in Spivak‘s notation.) Unfortunately, the use of the words “covariant” and “contravariant” in the context of tensors is backward to what is now customary usage, though for good historical reasons.

* * *

The convention described here of putting stars downstairs for covariant functors and upstairs for contravariant functors is common, but it’s not universal. I ran into an exception right after writing this post. But I believe the convention is followed more often than not.

* * *

My initial impression of category theory was positive: it could tell me why the star goes downstairs in my topology course and upstairs in my functional analysis course! My next exposure to category theory left a bad impression that lasted for years. Category theory can be used to clarify or to obfuscate, to solve problems or to create problems, like any other tool.

Related: Applied category theory

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!

JC: I believe you said that Nakui has a similar grammar to other languages in PNG but completely different vocabulary. Were you able to benefit from any other translation work in the area? Will your work serve as a starting point for translating another language?

GG: Yes. Missionaries had moved into our general area back in the 80’s and the languages they studied had mostly the same grammar features that we saw in the Nakui language. This sped the process, but in truth, the slowest part of learning to speak was not analyzing the grammar, it was training yourself to use it. Each Nakui verb could conjugate 300 different ways depending on person, recipient, tense, aspect, direction, and number.

JC: Do any of the Nakui speak a pidgin or any other language that served as a bridge for you to learn their language?

GG: We were blessed with one very good pidgin speaker when we moved into the village and several others who spoke the Melanesian Tok Pisin at a moderate level. That was a help in eliciting phrases and getting correction, but there were limits to how much they understood about their own speech. They had never thought about their language analytically and could not state a reason for the different suffixes used in the language, they just knew it was the right way to say something. Most peculiar was that they couldn’t even tell where certain word breaks were. Their language had never been “visible” to them. Nouns were easy to separate out, but it was hard to know if certain modifiers were affixes or separate function words.

JC: What are a few things that English speakers would find surprising about the language?

GG: Nakui has very few adjectives but innumerable verbs. They do the majority of their describing by using a very specific verb. There is a different verb for cutting something in the middle as opposed to cutting off a small section or cutting it long ways or cutting something to fall downward or cutting something to bits. The correct verb for the situation will also depend on the object being cut — is it log-like, leaf-like, or flesh-like.

JC: Do you try to learn a new language aurally first before starting on a writing system, or do you start developing a writing system early on so you can take notes?

GG: It’s language, so you always want your ears and tongue to lead your eyes. We use the international phonetic alphabet to write down notes, but we encourage language learners to hold off on writing anything for almost of month. After they are memorizing and pronouncing correctly a host of nouns and some noun modifiers, then we encourage them to start writing down their data with the phonetic alphabet. About half way to fluency they usually have enough perspective on the variety of sounds and where those sounds occur that they can narrow down a useful alphabet.

JC: How long did it take to learn the language? To create the writing system? How many people were working on the project?

GG: Primarily Tim Askew and myself, but there were three other missionaries that worked among the Nakui in the early days and each had some contribution to our understanding. The biggest credit really belongs to God, by whose grace we were allowed to live there and by whose strength we were able to chip away for three years until the job was done.

JC: Can you describe the process you went through to create the writing system?

GG: Well after collecting thousands of words written phonetically we could start a process of regularizing all that data. Looking at the language as a whole we had to decided the sleekest, most uniform way to consistently spell those sounds phonetically. After cleaning up our data we could take a hard look at which of the sounds were unique and which are just modified by surrounding sounds. Phonetically the English language has three different ‘t’ sounds: an aspirated ‘t’, and unaspirated ‘t’, and an unreleased ‘t’. We only think of one ‘t’ sound, though, and it would be confusing (and irritating) if we had three ‘t’ symbols in our alphabet. Our ‘t’s just become unreleased automatically when they are at the end of a word and they become unaspirated when they blend with an ‘s’. You need to narrow down the number of sounds to just the ones that are significant and meaningful. It is only those unique sounds that are given letters in the alphabet.

JC: What is the alphabet you settled on? Do the letters represent sounds similar to what an English speaker would expect?

GG: We found 10 vowel sounds and 10 consonant sounds were needful in the Nakui language. The 10 consonants are symbolized the same as English, but the vowels had to be augmented. We borrowed the letter ‘v’ to become the short ‘u’ sound and used accent marks over other vowels to show their lowered and more nasalized quality.

JC: Could you give an example of something written in Nakui?

GG: This is John 3:16. Músvilv Sisasvyv me iyemvi, “Kotvlv asini niyanú nonú mvli mvlei ufau. Múmvimvilv, tuwani aluwalv siyv tuwayv itii, asinosv. Mvimeni notalv me svmvleliyelv, ‘Sisasvni yáfu kokuimvisv,’ múmeni nonv ba itinvini, i tínonvminvini.

JC: Is it unusual for a language to have as many vowel symbols as consonant symbols?

GG: Good question. I’m not sure what normal would be worldwide, but I know we have a lot more than five vowel sounds in English! All our English vowel symbols have double or triple allophones (long sounds, short sounds, alternate sounds) making it very challenging to instruct my 6 yr old in the skill of reading.

JC: Have you published anything on your work, say in a linguistics journal?

GG: No, there is nothing unique in what we did. Truth is, we organized our findings and reported our work in an informal, non-academic, pragmatic way because our goal was not a PhD in anthropology, but a redeeming ministry in the lives of tribal men and women and ultimately a commendation from the Maker of men.

JC: How many of the Nakui can read their language?

GG: All the young men in our village are readers now, with the exception of a dyslexic man who attempted our literacy course three times without result. About 1/3 of the young women can read. They have less available time for study, and in the early days the village leaders did not allow the girl to be in class with the boys. As a result, literacy for ladies had a slower start and fewer participants. There were older men who tried to learn to read, but none that succeeded. The gray matter seemed to have stiffened.

JC: If English didn’t have a writing system and you were designing one from scratch, what would you do differently?

GG: Wow, we have six kids we’ve taught to read – we would do a lot differently! The ideal is to have one symbol for each meaningful sound in the language. English would need more vowels and fewer consonants. Life would actually be more pleasant without ‘c’, ‘j’, ‘q’ and ‘x’. If you removed those and added about six vowels we could come up with a spelling system that was predictable and easy to learn.

JC: Anything else you’d like to say?

GG: One of the most remarkable things about the Nakui language is how sophisticated and complex it is. Unblended with other languages, it is extremely consistent in its grammar. Although it is in a constant state of change (rapid change relative to written languages of the world), it remains organized. This order is not to the credit of the society that speaks it, it happens utterly in spite of them. They are completely unaware of the structure of their own grammar and are perhaps the most disorderly people on the planet. The aspects of life over which they hold sway are corrupt and miserable, but in this small, unmanaged area of their lives, a glimpse of the divine still peeks out. The God of order, who created them in His own image, gave them an innate ability to communicate complex ideas in and orderly way. Like Greek, they specify singular, dual and plural. They have six tenses (English has only three), and 11 personal pronouns (English has only six). Every verb is conjugated to carry this specificity with extreme consistency. The verb to ‘go’ is the only irregular verb in the whole Nakui language. English, although vast, is a disheveled mess compared to what is spoken by these stone age people in the swamps of interior New Guinea.

Related posts:

Imaginary gold, silver, bronze, …

The previous post gave a relationship between the imaginary unit i and the golden ratio. 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

\phi_n = n + \frac{1}{\phi_n}

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

2 \sin \left( i \log \phi_n \right) = ni

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 posts:

“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.

Real World Haskell

I’m reading Real World Haskell because one of my clients’ projects is written in Haskell. Some would say that “real world Haskell” is an oxymoron because Haskell isn’t used in the real world, as illustrated by a recent xkcd cartoon.

It’s true that Haskell accounts for a tiny portion of the world’s commercial software and that the language is more popular in research. (There would be no need to put “real world” in the title of a book on PHP, for example. You won’t find a lot of computer science researchers using PHP for its elegance and nice theoretical properties.) But people do use Haskell on real projects, particularly when correctness is a high priority.[1] In any case, Haskell is “real world” for me since one of my clients uses it. As I wrote about before, applied is in the eye of the client.

I’m not that far into Real World Haskell yet, but so far it’s just what I was looking for. Another book I’d recommend is Graham Hutton’s Programming in Haskell. It makes a good introduction to Haskell because it’s small (184 pages) and focused on the core of the language, not so much on “real world” complications.

A very popular introduction to Haskell is Learn You a Haskell for Great Good. I have mixed feelings about that one. It explains most things clearly and the informal tone makes it easy to read, but the humor becomes annoying after a while. It also introduces some non-essential features of the language up front that could wait until later or be left out of an introductory book.

* * *

[1] Everyone would say that it’s important for their software to be correct. But in practice, correctness isn’t always the highest priority, nor should it be necessarily. As the probability of error approaches zero, the cost of development approaches infinity. You have to decide what probability of error is acceptable given the consequences of the errors.

It’s more important that the software embedded in a pacemaker be correct than the software that serves up this blog. My blog fails occasionally, but I wouldn’t spend $10,000 to cut the error rate in half. Someone writing pacemaker software would jump at the chance to reduce the probability of error so much for so little money.

On a related note, see Maybe NASA could use some buggy software.

Where combinator names come from

Today I found out where the one-letter names of some functions in combinatory logic come from. I’d seen these before (for example, in To Mock a Mockingbird) but I had no idea what inspired the names.

These functions — I, K, S, T, and Z — are known as the Schönfinkel combinators, and their names are somewhat mnemonic in German. (Only somewhat. Don’t get your hopes up.)

DefinitionNameName origin
λx. xIIdentitätsfunktion (identity function)
λx,y. xKKonstanzfunktion (constant function)
λx,y,z. xz(yz)SVerschmelzungsfunktion (amalgamation function)
λx,y,z. xzyTVertauschungsfunktion (exchange function)
λx,y,z. x(yz)ZZusammensetzungsfunktion (composition function)

Source: Practical Foundations of Mathematics, footnote on page 89. Available online here.

If you’re not familiar with the notation in the function definitions, see this introduction to lambda calculus.

* * *

For a daily dose of computer science and related topics, follow @CompSciFact on Twitter.

CompSciFact twitter icon

What good is an old weather forecast?

Why would anyone care about what the weather was predicted to be once you know what the weather actually was? Because people make decisions based in part on weather predictions, not just weather. Eric Floehr of ForecastWatch told me that people are starting to realize this and are increasingly interested in his historical prediction data.

This morning I thought about what Eric said when I saw a little snow. Last Tuesday was predicted to see ice and schools all over the Houston area closed. As it turned out, there was only a tiny amount of ice and the streets were clear. This morning there actually is snow and ice in the area, though not much, and the schools are all open. (There’s snow out in Cypress where I live, but I don’t think there is in Houston proper.)

Aftermath of last Tuesday’s storm

Related posts:

Time and Productivity

Contractors were working on my house all last week. I needed to be home to let them in, to answer questions, etc., but the noise and interruptions meant that home wasn’t a good place for me to work. In addition, my Internet connection was out for most of the week and I had a hard disk failure.

Looking back on the week, my first thought was that the week had been an almost total loss, neither productive nor relaxing. But that’s not right. The work I did do made a difference, reinforcing my belief that effort and results are only weakly correlated. (See Weinberg’s law of twins.)

Sometimes you have a burst of insight or creativity, accomplishing more in a few minutes than in an ordinary day. But that didn’t happen last week.

Sometimes your efforts are unusually successful, either because of the preparation of previous work or for unknown reasons. That did happen last week.

Sometimes you simply work on more important tasks out of necessity. Having less time to work gives focus and keeps work from expanding to fill the time allowed. That also happened last week.

* * *

I did get out of the house last Tuesday and wrote about it in my previous post on quality over quantity. This turned out to the theme of the week.