Polyprograms as a representation of sets of functional programs, and their transformations

In different program transformation methods there arise objects similar to programs but capable of having multiple definitions of the same function. We will call such objects polyprograms. For example, in the Burstall-Darlington framework such objects are simply sets of recursion equations, and in equality saturation of Tate et al. the corresponding structure is called E-PEG. An important property of polyprograms, which is used in these transformations, is their ability to represent sets of ordinary programs. In this paper we introduce the notion of polyprogram in a non-strict first-order functional language. We define a denotational semantics for polyprograms and describe some possible transformations of polyprograms. We also touch on the subject of extracting ordinary programs from polyprograms.