MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

Generate, Test, and Aggregate—A Calculation-based Framework for
Systematic Parallel Programming with
MapReduce—

Kento EMOTO, Sebastian FISCHER, and Zhenjiang HU

METR 2011–34

October 2011

DEPARTMENT OF MATHEMATICAL INFORMATICSGRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGYTHE UNIVERSITY OF TOKYOBUNKYO-KU, TOKYO 113-8656, JAPANWWW page: http://www.keisu.t.u-tokyo.ac.jp/research/techrep/index.html

The METR technical reports are published as a means to ensure timely dissemination ofscholarly and technical work on a non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright holders, notwithstanding that they
have offered their works here electronically. It is understood that all persons copying thisinformation will adhere to the terms and constraints invoked by each author’s copyright.
These works may not be reposted without the explicit permission of the copyright holder.

Generate, Test, and Aggregate
A Calculation-based Framework for Systematic Parallel Programming with MapReduce
Kento Emoto1 , Sebastian Fischer2 , and Zhenjiang Hu2
1

2

The University of Tokyo
National Institute of Informatics, Tokyo

Abstract
MapReduce, being inspired by the map and reduce primitives available in many functional languages, is the de facto standard for large scale data-intensive parallel programming.
Although it has succeeded in popularizing the use of the two primitives for hiding the details of parallel computation, little effort has been made to emphasize the programming
methodology behind, which has been intensively studied in the functional programming andprogram calculation fields.
We show that MapReduce can be equipped with a programming theory in calculational
form. By integrating the generate-and-test programing paradigm and semirings for aggregation of results, we propose a novel parallel programming framework for MapReduce. The
framework consists of two important calculation theorems: the shortcut fusion theorem of
semiring homomorphisms bridges the gap between specifications and efficient implementations, and the filter-embedding theorem helps to develop parallel programs in a systematicand incremental way.
We give nontrivial examples that demonstrate how to apply our framework.

1

Introduction

MapReduce [13], the de facto standard for large scale data-intensive applications, is a remarkableparallel programming model, allowing for easy parallelization of data intensive computations
over many machines in a cloud. It is used routinely at companies such as Yahoo!, Google,
Amazon, and Facebook. Despite its abstract interface that effectively hides the details of parallelization, data distribution, load balancing and fault tolerance, developing efficient MapReduceparallel programs remains as a challenge in practice.
As a concrete example, consider the known statistics problem of inferring a sequence ofhidden states of a probabilistic model that most likely causes a sequence of observations [22](see details in Section 6). This problem is important in natural language processing and error
code correction, but it is far from easy for one to come up with an efficient MapReduce program
to solve it. The problem becomes more difficult, if we would like to find the most likely sequencewith additional requirements such that the sequence should contain a specific state exactly fivetimes, or that the sequence should not contain a specific state anywhere after another. The
main difficulty in programming with MapReduce is that nontrivial problems are usually not ina simple divide-and-conquer form that can be easily mapped to MapReduce without producing
an exponential number of intermediate candidates. Moreover, the inputs may not just form asimple set of elements as in MapReduce; rather they are often structured as lists.
The MapReduce framework was inspired by the map and reduce (fold) primitives available
in many functional languages. Although it has successfully popularized the use of these two1primitives for hiding the details of parallel computation, little effort has been made to emphasize the programming methodology behind, which has been intensively studied in functional
programming and program calculation [3, 5, 35, 15, 23]. This lack of programming methodology for MapReduce has led to publication of too many papers about MapReduce applications[29], each addressing a solution to one specific problem, even if quite a lot of problems follow acommon pattern and can be solved generally.
To remedy this situation, we will show that MapReduce can be equipped with a programming
theory in calculational form [5, 24, 36], which can be applied to give efficient solutions to a wideclass of problems. For illustration, we consider a general class of problems which can be specified
in the following generate-test-and-aggregate (GTA for short) form:
aggregate ◦ test ◦ generate
Problems that match this specification can be solved by first generating possible solution candidates, then keeping those candidates that pass a test of a certain condition, and finally selecting
a valid solution or making a summary of valid solutions with an aggregating computation. For
example, the above statistics problem may be informally specified by generating all possible
sequences of state transitions, keeping those that satisfy a certain condition, and selecting one
that maximizes the products of probabilities (see Section 6).
Like other programming theories in calculational form [24, 36], the big challenges in thedevelopment of our calculation theory are to decide a structured form such that any programin this form is guaranteed to be efficiently parallelized, and to show how a specification canbe systematically mapped to the structured form. To this end, we refine the specification withconstraints on each of its components.
 The generator should be parallelizable in a divide-and-conquer manner and polymorphic
over semiring structures, guaranteeing that the final program can be coded with MapReduce efficiently.
 The condition for the test should be defined structurally in terms of a list homomorphism.
 The aggregator should be a semiring computation (semiring homomorphism), guaranteeing that the aggregating computation is structured in a way that matches with thegenerator.

These constraints, as will be seen later, can be satisfied for practical problems such as thestatistics problem mentioned above. An interesting result of this paper is that any specificationthat satisfies these constraints can be automatically mapped to an efficient parallel program in,but not limited to, MapReduce.
Notice that the key feature of our framework is the use of a semiring for gluing computations;the generator produces a result parametrized by semirings and this result is consumed laterby the aggregator. In fact, using semirings to structure computation is not new. Semirings
have been widely used for uniform formalization of a large number of problems in various
fields, such as shortest or most reliable paths problems, maximum network flow problem, cutset
enumeration, computing the transitive closure of binary relations, string parsing, solving systemsof linear equations, and relational algebras for incomplete or probabilistic databases in computerscience and operations research [20, 1, 17, 2, 38, 16, 12, 9]. However, the use of semirings forthe systematic development of reliable efficient parallel programs has not been studied well.
In this paper, by integrating the generate-and-test programing paradigm and semirings forresult aggregation, we propose a novel parallel programming framework that is centered on two
calculation theorems, the semiring fusion theorem and the filter embedding theorem. These two2

calculation theorems play an important role for the systematic development of efficient parallel
programs in MapReduce for a problem that is specified by a semiring-polymorphic generator,
a test with a homomorphic predicate, and a semiring homomorphism as aggregator. Our maintechnical contributions can be summarized as follows.
 We propose a new formalization of GTA problems in the context of parallel computation
based on the semiring fusion theorem. We show how a generator can be specified as a list
homomorphism polymorphic over semirings, an aggregator can be specified as a semiring
homomorphism, and fusion of their composition can be done for free and results in an
efficient homomorphism parallelizable by MapReduce.
 We propose a new systematic and incremental development of parallel programs for more
complicated GTA problems based on the filter embedding theorem. The filter-embedding
theorem allows a semiring homomorphism to absorb preceding tests yielding a new semiring homomorphism. We give nontrivial examples that demonstrate how to apply ourframework.

The rest of the paper is organized as follows. We start with background on lists, monoids,
homomorphisms, and MapReduce in Section 2. Then, after exemplifying our approach to specify
parallel programs by means of the knapsack problem in Section 3, we focus on two importantcalculation theorems, the shortcut fusion theorem for semiring homomorphisms in Section 4,
and the filter embedding theorem in Section 5. We discuss a more complex application in
Section 6 and show that our approach can be generalized from lists to other data types in
Section 7. Finally, we discuss related work in Section 8, and conclude in Section 9.

2

Background: Lists, Monoids and MapReduce

The notation in this paper is reminiscent of Haskell [4]. Function application is denoted by aspace and the argument may be written without brackets, so that (f a) means f (a) in ordinary
notation. Functions are curried: they always take one argument and return a function or avalue, and the function application associates to the left and binds more strongly than any
other operator, so that f a b means (f a) b and f a ⊗ b means (f a) ⊗ b. Function composition
is denoted by ◦, and (f ◦ g) x = f (g x ) according to its definition. Binary operators can beused as functions by sectioning as follows: a ⊕ b = (a⊕) b = (⊕b) a = (⊕) a b.

2.1

Lists, Monoids, and Homomorphisms

Lists are finite sequences of values of the same type. A list is either empty, a singleton, or the
concatenation of two other lists. We write [ ] for the empty list, [x ] for the singleton list withelement x , and xs ++ ys for the concatenation of two lists xs and ys. For example, the term
[1] ++ [2] ++ [3] denotes a list with three elements, often abbreviated as [1, 2, 3]. We write [A]for the type of lists with elements of type A.
Definition 1 (Monoid). Given a set M and a binary operator
called a monoid if is associative and has an identity ı ∈ M :(aıb) c = aa=a =a

(b
ı

c)

3

on M , the pair (M , ) isFor example, ([A], ++) is a monoid, because ++ is associative and [ ] is its identity.
Homomorphisms are structure preserving mappings. In the case of monoids they respect
the binary operation and its identity.
Definition 2 (Monoid Homomorphism). Given two monoids (M , ) and (M 0 ,0 ), a function

hom : M → M 0
is called monoid homomorphism from (M , ) to (M 0 ,hom ıhom (x=ı 0y) = hom x0 ) if and only if:

