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


Break from blogging

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.


What is first-order logic?

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:

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.


  1. The exact set of connectives varies by the source, but it does not really matter. Having ∧, ∨, and ¬ is enough, because you can express all the other logical connectives in terms of them.


Please publish changelogs

Signs of changes in a log.

Signs of changes in a log.

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.