Full Abstraction and Expressive Completeness for FP

We consider issues related to the expressive power of the programming language FP. In particular, we consider whether a number of variants of FP are fully abstract and expressively complete. For example, we show that a version of FP with only one-sided sequences behave similarly to PCF in that the a...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 1995-05, Vol.118 (2), p.246-271
Main Authors: Halpern, J.Y., Wimmers, E.L.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Programming theory
Theoretical computing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider issues related to the expressive power of the programming language FP. In particular, we consider whether a number of variants of FP are fully abstract and expressively complete. For example, we show that a version of FP with only one-sided sequences behave similarly to PCF in that the addition of parallel or is sufficient to make it fully abstract. However, the addition of parallel or to FP (with its two-sided infinite sequences) is not sufficient to achieve full abstraction. By considering these and other variants, we obtain a better understanding of what is required of a language and semantics in order to guarantee full abstraction and expressive completeness.
ISSN:0890-5401
1090-2651
DOI:10.1006/inco.1995.1065