Getting back to our first example, let us consider the definition of the function revflat which flattens a tree and then reverses the obtained list. In this composition the result of flat is a deforestable intermediate list, since it is consumed by rev.
Intuitively, in the context of our attribute grammar notation, the composition of rev and flat involves the two following sets of attributes:
More generally, consider an attribute grammar, say 
(e.g.,
flat), producing an intermediate data structure to be consumed by
another attribute grammar, say 
(e.g., rev). Two sets of
attributes are involved in this composition. The first one, 
,
contains all the attributes used to construct the intermediate
data-structure. The second one, 
, contains the attributes of
.
As in the descriptional composition, the idea of the symbolic composition is to
project the attributes of (e.g., 
)
everywhere an attribute of (e.g., 
) is
defined. This global operation brings the equations that specify a computation
over the intermediate data-structure on its construction. The basic step of
this projection is presented in Figure 7. Then, the application
of the symbolic evaluation (Figure 6) will eliminates the useless
constructors.
However, a point remains undefined: how find the application sites for the
projection steps? As attended, the constraint in the Check
predicate avoiding expressions like (x.a).b to arise is temporarily
relaxed. In fact, all these expressions are precisely the sites where
deforestation could be performed (e.g., 
).
With this relaxed Check predicate, and from the revflat function definition, we obtained the following blocks (first is for the revflat profile, and others correspond to the flat and the rev attribute grammars). In the blocks building the intermediate data structure, the application sites for the projection step are underlined, and a * highlights the constructions to be deforested.
The application of (Proj) is illustrated below on the pattern
.
All possible applications of these projection steps yield the following blocks:
Now, symbolic evaluation (Figure 6) could be applied on annotated
sites, performing the real deforestation. New attributes are created by
renaming attributes a.b into 
(when 
and 
). More precisely, (x.a).b is transformed into 
. Then,
the basic constituents of the symbolic composition are defined:
Thus, for the revflat function, the symbolic composition yields the
deforested attribute grammar that is presented below, together with its
equivalent function definition, corresponding to a functional evaluator
generated for this attribute grammar [18, 29]. Four
attributes have been generated. The final list is constructed with
and 
; this construction
corresponds to the function revflat1. Then it is propagated backward,
with 
and , before being assigned
to result; this corresponds to the function revflat2. We will
present in section 3.4 a way to eliminate most of these propagations, but
henceforth, no longer intermediate list is constructed.
