Expressivity of Programming Languages

The dictionary says that expressivity is

the quality of a mimical, oral, written, musical, or plastic manifestation that shows with full of feeling or meaning the ideas or emotions of the author or player.
Expressivity of a programming language:

Capability of a programming language to express the solution of a problem in:

The definition is clearly not formalized and, of course, it is not free from a lot of criticism. At least, it is useful to consider a language more expressive than other. Some considerations are the following:

From this point of view, it is clear that an imperative programming language with subroutines is more expressive than a language without them: Procedures allow to write pieces of programs in natural language - the name of the procedures - (what fulfil a)) and the programmer can reuse some procedures for other problems (following c)). The example also serves to notice that the definition is, sometimes, difficult to follow without contradiction: A program with a correct use of subroutines is usually less concise that the corresponding program without them.

The definition is specially appropriate for declarative languages. In fact, it reminds the notion of a declarative language, but it is meaningful, because declarative languages are widely accepted to be more expressive than imperative ones.

In general, the only way to increase the expressive power of a imperative language is to add more primitive constructions (the FOR instruction can be easily written in terms of a WHILE instruction, but some intuition is lost. However, this should decrease the simplicity of the language (as it happens with languages like PLM, COBOL, or Ada).

The same idea is true for a declarative language: the expressive power is increased by adding more features. One could argue that if the antecedent is the same, the consequent too: the resulting language is more complex. But it is not the case. The reason is that while imperative programming languages are based on a model provided by the computer architecture, declarative languages are based in a limited use of mathematics (functions, logic, equality theory, etc.). Any addition is easy to understand if it is done to overcome a limitation previously imposed. In other words, we understand mathematics and logic and declarative programming is only a subset of it. Any new feature of the language that is a feature of mathematics does not complicate the language. It is clear that we do not want to increase the expressive power of a language by adding new ``impure'' features (like cut in PROLOG). Instead, we want declarative constructions.

From the previous definition one can follow that neither functional programming is more expressive than logic programming nor logic programming is more expressive than functional programming. It is easily seen in the following examples:

Go to index