<p>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 <span class="math-container">$L$</span> is extended by some feature, we say that the extended language <span class="math-container">$L^{+}$</span> is <strong>macro expressible</strong> when there is a <em>local</em> syntax-directed translation (a macro translation) from <span class="math-container">$L^{+}$</span> to <span class="math-container">$L$</span> that keeps the features in <span class="math-container">$L$</span> fixed. (Note the word &quot;local&quot; -- it means we are not allowed to transform the whole program just to accommodate a new feature.)</p>
<p>The original reference is: Felleisen, Matthias. (1991). <a href="https://doi.org/10.1016/0167-6423(91)90036-W" rel="nofollow noreferrer">On the expressive power of programming languages.</a> Science of computer programming, 17(1), 35–75.</p>

CC BY-SA 4.0
2024-01-19T15:43:47.687Z
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.
Evan Aad
CC BY-SA 4.0
2024-01-19T07:35:06.997Z
2024-01-19T07:35:06.997Z
Andrej Bauer
<p><a href="https://en.wikipedia.org/wiki/Semantics_(computer_science)" rel="nofollow noreferrer">The Wikipedia article about programming language semantics</a> distinguishes three major approaches to semantics: denotational, operational, and axiomatic.</p>
<p>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?</p>
<p>For instance, if we wish to describe the meaning of the Java line of code</p>
<p><code>int b = a++;</code></p>
<p>we can say that it has the same meaning as</p>
<p><code>int b = a; a++;</code></p>
<p>and that <code>a++;</code> has the same meaning as <code>a = a + 1;</code>.</p>

CC BY-SA 4.0
2024-01-18T08:38:26.170Z
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`?
Andrej Bauer
CC BY-SA 4.0
2024-01-18T18:53:03.213Z
@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.
Evan Aad
CC BY-SA 4.0
2024-01-18T18:56:16.230Z
@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.
Evan Aad
<semantics><term-rewriting-systems>
Is there such a thing as "transformational semantics"?
Evan Aad
# Is there such a thing as "transformational semantics"?

(Asked by: username_0 on 2024-01-17)

[The Wikipedia article about programming language semantics](https://en.wikipedia.org/wiki/Semantics_(computer_science)) 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;`.

**Tags:** semantics, term-rewriting-systems
> **Comments:**
> **username_1**: 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`?  
> **username_0**: @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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2024-01-19. Score: 2

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.](https://doi.org/10.1016/0167-6423(91)90036-W) Science of computer programming, 17(1), 35–75.

> **Comments:**
> **username_0**: 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.  

---

