A study note based on the 1990 paper “On the Expressive Power of Programming Languages” by Matthias Felleisen and the video. The paper develops a formal notion of expressiveness of programming language (PL) and investigate its properties. The theory is validated by analyazing expressive power of several extensions of functional languages.

1 Introduction

By adapting the ideas about the relationship among formal systems to PL, we obtain a relation that determines whether a PL can express a programming construct.