Under consideration for publication in Formal Aspects of Computing

Filter-embedding Semiring Fusion for
Programming with MapReduce1
Kento Emoto† , Sebastian Fischer‡ , and Zhenjiang Hu‡† The University of Tokyo,‡ National Institute of Informatics, Tokyo

Abstract.
We show that MapReduce, the de facto standard for large scale data-intensive parallel programming, canbe equipped with a programming theory in calculational form. By integrating the generate-and-test programming paradigm and semirings for aggregation of results, we propose a novel parallel programming frameworkfor MapReduce. The framework consists of two important calculation theorems: the shortcut fusion theoremof semiring homomorphisms bridges the gap between specifications and efficient implementations, and thefilter-embedding theorem helps to develop parallel programs in a systematic and incremental way.
Keywords: MapReduce, List Homomorphisms, Functional Programming, Program Transformation, Program Calculation, Semiring Computation.

1. Introduction
Programming is more than just writing programs. Programmers must be concerned with efficiency (both insequential and parallel) and maintainability (modularity), while meeting specifications. This calls for moreprogramming theory that is both theoretically beautiful and practically useful.
MapReduce [DG08], the de facto standard for large scale data-intensive applications, is a remarkable parallel
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 andfault tolerance, developing efficient MapReduce parallel programs remains as a challenge in practice, andlittle effort has been made to emphasize the programming methodology behind. This lack of programming
methodology for MapReduce has led to publication of too many papers about MapReduce applications[Lis11], each addressing a solution to one specific problem, even if quite a lot of problems follow a common
pattern and can be solved generally.
Can MapReduce be equipped with a programming theory (in calculational form [BdM96, HYT05, THT98])
that can be applied to give efficient solutions to a wide class of problems? We consider a general class ofproblems which can be specified in the following generate-test-and-aggregate (GTA for short) form:
Correspondence and offprint requests to: Kento Emoto, University of Tokyo, Hongo 7-3-1, Bunkyo, Tokyo, Japan. e-mail:emoto@mist.i.u-tokyo.ac.jp
1 This is an extended version of the paper ”Generate, Test, and Aggregate: A Calculation-based Framework for Systematic
Parallel Programming with MapReduce” presented at ESOP 2012.

2

K. Emoto, S. Fischer, and Z. Hu

aggregate ◦ test ◦ generate
Problems that match this specification can be naively 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.
Like other programming theories in calculational form [HYT05, THT98], the big challenges in the development of our calculation theory are to decide a structured form such that any program in this form isguaranteed to be efficiently parallelized, and to show how a specification can be systematically mapped tothe structured form. To this end, we refine the specification with constraints 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 theaggregating computation is structured in a way that matches with the generator.
These constraints, as will be seen later, can be satisfied for many practical problems. An interesting result of
this paper is that any specification that satisfies these constraints can be automatically mapped to an efficient
program in, but not limited to, MapReduce; if the generator can be efficiently implemented in parallel, so
does the whole specification.
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 later by the aggregator. In fact, using
semirings to structure computation is not new. Semirings have been widely used for uniform formalizationof 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 systems of linear equations, and relational algebras for incomplete or probabilistic databasesin computer science and operations research [GKT07, Abd93, Goo99, AS85, Tar81, GMV84, Con71, Car79].
However, the use of semirings for the systematic development of reliable efficient parallel programs has notbeen studied in depth.
In this paper, by integrating the generate-and-test programming paradigm and semirings for result aggregation, we propose a novel programming framework based on automatic filter-embedding semiring fusionthat is centered on two calculation theorems, the semiring fusion theorem and the filter embedding theorem.
These two 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 witha homomorphic predicate, and a semiring homomorphism as aggregator. Our main technical contributions
can be summarized as follows.
• We propose a new formalization of GTA problems in the context of parallel computation based on thesemiring 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 theircomposition can be done for free and results in an efficient homomorphism parallelizable by MapReduce.
• We propose a new systematic and incremental approach to developing parallel programs for more complicated GTA problems based on the filter embedding theorem. The filter-embedding theorem allows asemiring homomorphism to absorb preceding tests yielding a new semiring homomorphism. We give
nontrivial examples that demonstrate how to apply our framework.
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 specifying parallel programs bymeans of the knapsack problem in Section 3, we focus on two important calculation 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 [Bir98]. Function application is denoted by a space andthe argument may be written without brackets, so that (f a) means f (a) in ordinary notation. Functions

Filter-embedding Semiring Fusion for Programming with MapReduce3

are curried: they always take one argument and return a function or a value, 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 ⊗bmeans (f a) ⊗ b. Function composition is denoted by ◦, and (f ◦ g) x = f (g x ) according to its definition.
Binary operators can be used as functions by sectioning as follows: a ⊕ b = (a⊕) b = (⊕b) a = (⊕) a b. The
symbol ≡ denotes the equivalence predicate that returns True if both sides are equivalent.
Lists are finite sequences of values of the same type. A list is either empty, a singleton, or the concatenationof two other lists. We write [ ] for the empty list, [x ] for the singleton list with element x , and xs ++ ys forthe concatenation of two lists xs and ys. For example, the term [1] ++ [2] ++ [3] denotes a list with threeelements, 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
on M (i.e., M is closed underpair (M , ) is called a monoid if is associative and has an identity ı ∈ M :(aıb) c = aa=a =a(bı), thec)

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 operationand its identity.
Definition 2 (Monoid Homomorphism). Given two monoids (M , ) and (M 0 ,hom : M → M), a function0

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

