Full Abstraction and Expressive Completeness for FP
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown 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.
Abstract
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.