Lightweight Fusion by Fixed Point Promotion ∗(the author’s version)
Isao Sasano †Atsushi Ohori

Research Institute of Electrical Communication
Tohoku University{ohori, sasano}@riec.tohoku.ac.jp

Abstract

1. Introduction

This paper proposes a lightweight fusion method for general recursive function deﬁnitions. Compared with existing proposals, ourmethod has several signiﬁcant practical features: it works for general recursive functions on general algebraic data types; it does notproduce extra runtime overhead (except for possible code size increase due to the success of fusion); and it is readily incorporated
in standard inlining optimization. This is achieved by extending
the ordinary inlining process with a new fusion law that transforms a term of the form f ◦ (fix g.λx.E) to a new ﬁxed pointterm fix h.λx.E 0 by promoting the function f through the ﬁxed
point operator. This is a sound syntactic transformation rule thatis not sensitive to the types of f and g. This property makes our
method applicable to wide range of functions including those withmulti-parameters in both curried and uncurried forms. Although
this method does not guarantee any form of completeness, it fuses
typical examples discussed in the literature and others that involve
accumulating parameters, either in the foldl-like speciﬁc forms
or in general recursive forms, without any additional machinery. In
order to substantiate our claim, we have implemented our method
in a compiler. Although it is preliminary, it demonstrates practicalfeasibility of this method.

Fusion is a program optimization technique to combine two adjacent computations, where one produces a result which is thenprocessed by the other, by “fusing” two successive computation
steps (function applications or loops) into one, yielding a more
efﬁcient program. In functional programming, this technique has
the additional signiﬁcance that it suppresses construction of intermediate data structures, such as lists and other inductively deﬁned data structures. Burstall and Darlington [1] were perhaps theﬁrst to study this optimization in functional programming and presented a general strategy for generating efﬁcient recursive programs
through fold/unfold transformation. Wadler [23] observed that thisoptimization can be carried out systematically to eliminate intermediate trees altogether and showed the “deforestation” theorem
stating that every composition of functions in a certain restricted
form can be effectively fused into a single function. Since this seminal observation, a series of investigations have been done towards
establishing a general method for program fusion.
One direction toward developing a practical fusion method is torestrict the target functions to be of speciﬁc forms. Gill, Launchbury and Peyton Jones [6] presented the “short cut” deforestation
law stating that if both the producer function and the consumer
function are written in a speciﬁc form then they are fused together.
Since this rule is a simple local transformation, it is easily incorporated in an optimizing compiler. This approach has been generalized to user-deﬁned recursive data types [19, 22].
One major limitation of these approaches is that they do not deal
with general recursive functions. While it is certainly a valid claimthat “lucid” or compositional style programming has the advantages of clarity and modularity, one often has to deﬁne data structures speciﬁc to the problem domain and to write specialized functions using general recursion. In serious practical software development, this tendency is predominant. Even in the GHC compiler
for Haskell, which implements the rule for short cut fusion [17],build/cata style code appears to be minority compared with generalrecursive functions. Since the general idea underlying deforestation
is equally applicable to general recursive deﬁnitions, it is highly desirable to develop a fusion method that works directly on generalrecursive functions.
Launchbury and Sheard [12] proposed one solution to this problem by developing an algorithm to transform a recursive function
deﬁnition into a program in build/cata form. The resulting programis then fused by build/cata laws. Chitil [4] proposed a type based
approach to obtaining build forms from general recursive deﬁnitions. These approaches are conceptually elegant, but their practical feasibility is not clear. A key step in their development is torepresent a term that constructs a data structure as a higher-orderfunction using the technique of representing term algebra (induc-

Categories and Subject Descriptors D.3.4 [Programming Languages]: Processors—Compilers, Optimization; D.3.4 [Programming Languages]: Language Classiﬁcations—Applicative (functional) languages; F.3.3 [Logics and Meanings of Programs]:
Studies of Program Constructs—Program and recursion schemes
General Terms Languages, Theory
Keywords Fusion, inlining, ﬁxed point∗ This research was partially supported by the Japan MEXT (Ministryof Education, Culture, Sports, Science and Technologies) leading projectof “Comprehensive Development of Foundation Software for E-Society”
under the title “dependable software development technology based on
static program analysis.”† The second author was also partially supported by Grant-in-Aid for Young
Scientists (B), 16700029 from the Ministry of Education, Culture, Sports,
Science and Technology.

c°ACM(2007). This is the author’s version of the work. It is posted here bypermission of ACM for your personal use. Not for redistribution. The deﬁnitive version will be/was bublished in: Proceedings of ACM POPL’07 (the ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages), January 17–19, 2007, Nice, France.

1

tive types) in the second-order lambda calculus. For example, an
efﬁcient and compact list term 1:2:nil (written in Haskell syntax) is temporarily “heated up” to a lambda term λc.λn.c 1 (c 2 n).
It is questionable whether or not these costly abstractions should
all be fused away in an optimizing compiler for a language thatinvolves various features over pure lambda expressions.
Another limitation of the short-cut fusion approach is that itis restricted to functions of single argument. In practical softwaredevelopment, functions are often written in efﬁcient tail recursive
form using accumulating parameters, or they may take various
extra parameters required by the problem domain. Unfortunately,short-cut fusion [6] and its extension [22, 21] do not scale up to
those functions.
In order for a fusion method to become a practical optimization method for an optimizing compiler, it should ideally have thefollowing features.

body using (AppDist) and other reduction axioms. We refer to thistransformation rule as (FixPromote).
This remarkably simple process can fuse various general recursive functions, including those involving accumulating parameters
or tail recursive functions such as foldl without resorting to any
heuristics. Since this process only involves two simple deterministic transformation rules, it can easily be incorporated in any inlining process. Moreover, it is robust enough to scale up to practical optimizing compiler of a polymorphic functional language. We
therefore claim that the resulting fusion algorithm is a practical one
that satisﬁes the desired criteria mentioned above. In order to substantiate this claim, we have implemented the algorithm in a prototype compiler for a full scale functional language, and have tested
various examples. The results verify that our method fuses typicalexamples including those with extra parameters. The implementation is made available through the Internet for downloading. See
Section 6 for the details. We should note that the implementation
is a preliminary one only for testing the behavior of the proposed
method, and does not intend to be a part of a practical optimization
phase.
The rest of the paper is organized as follows. Section 2 informally presents our lightweight fusion method through examples.
Section 3 deﬁnes a simple functional language, gives our two new
fusion rules, and proves the soundness of the two rules. Section 4
presents the fusion algorithm. Section 5 demonstrates the power of
the algorithm through various examples. Section 6 descries our experimental implementation. Section 7 shows some general benchmark results and their analysis. Section 8 discusses related work.
Section 9 concludes the paper.

1 It is simple and fully automatic so that it can be easily embedded
in an optimizing compiler.
2 It does not introduce any extra runtime overhead.
3 It works for general recursive functions with multiple parameters (including accumulating parameters and others).
4 It works for general user-deﬁned data types.
5 It fuses all fusable functions.
Development of such a method is the ultimate goal of the subject.
However, if we weaken the requirement by replacing the last condition of completeness to
5’ it works for expected typical cases,

2. Overview of Lightweight Fusion

then we can indeed develop such a system. An attempt is made inthis paper to develop such a fusion method.
Previous researches have mainly focused on algebraic (or categorical) properties of generic functions on data structures for deducing general fusion patterns. Some notable examples include thepromotion theorem for foldr [13] and its generalizations [14, 19],
short-cut deforestation for foldr and build [6] and its generalization in calculational form [22], destroy and unfold fusion [21],and more recent algebraic fusion based on monoid homomorphism[11]. Instead of pursuing this direction, we follow the original approach of fold/unfold transformation [1] and develop a method tofuse two recursive function deﬁnitions directly through unfolding,simpliﬁcation (beta-reduction), and folding (generating new recursive deﬁnitions). The crucial step in developing a practical fusion
method is to ﬁnd deterministic and simple, yet powerful rules tocontrol the fusion process.
By analyzing various fusable recursive functions, we have discovered the following simple yet effective transformation strategy.
Let f = fix f.λx.Ef and g = fix g.λx.Eg be recursive function
deﬁnitions. Under these bindings, we can transform the composition f ◦ g to obtain a fusion of the two as follows.

