Is there an objective measure of a programming language's complexity in terms of syntax and semantics, not how complex the language is to use ?
I've read many subjective comments but little rigorous analysis.
A:
How complex the language is to use is completely subjective.
On the other hand, questions about how complex the language semantics are, can be answered, but only when compared with other languages. These are not necessarily useful, however. For example, I would give Smalltalk a semantic complexity of 1 and C++ a complexity of 9. However, I will bet anything that the browser you are reading this in is written in C++, not Smalltalk.
anon
2009-07-22 21:24:33
A:
If there is such an objective measure, it is probably very nearly useless for evaluating the utility or cost of using a given language for a given purpose. It'd help you rule out whitespace or brainfuck, but that can be done just as easily without expending resources on such an objective measure—by subjectively observing source code and realizing you'd never want to do serious work with it.
Most languages are going to have a lot of positives and negatives that you'd need to weigh against the goal you're trying to achieve and the conditions that need to be met.
eyelidlessness
2009-07-22 21:25:09
Don't forget INTERCAL.
Martinho Fernandes
2009-07-22 21:35:05
I sure wish SO required a comment on downvote. People, if you don't like an answer, explain why.
eyelidlessness
2009-07-27 20:37:51
+2
A:
The best measure I've seen of a language is the probability that a random string will be a valid program. Perl is a language that ranks high on this scale, Ada ranks rather low.
What this metric means is another issue entirely.
caskey
2009-07-22 21:31:07
It means definitly not complexity, since languages like brainfuck with a very limited set of instructions would score very high.
THC4k
2009-07-22 21:38:55
THe proud boast of the TECO editor was that any string of characters when treated as a command would do something. This is one of many reasons you don't see many TECO users around these days.
anon
2009-07-22 21:45:24
The reason for this is if the first (or one of the first?) tokens is __END__ then ANYTHING produced after that is a valid Perl program. This alone has Perl in the lead for having a slice of infinite sequences that are valid programs.
Mark Canlas
2009-07-22 21:57:41
It is not complexity, it measures operator length. Java would also be low.
Alexandr Ciornii
2009-10-26 13:46:45
You could add number of AST traversals required and other translation metrics.
Aiden Bell
2009-07-22 21:48:46
+2
A:
As a general rule, the more dynamic and abstracted the syntax or semantics or implementation are, the more complex the language (not to use as you stated).
Hence, Java is a more complex language than C, because:
- C has simple scoping rules vs Java's relatively complex rules
- Types are more complex, method resolution and overloading
- Things like inheretance, argument enumeration and checking, method overloading make the compilation process much more complex.
I would argue Python simpler than Java on this basis, because it's object model, whilst complex, is simple in terms of reduction into a simpler form. The ease in which a given syntax can be translated into a simpler form from a time and calculation perspective might also be an angle.
A language such as lisp on the other hand, some would argue is complex to use but very simple. The same goes for things like Haskell.
You could measure complexity in one of the following ways, but non are complete:
- The number of keywords, lines of code and the complexity of semantics (like identifier resolution) for a simple problem. Fibonacci computation might be one. Comparing agreeably efficient implementation of common algorithms.
- What happens when? Are names bound late at runtime, or are they resolved at compile-time?
- Could a given snippet of code be understood in more than one way, when not given all the facts of the identifiers, types and external code?
There are tons of ways. You could measure computational complexity of the compilation process for a given syntax.
Not all of these examples are true. Some object models are very complex, but very fast because they use a fast foundation. Self might be an example.
Aiden Bell
2009-07-22 21:35:03
Added Ada's. Feel free to take it back out if you don't want your list to grow, Nick.
T.E.D.
2009-07-23 13:39:33
+1
A:
The easiest two entirely objective things to look at would be the amount of languaged defined symbols and keywords/reserved words, and the amount of productions in its BNF.
Another thing you could look at, for those languages that have them, is the relative sizes of their standards documents. Some would argue that not all standard documents are written at the same level, though.
T.E.D.
2009-07-22 22:04:44
+1
A:
I think if you look in the area of proof-of-correctness you'll find more detailed analysis of semantic complexity. Systems like CSP (and to a lesser extent, Lambda Calculus) are designed to be tractable via analysis. The closer a language is to being an expression of the underlying formal system, the simpler it is from a semantic standpoint.
The counter-example would be something like the C programming language. It's not possible to figure out what a C program actually does, without knowing what OS and hardware it'll be run on.
Mark Bessey
2009-07-22 22:09:34