12 ms·
How can we compare expressive power between two Turing-complete languages?
- scj 3y agoHave language X implement language Y and vice-versa?
- crote 3y agoSee, 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.
- klyrs 3y agoGiving 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.
- Joker_vD 3y agoSo 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.
- scj 3y agoThis 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).
- deleted 3y ago[deleted]
- tromp 3y agoA 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]. [1] https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html
- jwilk 3y agoHow do you implement sleep() in lambda calculus?
- zokier 3y agoOr `read` or `write` or invocation of any syscall. There is more to computer system than pure computation.
- bmacho 3y agoYou 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.
- bada-boom 3y ago[flagged]
- lukeasrodgers 3y agoStrongly recommend the talk on which this answer is based: https://www.youtube.com/watch?v=43XaZEn2aLc https://www.youtube.com/watch?v=43XaZEn2aLc
- tetromino_ 3y agoDavid Young's answer seems to give a precise mathematical criterion for deciding whether a language feature is mere syntactic sugar or more fundamental. Neat!
- ashton314 3y agoGlad 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. :)
- chongli 3y agoI 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. [1] https://htdp.org/ https://htdp.org/
- mrslave 3y agohttps://www.bootstrapworld.org/ https://www.bootstrapworld.org/ for the curious
- schemescape 3y agoWhat 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 :)
- jenadine 3y agoFunctions. Goto. Return. Destructors. Dynamic dispatch. Macros. Templates. System calls. Async. Generators.
- zogrodea 3y agoI 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.
- rcme 3y agoRegarding 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.
- ajuc 3y ago2 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.
- nitnelave 3y agoYou 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.
- Nevermark 3y agoI 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.
- ftxbro 3y agoI 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.
- deleted 3y ago[deleted]
- whateveracct 3y agoUnderstand 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
- deleted 3y ago[deleted]
- carlmr 3y ago>deficiency clown What is that?
- gcanyon 3y agoThe 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.
- soulbadguy 3y agoIMO, the line count is more a function of the "base/standard" libraries as opposed to expressiveness
- gcanyon 3y agoI 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.
- soulbadguy 3y ago> 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.
- Legend2440 3y agoI'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?
- pyrale 3y agoEven 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.
- passion__desire 3y agoCan you say more about the benefits?
- tsimionescu 3y agoIn 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.
- calf 3y agoIn 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.
- tsimionescu 3y agoI 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;}
- avgcorrection 3y agoThe 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.
- unwind 3y agoUh 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.
- quixoticaxolotl 3y agoI 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.
- noduerme 3y agoThe 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.
- tialaramex 3y ago> 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-rustc-bootstrap/src/lib.rs https://github.com/m-ou-se/nightly-crimes/blob/main/yolo-rus...
- noduerme 3y agouh, what? Random Rust code?
- tialaramex 3y ago
- paldepind2 3y agoIn 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.
- zokier 3y agoI 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.
- rowanG077 3y agoI 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".