Atom Feed SITE FEED   ADD TO GOOGLE READER

Language Expressiveness and Complexity

Recently I've seen comments about how language complexity is a Bad Thing that Must Be Avoided. I disagree. The expressiveness of a language influences what you can say with it. This applies to natural languages, programming languages, even programming APIs! When the language gets more complex (by adding new words or structures), the stuff you can say in that language becomes simpler.

Natural Languages
  • In German, the word schadenfreude means taking pleasure from other's pain. We need a word like this in English! When something terrible happens to Paris Hilton or Tom Cruise, we revel in it. But English speakers cannot concisely describe this satisfaction!
  • What's a website that gets updated regularly? With posts? It's a blog. It's a made-up word that neatly describes a concept. Attaching a name to the concept makes it more real. Adding a word to English makes English harder to learn, but more powerful to use.

    Programming Languages
  • Autoboxing and varargs in Java 5 makes it easier to express my intention without the mechanics. Compare this:
    List smallPrimes = Arrays.asList(new Integer[] { 
    new Integer(3), new Integer(5), new Integer(7), new Integer(11) });
    to this:
    List<Integer> smallPrimes = Arrays.asList(3, 5, 7, 11);

  • Language-integrated query (LINQ) in C# lets you manipulate collections declaratively rather than programatically. I describe what I want from the collection without the gory details on how to get it!

    APIs
  • The Future interface introduces a new concept: a return value that isn't available immediately. Using Futures allows client code to parallelize work without the clutter of managing threads.
  • Instead of manually managing the enabled state of the attached buttons and menus, the Action interface neatly encapsulates related behaviours. This makes the button API bigger and the client code smaller.

    We can certainly get around with simpler languages. But I don't think that language simplicity should be preferred over language expressiveness. Java Closures give us a huge amount of expressivity for a small amount of complexity.


    Footnote: C++
    When anyone makes a case against language complexity, C++ is their canonical example of what not to do. The fallacy of this argument is that much of the complexity in C++ is accidental complexity. If done carefully, adding new features to Java will not harm the language.
  • I completely agree. I'm currently working on a .NET/C# project and C# is a much larger, complex, and expressive language than Java. I'm anxious to play with C# 3.0 and Linq.
    Read The Design and Evolution of C++ and you will see that C++'s complexity is not accidental at all.
    C++ suffers from accidental complexity. This does not mean that the complexity was introduced inadvertently (ie. not by accident). Accidental Complexity is complexity that could have been avoided. In the case of C++, much complexity comes as a consequence of interoperability with C.
    No, it doesn't. The complexity introduced by C interop, for instance, is not accidental complexity. It could not have been avoided--C interop was a design and criteria-for-success requirement for C++.
    Yes, I also agree that C++ might not have had been successful without the migration path for C programmers and C code.

    But it makes the language more complex. Java has the same problem with primitives, for example.
    C++ is complex, absolutely, no disagreement there. I just took issue with the claim that it is accidental complexity--reading D&EoC++ reveals that it really isn't in almost all cases, and in fact C++ is a bit of a model for how even carefully planned language changes can start to go wrong.
    In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a generalization of L, the class for logspace problems on a deterministic Turing machine. Since any deterministic Turing machine is also a nondeterministic Turing machine, we have that L is contained in NL.

    NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE(log n).

    Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of algorithms, on the other hand, tell us which problems can be solved with this resource. Unfortunately, like much of complexity theory, many important questions about NL are still open.