Parallel Programming with List Homomorphisms

Research output: Contribution to journalArticlepeer-review


We review the use of the Bird-Meertens Formalism as a vehicle for the construction of programs with massive implicit parallelism. We show that a simple result from the theory, concerning the expression of list homomorphisms, can help us in our search for parallel algorithms by suggesting an informal methodology which is applicable when the original result is not, and demonstrate its application to a variety of problems. One of these, a language recognition algorithm, produces a program which exploits nested parallelism. Our main purpose is to show that an understanding of the homomorphism lemma can be helpful in producing parallel programs for problems which are "not quite" list homomorphisms themselves. A more general goal is to illustrate the benefits which can arise from taking a little theory with a pinch of pragmatic salt.
Original languageEnglish
Pages (from-to)191-203
Number of pages13
JournalParallel Processing Letters
Issue number02
Publication statusPublished - Jun 1995


Dive into the research topics of 'Parallel Programming with List Homomorphisms'. Together they form a unique fingerprint.

Cite this