0 hom yFor example, the function sum for summing up all elements in a list is a monoid homomorphism from ([Z], ++) to (Z, +):sum [ ]
=0sum [x ]=xsum (xs ++ ys) = sum xs + sum ys
There is more than one monoid homomorphism from ([Z], ++) to (Z, +) but the property
sum [x ] = x characterizes sum uniquely, because [A] is the free monoid over A: for every resultmonoid, a list homomorphism (monoid homomorphism from lists) is characterized uniquely by
its result on singleton lists.
Lemma 3 (Free Monoid). Given a set A, a monoid (M , ), and a function f : A → M there isexactly one monoid homomorphism h : [A] → M from ([A], ++) to (M , ) with h [x ] = f x .
We can generalize the sum function by parameterizing it with a monoid operation (and its
identity). The function reduce : [M ] → M collapses a list into a single value by repeatedapplication of .
reducereducereduce

[]
=ı
[x ]
=x
(xs +
+ ys) = reduce

xs

reduceys

Informally, we have
reduce[x1 , x2 , ..., xn ] = x1

x2 ... xn

The function sum is a specialization of reduce , namely, sum = reduce + .
Another important monoid homomorphism on lists, or list homomorphism for short, is thefunction map that applies a given function to each element of a list. It is characterized by
map f [x ] = [f x ]Informally, we have
map f [x1 , x2 , ..., xn ] = [f x1 , f x2 , ..., f xn ]According to the homomorphism lemma [3], which follows from Lemma 3, every list homomorphism hom into a monoid (M , ) can be written as composition of a reduction and a map that
calls hom only on singleton lists:4hom = reduce ◦ map (λx → hom [x ])The lambda abstraction passed as argument to map is an anonymous function that takes a list
element x and yields the result of applying hom to a singleton list containing x .
List homomorphisms are relevant to parallel programming because associativity allows to
distribute the computation evenly among different processors or even machines by the wellknown devide-and-conquer parallel paradigm [35, 11].
For example, by providing a parallel implementation for the composition of a reduction anda map, every monoid homomorphism can be executed in parallel by implementing it according
to the homomorphism lemma. More detailed studies on showing that monoid homomorphisms
are a good characterization of parallel computational models can be found in [35, 11].

2.2

MapReduce

MapReduce [13] is a parallel programming technique, made popular by Google, used for processing large amounts of data. Such processing can be completed in a reasonable amount oftime only by distributing the work to multiple machines in parallel. Each machine processes asmall subset of the data.
We will not discuss the details of MapReduce in this paper. It is reminiscent of, though
not the same as, using the map and reduce functions defined above. Basically, a MapReduce
computation involves two operations: a map operation to each logical record in the input tocompute a set of intermediate key/value pairs, and a reduce operation to all the values thatshared the same key to get the appropriate derived data.
List homomorphisms fit well with MapReduce, because their input list can be freely divided
and distributed among machines. In fact, it has been shown recently that list homomorphisms
can be efficiently implemented using MapReduce [30]. Our approach builds on such an implementation which is orthogonal to our work. Therefore, if we can derive an efficient list
homomorphism to solve a problem, we can solve the problem efficiently with MapReduce.

3

Running Example: The Knapsack Problem

In this section we give a simple example of how to specify parallel algorithms in GTA form. We
give a clear but inefficient specification of the knapsack problem following this structure anduse it throughout Sections 4 and 5 to show how to transform such specifications into efficientparallel programs. 1
The knapsack problem is to fill a knapsack with items, each of certain value and weight,
such that the total value of packed items is maximal while adhering to a weight restriction of
the knapsack. For example, if the maximum total weight of our knapsack is 5kg and there
are three items (¥2000, 1kg), (¥3000, 3kg), and (¥4000, 3kg) then the best we can do is pickthe selection (¥2000, 1kg), (¥4000, 3kg) with total value ¥6000 and weight 4kg because all
selections with larger value exceed the weight restriction.
The function knapsack , which takes as input a list of value-weight pairs (both positive
integers) and computes the maximum total value of a selection of items not heavier than a total
weight w , can be written as a composition of three functions:knapsack = maxvalue ◦ filter ((6 w ) ◦ weight) ◦ sublists
1
The knapsack problem is NP-complete and the knapsack function calculated in Section 5 is pseudo-polynomial,i.e., polynomial in the maximum weight but not in the size of its binary encoding.

5 The function sublists is the generator. From the given list of pairs it computes all possible
selections of items, that is, all 2n sublists if the input list has length n.
 The function filter ((6 w ) ◦ weight) is the test. It discards all generated sublists whose
total weight exceeds w and keeps the rest.
 The function maxvalue is the aggregator. From the remaining sublists adhering to theweight restriction it computes the maximum of all total values.

The function sublists can be defined as follows:
sublists [ ]= *[ ]+
sublists [x ]= *[ ]+ ] *[x ]+sublists (xs ++ ys) = sublists xs ×++ sublists ys
The result of sublists is a bag of lists which we denote using * and +. The symbol ] denotes
bag union and ×++ the lifting of list concatenation to bags, concatenating every list in one bagwith every list in the other.
Here is an example application of sublists along with a derivation of its result.
sublists [1, 3, 3]= sublists ([1] ++ [3] +
+ [3])= sublists [1] ×++ sublists [3] ×++ sublists [3]= (*[ ]+ ] *[1]+) ×++ (*[ ]+ ] *[3]+) ×++ (*[ ]+ ] *[3]+)= *[ ], [1]+ ×++ *[ ], [3]+ ×++ *[ ], [3]+= *[ ] ++ [ ], [ ] ++ [3], [1] ++ [ ], [1] ++ [3]+ ×++ *[ ], [3]+= *[ ], [1], [1, 3], [3]+ ×++ *[ ], [3]+= *[ ], [1], [1, 3], [1, 3], [1, 3, 3], [3], [3], [3, 3]+
We took the liberty to reorder bag elements lexicographically because bags are unordered collections. Note, however, that elements may occur more than once as witnessed by [1, 3] and[3].
The function sublists is a monoid homomorphism: ×++ is associative and *[ ]+ is its identity.
The function filter filters a bag according to the given predicate. We pass as predicate thecomposition of the function weight that adds all weights in a list and the function (6 w ) thatchecks the weight restriction. Like sublists, weight is a monoid homomorphism:weight [ ]=0weight [(v , w )] = w
weight (xs ++ ys) = weight xs + weight ys
Finally, maxvalue computes the maximum of summing up the values of each list in a bag using
the maximum operator ↑.
maxvalue *+= −∞maxvalue *l += sum (map (λ(v , w ) → v ) l )maxvalue (b ] b 0 ) = maxvalue b ↑ maxvalue b 0
This specification is equivalent to the following equations.
maxvalue *+= −∞maxvalue *[ ]+=0maxvalue *[(v , w )]+ = v
6maxvalue (b ] b 0 ) = maxvalue b ↑ maxvalue b 0
maxvalue (b ×++ b 0 ) = maxvalue b + maxvalue b 0
The second and third equations follow directly from the specifications of sum and map. Regarding the last equation, remember that the lifted list concatenation ×++ appends each list in
one bag with each in the other, and, therefore, the maximum total value of the concatenatedlists is the sum of the maximum total values of the lists in each bag. This observation relies on
distributivity of + over ↑, a property that we will revisit in the next section.

4

Semiring Fusion

In this section we show how to derive efficient parallel programs from specifications in generateand-aggregate form:
aggregate ◦ generateThis form is a simplified version of GTA form, missing the test. We define specific kinds of generators and aggregators that allow such specifications to be implemented efficiently and provide
a theorem that shows how to calculate efficient parallel implementations. Such a calculation
can turn an exponential-time specification into a linear-time implementation.

4.1

Semirings and their Homomorphisms

The alternative specification for the function maxvalue in Section 3 shows that it is a monoid
homomorphism with respect to two different monoids over the same set (bags of lists). We now
consider an algebraic structure that relates two such monoids.
Definition 4 (Semiring). A triple (S , ⊕, ⊗) is called a semiring if and only if (S , ⊕) and (S , ⊗)are monoids, and additionally ⊕ is commutative, ⊗ distributes over ⊕, and ı⊕ is a zero of ⊗:a ⊕b =b⊕aa ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)(a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c)ı⊕ ⊗ a = ı⊕ = a ⊗ ı⊕
We have already seen two semirings in Section 3:
 (Z−∞ , ↑, +) is a semiring because both ↑ and + are associative, commutative and haveidentities −∞ and 0, respectively, where Z−∞ = Z∪{−∞}. Moreover, + distributes over
↑ and −∞ is a zero of +.
 (*[A]+, ], ×++ ) is a semiring for every set A because ] is associative and commutative and×++ is associative. Moreover, *+ and *[ ]+ are the identities of ] and ×++ , respectively.
Interestingly, ×++ distributes over ] and, clearly, *+ is a zero of ×++ . Readers who verify
distributivity of ×++ will make crucial use of the ability to reorder bag elements.

