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!

2 thoughts on “It’s MetaTurtles, all the way down”


  1. 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”.

    Hmmm. Douglas Hofstadter would argue that structure-preserving mappings (isomorphisms) and meanings are basically the same thing. How do you see them as differing, Andy? You kind of accept that all useful semantics are translations yourself, but this statement seems to suggest you don’t want to go the whole hog. What do you think the “true meaning” of a language could be?


    you can actually use BNF to describe the syntax of BNF.
    […]
    Can “operational semantics” be used to define the semantics of “operational semantics”?

    I think you’re maybe making a category error here – as phrased, the two questions do not quite seem analogous to me.

    BNF is just a language for describing the syntax of languages, it’s not the only one. As you say, BNF can be used to describe the syntax of a large set of languages (i.e. all context-free grammars), including itself.

    So, I think you are observing that there exist certain context-free grammars, such as BNF, that can be used to represent the syntax of all context-free grammars.

    In which case, the analogous question would seem to be: do there exist certain systems of operations semantics that can be used to represent the semantics of all systems of operational semantics?

    Then, if you then accept Hofstadter’s “isomorphisms induce meaning” philosophy at least as far as using operational semantics goes – which you would seem to – and I understand correctly that we’re talking about the operational semantics of Turing-complete languages here, then I think that (qualms about the status of the Church-Turing thesis aside) the answer to this question is “yes, and the systems in question are such things as universal Turing machines.” (Although my head is hurting a little now too.)

  2. You kind of accept that all useful semantics are translations yourself, but this statement seems to suggest you don’t want to go the whole hog. What do you think the “true meaning” of a language could be?

    Ah, no. My intention with that sentence was just to remind myself which “level” I was discussing. I spend a lot of time working with abstract syntax trees, and informally people usually say that they “capture the meaning” of a particular program – at least, independent of formatting and syntactic sugar. So, I was reiterating the fact that a given operation semantics has the type “java_program -> abstract_machine_program”.

    I agree that semantics must just be isomorphisms, at least up until the point where you end up in a language which you just “get”, and then it starts getting tricky.

    Thanks a lot for your comments. I’ll chew over them once I’ve woken up more. I find that I’m very happy thinking about computer programs, fairly happy thinking about type systems and meta-programs, but really quite unused to thinking about formal semantics. So I probably often make category errors and don’t notice it.

Comments are closed.