<p>Is this possible?</p>
<p>Is there an accepted (and unambiguous) notion of &quot;expressive power&quot; that could differ between two different <em>Turing-complete</em> languages?</p>
<p>It seems like, for example, Python is intuitively much more &quot;expressive&quot; (in some sense) than an assembly language since Python's high-level constructs (like <code>class</code>es, functions and even <code>for</code> loops) often make it much easier to organize and think about code compared with assembly languages.</p>
<p>On the other hand, any program you can write in Python you can also write in an assembly language since both languages are Turing-complete (ignoring library availability, etc).</p>
<p>But do you <em>really</em> want to implement complex algorithms in <a href="https://en.wikipedia.org/wiki/FRACTRAN" rel="noreferrer">FRACTRAN</a> or as a <a href="https://arxiv.org/abs/1904.09828" rel="noreferrer"><em>Magic: the Gathering</em> deck</a>? Why not?</p>
<p>Is there a way to give a real, unambiguous definition to this intuitive notion of &quot;expressiveness?&quot;</p>

<language-comparison>
How can we compare expressive power between two Turing-complete languages?
CC BY-SA 4.0
2023-07-05T07:43:49.457Z
Too vague for an answer, but: a kind of reverse-[Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity) would make sense. When you have a program that solves a problem, you can measure its time complexity, space complexity, but also its length (in bytes), its readability/maintainability, etc. Use all these measures to attribute a score to each program. Then if you have a list of standard problems in order of difficulty, you could "grade" a language by the minimum scores of programs that solves these problems.
Stef
CC BY-SA 4.0
2023-07-05T07:52:07.747Z
For instance, compare a Turing-machine's tape with C's allocation of memory. In C you can use pointers to quickly access any memory you've allocated. On a Turing-machine, you need to move the data head one cell at a time to access memory. Although both are Turing-complete, solving a problem that requires large amounts of memory is going to be slower with a Turing-machine, because you need time to move the data head back and forth - you wouldn't need that time if you had pointers like in C. So, "pointers" are a feature that noticeably reduces the time-complexity of programs.
Stef
CC BY-SA 4.0
2023-07-05T08:56:04.760Z
Good idea but you have to be very careful of your costs. Do you include library functions and system calls? What about machine level instructions like microcode?
You might argue the measurement should be relative. So you do include those if you are comparing with a turing machine but you might not if comparing two languages that both assume an x86 architecture.
Bruce Adams
CC BY-SA 4.0
2023-07-05T16:49:17.433Z
https://stackoverflow.com/q/2427496/781723
D.W.
<p>Surprisingly <strong>yes</strong>, this is possible!</p>
<p>This is actually pretty important for people that work on optimizing compilers. If I add this new feature, will it break any existing optimization pass? I will show why this is a concern later in the answer.</p>
<p>And this is good since all of us are interested in programming languages. Surely we should have at least one clear-cut way to distinguish between them, beyond the names of keywords, etc! Most people would rather write a large system in <em>[insert your favorite language here]</em> than, say, <a href="https://en.wikipedia.org/wiki/Befunge" rel="noreferrer">Befunge</a> or <a href="https://en.wikipedia.org/wiki/INTERCAL" rel="noreferrer">INTERCAL</a>. But those languages <em>are</em> Turing-complete.</p>
<p>So, what's going on here?</p>
<p>Not only that, the concept we need here has significance in formal semantics beyond this question. I'll briefly mention this at the end of the answer.</p>
<p>Can you ever distinguish between <code>2 * 3</code> and <code>3 + 3</code> in a programming language? Are you <em>sure</em>? Are there any &quot;reasonable&quot; languages in which you can distinguish between these? What, exactly, would it mean to be able to distinguish between them and how can we give a definition for &quot;this language distinguishes between these things?&quot; Read on to find out more!</p>
<p>The concept we need is called &quot;observational equivalence.&quot;</p>
<p>A roadmap:</p>
<ul>
<li>First I'll give an intuitive description of how you could understand the statement <em>&quot;feature X adds expressive power to language L&quot;</em>.</li>
<li>Next, I'll need to talk about programs that have a hole in them. These are called <em>&quot;one-hole contexts&quot;</em>. Sometimes this is abbreviated to just <em>&quot;context.&quot;</em></li>
<li>Then I'll use one-hole contexts to define <em>&quot;observational equivalence.&quot;</em> This is one way to talk about certain programs being &quot;equivalent.&quot;</li>
<li>Finally, we will see that we can say adding feature X to language L makes the language <em>more expressive</em> if, by adding feature X, we end up with <em>fewer</em> observational equivalences in the resulting language L+X. That might sound backward. I'll get to this, though.</li>
</ul>
<p>The <strong>key idea</strong> is this: Consider taking a Turing-complete language L and adding feature X. Now think about how we could translate code written in L+X back into into L. If feature X makes the language &quot;more expressive,&quot; then this transformation will require you to apply a large-scale, <em>&quot;global&quot;</em> transformation. On the other hand, if language L and L+X are &quot;equally expressive,&quot; then L+X can be transformed into L using only a <em>&quot;local&quot;</em> transformation.</p>
<h1>Inspiration</h1>
<p>I will state upfront that this answer (and the way I framed the original question) is inspired by <a href="https://www.youtube.com/watch?v=43XaZEn2aLc" rel="noreferrer">Shriram Krishnamurthi's excellent and approachable 2019 talk</a> about Matthias Felleisen's paper &quot;On the Expressive Power of Programming Languages.&quot; Anyone who is interested in this question should absolutely watch it. The corresponding paper is <a href="https://www.sciencedirect.com/science/article/pii/016764239190036W" rel="noreferrer">here</a>.</p>
<p>I actually think that talk would be interesting to everyone here, in fact. There are many questions that have variations on &quot;... what if I add feature X to a language ...&quot; and this talk gives a way to understand one aspect of that kind of question!</p>
<p>Incidentally, I <em>will</em> be giving spoilers for the talk in this answer!</p>
<h1>Intuition</h1>
<p>Let's say we start with a language that only has functions, conditionals, integer literals, addition, subtraction, and multiplication. This is Turing-complete if we allow recursion. Let's also say that functions are first-class. This won't come up right now, though.</p>
<p>If we add, say, a unary negation operator to our language, this does not intuitively &quot;increase expressive power.&quot; However, if we add <em>exceptions</em> to the language, well, that <em>does</em> seem to intuitively &quot;increase expressive power.&quot;</p>
<p>Why? Well, for the first feature, whenever we see a unary negation <code>-x</code> we can just translate it, right then and there, into <code>0 - x</code>. <em>However</em>, for the second feature, when we see an exception being thrown or a <code>try-catch</code> block, then we actually have to do a large scale transformation of the program.</p>
<p>I chose exceptions since they are of greater interest, but let's consider a simpler example of a feature that &quot;adds expressiveness.&quot; How about a keyword <code>halt</code> that immediately terminates the program? You certainly cannot implement this as a <em>local</em> transformation to our language! You actually have to apply a transformation that starts at <em>the beginning of the program</em>!</p>
<p>With the negation feature, we only had to transform the exact part of the code where the unary negation is used. For the <code>halt</code> feature, we had to transform the code far beyond where that keyword is used.</p>
<p>This distinction between &quot;feature only requiring local transformation&quot; and &quot;feature requiring global transformation&quot; is what we want to formalize.</p>
<p>We can get closer to a formal statement by saying: a feature does not &quot;add expressive power&quot; if we can implement it as a <em>macro</em> that turns it into something in the original language. Even if the language doesn't have macros, you could imagine using some kind of preprocessor to implement a local transformation as a kind of macro.</p>
<p>This is not <em>quite</em> a formal description yet, but we're getting there! For one thing, how do we <em>prove that a macro cannot exist</em> for some feature? To do this, we still need a formal description of the problem.</p>
<h1>What's tricky about equality of programs?</h1>
<p>First, we need a way to compare programs for equality.</p>
<p>You might wonder: why not just use the equality built in to the language? Well, there are a few reasons:</p>
<ul>
<li>The equality operation might not cover everything. For example, it's actually impossible to compare arbitrary functions for equality in a Turing-complete programming language (in a way that is always correct and always halts).</li>
<li>The language might not even <em>have</em> an equality operation, even though it's Turing-complete. This is the case for many esoteric languages, like FRACTRAN.</li>
</ul>
<p>So we really want something that's somehow <em>&quot;more fundamental&quot;</em> than that and more broadly applicable. We actually <em>do</em> want something that's <em>inside</em> the language that can distinguish between two things, though. But how do we do this?</p>
<p>What it really boils down to is this: given two things in our language <code>x</code> and <code>y</code>, is there <em>any</em> way to write a program in our language that behaves differently if you used <code>x</code> vs if you used <code>y</code>?</p>
<p>A specific question: Is it possible to distinguish between <code>2 * 3</code> and <code>3 + 3</code>? I will return to this particular question in the <em>Expressiveness</em> section.</p>
<p>Formalizing all this is where we get observational equivalence.</p>
<p>But first, we need to talk about what happens when you take a program and cut a hole out of it.</p>
<h1>Programs with a hole</h1>
<p>Imagine you take a valid program in your language and print it out. Then you physically cut out exactly one subterm and throw it away. What you have left is a &quot;program with a hole in it,&quot; or a printout of a &quot;one-hole context&quot; (sometimes just called &quot;a context&quot;).</p>
<p>If you take a slip of paper, write a term on it, and tape it into the hole you now have a program again (as long as the result of this process is well-typed). This is the primary thing you can <em>do</em> with a one-hole context: You can obtain a program by combining it with a term that can fill in the hole.</p>
<p>If we call our context <code>C</code> and the new term we're taping into it <code>t</code> then the complete program we obtain when we tape <code>t</code> into <code>C</code> is called <code>C[t]</code>.</p>
<p>Note that this definition actually always makes sense no matter what programming language we are looking at! I've made <em>no</em> assumptions about the language.</p>
<p>Our definition of observational equivalence will center around these contexts (that is, programs with exactly one hole in them).</p>
<h1>Observational equivalence</h1>
<p>One way to define what it means for two programs to be &quot;equivalent&quot; is that every observation you can make about them is the same. There is actually a decent amount of nuance to <em>&quot;what counts as an observation?&quot;</em> but that's outside the scope of this answer.</p>
<p>We will define observational equivalence like this (<em>first attempt</em>):</p>
<ul>
<li>Two expressions e<sub>1</sub> and e<sub>2</sub> are called &quot;observationally equivalent&quot; if, for <em>every</em> context C, we have C[e<sub>1</sub>] = C[e<sub>2</sub>]</li>
</ul>
<p>This is <em>the same</em> as saying, given those two expressions, does the language provide you a way to tell them apart! It's asking &quot;Are the two expressions identical when plugged into any context?&quot;</p>
<p><em>&quot;Uh, wait a minute...&quot;</em> I hear you say. <em>&quot;But there's still an equals sign! What does that mean? The whole point was to <em>avoid</em> using an existing notion of equality!&quot;</em></p>
<p>That is very true! We need to improve our definition. We need to be a bit more clever (this new definition is due to James Morris's 1969 PhD thesis):</p>
<blockquote>
<p>Two expressions e<sub>1</sub> and e<sub>2</sub> are called &quot;observationally equivalent&quot; if, for <em>every</em> context C, we have: C[e<sub>1</sub>] halts if and only if C[e<sub>2</sub>] halts</p>
</blockquote>
<p>This might seem a bit weird. Think about this for a minute. Does this seem, somehow, wrong?</p>
<p>Take a moment to consider this question: &quot;Are we saying that 1 and 2 are 'observationally equivalent'? Both 1 and 2 very straightforwardly terminate!&quot; (I've taken this from <a href="https://youtu.be/43XaZEn2aLc?t=1575" rel="noreferrer">this part of Shriram's talk</a>. Spoilers for the talk ahead!)</p>
<p>I am <em>not</em> saying they are observationally equivalent! An example: Can you write a Python program with one hole in it that will halt if the hole is filled with <code>1</code> but will loop forever if it is filled with <code>2</code> (you could just write <code>&lt;hole&gt;</code> for the hole and fill it in as appropriate)? If so, you've proven that <code>1</code> and <code>2</code> are observationally <em>distinct</em> in Python! To show that they are <em>distinct</em>, all you have to do is find <em>one</em> context <code>C</code> where <code>C[1]</code> halts but <code>C[2]</code> does not (or visa-versa). If they were <em>the same</em> then every context would behave the same (with regard to halting) regardless of whether you plugged in <code>1</code> or <code>2</code>.</p>
<p>What if we only have a <code>isZero(x)</code> builtin function, but no builtin equality operation? Can we still tell <code>1</code> apart from <code>2</code>? Well, how about the context <code>while (isZero(1 - &lt;hole&gt;)) { }</code>? This is why the definition works well: we need to consider <em>all possible contexts</em>!</p>
<p>Okay, but what if there is <em>actually</em> no way to tell <code>1</code> and <code>2</code> apart? Then we would actually say that <em>are</em> observationally equivalent! Observational equivalence captures the idea of what it means for two things to be indistinguishable inside a programming language.</p>
<h1>Expressiveness</h1>
<p>Now how does all of this relate to expressiveness? I'm going to start by way of example. I'll return to the question: <em>Is it possible to distinguish between <code>2 * 3</code> and <code>3 + 3</code></em>?</p>
<p>My answer: It depends on the features of the language! It certainly is not possible in the language which only has basic arithmetic, functions and recursion. Can you think of a feature we could add where it <em>is</em> possible to distinguish them?</p>
<p>Operator overloading! Say we have operator overloading and the ability to redefine existing function. If we overload <code>*</code> to do something weird, like return the first argument but we don't overload <code>+</code>. We can now distinguish between those two expressions!</p>
<p>By adding that feature, we <em>broke</em> an observational equivalence. The expressions <code>2 * 3</code> and <code>3 + 3</code> <em>used to be</em> observationally equivalent. Then we added operator overloading and now they are <em>observationally distinct</em>.</p>
<p>Now we need to address how to tell if a feature requires a &quot;local&quot; transformation vs &quot;global&quot; transformation.</p>
<h2>The key theorem</h2>
<blockquote>
<p>If feature X can be implemented for language L as a local transformation to obtain the language L+X, then for any two expressions e<sub>1</sub> and e<sub>2</sub> that are observationally equivalent in L, it is also the case that they are observationally equivalent in L+X</p>
</blockquote>
<p>The theorem is proven in <a href="https://www.sciencedirect.com/science/article/pii/016764239190036W" rel="noreferrer">the paper</a>.</p>
<p>This is saying that if feature X only required a local transformation to implement, then it did not &quot;break&quot; any observational equivalences. All of the observational equivalences from L are still true in L+X.</p>
<p>Note that this was <em>not</em> the case for operator overloading. Adding operator overloading <em>did</em> break some observational equivalences. On the other hand, when we added unary negation we <em>did not</em> break any observational equivalences.</p>
<p>Now we can say that when we <em>add</em> expressiveness to a language, we <em>break</em> some observational equivalences.</p>
<p>One practical implication of this is that some optimization passes might be broken when you add a new feature. This is because optimizations assume that certain things are identical. But when you add a new &quot;expressive&quot; feature, you will break some of those equivalences!</p>
<p><em>Exercise for the reader</em>: I mentioned adding <code>halt</code> to a simple language and I said that this is an <em>expressive</em> new feature for that language. Can you give an example of an observational equivalence that holds in the original language, but not the new language with <code>halt</code>?</p>
<h1>Bonus: Connecting a denotational semantics to an operational semantics</h1>
<p>Even though this is just a small part of the answer that is only tangentially relevant to my question, this is what motivated me to write the question and this answer. Particularly, to partially clear up some confusion about denotational semantics <a href="https://langdev.stackexchange.com/questions/1953/how-can-i-understand-a-recursive-function-in-terms-of-denotational-semantics">from the comments of my previous question and answer</a>. This is only one component of that, but it is an important one.</p>
<p>Up until now, we see one useful application of observation equivalence. This allowed me to define it and motivate it. Now we can see, briefly, another application of observational equivalence that is relevant to defining a denotational semantics. It would really be a different answer to a different question to address this in more detail, however, so I will gloss over some things.</p>
<p>There are two very crucial properties you want from your denotation function when you create a denotational semantics. One is called &quot;compositionality&quot; and the other is called &quot;adequacy.&quot; &quot;Adequacy&quot; is defined using observational equivalence. Observational equivalence is derived from an operational semantics.</p>
<ul>
<li>&quot;Adequacy&quot;: If two programs are <em>observationally distinct</em>, then they must have <em>distinct denotations</em>.</li>
</ul>
<p>Consider what it would be like if our denotation function was not &quot;adequate.&quot; We would have two programs that we can observe are different, but they would be mapped to the same mathematical object. That's not very useful way to denote programs!</p>
<h1>Further reading</h1>
<h2>Papers</h2>
<ul>
<li><a href="https://www.sciencedirect.com/science/article/pii/016764239190036W" rel="noreferrer"><em>On the expressive power of programming languages</em></a> by Matthias Felleisen. This paper introduced the formal notion of &quot;expressiveness&quot; I've described above.</li>
<li><a href="https://dspace.mit.edu/handle/1721.1/64850" rel="noreferrer"><em>Lambda-calculus models of programming languages</em></a>, James Morris's 1969 PhD thesis. This is the origin of the concept of &quot;observational equivalence&quot; (he called it &quot;extensional equivalence&quot;).</li>
</ul>
<h2>Books</h2>
<ul>
<li><em>Types and Programming Languages</em> by Benjamin Pierce</li>
<li><em>The Formal Semantics of Programming Languages: An Introduction</em> by Glynn Winskel</li>
<li><a href="https://plfa.github.io/ContextualEquivalence/" rel="noreferrer"><em>Programming Language Foundations in Agda: Contextual Equivalence</em></a> (&quot;contextual equivalence&quot; is another name for &quot;observational equivalence&quot;)</li>
<li><a href="https://softwarefoundations.cis.upenn.edu/plf-current/toc.html" rel="noreferrer"><em>Software Foundations, Vol 2: Programming Language Foundations</em> by Benjamin Pierce et al</a></li>
</ul>

CC BY-SA 4.0
2023-07-04T20:38:11.057Z
2023-07-05T03:36:41.477Z
2023-07-05T03:36:41.477Z
David Young
CC BY-SA 4.0
2023-07-05T07:53:47.497Z
This is awesome, but seems to interact weirdly with some specific features. For instance, consider having a `quote` macro that would take its operand and return it as a string. For a language with that and string comparison, any two different expressions are observationally distinct. Does it make this language the pinnacle of expressiveness?
abel1502
CC BY-SA 4.0
2023-07-05T10:14:11.793Z
a=a*[hole]  `a=a*2*3` vs `a=a*3+3`  maybe I misunderstand?
Jasen
CC BY-SA 4.0
2023-07-05T10:52:04.897Z
Trying the exercise: hole = while(True){ f(0) } versus hole = while(True){ f(1) }.
And as context:
define f(x):
     if x == 0: halt;
[hole]

did i understand this correctly?
Squala
CC BY-SA 4.0
2023-07-05T11:48:44.883Z
@Jasen: I would argue you did, by replacing texts, not expressions. That is, your proposed replacement "breaks apart" the expression `3 + 3`. To replace an expression you'd replace in the AST. So the AST `+ (2) (* (2) (3))` becomes `+ (2) (+ (3) (3))`, or back in text... `3 + 3` is parenthesized implicitly when plugging it back in.
Matthieu M.
CC BY-SA 4.0
2023-07-05T14:04:34.133Z
See also Shutt's 2013 post on [abstractive power](https://fexpr.blogspot.com/2013/12/abstractive-power.html), where category theory is used to make expressive and abstractive power into categorical relationships.
Corbin
CC BY-SA 4.0
2023-07-05T14:25:28.707Z
@Squala You did! That's a correct answer
David Young
CC BY-SA 4.0
2023-07-05T15:00:53.070Z
@Jasen This does get at a point I glossed over in the answer. As Matthieu said, you are doing *textual* substitution, which is not correct here. The kind of substitution I'm talking about can be thought of as substitution in the abstract syntax tree. You can think of it this way: take `a*[hole]` and draw its AST. One of the children of `*` is `[hole]`. Let's say we want to substitute the AST for `3+3` in for `[hole]`. We end up with an AST that represents `a * (3+3)` *not* an AST that represents `(a * 3) + 3`
David Young
CC BY-SA 4.0
2023-07-05T15:02:09.207Z
I drew a diagram of this situation [here](https://q.uiver.app/#q=WzAsMTEsWzcsMCwiKyJdLFs2LDIsIjMiXSxbOCwyLCIzIl0sWzQsNCwiKiJdLFszLDYsImEiXSxbNSw2LCIrIl0sWzQsOCwiMyJdLFs2LDgsIjMiXSxbMCwyLCJhIl0sWzEsMCwiKiJdLFsyLDIsIltob2xlXSJdLFswLDFdLFswLDJdLFszLDRdLFszLDVdLFs1LDZdLFs1LDddLFs5LDhdLFs5LDEwXV0=). The tree on the left is the AST for `a*[hole]` and the tree on the right is for `3+3`. The tree at the bottom is what you get when you substitute `3+3` for the hole in `a*[hole]`
David Young
CC BY-SA 4.0
2023-07-05T17:11:00.163Z
In case that q.uiver link goes down at some point, [here](https://i.sstatic.net/8MMvw.png) is an image of those trees hosted on the site StackExchange uses for images. I also zoomed out a bit and removed the grid when I made that image, so it might be immediately a bit more readable
David Young
CC BY-SA 4.0
2023-07-05T17:20:46.217Z
@abel1502 Your example is intuitively wrong, but I'm not sure how to formalize why. The most obvious example is `quote(2 + 2) != quote(2  + 2)`, when in fact `2 + 2` and `2  + 2` resolve to the same syntax tree and therefore cannot be distinct.
Bbrk24
CC BY-SA 4.0
2023-07-05T17:37:07.907Z
@Bbrk24 Those would be indistinguishable in a Lisp-style language. `quote` gives you (a representation of) the AST of its argument. However, I agree that it seems intuitively wrong but I also don't know how to formalize why (right now)
David Young
CC BY-SA 4.0
2023-07-05T17:40:17.090Z
@DavidYoung If "quote" doesn't satisfy you, what about C-style `#define STRINGIFY(x) #x` (or, depending on your use case, [doing it twice](https://stackoverflow.com/a/2653351/6253337))? Regardless of you you spell it, the ability to stringify code verbatim interferes with the definition in this answer.
Bbrk24
CC BY-SA 4.0
2023-07-05T19:53:18.237Z
@abel1502 How would quote() make things different if a language already has strings and string comparison? Keep in mind that you have to use quote() in the context, not in the hole, since you need the hole to contain code that is valid in L and L+X. And in the context, you could just use quote marks anywhere you used the quote() macro. Maybe I'm misunderstanding now though.
ArrayBolt3
CC BY-SA 4.0
2023-07-05T20:45:18.450Z
@ArrayBolt3 The "inside" of a string literal is not a term in the language. However, the string literal, when you *include* the quotation marks, *is* a term in the language. Say we are talking about Python and we have an expression `len("abc")`. Then we can say the whole expression is a subterm of itself. `len` is a subterm in the expression. Also, `"abc"` is a subterm in the expression. *However*, `abc` is *not* a subterm in the expression. A context is a program with exactly one *term* removed from it. So, a hole surrounded by double quotes is not a context.
David Young
CC BY-SA 4.0
2023-07-05T21:01:42.500Z
@DavidYoung True, but that's not what I meant. I meant that you can't fill a hole in language L with "if ( "abc" = quote(abc) ) then do something;" because quote() doesn't exist in language L. Just like how "halt" can make observationally equivalent statement distinct, but you can't use "halt" in what you fill the hole with. You could only use quote() somewhere in the context, and no way of doing that will result in something becoming observationally distinct because you could have just used quote marks.
ArrayBolt3
CC BY-SA 4.0
2023-07-05T21:14:55.003Z
@ArrayBolt3 You can observe what I'm talking about in Racket, for example. Consider the two expressions `(+ 2 2)` and `4`. Now, consider this context: `(eq? (quote <hole>) 4)`. If you fill the hole with `(+ 2 2)` you will get back `#f`. However, if you fill the hole with `4` then you get back `#t`.
David Young
CC BY-SA 4.0
2023-07-05T21:34:18.330Z
Furthermore, if you are concerned that `quote` is giving back `4` rather than some kind of quoted `4`, consider this context in a language that uses a string-y `quote` rather than a Lispy `quote`: `if (length(quote(<hole>)) == 1) { infinite_loop }` If you fill the hole with `4`, you will get an infinite loop. But if you fill it with `2+2`, it will do nothing.
David Young
CC BY-SA 4.0
2023-07-06T08:54:10.790Z
Follow on question - https://langdev.stackexchange.com/questions/2082/can-felleisens-expressivity-metric-be-abused-to-construct-ever-more-expressive
Bruce Adams
CC BY-SA 4.0
2023-07-06T14:53:05.267Z
@DavidYoung Wonderful answer! One question I have though. All of the answers I've seen here to your `halt` exercise (as well as the one I came up with myself) hinge on `halt` terminating the whole program. So what about `break`? As implemented in C and most other mainstream languages, `break` is lexical, which means it breaks out of the nearest enclosing *lexical* loop. Intuitively, `break` is a non-local transformation. But we can't just hide a `break` in a function like we did `halt` to prove it. Do you have an example of two expressions that are equivalent in `L` but not in `L + break`?
Silvio Mayolo
CC BY-SA 4.0
2023-07-07T15:28:11.573Z
@SilvioMayolo Thank you! That's a very interesting question. I've thought about it for a bit and I've come to the following conclusion. Even though it intuitively seems like `break` is "expressive," it looks like it can be implemented as a collection of macros with each one being local: turn `while (cond) { C }` into `{bool b = false; while(b || cond) { C' } }` where `b` is fresh. Then, transform *every* statement to include an `if`. So, `x = y` becomes `if (!b) { x = y }`, etc. `break` becomes `b = true`. Also put `bool b = false` in the outermost scope. Not efficient, but it should work.
David Young
CC BY-SA 4.0
2023-07-07T15:33:49.400Z
There are many situations in which it is not possible for a program to behave usefully (e.g. because it receives superficially valid but nonsensical input), and a wide variety of tolerably useless behaviors would be equally acceptable, but some behaviors would be intolerably worse than useless.  Can the principle of "observational equivalence" handle this?
supercat
CC BY-SA 4.0
2023-07-07T15:41:35.333Z
@supercat Hmm, I'm having trouble understanding what you mean. Maybe you could give an example?
David Young
CC BY-SA 4.0
2023-07-07T15:45:56.333Z
@DavidYoung: Suppose a language specifies the integer of overflow such that the result may behave as the non-deterministic union of all possible mathematical integers, but (1) it must have no side effects, and (2) any particular evaluation of any conditional expression must always behave as though it yields true or it yields false (collapsing any non-determinism).  Under such semantics, it would be possible to statically examine many programs and answer many questions of the form "Is there any input for which the program might do X", but the general question of whether any particular output...
supercat
CC BY-SA 4.0
2023-07-07T15:52:26.883Z
...could be produced by a particular execution of the program given any particular input would be undecidable.  If a particular language makes it possible to prove through static analysis that a program won't perform a certain unacceptable action X no matter what input it receives, is there any way to distinguish superset languages that would also facilitate such proofs from those that would make the question of whether the program might do X undecidable?
supercat
CC BY-SA 4.0
2023-07-07T16:18:45.847Z
@supercat I'm still having some trouble understanding, but let's see if I've got part of it: You are describing a language which has a static analysis feature that will semi-decide some, in general undecidable, property about a program. Without this feature, you could *not* semi-decide this property inside the language. And the question would be: "can 'Felleisen expressiveness' explain the new amount of expressiveness added by the static analysis feature?" Is that close?
David Young
CC BY-SA 4.0
2023-07-07T17:46:47.040Z
@DavidYoung: I think the simplest way to describe it may be that a Turing machine program represents a mapping from possible inputs to outputs, but in some cases it may be useful to be able to specify a mapping from inputs to sets of acceptable outputs., such that an optimizing compiler would strive to generate the most efficient machine code which, for any input in the set, will yield an output which is within the corresponding set of acceptable outputs.
supercat
CC BY-SA 4.0
2023-07-07T19:29:56.437Z
@supercat Okay, I think I understand now. Something like undefined behavior in C (although not necessarily as messy) or a program synthesis task using some ambiguous specification. I don't think observational equivalence in terms of contexts quite captures that. If you expand the notion of "observation" to a set of runtime behaviors, you might be able to use Felleisen's expressiveness, though. There are situations when you might need to change what you consider to be "observations" like this. This can happen in security, when you need to consider micro-architectural states for side-channels
David Young
CC BY-SA 4.0
2024-10-07T19:12:59.803Z
Delightful answer, thank you. Your point about "if I add feature X will my optimizing compiler do a bad job?" works in the opposite direction as well. Back when I was working on VBScript in the 1990s we used a build of the MSVC++ compiler that had compilation of programs with exception handling *disabled* because it generated better code than the same compiler with exception support turned on.
Eric Lippert
CC BY-SA 4.0
2024-10-15T16:55:48.340Z
@EricLippert Thank you for your comment! That is interesting. I hadn't considered that kind of situation in that way before.
David Young
<p>I don’t believe that’s generally possible. Expressive power depends on what specifically is being expressed.</p>
<p>Your python versus assembly example is obviously more expressive when you write general-purpose scalar code, manipulating strings or XML or JSON, access files or network.</p>
<p>However, for other programs the expressiveness can be opposite because processors are implementing interesting instructions hard to express in Python. For modern AMD64 processors, <a href="https://haskell-works.github.io/posts/2018-08-22-pdep-and-pext-bit-manipulation-functions.html" rel="noreferrer">bit manipulation</a> like <code>popcnt</code>, <code>pext</code>, <code>pdep</code>, vector math like <code>psadbw</code>, <code>pshufb</code>, <code>psignd</code>, <code>dpps</code>, saturated integer stuff like <code>paddusb</code>, checksum and cryptography support like <code>crc32</code>, <code>aesenc</code>, <code>aesdec</code>, <code>sha1rnds4</code> are easy to express in assembly (and even easier in C++ with intrinsics because the compiler takes care about register allocation and scalar parts of the code), but harder to express in Python.</p>
<p>The observation is not specific to AMD64, other instruction sets also contain instructions hard to express in higher level languages. An example is ARM’s <code>rbit</code> instruction which reverses order of bits in an integer. That single instruction requires rather complicated code to express in higher level languages. Other ARM examples are saturating arithmetic, and <code>bfi</code>.</p>

CC BY-SA 4.0
2023-07-06T13:49:01.580Z
2023-07-06T15:28:02.743Z
2023-07-06T15:28:02.743Z
Soonts
CC BY-SA 4.0
2023-07-06T15:35:59.980Z
There is the most highly upvoted answer on this site, by a high-rep user, that directly contradicts your first sentence @Soonts
Starship
CC BY-SA 4.0
2023-07-07T21:25:56.743Z
@Starship-OnStrike I think it's reasonable to say that David's answer (while very interesting) doesn't necessarily give us tools to answer questions like "which is more expressive, Python or assembly". It's a neat result, but it doesn't mean this response isn't also useful.
Kaia
CC BY-SA 4.0
2023-07-07T23:21:46.767Z
It sounds like the main disagreement is with the first sentence of the answer. I see two different readings of that sentence, depending on how you interpret the scope of the word "generally": (1) *"There is no technique that will compare any notion of expressiveness between two Turing complete languages"* (2) *"No technique for measuring expressiveness works for _every_ form of expressiveness"*. I don't agree with (1), but I do agree with (2). I suspect (2) is intended for this answer, though.
David Young
<p>Matthias Felleisen's <a href="https://www.sciencedirect.com/science/article/pii/016764239190036W" rel="nofollow noreferrer">paper</a> is a little hard to follow. It gives an expansion-based notion of expressive power.</p>
<p>In the concluding paragraph, Felleisen expresses the belief that this is a
superior way of exploring expressive power to the approach based on
interpretation. I think that is referring to the general idea that a language A
is more expressive than B, if the only way to get B to express programs in the
same way as A is to write an A interpreter in B and then just run the A
programs.</p>
<p>Turing showed us the concept of a Universal Turing Machine, which is
programmable. What that means that for any given Turing Machine (input tape
plus symbol manipulating rules), the Universal Turing Machine can be programmed
to run that Turing Machine by an extended tape: a tape which contains
instructions for the Universal Turing Machine, followed by the
to-be-simulated/emulated Turing Machine's tape. The UTM concept tells us that
(if resources are no object), we can directly run the programs of one language
in any other language, by interpreting it.</p>
<p>Thus, Turing equivalence speaks to expressiveness because we know not only that
any universal machine can calculate all the same recursive functions as any
other, but that an universal machine can interpret a calculation written in any
expressive form. If a language A, however, can <em>translate</em> a program in
language B into language A, such that no interpretation is involved; B programs
thus translated are at no performance disadvantage compared to A programs, and
interoperate easily with A programs, that that somehow gives us a more
satisfying sense that B has the expressive power of A.</p>
<p>Felleisen's basic idea seems to be this. We would like to compare the
expressive power of two languages L0 and L1, using the concept of translation.
Firstly, we need some common ground. We assume that there is a common language
L, from which L0 and L1 are derived.</p>
<p>Informally, we can identify L as a common virtual machine for L0 and L1.
Languages L0 and L1 expose some subset of L.  We make a simplifying assumption.
Whenever L0 or L1 feature something from L, that feature &quot;looks like&quot; the L
feature; it is not weirdly disguised, twisted or damaged in some way.</p>
<p>We allow L0 and L1 to have macros.</p>
<p>Then, we can say that L1 is strictly more expressive than L0 if L1 can use
macros to express every L0 program, but the reverse isn't the case.
For any construct in L0, an identical or similar macro is defined in the L1
program, if necessary, and then the L0 construct is simply transliterated,
but in the reverse direction, there are L1 constructs that aren't in L0,
and cannot be provided by L0 macros.</p>
<p>Now, according to Turing, we could have some <code>L1-interpret</code> macro in L0 such
that <code>(L1-interpret '(... quoted L1 program ...))</code>. But the quoted L1 program
is being (partially or entirely) interpreted and not actually translated into
L0 primitives.</p>
<p>We rule out this Turing interpretation trick as not providing a true
expressiveness bridge for the follwoing reasons.  If L0 can only express L1
programs by interpreting them, then those interpreted L1 programs are not
directly using the required L features, which are used by the real L1
implementation.</p>
<p>We can justify that with an example.  Suppose that the underlying L has, say,
dynamic non-local transfers (for implementing exceptions and such), with unwind
protection.  Suppose that feature is exposed in  L1, but is not found in L0: L0
has no dynamic control transfers, no unwind-protect.  Then it will be
impossible for L0 to translate and execute an L1 program, other than by L0
providing its own implementation of dynamic non-local control transfers, which
are not based on the ones in L. L1 programs execute in L0, but in with a severe
limitation: they cannot initiate a dynamic control transfer which jumps out of
L0 entirely and terminates in an exit point in a <em>genuine</em> L1 program running
directly on the L machine. More importantly, the interpreted L1 programs also
cannot catch exceptions emanating from L itself, like from the L I/O library or
what have you. L0 has no access to that; it has no way of catching exceptions
and forwarding them into the interpreted L1 code. Thus L1 programs themselves
lose expressiveness with respect to the L environment if they are interpreted
by L0.</p>
<p>The generalization is that if L0 exposes only a subset of the L features than
L1 exposes, in a way that some L1 programs cannot be converted to L0 programs
while remaining fully-fledged L programs, but L0 programs <strong>can</strong> so be converted
to L1 programs, then L1 has more expressive power.</p>
<p>Expressive power is related in some way to succinctness but not defined by it. If both L0 and L1 have macros, they can both condense code. The above notion of expressiveness strikes at the idea that there are situations in which L0 cannot express some <strong>semantics</strong> in L1 in spite of having macros for expressing the <strong>syntax</strong>. You can write the interface part of the macro which matches the syntactic pattern of the L1 construct, and all its conciseness, but have no way to actually write the transformation: the macro's target language doesn't have the constructs for <strong>expressing</strong> the macro's meaning.</p>
<p>If we have a L0 and L1 which both have all the features of L, but L1 has macros whereas L0 doesn't, then conciseness becomes utterly relevant to expressiveness, because L1 macros can express new kinds of constructs that are not replicable in L0. If we take the fully macro-expanded L1 program, we can express <em>that</em> in L0, because all the constructs it's using are available in L0. Expressing the macro-expanded program is not the same thing as expressing the original program.</p>

CC BY-SA 4.0
2023-07-06T17:42:22.860Z
2023-07-06T18:08:26.680Z
2023-07-06T18:08:26.680Z
Kaz
CC BY-SA 4.0
2023-07-06T22:25:28.273Z
This seems to require that both L0 and L1 share a common subset of feature L which I suppose must be vacuuously true given that both are turing complete. But doesn't the answer actually depend heavily on L?

Also how can we be sure this ordering relation is total or partial? If you compare two languages you might find they both have features that can't be expressed in the other. E.g. L0 has exceptions but L1 has continuations.   L0!>L1 && L1!>L0 && L0 != L1
Bruce Adams
CC BY-SA 4.0
2023-07-06T22:25:31.663Z
Third point. I would argue that a macro system makes a language more expressive. So if L1 is L0 but with a macro system an ideal metric should say L1>L0
Bruce Adams
CC BY-SA 4.0
2023-07-06T23:11:18.700Z
@BruceAdams Turing machines don't have to share any common L. E.g. we can have a tape with a read/write head, versus lambda calculus.  Now suppose we are talking about real languages. We can identify multiple L's. They all run on my PC, so L could be x86-64.  No wait, both languages are on the JVM, so that's the L.  Perhaps L should typically be something like the highest level substrate that the two have in common.
Kaz
CC BY-SA 4.0
2023-07-06T23:14:41.987Z
In reality, we often deal with differently expressive languages. Say we have some language with macros, but is missing something relative to another language. Neither is strictly more expressive than another, but for some task where that missing something is critical, the language which has that feature is expressive, whereas the other one isn't. Where that missing feature is not relevant, the language with macros is more expressive.  Tasks often just require a subset of a language, and so expressiveness can be evaluated over subsets.
Kaz
CC BY-SA 4.0
2023-07-07T03:12:35.307Z
@BruceAdams Regarding your point, yes, I hoped to convey that that would be true. If L1 is L0 with macros, it is more expressive, because the macro expressions in L1 have no equivalent in L0. In this answer, to express means to present in the same way, expression by expression. If L1 uses a `with-open-file` macro, but `L0` handles all errors and manually cleans up, `L0` is not expressing what `L1` is expressing.
Kaz
<p>A straightforward approach is to write the same program in multiple languages, <a href="https://en.wikipedia.org/wiki/Minification_(programming)" rel="nofollow noreferrer">minify</a> the source code (so that you're counting only “real” code rather than indentation or variable name length), and score “expressiveness” as inversely related to the number of bytes of minified code.</p>
<p>However, this fails to meet your criterion of being “unambiguous”, because it depends on the choice of benchmark program(s).  Different languages have different standard libraries and different domain-specific features, making some languages better specialized for specific tasks than others.  For example, if your assignment is to write a simple <code>cat</code>-style program that copies data from stdin to stdout, it's hard to beat the 5-character program Brainfuck program <code>,[.,]</code>.  But the language is unwieldy for pretty much anything else.</p>

CC BY-SA 4.0
2023-07-06T16:48:17.793Z
2023-07-06T16:48:17.793Z
dan04
CC BY-SA 4.0
2023-07-06T17:57:28.717Z
Two languages can both be given "minifying power" via structural macros. Yet it may be that programs in one still cannot be expressed in the other, no matter how you try to write the macros.  E.g. Common Lisp doesn't have continuations. You can't get them via macros. You can create a macro-based sublanguage in which there are continuations, but those continuations are restricted to staying within that language. You've not introduced continuations into the underlying Common Lisp; you cannot capture the computing future of arbitrary Lisp code as a continuation.
Kaz
CC BY-SA 4.0
2023-07-06T21:04:12.637Z
If I were to take Python and add in INTERCAL’s requirement that some percentage of statements begin with `PLEASE`, the resultant language would score less favorably by this metric, but would not be any less expressive. Similarly, deriving a language that substitutes APL-style special characters for keywords from Python would score more favorably by this metric, even though it is no more expressive than Python. At minimum, you need to be looking at token counts, not character counts.
Austin Hemmelgarn
<p>Expressive power is absolutely not about the lines of code required to achieve the needed functionality. If we would count so, the most expressive language is Bash. Feel the power:</p>
<pre><code>firefox
</code></pre>
<p>A complex browser, with rendering engine, security, scripting and lots of other stuff is implemented with just a <strong>single line of code</strong>. One may say, best language ever. No firefox on the system?</p>
<pre><code>firefox || sudo apt-get install -y firefox &amp;&amp; firefox
</code></pre>
<p>We are still able to provide the firefox anyway with just one line of code, this will work nice also if it is already present. But if there is no existing program available, building brand new functionality with Bash is less fun, even if possible.</p>
<p>Now feel the Python expressive power for the following real world example (<a href="https://stackoverflow.com/questions/42316380/sum-of-negative-elements-in-each-column-of-a-numpy-array">source</a>):</p>
<pre><code>numpy.where(arr&lt;0,arr,0).sum(0)
</code></pre>
<p>Assuming you are not an expert of the large <a href="https://numpy.org/doc/stable/reference/routines.math.html" rel="nofollow noreferrer">numpy</a> API yet, it may actually take the comparable time to understand the same in Assembler (<a href="https://stackoverflow.com/questions/70202471/how-find-sum-of-negative-values-in-assembly">source</a>):</p>
<pre><code>  xor  edx, edx
  mov  esi, [arr]
  mov  ecx, [arr_rows]
  imul ecx, [arr_cols]
more:
  mov  eax, [esi]
  test eax, eax         ; TEST is efficient to inspect the sign
  jns  skip
  add  edx, eax         ; Only adding negative values
skip:            
  add  esi, 4
  dec  ecx
  jnz  more
</code></pre>
<p>and while the old C++ version may not look very cool, I still suspect that for many it would take less time to understand it than that numpy twist:</p>
<pre><code>   int sum = 0;
   for (int v: arr) {
     if (v &gt; 0) sum += v;
   }
</code></pre>
<p>Bash (<a href="https://stackoverflow.com/questions/23125601/how-to-add-only-positive-numbers-in-shell-script">source</a>) ?</p>
<pre><code>sum=0
for file in $*
do
  for number in `grep -wo &quot;[0-9]*&quot; $file`
  do
    if [[ $number -gt 0 ]];
    then
        sum=$(($sum+$number))
    fi
  done
done
echo &quot;Sum: $sum&quot;
</code></pre>
<p>Not that easy, even if we tried to play on Bash stronger side a little bit by accessing the existing program, <code>grep</code>. Similar problems as with Python: to understand this code, you need to know that the <a href="https://www.geeksforgeeks.org/grep-command-in-unixlinux/" rel="nofollow noreferrer">grep</a> is and which switches does it take. $* is also not for mundane ones, further illustrating the fact that &quot;two characters only&quot; does not necessary mean a lot of readability. Something more along <code>all_args</code> would probably be understandable without googling <a href="https://superuser.com/questions/247127/what-is-and-in-linux">this answer</a>.</p>
<p>Python looks somewhat similar to Bash (and some administrators actually use it that way). When there is a complex functionality available, it is great in accessing it. Especially when that complex functionality does not actually take or return any complex data structures to deal with, just does its magic when called by name. But when implementing some complex algorithm from the mathematical article, Python may still not be the best tool for the purpose.</p>
<p>I am not sure what the &quot;expressive power&quot; means exactly, but the language I would pick for implementing or developing some complex algorithm should:</p>
<ul>
<li>Make it very easy to implement the huge number of the known <a href="https://en.wikipedia.org/wiki/Software_design_pattern" rel="nofollow noreferrer">software design patterns</a> I expect to use.</li>
<li>Provide reasonable amount of context. A structure with named and typed fields provides more context than a map that could contain almost anything, and may take long time to figure out what exactly. Python is proud of demanding very little context, but I really had big problems in understanding complex undocumented structures as returned by some third party libraries. In C++, this would at least not compile.</li>
<li>Make it easy to split a complex step into multiple simpler steps.</li>
<li>Due reason above, it must run loops at usable speed, because a single iteration of the loop is often much easier to understand than the complete action on the whole array, expressed in the terms of matrix algebra or the like.</li>
</ul>
<p>From the other side, a language that is explicitly designed for the group of tasks where our current task also belongs may be very expressive and efficient there, easy to write and read. I would probably put the winner on SQL here, at least against Python, even it it is not Turing complete:</p>
<pre><code>select sum(x) from array where x &gt; 0
</code></pre>
<p>I am convinced that likely any non programming teenager would understand.</p>

CC BY-SA 4.0
2023-07-06T15:42:13.230Z
2023-07-06T18:09:54.760Z
2023-07-06T18:09:54.760Z
Audrius Meškauskas
CC BY-SA 4.0
2023-07-06T17:15:48.080Z
“One may say, best language ever. But it may be something wrong with this view.” I share that view, and I don’t think there’s anything wrong with it. For this particular problem, and for many other programs which only need to run other programs (no matter how complicated), and pipe these input/output/error streams forwarding them into yet another programs, Bash is incredibly expressive. People are using Bash and similar languages all the time, precisely because these are probably the most expressive languages _for that particular class of problems_.
Soonts
<p>In many cases, it's useful for a programmer to be able to specify &quot;don't care&quot; aspects of program behavior, and allow an implementation to choose in Unspecified fashion from among them.  While all Turing Complete languages may be equally capable of handling all situations where, for any particular input, a program would be required to produce some particular exact ouptut, there can be substantial differences in their ability to specify &quot;don't care&quot; aspects.  From a purely theoretical standpoint, there's never any need for a programmer to characterize any aspects of behavior as &quot;don't care&quot;, but from a practical standpoint it can nonetheless be useful.</p>
<p>Consider, for example, the design of a circuit which accepts 32 inputs and produces one output, subject to the each of the following set of requirements:</p>
<p>Set #1:</p>
<ol>
<li>If more than half of the inputs are high, the output must be high.</li>
<li>If less than two inputs are low, the output must be low.</li>
<li>In all other cases, the output may be arbitrarily high or low.</li>
</ol>
<p>Set #2:</p>
<ol>
<li>If more than half of the inputs are high, the output must be high.</li>
<li>In all other cases, the output must be low.</li>
</ol>
<p>Any design that satisfies the first specification would also satisfy the second, but a minimal circuit which upholds the first specification could be realized much more cheaply than one which must satisfy the second.  If application requirements would be satisfied by either circuit, the first circuit would be a cheaper way of satisfying such requirements than the second would be.</p>
<p>The second requirement could be satisfied by using eight circuits which each accept four inputs, and have four outputs indicating whether at least one, at least two, at least three, or at least four inputs are high.  Those could then be paired to yield four sets of outputs indicating whether at least one, etc. up to at least eight inputs from each group of 8 are high, and those can then be paired to yield two sets of 16 outputs.  From there, one can report that the condition is satisfied if at least one input from the first group is high and all sixteen from the second group is high, or at least two from the first group and at least fifteen from the second group, or at least three from the first group and at least fourteen from the second group, etc.  Possible, but expensive.</p>
<p>The first requirement could be satisfied by having 16 circuits each examine a pair of inputs and reporting whether both inputs of each pair are set, and then checking if any of those circuits reported true.  Much simpler.</p>
<p>In this case, a human writing the specs migh recognize that a specification making the output high if any pair inputs had both inputs high would be cheaper to process than one which outputs low unless at least half of the inputs are high, but in many cases it would be useful for a compiler to be able to automatically identify which acceptable combination of behaviors could be realized most efficiently.  Languages vary considerably in their ability to express such concepts.</p>

CC BY-SA 4.0
2023-07-07T17:00:36.183Z
2023-07-07T22:57:20.420Z
2023-07-07T22:57:20.420Z
supercat
<p>Most people would consider &quot;expressiveness&quot; as the time it takes them to get a certain task done without bugs. As such, there won't be an accepted way to compare two languages. It would require an infinite set of expensive tests and people would argue whether the submissions are really comparable or if the subset of actual tests is a good one.</p>
<p>If there were such a notion, people could simply optimize on it. But this does not happen. In fact, the Python vs. assembly example is already wrong, because programming a micro controller with Python would not lead anywhere. Or if you want to make use of a certain processor instruction. What I'm trying to say here is that actual expressiveness depends on the domain you are operating in. In such a domain, certain concepts can help you that might even be considered a reduction of expressiveness in other domains. Ada has a lot of concepts that work well for programming rockets but are in your way when building common desktop software.</p>
<p>Nonetheless, if you really need such a notion for some sort of comparison you made, I'd time how long it takes to write a program for a predefined set of tasks in each language. The issue with such comparisons is that they overrate languages that are good for trivial tasks and bad for implementing large software projects.</p>
<p>What you could also do is compare expressiveness of type systems. However, you'll end up in a similar situation as with Turing completeness, because a lot of them can express arbitrary proofs and computations and there is no really good way to say &quot;in a sane piece of code&quot;.</p>

CC BY-SA 4.0
2023-07-08T09:30:29.323Z
2024-10-07T05:16:13.573Z
2024-10-07T05:16:13.573Z
feldentm
CC BY-SA 4.0
2023-07-08T10:40:06.717Z
I think its not so much that it can't be done rationally and objectively but that it is hard. Not just AI hard but a hard multi-variable optimisation problem for humans too. By attempting to formalise it we try to remove the human biases.
Bruce Adams
CC BY-SA 4.0
2023-07-08T12:44:25.447Z
While I appreciate the idea, I doubt that the formalization will result in something that reflects the subjective understanding of "expressiveness" of most people. At least if it is provably a partial order on formal semantics of programming languages. The thing with these approaches is that marginal changes in the formalization can have massive impacts on the outcomes of such orders.
feldentm
# How can we compare expressive power between two Turing-complete languages?
Posted by: username_0 on 2023-07-04
Is this possible?

Is there an accepted (and unambiguous) notion of "expressive power" that could differ between two different *Turing-complete* languages?

It seems like, for example, Python is intuitively much more "expressive" (in some sense) than an assembly language since Python's high-level constructs (like `class`es, functions and even `for` loops) often make it much easier to organize and think about code compared with assembly languages.

On the other hand, any program you can write in Python you can also write in an assembly language since both languages are Turing-complete (ignoring library availability, etc).

But do you *really* want to implement complex algorithms in [FRACTRAN](https://en.wikipedia.org/wiki/FRACTRAN) or as a [*Magic: the Gathering* deck](https://arxiv.org/abs/1904.09828)? Why not?

Is there a way to give a real, unambiguous definition to this intuitive notion of "expressiveness?"
**Tags:** language-comparison
> **Comments:**
> **username_1**: Too vague for an answer, but: a kind of reverse-[Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity) would make sense. When you have a program that solves a problem, you can measure its time complexity, space complexity, but also its length (in bytes), its readability/maintainability, etc. Use all these measures to attribute a score to each program. Then if you have a list of standard problems in order of difficulty, you could "grade" a language by the minimum scores of programs that solves these problems.  
> **username_1**: For instance, compare a Turing-machine's tape with C's allocation of memory. In C you can use pointers to quickly access any memory you've allocated. On a Turing-machine, you need to move the data head one cell at a time to access memory. Although both are Turing-complete, solving a problem that requires large amounts of memory is going to be slower with a Turing-machine, because you need time to move the data head back and forth - you wouldn't need that time if you had pointers like in C. So, "pointers" are a feature that noticeably reduces the time-complexity of programs.  
> **username_2**: Good idea but you have to be very careful of your costs. Do you include library functions and system calls? What about machine level instructions like microcode?
You might argue the measurement should be relative. So you do include those if you are comparing with a turing machine but you might not if comparing two languages that both assume an x86 architecture.  
> **username_3**: https://stackoverflow.com/q/2427496/781723  
---
## 7 answers
### Answer by username_0 on 2023-07-04. Score: 100
Surprisingly **yes**, this is possible!

This is actually pretty important for people that work on optimizing compilers. If I add this new feature, will it break any existing optimization pass? I will show why this is a concern later in the answer.

And this is good since all of us are interested in programming languages. Surely we should have at least one clear-cut way to distinguish between them, beyond the names of keywords, etc! Most people would rather write a large system in *[insert your favorite language here]* than, say, [Befunge](https://en.wikipedia.org/wiki/Befunge) or [INTERCAL](https://en.wikipedia.org/wiki/INTERCAL). But those languages *are* Turing-complete.

So, what's going on here?

Not only that, the concept we need here has significance in formal semantics beyond this question. I'll briefly mention this at the end of the answer.

Can you ever distinguish between `2 * 3` and `3 + 3` in a programming language? Are you *sure*? Are there any "reasonable" languages in which you can distinguish between these? What, exactly, would it mean to be able to distinguish between them and how can we give a definition for "this language distinguishes between these things?" Read on to find out more!

The concept we need is called "observational equivalence."

A roadmap:

* First I'll give an intuitive description of how you could understand the statement *"feature X adds expressive power to language L"*.
* Next, I'll need to talk about programs that have a hole in them. These are called *"one-hole contexts"*. Sometimes this is abbreviated to just *"context."*
* Then I'll use one-hole contexts to define *"observational equivalence."* This is one way to talk about certain programs being "equivalent."
* Finally, we will see that we can say adding feature X to language L makes the language *more expressive* if, by adding feature X, we end up with *fewer* observational equivalences in the resulting language L+X. That might sound backward. I'll get to this, though.

The **key idea** is this: Consider taking a Turing-complete language L and adding feature X. Now think about how we could translate code written in L+X back into into L. If feature X makes the language "more expressive," then this transformation will require you to apply a large-scale, *"global"* transformation. On the other hand, if language L and L+X are "equally expressive," then L+X can be transformed into L using only a *"local"* transformation.

# Inspiration

I will state upfront that this answer (and the way I framed the original question) is inspired by [Shriram Krishnamurthi's excellent and approachable 2019 talk](https://www.youtube.com/watch?v=43XaZEn2aLc) about Matthias Felleisen's paper "On the Expressive Power of Programming Languages." Anyone who is interested in this question should absolutely watch it. The corresponding paper is [here](https://www.sciencedirect.com/science/article/pii/016764239190036W).

I actually think that talk would be interesting to everyone here, in fact. There are many questions that have variations on "... what if I add feature X to a language ..." and this talk gives a way to understand one aspect of that kind of question!

Incidentally, I *will* be giving spoilers for the talk in this answer!

# Intuition

Let's say we start with a language that only has functions, conditionals, integer literals, addition, subtraction, and multiplication. This is Turing-complete if we allow recursion. Let's also say that functions are first-class. This won't come up right now, though.

If we add, say, a unary negation operator to our language, this does not intuitively "increase expressive power." However, if we add *exceptions* to the language, well, that *does* seem to intuitively "increase expressive power."

Why? Well, for the first feature, whenever we see a unary negation `-x` we can just translate it, right then and there, into `0 - x`. *However*, for the second feature, when we see an exception being thrown or a `try-catch` block, then we actually have to do a large scale transformation of the program.

I chose exceptions since they are of greater interest, but let's consider a simpler example of a feature that "adds expressiveness." How about a keyword `halt` that immediately terminates the program? You certainly cannot implement this as a *local* transformation to our language! You actually have to apply a transformation that starts at *the beginning of the program*!

With the negation feature, we only had to transform the exact part of the code where the unary negation is used. For the `halt` feature, we had to transform the code far beyond where that keyword is used.

This distinction between "feature only requiring local transformation" and "feature requiring global transformation" is what we want to formalize.

We can get closer to a formal statement by saying: a feature does not "add expressive power" if we can implement it as a *macro* that turns it into something in the original language. Even if the language doesn't have macros, you could imagine using some kind of preprocessor to implement a local transformation as a kind of macro.

This is not *quite* a formal description yet, but we're getting there! For one thing, how do we *prove that a macro cannot exist* for some feature? To do this, we still need a formal description of the problem.

# What's tricky about equality of programs?

First, we need a way to compare programs for equality.

You might wonder: why not just use the equality built in to the language? Well, there are a few reasons:

* The equality operation might not cover everything. For example, it's actually impossible to compare arbitrary functions for equality in a Turing-complete programming language (in a way that is always correct and always halts).
* The language might not even *have* an equality operation, even though it's Turing-complete. This is the case for many esoteric languages, like FRACTRAN.

So we really want something that's somehow *"more fundamental"* than that and more broadly applicable. We actually *do* want something that's *inside* the language that can distinguish between two things, though. But how do we do this?

What it really boils down to is this: given two things in our language `x` and `y`, is there *any* way to write a program in our language that behaves differently if you used `x` vs if you used `y`?

A specific question: Is it possible to distinguish between `2 * 3` and `3 + 3`? I will return to this particular question in the *Expressiveness* section.

Formalizing all this is where we get observational equivalence.

But first, we need to talk about what happens when you take a program and cut a hole out of it.

# Programs with a hole

Imagine you take a valid program in your language and print it out. Then you physically cut out exactly one subterm and throw it away. What you have left is a "program with a hole in it," or a printout of a "one-hole context" (sometimes just called "a context").

If you take a slip of paper, write a term on it, and tape it into the hole you now have a program again (as long as the result of this process is well-typed). This is the primary thing you can *do* with a one-hole context: You can obtain a program by combining it with a term that can fill in the hole.

If we call our context `C` and the new term we're taping into it `t` then the complete program we obtain when we tape `t` into `C` is called `C[t]`.

Note that this definition actually always makes sense no matter what programming language we are looking at! I've made *no* assumptions about the language.

Our definition of observational equivalence will center around these contexts (that is, programs with exactly one hole in them).

# Observational equivalence

One way to define what it means for two programs to be "equivalent" is that every observation you can make about them is the same. There is actually a decent amount of nuance to *"what counts as an observation?"* but that's outside the scope of this answer.

We will define observational equivalence like this (*first attempt*):

* Two expressions e1 and e2 are called "observationally equivalent" if, for *every* context C, we have C[e1] = C[e2]

This is *the same* as saying, given those two expressions, does the language provide you a way to tell them apart! It's asking "Are the two expressions identical when plugged into any context?"

*"Uh, wait a minute..."* I hear you say. *"But there's still an equals sign! What does that mean? The whole point was to *avoid* using an existing notion of equality!"*

That is very true! We need to improve our definition. We need to be a bit more clever (this new definition is due to James Morris's 1969 PhD thesis):

> Two expressions e1 and e2 are called "observationally equivalent" if, for *every* context C, we have: C[e1] halts if and only if C[e2] halts

This might seem a bit weird. Think about this for a minute. Does this seem, somehow, wrong?

Take a moment to consider this question: "Are we saying that 1 and 2 are 'observationally equivalent'? Both 1 and 2 very straightforwardly terminate!" (I've taken this from [this part of Shriram's talk](https://youtu.be/43XaZEn2aLc?t=1575). Spoilers for the talk ahead!)

I am *not* saying they are observationally equivalent! An example: Can you write a Python program with one hole in it that will halt if the hole is filled with `1` but will loop forever if it is filled with `2` (you could just write  for the hole and fill it in as appropriate)? If so, you've proven that `1` and `2` are observationally *distinct* in Python! To show that they are *distinct*, all you have to do is find *one* context `C` where `C[1]` halts but `C[2]` does not (or visa-versa). If they were *the same* then every context would behave the same (with regard to halting) regardless of whether you plugged in `1` or `2`.

What if we only have a `isZero(x)` builtin function, but no builtin equality operation? Can we still tell `1` apart from `2`? Well, how about the context `while (isZero(1 - )) { }`? This is why the definition works well: we need to consider *all possible contexts*!

Okay, but what if there is *actually* no way to tell `1` and `2` apart? Then we would actually say that *are* observationally equivalent! Observational equivalence captures the idea of what it means for two things to be indistinguishable inside a programming language.

# Expressiveness

Now how does all of this relate to expressiveness? I'm going to start by way of example. I'll return to the question: *Is it possible to distinguish between `2 * 3` and `3 + 3`*?

My answer: It depends on the features of the language! It certainly is not possible in the language which only has basic arithmetic, functions and recursion. Can you think of a feature we could add where it *is* possible to distinguish them?

Operator overloading! Say we have operator overloading and the ability to redefine existing function. If we overload `*` to do something weird, like return the first argument but we don't overload `+`. We can now distinguish between those two expressions!

By adding that feature, we *broke* an observational equivalence. The expressions `2 * 3` and `3 + 3` *used to be* observationally equivalent. Then we added operator overloading and now they are *observationally distinct*.

Now we need to address how to tell if a feature requires a "local" transformation vs "global" transformation.

## The key theorem

> If feature X can be implemented for language L as a local transformation to obtain the language L+X, then for any two expressions e1 and e2 that are observationally equivalent in L, it is also the case that they are observationally equivalent in L+X

The theorem is proven in [the paper](https://www.sciencedirect.com/science/article/pii/016764239190036W).

This is saying that if feature X only required a local transformation to implement, then it did not "break" any observational equivalences. All of the observational equivalences from L are still true in L+X.

Note that this was *not* the case for operator overloading. Adding operator overloading *did* break some observational equivalences. On the other hand, when we added unary negation we *did not* break any observational equivalences.

Now we can say that when we *add* expressiveness to a language, we *break* some observational equivalences.

One practical implication of this is that some optimization passes might be broken when you add a new feature. This is because optimizations assume that certain things are identical. But when you add a new "expressive" feature, you will break some of those equivalences!

*Exercise for the reader*: I mentioned adding `halt` to a simple language and I said that this is an *expressive* new feature for that language. Can you give an example of an observational equivalence that holds in the original language, but not the new language with `halt`?

# Bonus: Connecting a denotational semantics to an operational semantics

Even though this is just a small part of the answer that is only tangentially relevant to my question, this is what motivated me to write the question and this answer. Particularly, to partially clear up some confusion about denotational semantics [from the comments of my previous question and answer](https://langdev.stackexchange.com/questions/1953/how-can-i-understand-a-recursive-function-in-terms-of-denotational-semantics). This is only one component of that, but it is an important one.

Up until now, we see one useful application of observation equivalence. This allowed me to define it and motivate it. Now we can see, briefly, another application of observational equivalence that is relevant to defining a denotational semantics. It would really be a different answer to a different question to address this in more detail, however, so I will gloss over some things.

There are two very crucial properties you want from your denotation function when you create a denotational semantics. One is called "compositionality" and the other is called "adequacy." "Adequacy" is defined using observational equivalence. Observational equivalence is derived from an operational semantics.

* "Adequacy": If two programs are *observationally distinct*, then they must have *distinct denotations*.

Consider what it would be like if our denotation function was not "adequate." We would have two programs that we can observe are different, but they would be mapped to the same mathematical object. That's not very useful way to denote programs!

# Further reading

## Papers

* [*On the expressive power of programming languages*](https://www.sciencedirect.com/science/article/pii/016764239190036W) by Matthias Felleisen. This paper introduced the formal notion of "expressiveness" I've described above.
* [*Lambda-calculus models of programming languages*](https://dspace.mit.edu/handle/1721.1/64850), James Morris's 1969 PhD thesis. This is the origin of the concept of "observational equivalence" (he called it "extensional equivalence").

## Books

* *Types and Programming Languages* by Benjamin Pierce
* *The Formal Semantics of Programming Languages: An Introduction* by Glynn Winskel
* [*Programming Language Foundations in Agda: Contextual Equivalence*](https://plfa.github.io/ContextualEquivalence/) ("contextual equivalence" is another name for "observational equivalence")
* [*Software Foundations, Vol 2: Programming Language Foundations* by Benjamin Pierce et al](https://softwarefoundations.cis.upenn.edu/plf-current/toc.html)
> **Comments:**
> **username_4** (2023-07-05): This is awesome, but seems to interact weirdly with some specific features. For instance, consider having a `quote` macro that would take its operand and return it as a string. For a language with that and string comparison, any two different expressions are observationally distinct. Does it make this language the pinnacle of expressiveness?  
> **username_5** (2023-07-05): a=a*[hole]  `a=a*2*3` vs `a=a*3+3`  maybe I misunderstand?  
> **username_6** (2023-07-05): Trying the exercise: hole = while(True){ f(0) } versus hole = while(True){ f(1) }.
And as context:
define f(x):
     if x == 0: halt;
[hole]

did i understand this correctly?  
> **username_7** (2023-07-05): @Jasen: I would argue you did, by replacing texts, not expressions. That is, your proposed replacement "breaks apart" the expression `3 + 3`. To replace an expression you'd replace in the AST. So the AST `+ (2) (* (2) (3))` becomes `+ (2) (+ (3) (3))`, or back in text... `3 + 3` is parenthesized implicitly when plugging it back in.  
> **username_8** (2023-07-05): See also Shutt's 2013 post on [abstractive power](https://fexpr.blogspot.com/2013/12/abstractive-power.html), where category theory is used to make expressive and abstractive power into categorical relationships.  
> **username_0** (2023-07-05): @Squala You did! That's a correct answer  
> **username_0** (2023-07-05): @Jasen This does get at a point I glossed over in the answer. As Matthieu said, you are doing *textual* substitution, which is not correct here. The kind of substitution I'm talking about can be thought of as substitution in the abstract syntax tree. You can think of it this way: take `a*[hole]` and draw its AST. One of the children of `*` is `[hole]`. Let's say we want to substitute the AST for `3+3` in for `[hole]`. We end up with an AST that represents `a * (3+3)` *not* an AST that represents `(a * 3) + 3`  
> **username_0** (2023-07-05): I drew a diagram of this situation [here](https://q.uiver.app/#q=WzAsMTEsWzcsMCwiKyJdLFs2LDIsIjMiXSxbOCwyLCIzIl0sWzQsNCwiKiJdLFszLDYsImEiXSxbNSw2LCIrIl0sWzQsOCwiMyJdLFs2LDgsIjMiXSxbMCwyLCJhIl0sWzEsMCwiKiJdLFsyLDIsIltob2xlXSJdLFswLDFdLFswLDJdLFszLDRdLFszLDVdLFs1LDZdLFs1LDddLFs5LDhdLFs5LDEwXV0=). The tree on the left is the AST for `a*[hole]` and the tree on the right is for `3+3`. The tree at the bottom is what you get when you substitute `3+3` for the hole in `a*[hole]`  
> **username_0** (2023-07-05): In case that q.uiver link goes down at some point, [here](https://i.sstatic.net/8MMvw.png) is an image of those trees hosted on the site StackExchange uses for images. I also zoomed out a bit and removed the grid when I made that image, so it might be immediately a bit more readable  
> **username_9** (2023-07-05): @abel1502 Your example is intuitively wrong, but I'm not sure how to formalize why. The most obvious example is `quote(2 + 2) != quote(2  + 2)`, when in fact `2 + 2` and `2  + 2` resolve to the same syntax tree and therefore cannot be distinct.  
> **username_0** (2023-07-05): @Bbrk24 Those would be indistinguishable in a Lisp-style language. `quote` gives you (a representation of) the AST of its argument. However, I agree that it seems intuitively wrong but I also don't know how to formalize why (right now)  
> **username_9** (2023-07-05): @DavidYoung If "quote" doesn't satisfy you, what about C-style `#define STRINGIFY(x) #x` (or, depending on your use case, [doing it twice](https://stackoverflow.com/a/2653351/6253337))? Regardless of you you spell it, the ability to stringify code verbatim interferes with the definition in this answer.  
> **username_10** (2023-07-05): @abel1502 How would quote() make things different if a language already has strings and string comparison? Keep in mind that you have to use quote() in the context, not in the hole, since you need the hole to contain code that is valid in L and L+X. And in the context, you could just use quote marks anywhere you used the quote() macro. Maybe I'm misunderstanding now though.  
> **username_0** (2023-07-05): @ArrayBolt3 The "inside" of a string literal is not a term in the language. However, the string literal, when you *include* the quotation marks, *is* a term in the language. Say we are talking about Python and we have an expression `len("abc")`. Then we can say the whole expression is a subterm of itself. `len` is a subterm in the expression. Also, `"abc"` is a subterm in the expression. *However*, `abc` is *not* a subterm in the expression. A context is a program with exactly one *term* removed from it. So, a hole surrounded by double quotes is not a context.  
> **username_10** (2023-07-05): @DavidYoung True, but that's not what I meant. I meant that you can't fill a hole in language L with "if ( "abc" = quote(abc) ) then do something;" because quote() doesn't exist in language L. Just like how "halt" can make observationally equivalent statement distinct, but you can't use "halt" in what you fill the hole with. You could only use quote() somewhere in the context, and no way of doing that will result in something becoming observationally distinct because you could have just used quote marks.  
> **username_0** (2023-07-05): @ArrayBolt3 You can observe what I'm talking about in Racket, for example. Consider the two expressions `(+ 2 2)` and `4`. Now, consider this context: `(eq? (quote <hole>) 4)`. If you fill the hole with `(+ 2 2)` you will get back `#f`. However, if you fill the hole with `4` then you get back `#t`.  
> **username_0** (2023-07-05): Furthermore, if you are concerned that `quote` is giving back `4` rather than some kind of quoted `4`, consider this context in a language that uses a string-y `quote` rather than a Lispy `quote`: `if (length(quote(<hole>)) == 1) { infinite_loop }` If you fill the hole with `4`, you will get an infinite loop. But if you fill it with `2+2`, it will do nothing.  
> **username_2** (2023-07-06): Follow on question - https://langdev.stackexchange.com/questions/2082/can-felleisens-expressivity-metric-be-abused-to-construct-ever-more-expressive  
> **username_11** (2023-07-06): @DavidYoung Wonderful answer! One question I have though. All of the answers I've seen here to your `halt` exercise (as well as the one I came up with myself) hinge on `halt` terminating the whole program. So what about `break`? As implemented in C and most other mainstream languages, `break` is lexical, which means it breaks out of the nearest enclosing *lexical* loop. Intuitively, `break` is a non-local transformation. But we can't just hide a `break` in a function like we did `halt` to prove it. Do you have an example of two expressions that are equivalent in `L` but not in `L + break`?  
> **username_0** (2023-07-07): @SilvioMayolo Thank you! That's a very interesting question. I've thought about it for a bit and I've come to the following conclusion. Even though it intuitively seems like `break` is "expressive," it looks like it can be implemented as a collection of macros with each one being local: turn `while (cond) { C }` into `{bool b = false; while(b || cond) { C' } }` where `b` is fresh. Then, transform *every* statement to include an `if`. So, `x = y` becomes `if (!b) { x = y }`, etc. `break` becomes `b = true`. Also put `bool b = false` in the outermost scope. Not efficient, but it should work.  
> **username_12** (2023-07-07): There are many situations in which it is not possible for a program to behave usefully (e.g. because it receives superficially valid but nonsensical input), and a wide variety of tolerably useless behaviors would be equally acceptable, but some behaviors would be intolerably worse than useless.  Can the principle of "observational equivalence" handle this?  
> **username_0** (2023-07-07): @supercat Hmm, I'm having trouble understanding what you mean. Maybe you could give an example?  
> **username_12** (2023-07-07): @DavidYoung: Suppose a language specifies the integer of overflow such that the result may behave as the non-deterministic union of all possible mathematical integers, but (1) it must have no side effects, and (2) any particular evaluation of any conditional expression must always behave as though it yields true or it yields false (collapsing any non-determinism).  Under such semantics, it would be possible to statically examine many programs and answer many questions of the form "Is there any input for which the program might do X", but the general question of whether any particular output...  
> **username_12** (2023-07-07): ...could be produced by a particular execution of the program given any particular input would be undecidable.  If a particular language makes it possible to prove through static analysis that a program won't perform a certain unacceptable action X no matter what input it receives, is there any way to distinguish superset languages that would also facilitate such proofs from those that would make the question of whether the program might do X undecidable?  
> **username_0** (2023-07-07): @supercat I'm still having some trouble understanding, but let's see if I've got part of it: You are describing a language which has a static analysis feature that will semi-decide some, in general undecidable, property about a program. Without this feature, you could *not* semi-decide this property inside the language. And the question would be: "can 'Felleisen expressiveness' explain the new amount of expressiveness added by the static analysis feature?" Is that close?  
> **username_12** (2023-07-07): @DavidYoung: I think the simplest way to describe it may be that a Turing machine program represents a mapping from possible inputs to outputs, but in some cases it may be useful to be able to specify a mapping from inputs to sets of acceptable outputs., such that an optimizing compiler would strive to generate the most efficient machine code which, for any input in the set, will yield an output which is within the corresponding set of acceptable outputs.  
> **username_0** (2023-07-07): @supercat Okay, I think I understand now. Something like undefined behavior in C (although not necessarily as messy) or a program synthesis task using some ambiguous specification. I don't think observational equivalence in terms of contexts quite captures that. If you expand the notion of "observation" to a set of runtime behaviors, you might be able to use Felleisen's expressiveness, though. There are situations when you might need to change what you consider to be "observations" like this. This can happen in security, when you need to consider micro-architectural states for side-channels  
> **username_13** (2024-10-07): Delightful answer, thank you. Your point about "if I add feature X will my optimizing compiler do a bad job?" works in the opposite direction as well. Back when I was working on VBScript in the 1990s we used a build of the MSVC++ compiler that had compilation of programs with exception handling *disabled* because it generated better code than the same compiler with exception support turned on.  
> **username_0** (2024-10-15): @EricLippert Thank you for your comment! That is interesting. I hadn't considered that kind of situation in that way before.  
---
### Answer by username_14 on 2023-07-06. Score: 7
I don’t believe that’s generally possible. Expressive power depends on what specifically is being expressed.

Your python versus assembly example is obviously more expressive when you write general-purpose scalar code, manipulating strings or XML or JSON, access files or network.

However, for other programs the expressiveness can be opposite because processors are implementing interesting instructions hard to express in Python. For modern AMD64 processors, [bit manipulation](https://haskell-works.github.io/posts/2018-08-22-pdep-and-pext-bit-manipulation-functions.html) like `popcnt`, `pext`, `pdep`, vector math like `psadbw`, `pshufb`, `psignd`, `dpps`, saturated integer stuff like `paddusb`, checksum and cryptography support like `crc32`, `aesenc`, `aesdec`, `sha1rnds4` are easy to express in assembly (and even easier in C++ with intrinsics because the compiler takes care about register allocation and scalar parts of the code), but harder to express in Python.

The observation is not specific to AMD64, other instruction sets also contain instructions hard to express in higher level languages. An example is ARM’s `rbit` instruction which reverses order of bits in an integer. That single instruction requires rather complicated code to express in higher level languages. Other ARM examples are saturating arithmetic, and `bfi`.
> **Comments:**
> **username_15** (2023-07-06): There is the most highly upvoted answer on this site, by a high-rep user, that directly contradicts your first sentence @Soonts  
> **username_16** (2023-07-07): @Starship-OnStrike I think it's reasonable to say that David's answer (while very interesting) doesn't necessarily give us tools to answer questions like "which is more expressive, Python or assembly". It's a neat result, but it doesn't mean this response isn't also useful.  
> **username_0** (2023-07-07): It sounds like the main disagreement is with the first sentence of the answer. I see two different readings of that sentence, depending on how you interpret the scope of the word "generally": (1) *"There is no technique that will compare any notion of expressiveness between two Turing complete languages"* (2) *"No technique for measuring expressiveness works for _every_ form of expressiveness"*. I don't agree with (1), but I do agree with (2). I suspect (2) is intended for this answer, though.  
---
### Answer by username_17 on 2023-07-06. Score: 3
Matthias Felleisen's [paper](https://www.sciencedirect.com/science/article/pii/016764239190036W) is a little hard to follow. It gives an expansion-based notion of expressive power.

In the concluding paragraph, Felleisen expresses the belief that this is a
superior way of exploring expressive power to the approach based on
interpretation. I think that is referring to the general idea that a language A
is more expressive than B, if the only way to get B to express programs in the
same way as A is to write an A interpreter in B and then just run the A
programs.

Turing showed us the concept of a Universal Turing Machine, which is
programmable. What that means that for any given Turing Machine (input tape
plus symbol manipulating rules), the Universal Turing Machine can be programmed
to run that Turing Machine by an extended tape: a tape which contains
instructions for the Universal Turing Machine, followed by the
to-be-simulated/emulated Turing Machine's tape. The UTM concept tells us that
(if resources are no object), we can directly run the programs of one language
in any other language, by interpreting it.

Thus, Turing equivalence speaks to expressiveness because we know not only that
any universal machine can calculate all the same recursive functions as any
other, but that an universal machine can interpret a calculation written in any
expressive form. If a language A, however, can *translate* a program in
language B into language A, such that no interpretation is involved; B programs
thus translated are at no performance disadvantage compared to A programs, and
interoperate easily with A programs, that that somehow gives us a more
satisfying sense that B has the expressive power of A.

Felleisen's basic idea seems to be this. We would like to compare the
expressive power of two languages L0 and L1, using the concept of translation.
Firstly, we need some common ground. We assume that there is a common language
L, from which L0 and L1 are derived.

Informally, we can identify L as a common virtual machine for L0 and L1.
Languages L0 and L1 expose some subset of L. We make a simplifying assumption.
Whenever L0 or L1 feature something from L, that feature "looks like" the L
feature; it is not weirdly disguised, twisted or damaged in some way.

We allow L0 and L1 to have macros.

Then, we can say that L1 is strictly more expressive than L0 if L1 can use
macros to express every L0 program, but the reverse isn't the case.
For any construct in L0, an identical or similar macro is defined in the L1
program, if necessary, and then the L0 construct is simply transliterated,
but in the reverse direction, there are L1 constructs that aren't in L0,
and cannot be provided by L0 macros.

Now, according to Turing, we could have some `L1-interpret` macro in L0 such
that `(L1-interpret '(... quoted L1 program ...))`. But the quoted L1 program
is being (partially or entirely) interpreted and not actually translated into
L0 primitives.

We rule out this Turing interpretation trick as not providing a true
expressiveness bridge for the follwoing reasons. If L0 can only express L1
programs by interpreting them, then those interpreted L1 programs are not
directly using the required L features, which are used by the real L1
implementation.

We can justify that with an example. Suppose that the underlying L has, say,
dynamic non-local transfers (for implementing exceptions and such), with unwind
protection. Suppose that feature is exposed in L1, but is not found in L0: L0
has no dynamic control transfers, no unwind-protect. Then it will be
impossible for L0 to translate and execute an L1 program, other than by L0
providing its own implementation of dynamic non-local control transfers, which
are not based on the ones in L. L1 programs execute in L0, but in with a severe
limitation: they cannot initiate a dynamic control transfer which jumps out of
L0 entirely and terminates in an exit point in a *genuine* L1 program running
directly on the L machine. More importantly, the interpreted L1 programs also
cannot catch exceptions emanating from L itself, like from the L I/O library or
what have you. L0 has no access to that; it has no way of catching exceptions
and forwarding them into the interpreted L1 code. Thus L1 programs themselves
lose expressiveness with respect to the L environment if they are interpreted
by L0.

The generalization is that if L0 exposes only a subset of the L features than
L1 exposes, in a way that some L1 programs cannot be converted to L0 programs
while remaining fully-fledged L programs, but L0 programs **can** so be converted
to L1 programs, then L1 has more expressive power.

Expressive power is related in some way to succinctness but not defined by it. If both L0 and L1 have macros, they can both condense code. The above notion of expressiveness strikes at the idea that there are situations in which L0 cannot express some **semantics** in L1 in spite of having macros for expressing the **syntax**. You can write the interface part of the macro which matches the syntactic pattern of the L1 construct, and all its conciseness, but have no way to actually write the transformation: the macro's target language doesn't have the constructs for **expressing** the macro's meaning.

If we have a L0 and L1 which both have all the features of L, but L1 has macros whereas L0 doesn't, then conciseness becomes utterly relevant to expressiveness, because L1 macros can express new kinds of constructs that are not replicable in L0. If we take the fully macro-expanded L1 program, we can express *that* in L0, because all the constructs it's using are available in L0. Expressing the macro-expanded program is not the same thing as expressing the original program.
> **Comments:**
> **username_2** (2023-07-06): This seems to require that both L0 and L1 share a common subset of feature L which I suppose must be vacuuously true given that both are turing complete. But doesn't the answer actually depend heavily on L?

Also how can we be sure this ordering relation is total or partial? If you compare two languages you might find they both have features that can't be expressed in the other. E.g. L0 has exceptions but L1 has continuations.   L0!>L1 && L1!>L0 && L0 != L1  
> **username_2** (2023-07-06): Third point. I would argue that a macro system makes a language more expressive. So if L1 is L0 but with a macro system an ideal metric should say L1>L0  
> **username_17** (2023-07-06): @BruceAdams Turing machines don't have to share any common L. E.g. we can have a tape with a read/write head, versus lambda calculus.  Now suppose we are talking about real languages. We can identify multiple L's. They all run on my PC, so L could be x86-64.  No wait, both languages are on the JVM, so that's the L.  Perhaps L should typically be something like the highest level substrate that the two have in common.  
> **username_17** (2023-07-06): In reality, we often deal with differently expressive languages. Say we have some language with macros, but is missing something relative to another language. Neither is strictly more expressive than another, but for some task where that missing something is critical, the language which has that feature is expressive, whereas the other one isn't. Where that missing feature is not relevant, the language with macros is more expressive.  Tasks often just require a subset of a language, and so expressiveness can be evaluated over subsets.  
> **username_17** (2023-07-07): @BruceAdams Regarding your point, yes, I hoped to convey that that would be true. If L1 is L0 with macros, it is more expressive, because the macro expressions in L1 have no equivalent in L0. In this answer, to express means to present in the same way, expression by expression. If L1 uses a `with-open-file` macro, but `L0` handles all errors and manually cleans up, `L0` is not expressing what `L1` is expressing.  
---
### Answer by username_18 on 2023-07-06. Score: 2
A straightforward approach is to write the same program in multiple languages, [minify](https://en.wikipedia.org/wiki/Minification_(programming)) the source code (so that you're counting only “real” code rather than indentation or variable name length), and score “expressiveness” as inversely related to the number of bytes of minified code.

However, this fails to meet your criterion of being “unambiguous”, because it depends on the choice of benchmark program(s). Different languages have different standard libraries and different domain-specific features, making some languages better specialized for specific tasks than others. For example, if your assignment is to write a simple `cat`-style program that copies data from stdin to stdout, it's hard to beat the 5-character program Brainfuck program `,[.,]`. But the language is unwieldy for pretty much anything else.
> **Comments:**
> **username_17** (2023-07-06): Two languages can both be given "minifying power" via structural macros. Yet it may be that programs in one still cannot be expressed in the other, no matter how you try to write the macros.  E.g. Common Lisp doesn't have continuations. You can't get them via macros. You can create a macro-based sublanguage in which there are continuations, but those continuations are restricted to staying within that language. You've not introduced continuations into the underlying Common Lisp; you cannot capture the computing future of arbitrary Lisp code as a continuation.  
> **username_19** (2023-07-06): If I were to take Python and add in INTERCAL’s requirement that some percentage of statements begin with `PLEASE`, the resultant language would score less favorably by this metric, but would not be any less expressive. Similarly, deriving a language that substitutes APL-style special characters for keywords from Python would score more favorably by this metric, even though it is no more expressive than Python. At minimum, you need to be looking at token counts, not character counts.  
---
### Answer by username_20 on 2023-07-06. Score: 2
Expressive power is absolutely not about the lines of code required to achieve the needed functionality. If we would count so, the most expressive language is Bash. Feel the power:
firefox

A complex browser, with rendering engine, security, scripting and lots of other stuff is implemented with just a single line of code. One may say, best language ever. No firefox on the system?
firefox || sudo apt-get install -y firefox && firefox

We are still able to provide the firefox anyway with just one line of code, this will work nice also if it is already present. But if there is no existing program available, building brand new functionality with Bash is less fun, even if possible.
Now feel the Python expressive power for the following real world example (source):
numpy.where(arr<0,arr,0).sum(0)

Assuming you are not an expert of the large numpy API yet, it may actually take the comparable time to understand the same in Assembler (source):
  xor  edx, edx
  mov  esi, [arr]
  mov  ecx, [arr_rows]
  imul ecx, [arr_cols]
more:
  mov  eax, [esi]
  test eax, eax         ; TEST is efficient to inspect the sign
  jns  skip
  add  edx, eax         ; Only adding negative values
skip:            
  add  esi, 4
  dec  ecx
  jnz  more

and while the old C++ version may not look very cool, I still suspect that for many it would take less time to understand it than that numpy twist:
   int sum = 0;
   for (int v: arr) {
     if (v > 0) sum += v;
   }

Bash (source) ?
sum=0
for file in $*
do
  for number in `grep -wo "[0-9]*" $file`
  do
    if [[ $number -gt 0 ]];
    then
        sum=$(($sum+$number))
    fi
  done
done
echo "Sum: $sum"

Not that easy, even if we tried to play on Bash stronger side a little bit by accessing the existing program, grep. Similar problems as with Python: to understand this code, you need to know that the grep is and which switches does it take. $* is also not for mundane ones, further illustrating the fact that "two characters only" does not necessary mean a lot of readability. Something more along all_args would probably be understandable without googling this answer.
Python looks somewhat similar to Bash (and some administrators actually use it that way). When there is a complex functionality available, it is great in accessing it. Especially when that complex functionality does not actually take or return any complex data structures to deal with, just does its magic when called by name. But when implementing some complex algorithm from the mathematical article, Python may still not be the best tool for the purpose.
I am not sure what the "expressive power" means exactly, but the language I would pick for implementing or developing some complex algorithm should:

Make it very easy to implement the huge number of the known software design patterns I expect to use.
Provide reasonable amount of context. A structure with named and typed fields provides more context than a map that could contain almost anything, and may take long time to figure out what exactly. Python is proud of demanding very little context, but I really had big problems in understanding complex undocumented structures as returned by some third party libraries. In C++, this would at least not compile.
Make it easy to split a complex step into multiple simpler steps.
Due reason above, it must run loops at usable speed, because a single iteration of the loop is often much easier to understand than the complete action on the whole array, expressed in the terms of matrix algebra or the like.

From the other side, a language that is explicitly designed for the group of tasks where our current task also belongs may be very expressive and efficient there, easy to write and read. I would probably put the winner on SQL here, at least against Python, even it it is not Turing complete:
select sum(x) from array where x > 0

I am convinced that likely any non programming teenager would understand.
> **Comments:**
> **username_14** (2023-07-06): “One may say, best language ever. But it may be something wrong with this view.” I share that view, and I don’t think there’s anything wrong with it. For this particular problem, and for many other programs which only need to run other programs (no matter how complicated), and pipe these input/output/error streams forwarding them into yet another programs, Bash is incredibly expressive. People are using Bash and similar languages all the time, precisely because these are probably the most expressive languages _for that particular class of problems_.  
---
### Answer by username_12 on 2023-07-07. Score: 1
In many cases, it's useful for a programmer to be able to specify "don't care" aspects of program behavior, and allow an implementation to choose in Unspecified fashion from among them. While all Turing Complete languages may be equally capable of handling all situations where, for any particular input, a program would be required to produce some particular exact ouptut, there can be substantial differences in their ability to specify "don't care" aspects. From a purely theoretical standpoint, there's never any need for a programmer to characterize any aspects of behavior as "don't care", but from a practical standpoint it can nonetheless be useful.

Consider, for example, the design of a circuit which accepts 32 inputs and produces one output, subject to the each of the following set of requirements:

Set #1:

1. If more than half of the inputs are high, the output must be high.
2. If less than two inputs are low, the output must be low.
3. In all other cases, the output may be arbitrarily high or low.

Set #2:

1. If more than half of the inputs are high, the output must be high.
2. In all other cases, the output must be low.

Any design that satisfies the first specification would also satisfy the second, but a minimal circuit which upholds the first specification could be realized much more cheaply than one which must satisfy the second. If application requirements would be satisfied by either circuit, the first circuit would be a cheaper way of satisfying such requirements than the second would be.

The second requirement could be satisfied by using eight circuits which each accept four inputs, and have four outputs indicating whether at least one, at least two, at least three, or at least four inputs are high. Those could then be paired to yield four sets of outputs indicating whether at least one, etc. up to at least eight inputs from each group of 8 are high, and those can then be paired to yield two sets of 16 outputs. From there, one can report that the condition is satisfied if at least one input from the first group is high and all sixteen from the second group is high, or at least two from the first group and at least fifteen from the second group, or at least three from the first group and at least fourteen from the second group, etc. Possible, but expensive.

The first requirement could be satisfied by having 16 circuits each examine a pair of inputs and reporting whether both inputs of each pair are set, and then checking if any of those circuits reported true. Much simpler.

In this case, a human writing the specs migh recognize that a specification making the output high if any pair inputs had both inputs high would be cheaper to process than one which outputs low unless at least half of the inputs are high, but in many cases it would be useful for a compiler to be able to automatically identify which acceptable combination of behaviors could be realized most efficiently. Languages vary considerably in their ability to express such concepts.
---
### Answer by username_21 on 2023-07-08. Score: 1
Most people would consider "expressiveness" as the time it takes them to get a certain task done without bugs. As such, there won't be an accepted way to compare two languages. It would require an infinite set of expensive tests and people would argue whether the submissions are really comparable or if the subset of actual tests is a good one.

If there were such a notion, people could simply optimize on it. But this does not happen. In fact, the Python vs. assembly example is already wrong, because programming a micro controller with Python would not lead anywhere. Or if you want to make use of a certain processor instruction. What I'm trying to say here is that actual expressiveness depends on the domain you are operating in. In such a domain, certain concepts can help you that might even be considered a reduction of expressiveness in other domains. Ada has a lot of concepts that work well for programming rockets but are in your way when building common desktop software.

Nonetheless, if you really need such a notion for some sort of comparison you made, I'd time how long it takes to write a program for a predefined set of tasks in each language. The issue with such comparisons is that they overrate languages that are good for trivial tasks and bad for implementing large software projects.

What you could also do is compare expressiveness of type systems. However, you'll end up in a similar situation as with Turing completeness, because a lot of them can express arbitrary proofs and computations and there is no really good way to say "in a sane piece of code".
> **Comments:**
> **username_2** (2023-07-08): I think its not so much that it can't be done rationally and objectively but that it is hard. Not just AI hard but a hard multi-variable optimisation problem for humans too. By attempting to formalise it we try to remove the human biases.  
> **username_21** (2023-07-08): While I appreciate the idea, I doubt that the formalization will result in something that reflects the subjective understanding of "expressiveness" of most people. At least if it is provably a partial order on formal semantics of programming languages. The thing with these approaches is that marginal changes in the formalization can have massive impacts on the outcomes of such orders.  
---
