How can we compare expressive power between two Turing-complete languages?
langdev.stackexchange.comThe answer given is thorough, but somewhat abstract. As a more concrete response, go to projecteuler.net, solve a problem, and go to the discussion board for it.
For most problems:
There will be a ~80 line C solution.
There will be a ~120 line Java solution.
There will be a ~50 line Javascript solution.
There will be a ~40 line Visual Basic solution.
There will be a ~30 line PHP solution.
There will be a ~25 line raw Python solution.
There will be a ~20 line typical Lisp solution.
There will be a ~15 line Python solution using some obscure library.
There will be a ~10 line Lisp solution using some clever hack.
There will be a 1 line J solution.
(other languages omitted, and line estimates are pulled out of my ass)
Whether due to unfamiliarity or genuine opacity, some of the shorter solutions will be incomprehensible to some (most?) people. So while technically more expressive, what good is that if you can't read the solution, let alone write it?
But yeah -- typical line count proxies (inversely) for expressiveness.
IMO, the line count is more a function of the "base/standard" libraries as opposed to expressiveness
I don't disagree, the expressiveness of base Python is less than Python + whatever libraries you like.
But the difference in line count between Java + a bunch of libraries and Python + a bunch of libraries is a lot. And the J one-liners rarely involve libraries.
> the difference in line count between Java + a bunch of libraries and Python + a bunch of libraries is a lot
In term of line of code yes, that's correct. But i think this simply shows that "delta in number of line of code" is not a great approximation for expressiveness. The difference between java and python are mainly "ceremonious" line of code that case be generate by any semi-serious IDE. I would put python and java in the same general class of expressiveness (even if python is much more terse).
I think "expressiveness" of languages form a partially ordered lattice, with few language on top.
- Some languages are unilateraly more expressive than other like C++ vs Java
- Most it depends : scheme vs C ; If you are talking about meta-programming and AST manipulation scheme is more expressive. If you are talking accurate memory modeliation and bit manipulation C win.
Since all the languages we're talking about here are Turing-complete, if you don't consider line count or code complexity, then they are all equally "expressive".
So almost by definition we have to look at what is syntactically well-supported, not just "supported at all."
And part of that can be proxied by "I want to do xyz, how many lines of code is that going to take?"
And part of that means that "ceremonious" code isn't excluded, even if a competent IDE can provide it. If um my um comment um includes um a um bunch um of um junk, it doesn't matter if a quick find-and-replace would fix it, it's still annoying cruft that shouldn't be there.
I’ll bring that python solution down to 2 lines with some nested list/dict/set comprehension and lambdas…
Yep, I've seen those.
> Whether due to unfamiliarity or genuine opacity, some of the shorter solutions will be incomprehensible to some (most?) people. So while technically more expressive, what good is that if you can't read the solution, let alone write it?
How many people can read advanced math formulas? Mostly none. So what good is it that they are used?
The answer is, it doesn't really matter if outsiders can't read it. Yes, it increases the hurdle to enter the field, but the benefits drastically outweight the initial learning in the long term.
Same is true (even more so, I would say) for programming languages.
>How many people can read advanced math formulas? Mostly none. So what good is it that they are used? The answer is, it doesn't really matter if outsiders can't read it. Yes, it increases the hurdle to enter the field, but the benefits drastically outweight the initial learning in the long term.
Do they? I feel like a "citation needed" is in order.
There's a target for math formulas, and it's mathematicians. Those can read math formulas, even advanced ones. If outsiders (that is, laymen) can't read them, it's ok: they aren't supposed to be working with math most of the time.
The target for programming languages is programmers. But unlike math formulas, the outsiders that can't read some language J isn't laymen, but still programmers. The problem is not that non-programmer Joe Sixpack can't read J. The problem is that programmers can't read it, or find it unyieldly.
You could argue that, 'that's ok, the target for J is people who comprehend and are productive with something like J'. Sure, but that's precisely what we call out here. That some languages, even though expressive technically, put off not just outsiders from programming, but also programmers.
I don't think every mathematician can read any formula, no matter of the field and how advanced it is.
And for developers it's the same. However, I'll grant that PLs are evolving faster than math does, so there is more catchup-required for sure. But without that there would be much more limited progress. Think lambdas: before they were an "elite feature" and now they are everywhere and languages have adopted them and people had to learn new syntax.
Experts in J say something like, "If you think through the problem, you've solved the problem in J"
I definitely agree that "can outsiders, or even less experienced coders, understand it?" is orthogonal to "expressiveness." I went a little harder than I intended listing that as a drawback to expressiveness, although it's certainly a complementary feature: given two languages of equal expressiveness, the one that encapsulates that range in more comprehensible terms is "better" (there are many other factors to consider, hence the mitigation quotes).
I love the fact that in J:
Meaning that you can express, from primitives, calculating the mean average with just four characters. And even with my very weak J, that's clear. But then I look at something I wrote over ten years ago:mean =: +/%#
and I have zero clue how to interpret that. It's almost certainly not idiomatic J, so it's possible (likely) that it looks like garbage to a J expert as well. Certainly J's terseness doesn't lend itself to commentation. :-)candidates =:,/((_4]\4#"3 (_1 + 2 * #:i.2^9) (* &. |:)" 1 _ list) * (>rowSigns))
That's true. After all, in my E-lang I can solve every Project Euler program in under 6 bytes.
Even monopoly odds?
I don't think this formalization does a great job of what we intuitively mean by expressive power.
For one thing, there is no real way to use this definition to compare different languages, only the same language with one extra feature.
For another, even for individual features, it is too coarse. The very fact that it doesn't consider syntactic sugar expressive is wrong - most people would agree that a language with more syntax sugar is more expressive, since it allows you to avoid writing boilerplate. By this definition, list comprehensions and switch expressions for example don't add expressive power to a language.
Even if we ignore syntax sugar, the comments point out another counterintuitive property of this definiton: any language which includes a facility to convert expressions to ASTs is maximally expressive, since that facility can be used to distinguish any two expressions. This includes things like Lisp's `quote' special form or C's # macro, but also built-in code parsers. So, C++ for example added no expressive power to C by this definition, since C was already maximally expressive:
#define quote(x) #x
if (strcmp("3 + 3", quote(3 + 3)) {return 1;}I would push back on the interpretation that syntactic sugar, by virtue of making programs shorter, is more expressive. APL folds entire compositions into single character sequences, but one would probably not argue that it is more expressive than Brainfuck.
Rather, it seems expressiveness as used in common parlance is closer to ease of comprehension. We like programs that are easy to "think of", that are "natural" to write in that they are succinct and "natural" to read in that they mimic what you are conceptually trying to accomplish. This has very little to do with programming language design and more the experience of the language user - aesthetics, really.
Uh I think the CS-theoretical part of your comment kinda whooshes over my head, but I think it's good to clarify what you're doing with the return value of strcmp().
I'm sure you probably know this, but for non-C-programmers it's not obvious: strcmp() returns 0 when the strings are equal, <0 if the first string is lexicographically less than the second, and >1 otherwise.
Since the two strings handed to strcmp() in your snippet are equal, it will return 0 and the if will not execute.
The C preprocessor is an example where expressiveness definitely stops being an honorific and starts being a liability.
But then you are perhaps back to square one, since the motivation for the question was to get away from the Turing Complete categorization which says nothing about whether it is practical to solve certains problems in a given language.
Glad to see Matthias Felleisen's paper "On the Expressive Power of Programming Languages” mentioned right off the bat.
Shriram’s talk on the same is mentioned too—Shriram is a great guy and I’ve enjoyed all my interactions with him. He’s working on improving CS education. There’s a neat program called “Bootstrap” that he’s helped found that aims at teaching algebra with programming. The idea is that functional programming helps students grok important algebraic concepts. (Sorry if I slaughter the description.)
Anyway, I appreciate these people and their work. Cool stuff.
(Disclaimer: my advisor has had both Shriram and Matthias as advisors. I thought they were cool before starting my PhD though, so it’s genuine. :)
I think it also bears mentioning that Felleisen and Krishnamurthi are two of the authors of the eminent How to Design Programs [1]. For anyone looking to begin their journey into the world of software development, it’s really hard to beat HtDP! It will teach you a systematic approach to software design and development, without letting the messy details of programming languages get in the way.
https://www.bootstrapworld.org/ for the curious
The answer is great, but I'm questioning its underlying assumption of what "expressiveness" really means, upon which the remainder of the explanation rests.
>> 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
If adding features that could be implemented as macros doesn't make the language more "expressive", then the inverse should be true: Removing features that could be implemented as macros would not make a language less "expressive".
This seems to favor c++, in which basically anything imaginable can be done with macros, and any other language can be implemented. There's no global-level total thing that's missing which can't be cleverly built at an inline level. Yet all of c++'s granularity in memory management requires a huge amount of verbosity, which is to say it isn't as expressive (to me) as something that just runs garbage collection out of the box and makes assumptions about weak vs. strong references and lets you tinker with them if or when you like.
"Expressive" to me implies being able to get a lot of meaning across in a few choice words, whilst having a broad vocabulary to choose from.
Does adding .reduce() add no expressiveness to Javascript, just because it's easily implemented with a macro? I'd argue it adds a lot, because it adds a new color to the palette; it gives rise to styles of programming that allow one to distinguish intentionally between normal loops and functional recursion, and choose, i.e. express, the music according to their own intent.
> This seems to favor c++, in which basically anything imaginable can be done with macros, and any other language can be implemented.
Pfft. C++ macros can't even run a different compiler:
https://github.com/m-ou-se/nightly-crimes/blob/main/yolo-rus...
uh, what? Random Rust code?
That's the heart of Mara's Rust proc macro nightly_crimes!
This macro allows you to use Rust's unstable nightly features from your stable Rust programs, in some sense this is clearly silly and can't work, but it actually works fine†. The proc macro is allowed to run software, in this case it destroys the running compiler and launches a different compiler, then it tidies up the resulting mess.
† In a very literal sense, obviously in principle you should never use this, that's why it is named nightly_crimes! not perfectly_reasonable_idea!
>>> a feature does not "add expressive power" if we can implement it as a macro that turns it into something in the original language
But a macro is just an integrated language that lets us emulate more expressive features. To me that's no different from implementing a more expressive language in a simpler one, so this claim seems equivalent to saying all Turing-complete languages have the same expressive power because you can emulate them in each other.
Well put.
In my humble opinion the SO question and some of the comments here conflate "expressive" as it's used when talking about the theory of computation and "expressive" as it's used when comparing various high-level programming languages. The former has a very precise (but also quite narrow) formal meaning and the later is just the normal English work "expressive". They mean very different things so I think it's a bit unfortunate that we use the same word for both because some people get the idea that they're somehow related when they're really not. I mean, in a way regular expressions are more expressive than turing machines but turing machine are more expressive than regular expressions.
Even though that's a reaction on the title rather than the (interesting) content, I would like to add that Turing-completeness isn't the gold-standard of languages. Some very interesting languages like Agda or Idris focus on the benefits of abandoning it.
Can you say more about the benefits?
In a Turing complete language, the halting problem prevents you from proving formally that any program has certain properties (say, that it doesn't leak memory).
In a language where any program halts by construction, the compiler can actually check such properties.
Strongly recommend the talk on which this answer is based: https://www.youtube.com/watch?v=43XaZEn2aLc
David Young's answer seems to give a precise mathematical criterion for deciding whether a language feature is mere syntactic sugar or more fundamental. Neat!
What are some practical examples of expressive features that distinguish popular languages?
The link mentions exceptions and operator overloading.
I won’t embarrass myself by speculating here :)
I think "sum types" and "pattern matching" in functional languages are great and expressive.
A sum type is basically an enum type you can associate arbitrary (but still strongly typed) data with (like associating two strings and an integer for one case, and nothing at all for the second case).
Pattern matching is basically like a switch statement on these sum types, destructuring the data and branching on the different cases. It comes with compile-time checking making sure you've covered all the cases if your business requirements change which is helpful too.
They are useful for implementing state machines which go from one discrete state to another. They've also been used to implement data structures like balanced binary trees, but I think that's a less "everyday" use for them.
I hope I explained them at least sort-of clearly. I think their functionality can be replicated in other ways (like defining an abstract Animal class and implementing Cat and Dog classes, instead of defining an Animal "enum" and a function that branches on each case), but this feels more natural and expressive to me personally.
Functions. Goto. Return. Destructors. Dynamic dispatch. Macros. Templates. System calls. Async. Generators.
I like the phrase "pacman-complete", that Brady coined for Idris, to express more practical concerns besides pure algorithmic computation. Personally I would argue that for example brainfuck is not pacman-complete despite being turing complete. But then interestingly enough I don't think pacman completeness necessary implies turing completeness either.
Regarding the definition of “observational equivalence”: I would love to see an example of two non-trivial statements that aren’t equal but are observationally equivalent. It seems impossible in almost any programming language.
2 pure functions that calculate n digits of pi using different algorithms.
I guess you could exploit memory layout, different number of variables or timing attacks to distinguish them, but that's cheating IMHO. By that same method you could distinguish anything that compiles to different machine code.
You could argue that an implementation of a function to which you added asserts to make sure that logical invariants are maintained is different from the implementation without. The asserts will never trigger because they enforce properties that are always true for this function.
I think the interesting problem being described is:
Find two non-trivial algorithms so different that their equivalence is difficult to establish but which will always produce the same results.
Artificial code obfuscation techniques are not allowed. The algorithms can’t just be differently obfuscated versions of each other.
I.e. both algorithms should be in their simplest form given their respective approaches.
I don't even think that Turing completeness and expressive power are linked at all. You could easily imagine a language like haskell without general recursion or inductive date types. It's still much, much more expressive then C, but without the Turing completeness.
Expressive power to me is something akin to "how easy is it to express a problem as close as possible to it's natural state in a PL".
I'm interested in the more general problem; how can you compare expressive power between completely different models of computation?
Are neural networks more or less expressive than other forms of computation like register machines? What makes them so? And what can we do to make them more expressive while still being trainable?
In CS 61A we weren't taught about Turing complete, we simply learned that expressive power is the ability to represent the abstractions you use to solve or model a computational problem correctly and efficiently.
Have language X implement language Y and vice-versa?
See, that's the problem: it doesn't work!
If both languages are Turing-complete, you can always implement language X in Y, and Y in X. That's basically the definition of Turing-completeness.
Any feature can be implemented in the destination language, even if it is by something as silly as running the source language compiler and executing the resulting bytecode in a x86 VM in your destination language.
Giving the GP a more generous interpretation: let L(X, Y) be the shortest possible size of an interpreter of language X written in language Y. If L(X, Y) > L(Y, X), then implementing X in Y requires more than implementing Y in X, and X could be considered "more expressive" than Y. That said, the answer in OP is much more insightful and thought-provoking.
A very large L(X, Y) need not indicate that Y lacks expressiveness, but instead could indicate that X is a hugely complicated language. E.g. X might have a primitive that greps from all of Wikipedia snapshotted at some fixed time. Or X could have a huge standard library (think Mathematica).
I think a better way to compare languages is to take some collection of tasks, e.g. the first so many Euler problems, and see how concise the best known solutions in language X compare to those in other languages.
It would be best to express the length of all programs in bits, so that languages with alphabets significantly smaller than ASCII like Brainfuck or Binary Lambda Calculus are not unfairly penalized. The latter would seem to be particularly expressive [1].
So if you add "EVAL_AS_Y{ ... }" core primitive into X, it becomes strictly more expressive as Y until you add "EVAL_AS_X { ... }" to Y: then they become exactly as exressive as each other.
This would be in line with my thoughts.
Of course, my off-hand comment is just an exercise rather than an objective measurement. It'd only suffice for trivial examples (say, where X is a strict subset of Y).
You can even prove that languages that can do IO are equally fast. For example for every Java program there is a C program with the same performance: just put the binary of the JVM in a .c file, and write out a JVM on the disk at compile time, and start it from C at runtime. Then you have a C program for every Java program, which has the same performance.
How do you implement sleep() in lambda calculus?
Or `read` or `write` or invocation of any syscall. There is more to computer system than pure computation.
Understand curry howard and you're on your way to answering this question
Every person i've met who uses turing equivalence as a real argument about PLs has been a deficiency clown
>deficiency clown
What is that?
I feel like these kind of questions will be explored more in the future when LLMs are more powerful. You could get some equivalent corpuses of different languages and train an LLM on each one and then see how capable is the resulting LLM of the respective language. Presumably if everything else is equal the language with more capable resulting LLM would be better in some sense, maybe this sense would be called 'expressive power' or maybe called another thing.