What specifically does expressive power refer to?

Question

Expressive Power is defined by Wikipedia as:

.. the breadth of ideas that can be represented and communicated in that language.

Does "ideas" refer to the things (operations, structures, algorithms, etc.?) we can communicate to the machine? Or does it refer to the "human" concepts that can be captured and communicated with the language to other humans?

How is expressive power assessed and measured?

For instance, if we took a language like JavaScript and imposed a weird restriction on variable names, such as variable must be an 8-digit number preceded by an underscore, matching /^_[0-9]{8}$/, would we lose expressive power?

Or would that only be absurd and annoying?

---

To clarify:

Is expressive power measured by the general ideas inherent to the language:

• integers and strings
• loops
• conditionals

Or the number of specific, unique ideas that the language can represent:

• the integers 1, 2 ... 2^32
• strings containing "what does the fox say?" and "wha pah pah pah pah pah pow"
• for each frog in my collection of frogs
• if frog is green or something then do something

Answer 1

The landmark paper on expressiveness is On the Expressive Power of Programming Languages by Matthias Felleisen (1991). It contains a mathematically rigorous definition of language expressiveness.

Intuitively, if every program that can be written in language A can also be written in language B with only local transformations, but there are some programs written in language B which cannot be written in language A without changing their global structure (i.e. not with just purely local transformations), then language B is more expressive than language A.

One nice property of this definition is that it admits the possibility that there are pairs of languages where there are programs in X which cannot be expressed in Y and programs in Y which cannot be expressed in X, and thus the languages are distinct, but neither language is more expressive than the other. This meshes well with our real-world experience of there being some languages which are good at some things and some which are good at other things, and neither is generally "better" than the other.

Answer 2

Expressive Power is defined by Wikipedia as:

Let's give that page a re-read. One of the first things to note is that it says "language", not "programming language", and most of its examples are not programming languages, e.g. the first example given is a comparison of OWL2 EL and OWL2 RL, which are both ontology languages.

One can apply the concept to programming languages, but also pattern-matching langauges, markup languages, query languages, visual stylesheet langauges, regular expressions (and all the regular languages they refer to) and so on. One can even refer to the expressive power of natural languages like English, which is often done very informally, but with more seriousness when considering the problems related to natural language processing.

Does "ideas" refer to the things (operations, structures, algorithms, etc.?) we can communicate to the machine? Or does it refer to the "human" concepts that can be captured and communicated with the language to other humans?

It refers to what can be expressed in that language, considered purely as a thing in itself.

