On the power and limitations of strictness analysis.
Strictness analysis is an important technique for optimization of lazy functional languages.  It is well known that all strictness analysis methods are incomplete, i.e., fail to report some strictness properties.  In this paper, we provide a precise and formal characterization of the loss of information that leads to this incompletenss.  Specifically, we establish the following characterization theorem for Mycroft's strictness analysis method and a generalization of this method, called ee-analysis, that reasons about exhaustive evaluation in nonflat domains: Mycroft's method will  deduce a strictness property for program P iff the property is independent of any constant appearing in any evaluation of P. To prove this, we specify a small set of equations, called E-axioms, that capture the information loss in Mycroft's method and develop a new proof technique called E-rewriting. E-rewriting extends the standard notion of rewriting to permit the use of reductions using E-axioms interspersed with standard reduction steps.  E-axioms are a syntactic characterization of information loss and E-rewriting provides and algorithm-independent proof technique for characterizing the power of analysis methods.  It can be used to answer questions on completeness and incompleteness of Mycroft's method on certain natural classes of programs. Finally, the techniques developed in this paper provide a general principle for establishing similar results for other analysis methods such as those based on abstract interpretation.  As a demonstration of the generality of our technique, we give a characterization theorem for another variation of Mycroft's method called dd-analysis.
INTRODUCTION
Mycroft [1980] pioneered the concept of strictness analysis as a technique for optimizing
lazy functional languages by transforming call-by-need to call-by-value. His
results have had major impact on techniques for compilation, optimization and parallel
evaluation of lazy functional languages.Mycroft's work was based on abstract
interpretation of first-order functions defined over flat domains. Subsequently, there
has been much research into developing strictness analysis techniques for higher-order
functions [Burn et al. 1985; Hudak and Young 1986; Kuo and Mishra 1989]
Work partially supported by NSF grants CCR-8706973, CCR- 8805734 and CCR-9102159. A
preliminary version of this paper was presented in POPL '91.
Authors' addresses: R. Sekar, Bellcore, Room 1J-226R, 445 South Street, Morristown, NJ 07960;
email: sekar@bellcore.com; P. Mishra and I.V. Ramakrishnan, Department of Computer Science,
SUNY at Stony Brook, NY 11794; email: fmishra,ramg@cs.sunysb.edu.
and non-flat domains [Hughes and Wadler 1987; Hall and Wise 1987; Sekar et al.
1990; Wadler 1987].
It is well-known that no strictness analysis method can deduce all the strictness
properties of a function. For example, consider the function
where P (x) is always true for all values of x. Observe that F is strict in y, but this
fact is impossible to detect uniformly. Therefore, any strictness analysis method
must be incomplete, i.e., fail to report some strictness properties. This incompleteness
may arise from a variety of sources such as inability to represent all possible
strictness properties, inability to accurately analyze function composition or re-
cursion, etc. Such inaccuracy leads to some "information loss" in any strictness
analysis method. Despite a decade of research into strictness analysis methods,
the important problem of discovering a precise and formal characterization of this
loss of information has remained open. Such results, which we call characterization
theorems, are important because they provide an unequivocal basis for comparing
different strictness analysis methods. They also enable us to pinpoint weaknesses of
existing methods, improve them and aid us in discovering new and more powerful
methods.
1.1 Main Results
In this paper we present the first characterization theorems for Mycroft's method
and its natural generalization to non-flat domains called ee-analysis [Sekar et al.
1990]. Our main theorem is:
Mycroft's method will deduce a strictness property for program P iff the deduction
is independent of any constant appearing in any evaluation of P .
For instance, in the function F above, deducing that F is strict in y is based on the
fact that P (x) always evaluates to the constant true and thus Mycroft's method
cannot deduce this.
In Mycroft's method all constants are mapped to a single value in the abstract
domain. This obviously must contribute to loss of information. However there are
several other steps in the abstraction that might also contribute to information
loss: the choice of abstract representations for the primitive functions, the use of
composition and fix point iteration to analyze user-defined functions, etc. Our
contribution is to show that the information loss in Mycroft's method is only due
to the mapping of all constants to a single value; all other abstraction steps are
lossless. An important consequence of our result is that any method that uniformly
ignores constants cannot be any more powerful than Mycroft's method.
1.2 Overview of Approach
To state our characterization theorem formally and prove it, we needed to devise
new technical ideas and proof techniques. First, we specify a small set of equational
axioms (called E-equations) that make all constant terms interconvertible, thereby
capturing the information loss incurred by mapping all constants to the same value.
The E-equations induce an equivalence relation =E (called E-equivalence) on pro-
grams, given by P =E Q iff P can be obtained from Q by "changing its constant
parts". Based on this notion of E-equivalence of programs, our main theorem can
On the Power and Limitations of Strictness Analysis \Delta 3
be formally stated as: Mycroft's (and our ee-analysis) method will deduce strictness
property ' of program P iff ' is a strictness property shared by every program
For illustration, the following two programs are E-equivalent since one can be
obtained from the other by changing true to false or vice-versa.
Note that F 1 is strict in x, whereas F 2 is strict in y. However, neither of these
properties are shared by both programs. Thus these two properties will not be
inferred by Mycroft's method. On the other hand, the property x  y is shared by
both and hence will be inferred by Mycroft's method.
For the only if part of the characterization theorem we show that if P =E Q then
we compute the same strictness properties for P and Q. For establishing the if
part we need to show that for any strictness property ' of P that is not inferred by
Mycroft's method, there exists a Q =E P for which ' is not a strictness property.
The construction of such a Q is quite complex and cumbersome. Therefore we
develop a new proof technique called E-rewriting that precisely formalizes the notion
of performing reductions with any Q =E P . E-rewriting extends the standard
notion of rewriting to permit the use of equational steps interspersed with standard
reduction steps from P . Thus constants can be interchanged at any point in the
reduction sequence. Finally, we show that there is no loss of information due to
composition and recursion, other than that captured by E-rewriting.
E-equations are a syntactic characterization of information loss and E-rewriting
provides an algorithm independent proof technique for characterizing the power of
strictness analysis. (By this we mean that if we want to know whether an analysis
procedure will compute a strictness property, we need not know its computation
procedure at all. We need only check if the strictness property is preserved if the
program is modified as permitted by the E-axioms, e.g., changing constants in My-
crofts and ee-analysis method.) It can be used to answer questions of completeness
of such methods with respect to classes of programs. In contrast, it appears difficult
to deal with such questions using the setup of abstract interpretation. Section 5
describes in detail our completeness results based on E-rewriting.
The techniques developed in this paper provide a general principle for establishing
similar characterization theorems for many other analysis methods. As a
demonstration of the generality of our technique, we have been able to give a characterization
theorem for another variation of Mycroft's method called dd-analysis.
dd-analysis is an enhancement of Mycroft's method to reason about head normal
forms in non-flat domains. Among other applications, dd-analysis has been shown
to be a valuable tool for repairing violations of strong sequentiality, a concept pioneered
by Huet and Levy [1979] for lazy evaluation of equational programs.
Since the preliminary version of this paper appeared in POPL '91, much research
[?; ?] has taken place in the area of completeness of abstract-interpretation-based
analyses. In Section 6 we provide a detailed comparison between our approach and
the approaches proposed in these works.
The rest of this paper is organized as follows: Section 2 is an overview of the
ee-analysis method. Technical details of E-rewriting and the main theorem appear
in section 3. In section 4 we give a characterization theorem for dd-analysis. Implications
and significance of our results appear in section 5 together with remarks
on its generality. Finally relationship with other research is dicussed in Section 6.
2. PRELIMINARIES
The language we consider is a constructor-based term rewriting system (TRS). Such
a system consists of a set of oriented equations (called rewrite rules) of the form
r where the left-hand side (lhs) l and right-hand side (rhs) r are terms that may
contain variables. The lhs must be linear, i.e., no variable in them can occur more
than once. Furthermore, the nonvariable symbols are partitioned into two disjoint
sets - the set of function symbols F , and the set of constructor symbols C, such
that the outermost symbol of every lhs is in F while the rest are in C. First-order
programs written in functional languages, as well as the recursion equations studied
by Mycroft, follow this discipline.
By t[x / v] we refer to the term obtained from t by substituting the variable
x with the term v. If u is a term with n variables x
shorthand for u[x 1 substitution fi maps variables to terms.
An instance tfi of a term t is obtained by replacing x by fi(x) for each variable x
in t. A redex in term u is an occurrence of an instance of an lhs. A term t is in
normal form (NF) if it contains no redexes.
By t ! u we mean that u is obtained by replacing a redex lfi in t by rfi, where
r] is a rewrite rule. The reflexive and transitive closure of ! is denoted by
We use the notations t # NF and t " NF to denote respectively that t can or
cannot be reduced to a term in NF. A term t is in head normal form (HNF) if there
is no redex t 0 such that t !   t 0 .
2.1 Overview of ee-analysis
Our characterization theorem is based on ee-analysis which is a strictness analysis
method for non-flat domains. This analysis tells us which subterms of a term are
to be normalized in order to normalize the entire term. We review this method
and remark that it reduces to Mycroft's method for programs on flat domains.
Therefore our results for ee-analysis directly apply to Mycroft's method as well.
First we define strictness property of a term t as follows.
Definition (ee-Strictness). Let t be a term,
is an ee-strictness property of t
iff, in every reduction sequence that normalizes any instance tfi of t, all the terms
in one of the sets ffi(x 11 ); :::; fi(x 1r1 )g; :::; ffi(x n1 ); :::; fi(x nrn )g are normalized.
For instance, the ee-strictness of if is means that in
order to normalize if(t we have to normalize either t 1 and t 2 or t 1 and t 3 .
We use the notation t ee to denote the ee-strictness of a term t. The strictness
of arbitrary terms is computed by composing the strictness of constructors and
function symbols using the following rule.
On the Power and Limitations of Strictness Analysis \Delta 5
Definition (Rule of Substitution). Let t be a term, x xn be the variables in t
and fi be a substitution for these variables. Then
To illustrate this rule, consider the and the substitution fi(x 0
z). The rhs of the above rule becomes f ee [x 0 / x; x 00 / g ee (y; z)].
Suppose that f ee ee (y; z. Then the rhs would
simplify to yield the strictness of
Now we proceed to the equations to compute x ee ; c ee , and f ee , so that, together
with the above rule of substitution, we can compute strictness of arbitrary terms.
For the variable case, its substitution is to be normalized, and hence x
For the case c(x 1 ; :::; xn ), the NF of its instance c(s 1 ; :::; s n ) is obtained only by
normalizing each of s Hence c ee is the conjunction of the x i . Note that, by
this definition, if the arity of c is zero then c ee = true. This discussion yields the
following two equations:
For the case when the root symbol is a function symbol f , assume that f is defined
by the rules:
Observe that any instance f(s can be rewritten into only
one of e 1 ; :::; e k . Therefore f ee is a disjunction of e ee
k. However,
f ee is a formula on x 1 ; :::; xn , and these variables differ from those in e j (which
are actually variables in t 1
Hence we need a function g j that projects the
demand on the variables in t 1
into a demand on x 1 ; :::; xn . This leads us to
the following equation for defining f ee .
The equations to define g j are as follows. These equations are to be applied in
the order in which they are given. In this definition, ' and / stand for arbitrary
boolean formulae in disjunctive normal form (DNF), and ' with a subscript stands
for a conjunction.
contains no variable
6 \Delta R. Sekar et al.
The justification for the definition of g j is as follows. Eq. (4) simply "pushes" the
operations into individual conjunctions. For Eqs. (5) through (7), note that if
rewritten by the jth equation then it must be the case that s
for some fi. If t i
contains variables x i1 ; :::; x ir i
, and all these are e-demanded to
normalize e j , then s i must be normalized. This is because all nonvariable symbols
in t i
are constructors, and so s i will be in NF if each of fi(x i1 ); :::; fi(x ir i
are in
NF. Hence x i appears in g j (e ee
appears in e ee
(and hence (6)).
By the same argument, if t i
consists entirely of constructors (no variables), s i must
be normalized to match it, and hence x i is e-demanded (and hence (5)). Otherwise
we cannot conclude an e-demand on x i , and thus it does not appear in f ee (and
hence (7)).
The above equations directly compute f ee if f is nonrecursive. In case of recursive
functions we use the following fixpoint iteration procedure. Let f 1 ; :::; fm denote
all functions in the program. For
e ee
l / f ee;r
l
is the number of rules defining f i . The limit of the sequence f ee;0
is defined to be f ee
We illustrate ee-analysis using the following program:
Example 1.
We begin with f
(by definition of
(by (5)), which can then be simplified to x
using 2 applications of (6). It can be easily seen that e ee;0
Substituting this, we get g 1 (e ee;1
. Observe that
e ee;1
(by two applications of (6)).
Also note g 3 (e ee;1
which can be reduced to x
applications of (6)) and then to x
Following the same procedure, we arrive at f Thus, f is ee-strict
only in its second argument.
To derive Mycroft's method from ee-analysis, observe that each function in his
recursion equation notation is defined using a single rewrite rule. Therefore the
disjunction in rule (3) is unnecessary. Furthermore, since these equations have no
constructors on the lhs (no pattern matching), it can be easily shown that the g j 's
reduce to identity function. Finally, note that some of the primitive functions such
as the conditional, used by Mycroft can be defined using pattern matching. The
strictness properties derived by our analysis for such functions are exactly those
assumed by Mycroft.
On the Power and Limitations of Strictness Analysis \Delta 7
3. CHARACTERIZATION THEOREM FOR EE-ANALYSIS
3.1 Alternative Definition of Strictness Property
We start this section with an alternative definition of strictness property that is
used in our proofs. For this definition, we need to relate substitutions and truth
assignments as follows. (In the following, we use the notations t # NF and t " NF
to denote respectively that t can or cannot be reduced to a term in NF.) Let A
be a (truth assignment) function assigning true or false to x 1 ; :::; xn and oe be a
(substitution) function assigning terms to x 1 ; :::; xn . We say oe
In other words, A assigns true to a variable whenever
oe substitutes a term possessing NF in its place. Similarly, oe  c A means that
Definition (Strictness Property II). ' is a strictness property of t iff
Note that this definition is a compact version of Mycroft's original definition (pp.275
in [Mycroft 1980]) of strictness property. Now we show that the two definitions of
strictness property are equivalent.
Proof of equivalence of Strictness Properties I and II. To show that
definition 1 implies definition 3, we proceed as follows. Let A(') be false. Then A
must assign false to one literal in each conjunct in the DNF of '. Therefore every
oe  c A; must substitute a term with no NF for one literal in every conjunct. From
the contrapositive of definition 1, the consequent toe " NF of definition 3 follows. To
show that definition 3 implies 1, assume that the antecedent of the contrapositive
of definition 1 holds (i.e., 8j 9i
Note that and hence by definition 3, tfi '' NF.
3.2 Maximal Strictness Property
The set of strictness properties forms a lattice and hence every term t has a maximal
strictness property, which is defined as follows.
Definition (Maximal Strictness Property).
A strictness property ' of t is said to be maximal if either of the following (equiv-
alent) conditions hold.
1. If / is a strictness property for t then ' ) /.
2. 8A A(') ) 9oe  c A; toe #NF.
In the following example, are all strictness properties
of f whereas x 2 is its maximal strictness property.
Example 2.
Proof of equivalence of the conditions in Definition 4. Henceforth we
assume that ' is in DNF. To show that (2) implies the (contrapositive) of (1), pick
any arbitrary /. If holds. Otherwise, we can find an A such that
true and false. For this A, there is a oe  c A; such that toe # NF
(by 2). Note that toe # NF although hence / is not a strictness
property of t.
Now we show that :2 ) :1 (i.e., 1 ) 2). Assuming :2, there is an A such
that true and 8oe  c A; toe '' NF. Since true, there is a conjunct
' 1 of ' such that A(' 1
be the disjunction of all the remaining clauses in ' other than ' 1 . Let
now show that / is a strictness property
of t, thus contradicting 1. To do this, consider any
A such that
A(') is also false, then since ' is a strictness property, we have 8oe  c
Otherwise, (i.e.,
must be the case that
in t). This means that
and hence
. Since we already know that 8oe  c A 0 toe " NF, we have
established that / is a strictness property of t.
3.3 E-axioms and E-Rewriting
We introduce the following equations (henceforth called E-axioms) to capture the
notion that we cannot distinguish between constants in ee-analysis.
Note that a term c(c consisting entirely of constructors can be built
from
c using equation (8). By repeating this process, we can build any such constructor
term containing  c starting with  c. All such terms are equal. Since any
two zeroary constructors are equal by equation (9), any two constructor terms are
made equal by these equations.
We say t can be obtained from s using the above two equations.
This relation can be naturally lifted to rewrite rules and programs as follows: l !
. For programs P and Q, P =E Q iff for every
rule l ! r in P there is a rule l in Q and vice versa. Henceforth P
and Q stand for programs.
Finally we define E-derivation each t i is obtained
from t i\Gamma1 by applying one of the rewrite rules in the program or one of the above
equations. We call the reduction step a P -step (denoted t i !P t i+1 ) in the former
case and an E-step (denoted t i !E t i+1 ) in the latter case. If it is a P or an
E-step then we denote it as Note that in an E-step equation (8)
can be applied either right-to-left, denoted (8r), or left-to-right, denoted (8l). We
say that a term t is in E-normal form iff it contains no function symbols and use
the notation s#E-NF to denote that s possesses an E-NF.
As noted in the introduction, E-rewriting formalizes the notion that constants
can be interchanged at any point in the reduction sequence and therefore we achieve
the effect of performing reductions w.r.t. to any Q =E P . Formally,
Theorem 1. t !
On the Power and Limitations of Strictness Analysis \Delta 9
Proof. By definition of E-equivalence of programs, a Q-reduction step l 0
(here l is equivalent to a (P; E)-reduction sequence l 0 oe !
Therefore every Q-derivation can be viewed as a
special type of (P; E)-derivation and hence the proof in (() direction. For the proof
in the other direction, we need to transform an arbitrary (P; E)-derivation sequence
into one of this special type. To do such a transformation requires rearranging
the order in which the E-steps and P -steps are performed. It is straightforward
to rearrange a sequence consisting of an E-step followed by a P -step (or P -step
followed by a E-step) into one consisting of zero or more P -steps followed by zero or
more E-steps (or zero or more E-steps followed by zero or more P -steps). However,
simply repeating this process may create arbitrarily many new E or P -steps and
so this process of rearrangement may not terminate. Therefore a sophisticated
analysis of the interaction between the E and P -steps is necessary to construct
the desired reduction sequence. We first present an outline of such a construction
below:
1. Let t k ! t k+1 be the first application of (8r) in the sequence t !
(P;E) s. We
show that either this reduction and the one immediately preceding it can be inter-
changed, or that the preceding equation uses a program rule l ! r and the effect
of performing these two reductions can be achieved by performing one reduction
using a rule l ! r 0 (here r =E r 0 ).
2. We repeat step 1 till the reduction using (8r) rule "disappears" or is moved
ahead of all other reductions.
3. Repeat step 2 on the next application of (8r) rule and so on. At this point,
we have a reduction sequence which can be partitioned into two parts. The initial
contains a sequence of reductions using (8r) rules alone. The latter
part contains reductions using (8l), (9) and rules of the form l ! r 0 , where l ! r
is a rule in P and r =E r 0 . Let t t.
4. In a manner analogous to the steps above, we "push" all applications of rules
r is a rule in P and r =E r 0 ) ahead of all applications of (8l) and
steps.
Now we have constructed the reduction sequence t !
Note that Q consists only of rules l that are E-equivalent to some rule l ! r
in P and thus Q =E P . We now fill in the details of the proof by providing the
details of each of the above four proof steps:
be the first reduction step that uses the (8l) rule and let
r be the rule used in the reduction t immediately preceding it. Noting
that t k+1 must be of the form u[roe], we have the following cases depending upon
whether the (8l) rule is applied inside u (case 1a) or inside oe (case 1b) or inside r
(case 1c).
Case 1a: Let a term at whose root the reduction using
(8l) is performed. Now, the following diagram illustrates how the order of these
reductions can be interchanged.
Case 1b: In this case, (8l) must have been applied inside some subterm
for a variable x in r and must have rewritten s into some s 0 . Thus t
s; be the other subterms that are
substitutions for x (i.e., the variable x occurs times in r). So t k+1 is of the
We can interchange the order of these
reductions as follows: t
k+1 can be reduced to t k+2 by n applications of (8r) rules
to reduce each s 0
i back to s i .
Case 1c: Note that in this case l ! r cannot itself be a (8l) rule since the first
application of (8l) rule was in t It cannot be a (8r) rule since in that
case x and we cannot apply (8l) rule within r. If it is the rule, then we
have the following diagram.
Otherwise, if it is a program rule, we have the following diagram.
J"
This completes the proof of step 1.
be the first application of a program rule l ! r. Therefore
and we again have three cases to consider depending upon whether the
preceding reduction (using (8r) or (9) was performed within u (case 4a) or within
oe (case 4b) or within l (case 4c).
Case 4a: Note that this case is not possible if the rule applied in the step
On the Power and Limitations of Strictness Analysis \Delta 11
rule and so it must have been a (8r) rule. The following
diagram illustrates how the two reductions can be interchanged.
Case 4b: In this case, the (8r) or (9) rule must have been applied within some
subterm s 1 and must have rewritten into s 0
1 is a substitution for a variable
x in l. Assume that x occurs n times in r and let s 0
denote the substitutions
for these occurrences in t k+2 . So t
We can now interchange the
order of these reductions as follows:
We can now apply
rule (8r) on subterms s
Case 4c: The following diagram shows how we can get another program rule
that achieves the effect of both these reductions.
J"
3.4 Shared Strictness Property and Main Theorem
We now require notation to denote strictness properties of a term w.r.t. different
programs. We denote the strictness property ' of t w.r.t. P as '(P ), where P may
be dropped when it is irrelevant or obvious from context.
Definition (Shared Strictness Property).
' is a shared strictness property of t w.r.t. P iff either of the following (equivalent)
conditions hold:
1. ' is a strictness property of every term s =E t w.r.t every program Q =E P .
2. 8A:A(') ) 8oe  c A; toe '' E-NF.
Equivalence of the above two conditions follow directly from theorem 1. Now we
are ready to present our main theorem.
Theorem Main Theorem. t ee shared strictness property of
The main part of the proof effort is in establishing the if part of the above
theorem. The proof of only if part is fairly easy and is based on the concept of
strictness properties of two terms s and t being syntactically identical (denoted
these two formulas are identical even without expanding out the
strictness property of some subterms in s and t. Consider for example, the terms
f(x) and f(c(x)), where f 2 F and c 2 C. Note [f(c(x))] ee j (f(x 1
Lemma 3. (a) 8s; t; s =E t ) s ee j t ee .
(b)
Proof. For part (a), we show that s ee and t ee are syntactically identical whenever
s can be obtained from t by one application of an E-axiom. By induction on
number of applications of E-axioms required to get t from s, part (a) of the lemma
follows. is the E-axiom applied.
Note that t ee j t 0ee [x / (loe) ee ] and s ee j t 0ee [x / (roe) ee ]. Observe that for both
E-axioms, (loe) ee j (roe) ee and so s ee j t ee .
For part (b), it suffices to show that the expressions obtained for t ee (using
the rule of substitution and rules (1), (2) and (3) in section 2.1) are syntactically
identical for programs P and Q. Since the expression for t ee are obtained from f ee
and the rule of substitution, t ee (P ) and t ee (Q) will be identical whenever f ee (P )
and f ee (Q) are identical for all functions f . Let l
be the rules defining f in P and Q respectively. By definition,
f ee (P
that 8j there is an l 0
By part (a) of this theorem, r ee
. Also observe that the equations in E do
not change the variables in t j
are
identical. Furthermore, note that for each l there is an l 0
and hence each disjunct in the expression for f ee (P ) also appears in f ee (Q). By
interchanging P and Q in the above argument, we see that the converse of this also
holds and therefore f ee (P
Thus we have established the only if part of our main theorem. The proof of the
if part is quite difficult. We first present an outline of our approach to this part of
the proof and then present a detailed proof.
3.5 Approach to Proof of Main Theorem
Our proof strategy is to show that ee-analysis infers the maximal shared strictness
property. In other words, if t ee (P then we wish to show (cf. definition 4):
We call a strictness property that satisfies (10) as an E-maximal strictness property
(abbreviated EMSP). For the purposes of proof we choose to show that t ee (P
satisfies the stronger property:
Note that stronger property (11) implies (10). We now show that (11) also implies
the if part of theorem 2. Assume (11) and that / is a shared strictness property. By
(11), if From the contrapositive
On the Power and Limitations of Strictness Analysis \Delta 13
of the second condition in definition 5, it follows that true and hence we
have t ee
For the proof of (11) we need the concept of depth of a reduction sequence
t. Label all occurrences of function symbols in t (exclude function
symbols within oe) with 0. Let t i+1 be obtained from t i using the rule l ! r. If
the root of the redex is labelled (say, with j), then label all occurrences of function
symbols in r with rewrite. If the root of the redex is not labelled then
proceed as usual. Then the depth of t is the maximum among all
the labels assigned to any function symbol in any of t 1 ; :::; t n . We use the notation
to denote that s can be E-normalized using a reduction sequence of
depth  k w.r.t. t; analogously, s# k;t NF can be similarly defined.
Now recall the fix point computational method used in ee-analysis. Just as f ee
specifies all the arguments that must have an NF whenever f(s
we remark that f ee;k specifies all the arguments that must have an NF whenever
In Example 2, if f(s
must have NF; if f(s one of s 2 or s 3
must have NF as so on. The above remark implies that f ee;k are maximal in some
sense and motivates the following definition of a k-maximal property ' of t.
Observe that property (12) implies (11). We show that t ee;k is a k-maximal prop-
erty. Then, by soundness of ee-analysis, t ee is a strictness property of t that satisfies
and hence is an EMSP.
3.6 Proof of Main Theorem
We first show that the rule of substitution preserves k-maximal properties.
Lemma 4. Let t 1 arbitrary terms and ' 1 ; :::; 'n be the respective k-
maximal properties. Also let / be a k-maximal property of
is a k-maximal property of
Proof. The theorem is proved by showing in three steps that
1. Given
A we construct an A such that
/).
2. Given a oe  c
A, we construct a fi such that can be reduced to
by an E-derivation whose depth w.r.t.
show that fi  c A.
3. Since / is a k-maximal property of
every fi 0  c A, there exists an E-derivation of depth  k (w.r.t.
normalize We select a suitable fi 0 and from such a derivation for
another E-derivation to normalize in a
depth  k w.r.t.
A be such that A(x j
To show that
/m be all the conjuncts in the DNF of /. Then
/m where
Note that
/) is true iff 9
that is true. But then A(/
iff
definition of A).
14 \Delta R. Sekar et al.
A. Since ' j is a k-maximal property for t j , there exists an E-
derivation (of depth  k w.r.t. t j ) that normalizes t j oe whenever
denote the normal form reached by such a derivation. Now let fi(x
concatenating
E-derivations to normalize each t j oe such that
true, we obtain an E-
derivation \Delta that reduces by definition of
depth, that this derivation is of depth  k w.r.t.
that fi(x j ) is in NF whenever
true, and so fi  c A.
be such that fi 0
otherwise. Notice fi 0  c A and true. Therefore there exists an E-derivation
a depth of k with respect to d(x
Observe that in \Gamma 0 all subterms that do not possess a HNF must be discarded.
Therefore all reductions performed within fi 0 are
irrelevant and can be removed from \Gamma 0 to obtain a new derivation \Gamma. Now, observe
that whenever A(x discarded by \Gamma without ever reducing any
redex inside it and that fi 0 can be used to
normalize in a depth  k w.r.t.
Now consider the E-derivation
obtained by concatenating \Delta (from Step 2) and
\Gamma. Note that no function symbol in any t j such that A(x j true appears in
and so the maximum label assigned to any of these function symbols
in
observe that the labels of function symbols
in t j for those j such that A(x j remain zero since no redex with these
function symbols is ever reduced in \Delta or \Gamma. Furthermore, since the label of d in
is zero and since depth of \Gamma w.r.t. its label never
increases beyond k. Therefore the depth of
Now we show that equation 3 (in section 2.1) computes (k +1)-maximal property
of f , given the k-maximal properties of the e j 's.
Lemma 5. Let ' j 's be respective k-maximal properties of e j 's. Then
1)-maximal property of f(x
Proof. This theorem is proved in three steps by showing that
1. Given an A such that true, we select one rule
construct an s =E A an instance soe can be reduced
into an instance e j fi.
2. We show that fi  c A 0 for some A 0 such that A 0
3. Finally, we construct an E-derivation to normalize f(x 1 ; :::; xn ) in depth  k+
(w.r.t. based on the the derivation sequence to reduce f(x 1 ; :::; xn )oe
into e j fi and the fact that ' j is a k-maximal property of e j .
Given any A such that true, there is a j such that A(g j (' j
Let / be a conjunct in the DNF of g j (' j ) that is made true by A. By equation (4)
(in section 2.1) defining the g j 's, there is a conjunct / 0 in the DNF of ' j such that
stands for any term lacking head normal form.
On the Power and Limitations of Strictness Analysis \Delta 15
further specified by one
of the following two cases.
Case 1. x i is in /: s
Case 2. x i is not in /: Let x
be the variables in t i . Then, by equations
6 (in section 2.1), 9x il (1  l  r i ) that is not in / 0 or otherwise x
c is a constructor. It can be easily seen
that s i =E x i and so s =E
Observe that A(x i ) is true for x i in / and since oe  c A, oe(x i ) can be normalized
into some term u. Since u consists of only constructors, it can be reduced into an
instance t i [x im / c] (for every variable xim in t i and for some constructor c) using
E-reductions. Thus there is an E-derivation that reduces s i oe into t i [x im / c] for
Also note that for x i 62 /, s i itself is an instance of t i and therefore s i oe is
an instance of t i . By concatenating such E-derivations for each x i in / we obtain
an E-derivation \Delta that reduces soe into an instance This can now be
reduced using the rule
be defined by A 0 (xim
and since / 0 is a conjunct in ' j , A 0 We consider the cases 1 and 2 (of
step 1) to show that fi  c A 0 , or equivalently that fi(x im
appears in / 0 . In case 1, every xim in t i is in / 0 and the substitution for every one
of them is c and so is in E-NF. In the second case also, the substitution for every
variable xim that appears in / 0 is c. Therefore fi(x im ) #E-NF in both cases.
Step 3 Since ' j is a k-maximal property of e j and A 0 true, and since fi  c
A 0 , there is an E-derivation \Gamma 0 of depth  k w.r.t. e j that normalizes e j fi. Consider
the E-derivation obtained by concatenating \Delta, the reduction
This derivation normalizes f(x 1 ; :::; xn )oe and is of depth
because in the step f(t the label of all function
symbols in e j is one and these labels increase by at most k in \Gamma 0 .
Lemma 6. t ee;k is a k-maximal property of t.
Proof. By induction on k. For the basis, note that f false and so 12
holds vacuously. Using lemma 4 and the definition of t ee;k in terms of f ee;k , we
can establish by simple induction on the structure of t that t ee;0 is a 0-complete
property of t.
For the induction step, assume that e ee;k
j 's are the respective k-complete properties
of e j 's. By lemma 5, we see that f ee;k+1 is a k + 1-complete property of f . As
in the basis step, using the definition of t ee;k+1 (in terms of f ee;k+1 ) and lemma 4,
we can show that t ee;k+1 is a k + 1-complete property of t.
Now, by soundness of ee-analysis,
Corollary 7. t ee is EMSP of t.
4. CHARACTERIZATION THEOREM FOR DD-ANALYSIS
To illustrate the generality of our technique we briefly outline its use in proving a
similar characterization theorem for dd-analysis. As mentioned earlier, dd-analysis
is an enhancement of Mycroft's method to deal with head normal forms in non-flat
domains. In particular, a dd-strictness property of a function f specifies which
arguments of the function are to be head normalized in order to obtain the head
normal form of an application of f . Among other applications, it has proven valuable
in repairing violations of strong sequentiality (a concept pioneered by Huet and
Levy [1979]) in functional programs. The equations to compute t dd are as follows
(See [Sekar et al. 1990] for details).
The are defined as follows.
i is a
nonvariable
i is a variable (19)
i is a nonvariable (20)
To obtain a characterization theorem, the first step is to specify E-axioms appropriate
for dd-analysis.
The effect of this equation is to equate any two terms that are in head normal form.
In the remainder of this section, we specify the necessary changes to definitions
and theorems (used in proving the characterization theorem for ee-analysis) so as to
obtain a similar result for dd-analysis. In all definitions, theorems and lemmas we
replace NF by HNF, E-NF by E-HNF and "term without normal form" by "term
lacking head normal form".
We can prove theorem 1 with respect to the E-axioms for dd-analysis using essentially
the same proof used for ee-analysis. In lemma 3, for part (a) note that
dd of right-hand side is precisely the dd of the left-hand side in equation (21). For
part (b) we only need to argue that g j functions of equivalent programs remain
unchanged. To do so, we only need consider equations (16), (19) and (20). Observe
that these rules depend only on whether t i
j is a variable or non-variable. But this
property is left unchanged by the E-axiom.
Lemma 4 carries over without any changes in the arguments. For lemma 5, the
following observations are necessary. In case 2 of step 1, we observe that x 62 /
implies that x i1 62 / 0 and t Therefore, in both cases s i is identical to x i .
Also observe that whenever A(x i ) is true for x i 2 / and oe  c A, then oe(x i ) can be
head normalized to some term u. As u is in HNF it can be E-reduced to t i [x i1 / c].
The remainder of the reasoning carries over unchanged. With these changes, we
have the following result for dd-analysis as well.
On the Power and Limitations of Strictness Analysis \Delta 17
Theorem 8. t dd is a shared (dd) strictness property for t.
5. SIGNIFICANCE AND IMPLICATIONS
Strictness analysis methods such as that of Mycroft are often defined by a non-standard
semantics obtained by re-interpreting programs over a simpler abstract
domain. This definition is useful for computing strictness properties but not helpful
in answering questions dealing with the power of the method in a manner independent
of the computational procedure used. Such questions take the form: given
a class of programs P is the method complete for this class? What is the information
lost by the method? How can its power be enhanced? etc. In contrast,
we give a proof technique to answer these questions in a computation independent
manner. Specifically, E-axioms are a syntactic characterization of the information
lost by the method and E-rewriting provides a powerful algorithm-independent tool
for answering questions such as above. By this we mean that if we want to know
whether an analysis procedure will compute a strictness property, we need not know
its computation procedure at all. We need only check if the strictness property is
preserved if the program is modified as permitted by the E-axioms (e.g., changing
constants in Mycrofts and ee-analysis method). Thus, using our approach we can
draw the following conclusions about Mycroft's and our method.
-The information loss in ee-analysis method is only due to the mapping of all
constants to a single value; all other abstraction steps are lossless.
-Any method that uniformly ignores constants can be no more powerful than ee-
analysis method. More precisely, if such a method computes the same strictness
properties for the lhs and rhs of the E-axioms then it will not have any additional
power. Therefore the only source of improvement is to enrich the analysis domain
by adding more "points" to it.
-We show that Mycroft's and our methods are complete for non-erasing programs,
wherein all the variables in the lhs of a rule appears on the rhs. There are
many important functions that are non-erasing such as append, reverse, matrix
multiplication, etc. Observe that if P is non-erasing, so is any Q =E P . By
our main theorem, ee-analysis method deduces all shared strictness properties
and so it is complete for the class of non-erasing programs. Note that this proof
makes no reference to the computational procedure used in deducing strictness
properties.
-We can enhance the above class by permitting the use of if-then-else (an erasing
function) in the following way: if-then-else must not be used to "potentially
throw away" function arguments. For example, if x then y else z throws away
one of y or z, whereas if x then y*z else y/z does not throw away any arguments.
ee-analysis method is also complete for this class of programs as well.
-On the other hand, ee-analysis method is incomplete even for the simple class
of non-recursive programs with linear rhs. Functions F 1 and F 2 (Section 1.2)
illustrate the incompleteness.
Finally, the technique developed in this paper provides a general principle for establishing
similar characterization theorems for other strictness analysis methods.
This is further discussed below.
5.1 Generality of Approach
In order to generalize our approach to deal with other methods for strictness analysis
as well as extensions of our ee-analysis mentioned before, we first need to discover
equational axioms to capture the loss of information in the analysis method. Discovering
E-axioms that not only capture loss of information in an intuitive way
but are also useful in proving completeness results, may require considerable inge-
nuity. For example, we leave as an open problem the discovery of such E-axioms
for a method proposed by Wadler [1987] that reasons about lists using a four point
domain.
The E-axioms induce an equivalence relation over classes of programs. It then
remains to show that inferred strictness properties are related to equivalence classes
of programs. The first step in this direction is to give a formal statement of the
characterization theorem. In this direction, it is useful to develop the notion of
E-rewriting and establish a result similar to theorem 1 which relates E-rewriting
and performing reductions w.r.t. several programs. Such a result will make the
statement of the characterization theorem and its proof cleaner and a lot less cum-
bersome. However, establishing such a theorem may be nontrivial. It appears that
the only way the presence of E-axioms changes reduction sequences is in that E-
axioms can make a non-redex into a redex or convert a redex for one lhs into a redex
for another. Both these can be accomplished by allowing application of E-axioms
only "around" redexes, suggesting that a result similar to theorem 1 will hold. If
this theorem fails to hold, a characterization that explicitly refers to all programs
E-equivalent to the given program can be given.
The next step is to show that the strictness properties computed are all shared
strictness properties. This can be established using the analysis in a fairly straight
forward manner if the E-axioms are correctly set up. The more difficult part of
establishing the characterization theorem is to show that every shared strictness
property (or equivalently, the maximal shared strictness property) is computed.
The proof of this involves showing that each step in the analysis procedure (such
as composition, function definition by pattern match, etc.) preserves maximal
shared strictness properties. This part of the proof is simplified if we avoid pattern
matching, but instead restrict ourselves to the language of recursion equations. In
this case, we need only show that we have the maximal shared strictness properties
of the base functions (such as if and arithmetic operators) and that the composition
step loses no information other than that given by the E-axioms. Thus the only
proof that needs to be extended is that of lemma 4.
6. RELATED WORK
Since the preliminary version of this paper appeared in POPL '91, much research
[?; ?] has taken place in the area of completeness of abstract-interpretation-based
analyses. ?] use a denotational approach to prove results similar to ours for the
more general problem of abstract interpretation based analyses. Their proofs are
based on a notion of similarity semantics that permits the semantics of values to
be "confused." The confusion permitted is exactly that captured by the abstract
domain. They show that abstract interpretation over linearly ordered domains for
a first-order and a typed higher-order language is complete upto this notion of
On the Power and Limitations of Strictness Analysis \Delta 19
confusion.
Reddy and Kamin's proofs are based on denotational semantics. In particular,
their completeness result is stated in terms of a similarity semantics that is derived
directly from the structure of the abstract domain. This approach enables them
establish a result with much wider applicability than ours. However, our approach
has its own advantages that we mention below. First, the E-axioms provide a
characterization that is not closely tied to the abstract domain itself. Moreover, the
E-axioms provide a syntactic (or "localized") characterization of the information
loss, whereas Reddy and Kamin's approach is based on replacing entire values
(or expressions) with others that have the same similarity semantics. We believe
that a syntactic characterization is more useful for drawing implications about
the completeness of a method on classes of programs. For instance, it readily
follows from our result that Mycroft's and ee-analysis are complete for non-erasing
programs. In contrast, it is unclear how such simple arguments can be used to draw
this conclusion based on the similarity semantics approach.
A second important difference between the results is as follows. Reddy and
Kamin's result is based on the semantics-based formulation of abstract interpreta-
tion. Often, methods based on abstract intepretation do not make direct use of the
semantics based formulation since it can lead to inefficiencies in practice. More efficient
computational algorithms are hence developed for implementation purposes.
(See, for instance, [Clack and Jones 1985; ?].) One must then address the issue of
completeness of such algorithms. An operational approach such as ours can more
easily deal with completeness issues at such algorithmic and implementation levels
as well, in addition to addressing them at the formulation level. Indeed, our
ee-analysis is specified in [Sekar et al. 1990] to provide the computational methods
as well, and our completeness results thus apply to the actual implemtation of
ee-analysis. It is this additional burden that makes our proofs quite detailed.
As a final remark on Reddy and Kamin's work, they note that their method does
not extend to non-linearly-ordered domains. They remark that the basic problem is
the possible loss of information in computing least upper bounds. It is interesting to
note that our generalization of ee-analysis to arbitrary demands (as reported in [?]),
produces results quite similar to abstract interpretation, but does not suffer from
the above drawback when dealing with domains with lossy lub's. It is an interesting
open problem whether demand analysis possesses completeness properties for all
finite domains.
The results of ours and that of Reddy and Kamin enable us to characterize the
power of an abstract intepretation in terms of information obtained by a concrete
interpretation. While such a characterization can typically be useful to compare
the power of different abstract interpretations, they may not answer the question
of the relative power of two abstract interpretations with respect to the ability
to deduce specific properties. For instance, Reddy and Kamin's result seems to
suggest that the power of an abstract interpretation is determined simply by the
structure of abstract domain. However, ?] gave an example where two abstract
interpretations used different domains, but were able to identify the same strictness
properties. To address this problem of more easily comparing abstract interpreta-
tions, Mycroft has proposed the concept of predicate-based abstract interpretation.
In this approach, in addition to the two components of interpretation (namely, a
domain and the interpretation of functions), Mycroft adds a third component in
the form of predicates that capture the program properties of interest. Another
way to view the predicates is that they define a notion of observability. Mycroft
then proceeds to set up a framework in which one can compare the power of two
abstract interpretations with respect to this notion of observability.

ACKNOWLEDGMENTS

The authors would like to thank all the referees for their comments and suggestions,
which have resulted in significantly improving the content as well as the presentation
of this article.



--R

A compiler for lazy ML.
Theory and practice of strictness analysis for higher order functions.
Strictness analysis - a practical approach

Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints.
Compiling strictness into streams.
Higher order strictness analysis for untyped lambda calculus.
In the 12th Annual ACM Symposium on Principles of Programming Languages.
Computations in nonambiguous linear term rewriting systems.

Projections for strictness analysis.
Fast parallel implementation of functional languages - the EQUALS experience
Strictness analysis: A type inference perspective.
The theory and practice of transforming call-by-need into call-by-value
A symbolic constraint-solving framework for analysis of logic programs
Beyond strong sequentiality.
On the power and limitation of strictness analysis based on abstract interpretation.

Strictness analysis on non-flat domains (by abstract interpretation over finite domains)
--TR
Strictness analysisMYAMPERSANDmdash;a practical approach
The theory of strictness analysis for higher order functions
Projections for strictness analysis
Compiling strictness into streams
Strictness analysis
On the power and limitation of strictness analysis based on abstract interpretation
Fast parallel implementation of lazy languagesMYAMPERSANDmdash;the EQUALS experience
Completeness and predicate-based abstract interpretation
Programming in equational logic
A symbolic constraint solving framework for analysis of logic programs
Fast strictness analysis based on demand propagation
Higher-order strictness analysis in untyped lambda calculus
Abstract interpretation
The Theory and Practice of Transforming Call-by-need into Call-by-value
A compiler for lazy ML

--CTR
Wan Fokkink , Jasper Kamperman , Pum Walters, Lazy rewriting on eager machinery, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.45-86, Jan. 2000
Roberto Giacobazzi , Francesco Ranzato , Francesca Scozzari, Making abstract interpretations complete, Journal of the ACM (JACM), v.47 n.2, p.361-416, March 2000
program analysis;strictness analysis;completeness;abstract interpretation