Polyprograms as a representation of sets of functional programs, and their transformations
Abstract:
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.
Keywords:
polyprograms
program transformation
equality saturation