To illustrates our method, let us ﬁrst consider the following simple
example.
let mapsq =fix mapsq.
λL.case L ofnil => nil,cons(h,t) => cons(h*h, mapsq t)
sum = fix sum.λL.case L ofnil => 0,cons(h,t) => h + sum t
in · · · sum (mapsq E) · · · end
On detecting an application sum (mapsq E) of a composition of
two recursive functions, we attempt to generate a new recursivedeﬁnition starting from the composition function:
λx.sum (mapsq x)
where the subterms that are transformed in the subsequent step areunderlined.
We ﬁrst inline the lambda body of the inner function mapsq.

1. Inline the body of g to obtain f ◦ λx.Eg , which is beta reduced
to λx.f Eg .

λx.sum (case x ofnil => nil,cons(h,t) => cons (h*h, mapsq t))

2. Transform f Eg to Eg0 by distributing the function symbol f to
all the tail positions of Eg .

Inlining is not recursive, and hence mapsq in the body refers to theoriginal deﬁnition.
Next, we apply the (AppDist) rule: we distribute the function
name sum to all the tail positions of its argument term.

3. Inline f once in Eg0 and simplify the term to obtain a term Ef,g .
4. Replace the occurrences of f ◦ g in Ef,g by a new function
name f g and generate a new binding f g = fix f g.λx.Ef g .

λx.case x ofnil => sum nil,cons(h,t) => sum (cons (h*h, mapsq t))

Since this process promotes the function f through the ﬁxed point
operator, we call it ﬁxed point promotion.
Step 2 is represented by a term transformation axiom, which wecall (AppDist). The entire step is represented by a transformation
rule that produces a new ﬁxed point term (Step 4) by reducing theWe then inline the lambda body of sum once, and simplify the
resulting term.

2λx.case x ofnil => 0,cons(h,t) => h*h + sum (mapsq t)

We note that the process outlined above is simple, terminatingand entirely automatic, so that it can easily be embedded in thestandard inlining process. Moreover, it relies neither on any heuristics nor on any special properties of data types or functions. It istherefore applicable to general function deﬁnitions manipulatinguser-deﬁned data types.

If the resulting term contains the composition sum (mapsq )that we are fusing, then we create a new recursive function namesum mapsq and substitute it for the composition.
fix sum mapsq.λx.case x ofnil => 0,cons(h,t) => h*h + sum mapsq t

3. Fixed Point Promotion Laws and its Soundness
This section presents the new fusion laws on which our method isbased, and shows their soundness.

This entire process is an application of (FixPromote).
The successful application of (FixPromote) indicates that thecomposition of the two functions is fused into a new recursivefunction. If this happens, then we put the new deﬁnition after thedeﬁnitions of sum and mapsq, and replace all the occurrences of thecomposition sum ◦ mapsq appearing in the rest of the programby sum mapsq. If there is no reference to the original functions
sum and mapsq then their deﬁnitions are removed by dead code
elimination, and the following program is obtained.

3.1

The source language and some notations

We consider the following set of lambda terms.
M

let sum mapsq =fix sum mapsq.
λx.case x ofnil => 0,cons(h,t) => h*h + sum mapsq t
in · · · sum mapsq E · · · endpx | λx.M | fix f.M | M M
C(M, . . . , M )case M of p => M, . . . , p => M
let x = M in M end
C(x, . . . , x)fix f.M denotes the ﬁxed point of the functional λf.M and represents a recursive function term. C(M, . . . , M ) is a data constructor
term for algebraic (user deﬁned) data types. We sometimes write
let x1 = M1 , . . . , xn = Mn in M end for an abbreviation of anested let expression. If M and N are terms, we write M {N/x}for the term obtained by the usual capture free substitution of N forx in M . In addition to this core syntax, in examples, we use terms
containing primitive operations.
For this language, we assume the usual bound variable convention, i.e., the set of bound variables are pairwise distinct and are
different from free variables.
A context, ranged over by C, is deﬁned by the following syntax

This process is easily extended to functions of multiple parameters. For example, suppose sum is deﬁned in tail recursive form as
follows.
let mapsq = ...
sum = fix sum.λL.λS.
case L ofnil => S,cons(h,t) => sum t (S + h)
in · · · sum (mapsq E) 0 · · · endCWe start with λx.λS.sum (mapsq x) S and ﬁrst inline mapsq.
λx.λS.sum (case x ofnil => nil,cons(h,t) => cons (h*h, mapsq t)) S
We then distribute the application context sum
positions.

::=
|
|
|
::=

::=
|
|
|

[ ] | x | λx.C | fix f.C | C C
C(C, . . . , C)case C of p => C, . . . , p => C
let x = C in C end

where [ ] is a “hole”. If we need to identify each hole differently,
we use some index i and write [ ]i . A context C generated by thisgrammar contains zero or more holes. In what follows, we let C
range only over those contexts that contain one or more holes. We
write C[Mi ]i for the term obtained from C by ﬁlling each hole [ ]iof C with (different) Mi , and write C[M ] for the term obtained
from C by ﬁlling all the holes of C with the same M . We also write
C{N/x} for the context obtained from the capture free substitutionof N for x in C. In particular, C{N/x}[Mi ]i denotes the term
obtained by ﬁlling each hole [ ]i of the context C{N/x} with Mi .
A tail context, ranged over by T , is deﬁned by the following
syntax.

S to all the tailλx.λS.case x ofnil => sum nil S,cons(h,t) => sum (cons (h*h, mapsq t)) S
Next, we inline sum once and simplify.
λx.λS.case x ofnil => S,cons(h,t) => sum (mapsq t) (S + h*h)TFinally, we replace λx.λS.sum (mapsq x) S with a new function name sum mapsq and obtain the following program (after deadcode elimination).

::=
|
|

[]
case M of p => T , . . . , p => T
let x = M in T end

A tail context T is a term with “holes” at its all tail positions. We
write T [Mi ]i for the term obtained by ﬁlling each hole [ ]i in Twith Mi .

let sum mapsq =fix sum mapsq.λx.λS.
case x ofnil => S,cons(h,t) => sum mapsq t (S + h*h)
in · · · sum mapsq E 0 · · · end

3.2

Fusion laws for single parameter functions

We assume the standard call by name semantics. Later in Section 6,
we shall comment on applying our fusion method to strict languages.

This transformation process also extends to uncurried multiargument functions.

3Our ﬁrst fusion law is “apply distribution” deﬁned below.

We further assume the standard denotational semantics based on
the standard domain theory, where the ﬁxed point construct denotes
the least ﬁxed point in the continuous function space.

(AppDist) f T [Mi ]i =⇒ T [f Mi ]i

T HEOREM 2. (FixPromote) is sound for any strict f .

By this reduction, (static) evaluation can continue. This rule pulls
out the head term of a case expression. For this rule to be sound, itis therefore necessary for f to be strict. Note that this condition isenforced in short-cut fusion.

Proof. In the following argument, we implicitly identify termswith their denotations in the domain theory. Since the denotationof fix h.(C{fix g.M/g})[h] is the least ﬁxed point, Lemma 1
establishes the following.

T HEOREM 1. (AppDist) is sound for any strict f .

f ◦ fix g.M w fix h.(C{fix g.M/g})[h]Proof. Here we assume a standard environment-style denotationalsemantics [[M ]]η of lambda term M under environment η, and show
the semantic equation:

