busy and lazy fp with infinite objects
The paper introduces a variant of Backus' functional programming language FP that has non-strict basic operations as well as non-strict language constructs. The basic data structure of FP, finite nested sequences, is generalized to infinite trees by allowing a non-strict sequence constructor. Then infinite objects can be described as least solutions of recursion equations. For this language variant we give a structured mathematical and operational semantics which employs rewriting rules on finite terms. Infinite objects are evaluated by repeated unfolding of their recursive definitions and subsequent simplifications according to a confluent and Noetherian rewriting system on the level of objects. Two algorithms are given that formalize the ideas of busy (data-driven) and lazy (demand-driven) evaluation. Throughout the paper the semantic concepts of FP are explained; special emphasis is laid on the notion and the proper algebraic treatment of infinite objects.
object paper functional programming language operability data structures data structure sequence general trees recursion operational semantics semantic rewrite rules evaluation definition systems algorithm concept