For example, (I'll use javascript throughout for my examples, because your question indicates that its one of the languages you know) consider the javascript statement:

var x = 3 + 4;

This represents that the value sum of 3 and 4 is computed and the value associated with a label x within a given namespace scope.

If we destroyed all the computers in the world and wrote that code on a piece of paper, it would remain that in javascript it still had that same meaning; we wouldn't be able to run such code on anything, but the abstract definition of the language is still something we could talk about.

This may seem pedantic, but it's actually quite important that languages are things that can be reasoned about in the abstract without consideration of real computers. For one thing, people reasoning about theoretical points of computer languages that were not yet feasible in practice is one of the things that has got us to where we are today; computers need computer science, but computer science does not need computers, just the idea of a computation.

Of course, we do use computers in the real world, and these days there are a lot of people using them in practice rather than a few specialists discussing them in theory. The page you linked to says:

The term expressive power may be used with a range of meaning. It may mean a measure of the ideas expressible in that language:

• regardless of ease (theoretical expressivity)

• concisely and readily (practical expressivity)

The first sense dominates in areas of mathematics and logic that deal with the formal description of languages and their meaning, such as formal language theory, mathematical logic and process algebra.

In informal discussions, the term often refers to the second sense, or to both. This is often the case when discussing programming languages. Efforts have been made to formalize these informal uses of the term

Of these two uses of the term, the first's practical impact relates solely to the what can be conveyed to the computer.

The second relates more to human understanding in both reading and writing, though the degree to which it does so, differs a lot between uses, since they are informal and as such are not rigourously defined.

For instance, if we took a language like JavaScript and imposed a weird restriction on variable names, such as variable must be an 8-digit number preceded by an underscore, matching /^_[0-9]{8}$/, would we lose expressive power?

By the formal definition, we've lost no expressive power: We're restricted to 100,000,000 variables, but if we really needed to we could get around this by creating objects to hold more variables within the newly-created namespace. As such any program written in javascript today could be rewritten in this new form, so they are equally expressive.

By the informal definition, we've lost some, but just how much depends on just how informal we're being, which will vary because again you can't say what is "the rule" about an informl use. We might say we've lost a tiny amount, because programs with more than 100,000,000 variables in the same namespace have to be rewritten beyond a simple substitution. An even more informal use again would refer to the mental impact of such ungainly variable names on human comprehensive.

Its also worth noting that people will informally consider things that are not strictly part of the language at all. Consider the changes in Javascript from its creation until today.

By the most formal definition, there has been pretty unchanged in expressiveness; it was Turing complete to start with, after all.

By a more informal definition, it has become considerably more expressive in certain things like array manipulation, exception handling and (perhaps most of all) in the inclusion of regular expressions. These don't do anything that couldn't be done in javascript before, though they can often do something in a few lines and a subsecond execution time that would take kilobytes of code to write in javascript1.0 and a long time to run.

By a much more informal definition again, the change from javascript's first use in browsers (able to change the values of form inputs, document.write while the page is first being parsed and move to a new location or go back or forward in the history, but pretty much nothing else) to that today (able to change just about anything on the page, including on the basis of data from server calls) is absolutely immense, though most of it doesn't relate to javascript but to the object models and APIs made available, rather than the language (e.g. vbscript in IE benefitted from those changes equally).

To my mind, that last use is so informal as to not really be correct, but that's the problem with informal definitions.

By the formal defintion, it really hasn't become more expressive at all.

Answer 3

I don't think that variable naming rules really capture what is meant by "expressiveness". I think that "expressiveness" refers to more fundamental things. Consider C# with Linq versus C# before Linq, for example. After the addition of Linq, it became possible to write SQL-like queries directly in the C#. This is a lot more elegant than the prior alternatives, e.g. putting SQL into string literals and then passing it to the server, or iterating over a collection using "for".

Another good example might be languages with prototype-based inheritance. In those languages, it's possible to simply add new methods to an instance or even a class (by whatever name a "class" may go in a given language...) at runtime. You can't really do that in C++ or C#. They lack this degree of expressiveness compared to prototype-based languages. (C# does have the concept of extension methods, and those could certainly be said to add expressiveness.)

Answer 4

As referenced by the Wikipedia article, expressive power refers to the set of programs that can be expressed in the language. Everything you think of as a "programming language" (JavaScript, LISP, C#, Perl, etc.) are essentially Turing complete, meaning that they can express anything said to be "computable".

However, it should be pretty clear that regular expressions are not as expressive as regular programming language. Furthermore, shell wildcards are somewhat less expressive than regular expressions.

A version of SQL with common table expressions is more expressive than a version without because CTEs allow you to represent recursive queries that would otherwise be impossible to express in SQL.

Answer 5

There is a simpler and more straight forward way to understand expressive power, but first we need to establish what we mean by languages. There are two disciplines which study languages: linguistics and automata. Both would agree on language being sets of words (finite sequences) constructed from some finite alphabet using concatenation. Typically, interesting languages (by interesting I mean such languages which we can interpret in a useful way) have also a set of rules which govern which words are in the language and which aren't. Note that expressiveness can only exist when there is interpretation.

By interpretation I mean existence of a function which given a word in a language selects an object from some set of objects (this is obviously debatable for natural languages).

Don't be mislead by the use of "word" though. A Java program is a word in the Java language (although it may span multiple files containing multiple strings of characters separated by spaces).

It would be counter-productive to use such complicated languages as modern programming languages to deal with this relatively simple concept, this is why I'd rather use mathematical formulas instead.

• Let's define language A to be all formulas involving integer addition.

• Let's define language B to be the language of all formulas involving integer multiplication.

In both cases we disallow the use of the identity element. Thus language A contains words "1+1", "1+2", "1+3", "2+3" and so on. The language B contains words "2*2", "2*3", "2*4", "3*4" and so on. We also assign usual interpretations to "*" and "+" (integer addition and integer multiplication) to the respective symbols. So, the interpretation of "1+1" is 2, and interpretation of "2*2" is 4.

Observe now that the language A is strictly more expressive than language B, since in integers it is true that multiplication may be cast as repeated addition, but there isn't a way to represent addition as multiplication in general.

---

To sum this up: language A can be said to be more expressive than language B when their interpretation functions share co-domain, but the image of the interpretation function of B is a proper subset of the image of the interpretation function of A.

Answer 6

TLDR: If a feature is missing but can be expressed in other ways it is not a lack of expressiveness. If you can envision an algorithm in your mind or even implement it in one language but another language is somehow structured in a way that makes it impossible to implement the algorithm it is an expressiveness problem*.

Variable naming restrictions do not reduce expressiveness (unless there are so few names that one cannot express all algorithms anymore and one cannot fake variables with something like arrays + indexes).

A simple example of a lack of expressive power is this: You have to do_homework and bring_down_trash. This is easily written in code:

do_homework();
bring_down_trash();

This solution looks pretty straightforward but actually do_homework and bring_down_trash are unordered, one could also write:

bring_down_trash();
do_homework();

Which is equally imprecise because it does not express that we did not intend to enforce an order. We also do not want to use threads. We want to say something like this:

compiler_or_interpreter_pick_one(
    {
        do_homework();
        bring_down_trash();
    },
    {
        bring_down_trash();
        do_homework();
    }
);

As far as I know this is very tricky to impossible to express in any programming language.

An example that bugs me to no end is that it is impossible in Java to have an array of objects. You can make an array of pointers to objects but that does not have the same memory layout (speak efficiency).

Taking an example from another answer: C++ does not support adding methods to a class or an instance. This is true, however, it does not limit the expressiveness of C++.

struct Extensible{
    std::vector<std::function<void(Extensible *)>> instanceExtensions;
    static std::vector<std::function<void(Extensible *)>> classExtensions;
};

This is a class to which you can add, remove and call an arbitrary number of member functions for instances and the class. Technically C++ is probably more expressive in this regard than programming languages that actually support this feature because in C++ you can choose how to store the functions (vector vs array vs forward_list).

*Some languages have a lack of expressiveness as a feature. Typically they make it impossible to write infinite loops. This can make the halting problem solvable and allow automatic proves for correctness.