On the expressive power of programming languages by Felleisen, M. (1991)

source
(Felleisen 1991)
tags
Programming languages
resources
PWL Conf talk

Summary

Programming languages have different levels of expressiveness. While can be used to create for loops, binary if statements can implement multi-if statements, etc.

Turing tarpit: once we get to programming languages that are universal, everything can be re-written into anything and the notion of “expressiveness” of programming languages doesn’t make much sense.

For a language \(L\) and \(F + L\) the addition of some features, can we say the second is more expressive than the first? Intuitively, this is related to some form of re-writing of programs into one another.

\(F + L\) isn’t more expressive than \(L\) when a macro for \(F\) to \(L\) exists. This means that for all programs \(P\) in \(L+F\), \(P_L\) its extension in \(L\), the two programs are equal.

When \(F\) is expressive relative to \(L\), you need to show that there cannot possibly exist such a macro.

A definition of equality

Equality is hard to define formally with programming languages. Is there a way in the language to tell them apart? If not, two things can be said to be equal within that language. But an even more general definition of equality: if for all contexts \(C\), \(C[e_1]\) halts iff \(C[e_2]\) halts (additional “trick”: programs with errors don’t terminate). The power of the definition comes from the fact that it has to hold for all contexts. This is called observational equivalence.

With this definition of equality, we can re-frame expressiveness. If we have of a language with more features, are all things previously considered equal still equal?

Key theorem

If we suppose \(F\) is written as a local macro, then for each terms that are equal under \(L\) they will be equal under \(F+L\). This means it hasn’t added power to \(L\).

With this, how do we show expressiveness? We show that we can find a context in \(L + F\) which makes two previously equal things distinguishable. \(F\) added power to the language \(L\).

Examples

With this one can show that a halts statement does add expressiveness to a language. Similarly, state gives the power to count compared to a pure functional language.

Conclusions

Local vs global transformations, in all of the above, transformations were local. But things like state can for example be implemented in functional programming through store-passing style.

When two languages are not as expressive, no local transformations can work.

This gives us two great definitions of equality and expressiveness.

Macros in language can add expressiveness, but expressiveness isn’t always suitable because they break existing equalities. However they can help avoid global transformations when a feature is needed.

Bibliography

Felleisen, Matthias. 1991. “On the Expressive Power of Programming Languages.” Science of Computer Programming 17 (1):35–75.


← Back to Notes