Definition 5 (Semiring Homomorphism). Given two semirings (S , ⊕, ⊗) and (S 0 , ⊕0 , ⊗0 ), afunction hom : S → S 0 is a semiring homomorphism from (S , ⊕, ⊗) to (S 0 , ⊕0 , ⊗0 ) if and only if
it is a monoid homomorphism from (S , ⊕) to (S 0 , ⊕0 ) and a monoid homomorphism from (S , ⊗)to (S 0 , ⊗0 ).

7

The maxvalue function presented in Section 3 is a semiring homomorphism from (*[Z−∞ ×
Z−∞ ]+, ], ×++ ) to (Z−∞ , ↑, +). It additionally satisfies the property
maxvalue *[(v , w )]+ = v
which characterizes it uniquely because bags of lists over a set A form the free semiring.
Lemma 6 (Free Semiring). Given a set A, a semiring (S , ⊕, ⊗), and a function f : A → S
there is exactly one semiring homomorphism h : *[A]+ → S from (*[A]+, ], ×++ ) to (S , ⊕, ⊗) thatsatisfies h *[x ]+ = f x .
The unique homomorphism can be thought of as applying f to each list element, thenaccumulating the results in each list using the operator ⊗, and finally accumulating thoseresults using the operator ⊕.

4.2

Polymorphic Generators

We now return to the generator sublists defined in Section 3. This function almost exclusively
uses the semiring operations of the semiring *[A]+ and their identities. The only exception isthe value *[x ]+ constructed from an element x ∈ A.
We can generalize sublists by parameterizing it with operations ⊕ and ⊗ of an arbitrary
semiring (and their identities) as well as an embedding function that constructs semiring elements from elements of a (potentially) different type:sublists ⊕,⊗ f [ ]= ı⊗sublists ⊕,⊗ f [x ]= ı⊗ ⊕ f x
sublists ⊕,⊗ f (xs ++ ys) = sublists ⊕,⊗ f xs ⊗ sublists ⊕,⊗ f ys
This function is called polymorphic over semirings because it can construct a result in anarbitrary semiring determined by the passed semiring operators and embedding function. It isa generalization of sublists because
sublists = sublists ],×++ (λx → *[x ]+)The anonymous function passed as argument constructs a singleton bag containing a singleton
list with the argument x .
Definition 7 (Polymorphic Semiring Generator). A function
generate ⊕,⊗ : (A → S ) → [A] → S
that is polymorphic over an arbitrary semiring (S , ⊕, ⊗) is called a polymorphic semiring generator.
The function sublists ⊕,⊗ is a polymorphic semiring generator, and being a monoid homomorphism for any semiring it can be executed in parallel. We could also pass the operations of
the semiring Z−∞ to compute a result in Z−∞ .
sublists ↑,+ (λ(v , w ) → v ) : *[Z−∞ × Z−∞ ]+ → Z−∞
What does this function compute? Theorem 8, which is a variant of short-cut fusion for semiring
homomorphisms, casts light on this question.

8

Theorem 8 (Semiring Fusion). Given a set A, a semiring (S , ⊕, ⊗), a semiring homomorphism
aggregate from (*[A]+, ], ×++ ) to (S , ⊕, ⊗), and a polymorphic semiring generator generate, thefollowing equation holds:
aggregate ◦ generate ],×++ (λx → *[x ]+) = generate ⊕,⊗ (λx → aggregate *[x ]+)Proof. Free Theorem [40].
Interestingly, in a polymorphically typed language like Haskell this theorem can be proved
solely based on type information, for example, using an automatic generator for free theorems.2
We can use Theorem 8 to answer the question what sublists ↑,+ (λ(v , w ) → v ) computes.
maxvalue ◦ sublists= maxvalue ◦ sublists ],×++ (λ(v , w ) → *[(v , w )]+)
= sublists ↑,+ (λ(v , w ) → maxvalue *[(v , w )]+)
= sublists ↑,+ (λ(v , w ) → v )This derivation shows that sublists ↑,+ (λ(v , w ) → v ) computes the maximum of all total valuesof sublists of the input list, but—unlike the intuitive formulation at the beginning of the equation
chain—efficiently. While the run time of maxvalue ◦ sublists is exponential in the length of the
input list (because the result of sublists has exponential size), the run time of the derived version
sublists ↑,+ (λ(v , w ) → v ) is linear in the length of the input list.
Here is an example derivation that shows how the efficient computation proceeds:
sublists ↑,+ (λ(v , w ) → v )[(2000, 1), (3000, 3), (4000, 3)]= sublists ↑,+ (λ(v , w ) → v )([(2000, 1)] ++ [(3000, 3)] ++ [(4000, 3)])= sublists ↑,+ (λ(v , w ) → v ) [(2000, 1)] +sublists ↑,+ (λ(v , w ) → v ) [(3000, 3)] +sublists ↑,+ (λ(v , w ) → v ) [(4000, 3)]= (0 ↑ 2000) + (0 ↑ 3000) + (0 ↑ 4000)= 2000 + 3000 + 4000
= 9000Apparently, to compute the maximum value over all sublists of a list of items, we can add up
all positive values of this list.
Of course, this is of little use for solving the knapsack problem posed in Section 3 because theinput list in this problem contains only positive values and maxvalue ◦ sublists, thus, computes
the total value of all available items.
For solving the knapsack problem, it is crucial to compute the maximum value only of thosesublists of the input list which adhere to the weight restriction. We need to account for the test
that implements this restriction which is the topic of the next section.

5Filter Embedding

We cannot apply Theorem 8 to transform specifications of the form
aggregate ◦ test ◦ generate2

http://www-ps.iai.uni-bonn.de/cgi-bin/free-theorems-webui.cg

9because the intermediate test goes in the way of fusing the aggregator with the generator. We
now show how specific instantiations of test allow to rewrite specifications like above into theform
postprocess ◦ aggregate 0 ◦ generate
where aggregate 0 is a semiring homomorphism derived from aggregate and postprocess maps theresult type of aggregate 0 to the result type of aggregate. This form then allows to fuse aggregate 0
with generate to derive an efficient implementation.
This transformation is possible if
test = filter (ok ◦ hom)
is a filter where the predicate is a composition of a monoid homomorphism hom : [A] → M intoa finite monoid M and a function ok : M → Bool that maps elements of M to Booleans.
Before we describe the general theorem in Section 5.2, we develop the underlying ideas byderiving an efficient implementation from the knapsack specification. This development may
seem to require some clever insights but users of our approach do not need to follow the same
path when transforming their own specifications. We chose to present the ideas using a concrete
example first, to make them seem less clever in the subsequent generalization. Others can simply
apply our general theorem to their specifications rather than repeating our development for eachspecification on their own. We can even provide an API that supports specifications in GTA
form and implements them as efficient parallel programs automatically.

5.1

Developing Intuitions by Example

In Section 3 we have specified the knapsack function as follows:
knapsack = maxvalue ◦ filter ((6 w ) ◦ weight) ◦ sublists
This specification is almost of the form we require: maxvalue, the aggregator, is a semiring homomorphism and the predicate used for filtering is a composition of the monoid homomorphism weight andthe function (6 w ) that maps the result of weight into the Booleans.

