13
$\begingroup$

The idea of comparing the expressivity of languages objectively using various metrics is very interesting.

A particularly interesting answer 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.

$\endgroup$
3
  • 1
    $\begingroup$ I think that the relevant Gödelian concept is Gödel's speedup theorem. $\endgroup$
    – Corbin
    Commented Jul 7, 2023 at 22:31
  • $\begingroup$ 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 $\endgroup$
    – Bruce Adams
    Commented Jul 8, 2023 at 7:22
  • $\begingroup$ Any metric can be abused, but that doesn’t make the idea of metrics useless $\endgroup$
    – jmoreno
    Commented Oct 15, 2023 at 22:08

2 Answers 2

Reset to default
10
$\begingroup$

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(<hole>) == "<string representation of e_1>") {} 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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .