18

I originally tried asking this on StackOverflow, but it was too subjective :-(. I am interested in methods of defining the power of programming languages. Turing completeness is one, but it is almost universally satisfied. What would be nice is to define a measure of power that discriminates among programming languages that are actually in used. For example, can anyone propose a non-subjective method that would discriminate between assembly and Java?

Turing completeness means that a language is maximally powerful in what it can output (which pretty much means it can do anything non-time based in the real world). So if we want to define a stronger measure of power, we need to take another approach. Shortness was suggested in the original question, but this is not easy to define at all. Does anyone have any other suggestions?

Casebash
  • 7,662
  • 5
  • 41
  • 62

4 Answers4

26

The notion you are looking for is called expressiveness and Matthias Felleisen has a mathematically rigorous definition:

"On the Expressive Power of Programming Languages"

www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz (Postscript version)

The intuition behind the idea is that if you have two equivalent programs in two different languages-- say, program A in language X and program B in language Y-- and if you make a local change to A that requires a global change to B, then X is more expressive than Y.

One example Felleisen provides is assignment: In the Scheme programming languages you can remove the assignment operator and still have a Turing complete language. However, in such a restricted language, adding in a feature that would be localized if assignment was allowed would require a global change to the program without assignment.

My discussion has simplified some details, and you should read the paper itself for the full account.

To answer your other question: You can say that Java is more expressive than assembly because you can add a new class to your Java program, and then gain the benefits of polymorphism by having other parts of your program call its methods without global modification. Exception handling is another example where Java is more expressive than assembly: You simply need to write a single throw statement to transfer control up the stack. On a more elementary level, you can also add a new case statement near the beginning of a switch and you won't have to worry about recalculating any jump offsets by hand.

Community
  • 1
Macneil
  • 8,223
  • 4
  • 34
  • 68
6

If I understand your question correctly, you are nonetheless looking for something that is relatively measurable and not just a subjective judgement call. If so, I would personally favour the amount of time taken to solve any particular problem (averaged over all problems and all programmers). In this measure, you might need to consider not just the language itself but also the framework/API used with it. Succinct syntax is a very small factor: a much more important one is that the most commonly required functionality is easily accessible.

If you are looking for something more subjective, I’d say how fun it is. Programmers tend to be people who want problems solved, so a programming language that is fun for programmers to use is inevitably going to be the one that will solve the most problems. This measure takes into account that different people have different preferences on how to use things, so the “best” programming language will be the one that is most appealing to the widest range of programmers. However, you might need to consider not just the programming language and API here, but also the environment (IDE), which is of course what the programmer actually interacts with.

Timwi
  • 4,411
  • 29
  • 37
  • I would say that measuring the time taken is subjective as well. Which programmer took the time? If you test both languages' times with the same programmer, then which language did he know better? There are statistical ways to deal with this, but a person couldn't do it alone. – John Fisher Oct 29 '10 at 01:25
  • 1
    @John: Just because something can only be analyzed statistically doesn't mean it's subjective. – David Thornley Oct 29 '10 at 20:05
  • @David: That wasn't really my point. The point was that without a preexisting study, the asker would be unable to compare the "power" of the languages he cared about -- leaving it subjective when not analyzed statistically over a large group. – John Fisher Oct 29 '10 at 21:34
1

I'd define how powerful a language is by how productive you can be with it. A lot of people tend to talk about productivity in terms of writing code quickly, but since the majority of a program's lifecycle is maintenance, not development, a better measure is how easily you can read and debug the code, especially when it's written by someone else. The most powerful languages are the ones that are easiest to read and maintain.

Mason Wheeler
  • 82,151
  • 24
  • 234
  • 309
  • 2
    The difficulty with this is that knowing a language makes it easier for the one who knows it. So, this measure becomes subjective. – John Fisher Oct 29 '10 at 01:29
1

You need to define your terminology better.

Turing completeness is not about "power" in the sense that you probably mean. Rather it is about computability; i.e. whether a given language can express any program that can be implemented using a Turing machine. It turns out that just about every programming language is Turing complete.

What you are probably after is a measure of what is referred to as programming language "expressiveness". I'm not sure if any such measure exists, or if it does, if it is useful. Fundamentally, different programming languages are better at expressing solutions to different types of problem.

EDIT

Just to spell it out, programming languages do not have a property know as "power". There is a concept commonly known as "expressiveness" or "expressive power" of a programming language. Expressiveness is partly about how easy it is to write succinct programs to address particular problems. But there is also a considerable measure of how easy it is to read and write the programs. It is sort of like "beauty". I'll know it when I see it, but don't ask me to define it.

Simply comparing character counts does not give you an adequate measure of expressiveness. Otherwise you could make a language more expressive by compressing the sourcecode ... and that's nonsense. In fact, I don't know of any objective measure of expressiveness, and I strongly suspect that none exists. Which effectively renders the characteristic useless, and pretty uninteresting.

Stephen C
  • 25,180
  • 6
  • 64
  • 87
  • 1
    I know that Turing completeness is about computability. We know that there exist lesser measures on the scale of computability, such as finite state machines. But we cannot use computability to define a level of power above this, as Turing completeness is maximally powerful in terms of computability – Casebash Sep 05 '10 at 12:17
  • @Casebash - you still haven't said what "power" is. – Stephen C Sep 05 '10 at 21:30
  • 2
    Thats because I don't know and that is the whole point of this question! – Casebash Sep 05 '10 at 22:46
  • Then what's the point of your answering? It should have been a comment. – reinierpost Jan 30 '12 at 17:53
  • @reinerpost - The point of **my** answer is to explain in detail that the Question is meaningless, and why. Basically the Question is asking *"There is something called 'expressive power' - I don't know what it is but could you tell me how to measure it."* And the nub of my answer is that 'expressive power' is ill-defined concept / property, and DEFINITELY not a measurable / quantifiable one. (And it is clearly an Answer and not a comment. Perhaps you simply didn't understand what I'm trying to say?) – Stephen C Feb 22 '12 at 01:16