However, the result type of weight is N which is an infinite monoid, not a finite one. We canremedy the situation by defining Mw = {0, . . . , w + 1} andweight w [ ]=0weight w [n ]= (w + 1) ↓ nweight w (ms ++ ns) = weight w ms +w weight w ns
where m +w n = (w + 1) ↓ (m + n)
The operator +w implements addition but limits the result by computing the minimum withw + 1. For non-negative arguments it is associative and 0 is its identity. Consequently, weight w
is a monoid homomorphism into the finite monoid (Mw , +w ) for all weight restrictions w .
To transform the function maxvalue ◦ filter ((6 w ) ◦ weight w ) into the form postprocess w ◦maxvalue w we need to invent a semiring to use as result type of maxvalue w . The idea is tocompute simultaneously for all weights in Mw the maximum value of lists with exactly thatweight. The function postprocess w then computes the maximum over all values associated toweights 6 w .
10Like in Section 3, we use w = 5, so semiring elements can be represented as 7-tuples overZ−∞ . The function postprocess 5 is defined as follows:
postprocess 5 (v0 , v1 , v2 , v3 , v4 , v5 , v6 ) = v0 ↑ v1 ↑ v2 ↑ v3 ↑ v4 ↑ v5
It computes the maximum of all values associated with weights 6 5. The entry for the weight6 accumulates the maximum value corresponding to all weights > 6 because +w cuts off greatersums.
We now turn Z7−∞ into a semiring (Z7−∞ , ↑7 , +7 ). To compute the maximum value associatedto each weight of two 7-tuples, we use the underlying maximum operation on values.
(v0 , v1 , v2 , v3 , v4 , v5 , v6 ) ↑7 (v00 , v10 , v20 , v30 , v40 , v50 , v60 ) =(v0 ↑ v00 , v1 ↑ v10 , v2 ↑ v20 , v3 ↑ v30 , v4 ↑ v40 , v5 ↑ v50 , v6 ↑ v60 )This operator clearly inherits associativity and commutativity from the underlying maximum
operator and its identity is(−∞, −∞, −∞, −∞, −∞, −∞, −∞)The operator +7 is more interesting. From two 7-tuples that associate maximum values to eachweight in M5 it computes another 7-tuple that associates maximum values to the combined
weights. For example, to find the maximum value associated to the weight 3, it computes the
maximum of all sums of values associated to weights that sum up to 3 (we omit the part forlarger weights):(v0 , v1 , v2 , v3 , v4 , v5 , v6 ) +7 (v00 , v10 , v20 , v30 , v40 , v50 , v60 ) =(v0 + v00
, (v0 + v10 ) ↑ (v1 + v00 ), (v0 + v20 ) ↑ (v1 + v10 ) ↑ (v2 + v00 ), (v0 + v30 ) ↑ (v1 + v20 ) ↑ (v2 + v10 ) ↑ (v3 + v00 ), ...)
This operator is associative and its identity is(0, −∞, −∞, −∞, −∞, −∞, −∞)We now define maxvalue 5 as the (cf. Lemma 6) semiring homomorphism that satisfies thefollowing equation:
maxvalue 5 *[(v , w )]+ = (val 0, val 1, val 2, val 3, val 4, val 5, val 6)
where val i = if i ≡ w ↓ 6 then v else − ∞When applied to a singleton bag that contains a list with exactly one item, maxvalue 5 associates
to almost all weights the value −∞ with one exception: the value of the given item is associatedto its weight (or to the weight 6 if it is heavier).
Our Main Theorem 13 below, now implies that for w = 5
knapsack = postprocess 5 ◦ sublists ↑7 ,+7 (λ(v , w ) → maxvalue 5 *[(v , w )]+)
We can test this result with the example from Section 3:
knapsack [(2000, 1), (3000, 3), (4000, 3)]= knapsack ([(2000, 1)] ++ [(3000, 3)] ++ [(4000, 3)])11

= postprocess 5( ( (0, −∞, −∞, −∞, −∞, −∞, −∞)↑7 (−∞, 2000, −∞, −∞, −∞, −∞, −∞))
+7 ( (0, −∞, −∞, −∞, −∞, −∞, −∞)↑7 (−∞, −∞, −∞, 3000, −∞, −∞, −∞))
+7 ( (0, −∞, −∞, −∞, −∞, −∞, −∞)↑7 (−∞, −∞, −∞, 4000, −∞, −∞, −∞)))= postprocess 5( (0, 2000, −∞, −∞, −∞, −∞, −∞)+7 (0, −∞, −∞, 3000, −∞, −∞, −∞)+7 (0, −∞, −∞, 4000, −∞, −∞, −∞))= postprocess 5( (0, 2000, −∞, 3000, 5000, −∞, −∞)+7 (0, −∞, −∞, 4000, −∞, −∞, −∞))= postprocess 5 (0, 2000, −∞, 4000, 6000, −∞, 9000)= 6000So, indeed, we get the maximum value of ¥6000 predicted earlier. ¥2000 is the maximum valuethat can be achieved with a weight restriction of 1kg. If only 3kg were allowed, the maximum
value would be ¥4000, and the total value of all items is ¥9000.
The run time of the transformed version of knapsack is O(nw2 ) if there are n items andthe weight restriction is w. As sublists ↑7 ,+7 is a monoid homomorphism we can execute it inparallel, say using p processors, which leads to the run time O((log p + np )w2 ). This complexity
resembles the run time of other parallel algorithms to solve the knapsack problem. The standard
sequential algorithm has run time O(nw).
Unlike existing algorithms to solve the knapsack problem, our approach can be generalized
to other specifications in GTA form. The knapsack function is a special case well suited tohighlight the ideas behind our approach, which we now generalize.

5.2

The Generalized Theorem

We now generalize the ideas of Section 5.1 to support
 arbitrary polymorphic semiring generators,
 arbitrary filters with homomorphic predicates, and arbitrary semiring homomorphisms as aggregators.

In Section 5.1 we have used a semiring of 7-tuples storing maximum values corresponding toeach weight in M5 . In general, if we have a finite monoid M and a semiring S , then the set
S M = {{fm }m∈M |fm ∈ S}
of families of elements in S indexed by M is a semiring too. Indexed families are a generalizationof tuples and we write fm for the element in S indexed by the value m ∈ M if f ∈ S M is anindexed family. We give definitions of indexed families by defining their value in S for eachm ∈ M.
Lemma 9 (Lifted Semiring). Given a finite monoid (M , ) and a semiring (S , ⊕, ⊗) the triple(S M , ⊕M , ⊗M ) where12(f ⊕M f 0 )m = fmL⊕ fm0(f ⊗M f 0 )m =(fk ⊗ fl0 )
k,l∈M
k l=m

is a semiring and(ı⊕M )m = ı⊕(ı⊗M )m = if m ≡ ı then ı⊗ else ı⊕
Proof. The monoid laws for ⊕M follow directly from those of ⊕. We leave the proof of the lawsfor ⊗M to interested readers.
The definition of ⊕M uses the underlying ⊕ operator just like the definition of ↑7 in Section 5.1 uses ↑. The operator ⊗M , like +7 , computes for each m the maximum of all sums ofvalues associated to weights that add up to m if we instantiate and ⊗ with + and ⊕ with ↑.
The identities also reflect their specific counterparts from Section 5.1.
Intuitively, given a monoid homomorphism hom : [A] → M , a semiring homomorphism
aggregate : *[A]+ → S , and a bag of lists ls, we can associate to ls an indexed family f ls ∈ S M
that describes for each m ∈ M the result of applying aggregate to a bag of exactly those listsl ∈ ls that satisfy hom l = m:ls = aggregate (filter ((m ≡) ◦ hom) ls)
fm

Considering different instantiations for ls, we can observe the following identities:
fm

= ı⊕
*[ ]+
fm
= if m ≡ ı then ı⊗ else ı⊕0ls ⊕ f ls0
fmls]ls = fmm0L0ls×++ ls
fm=
(fkls ⊗ flls )
k,l∈M
k l=m
*+

They reflect the definitions of the semiring operations for S M and their identities. Becauseof these homomorphic equations for f ls , we can compute f ls using a semiring homomorphism
aggregate M that satisfies(aggregate M *[x ]+)m*[x ]+= fm= aggregate (filter ((m ≡) ◦ hom) *[x ]+)= if hom [x ] ≡ m then aggregate *[x ]+ else ı⊕
According to Lemma 6 this semiring homomorphism is unique.
Definition 10 (Lifted Homomorphism). Given a set A, a finite monoid (M , ), a monoid homomorphism hom from ([A], ++) to (M , ), a semiring (S , ⊕, ⊗), and a semiring homomorphism
aggregate from (*[A]+, ], ×++ ) to (S , ⊕, ⊗), the function
aggregate M : *[A]+ → S M
is the unique semiring homomorphism from (*[A]+, ], ×++ ) to (S M , ⊕M , ⊗M ) that satisfies(aggregate M *[x ]+)m = if hom [x ] ≡ m then aggregate *[x ]+ else ı⊕
13

The function aggregate M generalizes the function maxvalue 5 by using aggregate and ı⊕
instead of maxvalue and −∞.
ls
Once we have computed f ls , we can use a function ok : M → Bool to combine all results fm
for m ∈ M with ok m = True to get the result of
aggregate
L (filter (ok ◦ hom) ls) =(aggregate (filter ((m ≡) ◦ hom) ls))m∈M
ok m=T rue

According to this equation, we can partition the bag of accepted lists according to elementsof M and aggregate them individually because aggregate is a semiring homomorphism. The
postprocessor defined next combines such individual aggregations.
Definition 11 (Postprocessor). Given sets M (finite) and S and a function ok : M → Bool thefunction postprocess M ok : S M → S is defined as follows:L
postprocess M ok f =fmm∈M
ok m=T rue

It is clearly a generalization of postprocess 5 which computes the maximum of all values
associated to weights 6 5.
We can now prove the theorem which constitutes the second half of our approach. It clarifies
how to embed an arbitrary filter with a homomorphic predicate into an arbitrary semiring
homomorphism.
Theorem 12 (Filter Embedding). Given a set A, a finite monoid (M , ), a monoid homomorphism hom from ([A], ++) to (M , ), a semiring (S , ⊕, ⊗), a semiring homomorphism aggregate
from (*[A]+, ], ×++ ) to (S , ⊕, ⊗), and a function ok : M → Bool the following equation holds:
aggregate ◦ filter (ok ◦ hom) = postprocess M ok ◦ aggregate M
Proof. The following calculation combines previous observations and definitions to show theclaimed identity.
=

aggregate (filter (ok ◦ hom) ls){L
Partition, individual aggregation }(aggregate (filter ((m ≡) ◦ hom) ls))m∈M
ok m=T rue{ Definition of f ls , and Definition 11 }postprocess M ok f ls
= { Definition 10, homomorphic equations for f ls }postprocess M ok (aggregate M ls)=

