The semantics of an fp language with infinite objects
Teresa A. Thomas, Donald F. Stanat · 1988
We describe an extension of Backus's FP (Functional Programming) languages to include infinite objects and discuss the semantic and mathematical issues surrounding the change. The extended languages, called SFP (Stream Functional Programming) languages, satisfy the following desiderata: (1) The domain for FP is embedded in the new domain. (2) The new domain contains infinite objects, both those infinite in length and those infinitely nested. (3) The new language is not substantially different in syntax from Backus's language. (4) The primitive functions of an FP language extend in an intuitively satisfying way to continuous functions on the new domain. (5) The functional style of FP programming is preserved. (6) The algebra of FP programs survives with few changes. SFP differs from FP in that the domain for SFP contains infinite objects, approximations to complete objects, and sk8 (top), used to denote an error. Approximations to complete objects include $\bot$ (bottom) and prefixes, where a prefix is a sequence that can be extended on the right. SFP uses a parallel outermost evaluation rule. Any monotonic function on the FP domain can be extended to a continuous function on the SFP domain. We describe a domain of objects, a collection of functions, and two semantics, one denotational and one operational, for SFP. We show that the two semantics define nearly the same language. The definitions of the primitive functions and functional forms, according to both the operational and denotational semantics, are given, as well as example programs.