To show the converse, let F = λw.C{fix g.M/g}[w], and write
F n (x) for F (F · · · (F x) · · · ). We ﬁrst show the following in| {z }n timesequation for all n by induction on n.

[[f T [Mi ]i ]]η = [[T [f Mi ]i ]]η
The following argument does not depend on speciﬁc property ofthe semantic deﬁnition.
The proof is by simple induction on the structure of thetail context T . The base case is the identity. Suppose T =case M0 of · · · , pk => Tk , · · · . Then

F n (⊥) w f ◦ ((λg.M )n (⊥))
This holds for n = 0 since f ◦ ⊥ = ⊥. The induction step is asfollows.
F n+1 (⊥) = C{fix g.M/g}[F n (⊥)]
w C{fix g.M/g}[f ◦ ((λg.M )n (⊥))]
w C{(λg.M )n (⊥)/g}[f ◦ ((λg.M )n (⊥))]= C[f ◦ g]{(λg.M )n (⊥)/g}= (f ◦ M ){(λg.M )n (⊥)/g}= f ◦ ((λg.M )((λg.M )n (⊥)))= f ◦ ((λg.M )n+1 (⊥))

T [f Mi ]i = case M0 of · · · , pk => Tk [f Mjk ]jk , · · ·Suppose [[f T [Mi ]i ]]η 6= ⊥. Since f is strict, [[T [Mi ]i ]]η 6= ⊥.
Suppose [[M0 ]]η = Ci (v1 , . . . , vn ) for some Ci such that pi =Ci (x1 , . . . , xn ). Then we have the following.
[[f (case M0 of · · · , pi => Ti [Mji ]ji , · · · )]]η= [[f Ti [Mji ]ji ]]η ∪ {x1 7→ v1 , . . . , xn 7→ vn }= [[Ti [f Mji ]ji ]]η ∪ {x1 7→ v1 , . . . , xn 7→ vn }(by induction hypothesis)= [[case M0 of · · · , pi => Ti [f Mji ]ji , · · · ]]η

From the above inequality, we have the following.
fix h.(C{fix g.M/g})[h]The cases other than [[M0 ]]η 6= Ci (v1 , . . . , vn ) are trivial in an
untyped semantics, or vacuous in a typed semantics.
The case for let x = M in T end is simpler and omitted. 2
Our main law for ﬁxed point promotion is the following inference rule.

=

3.3

+

Fusion laws for multiple parameter functions

1. The outer f is a two parameter curried function whose ﬁrst
argument is the target of fusion.
2. The outer f is a two parameter uncurried function whose ﬁrst
argument is the target of fusion.
For the curried case, the law (AppDist) and (FixPromote) become (AppDist-c) and (FixPromote-c) as shown in Figure 1. For
these laws, we can show the following.

fix g.M = M {fix g.M/g}
and we write M ≡ N for the syntactic and deﬁnitional equality.

T HEOREM 3. (AppDist-c) is sound for any function f that is strict
with respect to the ﬁrst argument, i.e. f ⊥ y = ⊥.

L EMMA 1. If f ◦ M = C[f ◦ g] then f ◦ fix g.M is a ﬁxed pointof the functional λh.(C{fix g.M/g})[h].

L EMMA 2. If f (M x) y = C[f (g M1i ) M2i ]i then

Proof. Assume f ◦ M = C[f ◦ g]. We have the following.
≡
=
≡
≡
=
=
≡
=

2

Both of (AppDist) and (FixPromote) extend systematically tomulti-parameter functions. The case where the inner g is a multiparameter function is straightforward. Here we only show the following two cases.

f ◦ M =⇒ C[f ◦ g]f ◦ fix g.M =⇒ fix h.(C{fix g.M/g})[h]where =⇒ represents one or more applications of the transformation relation =⇒ generated by our fusion laws (together with standard simplifying reduction rules.)To show the soundness of this rule, we ﬁrst show a generalequational property. We write M = M 0 for the β equality relation
with the following rule for fix

f ◦ fix g.M

t {F n (⊥) | n ≥ 0}
t {f ◦ (λg.M )n (⊥) | n ≥ 0}f ◦ t {(λg.M )n (⊥) | n ≥ 0}
(since f and ◦ are continuous)f ◦ fix g.M

This concludes the proof.

+(FixPromote)=w=

λx.λy.f ((fix g.M ) x) y
is a ﬁxed point of λh.λx.λy.C[h M1i M2i ]i {fix g.M/g}.

λx.f ((fix g.M ) x)
λx.f ((M {fix g.M/g}) x)
λx.(f (M x)){fix g.M/g}(f ◦ M ){fix g.M/g}
C[f ◦ g]{fix g.M/g} (by assumption)
C[f ◦ fix g.M ]{fix g.M/g}C{fix g.M/g}[f ◦ fix g.M ](λh.C{fix g.M/g}[h])(f ◦ fix g.M ) 2

For the uncurried case, the law (AppDist) and (FixPromote)become (AppDist-u) and (FixPromote-u) as shown in Figure 1. Inthese deﬁnitions, we have used extended lambda terms: λ(x, y).M
for two-parameter lambda abstraction and M (M1 , M2 ) for twoparameter lambda application. For these laws, we can show thefollowing.
T HEOREM 4. (AppDist-u) is sound for any function f that is strict
with respect to the ﬁrst argument, i.e. f (⊥, y) = ⊥.
4

(AppDist-c) f T [Mi ]i x =⇒ T [f Mi x]i(FixPromote-c)f (M x) y =⇒ C[f (g M1i ) M2i ]iλx.λy.f ((fix g.M ) x) y =⇒ fix h.λx.λy.C[h M1i M2i ]i {fix g.M/g}(AppDist-u) f (T [Mi ]i , x) =⇒ T [(f Mi , x)]i
(FixPromote-u)f (M x, y) =⇒ C[f (g M1i , M2i )]iλ(x, y).f ((fix g.M ) x, y) =⇒ fix h.λ(x, y).C[h (M1i , M2i )]i {fix g.M/g}
Figure 1. Fusion Laws extended to Multi-parameter Functions

L EMMA 3. If f (M x, y) = C[f (g M1i , M2i )]i then

• For all the other terms, the algorithm performs standard inlining

and simpliﬁcation.

λ(x, y).f ((fix g.M ) x, y)

To deﬁne the algorithm, we introduce some notations. We use
f, g for variables bound to functions. We let µ range over binding
environments, which is a mapping from variables to terms. We
write µ{x 7→ M } for the environment obtained from µ by adding
the binding {x 7→ M }, and write µ|x for the environment obtained
from µ by deleting the entry of x. We let η range over fusion
environments, which is a mapping from pairs of variables to oneof the following results of fusion attempts.

is a ﬁxed point of λh.λ(x, y).C[h (M1i , M2i )]i {fix g.M/g}.
Theorems 3, 4 and Lemmas 2, 3 can be proved similarly tothe corresponding proofs of Theorem 1 and Lemma 1. We expectthat semantic correctness of these generalized lows can be shown
similarly to the proof of Theorem 2.
Note that it is straightforward to generalize these results to thecases with functions having more than two parameters. Our fusion
algorithm shown in Section 4 and our implementation described in
Section 6 treat general multi-parameter cases.

4.

• Undeﬁned : fusion has never been tried for the pair.
• Failed : fusion has failed for this pair.
• Succeeded M : fusion has succeeded for the pair with the fused

The Lightweight Fusion Algorithm

function term M .

We now develop a lightweight fusion algorithm by embedding
the fusion mechanism explained above in an inlining process. The
strategy is summarized below.