Our main result combines the theorems from Sections 4 and 5. It allows, under certain
conditions, to transform specifications in GTA form into efficient parallel algorithms.
Main Theorem 13 (Filter-embedding Semiring Fusion). Given a set A, a finite monoid(M , ), a monoid homomorphism hom from ([A], ++) to (M , ), a semiring (S , ⊕, ⊗), a semiring homomorphism aggregate from (*[A]+, ], ×++ ) to (S , ⊕, ⊗), a function ok : M → Bool , anda polymorphic semiring generator generate, the following equation holds:
14

aggregate ◦ filter (ok ◦ hom) ◦ generate ],×++ (λx → *[x ]+)= postprocess M ok ◦ generate ⊕M ,⊗M (λx → aggregate M *[x ]+)Proof. Combining previous Theorems.
aggregate ◦ filter (ok ◦ hom) ◦ generate ],×++ (λx → *[x ]+)= { Theorem 12 }postprocess M ◦ aggregate M ◦ generate ],×++ (λx → *[x ]+)= { Theorem 8 }postprocess M ◦ generate ⊕M ,⊗M (λx → aggregate M *[x ]+)Filter-embedding Semiring Fusion is not restricted to parallel algorithms. It can be used to
calculate efficient programs from specifications that use arbitrary polymorphic semiring generators.
It is worth noting that it is possible to derive finite monoidal filters from predicates expressedusing regular expressions or monadic second order logic [39]. This fact may help readers toassess what kinds of problems fit into our setting. It is also possible to remove the finitenessrequirement for monoids and define a lifted semiring of finite mappings of unbounded andunknown size. We require the finiteness only in order to be able to describe the complexity of
the resulting parallel algorithms more accurately.
If the generator happens to be a list homomorphism, like sublists, then associativity of list
concatenation allows the resulting program to be executed in parallel by distributing the input
list evenly among available processors. The complexity of a derived program using sublists as
generator is linear in the size of the input list and quadratic in the size of the range M of thehomomorphic predicate because the semiring multiplication of the lifted semiring S M , which isused to combine all list elements, can be implemented by ranging over M × M .

6

A More Complex Application

In this section we describe how to use our framework to derive an efficient parallel implementation for a practical problem in statistics. We further demonstrate how to extend the derived
basic program incrementally.

6.1

Finding a Most Likely Sequence of Hidden States

We now revisit the statistics problem mentioned in Section 1 which is to find a sequence ofhidden states of a probabilistic model that most likely causes a sequence of observed events.
For example, for speech recognition, the acoustic signal could be the sequence of observed events,
and a string of text the sequence of hidden states.
Given a sequence x = (x1 , . . . , xn ) of observed events, a set S of states in a hidden Markov
model, probabilities Pyield (xi | zj ) of events xi being caused by states zj ∈ S, and probabilities
Ptrans (zi | zj ) of states zi appearing immediately after states zj , the objective is to find asequence z = (z0 , . . . , zn ) of hidden states that is most likely to cause the sequence x of events
such that every zi causes xi for i > 0 and z0 is an initial state. This problem can be formalized
by the following expression.
arg maxn
Qz∈S n+1i=1

Pyield (xi | zi )Ptrans (zi | zi−1 )15

To derive an efficient parallel algorithm to solve this problem, we transform this expression to
fit in our framework.
To eliminate the index i − 1, we let the expression range over pairs of hidden states in S × S
and introduce a predicate trans to restrict the considered lists of state pairs. Intuitively, trans yis True if and only if the given sequence y of state pairs describes consecutive transitions((z0 , z1 ), (z1 , z2 ), . . . , (zn−2 , zn−1 ), (zn−1 , zn ))and False otherwise. Introducing the function
prob (x, (s, t)) = Pyield (x | t)Ptrans (t | s)the expression above can be transformed into the following equivalent expression.
arg maxy∈(S×S)ntrans y=TruenQprob (xi , yi )



i=1

In a first step, we specify only the maximum probability in GTA form. We show how to computea state sequence corresponding to this probability by using a different aggregator later.
Representing sequences of states and events as lists, we can write the transformed specification as follows.
maxLikeliness =maxprob ◦filter (trans ◦ map (λ(x , (s, t)) → (s, t))) ◦assignTrans ],×++ (λx → *[x ]+)The polymorphic semiring generator assignTrans ⊕,⊗ is defined as the unique monoid homomorphism from ([X ], ++) to the multiplicative monoid (T , ⊗) of an arbitrary semiring (T , ⊕, ⊗)that satisfies
assignTrans ⊕,⊗ f [x ] = reduce ⊕ [f (x , (s, t)) | s ← S , t ← S ]Here, reduce ⊕ is a monoid homomorphism from ([T ], ++) to (T , ⊕) that satisfies reduce ⊕ [x ] =x . Intuitively, assignTrans ],×++ (λx → *[x ]+) produces a bag of event sequences with associatedstate transitions where the events are in the same order as in the input list and all possiblecombinations of state transitions are attached.
The predicate trans is defined as not ◦ ( ≡) ◦ reduce  where reduce  is a monoid homomorphism from ([S × S ], ++) to the finite monoid ((S × S ) , ) and (S × S ) is (S × S )∪{ı , }.
Here,  is a zero of  and(s, t)  (u, v ) = if t ≡ u then (s, v ) else Intuitively, reduce  returns the boundaries of a given sequence of state transitions if they areconsecutive (ı if the sequence is empty) and  otherwise.
The aggregator maxprob is the unique semiring homomorphism from (*[X ×(S ×S )]+, ], ×++ )to ([0, 1], ↑, ∗)3 that satisfies
maxprob *[(x , (s, t))]+ = prob (x , (s, t))
3
To avoid confusion, note that [0, 1] is the unit interval, that is, the set of all real numbers x such that0 ≤ x ≤ 1, not the list of the two elements. Multiplication distributes over ↑ on the unit interval.

16

Intuitively, it computes all total probabilities of state sequences causing the observed event
sequence by multiplying the individual probabilities given by prob and then computes the maximum of all total probabilities.
The range of reduce  has size |S|2 + 2, thus, applying Theorem 13 to the specification of
maxLikeliness yields an implementation with the total cost O(n|S|4 ) if n denotes the length ofan event sequence given as input. As assignTrans is a monoid homomorphism we can execute
it in parallel, say using p processors, which leads to the run time O((log p + np )|S|4 ). For a given
probabilistic model, where S is fixed, the result is a linear-time parallel algorithm. This is incontrast to the specification which, when executed, would generate an intermediate result of size
|S|2n . Interestingly, the derived program is equivalent to a program obtained by parallelizing
the Viterbi algorithm [21, 22] using matrix multiplication over a semiring [34].

6.2

Computing Sequences of States

We can compute both the maximum probability and the corresponding state sequences using
an alternative aggregator maxprobSeq which can replace maxprob above and is characterized by
maxprobSeq *[(x , (s, t))]+ = (prob (x , (s, t)), *[t ]+)The result is an element in the semiring ([0, 1] × *[S ]+, ↑0 , ∗0 ) where the identities of ↑0 and ∗0
are (0, *+) and (1, *[ ]+), respectively, and the semiring operations are defined as follows:(a, x ) ↑0 (b, y) = if a > b then (a, x ) else if a < b then (b, y) else (a, x ] y)(a, x ) ∗0 (b, y) = (a ∗ b, x ×++ y)

The bag in the second component of the result contains all most likely sequences. In practice,
we may use non-deterministic choice to compute one of them, though operators with nondeterministic choice do not satisfy the semiring laws.

6.3

Variations of the Problem

An interesting feature of our framework is that we can extend a basic algorithm by modifying
the specification which is easier than modifying the efficient algorithm directly.
Second-order Hidden Markov Model For example, we can extend maxLikeliness to deal
with a second-order hidden Markov model [21] where the transition probabilities are based on
the past two hidden states, not only the previous state. If the probability of transitioning tou after the past transition s → t is given as Ptrans (u | s, t) we can modify the function prob asfollows:
prob2 (x, (s, t, u)) = Pyield (x | u)Ptrans (u | s, t)
Similarly, we modify the specification of maxLikeliness:
maxLikeliness2 =maxprob2 ◦filter (trans ◦ map (λ(x , (s, t, u)) → ((s, t), (t, u)))) ◦assignTrans2 ],×++ (λx → *[x ]+)The function maxprob2 is defined similarly as maxprob and uses prob2 instead of prob. The
polymorphic semiring generator assignTrans2 ⊕,⊗ is characterized by the following equation:
assignTrans2 ⊕,⊗ f [x ] =reduce ⊕ [f (x , (s, t, u)) | s ← S , t ← S , u ← S ]17

