Paper Description: GesGor97a

BibTeX entry:

author={A. Geser and S. Gorlatch},
title={Parallelizing Functional Programs by Generalization},
series = "Lecture Notes in Computer Science 1298",
booktitle = "Algebraic and Logic Programming (ALP'97)",
editor = "M.~Hanus and J.~Heering and K.~Meinke",
publisher = "Springer-Verlag",
abstract =
"List homomorphisms are functions that are parallelizable using the divide-and-conquer paradigm. We study the problem of finding a homomorphic representation of a given function, based on the Bird-Meertens theory of lists. A previous work proved that to each pair of leftward and rightward sequential representations of a function, based on cons- and snoc-lists, respectively, there is also a representation as a homomorphism. Our contribution is a mechanizable method to extract the homomorphism representation from a pair of sequential representations. The method is decomposed to a generalization problem and an inductive claim, both solvable by term rewriting techniques. To solve the former we present a sound generalization procedure which yields the required representation, and terminates under reasonable assumptions. We illustrate the method and the procedure by the parallelization of the scan function (parallel prefix). The inductive claim is provable automatically. "

Paper itself:

Cross links:

Sergei Gorlatch