Expressiveness

A language is said to be more expressive than another one if it can express more concepts than the other. If concepts are computable functions, then there is a maximally expressive class of languages, those that are equivalent to Turing machines.

Now, what are concepts? If admittedly any language can be expressed inside another one, all its sentences explainable in the other, this does not mean that you can find a faithful translation of a sentence of one into a sentence of the other. Poetry, ambiguity, puns, style, are difficult to translate. So there can be more to a sentence that the informational meaning usually expected from it. While you can consider computer programs as just representations of computable functions, you can also consider criteria like computational complexity, human readability (under various circumstances), ease to modify, length, ease of connections with other concepts in other contexts, etc. There are many divergent and sometimes opposite ways to refine the concept of expressiveness. See Abstraction Level.

Now, a whole class of such ways is easily achieved with some Formal Logic: We said that structure S1 was computably more expressive than structure S2, iff there was an "representation" morphism of S2 into S1, that preserved all verifiable existential statements, which precisely means that any computable object in S2 could be computed in S1. Now, while existential statements represent what can be computed with the system, they surely do not suffice to express what can be computed about the system, or even simpler with extensions or restrictions to the system. So not to neglect pertinence, we must consider expressiveness relations between structures relatively to any family formularum defined in arbitrarily combined terms of quantification complexity (e.g. Sigma-n, Pi-n, Delta-n formulae), positivity constraints on some atomic relations, fixed behavior on some subset of the language, "weight" of formulae, etc, on either side of the morphism. Among these expressiveness relations, those with homogeneous symmetric constraints on the morphism induce a partial order over considered structures.

As a conclusion, we have plenty of well-defined tools that allow to build expressiveness hierarchies among programming languages. These tools seem almost never used in common courses about computer languages, which is a shame, and leads to most available language been very poorly expressive. Unhappily, we quickly see how poorly expressive are available languages relatively to what can be done, and how even among these available languages some are miserably expressive as compared to others.

Surely at the early times when logicians where the ones who studied programming languages, before computers were widely available, these expressiveness criterion appeared to them as obvious, so they did not study it a lot; the (often justified) minimalist trend among mathematicians also made them try to express the most with little expressive languages. Then, the tiny computer resources of early computers made the study of programs easy, and very expressive languages superfluous, while poorly expressive languages were much easier to implement within the limited available resources. All those phenomena contribute to programming language expressiveness having been neglected for long times. But if computer science is to accumulate any kind of tradition in a reliable way that lasts across generations, it can only be through expressive languages, because only they allow people to understand what people long forgotten, using technology long replaced, may have meant.

See From our motivation article, the small chapter on OS Expressiveness. The article On the Expressive Power of Programming Languages (SCP 91) by Matthias Felleisen at Rice University.

This page is linked from: Abstraction Level   Language   Programming Language   Self-extensible