It associates each observed event with a triple of states, not a pair.
The monoid homomorphism reduce  used in the definition of trans is now used as monoid
homomorphism from ([(S × S ) × (S × S )], ++) to the finite monoid (((S × S ) × (S × S )) , ).
The specification of  is the same as before but it now compares pairs of states for equality, notstates.
By applying Theorem 13, we get a linear-time parallel implementation for maxLikeliness2
and a given second-order hidden Markov model. The algorithm can be extended to even higher
orders similarly.
Maximum Sum of k Distinct Paths Another extension is to maximize the sum of k
distinct state sequences that lead to the observed events [22]. The specification is the same as
the specification of maxLikeliness apart from the aggregator maxprob k which computes the listof k largest probabilities of distinct state sequences and is composed with the sum function to
add up the probabilities.
maxLikeliness k =sum ◦ maxprob k ◦filter (trans ◦ map (λ(x , (s, t)) → (s, t))) ◦assignTrans ],×++ (λx → *[x ]+)The aggregator maxprob k is characterized by the equation
maxprob k *[(x , (s, t))]+ = [prob (x , (s, t))]
It computes a result in the semiring ([[0, 1]], ↑k , ∗k ) where [ ] and [1] are the identities of ↑k and∗k , respectively, and the semiring operations are defined as follows:+ y))x ↑k y = take k (sort (x +x ∗k y = take k (sort [a ∗ b | a ← x , b ← y ])The function take k computes the longest prefix with at most k elements of a given list, sortsorts descendingly.

6.4

Incremental Refinement

In the previous subsection we have modified some parts of a specification to obtain variationsof a basic algorithm. In our approach it is also possible to extend a specification incrementally,
by adding additional tests. By using Theorem 12 multiple times, it is possible to implement
specifications with multiple filters, not only one.
For example, we can compute the most likely sequence of hidden states satisfying certain
conditions, such as “state s is used exactly five times,” or “state t does not appear anywhere
after state s.” Our framework guarantees an efficient implementation also for these restricted
problems if the conditions can be defined by a homomorphic predicate.
For the first condition we use the monoid homomorphism count w p into (Z, +w ) characterizedbycount w p [x ] = if p x then 1 else 0
It computes the number of list elements that satisfy the given predicate p. Based on count w wecan define the predicate fixedTimes which only allows sequences of states that contain a given
state s exactly w times:18fixedTimes s w = (w ≡) ◦ count w (λ(x , (t, u)) → s ≡ u)
To check the second condition whether a state t occurs anywhere after a state s we can definea monoid homomorphism after s t into ((Bool × Bool ) , ?) that returns a pair of Booleans thatindicate whether the argument list contains the states s and t, or  if t occurs anywhere afters.4 Here, after is characterized byafter s t [(x , (u, v ))] = (s ≡ v , t ≡ v ),
 is a zero of ? and (s1 , t1 ) ? (s2 , t2 ) = if s1 ∧ t2 then  else (s1 | s2 , t1 | t2 ). Based on after
we can express a test which only allows sequences of states that do not contain a given state t
after s as not ◦ ( ≡) ◦ after s t.
Since both homomorphisms have finite ranges, we can get linear-time parallel algorithms forthe restricted problems. We can even combine both predicates or add similar conditions suchas “state s is used more than k times,” or “state s is used at most k times” and still get an
efficient parallel implementation.

7

Generalization to Algebraic Data Types

In this section we show extensions of our framework that involve more general data structures.
We first show that our framework presented so far can deal with a class of tree problems in which
the input is a tree but the intermediate data structure is a bag of lists. We then highlight ourgeneralized theory for problems in which the intermediate data structure is a bag of arbitrary
algebraic data types.

7.1

Trees as Input Data

The maximum path weight problem [32] is, given a binary tree, to find the maximum sum along
a path from the root to a leaf. The input of this problem is not a list but a node-valued binary
tree defined as follows using Haskell notation.
data Tree a = Tip | Bin (Tree a) a (Tree a)
A specification maxPathWeight of the problem can be given by composing maxsum and paths
to generate all paths of a given tree.
maxPathWeight = maxsum ◦ paths
The aggregator maxsum is the unique semiring homomorphism from (*[Z]+, ], ×++ ) to (Z−∞ , ↑, +)that satisfies
maxsum *[n ]+ = n
The generator paths is given as follows.
paths = paths ],×++ (λa → *[a ]+)paths ⊕,⊗ f Tip = ı⊗paths ⊕,⊗ f (Bin l n r ) = f n ⊗ (paths ⊕,⊗ f l ⊕ paths ⊕,⊗ f r )The example tree given in Figure 1 contains the following paths:
4(Bool × Bool ) = (Bool × Bool )∪{} and ı? = (False, False).

19

Bin

Bin

Tip

2

Tip

Bin

Tip

1

4

Bin

-3

Tip

Bin

Tip

5

Tip

Figure 1: Tree with maximum path weight 3 witnessed by the paths [1, 2] and [1, −3, 5]*[1, 2], [1, 2], [1, −3, 4], [1, −3, 4], [1, −3, 5], [1, −3, 5]+
All paths are duplicated because Tip nodes do not have values.
Since the function paths ⊕,⊗ is polymorphic over semirings, we can fuse maxvalue and paths to
get maxPathWeight = paths ↑,+ (λn → n), although its type (Z → Z−∞ ) → Tree Z → Z−∞ does
not match the type (A → S ) → [A] → S of polymorphic semiring generators in Definition 7.
However, Theorem 13 is independent of the input type [A] and can be generalized to support
other types such as Tree Z. Additionally, paths ⊕,⊗ satisfies, for any semiring, the parallelizableconditions given in [32]. Thus, the derived program is an efficient parallel program.

7.2

Algebraic Data Types in Intermediate Data

We generalize our framework to an algebraic data type D with a set of functions {φk }nk=1 in
which each φk has type ak → D1 → ... → Dlk . Here, Di is D itself (the subscript is simply
added to count the number of Ds), and ak is a type that does not depend on D (and might bea tuple or the unit type ()). These restrictions limit our generalization to so called regular datatypes where possible type parameters do not change in recursive occurrences.
A D-algebra corresponds to the notion of monoid in our previous development.
Definition 14 (D-Algebra). Given a set A and a set of functions {ck }nk=1 , the pair (A, {ck }nk=1 )is said to be a D-algebra if and only if for any k ∈ {1, . . . , n}, ck has the type ak → A1 → ... →Alk where Ai = A
For example, (D, {φk }nk=1 ) itself is a D-algebra. In the following, D denotes (D, {φk }nk=1 ).
The notion of a monoid homomorphism is generalized as D-algebra homomorphism as follows.
Definition 15 (D-Algebra Homomorphism). Given D-algebras A = (A, {ck }nk=1 ) and B =(B, {c0k }nk=1 ), a function h : A → B is called D-algebra homomorphism from A to B if and only
if it satisfies the following equation for all k.
h (ck a d1 · · · dlk ) = c0k a (h d1 ) · · · (h dlk )Next, we want to introduce a generalization of semirings. An important property of semirings
is distributivity which we generalize to the notion of D-distributivity first.
Definition 16 (D-Distributivity). Given a D-algebra (A, {ck }nk=1 ) and an operator ⊕ : A →A → A the set of functions {ck }nk=1 is said to be D-distributive over ⊕, if it satisfies the following
equation for any k ∈ {1, . . . , n}, any j ∈ {1, . . . , lk }, and any di s and d0j in A.
ck a d1 · · · (dj ⊕ d0j ) · · · dlk = (ck a d1 · · · dj · · · dlk ) ⊕ (ck a d1 · · · d0j · · · dlk )20

A zero of {ck }nk=1 is an element ν such that for all k and j
ck a d1 · · · dj−1 ν dj+1 · · · dlk = νBased on the generalized distributivity and zero, we define the following generalization of
semirings.
Definition 17 (D-Semiring). A triple (A, ⊕, {ck }nk=1 ) is a D-semiring, if and only if (A, {ck }nk=1 )is a D-algebra, (A, ⊕) is a commutative monoid, {ck }nk=1 is D-distributive over ⊕, and theidentity ı⊕ of ⊕ is a zero of {ck }nk=1 .
An important D-semiring is BD = (*D+, ], {Φk }nk=1 ) where the cross construction operator
Φk s are defined as follows.
Φk a b1 · · · blk = *φk a d1 · · · dlk | d1 ← b1 , . . . , dlk ← blk +The D-semiring BD is the free D-semiring in the sense that there is exactly one D-semiring
homomorphism from BD into every other D-semiring.
Definition 18 (D-Semiring Homomorphism). Given two D-semirings A = (A, ⊕, {ck }nk=1 ) andB = (B, ⊕0 , {c0k }nk=1 ), a function h :A → B is called D-semiring homomorphism from A to B if it
is a D-algebra homomorphism from (A, {ck }nk=1 ) to (B, {c0k }nk=1 ) and a monoid homomorphismfrom (A, ⊕) to (B, ⊕0 )Finally, we generalize polymorphic semiring generators.
Definition 19 (Polymorphic D-Semiring Generator). For a fixed set X , a function
generate ⊕,{ck }n

k=1

:X →S

