<p>The idea of comparing the <a href="https://stackoverflow.com/q/2427496/781723">expressivity</a> of languages objectively using various metrics is very interesting.</p>
<p>A <a href="https://langdev.stackexchange.com/a/2016/285">particularly interesting answer</a> is Matthias Felleisen's formal notion of expressivity.</p>
<p>I confess I don't follow the maths fully at this point, but looking at the idea, would it be possible to subvert it and, given any language definition, procedurally create a new more expressive language (by this measure) that is not actually more expressive in <em>human terms</em>?</p>
<p>Could this process be repeated ad nauseam and defeat the expressiveness measure altogether?</p>
<p>I feel like there should be a link to Gödel here as well, though I can't quite place it.</p>

<language-comparison><computability>
Can Felleisen's expressivity metric be abused to construct ever more expressive languages that aren't actually more expressive?
CC BY-SA 4.0
2023-07-07T22:31:56.097Z
I think that the relevant Gödelian concept is [Gödel's speedup theorem](https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem).
Corbin
CC BY-SA 4.0
2023-07-08T07:22:32.520Z
I see what you are getting at (a more expressive langage can produce a shorter proof) but that is not what I meant. More that you could perhaps construct an infinite sequence of more expressive languages but the Felleisen definition, apply Godel numbering or make self referential and disappear like the proverbial [Oozlum bird](https://en.wikipedia.org/wiki/Oozlum_bird)
Bruce Adams
CC BY-SA 4.0
2023-10-15T22:08:49.340Z
Any metric can be abused, but that doesn’t make the idea of metrics useless
jmoreno
<p>So I'm not really an expert on this subject, all I know is from David Young's post. Please correct me if this is wrong.</p>
<p>I think I found a way to add infinitely add expressiveness to any stack based language. This could probably be generalized to any language type.</p>
<p>In the base, least expressive version of the language, we have an operator <code>regswap_0</code>. It pops one element from the stack and copies it to the <span class="math-container">$r_0$</span> first register. Now assume this language has no way of actually reading from this register. This is <span class="math-container">$L_0$</span>.</p>
<p>Now for each version N, we add a builtin <span class="math-container">$\mathit{regswap}_n$</span>. This builtin will pop a value from the stack, copy it to <span class="math-container">$r_n$</span>. Then take the value from register <span class="math-container">$r_{n-1}$</span> and push it back onto the stack.</p>
<p>Now we can construct a program in this form:</p>
<pre><code>input regswap_(n-1) regswap_n &quot;1&quot; equals if [ loop [ ] ]
</code></pre>
<p>If we wanted to compile this to the n-1 version of the language, that didn't have <code>regswap_n</code>, we'd need to either add a <code>dup</code> instruction after input or remove the <code>regswap_(n-1)</code> instruction. Neither of which are local transformations.</p>
<p>Specifically these statements are no longer equivalent in language N</p>
<pre><code>1 regswap_(n-1) pop
[empty string]
</code></pre>
<p>Would always be have the same effect in language N-1.</p>
<p>This we can use this technique to construct an arbitrarily long chain of languages with increasing expressiveness.</p>
<p>This won't necessarily ever increase the expressiveness past any other language. You may be able to infinitely increase the expressiveness of Fractran without ever &quot;overtaking&quot; brainfuck, in the same way you can infinitely add to 1 without ever passing 2.</p>

CC BY-SA 4.0
2023-07-06T09:21:26.920Z
2023-08-11T16:41:58.550Z
2023-08-11T16:41:58.550Z
mousetail 'he-him'
<p>Duplicating my comment on that answer, a <code>quote</code> macro with the behavior of taking an expression and returning its string representation seems to provide infinite expressivity to any language. If a language has it, a context like <code>while (quote(&lt;hole&gt;) == &quot;&lt;string representation of e_1&gt;&quot;) {}</code> will prove observational non-equivalence for any given terms e_1 and e_2. Consequently, this means no other addition to the language can improve expressivity, since there are no observational equivalences left to break (except for between identical expressions, but it cannot be broken regardless).</p>
<p>By the way, since <code>quote</code> can be implemented in the C preprocessor as <code>#define quote(x) #x</code>, C is apparently the pinnacle of expressiveness.</p>

CC BY-SA 4.0
2023-07-06T09:53:20.770Z
2023-07-06T09:53:20.770Z
abel1502
# Can Felleisen's expressivity metric be abused to construct ever more expressive languages that aren't actually more expressive?
Posted by: username_0 on 2023-07-06
The idea of comparing the [expressivity](https://stackoverflow.com/q/2427496/781723) of languages objectively using various metrics is very interesting.

A [particularly interesting answer](https://langdev.stackexchange.com/a/2016/285) is Matthias Felleisen's formal notion of expressivity.

I confess I don't follow the maths fully at this point, but looking at the idea, would it be possible to subvert it and, given any language definition, procedurally create a new more expressive language (by this measure) that is not actually more expressive in *human terms*?

Could this process be repeated ad nauseam and defeat the expressiveness measure altogether?

I feel like there should be a link to Gödel here as well, though I can't quite place it.
**Tags:** language-comparison computability
> **Comments:**
> **username_1**: I think that the relevant Gödelian concept is [Gödel's speedup theorem](https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem).  
> **username_0**: I see what you are getting at (a more expressive langage can produce a shorter proof) but that is not what I meant. More that you could perhaps construct an infinite sequence of more expressive languages but the Felleisen definition, apply Godel numbering or make self referential and disappear like the proverbial [Oozlum bird](https://en.wikipedia.org/wiki/Oozlum_bird)  
> **username_2**: Any metric can be abused, but that doesn’t make the idea of metrics useless  
---
## 2 answers
### Answer by username_4 on 2023-07-06. Score: 10
Duplicating my comment on that answer, a `quote` macro with the behavior of taking an expression and returning its string representation seems to provide infinite expressivity to any language. If a language has it, a context like `while (quote() == "") {}` will prove observational non-equivalence for any given terms e\_1 and e\_2. Consequently, this means no other addition to the language can improve expressivity, since there are no observational equivalences left to break (except for between identical expressions, but it cannot be broken regardless).

By the way, since `quote` can be implemented in the C preprocessor as `#define quote(x) #x`, C is apparently the pinnacle of expressiveness.
---
### Answer by username_3 on 2023-07-06. Score: 1
So I'm not really an expert on this subject, all I know is from David Young's post. Please correct me if this is wrong.
I think I found a way to add infinitely add expressiveness to any stack based language. This could probably be generalized to any language type.
In the base, least expressive version of the language, we have an operator regswap_0. It pops one element from the stack and copies it to the $r_0$ first register. Now assume this language has no way of actually reading from this register. This is $L_0$.
Now for each version N, we add a builtin $\mathit{regswap}_n$. This builtin will pop a value from the stack, copy it to $r_n$. Then take the value from register $r_{n-1}$ and push it back onto the stack.
Now we can construct a program in this form:
input regswap_(n-1) regswap_n "1" equals if [ loop [ ] ]

If we wanted to compile this to the n-1 version of the language, that didn't have regswap_n, we'd need to either add a dup instruction after input or remove the regswap_(n-1) instruction. Neither of which are local transformations.
Specifically these statements are no longer equivalent in language N
1 regswap_(n-1) pop
[empty string]

Would always be have the same effect in language N-1.
This we can use this technique to construct an arbitrarily long chain of languages with increasing expressiveness.
This won't necessarily ever increase the expressiveness past any other language. You may be able to infinitely increase the expressiveness of Fractran without ever "overtaking" brainfuck, in the same way you can infinitely add to 1 without ever passing 2.
---
