- 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
- Matthias Felleisen. . "On the Expressive Power of Programming Languages". Science of Computer Programming 17 (1):35–75. DOI.