Deriving Data Parallel Implementations For List Predicates

摘要

We present three functional skeletons for data parallel programming that extend unary, binary resp. ternary predicates to nonempty lists such that all successive elements satisfy it. The high-level specification partitions the list into the collection of singletons, pairs resp. triples, evaluates each substructure and combines the subresults. From the specifications, we derive abstract implementations as list homomorphisms by a sequence of program transformations.