• Inserted : fusion has succeeded and the binding has alreadybeen inserted as a binding in some let expression.
We write η{(f, g) 7→ M } for the environment obtained from ηby adding the binding {(f, g) 7→ M }. Under the bound variable
convention for terms, both a variable and a pair of variables areglobally unique and therefore µ{x 7→ M } and η{(f, g) 7→ M }are always well deﬁned. We adopt the convention that the new fused
function name for a pair f ◦ g is f g (determined from f, g), andwe do not record this name in a fusion environment.
The lightweight fusion algorithm is now deﬁned as a function
F [[ ]] of the following functionality.

• The algorithm recursively evaluates the input term using a bind-ing environment.
• In order to suppress repeated fusion computations, the algo-rithm also maintains a fusion environment that records the results of previous fusion attempts for pairs of variables that arebound to recursive functions.
• When it encounters a function composition f ◦ g, the algorithm

ﬁrst checks in the binding environment whether both f and g
are bound to recursive functions. If this is the case then thealgorithm performs the following actions depending on the pasthistory of the pair (f, g) recorded in the fusion environment.

F [[M ]] η µ = (M 0 , η 0 )In order to avoid notational complication, we give the deﬁnitionof F [[ ]] for one-parameter functions, and explain the necessary
extensions for the multi-parameter case later.
The algorithm is given in Figure 2 and 3. It only shows thecases relevant to fusion. The other cases are simple recursive
evaluation as in ordinary inlining. The algorithm uses the subalgorithms fusion and dist. The function fusion is for fusing tworecursive functions; fusion (f, λx.Mf ) (g, λx.Mg ) µ η tries tofuse f and g in the expression λx.f (g x) under the bindings{f 7→ fix f.λx.Mf , g 7→ fix g.λx.Mg } according to the method
described in Section 3. The substitution {λx.Mf /f } used in thedeﬁnition of fusion indicates that f is inlined once in F[[ ]]. The
pattern C[f (g Mi )]i used in case branches in fusion indicates thata term of the form f (g M ) is replaced by f g M each time F[[ ]]encounters the successive application of f and g. These can be implemented by adding some extra information in the entries of thefusion environment µ. dist(f, M ) distributes the function variable
f to all the tail positions in M according to the deﬁnition given in
Section 3.

If fusion for this pair has succeeded before, then it returns
the new function name f g that was created by the previous
fusion attempt and recorded in the fusion environment.
If fusion failed before, then it returns f ◦ g.
If fusion has never been tried, then the algorithm attempts
to fuse the two by applying the fusion laws explained in
Section 3, and returns the environment extended with theresult of the fusion attempt.
• When it encounters a term let h = M1 in M2 end, the al-

gorithm processes M1 and obtains the new terms, and then processes M2 with the updated fusion environment. The algorithm
then checks whether the fusion environment holds new function
deﬁnitions that should be inserted into this let binding according to the following policy. If functions f and g are deﬁned inthis order, and f g = M is the new function deﬁnition createdby fusing f and g, then f g is inserted immediately after thebinding of g.
In a strict language, a further special treatment of bindings isnecessary during the computation of the (FixPromote) rule. We
shall discuss this issue in Section 6.3.

4.1

Extensions to multiple parameter functions

We describe the necessary extensions to deal with multiple parameter functions. Here we only consider uncurried functions, since an

5dist (f, M ) =case M ofcase M0 of p1 => M1 , . . . , pn => Mn⇒case M0 of
p1 => dist (f, M1 ), . . . , pn => dist (f, Mn )| let x = M1 in M2 end⇒ let x = M1 in dist (f, M2 ) end| ⇒ fM

F [[M ]] η µ =case M of(f (g M0 )) ⇒let (M00 , η 0 ) = F [[M0 ]] η µin case η 0 ((f, g)) ofFailed ⇒ ((f (g M00 )), η 0 )| Succeeded ⇒ (f g M00 , η 0 )| Inserted ⇒ (f g M00 , η 0 )| Undeﬁned ⇒if µ(g) = fix g.λx.Mg andµ(f ) = fix f.λx.Mf
thenletη 00 = fusion (f, λx.Mf ) (g, λx.Mg )η 0 µ|gincase η 00 ((f, g)) of
Succeeded ⇒ (f g M00 , η 00 )| Failed ⇒ (f (g M00 ), η 00 )endelse we perform ordinary inlining
end| let h = M1 in M2 end ⇒let(M10 , η1 ) = F[[M1 ]] η µ(M20 , η2 ) = F[[M2 ]] η1 µ{h 7→ M10 }inif η2 = η20 {(f, g) 7→ Succeeded M3 )} and(f = h or g = h)then (let h = M10 in let f g = M3 in M20 end,
η20 {(f, g) 7→ Inserted})else (let h = M10 in M20 end, η2 )end
| in all the other cases we perform ordinary inlining

