Home Updates Messages SandBox

Strange Loops and Programming

Meta Level

Hello!

I said 'Hello!'

Actually, I just wrote 'I said "Hello!"'

Those sentences are an example of what we call "going meta". The second sentence talks about the first, and the third sentence talks about the second, each going level up from the previous ones in the meta-level. Actually, this paragraph is also part of that sequence, talking about the third sentence.

You can continue that sequence indefinitely, going ever up in the meta levels of sentences. But wait, you can also talk about the infinite sequence of sentences, and that's also a higher meta-level!

In fact, whatever you say, you can subsequently talk about it, and there is an infinite number of infinities of meta levels. Or even more than that. That is possible because of a special trick in our language.

If you look at the second and third sentences, you will note that they increase their meta level by directly quoting the sentence they are talking about. The subsequent paragraphs, however, do no such thing. They merely refer to previous sentences by pointing to them. This, at the first sight, is just a convenience, however, it actually is a very powerful technique that changes everything.

Strange Loops

A reference lets a sentence talk about an infinite number of sentences, or about sentences that are only imagined, or about all possible sentences, etc. In particular, it allows a sentence to talk about itself, mixing in one statement two different meta-levels, and that leads to interesting effects. Consider this sentence:

This sentence is true.

At first glance there is nothing suspicious in it. It's a little bit trivial, sure, but otherwise there is nothing wrong with it. But consider the negation of that sentence:

This sentence is false.

Is that sentence true or false? Let's see, if we assume that it is true, then it says that it is false, so it is wrong. So it's false, right? But wait, if we assume it's false, then it's right, so it must be true! See what is happening? By referring to itself, the sentence can twist itself in such a way, that you can never be right about its truth! Sentences like this one are called "liar paradox", from the story of a liar who says "I am lying", leading to a similar problem.

It's possible to have this paradox with more than just a single sentence:

The following statement is true.

The preceding statement is false.

In fact, you can make it arbitrarily complex, and spanning as many meta-level as you want. The only requirement is that you have to cross from a lower to a higher level at some point.

Naive Set Theory

A similar problem of self-reference appears in many branches of mathematics. For instance, in the set theory, when you take the straightforward definition of a set: a collection of anything. This, in particular, allows your sets to contain other sets, or even itself. What's wrong with that? Well, that lets us make the equivalent of a liar paradox: consider a set of all sets that don't contain themselves. Would that set contain itself? If we assume yes, then it's wrong, as it can only contain sets that don't contain itself. If we assume no, then again we are wrong, as it would have to contain itself then…

Mathematicians really hate when things like that happen, as they really prefer to be right at all times. That's why they generally try to define things so that statements like that are impossible to form. In case of the set theory, for instance, one solution is to say that sets have levels, and a set of given level can only contain sets of a lower level (it's a meta-set of those sets). This creates a nice hierarchy, and prevents the set from referring to itself and forming a strange loop.

Gödel's Theorem

All would have been good in the world of mathematics, if not for a certain malicious mathematician who proved, that any formal system that includes the natural numbers will always include paradoxical statements like that (he did that by translating the formal system itself into operations on natural numbers, so that the numbers can refer to themselves…). It really spoiled the day for a lot of people, and we have since learned to live with the knowledge that not all questions have an answer, and that there is always a paradox hiding somewhere.

Meta Levels in Programming

Any problem in computer science can be solved with another layer of indirection. But that usually will create another problem. – David Wheeler

Programmers love meta-levels. We use them everywhere, and they are prevalent in programming languages. Pre-processors, templates, types, function calls, classes, scripts, static code analyzers, optimizers, profilers, configurations, domain-specific languages, comments, tests, documentation, design patterns, micro-services, configuration management, etc. – those all are examples of different tools for creating meta-levels and reasoning about what the computers do.

I'm going to show some practical examples of those from my experience, and I will try to show how jumping the levels inevitably leads to similar problems as we seen with the paradoxes above, making the programs harder to understand.