This is a weblog about computing, culture et cetera, by Miikka Koskinen. Read more.

I’m going to take a break from blogging on quanttype. I haven’t enjoyed writing the posts lately and the quality has suffered accordingly. There’s no point in forcing it.

The future of blogs that go on hiatus is always uncertain. I’m not going to make any promises.

I want to tell you about descriptive complexity theory, but it’s hard to explain if you don’t know what first-order logic is. Let’s have a tiny refresher.

Even if you haven’t heard about first-order logic, you’re probably familiar with it anyway. It’s the basic language of logic with the following elements:

- logical connectives ∧ for conjunction (AND), ∨ for disjunction, and ¬ for negation (NOT)
- existential quantifier \(\exists\) and universal quantifier \(\forall\)
- equality symbol \(=\)

Using this language, you can talk about a domain which is a set of values. It’s like having a database and writing queries against it using the first-order logic as the query language. For example, the statement \(\exists x (\exists y (\neg (x = y)))\) asserts that there at least two distinct values in the domain.

First-order logic, abbreviated FO, is not very powerful. You can make it more powerful by adding some extra predicates. For example, if you want to talk about natural numbers, you could add the predicates + and <. Then you can state theorems like \(\forall x (\forall y (x \leq x + y))\). The resulting logic is called FO(+,<).

FO is called *first-order* logic, because the existential and the universal quantifiers quantify over atomic values. In second-order logic (SO), you’re allowed to quantify over predicates. In third-order logic, you’re allowed to quantify over predicates of predicates etc. This gives you a lot of leverage. For example, in SO you can assert that the domain contains even number of elements. This is not expressible in FO.

When you release a new version of your library, please do a favor to your users and publish a changelog entry highlighting the most important changes.

The changelog tells your users what’s new – it gives them a reason to upgrade. It tells them what’s broken, so they won’t be surprised when nothing works anymore.

I’ve heard this quip that the changelog is one of the most important pieces of documentation, because even if the other documentation is lacking, it tells you what is outdated about the knowledge you have discovered yourself.

Sure, the commit history is always there, but usually it’s hard to understand. It’s easier to write a passable changelog than to curate the history.

How to do it in practice? keep a changelog has elaborate instructions. If you want to follow them, that’s great, but as long as you use a consistent format with version numbers and release dates, I’m happy.

For more posts, see archive.