We all know that all programming languages in use today are Turing complete. But what this comes down to in reality is Greenspun’s Tenth Rule, which isn’t that useful for common discourse. So I will ignore Turing completeness in this post, and argue as if some languages are absolutely more powerful than others in terms of expressiveness. How to measure that power is a different discussion, and something Paul Graham and many others have written about. So I’ll make it really simple here – I’m going to use my own subjective view of the power of different programming languages, where succinctness (ability to compress without losing readability, a hard thing indeed), high classes of abstractions and support for different paradigms are supported. Not surprisingly, this put languages like Lisp, Smalltalk and Haskell in the absolute top, while languages like Java, C#, Basic and many other end up further down the scale to different degrees. Assembler is somewhere near the absolute bottom.
My contention is that expressive power is the absolutely most important property to focus on right now. We have progressively gotten better and better at this, but it still feels as if many decisions in programming languages are still based on whether they can be implemented efficiently or not. That is definitely important in some circumstances, but maybe not as often as we think. As we know, programmers are prone to premature optimization, and I think this is true for programming language design too.
One of the core guiding principles for Ioke is to forcefully remove all concerns about performance when thinking about new abstraction capabilities. I think there are new abstractions, new ways of programming – or even just incrementally better ways of doing things – that aren’t being explored enough. Take something like Ruby’s variables and instance variables, which spring into use the first time they are assigned to. This is highly useful, and lead to very neat code, but it’s hell to implement efficiently. And the situation can be even worse, like what I do in Ioke, where it’s not possible to statically/lexically see if a variable assignment is the first or not, and where it belongs. This means that there is no way to create efficient closure structures, no way to create efficient storage mechanisms for local scope, and so on. Some guesses can be made, but in the general cases it’s hard to make it perform well.
So why do it? Well, we’ve been pretty good at creating medium expressive languages that perform well, and we’re really good at designing languages that aren’t expressive at all while performing very well. But I’m lacking the other end of the scale. The most expressive languages I mentioned above still make concessions to performance in many places. Just take something like let-bindings in Lisp, which actually turns out to be really easy to compile well. Lexical closures is also not too bad from an efficiency stand point. Actually, lexical closures are way more efficient than the dynamic scope most Lisps used to have once upon a time. Was the decision to move away from dynamic scope driven by performance? No, not entirely. There were other good reasons to abandon it – but note that Common Lisp and Emacs Lisp still contain it.
So. I hope there are new things to be found in terms of expressiveness. I hope I can find some of them with Ioke. One simple thing is the control over scoping that I’ve mentioned before. Another is implementing local variables as cells on objects, just like all other properties in Ioke. A third is allowing both macros and syntax. Another is the ‘it’ variable in if statement. Another is removing any kind of immediate objects (so numbers and symbols are simple objects just like everything else in Ioke. You can override a method on one specific symbol instance of you want, which isn’t really possible in Ruby.) Another is removing all floats from the language. That data type just doesn’t have a good purpose in Ioke.
But this is just beginning. I hope to see new ways of doing stuff later on. But keep in mind, whenever I talk about some feature of Ioke, I will try to disregard the performance cost of it. Really.
9 Comments, Comment or Ping
to some degree, this increases the difficulty of selling your language to folks looking from the outside in. they’ll see complexity, where you see expressive power. scala’s lang designer is currently wrestling with whether criticism leveled at as valid or perceived, after GvR leafed through the ebook and blogged his opinion.
thus, i think the “accessibility of expressive power” is also very important. take for example how trivial ruby makes it to express “opening a class and extending it.” the concept is partly a physical act of opening the class, and requires little abstract thought, though the implications can be profound to the system.
November 26th, 2008
I think that it’s absolutely fantastic that you’re attempting to push the expressiveness potential of computing languages.
The argument over expressiveness vs performance is something I have a lot in my workplace. I’m of the opinion that a lot of the problems we’re trying to solve at my workplace (and I don’t think we’re alone in this situation) are about correctly modelling aspects of business domains and not implementing fast algorithms. For this we need a sufficiently expressive languages and not necessarily performant ones. (For performance in
Oversimplified, the more expressive the language, the more domains open themselves up to being more accurately modelled. Also, (and I believe that this is key) the more agile we can be in our programming as simple changes in the business will reflect into simple changes in an accurate model, whereas they would probably reflect much more substantial changes in a less accurate model.
One day our programs might be as expressive as poetry – but we still have an awfully long way to get there from here…
November 27th, 2008
Great idea about getting rid of Floats… They only create problems.
What do you think about implementing Rational, with it’s internal representation: n / m . (n,m being integers)
Probably it can be done in libraries of such a powerful language like IOKE…
Another idea ternary logic: True, False, Unknown… ;-)
I can’t wait until I’ll have a chance to implement that stuff in IOKE.
Sure it’s not going to perform well. Who cares?
November 27th, 2008
I think it’s important to have the right balance between expressiveness and performance. In retrospective it was probably a mistake that Java did not support closures in the first place, because at least now they can be supported by the JIT without much performance overhead.
Another example is Pythons mechanism for calling functions versus Smalltalks “messages”. IMHO Smalltalk messsages where “good enough”, where as Pythons mechanism is so much more complicated that compiling it into efficient code is very hard. And at the end the flexibility of Python’s approach IMHO doesn’t by you much.
And last but not least, you need to take care that you don’t introduce concepts that make it impossible to write algorithms with the best know
complexity( O notation).
For example it’s not clear to me whether languages such as Clojure, which treat everything as immutable can really in all cases support data structures that are as efficient as if the where implemented in pure Java.
For example as far as I know Clojure does not have a “persistent” (in the sense of immutable) HashMap implementation that is O(1).
The sweetspot might be language, where you always can escape into a “lower level” language as soon as you got into a performance problem.
One could argue that all JVM based languages have this property.
November 27th, 2008
Sam Aaron: IMHO, the usage of “fast algorithms” in your statement is a bit unfortunate.
Correct model frequently leads to a clever and fast algorithm. And that’s OK.
The real problem is when we focus on the programs constant multiplier in big O – unbeautifying the code…
November 27th, 2008
Szymon J
Sorry, just to clarify, when I said “fast algorithms” I was referring to building a fast indexing engine or performing some heavy number crunching, which in my context only constitutes a small part of the code I write. For the most part I’m modelling business processes and for that expressiveness and not performance is the key element for success.
For example, in my previous project we had to model a complex set of relationships between pharmaceutical products. Most of that model was in the clients head, and none was in mine, which meant none was in the code we had to write to do stuff with that model. Also, throw in the fact that the model in the client’s head kept changing too. To solve this issue, instead of spending eons exchanging specifications, I wrote a little DSLish piece of Ruby code that we used as the communication medium: the client could read it, correct it and offer suggestions, and I could then translate that to code that did something. I believe that using such an expressive piece of code massively speeded up the project and also increased our accuracy as less was having to be translated from client-speak to code-speak.
I currently see limitations to the expressive power of Ruby for doing something similar in different domains. However the prospect of Ioke is really, really tantalising and I’m eager to see what we might be able to do with it.
November 27th, 2008
I thought Haskell already established that expressive power and performance are not forces that work against each other.
November 28th, 2008
> For example as far as I know Clojure does not have a “persistent” (in the sense of immutable) HashMap implementation that is O(1).
No HashMap has truly O(1) lookup in the worst case as there allways can be collisions.
Clojures Hashmap technically is O(log N) but as it’s a base 32 logarithm you’d have to have a gigantic amount of elements to notice the difference and probably wouldn’t store that in a memory hashmap anyway. Sometimes constant factors matter in the real world.
“Persistent” means more than just “immutable”. There are immutable datastructures that change under the covers when you create new copys so lookup characteristics change on the previous versions. Persistent means that all copys stay the same complexity-wise as well.
November 28th, 2008
If you get the expressiveness right, but the performance is poor, it will give CS researchers an interesting new topic to investigate :)
December 22nd, 2008
Reply to “Expressive power vs performance”