that is polymorphic over an arbitrary D-semiring (S , ⊕, {ck }nk=1 ) is called a polymorphic Dsemiring generator.
Now we can give generalized versions of our theorems. The generalization of Theorem 8 is
as follows.
Theorem 20 (D-Semiring Fusion). Given a D-semiring S = (S, ⊕, {ck }nk=1 ), a D-semiring
homomorphism aggregate from BD to S, and a polymorphic D-semiring generator generate,
the following equation holds:
aggregate ◦ generate ],{Φk }nk=1= generate ⊕,{ck }nk=1

Proof. Free Theorem [40].
Now, we proceed to the generalized filter embedding. Similar to the usual semirings, we canbuild a D-semiring of families of elements of another D-semiring indexed by a finite D-algebra.
Lemma 21 (Lifted D-Semiring). Given a D-algebra (E, {c0k }nk=1 ) where E is a finite set and anD-semiring (S, ⊕, {ck }nk=1 ), the triple (S E , ⊕E , {cEk }k=1 ) where0(f ⊕E f 0 )e = fe ⊕ feL(cE
e1 ,...,elk ∈E ck a (d1 )e1 · · · (dlk )elk
k a d1 · · · dlk )e =c0k a e1 ···elk ≡e

is a D-semiring with (ı⊕E )e = ı⊕ .
21

Proof. Associativity and commutativity of ⊕E follow from those of ⊕. D-distributivity ofn{ck }nk=1 and the properties of ⊕ guarantee D-distributivity of {cEk }k=1 . The zeroness of ı⊕E isclear from that of ı⊕ .
Based on generalized lifted semirings, we generalize the Filter Embedding Theorem 12.
Theorem 22 (Filter Embedding on D-Semiring). Given a finite D-algebra E = (E, {c0k }nk=1 ),a D-algebra homomorphism hom from D to E, a D-semiring S = (S, ⊕, {ck }nk=1 ), a D-semiring
homomorphism aggregate from BD to S, and a function ok : E → Bool , the following equation
holds.
aggregate ◦ test (ok ◦ hom) = postprocess ok ◦ aggregate E
Here, aggregate E is the D-semiring homomorphism from BD to the lifted D-semiring, andpostprocess is the same as that in the filter embedding for the usual semirings.
Proof. Similar to Theorem 12.
By combining the two previous theorems we get a generalized version of our Main Theorem 13.

7.3

Additional Laws for Parallelization

The generalized version of our Main Theorem is not strictly a generalization because it does
not consider additional laws necessary for parallelization. Filter-embedding D-semiring fusion
is independent of such laws because it works for an arbitrary polymorphic generator.
However, in order for the generator to be parallelizable, usually, additional laws are required. For example, parallelization of list homomorphisms relies crucially on associativity oflist concatenation. Polymorphic semiring generators that are expressed as a list homomorphism
are only meaningful because the result type is a semiring and semiring multiplication is associative. Both the free semiring (used in the specification) and the lifted semiring (used in
the efficient implementation) are multiplicative monoids and can, therefore, be results of list
homomorphisms.
We require neither the free D-semiring BD nor the lifted D-semiring to satisfy laws for parallelization because these laws depend on the used D-algebra. Although it may seem plausiblethat all laws of D-algebras are preserved in the construction of the free and lifted D-semirings
via D-distributivity, this is not the case. In this subsection, we give examples for laws that arepreserved as well as laws that are not preserved and argue intuitively what kinds of laws arepreserved in general. A more formal treatment is not in the scope of this paper.
As an example for a law that is preserved by the free D-semiring, consider tree commutativity
for the binary tree type introduced in Section 7.1:
Bin l x r = Bin r x l
For the sake of concreteness, we show for l = *s, t+ and r = *u+ that the free Tree-semiring
satisfies
Bin × l x r = Bin × r x l
if the underlying Tree-algebra satisfies tree commutativity. Following the definition of BD
specialized to Tree, Bin × is defined as follows.
Bin × l x r = *Bin v x w | v ← l , w ← r +22

Bin × l x r= { Definition of l and r }Bin × *s, t+ x *u+= { Definition of Bin × }*Bin s x u, Bin t x u+
= { Underlying tree commutativity }*Bin u x s, Bin u x t+
= { Definition of Bin × }Bin × *u+ x *s, t+= { Definition of l and r }Bin × r x lTree commutativity of the free Tree-semiring essentially follows from tree commutativity of theunderlying structure and distributivity of Bin × over bag union.
We can check similarly that the lifted Tree-semiring preserves tree commutativity of the underlying Tree-algebras. As an example, consider the lifted Tree-semiring of families of elementsin the free Tree-semiring indexed by Bool . We can define the Tree-algebra (Bool , {cBin , cTip }),that checks if the sum of all node labels is odd, as follows.
cBin l x r = (odd x ) ≡ (l ≡ r )cTip= FalseApparently, cBin satisfies tree commutativity and, as we have seen before, the free Tree-semiring
preserves tree commutativity of an underlying Tree-algebra. As an example for tree commutativity in the lifted Tree-semiring, we show
Bin Booll x r = Bin Boolrxl
××
for x = 1, l = (a, b), and r = (c, d ). Similar to Section 5.1 we represent indexed families astuples. The first component is the element indexed by False and contains bags of trees with aneven sum of node labels. The second component is the element indexed by True and contains
bags of trees with an odd sum of node labels.
Bin Boollxr
×= { Definition of x , l , and r }Bin Bool(a, b) 1 (c, d )×= { Definition of Bin Bool}×
(Bin × a 1 c ] Bin × b 1 d , Bin × a 1 d ] Bin × b 1 c)
= { Underlying tree commutativity }(Bin × c 1 a ] Bin × d 1 b, Bin × d 1 a ] Bin × c 1 b)
= { Definition of Bin Booland commutativity of ] }×
BoolBin × (c, d ) 1 (a, b)= { Definition of x , l , and r }Bin Boolrxl
×
The two given examples suggest that arbitrary laws of an underlying D-algebra are preservedby the free and lifted D-semirings.
However, certain laws are not preserved. For example, even if the underlying D-algebra has
an idempotent multiplication (satisfying x ⊗ x = x ), multiplication ×⊗ in the free D-semiring
is not idempotent:23

*x , y+ ×⊗ *x , y+
= *x ⊗ x , x ⊗ y, y ⊗ x , y ⊗ y+
= *x , x ⊗ y, y ⊗ x , y+
The result is different from *x , y+ because it contains four elements, not two. The problem inthis example is the duplication of the variable x on the left side of the idempotence law whichleads to different numbers of bag elements on both sides of the law.
In general, so called linear laws where each variable occurs exactly once (like associativity orcommutativity laws) are preserved by the free and lifted D-semirings but laws where variables
are duplicated or missing on one side (like idempotence or inverse laws) are not preserved.
Fortunately, laws that are employed for parallelization usually do not duplicate (or drop)elements in order to not cause additional (or missing) work.
An example for trees that support parallelism are ternary trees [31]. They come with socalled tree associativity laws that are used for load balancing. The tree associativity laws arelinear and, therefore, generators expressed as ternary-tree homomorphisms can be used together
with our generalized GTA framework.

8

Related Work

8.1

Homomorphism-based Parallelization

The research on parallelization via derivation of list homomorphisms has gained great interest [35, 11, 19]. The main approaches include the third homomorphism theorem based
method [18, 33], function composition based method [14, 23, 10], and matrix multiplication
based method [34]. Our work is a continued effort in this direction, giving a new approachbased on semiring homomorphisms, which is in sharp contrast to the existing work based on
monoid homomorphisms.
There has been a lot of work about using MapReduce to parallelize various kinds of problems[28]. Some formal work has been devoted to the study of a computation model of MapReduce(compared to the PRAM model of computation) [25]. However, little work has been doneon systematic construction of MapReduce programs. We tackle this problem via semiring
homomorphisms.

8.2

Shortcut Deforestation (Fusion) and Free Theorems

Our shortcut fusion theorem for semiring fusion is much related to the known shortcut deforestation [15, 37] which is based on a free theorem [40] and is practically useful for optimizationof sequential programs. Different from the traditional shortcut deforestation focusing on thedata constructors of the intermediate data structure that are passed from one function to another, our shortcut fusion focuses on the semiring operations in the intermediate data structure.
It is this semiring structure that allows for flexible rearrangement of computation for efficientparallel execution.

8.3

Semiring-based Computation