Figure 3. Distribution function distintermediate language of an optimizing compiler often uses the uncurried representation. This is also the case in our implementation.
The set of terms is extended to include the uncurried multiple
parameter functions as follows.
M::=· · · | λ(x1 , . . . , xk ). M | M (M, . . . , M )~ for a sequences of terms of the form
In what follows, we write M
M1 , . . . , Mk separated by comma. Similar notation is used for~ 1 , . . . , M~ n ) represents a tuple term of
patterns. For example, (M11
the form (M1 , . . . , Mk1 , . . . , M1n , . . . , Mknn ).
The extended algorithm FM[[ ]] processes multi-parameter
functions as follows.
FM[[M ]] η µ =case M of~)⇒f (M~ ) ofcase divide (M
~
~
~r) ⇒
(Ml , g (Mm ), M...
let
η 00 = fusionM (f, λ(~x).Mf ) (g, λ(~x).Mg ) η 0 µ|g
in···fusion (f, λx.Mf ) (g, λx.Mg ) η µ =let
Mbody = dist(f, Mg )incase Mbody ofC[f (g Mi )]i ⇒let(M1 , η 0 ) = F [[C[f g Mi ]i {λx.Mf /f }]] η µ|fincase M1 of
C[f (g Mi )]i ⇒η 0 {(f, g) 7→
Succeeded (fix f g.λx.C[f g Mi ]i )}| ⇒η 0 {(f, g) 7→
Succeeded (fix f g.λx.M1 )}end| ⇒case F [[Mbody {λx.Mf /f }]] η µ|f of(C[f (g Mi )]i , η 0 ) ⇒η 0 {(f, g) 7→ Succeeded (fix f g.λx.C[f g Mi ]i )}| ( , η0 ) ⇒η 0 {(f, g) 7→ Failed}end~ ), divide (M~)
When the algorithm detects an application f (M~ andsearches for an application term of the form g (M~m ) in M
~ l , g (M~m ), M
~ r ) indicating that M~ are divided into three
returns (Mparts, the middle of which is the application term g (M~m ). The~ l , M~m , M~ r are recursively processed by FM[[ ]]matched terms M
and then used as part of the result as in the algorithm F[[ ]]. Whenf and g are recursive functions and they have not been tried tofuse, the extended fusion function fusionM is invoked and it tries
to fuse f and g in the expression λ(x~l , x~m , x~r ). f (x~l , g (x~m ), x~r )under the bindings {f 7→ fix f.λ(~x).Mf , g 7→ fix g.λ(~x).Mg }.
Note that we allow both the outer function f and the inner function
g to have more than one arguments. The fusing function fusionM
is obtained by reﬁning fusion based on the rule (FixPromote-u) in
Section 3. The sub-algorithm dist is also reﬁned to distM according
to (AppDist-u) rule.
~ l ), M, (M~ r )) =distM (f, (Mcase M ofcase M0 of p1 => M1 , . . ., pn => Mn⇒ case M0 of~ l ), M1 , (M~ r )), . . . ,p1 => distM (f, (M~ l ), Mn , (M~ r ))
pn => distM (f, (M| let x1 = M1 , . . ., xk = Mk in M0 end⇒ let x1 = M1 , . . ., xk = Mk~ l ), M0 , (M~ r )) end
in distM (f, (M~~| ⇒ f (Ml , M, Mr )Figure 2. Fusion algorithm F [[ ]]6~ l, M~ r are always variables since the function
The arguments f , M
distM is invoked in the function fusion as follows.

After fusion:
let fun sum_mapsq [] = 0| sum_mapsq (x::xs) = x*x + sum_mapsq xs
in sum_mapsq list
end

let Mbody = distM (f, (x~l ), Mg , (x~r )) in . . .
So the function distM does not cause code duplication.
The function fusionM tries to ﬁnd successive function appli~ i , g Mi , M~ ri ) and replaces them withcations of the form f (Mli
~ i , Mi , M ). By using the pattern matching notation as inf g (Mrl
the algorithm F [[ ]], we can write the matching part as follows:• Sum of the integers from n to m.

An integer list is produced by from and is consumed by sum.
Before fusion:case Mbody of~ i , g Mi , M~ ri )]i ⇒ . . .
C[f (Mllet fun sum [] = 0| sum (x::xs) = x + sum xs
fun from a b = if a > b then []else a :: from (a+1) b
in sum (from 100000 200000)
end~ i and M~ ri are pattern variables used to match the arwhere Mlguments. When the matching succeeds, the algorithm creates the~ i , Mi , M i )]i . This achieves the replaceterm of the form C[f g (Mrl~ i , g Mi , M~ ri ) of f and g with uncurment of the composition f (Ml
~ i , Mi , M i ) of newried multi-parameters by the application f g (Mrlfunction f g to the multiple parameters.

5.

After fusion:
let fun sum_from a b = if a > b then 0
else a + sum_from (a+1) b
in sum_from 100000 200000 end

ExamplesWe claim that the lightweight fusion method we have just presented
has practical signiﬁcance in two ways. Firstly, it is readily implementable in any optimizing compiler that performs inlining, andit does not produce extra runtime overhead (except for code size
increase due to the fact that both fused functions and the originalfunctions are referenced.) Secondly, although it does not have any
formal completeness property, it is powerful enough to fuse a wide
range of recursively deﬁned functions.
As we shall report in Section 6 and Section 7, we substantiate
the ﬁrst property by developing a simple inliner for a prototype
compiler of a full scale functional language and testing it withsome benchmarks. The second property can only be substantiatedthrough long-term practical testing. We demonstrate its feasibility
through examples that have been discussed in the literature.
5.1• foldl: Tail recursive sum of squares of list of integers.

This is a rewrite of the previous example using foldl. The tailrecursive foldl is much preferred to foldr if the result is thesame. There seems to be no practically implemented automatedfusion system that can deal with this simple example.
Before fusion:
let fun from a b = if a > b then []else a :: from (a+1) b
fun foldl f r [] = r| foldl f r (x::xs) = foldl f (f (x,r)) xs
in foldl (op +) 0 (from 100000 200000)
end
After fusion:

Successful examples and their performanceThis subsection shows typical examples that our lightweight fusion
algorithm can deal with. All of them are successfully fused by ourimplementation without any preparation or ad-hoc modiﬁcation to
the algorithm. We measured execution time, heap usage, and ﬁlesize for the examples with or without the inlining and fusion on ourabstract machine. The input data are lists with 105 elements andtrees with 218 elements. Tables 1, 2, and 3 show the performance
results. The meaning of the column marks are: “-” is without
inlining, “Inline” is with inlining, “Fusion” is with inlining andfusion, and “F/I” is the ratio of the last two.
As we shall describe in Section 6, our implementation is in acompiler for SML#, an extension of Standard ML. So let us use
Standard ML syntax in showing examples. Although fusion is done
for a typed polymorphic intermediate language, in showing examples, we omit type information to avoid cluttering the programs.

let fun foldl_from f r a b =if a > b then relse foldl_from f (f (a,r)) (a+1) b
in foldl_from (op +) 0 100000 200000 end• Fusion of map.

A boolean function even is applied to each element in the input
integer list. Then the function allTrue checks whether all theobtained values are true or not.
Before fusion:
let fun allTrue [] = true
| allTrue (x::xs) = x andalso (allTrue xs)
fun map f [] = []| map f (x::xs) = f x :: map f xs
fun even x = x mod 2 = 0
in allTrue (map even list)end• Sum of squares of a list of integers.

This is the old friend of fusion, whose fusion steps have beenshown in Section 2.
Before fusion:

After fusion:

let fun sum [] = 0| sum (x::xs) = x + sum xs
fun mapsq [] = []| mapsq (x::xs) = x*x :: mapsq xs
in sum (mapsq list)end

let fun allTrue_map f [] = true
| allTrue_map f (x::xs) =f x andalso (allTrue_map f xs)
fun even x = x mod 2 = 0
in allTrue_map even listend

7Table 1. Execution time for typical examples (in seconds)
Program− Inline Fusion
F/I
sum mapsq
0.27
0.27
0.21 78%sum from
0.21
0.22
0.15 68%
foldl from
0.27
0.27
0.15 56%
allTrue map
0.43
0.33
0.18 55%
sumTree mapsqTree 0.77
0.76
0.51 67%

Table 3. Program sizes for typical examples (in byte)
Program− Inline Fusion
F/I
sum mapsq
3,567
3,371
3,459 102.6%
sum from
2,278
2,126
2,174 102.3%
foldl from
3,354
3,274
2,546
77.8%
allTrue map
5,011
4,599
4,543
98.8%
sumTree mapsqTree 5,420
4,556
4,596 100.9%• Two successive applications of the same function.

Table 2. Heap allocation for typical examples (in the number ofﬁelds divided by one thousand)
Programsum mapsq
sum from
foldl from
allTrue map
sumTree mapsqTree

−
600.2
300.2
500.2
1,200.3
2,621.7

Inline
600.2
300.2
500.2
600.2
2,621.7

Fusion
300.2
0.2
200.2
300.2
1,310.9

Our algorithm does not fuse two successive applications of thesame function like the following.
let fun mapsq [] = []| mapsq (x::xs) = x*x :: mapsq xs
in mapsq (mapsq list)
end

F/I
50.0%
0.1%
40.0%
50.0%
50.0%

This is because our fusion algorithm performs inlining of eachfunction only once. We ﬁrstly inline the inner application ofmapsq. Then we distribute the outer mapsq to the body of inner
mapsq. After the distribution the fusion algorithm tries to inline
the outer mapsq, but it fails since (the inner) mapsq has alreadybeen inlined.

In this case, the function even is simply passed to the next function call without any change. This is just an extra parameter but
not the so called accumulating parameter. Our fusion algorithm
does not depend on whether the parameter is accumulating ornot.

• Mutually recursive functions.

Our current algorithm does not fuse mutually recursive functions such as the following.
let fun f [] = []| f (x::xs) = 2 * x :: g xs
and g [] = []| g (x::xs) = 3 * x :: f xs
fun sum [] = 0| sum (x::xs) = x + sum xs
in sum (f list)
end• Fusion of functions on trees

Our fusion does not depend on lists. In fact, our fusion systemdoes not even know any property of list. Our system can fuse
functions on user deﬁned tree-like structure. Here is a simple
example of fusing tree.
Before fusion:
let fun sumTree Empty = 0| sumTree (Node (x,t1,t2)) =x + sumTree t1 + sumTree t2
fun mapsqTree Empty = Empty| mapsqTree (Node (x,t1,t2)) =Node (x * x,
mapsqTree t1,
mapsqTree t2)
in sumTree (mapsqTree tree)
endThis limitation is due to our simple strategy to treat a pair offunctions (f, g) as a unit of fusion, and to inline each of thetwo functions only once during each fusion trial. We believe it
possible to reﬁne this strategy to deal with mutual recursion.
For example, if g is one of mutually recursive set of functions{g1 , . . . , gn }, then one strategy is to try to fuse the set ofpairs {(f, g1 ), . . . , (f, gn )} simultaneously, with the restrictionthat each function is inlined once for each pair. We leave thereﬁnement to future work.

After fusion:

6. Implementation

let fun sumTree_mapsqTree t =case t ofEmpty => 0
| Node (x,t1,t2) =>x * x+ sumTree_mapsqTree t1+ sumTree_mapsqTree t2
in sumTree_mapsqTree treeend

We have implemented the lightweight fusion algorithm given in
Section 4. This section describes the overview of the implementation and discusses several issues we had to cope with when implementing our algorithm.
For the reader to test our implementation or to read the code, wehave made the implementation (including the source code) available through the Internet for downloading at: http://www.pllab.
riec.tohoku.ac.jp/software/fusion/index.html.
6.1 Implementation in a strict language

5.2

The implementation is done by adding an inliner phase to a prototype compiler for SML# [20], which is an extension of Standard
ML, an eager language having imperative features.
The rationale of choosing the SML# compiler is our intention toinvestigate the feasibility of program fusion in a strict and impure
language in future. Although fusion has mainly been investigated

Examples that cannot be fused

As shown in the above, our fusion algorithm works on typicalexamples, but of course it does not fuse all the fusable functions.
We give two examples below to show the limitation of our current
fusion algorithm.

8and implemented in lazy languages such as Haskell, the principleof eliminating redundant intermediate data structure is of course
equally important in strict and impure languages. The major problem in applying fusion to imperative languages is the preservationof the order of imperative effects. As we shall examine in details in
6.3, fusion transformation in general changes the order of evaluation and thus its straightforward application to functions with side
effects is unsound. We expect that, with a proper control of interaction between fusion and imperative features, fusion should become
an important optimization for strict and impure languages as well.
We note that this situation is analogous to the relationship between
fusion and non-strict functions in lazy languages.
This issue is outside the scope of the present paper, and wewould like to investigate it elsewhere. Our current implementation
does not properly deal with imperative features. However, it is sufﬁcient for the purpose of the present paper stated in the introduction
section.
6.2

in bind xs = #2 yin ::(*(x,x), mapsq xs) end
end| _ => raise MatchCompBug))Firstly, we create a new function name dsum_mapsq and thendistribute dsum into the body of mapsq. In the following, we omit
the raise expression.
(fn x =>
(case x ofnil => dsum (nil)| :: y => bind x = #1 yin bind xs = #2 yin dsum (::(*(x,x), mapsq xs))
end
end))
In the next step, we apply the main function, FM[[ ]], to the obtained term. The case branches pi => ei are processed one by one,from the top to the bottom. The ﬁrst case is just inlining of dsum
to the empty list, which results in 0. Note that we allow inlining ofrecursive function once. In the next branch, we inline the bindings
bind x = #1 y and bind xs = #2 y. At this point, the term becomes as follows.