For 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 result monoid, a list homomorphism(monoid homomorphism from the list monoid) 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 is exactly
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 repeated application 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 list homomorphism is the function map that applies a given function to each element ofa list. It is characterized by
map f [x ] = [f x ]Informally, we have
map f [x1 , x2 , ..., xn ] = [f x1 , f x2 , ..., f xn ]

4

K. Emoto, S. Fischer, and Z. Hu

According to the homomorphism lemma [Bir87], 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:
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 thecomputation evenly among different processors or even machines by the well-known divide-and-conquer
parallel paradigm [Ski92, Col95].
For example, by providing a parallel implementation for the composition of a reduction and a 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 [Ski92, Col95].
MapReduce [DG08] 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 of time only by distributing thework to multiple machines in parallel. Each machine processes a small 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 to compute a set of intermediate key/value pairs, anda reduce operation to all the values that shared the same key to get the appropriate derived data. Readers
can find a functional model of MapReduce in [Läm08].
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 [LHM11]. 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, enjoying its advantages such as automatic load-balancing, fault-tolerance, andscalability.
Some readers might feel that there is a mismatch between a typical MapReduce computation and computations in GTA style, because the size of the results generated by map in the former is often proportional to
the size of the input data while the latter appears to have much larger intermediate results. This mismatchis a strength of our approach: based on a naively-designed GTA specification our calculation theorems canprovide an efficient MapReduce implementation with intermediate results proportional to the size of the input, i.e., efficient list homomorphisms. Our approach makes MapReduce applicable to applications appearing
not to match the MapReduce pattern. As a consequence, it allows programmers to implement MapReduce
algorithms by providing an often simpler specification in GTA form.

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 and use it throughout Sections 4
and 5 to show how to transform such specifications into efficient parallel programs. 2
The knapsack problem is to fill a knapsack with items, each of certain non-negative value and weight, suchthat 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 pick the 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 acomposition of three functions:knapsack = maxvalue ◦ filter ((6 w ) ◦ weight) ◦ sublists
2

The knapsack problem is NP-complete and the knapsack function calculated in Section 5 is pseudo-polynomial, i.e., polynomialin the maximum weight but not in the size of its binary encoding.

Filter-embedding Semiring Fusion for Programming with MapReduce

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 weightexceeds w and keeps the rest.
• The function maxvalue is the aggregator. From the remaining sublists adhering to the weight 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, e.g.,*[ ], [x ]+ = *[ ]+ ] *[x ]+, 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]+= *[ ] ++ [ ], [ ] ++ [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 the composition of
the function weight that adds all weights in a list and the function (6 w ) that checks 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
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 lastequation, 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 concatenated lists is the sum of the maximum total valuesof the lists in each bag. This observation relies on distributivity of + over ↑, a property that we will revisit
in the next section.

6

K. Emoto, S. Fischer, and Z. Hu

4. Semiring Fusion
In this section we show how to derive efficient parallel programs from specifications in generate-and-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 thatshows 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 homomorphismwith respect to two different monoids (namely, (Z−∞ , ↑) and (Z−∞ , +)) 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 have identities −∞and 0, respectively, where Z−∞ = Z∪{−∞}. Moreover, + distributes over ↑ and −∞ is a zero of +. Thissemiring is sometimes called tropical algebra [But10].
• (*[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 ), a function
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 ).
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 , ⊕, ⊗) that satisfies h *[x ]+ = f x .

Proof. Regarding uniqueness, observe that any two semiring homomorphisms from bags of lists are identical
if they agree on singleton bags of singleton lists because the homomorphism properties allow to “push down”
the applications of semiring homomorphisms to such bags.
Regarding the existence of h, assume a variant of Lemma 3 for commutative monoids and bags instead oflists. Then there is a commutative-monoid homomorphism h from (*[A]+, ]) to (S , ⊕) such that h *l + = h 0 l
where h 0 is the monoid homomorphism from ([A], ++) to (S , ⊗) that satisfies h 0 [x ] = f x . The proof
that h is a semiring homomorphism is straightforward and uses only monoid-homomorphism properties anddistributivity.
The unique homomorphism h can be thought of as applying f to each list element, then accumulating theresults in each list using the operator ⊗, and finally accumulating those results using the operator ⊕.

Filter-embedding Semiring Fusion for Programming with MapReduce

7

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 is the value *[x ]+ constructedfrom an element x ∈ A.
We can generalize sublists by parameterizing it with operations ⊕ and ⊗ of an arbitrary semiring (and theiridentities) 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 an arbitrary semiring
determined by the passed semiring operators and embedding function. It is a generalization of sublists
becausesublists = sublists ],×++ (λx → *[x ]+)The anonymous function passed as argument constructs a singleton bag containing a singleton list with theargument x .
Definition 7 (Polymorphic Semiring Generator). A function
generate ⊕,⊗ : (A → S ) → [A] → S
that is polymorphic over an arbitrary semiring (S , ⊕, ⊗) is said to be 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 computea result in Z−∞ .
sublists ↑,+ (λ(v , w ) → v ) : *[Z−∞ × Z−∞ ]+ → Z−∞

