The Wikipedia article about programming language semantics distinguishes three major approaches to semantics: denotational, operational, and axiomatic.

What is the approach called when the meaning of a program is described by transforming/rewriting it as a simpler program that has the same meaning?

For instance, if we wish to describe the meaning of the Java line of code

int b = a++;

we can say that it has the same meaning as

int b = a; a++;

and that a++; has the same meaning as a = a + 1;.

  • $\begingroup$ You can't give a meaning to all of the programming langauge this way, so it's not semantics in the proper sense of the word. Can you say a bit more about the motivation for this question, as there are several possible answers here. Also, does the interpretation have to go from language X back to itself, or can it taget another language Y? $\endgroup$ Jan 18 at 8:38
  • $\begingroup$ @AndrejBauer Back to itself. I realize that you can't give a meaning to all of the programming language this way, just as you can't have a definition by recursion without specifying the base case. But the existence of a base case doesn't change the fact that the definition is by recursion, and analogously, in my opinion, the fact that you can't give meaning to all of the programming language this way doesn't mean that it's not semantics in the proper sense of the word. $\endgroup$
    – Evan Aad
    Jan 18 at 18:53
  • $\begingroup$ @AndrejBauer As for motivation, I noticed that some programming language constructs can be explained naturally by reducing them to other constructs of the same language. I gave a couple examples in my post. This roused my curiosity whether there is a name to this method of giving meaning to programs, as this semantics paradigm is not listed on the Semantics Wikipedia page. $\endgroup$
    – Evan Aad
    Jan 18 at 18:56

1 Answer 1


There are several possibilities here, but I think the closest one to what you have in mind is Felleisen's macro expressibility: when a programming language $L$ is extended by some feature, we say that the extended language $L^{+}$ is macro expressible when there is a local syntax-directed translation (a macro translation) from $L^{+}$ to $L$ that keeps the features in $L$ fixed. (Note the word "local" -- it means we are not allowed to transform the whole program just to accommodate a new feature.)

The original reference is: Felleisen, Matthias. (1991). On the expressive power of programming languages. Science of computer programming, 17(1), 35–75.

  • $\begingroup$ Thank you. What if we are allowed to transform the whole program? Could you point to a reference to that? In fact, I'd appreciate it if you would list all of the possibilities that you hinted at in your opening words. $\endgroup$
    – Evan Aad
    Jan 19 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.