(Optimal) duplication is not elementary recursive.
In 1998, Asperti and Mairson proved that the cost of reducing a -term using an optimal -reducer (a la Lvy) cannot be bound by any elementary function in the number of shared-beta steps. We prove in this paper that an analogous result holds for Lamping's abstract algorithm. That is, there is no elementary function in the number of shared beta steps bounding the number of duplication steps of the optimal reducer. This theorem vindicates the oracle of Lamping's algorithm as the culprit for the negative result of Asperti and Mairson. The result is obtained using as a technical tool Elementary Affine Logic.
Introduction
In the last ten years there has been a steady interest in optimal
reduction of -terms (or, more generally, of functional
programs). The very story started, in fact, more than twenty
years ago, with Jean-Jacques Levy's thesis [Lev78]. The
problem he attacked was to nd an execution strategy for
-terms minimizing the number of -reductions. It was already
known that no such strategy exists which reduces only
one redex (i.e., a single function call) at the time. Levy's insight
was to discover that a parallel optimal strategy exists,
the one reducing in a single step all the redexes belonging to
the same family, a crucial notion he introduced. However,
Levy lacked the programming technology to implement his
strategy. He showed it was eective, but no one knew at
that time what kind of data structure could be used to dynamically
maintain the families in such a way that all the redexes
of a given family could be somehow shared and, there-
fore, reduced as a single step. The solution came in 1989,
when independently Kathail [Kat90] and Lamping [Lam90]
gave abstract -calculus machines which reduced terms as
prescribed by Levy's optimality theory. Lamping's graph
rewriting approach is the one that received most interest,
and after his breakthrough other variants of optimal reducers
have been proposed, especially by Gonthier, Abadi and
Levy [GnAL92a] and Asperti [Asp95]. We will refer to all
of them as the optimal sharing graph approach.
All these variants share a common core | the abstract
algorithm in the terminology of [AM98] | and dier in the
way they implement the bookkeeping work needed to maintain
the families. The algorithms are described as elegant
graph rewriting systems, where any rule rewrites only a pair
of facing nodes (and then it can be easily implemented as
a constant time operation). The abstract algorithm is responsible
for the performing of the shared -rule and for
the incremental duplication of subterms. It is the job of the
bookkeeping part | also called the oracle | to maintain
in the graph enough distributed information to make the
abstract algorithm correct with respect to the standard -
reduction (see Section 2, or [AG98] for a complete account).
Since all the reduction rules can be implemented as constant
time operations, we may take the number of rewriting
steps to reach the normal form of a term as the cost of the
reduction algorithm. Levy's theory, given a -term M , prescribes
the number of shared -reductions needed to reach
the normal form. All optimal sharing graph algorithms perform
exactly this number of -rewritings, but the global
number of reductions is greater, since the algorithms also
perform both duplication (in the abstract algorithm) and
bookkeeping. Is it possible to bound the total work as a
(xed) function of the number of shared -reductions? It is
this question that has been behind several contributions by
Asperti, Lawall, and Mairson [Asp96, LM96, LM97], culminated
in [AM98]. Dene the Kalmar elementary functions
shows that there are -terms that can be normalized with n
shared -reductions, and for which the total work needed to
reach the normal form with any algorithm (and hence with
any optimal sharing graph algorithm) exceeds K ' (n) for any
xed '  0.
The theorem shows that optimal  reduction cannot be
realized as a unit cost operation. However, it does not mean
that optimal reduction, as a whole, is unfeasible. By a classical
theorem of Statman [Sta79], any -calculus machine
has to take non elementary time in the size of a term to
reach the normal form. In the case of optimal reduction,
the non elementary bound (as a function of the number of
shared -reductions) is just a consequence of the fact that
with this sharing technique the number of redex families is
surprisingly low (essentially linear in the size of the term).
Hence the most part of the work | that has to be done in
any case, by Statman's theorem | is devolved to duplication
and bookkeeping. Still, in the case of Lamping's algo-
rithm, it remained the problem to understand if this cost
was essentially due to duplication, or to the (pretty com-
bookkeeping technique. In this paper, we prove that
already the mere cost of duplication is not elementary. In
other words, it is not only Lamping's bookkeeping technique
to be unfeasible, but already the plain work of duplication.
This is particularly interesting since, by now, there is some
good evidence that the number of duplications performed
by Lamping's algorithm is a lower bound to the complexity
of any (sub-optimal 1 ) reduction technique [LM97, AL97].
As a working tool, we use in this paper Elementary A-ne
Partially supported by EC Grant ERB 4061 PL 97-0244 \LINEAR"
and MURST COFIN 1998.
1 Theoretically, there could be super-optimal implementations,
where one dynamically looks for common subexpressions. Levy's theory
of optimality does not cover these cases, which are neglected as a
l
b a
b a
a b
a
d d
d

Figure

1: Lamping's (abstract) algorithm nodes.
Logic [Asp98] (EAL), a variant of Elementary Linear Logic,
introduced in [Gir98]. In particular, we show that the simply
typed -terms used in [AM98] to code a certain decision
problem can be given a type also in EAL. A crucial feature
of the -terms typeable in EAL is that their reduction does
not need the bookkeeping part of the sharing graph algo-
rithm. Therefore, we can rene the rst corollary to the
main theorem in [AM98] in the following manner:
There exists a set of -terms En : Bool which normalize
in no more than n parallel -steps, where
the number of bookkeeping duplication interactions
that are required to normalize En using Lamping's
graph reduction algorithm grows as
any xed integer '  0.
The reader may be confused by the outward paradox of
typing non elementary terms in an elementary logic. There
is no paradox indeed, since the complexity of reducing terms
inside EAL is elementary once the depth of the term is xed.
In our case, the depth of the involved terms grows polynomially
in the size of the input.
The paper is organized as follows. In Section 2 we introduce
Lamping's graph reduction technology. Section 3
presents Elementary A-ne Logic, analyzing the complexity
of its cut-elimination and discussing the problem of type in-
ference. Section 4 recalls Asperti and Mairson's result and
sketches how to type their terms in EAL, obtaining our main
result.
Optimal reduction
We assume the reader to have some familiarity with the
simply typed -calculus. We only recall that the set of types
is dened inductively by the grammar  ::= oj ! , where
is a xed base type, and the (untyped) terms are generated
by the grammar M ::= xj(M M)jx:M . We assume to have
an enumerable set of variables, ranged over by x. Types
can be assigned to terms in the usual way. Reduction is
dened by the -rule: (x:M
While the details of Lamping's approach for optimal reduction
are complex and technical (see the book [AG98]),
the few concepts needed to understand the result of this paper
are easy to grasp. The rst step in Lamping's (abstract)
algorithm is to represent a term as a labelled graph built out
of the nodes given in Figure 1. The arrow exiting a node is
the principal port of the node. The graph is obtained from
the syntax tree of the term by: (i) representing a variable by
an arc (a wire); (ii) adding an explicit node (the triangular
node, called fan) for the sharing of a variable occurrence;
and (iii) connecting the single wire representing a variable
form of \syntactical coincidence".
A ' A (Ax)
(Cut)

Figure

3: Intuitionistic Linear Logic
(after sharing) to the node  which binds the variable. Reduction
of the term is represented by graph rewriting. The
(typed) rules of the abstract algorithm are displayed in Figure
2. Note that two nodes are rewritten (they interact) only
when their principal ports face each other. The rst rule is
the shared -rule; the others, as it should be clear from their
shape, perform an incremental (and controlled, to get opti-
mality) duplication of the graph. When the duplication is
over, the rst of the two fan-fan rules annihilate the fans
(intuitively, the two fans originate from the same node in
the starting graph); otherwise, in the last rule, one fan duplicates
the other. Observe, however, that this presentation
of the algorithm is non deterministic, since the two fan-fan
rules have the same left-hand side. To make the algorithm
deterministic, one may think to label the fans in the original
graph and then, throughout the reduction, apply the
rst fan-fan rule when the two fans have the same label; apply
the other otherwise. It is one of the crucial Lamping's
observations that this simple technique does not work for
the simply typed (and, a fortiori, the type free) terms. A
much more complex bookkeeping oracle machinery have to
be adopted, adding more nodes (brackets, croissants) to the
graphs and decorating any node with an index. The full al-
gorithm, therefore, consists of both the abstract algorithm
we just sketched and its bookkeeping part, which we omit.
We will introduce in the next section a formal system to
type terms for which the simple labelling of fans is enough
to get correctness.
3 Elementary A-ne Logic
3.1 The logical system
Linear Logic [Gir87] provides a logical interpretation of
Lamping's algorithm as a cut-elimination process for a suitable
notation for proofs (proof-nets). This was rst hinted
at in [GnAL92a] and then developed in [GnAL92b]. We give
here an intuitive introduction to the subject, to motivate the
use of EAL as a tool towards our result; see, e.g., Chapters
4 and 8 of [AG98] for a full account on the subject.

Figure

3 presents (in a somewhat non standard way) the
intuitionistic fragment of Linear Logic (ILL).
It is a modal system, where the modality (!) is used
to mark those formulas on which contraction and weakening
may be applied. The standard implicational fragment

a b
a b
a b

l l
a b a b
a
a
a
a

d d
d
d d
d d
d d
d d d d

d
d
a b @

a b
a b *

a b
a b
@
@
a
c
d
b a
a
a
a
a b
@
l
a
a
a
d
d d
d
d

Figure

2: Rules of the abstract algorithm.
l
l

Figure

5: [] n translation.

Figure

4: Bracket and croissant.
of Intuitionist Logic may be embedded into ILL via the interpretation
this, and the Curry-Howard
isomorphism, for any typed -term we may give a
corresponding ILL proof. Such proofs may be expressed as
graphs (proof-nets), essentially corresponding to the syntax
tree of the -terms but for the presence of !, which is expressed
by the so-called boxes. Boxes are given in standard
ILL proof-nets as global entities (they are certain subgraphs
with specied nodes as interfaces), but they can also be described
in a local way, by introducing new nodes (and node
indexes) besides the ones corresponding to the connectives
of the logic. These new nodes, corresponding to the rules
and -, are the nodes needed in the oracle of Lamping's
algorithm|brackets and croissants, see Figure 4.
A typed term M is translated into an optimal sharing
graph according to the inductive rules of Figure 5,
where also the corresponding ILL derivations are given. The
rightmost case corresponds to the abstraction of a variable
not appearing in the body; the
node
is called eraser and
can be thought of as a fan with zero premises. Observe, in
the application case, how the !-rule is translated into a box:
the level of the translation increases from [N ] i to [N ] i+1 .
The rationale of this translation is the following. Since
contraction (fan) may be perfomed only on !-formulas, the
translation of a variable puts a ! on any variable, getting
ready for a possible contraction. In the translation of an
application, we put a box around the argument N (!-rule)
and then, since there is now one more ! in the type of
the free variables of N , we apply the rule - (the bracket),
nally contracting the common variables. In view of the
technique allows the
translation of any typed term (and also of untyped terms,
provided we see them as having type O  O ( O).
Restrict now the logical system, removing the rules  and
-. We cannot any longer prepare to contract any variable
as we did in the translation of Figure 5. The contractible
variables will be only the ones that get a ! in their type
by means of rule !. And we cannot any longer decrease the
number of ! in the type of a variable, since rule - is no
longer there. As a reward, however, there are no brackets
and croissants in the translation of any -term. We moved
from the complete Lamping's algorithm to the abstract one.
It remains only to be seen how the application of the two fan-
fan rules may be discriminated. It not di-cult to see that,
in this framework, the level of a node never changes during
reduction. Therefore, we may apply the rst of the two fan-
fan rules (annihilate) if the two fans have the same level; we
apply the second one otherwise. In this restricted system,
levels behave like labels, and these labels are su-cient to
ensure correctness of reduction. If a -term M can be typed
inside the restricted system obtained by omitting the rules
and -, then the (optimal) reduction of M can be performed
without any need of the bookkeeping.
The -terms which can be given a type in this restricted
system, therefore, are the natural choice if we want to bound
the duplication work only.
What we have called so-far the restricted system, is a
(fragment of) Elementary Linear Logic (ELL), sketched by
Girard in [Gir98] as part of a work directed to the logical
characterization of polynomial and elementary functions.
completely describes the elementary functions. From
one side, any elementary function can be coded as a proof
of ELL; from the other, normalization of ELL proofs is an
elementary time procedure, once the box-nesting depth of
the proof is xed.
A more
exible syntax (also for a polynomial logic, LAL)
was introduced by one of the authors in [Asp98], by allowing
full weakening. The resulting system, Elementary A-ne
Logic (EAL), is presented in Figure 6, where also -terms
have been added to the rules. We say that a term M has an
type A under the context A is derivable
in the system of Figure 6. We remark that these terms
are not intended as a notation for proofs in EAL; terms
for this purpose can be easily obtained from those for LAL
in [Asp98]. Here we use EAL just as a typing system for
pure -terms. The following is subject reduction.
Fact
Although this may be non obvious at rst, there are simply
typed terms for which no EAL type can be derived. An
example will be given at the end of Section 3.3.
Like ELL, also EAL characterizes the elementary func-
tions: Any elementary function can be represented in EAL,
and the normalization procedure is elementary time.
Finally, and this is the crucial issue we need in the fol-
lowing, we stress again that if M gets an EAL type, then
M can be reduced by the abstract algorithm by a simple
labelling of the fan nodes.
3.2 Complexity of reducing EAL proofs
For lack of space, we cannot enter in the details of the
normalization procedure, in this paper. Let us just say
that by using the technique \by rounds" introduced by Girard
[Gir98] and rening a bit its argument, we obtain that
the complexity of the reduction is bounded by the following
where s is the size of the term and n is the nesting level of
boxes. The important fact is that we get a tower of exponentials
whose height only depends on the nesting depth of
the term. Hence normalization is elementary in the size of
the input, once the depth is given.
3.3 Decorating terms
It should be clear from the rules of EAL that a derivation
of a type in EAL (an EAL-type, from now on) for a -term
M consists of a skeleton | given by the derivation of a type
for M in the simple type discipline | together with a box
decoration, introducing a suitable number of !-rules. Such
modalities are needed since only !-typed variables can be
contracted. Observe, moreover, that a given (simply typed)
skeleton has an innite number of possible decorations, and
not all of them are instances of a single, most general one.
(Cut)
(Contr:)

Figure

Elementary A-ne Logic
z
z
@
y
@
y
@
x
@
x
x
@
I
I
I I
I
I
I I
I
I
I
I I
I I
I I
a)
z
z
@
y
@
y
@
x
@
x
x
@
I
!I I
I I
I I
!I I
I
I
I I
(!I I
!I I
I

Figure

7: Type inference in EAL, I
z
z
@
y
@
y
@
x
@
x
x
@
I
!I I
I I
I I
!I I
I
I
!I I
(!I I
!I I
I
c)
z
z
@
y
@
y
@
x
@
x
x
@
I
!I I
I I
I I
!I I
I !o
I
!I I
d)
(!I I
!I I
I !o

Figure

8: Type inference in EAL, II
Therefore, while the skeleton is trivially obtained, nding
the right decoration is the hard part, since the introduction
of a box in a portion of the proof forces other boxes to be
introduced somewhere else. We conjecture type inference in
EAL decidable, but we have not a complete proof of this yet.
The typing of the relevant terms in Section 4 is therefore
obtained using some heuristics, which we describe in this
section.
We may single out three main steps in the process of
type inference: \looking for contractions", \boxing argu-
ments" and \opening boxes". We discuss these steps by
going through an easy example.
Let
be the simply typed term to be typed in EAL. We start
from the syntax tree of the term, labelled with the types of
the simple discipline (just changing ! into () as in Figure
7 (a), where I def
Now look for contractions. If all the variables occur
only once | they are used linearly | we are done. This
is not the case in our example, since x occurs twice in
As contraction in EAL is admitted
only for formulas of type !, we need to introduce a !
before the abstraction of x. Using the usual sequent calculus
notation, the simple type derivation of M in Figure 7 (a)
corresponds to the following derivation
I I
I I
I I
which is not in EAL because the contraction rule is wrong.
To obtain a correct EAL derivation we add a !-rule before
contraction:
The corresponding typing is represented in Figure 7 (b),
where the type of x inside the box is II
outside. The new type for M , however, needs to be propagated
in the left branch of the tree for the full term N ,
or otherwise the topmost application would have the wrong
type. As a consequence, the variable n in Figure 7 (b) gets
type !I Io (!Io .
Observe now that the leftmost innermost application is
wrong. We need to box the argument z:z, which must have
type !I Io , as it is shown in Figure 8 (c).
Finally, in order to apply (n z:z) of type !I
to y of type o, we need to open the box , as in Figure 8 (d).
As mentioned above, types inside boxes \lose" one !, in particular
allowing us to perform the
application.
Observe how a single contraction inside the term M
forced us to introduce boxes all over the tree.
The nal decoration of Figure 8 (d) represents the following
derivation in EAL:
I
'I I
'!I I
Io ;o'o ((;l)
!I I
!I I
'(!I I
'!I I
'I !o
(Cut)
where E is the derivation given above for the subterm M .
As already mentioned, other decorations for N are possi-
ble. First, we may give N the type ! n I !o , by adding n !-rules
at the end of the derivation. Or, to be more general, we
may give N the type
the abstraction in the derivation of M . But there are other
possibilities. We may choose to introduce m !'s (\close" m
boxes) in Figure 8 (d) after the abstraction of y, obtaining
for N the type ! n+m Io .
Finally we remark that type inference in EAL is not always
possible. For example the simply typed -term
has no EAL decoration. To see this in a simple way, write
the term as a sharing graph and reduce it in the abstract
algorithm by matching fans by labels. The sharing graph in
normal form is a cycle, that is a sharing graph which does
not correspond to any -term (least to say to y, which is the
normal form of the given term). This means that the oracle
is needed for the reduction of this term, and hence it cannot
have a type in EAL.
Coding type theory into EAL proofs
4.1 Asperti and Mairson's result
The result of Asperti and Mairson [AM98] is obtained out
of three building blocks. The rst, and most novel, contribution
is that any simply typed term can be \pre-compiled"
in a certain way in order to drastically limit the number of
its shared -reductions.
Consider the size of types as the structural size, the size
of -terms counting 1 for each abstraction and application
and counting the size of the type for each variable and nally
consider the size of sharing graphs as the number of nodes.
Let x be a variable of type . The -expansion  (x) of
x is dened inductively on  as follows:
Given a simply typed lambda-term M , following the procedure
in [AM98], we construct a -equivalent variant or(M)
| the optimal root of M | replacing every subterm of the
During this process we introduce a certain number | clearly
linearly bounded by the size of M | of new preliminary -
redexes. (M) is the sharing graph obtained from or(M)
by reducing all the new preliminary redexes and propagating
all sharing nodes to the base type.
Theorem 1 For any simply-typed -term M , the total
number of shared -reductions in the graph normalization
of (M ) is limited by the size of (M).
The second ingredient is obtained from Mairson's proof
[Mai92] of theorems of Statman and Meyer [Sta79, Mey74].
The decision problem for propositional calculus can be naturally
generalized to higher-order types by allowing variables
and quantiers to range over values of Dk , for k  1. Let
be variables ranging over Dk ; we dene prime formulas
as true, false, true
Finally, let a formula  be built up out of prime formulas,
the propositional connectives ^, _, :, and the quantiers 8
and 9. Statman showed how to reduce the truth of a higher-order
formula to the reduction to a given normal form of a
suitable typed term. Mairson [Mai92] showed how to simplify
the proof of Statman with a dierent encoding based
on the same basic idea | the quantier elimination procedure
| but much simpler and easy to understand for the
use of list iteration as a quantier elimination procedure.
Theorem 2 A higher-order formula  is true if and only if
its typed -calculus interpretation ^
-equivalent
to true : Bool. Moreover, if  only quanties over universes
has order at most k, and
Finally, the last step is to show that any elementary time-bounded
Turing machine can be encoded into higher-order
logic, rening the proof in [Mai92].
Theorem 3 Let M be a xed Turing machine that accepts
or rejects an input x in K ' (jxj) steps. Then there exists a
formula x in higher-order logic such that M accepts x i
x is true. Moreover, x only quanties over universes D i
for 6, and has length O(jxj log  jxj).
>From the Theorems 1, 2, and 3 the main result
of [AM98] is obtained easily. In this paper, we show that
Theorems 1 and 2 hold for EAL-typed -terms. Then, combining
these results with Theorem 3 and the observation we
made at the end of Section 3.1, we derive our main result.
Theorem 4 There exists a set of -terms
normalize in at most n shared -reductions, where the number
of non -interactions that are required to normalize En
using Lamping's abstract algorithm grows as
any xed integer '  0.
4.2 Coding higher-order logic in EAL
We show in this section how higher-order logic can be coded
with EAL-typed -terms. The (type-free) -terms we use
are minor variants of those of [AM98] 2 , the main technical
contribution being the type-inference inside EAL.
Dene the type of Booleans as B
(!o. The
usual -terms true and false giving the Church encoding
of the boolean values can be given in EAL the types ! n B,
8n  0. The usual connectives AND, OR and NOT can be
typed, respectively, with type
We write L
for the EAL type of the generic lists of
elements
2 The modications to the encoding are the following: (i) we use
dierent terms for the encoding of equality; and (ii) the variable x1
is not a prime formula. As a consequence of (ii), one has to adopt
also a slightly dierent encoding of a Turing Machine in the proof of
Theorem 3. In particular, dene x 1 <
believe that, with more work, also Mairson's original encoding of the
Turing Machine would get a type in EAL.
Following [AM98], for any k the domain Dk can be encoded
by a -term Dk representing Dk as the list of its
values. Dene
where
powerset
double
Lemma 1 For any EAL-type ,
and  and for i  0:
double has type ! 3+i  (!(L
powerset has type L
Proof: See Figures 9 and 10, where the bold dashed lines
stand for i boxes.
Observe how the piling up of !'s is already present at
this stage of the encoding | in the type of powerset we
have two consecutive !'s. Since in EAL is not possible to
derive the number of consecutive !'s will keep in-
creasing; intuitively, n applications of powerset will produce
2n consecutive !'s in the nal type.
Given the type schema
we can prove the following:
8nk  2(k 1), Dk has type k .
Following [Mai92], quantiers can be encoded by using
iteration over lists. Given n  0 and some EAL type ,
suppose to have coded with the -terms ^
the set
of elements of type ; suppose moreover
that
is a term encoding a generic formula .
z)) true) is the term encoding the
Prime formulas are encoded by the following terms.
Observe that memberk is dened for k  2.
This encoding can be understood as the -calculus translation
of the following inductive denitions:
The quantied formulas 9z k 1 2 y k in the denition of 2k ,
and 8z k 1 2 Dk 1 in the denition of =k , are encoded by
list iteration, as described above.
Then memberk has EAL-type
maxf4k 9; 2(k 1)g.
Putting together all the ingredients of the encoding, we
obtain our main technical result, which establishes Theorem
2 for EAL-typed terms.
Theorem 5 Dene
be the term encoding an arbitrary formula
quantiers over
such that in EAL
Moreover the size of [x k 1
O(jj(2kMAX )!)
where kMAX is the greatest k such that memberk appears in
Proof: The main case of a universally quantied formula is
described in Figure 11, where
1), the
outer bold box stands for 2(k i 1) boxes 3 and the inner bold
box stands for p 1 boxes. Figure 12 is the complete coding
of an example.
The following bound on the number of !'s in the type
of a lambda term encoding an arbitrary formula provides a
limitation also for the box-nesting depth.
3 Notice that Dk i
and remember that
we need to \open the boxes" before apply.
@
l
l
l
l
@
@
l
l
x
l
c
c'
x
e c'
c'
le
@
l
l
c
c

Figure

9: EAL type of double
double
@
lA*
l
l
@
@
l
l
c
c c'
@
A*

Figure

10: EAL type of powerset
@
c
@
lc
@
c'
x
@
c'
e
l l
c' n' @
@
le @
c
@
l
@
l
c
l l l l @
@
@
lA*
@
A*
@
c
@
lc
@
c'
x
@
c'
e
l l
c' n' @
@
le @
c
@
l
@
l
c
l l l l @
@
@
lA*
@
A*
lc
@
true
c
@
@
false
c
@
@
lx3
@
@
true
@
AND
@
c
@
lc
@
c'
x
@
c'
e
l l
c' n' @
@
le @
c
@
l
@
l
c
l l l l @
@
@
lA*
@
A*
lc
@
true
c
@
@
false
c
@
ly3
@
c
@
lc
@
c'
x
@
c'
e
l l
c' n' @
@
le @
c
@
l
@
l
c
l l l l @
@
@
lA*
@
A*
lc
@
true
c
@
@
false
c
@
@
@
@
@
@
AND
@
@
true
member3
@
x3
@
@
AND
@
@
false
@
@
@
@
true
member2

Figure

@ true
@
y
@
AND
y

Figure

type of an arbitrary formula
Corollary 1 Let be a term encoding an arbitrary for-
mula. Then has type in EAL
where kMAX is the greatest k such that memberk appears in
and n is the number of quantiers in .
Proof. By the previous theorem has type
Theorem 6 Let be a term encoding an arbitrary for-
mula. Then has depth
is the greatest k such that memberk appears in and n
is the number of quantiers in . Moreover, we have also
In order to obtain the desired result on complexity of du-
plication, it remains to be shown that the pre-compilation of
the -terms given by eta-expansion can be performed inside
EAL.
Theorem 7 If M has an EAL type, so does or(M).
Proof: It is su-cient to prove that the -expansions are
always typeable in EAL, as it is described in Figure 13.
This is what is needed to obtain Theorem 1 for EAL-
typed terms, and, hence, our Theorem 4.
Conclusions
In this paper, we have shown that the complexity result for
parallel beta-reduction obtained in [AM98] can be obtained
with respect to just (optimal) duplication, and not only (as
one could have expected) to the complex machinery required
for the management of redex-families. This casts a new and
dierent light on Asperti and Mairson's work; in particular,
it helps to understand why it does not convey any negative
result for optimal reduction as a technique for the normalization
of lambda-terms. In any reduction of a lambda term
@
@
x
@

Figure

there is, potentially, a non elementary work of duplication
that has to be done, and even an optimal reduction tech-
nique, as parsimonious as it could be, cannot do any magic.
A lot of interesting issues are still to be investigated,
starting from a theoretical comparison of the performance
of Lamping's technique versus more traditional implemen-
tations. This comparison has been hindered so far by the
\bookkeeping" work, whose formal investigation is just too
complex with the current state of the art. But now we have
a huge set of lambda terms (i.e. all the terms of EAL) that
can be reduced without the need of bookkeeping, providing
a main and very promising arena for a theoretical investigation
of performance issues.



--R

The Optimal Implementation of Functional Programming Languages
On the dynamics of sharing graphs.
Parallel beta reduction is not elementary recursive.
Linear logic
On the complexity of beta- reduction
Light a-ne logic
Linear logic.
Light linear logic.


Optimal Interpreters for Lambda-calculus Based Functional Programming Languages
An algorithm for optimal lambda calculus reduction.

Optimality and ine-ciency: What isn't a cost model of the lambda calculus? ACM SIGPLAN Notices
On global dynamics of optimal graph reduction.
A simple proof of a theorem of Statman.
The inherent computational complexity of theories of ordered sets.
The typed
--TR
Linear logic
An algorithm for optimal lambda calculus reduction
A simple proof of a theorem of Statman
The geometry of optimal lambda reduction
Optimality and inefficiency
On the complexity of beta-reduction
On global dynamics of optimal graph reduction
Parallel beta reduction is not elementary recursive
Light linear logic
The optimal implementation of functional programming languages
Intuitionistic Light Affine Logic
On the Dynamics of Sharing Graphs
Light Affine Logic
complexity;elementary affine logic;graph rewriting;optimal reduction