What does this function compute? Theorem 8 below, which is a variant of short-cut fusion for semiring
homomorphisms, casts light on this question.
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, the following equation
holds:
aggregate ◦ generate ],×++ (λx → *[x ]+) = generate ⊕,⊗ (λx → aggregate *[x ]+)Proof. Free Theorem [Wad89].
Interestingly, in a polymorphically typed language like Haskell this theorem can be proved solely basedon type information, for example, using an automatic generator for free theorems.3 It is related shortcut
fusion [GLPJ93, TM95] with bags of lists as intermediate type (cf. Section 8.2).
We can use Theorem 8 to answer the question of 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 values of sublistsof 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 thelength of the input list.
3

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

8

K. Emoto, S. Fischer, and Z. Hu

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 the input listin this problem contains only positive values and maxvalue ◦ sublists, thus, computes the total value of allavailable items.
For solving the knapsack problem, it is crucial to compute the maximum value only of those sublists of
the input list which adhere to the weight restriction. We need to account for the test that implements thisrestriction which is the topic of the next section.

5. Filter Embedding
We cannot apply Theorem 8 to transform specifications of the form
aggregate ◦ test ◦ generatebecause the intermediate test goes in the way of fusing the aggregator with the generator. Instantiations oftest given below show how to rewrite certain specifications into the form
postprocess ◦ aggregate 0 ◦ generate
where aggregate 0 is a semiring homomorphism derived from aggregate and test, 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 into a finite
monoid M and a function ok :M → Bool that maps elements of M to Booleans. Here, we require the finiteness
only in order to be able to describe the complexity of the resulting parallel algorithms more accurately.
Before we describe the general theorem in Section 5.2, we develop the underlying ideas by deriving 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 ourdevelopment for each specification. 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 and the function(6 w ) that maps the result of weight into the Booleans.

Filter-embedding Semiring Fusion for Programming with MapReduce9

