It’s MetaTurtles, all the way down

(This is a postscript to my previous entry about “compiler compilers”)

A baby version of English, like the one understood by SHRDLU can be used to construct sentences about colored blocks. It is a language and as such, it has syntax rules (which tell you how to distinguish a well-formed sentence from gobblygook) and it has semantic rules (which tell you what a well-formed sentence actually means). This particular baby language is pretty much restricted to talking about blocks, positions and colors.

Java is a baby language too. It lets you construct sentences about computations – such as “do something five times”. It’s a language, and like all languages it has syntax rules and semantic rules.

There are languages such as BNF which allow you to describe syntax rules, in the same way that “baby english” allowed you to talk about shapes. So, a sentence in BNF could describe the syntax of the java language. Like any language, BNF has syntax rules and semantic rules which tell you what a valid BNF sentence looks like, and what it means. Let’s just clarify the previous-but-one sentence – a syntactically valid BNF sentence can be “intepreted” (according to the semantics of BNF) to describe the syntax of the Java language.

Now, for the first time, we have a chain; sentences in one language (BNF) are describing the syntax rules of another (Java). And those syntax rules just tell us which sentences make up valid Java programs. When we have chain, some people start using the word meta – ie. BNF is a meta-language.

(Question 1: What language do you use to describe the syntax of BNF?)

There are also languages such as OpenJava. They let you construct sentences about Java programs – for example, “add a new method foo() to class Bar()”. OpenJava is certainly a language – it has well-defined syntax rules and semantic rules. However, we’ve also got a chain here – sentences in the OpenJava language are referring to sentences in the Java language. It’s another case of a meta-language.

Earlier, we were looking at “operational semantics” and we noted that it was just a language too. It has syntax rules and semantic rules, like any other language. These rules are what you’ve understood when you can “read” operational semantics and know what they “mean”. A sentence in the “operational semantics” language describes the “meaning” of a programing language. Note that the “operational semantics for Java” sentence doesn’t describe the meaning of a particular java program. It describes a /mapping/ from syntactically correct Java programs to programs which run on a “hypothetical machine”.

And, of course, these “hypothetical machine programs” are just sentences in another language – one which has its own syntax and semantics. It’s turtles all the way down!

(Question 2: What language do you use to describe the semantics of “operation semantics”?)

Now let’s leave programming languages for a moment and look at Proper Grown-up English. It’s a pretty crazy language. The syntax rules are mixed up (and gradually changing), and the semantics are subtle, ambiguous and take years to grasp. But one if it’s cooler properties is that sentences in the english language can refer to other sentences in the english language. We can say things like ‘”nearly finished now” has three words’. We can also get really self-referential and have sentences which describe themselves, such as “multisyllabic”. Our dictionaries define the meaning (ie. the semantics) of english words by using english! There’s clearly a bootstrapping problem here – you couldn’t learn English from a dictionary unless you already knew some English. But English is clearly a self-describing language, at least to some extent.

So, let’s return to the two questions we left above. One obvious answer to the questions would be to use “English” to describe the syntax of BNF, and semantics of “operational semantics”. That’s the approach that a CS lecturer would take.

But, you can actually use BNF to describe the syntax of BNF. The expressive power of the language is enough, and the structure of the language is simple enough, that it can describe itself. BNF can be used to describe the syntax of any context-free language. BNF itself is a context-free language. Therefore it can describe it’s own syntax.

Before we try to answer the second question, we should look more closely at what we mean by “semantics”. A few paragraphs ago, we noted that the operational semantics for Java defined a /mapping/ from syntactically valid java programs to programs which run on some hypothetical machine. Haven’t we just moved the goalposts? We’ve not actually established some Platonic “meaning” for each Java program. We’ve just restated in the problem in terms of some “hypothetical machine”.

No, we’ve not cheated. This is an intrinsic property of semantics. You can’t attain a “Platonic ideal” of the semantics of Java. You can only restate the problem in some other form. Operational semantics tells you how to interpret (syntactically correct) Java programs as programs on a hypothetical machine. Denotational semantics tell you how to interpret them as mathematical domains. But it’s as if you are translating a story between English, French and German, hoping to get closer to the true meaning.

At some point, you just have to “get” one of the languages, whether that’s English or some other language, and be content that you understand with the version of the problem restated in that language. You didn’t learn English (or whatever your first language is) by studing grammar books and reading dictionaries. You learned it through some “side channel” – behavioural reenforcement as an infant.

So, let’s finally return to the one outstanding question. Can “operational semantics” be used to define the semantics of “operational semantics”? Hmm, I should leave this as an exercise for the reader. I myself will return to the question once my head has stopped hurting!