Kohlas and Wilson [26] studied semiring-induced valuation algebras and succeeded in giving
uniform formalization of many problems in various fields. However, their algorithm requires acost exponential to the size of the largest constraint, so that it cannot deal with global conditions
such as “the number of items with weight less than ten is at most three” in the knapsack problem.
Our filter-embedding would be useful to add global constraints to the framework.
24Goodman [17] extended the CYK parsing algorithm by substituting various semirings for
the Boolean semiring, so that one can reuse the algorithm for various computations such ascounting the number of parsings, computing the probability of generating the given string, andfinding the best k-parsing. We can reuse his semirings in our GTA form for computing similarvariations.
Bistarelli et al. [6, 7, 8] proposed a framework for semiring-based constraint logic programming, which extends the logic programming with semiring-based soft constraints, and studied its
semantics and decidabilities. One problem of their framework is that, given a complex problem,
one needs to design a system of recursive equations at once. Our method can decompose thedevelopment into design of the main simple algorithm and design of filters, which is much easierthan the direct development. Larrosa et al. [27] proposed a similar extension to propositional
logic programming.
Abdali and Saunders [1, 2] proposed an efficient parallel algorithm for the elimination operation in the matrix algebra on a *-semiring. The operation can be used to compose parallel
algorithms for solving systems of linear equations and computing transitive closures. Althoughthese are not directly related to our applications, they are useful for many problems in computerscience and operations research. The key point of their algorithm is that the ∗ operator canbe used to define an inverse of ⊗. It would be interesting future work to import such inverse
operations into our framework to derive more efficient programs.

9

Conclusion

We propose a calculation-based framework for the systematic development of efficient MapReduce programs in the form of GTA algorithms. The core of the framework consists of two
calculation theorems for semiring fusion and filter embedding. Semiring fusion connects a specification in GTA form and an efficient implementation by a free theorem, while filter embedding
transforms the composition of a semiring homomorphism and a test into another semiring homomorphism which enables incremental development of parallel algorithms. Our approach allows
to develop efficient parallel algorithms by combining simpler homomorphisms (for generation,
testing, and aggregation) into more complex ones, which is easier than defining the efficientparallel algorithms directly. In contrast to existing approaches, our theorems allow to modify
an efficient algorithm by adding homomorphic filters in the “naive world” which is easier thanmodifying it in the “efficient world”. Our new framework is not only theoretically interesting,but also practically significant in solving nontrivial problems.
For example, we have shown how to derive an efficient parallel implementation of a known
statistics problem and found that it is equivalent to an existing algorithm for the same problem.
This result shows that our approach generalizes existing techniques and provides a common
framework to express them. We expect that our approach can be applied to typical “bigdata” problems, like finding patterns in historical financial data, and plan to investigate suchapplications as future work.
Moreover, we plan to implement the developed programming theory as a domain specificlanguage or a library, for example upon Hadoop [41], so that typical MapReduce problems canbe tackled using our GTA approach. Our theorems can be easily mechanized because of theirsimple calculational form.

25References[1] S. Abdali. Parallel computations in *-semirings. In K. Fischer, P. Loustaunau, J. Shapiro,
E. Green, and D. Farkas, editors, Computational Algebra, volume 151 of Lecture Notes inPure and Applied Mathematics, pages 1–13. CRC Press, 1993.
[2] S. K. Abdali and B. D. Saunders. Transitive closure and related semiring properties via
eliminants. Theoretical Computer Science, 40:257–274, 1985.
[3] R. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programmingand Calculi of Discrete Design, pages 5–42. Springer-Verlag, 1987.
[4] R. Bird. Introduction to Functional Programming using Haskell. Prentice Hall, 1998.
[5] R. Bird and O. de Moor. Algebras of Programming. Prentice Hall, 1996.
[6] S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint satisfaction and optimization. Journal of ACM, 44:201–236, 1997.
[7] S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint logic programming:
syntax and semantics. ACM Transactions on Programming Languages and Systems, 23:1–
29, 2001.
[8] S. Bistarelli, U. Montanari, F. Rossi, and F. Santini. Unicast and multicast qos routing with
soft-constraint logic programming. ACM Transactions on Computational Logic, 12:5:1–
5:48, 2010.
[9] B. Carre. Graphs and Networks. Clarendon Press, 1979.
[10] W.-N. Chin, S.-C. Khoo, Z. Hu, and M. Takeichi. Deriving parallel codes via invariants.
In Static Analysis, 7th International Symposium, SAS 2000, volume 1824 of LNCS, pages
75–94. Springer, 2000.
[11] M. Cole. Parallel programming with list homomorphisms. Parallel Processing Letters,
5(2):191–203, 1995.
[12] J. H. Conway. Regular Algebra and Finite Machines. Chapman & Hall, 1971.
[13] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51:107–113, 2008.
[14] A. L. Fisher and A. M. Ghuloum. Parallelizing complex scans and reductions. In Proceedings of the ACM SIGPLAN 1994 conference on Programming language design andimplementation (PLDI ’94), pages 135–146. ACM, 1994.
[15] A. Gill, J. Launchbury, and S. L. Peyton Jones. A short cut to deforestation. In Conference
on Functional Programming Languages and Computer Architecture, pages 223–232, 1993.
[16] M. Gondran, M. Minoux, and S. Vajda. Graphs and algorithms. John Wiley & Sons, Inc.,
1984.
[17] J. Goodman. Semiring parsing. Computational Linguistics, 25:573–605, 1999.
[18] S. Gorlatch. Systematic efficient parallelization of scan and other list homomorphisms. In
Euro-Par ’96 Parallel Processing, volume 1124 of LNCS, pages 401–408. Springer, 1996.
26

[19] Z. Grant-Duff and P. Harrison. Parallelism via homomorphism. Parallel Processing Letters,
6(2):279–295, 1996.
[20] T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In Proceedings ofthe twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of databasesystems, PODS ’07, pages 31–40, New York, NY, USA, 2007. ACM.
[21] Y. He. Extended viterbi algorithm for second order hidden markov process. In 9th International Conference on Pattern Recognition, pages 718–720 vol.2. IEEE Press, 1988.
[22] T.-J. Ho and B.-S. Chen. Novel extended viterbi-based multiple-model algorithms for state
estimation of discrete-time systems with markov jump parameters. IEEE Transactions on
Signal Processing, 54(2):393–404, 2006.
[23] Z. Hu, M. Takeichi, and W.-N. Chin. Parallelization in calculational forms. In 25th
ACM Symposium on Principles of Programming Languages (POPL’98), pages 316–328,
San Diego, California, USA, 1998. ACM Press.
[24] Z. Hu, T. Yokoyama, and M. Takeichi. Program optimization and transformation in calculational form. In Summer School on Generative and Transformational Techniques in
Software Engineering (GTTSE 2005), 2005.
[25] H. Karloff, S. Suri, and S. Vassilvitskii. A model of computation for mapreduce. In
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’10, pages 938–948. SIAM, 2010.
[26] J. Kohlas and N. Wilson. Semiring induced valuation algebras: Exact and approximate
local computation algorithms. Artificial Intelligence, 172:1360–1399, 2008.
[27] J. Larrosa, A. Oliveras, and E. Rodrı́guez-Carbonell. Semiring-induced propositional logic:
definition and basic algorithms. In Proceedings of the 16th international conference on
Logic for programming, artificial intelligence, and reasoning, LPAR’10, pages 332–347.
Springer-Verlag, 2010.
[28] J. Lin and C. Dyer. Data-Intensive Text Processing with MapReduce. Morgan and Claypool
Publishers, 2010.
[29] M.
A.
P.
List.
applications/papers/. 2011.

http://www.mendeley.com/groups/1058401/mapreduce-[30] Y. Liu, Z. Hu, and K. Matsuzaki. Towards systematic parallel programming over mapreduce. In Euro-Par 2011 Parallel Processing, volume 6853 of LNCS. Springer, 2011.
[31] K. Matsuzaki. Parallel Programming with Tree Skeletons. PhD thesis, Graduate School ofInformation Science and Technology, University of Tokyo, 2007.
[32] A. Morihata, K. Matsuzaki, Z. Hu, and M. Takeichi. The third homomorphism theorem ontrees: downward & upward lead to divide-and-conquer. In Proceedings of the 36th annual
ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’09,
pages 177–185. ACM, 2009.
[33] K. Morita, A. Morihata, K. Matsuzaki, Z. Hu, and M. Takeichi. Automatic inversion generates divide-and-conquer parallel programs. In ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI ’07), pages 146–155. ACM Press,
2007.
27

[34] S. Sato and H. Iwasaki. Automatic parallelization via matrix multiplication. In Proceedingsof the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI ’11), pages 470–479. ACM, 2011.
[35] D. B. Skillicorn. The Bird-Meertens Formalism as a Parallel Model. In NATO ARW“Software for Parallel Computation”, 92.
[36] A. Takano, Z. Hu, and M. Takeichi. Program transformation in calculational form. ACM
Computing Surveys, 30(3), 1998.
[37] A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. Conference
on Functional Programming Languages and Computer Architecture, pages 306–313, La
Jolla, California, 1995.
[38] R. E. Tarjan. A unified approach to path problems. Journal of ACM, 28:577–593, 1981.
[39] W. Thomas. Automata on infinite objects. In Handbook of Theoretical Computer Science,
Volume B: Formal Models and Sematics, pages 133–192. Elsevier and MIT Press, 1990.
[40] P. Wadler. Theorems for free! In Proceedings of the fourth international conference on
Functional programming languages and computer architecture, FPCA ’89, pages 347–359.
ACM, 1989.
[41] T. White. Hadoop: The Definitive Guide. O’Reilly Media, 2009.

28