However, the result type of weight is N which is an infinite monoid, not a finite one. We can remedy thesituation 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 with w + 1 by
the minimum operator ↓. 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 , and wehave weight w x = (w + 1) ↓ weight x . In general, programmers are responsible to ensure the finitenessrestriction, but developing an automatic finitization method is part of our future work.
To transform the function maxvalue ◦ filter ((6 w ) ◦ weight w ) into the form postprocess w ◦ maxvalue w weneed to invent a semiring to use as result type of maxvalue w . The idea is to compute simultaneously for
all weights in Mw the maximum value of lists with exactly that weight. The function postprocess w thencomputes the maximum over all values associated to weights 6 w .
Like in Section 3, we assume the maximum total weight of our knapsack is 5kg, i.e., w = 5. Semiring
elements can be represented as 7-tuples over Z−∞ , namely, six maximum values associated with weights 6 5
and the accumulated maximum value corresponding to all weights > 6 because of the cut off. 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.
We now turn Z7−∞ into a semiring (Z7−∞ , ↑7 , +7 ). To compute the maximum value associated to each weightof 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 andits identity is (−∞, −∞, −∞, −∞, −∞, −∞, −∞) .
The operator +7 is more interesting. From two 7-tuples that associate maximum values to each weight in M5
it computes another 7-tuple that associates maximum values to the combined weights. For example, to findthe maximum value associated to the weight 3, it computes the maximum of all sums of values associatedto weights that sum up to 3 (we omit the part for larger 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 the following 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 associated to its weight (or to
the weight 6 if it is heavier).
Our Main Theorem 13 below will explain why, 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:

10

K. Emoto, S. Fischer, and Z. Hu

knapsack [(2000, 1), (3000, 3), (4000, 3)]= knapsack ([(2000, 1)] ++ [(3000, 3)] ++ [(4000, 3)])= 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 value that canbe 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 and the weight restriction
is w. As sublists ↑7 ,+7 is a monoid homomorphism we can execute it in parallel, say using p processors, whichleads to the run time O((log p + np )w2 ). This complexity resembles the run time of other parallel algorithms
to solve the knapsack problem, e.g., one given by [SI11]. The standard sequential algorithm has run timeO(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 to highlight the ideas behind ourapproach, 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 to each weight in
M5 . In the general setting, we use indexed families instead of tuples. A family f = {fm }m∈M of elements in
S indexed by M is extensionally equivalent to a function f : M → S where fm denotes f (m) for notational
convenience. For given sets M and S , we write S M for the set of all families of elements in S indexed by M .
If M is a finite monoid and S is a semiring, then S M is a semiring too. We give definitions of indexed families
by defining their value in S for each m ∈ M .
Lemma 9 (Lifted Semiring).
Given a finite monoid (M , ) and a semiring (S , ⊕, ⊗) the triple (S M , ⊕M , ⊗M ) where(f ⊕M f 0 )m = fmL⊕ fm00(f ⊗M f )m =(fk ⊗ fl0 )
k,l∈M
k l=m

is a semiring with (ı⊕M )m = ı⊕ and (ı⊗M )m = if m ≡ ı then ı⊗ else ı⊕ .
Proof. The monoid laws for ⊕M follow directly from those of ⊕. Regarding the laws for ⊗M , interested
readers can find proofs in [Emo11] or be content with the observation that (S M , ⊕M , ⊗M ) is a monoid
semiring which is a variant of a group ring [Haz02].

Filter-embedding Semiring Fusion for Programming with MapReduce11

The definition of ⊕M uses the underlying ⊕ operator just like the definition of ↑7 in Section 5.1 uses ↑. The
sum computed by ⊕M is finite because M is finite.4 The operator ⊗M , like +7 , computes for each m the
maximum of all sums of values associated to weights that add up to m if we instantiateand ⊗ 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 theresult of applying aggregate to a bag of exactly those lists l ∈ ls that satisfy hom l = m:lsfm
= aggregate (filter ((m ≡) ◦ hom) ls)

Considering different instantiations for ls, we can observe the following identities:
fm
= ı⊕
*[ ]+
fm
= if m ≡ ı then ı⊗ else ı⊕ls]ls 0
ls
ls 0
fm
= fm
⊕ fm
0
L
0
ls× lsfm ++ =
(fkls ⊗ flls )
*+

k,l∈M
k l=m

They reflect the definitions of the semiring operations for S M and their identities. Because of these homomorphic equations for f ls , we can compute f ls using a semiring homomorphism aggregate hom that satisfies(aggregate hom *[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 hom : *[A]+ → S M

is the unique semiring homomorphism from (*[A]+, ], ×++ ) to (S M , ⊕M , ⊗M ) that satisfies(aggregate hom *[x ]+)m = if hom [x ] ≡ m then aggregate *[x ]+ else ı⊕
The function aggregate hom generalizes the function maxvalue 5 by using aggregate and ı⊕ instead of maxvalueand −∞.
ls
Once we have computed f ls , we can use a function ok : M → Bool to combine all results fm
for m ∈ M withok m = True to get the result ofLaggregate (filter (ok ◦ hom) ls) =(aggregate (filter ((m ≡) ◦ hom) ls))m∈M
ok m=True

According to this equation, we can partition the bag of accepted lists according to elements of M andaggregate them individually because aggregate is a semiring homomorphism. The postprocessor defined next
combines such individual aggregations.
Definition 11 (Postprocessor). Given a finite set M , a monoid (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=True

4

An alternative definition of ⊕M ranging over the finite domains (with non-zero image) of indexed families can be given torelax the finiteness requirement for M .

12

K. Emoto, S. Fischer, and Z. Hu

It is 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 homfrom ([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 hom
Proof. The following calculation combines previous observations and definitions to show the claimed identity.
=

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

Our main result combines the theorems from Sections 4 and 5. It allows, under certain conditions, totransform 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 , and a polymorphic semiring generator
generate, the following equation holds:
aggregate ◦ filter (ok ◦ hom) ◦ generate ],×++ (λx → *[x ]+)= postprocess M ok ◦ generate ⊕M ,⊗M (λx → aggregate hom *[x ]+)Proof. Combining previous Theorems.
aggregate ◦ filter (ok ◦ hom) ◦ generate ],×++ (λx → *[x ]+)= { Theorem 12 }postprocess M ◦ aggregate hom ◦ generate ],×++ (λx → *[x ]+)= { Theorem 8 }postprocess M ◦ generate ⊕M ,⊗M (λx → aggregate hom *[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 expressed using regularexpressions or monadic second order logic [Tho90]. This fact may help readers to assess which problems
fit into our setting. It is also possible to remove the finiteness requirement for monoids and define a lifted
semiring of finite mappings of unbounded and unknown size. We require the finiteness only in order to beable to describe the complexity of the resulting parallel algorithms more accurately.
If the generator happens to be a monoid homomorphism from lists, 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 the homomorphic predicate because
the semiring multiplication of the lifted semiring S M , which is used to combine all list elements, can be
implemented by ranging over M × M .

Filter-embedding Semiring Fusion for Programming with MapReduce

13

6. A More Complex Application
In this section we describe how to use our framework to derive an efficient parallel implementation for apractical 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 of hidden statesof 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 sequenceof hidden states.
Given a sequence x = (x1 , . . . , xn ) of observed events, a finite 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 ) ofstates zi appearing immediately after states zj , the objective is to find a sequence 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. Here, argmax returns theargument that maximizes the objective function.
nQargmaxPyield (xi | zi )Ptrans (zi | zi−1 )z∈S n+1i=1

To derive an efficient parallel algorithm to solve this problem, we transform this expression to fit in ourframework.
To eliminate the index i − 1, we let the expression range over pairs of hidden states in S × S and introduce a
predicate trans, whose formal definition is given later, to restrict the considered lists of state pairs. Intuitively,trans y is 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.
nQargmaxprob (xi , yi )y∈(S×S)ntrans y=True

i=1

In a first step, we specify only the maximum probability in GTA form. We show how to compute a 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, f is a function from X × (S × S ) to T and 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 associated state transitions where the events are in the same order as in the input list andall possible combinations 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, the identity (ı ) andan element () defined as its zero are added to (S × S ) and(s, t)  (u, v ) = if t ≡ u then (s, v ) else 

14

K. Emoto, S. Fischer, and Z. Hu

Intuitively, reduce  returns the boundaries of a given sequence of state transitions if they are consecutive (ıif the sequence is empty) and  otherwise.
The aggregator maxprob is the unique semiring homomorphism from (*[X × (S × S )]+, ], ×++ ) to ([0, 1], ↑, ∗)that satisfies5
maxprob *[(x , (s, t))]+ = prob (x , (s, t))

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, and thus, applying Theorem 13 to the specification of maxLikelinessyields an implementation with the total cost O(n|S|4 ) if n denotes the length of an event sequence given as
input. As assignTrans is a monoid homomorphism we can execute it in parallel, say using p processors, whichleads to the run time O((log p + np )|S|4 ). For a given probabilistic model, where S is fixed, the result is alinear-time parallel algorithm. This is in contrast to the specification which, when executed, would generate
an intermediate result of size |S|2n . Interestingly, the derived program is equivalent to a program obtainedby parallelizing the Viterbi algorithm [He88, HC06] using matrix multiplication over a semiring [SI11].

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 non-deterministic choice do notsatisfy 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 secondorder hidden Markov model [He88] where the transition probabilities are based on the past two hidden states,
not only the previous state. If the probability of transitioning to u after the past transition s → t is given as
Ptrans (u | s, t) we can modify the function prob as follows:
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:
5 To avoid confusion, note that the range [0, 1] is the unit interval, that is, the set of all real numbers x such that 0 ≤ x ≤ 1,
not the list of the two elements. Multiplication distributes over ↑ on the unit interval.

Filter-embedding Semiring Fusion for Programming with MapReduce15

assignTrans2 ⊕,⊗ f [x ] = reduce ⊕ [f (x , (s, t, u)) | s ← S , t ← S , u ← S ]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 homomorphismfrom ([(S × S ) × (S × S )], ++) to the finite monoid (((S × S ) × (S × S )) , ). The specification of  is thesame as before but it now compares pairs of states for equality, not states.
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 [HC06]. The specification is the same as the specification of
maxLikeliness apart from the aggregator maxprob k which computes the list of 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:x ↑k y = take k (sort (x ++ y))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, sort sorts descendingly.

6.4. Incremental Refinement
In the previous subsection we have modified some parts of a specification to obtain variations of 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, suchas “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 bya homomorphic predicate.
For the first condition we use the monoid homomorphism count w p into (Mw , +w ) characterized bycount 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 we can define
the predicate fixedTimes which only allows sequences of states that contain a given state s exactly w times:
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 define a monoid
homomorphism after s t into ((Bool × Bool ) , ?) that returns a pair of Booleans that indicate whether theargument list contains the states s and t, or  if t occurs anywhere after s.6 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 atest which only allows sequences of states that do not contain a given state t after s as not ◦ ( ≡) ◦ after s t.
6

(Bool × Bool) = (Bool × Bool)∪{} and ı? = (False, False).

16

K. Emoto, S. Fischer, and Z. Hu

Bin

Bin

Tip

2

Tip

Bin

Tip

1

4

Bin

-3

Tip

Bin

Tip

5

Tip

Fig. 1. Tree with maximum path weight 3 witnessed by the paths [1, 2] and [1, −3, 5]

Since both homomorphisms have finite ranges, we can get linear-time parallel algorithms for the restricted
problems. We can even combine both predicates or add similar conditions such as “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 showthat 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 our generalized theory for problems inwhich the intermediate data structure is a bag of arbitrary algebraic data types.

7.1. Trees as Input Data
The maximum path weight problem [MMHT09] is, given a binary tree, to find the maximum sum along apath from the root to a leaf. The input of this problem is not a list but a node-valued binary tree defined asfollows 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−∞ , ↑, +) thatsatisfies
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:*[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 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 parallelizable conditions given in [MMHT09]. Thus, the derived program is an efficientparallel program.

Filter-embedding Semiring Fusion for Programming with MapReduce

17

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 Xk → D1 → ... → Dlk → D for lk > 0. Here, Di is D itself (the subscript is simply added to countthe number of Ds), and Xk is a type that does not depend on D (and might be a tuple or the unit type ()).
These restrictions limit our generalization to so called regular data types where possible type parameters do
not change in recursive occurrences.
In the rest of this section, we fix the data type D and the functions {φk }nk=1 .
A D-algebra extends 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 Xk → A1 → ... → Alk → A where
Ai = A .
Note that in general we do not assume associativity and identities of ck s.
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 theset of functions {ck }nk=1 is said to be D-distributive over ⊕, if it satisfies the following equation for anyk ∈ {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 )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 the identity ı⊕ of ⊕ is azero of {ck }nk=1 .
An important D-semiring is BD = (*D+, ], {Φk }nk=1 ) where the cross construction operators Φ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 homomorphismfrom BD into every other D-semiring.
Definition 18 (D-Semiring Homomorphism). Given two D-semirings A = (A, ⊕, {ck }nk=1 ) and B =(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 homomorphism from (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 }nk=1 : X → S
that is polymorphic over an arbitrary D-semiring (S , ⊕, {ck }nk=1 ) is called a polymorphic D-semiring generator.
Now we can give generalized versions of our theorems. The generalization of Theorem 8 is as follows.

18

K. Emoto, S. Fischer, and Z. Hu

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 [Wad89].
Now, we proceed to the generalized filter embedding. Similar to the usual semirings, we can build a Dsemiring 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 a D-semiringn(S, ⊕, {ck }nk=1 ), the triple (S E , ⊕E , {cEk }k=1 ) where0(f ⊕E f 0 )e = fe ⊕ feLE(ck a d1 · · · dlk )e =e1 ,...,elk ∈E ck a (d1 )e1 · · · (dlk )elk
c0k a e1 ···elk ≡e

is a D-semiring with (ı⊕E )e = ı⊕ .
Proof. Associativity and commutativity of ⊕E follow from those of ⊕. D-distributivity of {ck }nk=1 and thenproperties of ⊕ guarantee D-distributivity of {cEk }k=1 . The zeroness of ı⊕E is clear 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 Dalgebra homomorphism hom from (D, {φk }nk=1 ) 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 E ok ◦ aggregate hom
Here, aggregate hom is the D-semiring homomorphism from BD to the lifted D-semiring, and postprocess E is
the same as postprocess M 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 of list concatenation. Polymorphic
semiring generators that are expressed as a list homomorphism are only meaningful because the result typeis 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 plausible that all laws of D-algebras arepreserved 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 are preserved as well as laws that are not preserved and argue
intuitively what kinds of laws are preserved in general. A more formal treatment is not in the scope of thispaper.
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

Filter-embedding Semiring Fusion for Programming with MapReduce19

Bin × l x r = Bin × r x l
if the underlying Tree-algebra satisfies tree commutativity. Following the definition of BD specialized toTree, Bin × is defined as Bin × l x r = *Bin v x w | v ← l , w ← r +, and we have the following result.
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 l=Tree commutativity of the free Tree-semiring essentially follows from tree commutativity of the underlying
structure and distributivity of Bin × over bag union.
We can check similarly that the lifted Tree-semiring preserves tree commutativity of the underlying Treealgebras. As an example, consider the lifted Tree-semiring of families of elements in the free Tree-semiringindexed by Bool . We can define the Tree-algebra (Bool , {cBin , cTip }), that checks whether the sum of allnode 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 Treesemiring, we showrxl
l x r = Bin Bool
Bin Bool××
for x = 1, l = (a, b), and r = (c, d ). Similar to Section 5.1 we represent indexed families as tuples. The
first component is the element indexed by False and contains bags of trees with an even sum of node labels.
The second component is the element indexed by True and contains bags of trees with an odd sum of nodelabels.
lxr
Bin Bool×= { 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 ] }×
Bin Bool
(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 preserved by the freeand 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:*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 in this example

20

K. Emoto, S. Fischer, and Z. Hu

is the duplication of the variable x on the left side of the idempotence law which leads to different numbersof bag elements on both sides of the law.
In general, so called linear laws where each variable occurs exactly once (like associativity or commutativitylaws) 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.
Ternary trees [Mat07] provide an example of trees supporting parallelism. They come with so called tree
associativity laws that are used for load balancing. The tree associativity laws are linear and, therefore,
generators expressed as ternary-tree homomorphisms can be used together with our generalized GTA framework.

8. Related Work8.1. Homomorphism-based Parallelization
The research on parallelization via derivation of list homomorphisms has gained great interest since [Ski92,
Col95, GDH96]. The main approaches include the third homomorphism theorem based method [Gor96,
MMM+ 07], the function composition based method [FG94, HTC98, CKHT00], and the matrix multiplication based method [SI11]. Our work is a continued effort in this direction, giving a new approach basedon semiring homomorphisms, which is in sharp contrast to the existing work based on monoid homomorphisms. By introducing bags of lists as well as semirings and the GTA form, our method eases defining
effectively-parallelizable specifications for practical problems. This is illustrated with the knapsack problem,the discussed statistical problems, and querying problems, because the GTA form with bag of lists is a natural specification pattern for these combinatorial problems. Basically, specifications of these problems are toocomplex to be handled by the aforementioned approaches, which cannot derive efficient parallel programs forproblems like the knapsack problem and the statistical problems we discuss. Users of previous approaches
are required to make parallelizable sequential specifications, but such specifications for these problems arealmost equivalent to the efficient programs our proposed method derives. Thus, the previous approaches
cannot directly help users to solve problems such as those given in this paper. However, previous approaches
are still useful to build a parallelizable GTA specification which requires its components (generators andpredicates) to be parallel programs. We can use the techniques to get parallel versions from their sequential
specifications, which eases development of GTA specifications.
There has been a lot of work about using MapReduce to parallelize various kinds of problems [LD10].
Some formal work has been devoted to the study of a computation model of MapReduce (compared to
the PRAM model of computation) [KSV10] and a functional model of MapReduce [Läm08]. However, little
work has been done on 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 [GLPJ93,
TM95] which is based on a free theorem [Wad89] and is practically useful for optimization of sequential
programs. Different from the traditional shortcut deforestation focusing on the data constructors of theintermediate data structure that are passed from one function to another, our shortcut fusion focuses on thesemiring operations in the intermediate data structure. It is this semiring structure that allows for flexible
rearrangement of computation for efficient parallel execution.

8.3. Semiring-based Computation
Kohlas and Wilson [KW08] studied semiring-induced valuation algebras and succeeded in giving uniform
formalization of many problems in various fields. However, their algorithm requires a cost exponential to
the size of the largest constraint, so that it cannot deal with global conditions such as “the number of items

Filter-embedding Semiring Fusion for Programming with MapReduce21

with weight less than ten is at most three” in the knapsack problem. Our filter-embedding would be usefulto add global constraints to the framework.
Goodman [Goo99] extended the CYK parsing algorithm by substituting various semirings for the Boolean
semiring, so that one can reuse the algorithm for various computations such as counting the number ofparsings, computing the probability of generating the given string, and finding the best k-parsing. We canreuse his semirings in our GTA form for computing similar variations.
Bistarelli et al. [BMR97, BMR01, BMRS10] proposed a framework for semiring-based constraint logic programming, which extends the logic programming with semiring-based soft constraints, and studied its semantics and decidability. One problem of their framework is that, given a complex problem, one needs todesign a system of recursive equations at once. Our method can decompose the development into design ofthe main simple algorithm and design of filters, which is much easier than the direct development. Larrosa
et al. [LORC10] proposed a similar extension to propositional logic programming.
Abdali and Saunders [Abd93, AS85] 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. Although these are not directly related to ourapplications, they are useful for many problems in computer science and operations research. The key pointof their algorithm is that the ∗ operator can be 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 programsin 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 efficientalgorithm by adding homomorphic filters in the “naive world” which is easier than modifying it in the “efficient world”. Our new framework is not only theoretically interesting, but also practically significant insolving 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 ourapproach generalizes existing techniques and provides a common framework to express them. Our approachis expected to be applicable to typical “big-data” problems, like finding patterns in historical financial data,and plan to investigate such applications as future work.
Here, we give some general remarks on designing generators, aggregators and predicates to build GTA
specifications. We summarize different design possibilities without formal treatment of how they work.
Standard functions like segs for generating all segments (ranges), intis for all initial-segments (prefixes), andtails for all tail-segments (suffixes) are polymorphic semiring generators [Gor96, Gor97, Bir87, BdM96]. We
can use these generators to develop GTA specifications, e.g., for query problems of ranges and financial data
analysis [ACK01, Zan92]. Although it is, in general, difficult to give direct definitions of desired polymorphic
semiring generators, there is a principled approach. We can design a custom generator by defining filters that
discard unnecessary items from a bag of items produced by a standard generator. It is worth noting thatsome dynamic-programming algorithms are polymorphic over semirings [Goo99]. Therefore, we may reuse
them as generators in GTA specifications, in which we can utilize previous results [Gor96, MMM+ 07, FG94,
HTC98, CKHT00, SI11] to parallelize them.
Various semirings [Goo99] can be used as aggregators of GTA specifications. To count the number of items
passing through the tests, we can use an aggregator count that is the semiring homomorphism to the semiring(Z, +, ∗) with count *[a ]+ = 1. To solve combinatorial optimization problems such as the knapsack problem,
we often want to take the minimum or maximum of sums of items. In this case, we can use the semiring(Z∞ , ↓, +) or (Z−∞ , ↑, +) as seen in Section 4. Similarly, to solve statistical optimization problems suchas the one in Section 6.1, we can use the similar semiring ([0, 1], ↑, ∗). For these semirings, we can build
extended semirings to compute solutions as well as the optimal values, as seen in Sections 6.2 and 6.3. In

22

K. Emoto, S. Fischer, and Z. Hu

addition, we can generalize these semirings for various orderings: given a total order  on a given set S anda monotonic, associative addition ⊕ such that a  b ⇒ (a ⊕ c)  (b ⊕ c) ∧ (c ⊕ a)  (c ⊕ b), we canconstruct the semiring (S , ↓ , ⊕) in which a ↓ b = if a  b then a else b.
The most difficult task for programmers specifying GTA algorithms is the design of predicates for filtering,
since basic generators and aggregators can be reused for many problems. To guarantee the efficiency of
programs derived by our calculation theorems, a user has to design a predicate based on a finite monoid, andreaders might worry about how onerous this requirement is. One approach to satisfying the requirement isdesigning a homomorphism to an infinite monoid first and then limiting its range, as we did in Section 5.1.
As another approach to designing a predicate to a finite monoid, we can use the fact that a finite monoid
can be derived from a finite automaton. Thus, programmers can use a regular expression or monadic second
order logic expression [HJJ+ 95, Tho90] instead of defining a predicate directly. For example, an additional
condition ”we cannot choose items K and J at the same time” to the knapsack problem can be specified
by a regular expression (. ∗ K. ∗ J. ∗ |. ∗ J. ∗ K.∗) composed with the negation function not. Since a derived
monoid may have redundant elements, it is desirable to develop an optimization mechanism to reduce such
redundancy, which is part of our future work.
Moreover, we plan to implement the developed programming theory as a domain specific language or alibrary, for example upon Hadoop [Whi09], so that typical MapReduce problems can be tackled using our
GTA approach. Our theorems can be easily mechanized because of their simple calculational form.

References[Abd93][ACK01][AS85][BdM96][Bir87][Bir98][BMR97][BMR01][BMRS10][But10][Car79][CKHT00][Col95][Con71][DG08][Emo11][FG94][GDH96][GKT07][GLPJ93][GMV84][Goo99][Gor96]

S. Kamal Abdali. Parallel computations in *-semirings. In Klaus Fischer, Philippe Loustaunau, Jay Shapiro,
Edward Green, and David Farkas, editors, Computational Algebra, volume 151 of Lecture Notes in Pure andApplied Mathematics, pages 1–13. CRC Press, 1993.
Saswat Anand, Wei-Ngan Chin, and Siau-Cheng Khoo. Charting patterns on price history. In Proceedings of thesixth ACM SIGPLAN international conference on Functional programming, ICFP ’01, pages 134–145. ACM, 2001.
S. Kamal Abdali and B. David Saunders. Transitive closure and related semiring properties via eliminants. Theoretical Computer Science, 40:257–274, 1985.
Richard Bird and Oege de Moor. Algebra of Programming. Prentice Hall, 1996.
R. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete
Design, pages 5–42. Springer-Verlag, 1987.
Richard Bird. Introduction to Functional Programming using Haskell. Prentice Hall, 1998.
Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization.
Journal of ACM, 44:201–236, 1997.
Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint logic programming: syntax andsemantics. ACM Transactions on Programming Languages and Systems, 23:1–29, 2001.
Stefano Bistarelli, Ugo Montanari, Francesca Rossi, and Francesco Santini. Unicast and multicast QoS routing
with soft-constraint logic programming. ACM Transactions on Computational Logic, 12:5:1–5:48, 2010.
Peter Butkovič. Max-linear Systems: Theory and Algorithms. Springer-Verlag, 2010.
Bernard Carre. Graphs and Networks. Clarendon Press, 1979.
Wei-Ngan Chin, Siau-Cheng Khoo, Zhenjiang Hu, and Masato Takeichi. Deriving parallel codes via invariants. In
Static Analysis, 7th International Symposium, SAS 2000, volume 1824 of LNCS, pages 75–94. Springer, 2000.
Murray Cole. Parallel programming with list homomorphisms. Parallel Processing Letters, 5(2):191–203, 1995.
John Horton Conway. Regular Algebra and Finite Machines. Chapman & Hall, 1971.
Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of
the ACM, 51:107–113, 2008.
Kento Emoto. An algebraic approach to efficient parallel algorithms for nested reductions. Technical Report
METR2011–01, Department of Mathematical Informatics, Graduate School of Information Science and Technology,
University of Tokyo, 2011.
Allan L. Fisher and Anwar M. Ghuloum. Parallelizing complex scans and reductions. In Proceedings of the ACM
SIGPLAN 1994 conference on Programming language design and implementation (PLDI ’94), pages 135–146.
ACM, 1994.
Z.N. Grant-Duff and P. Harrison. Parallelism via homomorphism. Parallel Processing Letters, 6(2):279–295, 1996.
Todd J. Green, Grigoris Karvounarakis, and Val Tannen. Provenance semirings. In Proceedings of the twenty-sixth
ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’07, pages 31–40, New
York, NY, USA, 2007. ACM.
Andrew Gill, John Launchbury, and Simon L. Peyton Jones. A short cut to deforestation. In Conference on
Functional Programming Languages and Computer Architecture, pages 223–232, 1993.
Michel Gondran, Michel Minoux, and Steven Vajda. Graphs and algorithms. John Wiley & Sons, Inc., 1984.
Joshua Goodman. Semiring parsing. Computational Linguistics, 25:573–605, 1999.
Sergei 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.

Filter-embedding Semiring Fusion for Programming with MapReduce[Gor97]23

Sergei Gorlatch. Optimizing compositions of scans and reductions in parallel program derivation. Technical Report
MPI–9711, Universität Passau, 1997.
[Haz02]Michiel Hazewinkel, editor. Encyclopaedia of Mathematics. Springer-Verlag, 2002.
[HC06]
Tan-Jan Ho and Bor-Sen 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.
[He88]
Yang 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.
[HJJ+ 95]
Jesper G. Henriksen, Jakob L. Jensen, Michael E. Jorgensen, Nils Klarlund, Robert Paige, Theis Rauhe, andAnders Sandholm. Mona: Monadic second-order logic in practice. In Tools and Algorithms for the Construction
and Analysis of Systems, volume 1019 of LNCS, pages 89–110. Springer, 1995.
[HTC98]
Zhenjiang Hu, Masato Takeichi, and Wei-Ngan 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.
[HYT05]
Zhenjiang Hu, Tetsuo Yokoyama, and Masato Takeichi. Program optimization and transformation in calculational
form. In Summer School on Generative and Transformational Techniques in Software Engineering (GTTSE 2005),
2005.
[KSV10]Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedingsof the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 938–948. SIAM,
2010.
[KW08]
J. Kohlas and N. Wilson. Semiring induced valuation algebras: Exact and approximate local computation algorithms. Artificial Intelligence, 172:1360–1399, 2008.
[Läm08]
Ralf Lämmel. Google’s mapreduce programming model - revisited. Science of Computer Programming, 70(1):1–30,
2008.
[LD10]
Jimmy Lin and Chris Dyer. Data-Intensive Text Processing with MapReduce. Morgan and Claypool Publishers,
2010.
[LHM11]
Yu Liu, Zhenjiang Hu, and Kiminori Matsuzaki. Towards systematic parallel programming over mapreduce. In
Euro-Par 2011 Parallel Processing, volume 6853 of LNCS. Springer, 2011.
[Lis11]
MapReduce Application Paper List. http://www.mendeley.com/groups/1058401/mapreduce-applications/papers/.
2011.
[LORC10] Javier Larrosa, Albert Oliveras, and Enric 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.
[Mat07]
Kiminori Matsuzaki. Parallel Programming with Tree Skeletons. PhD thesis, Graduate School of Information
Science and Technology, University of Tokyo, 2007.
[MMHT09] Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, and Masato Takeichi. The third homomorphism theoremon trees: downward & upward lead to divide-and-conquer. In Proceedings of the 36th annual ACM SIGPLANSIGACT symposium on Principles of programming languages, POPL ’09, pages 177–185. ACM, 2009.
[MMM+ 07] Kazutaka Morita, Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, and Masato 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.
[SI11]
Shigeyuki Sato and Hideya Iwasaki. Automatic parallelization via matrix multiplication. In Proceedings of the
32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI ’11), pages 470–
479. ACM, 2011.
[Ski92]D. B. Skillicorn. The Bird-Meertens Formalism as a Parallel Model. In NATO ARW “Software for Parallel
Computation”, 92.
[Tar81]
Robert Endre Tarjan. A unified approach to path problems. Journal of ACM, 28:577–593, 1981.
[Tho90]Wolfgang 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.
[THT98]Akihiko Takano, Zhenjiang Hu, and Masato Takeichi. Program transformation in calculational form. ACM Computing Surveys, 30(3), 1998.
[TM95]
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.
[Wad89]
Philip 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.
[Whi09]Tom White. Hadoop: The Definitive Guide. O’Reilly Media, 2009.
[Zan92]
H. Zantema. Longest segment problems. Science of Computer Programming, 18:39–66, 1992.