matthias@titan.rice.edu (Matthias Felleisen) (08/27/90)
On the Expressive Power of Programming Languages
Matthias Felleisen, Rice University
Abstract
The literature on programming languages contains an
abundance of informal claims on the relative expressive
power of programming languages, but there is no framework
for formalizing such statements nor for deriving
interesting consequences. As a first step in this
direction, we develop a formal notion of expressiveness and
investigate its properties. To validate the theory, we
analyze some widely held beliefs about the expressive power
of several imperative extensions of functional languages.
Based on these results, we believe that our system
correctly captures many of the informal ideas on
expressiveness, and that it constitutes a good basis for
further research in this direction.
The (revised version of the) full paper is available in dvi format
through anonymous ftp at TITAN.RICE.EDU as ~/public/expressiveness.dvi.
The original version appeared in the Proceedings of the European
Symposium on Programming 90, Springer LNCS Volume 432, pages 134--151.