On Abstraction and the Expressive Power of Programming Languages
Lists
Only you see this
Abstract
We present a tentative theory of programming language expressiveness based on reductions (language translations) that preserve observational equivalence. These are called “abstraction-preserving” because of a connection with a definition of “abstraction” or “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 “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.
BibTeX
@inproceedings{mitchell1991abstraction,
author = {John C. Mitchell},
title = {{On Abstraction and the Expressive Power of Programming Languages}},
booktitle = {TACS},
year = {1991},
doi = {10.1007/3-540-54415-1\_51},
}Loading related content...