[tsimionescu]

I don't think this formalization does a great job of what we intuitively mean by expressive power.

For one thing, there is no real way to use this definition to compare different languages, only the same language with one extra feature.

For another, even for individual features, it is too coarse. The very fact that it doesn't consider syntactic sugar expressive is wrong - most people would agree that a language with more syntax sugar is more expressive, since it allows you to avoid writing boilerplate. By this definition, list comprehensions and switch expressions for example don't add expressive power to a language.

Even if we ignore syntax sugar, the comments point out another counterintuitive property of this definiton: any language which includes a facility to convert expressions to ASTs is maximally expressive, since that facility can be used to distinguish any two expressions. This includes things like Lisp's `quote' special form or C's # macro, but also built-in code parsers. So, C++ for example added no expressive power to C by this definition, since C was already maximally expressive:

  #define quote(x) #x

  if (strcmp("3 + 3", quote(3 + 3)) {return 1;}

[AkshatM]

I would push back on the interpretation that syntactic sugar, by virtue of making programs shorter, is more expressive. APL folds entire compositions into single character sequences, but one would probably not argue that it is more expressive than Brainfuck.

Rather, it seems expressiveness as used in common parlance is closer to ease of comprehension. We like programs that are easy to "think of", that are "natural" to write in that they are succinct and "natural" to read in that they mimic what you are conceptually trying to accomplish. This has very little to do with programming language design and more the experience of the language user - aesthetics, really.

[unwind]

Uh I think the CS-theoretical part of your comment kinda whooshes over my head, but I think it's good to clarify what you're doing with the return value of strcmp().

I'm sure you probably know this, but for non-C-programmers it's not obvious: strcmp() returns 0 when the strings are equal, <0 if the first string is lexicographically less than the second, and >1 otherwise.

Since the two strings handed to strcmp() in your snippet are equal, it will return 0 and the if will not execute.

[avgcorrection]

The C preprocessor is an example where expressiveness definitely stops being an honorific and starts being a liability.

But then you are perhaps back to square one, since the motivation for the question was to get away from the Turing Complete categorization which says nothing about whether it is practical to solve certains problems in a given language.