Implementing multiple argument fusion

Our fusion algorithm works on functions with multiple arguments.
We have given the rules for curried and uncurried versions, and our
method works on both versions. Among them, we have only implemented the uncurried version since the SML# compiler performs
uncurry optimization, which transforms multi-parameter functions
in curried form into uncurried intermediate code. For example, themap function is translated to the following term in the intermediate
language.

(fn x =>
(case x ofnil => 0| :: y => dsum (::(*(#1 y, #1 y),
mapsq (#2 y)))))[’a,’b. val rec map =(fn {f, x} =>(case x ofnil => nil {’b}| :: y => :: {’b}(f (#1 y), map {f, (#2 y)})| _ => raise MatchCompBug))]

We inline the application of dsum to the cons list. When inlining afunction applied to a term of some constructor, we make a bindingfor each argument of the constructor or put it in the inliner environment, depending on whether or not the argument is small andso on. In the usual inliner, the term at this point would become asfollows.

where {f, x} represents the multiple parameters. Our fusion algorithm for functions with multiple parameters works on this form ofterms.
6.3(fn x =>
(case x ofnil => 0| :: y => bind z = *(#1 y, #1 y)in bind zs = mapsq (#2 y)in +(*(2,z), dsum zs)
end
end))

Inlining bindings for function applications

In our implementation of the fusion algorithm, some special treatment of bindings is needed in addition to the usual inlining techniques. For the fusion of two functions f and g to succeed, successive function applications f (g ) should appear during the computation of the (FixPromote) rule for f and g. This implies that abinding of the form x = g e needs to be inlined during the fusionof f and g despite the fact that g e is not a value. The strategy wehave implemented is to inline the binding of the form x = g e if
the following conditions are met: (1) the inliner is processing thefusion for f ◦ g, and (2) x occurs in the context of f x so that the
inlining this binding will induce the replacement of f ◦ g with f g.
This means that successful fusion may change the order of evaluation if there is some computation between the binding x = g e andthe application f x.
Let us describe this strategy and the related issues by tracing
the fusion process for a variant of sum mapsq example, where thefunction sum is replaced with the following.

However, this does not make the successive application of dsum
and mapsq. So, we allow all the function applications to be put into
the inliner environment with the tag indicating that this should only
be inlined when the inlining makes fusion succeed. In this caseinlining zs makes the successive application, so we inline zs.
(fn x =>
(case x ofnil => 0| :: y => bind z = *(#1 y, #1 y)in +(*(2,z), dsum (mapsq (#2 y))end))

fun dsum [] = 0| dsum (x::xs) = 2 * x + dsum xs

Note that the evaluation order changes by the inlining of zs since a
multiplication occurs immediately after the squaring of the head element. By replacing the successive applications of dsum and mapsq
with dsum_mapsq, the evaluation order furthermore changes recursively.

The function mapsq is compiled to the following intermediate code.
val rec mapsq =(fn x =>
(case x ofnil => nil| :: y => bind x = #1 y

(fn x =>
(case x ofnil => 09

| :: y => bind z = *(#1 y, #1 y)in +(*(2,z), dsum_mapsq (#2 y))
end))

Table 4. Execution time for benchmarks (in seconds)
Benchmark− Inline Fusion
F/I
barneshut
21.0
16.7
16.7 100%
boyer
1.4
1.3
1.3 100%
coresml
89.6
88.6
88.4 100%countgraphs 199.9
140.2
140.6 100%
fft
24.7
16.1
16.1 100%knuthbendix
8.0
6.4
6.4 100%
lexgen19.0
13.2
13.3 101%
life
2.5
2.6
2.6 100%
logic
34.1
26.3
26.4 100%mandelbrot
13.7
12.3
12.3 100%
mlyacc2.6
2.3
2.4 100%
nucleic
1.5
1.1
1.1 100%
ray
16.7
14.2
14.2 100%
simple37.3
23.7
23.6 100%
tsp
8.5
7.3
7.3 100%
vliw
18.1
15.8
15.4
97%

This result is put into the fusion environment η. Our algorithm
performs this sequence of steps. The following is the actual term
generated by our compiler for the input term.
val rec dsum_mapsq =(fn $8 =>(case $8 of
nil => 0| ::$19 =>bind newVar = *(#1 $19, #1 $19)
in +(*(2,newVar), dsum_mapsq (#2 $19)) end| _ => raise MatchCompBug))
Note that an application of a function to a raise expression can be
reduced to the same raise expression with its type appropriatelychanged.
Let us remark a related issue concerning both strict and lazy
languages. The inlining of bindings for function applications may
in general cause work duplication. In the above example, if zs
occurs more than once in the scope of the binding zs = mapsq(#2 y), work duplication occurs even if fusion transformation
succeeds. This reﬂects the fact that our fusion method is for generalrecursive function deﬁnitions. There are various ways to cope withthis situation under the trade off between the duplicated work andthe effect of eliminating the production of data structures.

7.

Table 5. Heap allocation for benchmarks (in the number of ﬁelds
divided by one thousand)
Benchmarkbarneshutboyer
coresmlcountgraphs
fftknuthbendix
lexgenlife
logic
mandelbrot
mlyaccnucleicraysimpletsp
vliw

Benchmarks and Their Analysis

As we have stated in the introduction section, the purpose of our
implementation is to substantiate the following claims:• Our lightweight fusion algorithm can be readily implementablein an inlining phase of an optimizing compiler.
• It does not produce extra runtime overhead.

Our implementation and the performance results indeed verify
these two points. Except for several special treatments describedin the previous section, we were able to implement the algorithm in
a compiler of a full scale language using usual inlining techniques.
As shown in Section 5, the resulting system can fuse various typicalexamples discussed in the literature.
To verify the second point, we tested several standard benchmarks for Standard ML. We measured execution time, heap usage,
and code sizes with or without inlining and fusion transformation.
In the measurement, we made all the other optimizations on, including dead code elimination, uncurry optimization, constant folding, and tail call optimization. Tables 4, 5, and 6 show the benchmark results.
They show that our fusion transformation can be safely applied.
When fusion has failed, it just does usual inlining without producing any runtime overhead. The heap usage and program size are thesame as the case that fusion is off and inlining is on, except for thevliw benchmark. In the vliw benchmark, fusion occurs twice successfully, although the elimination of intermediate data structure
does not affect the execution time so much. Heap usage and ﬁlesize increase a little bit in the vliw benchmark when fusion option
is on, since after fusing (f ◦ g) to fg , the deﬁnitions of unused f
or g may remain even after the dead code elimination. This is dueto the limitation of our dead code elimination, which judges only
direct death and does not check the transitive death.
Looking at these benchmark results in the perspective of the effectiveness of fusion method for general ML programs, they would
give a pessimistic impression that fusion would not be effective inpractice. However, we should note that the implementation and the−102,515.4
7,138.9
0.3
1,077,263.9
112,517.3
53,258.9
91,378.5
4,313.5
180,964.5
69,444.4
14,731.3
11,818.8
87,368.6
172,191.6
30,313.4
112,342.8

Inline94,234.4
6,874.5
0.3
976,271.8
112,517.3
42,736.9
87,839.4
3,832.9
119,571.6
65,241.9
13,843.6
3,885.4
84,484.8
130,210.3
19,851.9
99,979.7

Fusion94,234.4
6,874.5
0.3
976,271.8
112,517.3
42,736.9
87,839.4
3,832.9
119,571.6
65,241.9
13,843.6
3,885.4
84,484.8
130,210.3
19,851.9
99,980.4

Table 6. Code sizes for benchmarks (in kilo byte)
Benchmark−
Inline Fusion
F/I
barneshut
205.4
231.7
231.7 100%
boyer
227.0
227.2
227.2 100%
coresml
1.7
1.5
1.5 100%
countgraphs
92.2
94.3
94.3 100%
fft
36.6
37.7
37.7 100%knuthbendix
132.8
156.0
156.0 100%lexgen243.3
295.6
295.6 100%
life
51.3
62.6
62.6 100%
logic
144.8
154.8
154.8 100%mandelbrot
8.4
8.3
8.3 100%
mlyacc1436.8 1641.6 1641.6 100%
nucleic
636.2
583.3
583.3 100%
ray
95.6
104.4
104.4 100%
simple263.5
347.7
347.7 100%
tsp
70.8
78.5
78.5 100%
vliw
794.6
941.3
944.9 100%

10

F/I
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%

benchmarks reported in this section are quite preliminary; we performed them only for verifying the above two points. In particular,
we put almost no effort to tune the fusion algorithm against thecompiler and the language. As such, the preliminary results should
not be interpreted as a deﬁnite negative evidence of the effectiveness of our light weight fusion method for strict imperative languages.
To analyze this issue, we have examined the fusion process of a
few benchmarks and have identiﬁed the following three problems
that have prevented fusion from occurring in our current implementation.

language, our light weight fusion method would show reasonable
speed up over already optimized code.

8. Related Work
In a general perspective, our fusion method can be regarded as a
special case of the fold/unfold method of Burstall and Darlington[1]. A major problem of applying the general idea of fold/unfold
transformation to automated program optimization is to control
termination and to ﬁnd a good strategy for folding (i.e. generating
new recursive deﬁnitions). Due to this difﬁculty, there does notseem to exist an automatic fusion method that directly fuses generalrecursive deﬁnitions.
In the work of deforestation [23, 3], this problem was solved by
restricting the class of fusable expressions. However, the restriction appears to be too strong for this method to be imporporated ina practical compiler. In short-cut fusion approach [6] or its extensions [7, 5], the problem was avoided by giving up fusing recursivedeﬁnitions and instead developing a speciﬁc fusion laws for expressions using foldr and build. Warm fusion [12] and transformation
to hylomorphism forms [9] also avoid this problem by transforming general recursion to speciﬁc forms to which short-cut fusion
laws can apply. As we mentioned in the introduction, its practicalfeasibility remains to be seen.
Our method appears to be the ﬁrst successful example that overcomes the difﬁculty of generating new recursive deﬁnition mentioned above and directly fuses general recursive deﬁnitions. The
key insight of our approach is that a practical fusion system is obtained by focusing on a speciﬁc fusion pattern of recursive function
deﬁnition and that this process is expressed by a combination ofsyntactic transformation rules without requiring any heuristics.
We share the motivation with the designers and developers of
optimizing compilers with fusion transformation. One notable example is the GHC compiler’s rules pragma [17], where the compiler
is extended with a mechanism to specify general rewrite rules. Thismechanism allows programmers, especially the designers of a basis
library, to specify the short-cut fusion [6], its extension [7], arrayfusion [2], and many other useful optimizations for functions. Our
system on the other hand allows fully automated fusion for generalrecursive function deﬁnitions.
There have been some attempts to implement warm fusion,
including a program transformation system Stratego [10] and an
experimental extension to the GHC compiler [15]. However, as
reported in [15], there is some overhead problem because of theintroduction of lambda abstractions. In [16], the GHC compiler isextended with the hylo fusion system [9]. Given that the underlying
mechanism is more general than warm fusion [12] in the sense thatit can deal with arbitrary data type, the benchmark results reported
in [16] are quite encouraging. Considering the lack of a mechanism
for functions with accumulating parameters such as tail recursivefunctions, its practical feasibility remains to be investigated.
Recent work by Katsumata and Nishimura [11] have shown thatshort-cut fusion can be generalized to incorporate accumulating
parameters using algebraic properties of functions. This result canbe used to extend automated fusion system such as the one [16] forwider range of recursive function deﬁnitions. But again, it remains
to be seen whether a practically feasible automated optimization
step can be extracted from its involved mathematical development.
Compared with those previous approaches, our method provides
an alternative very light weight fusion method that can be incorporated to an optimizing compiler.

1. Our current implementation only fuses functions if they appear
in a nested let expression. In particular, it cannot fuse any
functions in different compilation units. Since functions in thebasis library are always in different compilation units from thatof the user program, they cannot be fused.
2. The current SML# compiler can only perform uncurrying optimization for locally deﬁned functions. All the escaping functions are in curried form. This minimizes the opportunities forour multiple-parameter function fusion.
3. A function is often deﬁned as a simple call to a locally deﬁned
recursive function. A typical case is a function that uses a tailrecursive auxiliary function. Such a locally deﬁned auxiliary
recursive function is not recognized as a candidate of fusion.
The following code fragment in the “simple” benchmark illustrates
the ﬁrst two points.
flatten (map (fn k => (map (fn l => f (k,l))(from(lmin,lmax))))(from (kmin,kmax)))
The function map is deﬁned in the basis library and is in a curried
form. The following code in the benchmark ray exhibits the third
point.
implode (map fromStr x)
implode is deﬁned in the basis library as follows.
fun implode chars =letfun scan [] accum = accum| scan (char :: chars) accum =scan chars (accum ^ (Char_toString char))inscan chars ""endThis has a locally deﬁned recursive function inside and the function
implode itself is not a recursive function.
The ﬁrst problem can be solved by reﬁning our environment
management in such a way that the algorithm maintains an environment that keeps the body of each recursive function beyond its
compilation unit. The second point requires either to implement thefusion rules for curried multi-parameter fusions or to improve theuncurrying optimization so that it works for non local deﬁnitions.
The third point can be solved by inlining non-recursive (small)functions before fusion.
Remedying these three points and implementing a practical fusion algorithm are beyond the scope of the present paper. Instead,
we have hand-simulated the necessary extensions for the “simple”
benchmark by manually changing the source program. The resultshows that fusion succeeds ﬁve times and the execution time decreases 5% compared with the case where the other optimizations,
including inlining, are on. From this preliminary analysis, we expect that if we ﬁne tune our method against the compiler and the

9. Conclusions and Future Work
We have developed a lightweight fusion method that automatically fuses recursive function deﬁnitions. The method is based on

11

a new fusion process, called ﬁxed point promotion, that transformsf ◦ (fix g.λx.E) to a new ﬁxed point term fix h.λx.E 0 by promoting the function f through the ﬁxed point operator. We haveshown that this process is represented by the combination of two
new transformation rules (AppDist) and (FixPromote) and haveshown their soundness. We have then given a fusion algorithm byincorporating these rules in an inlining process. Since these rules
are not sensitive to the types of functions being fused, our fusion
method can be applicable to a wide range of functions including
those with multi-parameters in both curried and uncurried form andalso those that manipulate user-deﬁned general data types. Since
the two new laws are both simple and syntactic ones that only perform local transformation without requiring search or other heuristics, our method can be readily incorporated to any standard inlining optimization. To demonstrate the practical feasibility of our
method, we have implemented our method in a compiler of a fullscale functional language, and have successfully tested various examples including those that cannot be dealt with in any existing realcompiler. The performance result shows that our method does not
introduce runtime overhead for large scale benchmarks.
This is our ﬁrst step towards developing a practical lightweightfusion method, and a number of further issues remain to be investigated. The most important one is the evaluation of the feasibility of
our method through a serious implementation. As we have noted,
our current implementation is experimental and requires a number of reﬁnements as discussed Section 7. Furthermore, our current
implementation does not consider possible imperative effects andtherefore it may not be sound for programs with side effects. We
plan to combine our fusion method with a static effect system andinclude in our SML# compiler. Implementing our system in a lazy
language such as GHC would also be a worthwhile future work.
Another interesting direction of research is to investigate various formal properties of our fusion lows. We have shown the semantic soundness using denotational semantics. One possible reﬁnement wold be to adopt the idea of improvement theorem byDavid Sands [18] to our setting. Another important issue is the correctness in call-by-value semantics. Our correctness theorem (Theorem 2) depends on call-by-name semantics. A promising approach
toward this direction would be to use the axioms for recursion incall-by-value by Hasegawa and Kakutani [8].

[6] A. Gill, J. Launchbury, and S. Peyton Jones. A short cut todeforestation. In Proc. International Conference on Functional
Programming Languages and Computer Architecture, pages 223–
232, 1993.
[7] A. Gill. Cheap Deforestation for Non-strict Functional Languages.
Ph.D thesis, University of Glasgow, 1996.
[8] M. Hasegawa and Y. Kakutani. Axioms for recursion in call-by-value.
Higher-Order and Symbolic Computation, 15(2-3):235–264, 2002.
[9] Z. Hu, H. Iwasaki, and M. Takeichi. Deriving structural hylomorphisms from recursive deﬁnitions. In Proc. ACM International
Conference on Functional Programming, pages 73–82, 1996.
[10] P. Johann and E. Visser. Warm fusion in Stratego: A case study
in generation of program transformation systems. Annals of
Mathematics and Artiﬁcial Intelligence, 29(1-4):1 – 34, 2000.
[11] S. Katsumata and S. Nishimura. Algebraic fusion of functions withan accumulating parameter and its improvement. In Proc. ACM
International Conference on Functional Programming, pages 227–
238, 2006.
[12] J. Launchbury and T. Sheard. Warm fusion: Deriving build-catasfrom recursive deﬁnitions. In Proc. ACM Conference on Functional
Programming Languages and Computer Architecture, pages 314–
323, 1995.
[13] G. Malcolm. Homomorphism and promotability. In Proc. Mathematics of Program Construction, pages 335–347, 1989.
[14] E. Meijer, M. Fokkinga, and R. Paterson. Functional programmingwith bananas, lenses, envelopes and barbed wire. In Proc. International Conference on Functional Programming Languages andComputer Architecture (FPCA’91), Lecture Notes in Computer Science 523, pages 124–144, 1991.
[15] L. Nemeth and S. Peyton Jones. A design for warm fusion. In Proc.
International Workshop on Implementation of Functional Languages,
pages 381–393, 1998.
[16] Y. Onoue, Z. Hu, H. Iwasaki, and M. Takeichi. Veriﬁcation ofpractical effectiveness of program fusion (in Japanese). Computer
Software, 17(3):81–85, 2000.
[17] S. Peyton Jones, A. Tolmach, and T. Hoare. Playing by the rules:
rewriting as a practical optimisation technique in GHC. In Proc.
ACM Haskell workshop, 2001.
[18] D. Sands. Proving the correctness of recursion-based automatic
program transformations. Theoretical Computer Science, 167(12):193–233, 1996.

Acknowledgments[19] T. Sheard and L. Fegaras. A fold for all seasons. In Proc. Functional
Programming Languages and Computer Architecture, pages 233–
242, 1993.

We are grateful to Masahito Hasegawa for his comments on thepossibility of proving the correctness of our fusion laws based on
their axioms for recursion in call-by-value. We would like to thankanonymous referees for many helpful suggestions and comments.
Comments from Olaf Chitil, Philip Wadler, and Akimasa Morihata
were useful in improving the paper.

[20] SML# home page. http://www.riec.tohoku.ac.jp/smlsharp/, 2006.
[21] J. Svenningsson. Shortcut fusion for accumulating parameters & ziplike functions. In Proc. ACM International Conference on Functional
Programming, pages 124–132, 2002.
[22] A. Takano and E. Meijer. Shortcut deforestation in calculational
form. In Proc. ACM/IFIP Conference on Functional Programming
Languages and Computer Architecture, pages 306–313, 1995.

References[1] R. Burstall and J. Darlington. A transformation system for developing
recursive programs. Journal of the ACM, 24(1):44–67, 1977.

[23] P. Wadler. Deforestation: transforming programs to eliminate trees.
Theoretical Computer Science, 73:231–248, 1990. Special issue of
selected papers from 2’nd European Symposium on Programming.

[2] M. Chakravarty and G. Keller. Functional array fusion. In Proc.
ACM International Conference on Functional Programming, pages
205–216, 2001.
[3] W-N. Chin. Safe fusion on functional expression. In Proc. ACM
Conference on Lisp and Functional Programming, pages 11–20,
1992.
[4] O. Chitil. Type inference builds a short cut to deforestation. In Proc.
ACM International Conference on Functional Programming, pages
249–260, 1999.
[5] N. Ghani, P. Johann, T. Uustalu, and V. Vene. Monadic augment andgeneralised short cut fusion. In Proc. ACM International Conference
on Functional Programming, pages 294–305, 2005.

12