[Prev][Next][Index][Thread]
Paper on Programming Language Expressivenes
On abstraction and the expressive power of programming languages
John C. Mitchell
Department of Computer Science
Stanford University
Stanford, CA \ 94305
jcm@cs.stanford.edu
This paper presents a tentative theory of
programming language expressiveness based on reductions
(language translations) that preserve observational equivalence.
These are called \q{abstraction-preserving}
because of a connection with a definition of
\q{abstraction} or \q{information-hiding} mechanism.
If there is an abstraction-preserving reduction
>from one language to another, then essentially
every function on natural numbers that is definable in the first
is also definable in the second.
Moreover, regardless of the set of first-order
functions definable in either language,
no programming language with an abstraction mechanism
can be reduced to a language without.
Since Lisp with user-defined special forms
does not have an abstraction mechanism, it is therefore
not \q{universal} in this theory, in spite of
the ability to define every partial recursive
function on the natural numbers.
Several examples and counter-examples to abstraction-preserving
reductions are given. We do not
know whether there is a natural universal language
with respect to abstraction-preserving reduction.
Paper to appear in Proc. Int'l Conf. on Theoretical Aspects
of Computer Software, Sendai, Japan, Sept. 1991; to be published
by Springer-Verlag, in LNCS series.
Currently available (.dvi format) by anonymous ftp from
theory.stanford.edu in file tacs.dvi, subdirectory pub/jcm.