Infinite structures in programming languages
Thomas J. Myers · 1980
Infinite structures (streams, infinite arrays, infinite trees) are used in the semantics of ordinary programming languages, and in mathematical descriptions of problems. Their use in problem description makes many problems easier to describe and to solve, from Euclid's algorithm through coroutine problems to tree searches, but they are not commonly available as programming language constructs. They are presented in a few sources (e.g., Burge) of advanced programming techniques, where they are described as recursive data types to be manipulated by recursive functions and operators (function-valued functions). This means that infinite data structures are 'explained' via recursion in the language, when recursion has been explained by infinite structures in the semantics. This thesis brings such objects down to earth by rephrasing standard semantic constructions so that they can be brought into a programming language with a standard set of operators for structure generation, transformation, and consumption. A programming language is then designed on this basis, and the use of standardized operators rather than recursion is shown to have benefits similar to those gained with 'structured' procedural programs rather than explicit branches. Finally, an implementation for a syntactic variant of the language is developed, and possible extensions are discussed.