Expressive power of typed and type-free programming languages (Q761790)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Expressive power of typed and type-free programming languages |
scientific article |
Statements
Expressive power of typed and type-free programming languages (English)
0 references
1984
0 references
The paper investigates the influence of type-free programming concepts on the definability of functions and objects in comparison with the exclusive use of typed concepts plus fixed-point operators. The underlying schemes are the classes of type-free and typed lambda-schemes respectively. The formal semantics of both classes are analyzed in the same semantical domains. In particular it is shown that typed lambda- schemes are translatable into equivalent type-free lambda-schemes but not vice verse. Furthermore, it is proved that the class of type-free lambda- schemes is universal in the sense that in the initial models all recursively enumerable \(\Sigma\)-trees (where \(\Sigma\) is the set of operation symbols) are definable.
0 references
type theory
0 references
lambda-calculus
0 references
type-free programming concepts
0 references
typed lambda-schemes
0 references
formal semantics
0 references