Zipping Strategies and Attribute Grammars

José Nuno Macedo10000-0002-0282-5060 Marcos Viera2 João Saraiva10000-0002-5686-7151

J. N. Macedo et al.

University of Minho, Braga, Portugal

Universidad de la República, Montevideo, Uruguay

José Nuno Macedo

University of Minho

Marcos Viera

Universidad de la República

João Saraiva

University of Minho

Strategic term rewriting and attribute grammars are two powerful programming techniques widely used in language engineering. The former, relies on strategies to apply term rewrite rules in defining language transformations, while the latter is suitable to express context-dependent language processing algorithms. Each of these techniques, however, is usually implemented by its own powerful and large language processor system. As a result, it makes such systems harder to extend and to combine.

In this paper, we present the embedding of both strategic tree rewriting and attribute grammars in a zipper-based, purely functional setting. Zippers provide a simple, but generic tree-walk mechanism that is the building block technique we use to express the purely-functional embedding of both techniques.
The embedding of the two techniques in the same setting has several advantages: First, we easily combine/zip attribute grammars and strategies, thus providing language engineers the best of the two worlds. Second, the combined embedding is easier to maintain and extend since it is written in a concise and uniform setting. This results in a very small library

which is able to express advanced (static) analysis and transformation tasks. We show the expressive power of our library in optimizing  let expressions, expressing several  refactorings and solving several language processing tasks of the LDTA Tool Challenge.

§ INTRODUCTION

Since Algol was designed in the 60's, as the first high-level
programming language [36], languages have evolved
dramatically. In fact, modern languages offer powerful syntactic and
semantic mechanisms that do improve programmers productivity. In
response to such developments, the software language engineering
community also developed advanced techniques to specify those new
language mechanisms.

Strategic term rewriting [19] and Attribute Grammars
(AG) [13] have a long history in supporting the
development of modern software language analysis, transformations and
optimizations. The former, relies on strategies to traverse a tree while
applying a set of rewrite rules, while the latter is suitable to
express context-dependent language processing algorithms. Many
language engineering systems have been developed supporting both
AGs [11, 25, 15, 22, 9, 8, 34] and rewriting
strategies [5, 4, 16, 6, 28, 35]. These
powerful systems, however, are large systems supporting their own AG
or strategic specification language, thus requiring a considerable
developing effort to extend and combine.

A more flexible approach is obtained when we consider the embedding of
such techniques in a general purpose language. Language embeddings,
however, usually rely on advanced mechanisms of the host language,
which makes them difficult to combine. For example,
Strafunski [16] offers a powerful embedding of strategic
term rewriting in , but it can not be easily combined with
the  embedding of AGs as provided
in [24, 20]. The former works directly on the
underlying tree, while the later on a zipper representation
of the tree.

In this paper, we present the embedding of both strategic tree
rewriting and attribute grammars in a zipper-based, purely functional
setting. Generic zippers [12] is a simple, but generic
tree-walk mechanism to navigate both on homogeneous and heterogeneous
data structures. Traversals on heterogeneous data structures is the
main ingredient of both strategies and AGs. Thus, zippers provide the
building block mechanism we will reuse to express the
purely-functional embedding of both techniques. The embedding of the
two techniques in the same setting has several advantages: First, we
easily combine/zip attribute grammars and strategies, thus providing
language engineers the best of the two worlds. Second, the combined
embedding is easier to maintain and extend since it is written in a
concise and uniform setting. This results in a very small library (200
lines of  code) which is able to express advanced (static)
analysis and transformation tasks.

The purpose of this paper is three-fold:

* Firstly, we present a simple, yet powerful embedding of
strategic term rewriting using generic zippers. This results in a
simple and concise library, named , that is easy to maintain and
update. Moreover, our embedding has the expressiveness of the
Strafunski library [16].

* Secondly, this new strategic term rewriting embedding can
easily be combined with a zipper-based embedding of attribute
grammars [21, 10]. In fact, by relying on the same
generic tree-traversal mechanism, the zippers, (zipper-based)
strategies can access (zipper-based) AG functional definitions, and
vice versa. Such a joint embedding results in a multi-paradigm
embedding of the two language engineering techniques. We show two
examples of the expressive power of such embedding: First, we access
attribute values in strategies so that we express non-trivial
context-dependent tree rewriting. Second, strategies are used to
define attribute propagation patterns [11, 8], which
are widely used to eliminate (polluting) copy rules from AG

* Thirdly, we apply  in real language engineering problems, namely, in optimizing
let expressions, expressing a set of refactoring rules
that eliminate several  smells and solving tasks issued in the LDTA Tool Challenge [33]
for name binding, type checking and desugaring of Oberon-0 programs. We
benchmark our  smell eliminator using 150 student Haskell projects totaling 82124 lines of code,
from which we have eliminated 850 code smells.

This paper is organized as follows: Section <ref> presents
generic zippers and describes in detail the zipper-based embedding
of strategic term rewriting. In Section <ref>, we describe
zipper-based embedding of attribute grammars and we show how the two
techniques/embeddings can be easily combined. In Section <ref> we
present our  library and
we use it in defining several usage
examples, such as refactorings of  source code and name binding,
type checking and desugaring Oberon-0 source code. Section <ref>
discusses related work, and in Section <ref> we present our
conclusions and future work.

§ ZIPPER-BASED STRATEGIC PROGRAMMING

This section briefly describes functional Zippers [12]
which are the building blocks of the embedding of strategic term
rewriting we introduce in this paper.  Before we present our
embedding in detail
later in the section,
let us consider a motivating example we will use
throughout the paper. Consider the (sub)language of  expressions
as incorporated in most functional languages, including
. Next, we show an example of a valid
and we define the heterogeneous data type , taken
from [21], that models such expressions in  itself.

[6]𝐥𝐞𝐭 [12]

[12]b=𝐥𝐞𝐭 c=3 𝐢𝐧 c+c[E]

[6]𝐢𝐧 [12]

[B]𝐝𝐚𝐭𝐚 [7]
[16]Let List Exp[E]

[B]𝐝𝐚𝐭𝐚 [7]
[16]NestedLet [27]
[27]String Let List[E]

[16]Assign [27]
[27]String Exp List[E]

[B]𝐝𝐚𝐭𝐚 [7]
[16]Add [23]
[23]Exp Exp[E]

[16]Sub [23]
[23]Exp Exp[E]

[16]Neg [23]

[16]Var [23]

[16]Const [23]

Having introduced these data types, we can write  as a
(syntax) tree with type

[6]Let [11]
[11](Assign [23]
[23]34 a34 [28]
[28](Add (Var 34 b34) (Const 0))[E]

[11](Assign [23]
[23]34 c34 [28]
[28](Const 2)[E]

[11](NestedLet [23]
[23]34 b34 [28]
[28](Let [34]
[34](Assign 34 c34 (Const 3)[E]

[34]EmptyList) [E]

[34](Add (Var 34 c34) (Var 34 c34)))[E]

[11]EmptyList))) [E]

[11](Sub (Add (Var 34 a34) (Const 7)) (Var 34 c34))[E]

Consider now that we wish to implement a simple arithmetic optimizer
for our language. Let us start with a trivial optimization: the
elimination of additions with $0$. In this context, strategic term
rewriting is an extremely suitable formalism, since it provides a
solution that just defines the work to be done in the constructors
(tree nodes) of interest, and “ignore" all the others. In our example,
the optimization is defined in  nodes, and thus we express
the worker function as follows:

[B]expr::Exp→Maybe Exp[E]

[B]expr (Add e (Const 0))[25]
[25]=Just e[E]

[B]expr (Add (Const 0) e)[25]
[25]=Just e[E]

[B]expr e[25]
[25]=Just e[E]

The first two alternatives define the optimization (when either of the
sub-expressions of an Add expression is the constant $0$, then it
returns the other sub-expression), and the last one the default
behaviour for all other cases: it returns the original
expression. Because we also need to express transformations that may
fail (that is, do nothing),
a type-specific transformation function returns a

This function applies to  nodes only. To express our
optimization, however, we need a generic mechanism that traverses a
program/tree, applying this function when visiting
expressions.  This is where strategic term rewriting comes to the
rescue: It provides recursion patterns (i.e., strategies) to
traverse the (generic) tree, like, for example, top-down or bottom-up
traversals. It also includes functions to apply a node specific
rewriting function (like ) according to a given strategy. Next,
we show the strategic solution of our optimization where  is
applied to the input tree in a full top-down strategy. This is a Type
Preserving () transformation since the input and result trees have
the same type.

[B]opt::Zipper Let→Maybe (Zipper Let)[E]

[B]opt [6]
[6]t=applyTP (𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑃 step) t[E]

[6]𝐰𝐡𝐞𝐫𝐞 step=idTP`adhocTP`expr[E]

In fact, we have just presented our first zipper-based strategic
function.  Here,  is a transformation to be applied by function
to all nodes of the input tree  (of type )
using a full top-down traversal scheme (function ). The
rewrite step behaves like the identity function () by default
with our  function to perform the type-specific transformation,
and the  combinator joins them into a single function.

This strategic solution relies on our [The library and complete examples showed in this paper are available at

library: a purely
functional embedding of strategic term rewriting in . In this
solution we clearly see that the traversal function  needs
to navigate on heterogeneous trees, as it is the case of the
expression .  In a functional programming setting,
zippers [12] provide a simple, but generic tree-walk
mechanism that we will use to embed strategic programming in
. In fact, our strategic combinators work with zippers as in
the definition of .  In the remaining of this section, we start
by briefly describing zippers, and, next, we present in detail the
embedding of strategies using this powerful mechanism.

§.§ The Zipper Data Structure

Zippers were introduced by Huet [12] to represent a tree
together with a subtree that is the focus of attention. During a
computation the focus may move left, up, down or right within the
tree.  Generic manipulation of a zipper is provided through a set of
predefined functions that allow access to all of the nodes of a tree
for inspection or modification.

A generic implementation of this concept is available as the generic
zipper  library [1], which works for both
homogeneous and heterogeneous data types.  In order to illustrate the
use of zippers and its  library, let us consider again the
tree used as an example for our  program.

tree contains nodes of the types ,  and , and thus it
is an heterogeneous tree. Traditionally, a functional implementation
of a traversal of this tree would need three functions, one for each
different type that needs to be processed. Generic zippers, however,
provide a way to navigate in such heterogeneous data structures,
independently from the type of node it is traversing.

We build a zipper  from the previous  expression  through
the use of the  function. This
function produces a zipper out of any data type, requiring only that
the data types have an instance of the  and  type
classes[That can be easily obtained via the  data
type  mechanism.].

[B]𝑡_1=toZipper p[E]

We can navigate  using pre-defined functions from the zipper
library. The function  moves the focus down to the
leftmost child of a node, while  moves the focus to the
rightmost child instead.  Similarly, functions ,  and
, move towards the corresponding directions. They have types:

[30]Zipper a→Maybe (Zipper a)[E]

Finally, the zipper function  extracts the actual node the zipper is focusing on.  Using
these functions, we can freely navigate through this newly created
zipper. For example, consider our expression . We can move the focus of the zipper towards the
sub-expression as follows:

[B]sumBZero::Maybe Exp[E]

[22] . [22E]
[25]fromJust . right[E]

[22] . [22E]
[25]fromJust . down’[E]

[22] . [22E]
[25]fromJust . down’) 𝑡_1[E]

Because the navigation functions can fail, the data type  is
used to make them total. To simplify our example we are unwrapping it
using the library function .

To avoid the repeated use of  and to define total
functions, which also express a more natural top-down
writing/reading of the navigation on trees, we can rewrite these
functions using the monadic do-notation[A pure monadic
definition can also be used, which make these definitions even
simpler. In section <ref> we will show how to obtain them.], as

[B]sumBZero'::Maybe Exp[E]

[14]𝐝𝐨 [18]
[18]𝑡_2←down’ [32]

[18]𝑡_3←down’ [32]

[18]𝑡_4←right [32]

[18]getHole 𝑡_4[E]

The zipper library also contains functions for the transformation of the
data structure being traversed. The function  applies a generic transformation to the node the
zipper is currently pointing towards, while   applies a generic monadic

In order to show a zipper-based transformation, let us consider
that we wish to increment a constant in a  expression.

We begin by defining a trivial function that increments constants,

[B]incConstant (Const n)=Const (n+1)[E]

Since  works on type  only, we use the generic
function  (from the generics library [18]) to generalize
this type-specific function to all types.

[B]incConstantG=mkT incConstant[E]

This function has type  (meaning Generic Transformation)
that is the required type of . To transform the assignment
(in ) to  we just have to navigate to the desired constant
and then apply , as follows:

[B]incrC::Maybe (Zipper Let)[E]

[B]incrC=𝐝𝐨 [13]
[13]𝑡_2←down’ [27]

[13]𝑡_3←down’ [27]

[13]𝑡_4←right [27]

[13]𝑡_5←right [27]

[13]𝑡_6←down’ [27]

[13]𝑡_7←right [27]

[13]return (trans incConstantG 𝑡_7)[E]

In fact, generic zippers is a simple, but very expressive technique to
navigate in heterogeneous data structures. Since strategic term
rewriting relies on generic traversals of trees, and on the
transformation of specific nodes, zippers provide the necessary
machinery to embed strategic programming in , as we will show
in the next section. It should also me mentioned that zippers also
provide a powerful embedding of attribute grammars in
[20, 21, 10]. In Section <ref>
we will show how these two language engineering techniques/embeddings
can be easily combined as a result of being expressed on the same
setting; i.e. via zippers.

§.§ Strategic Programming

In this section we introduce the embedding of strategic programming
using generic zippers. Our embedding directly follows the work of
Laemmel and Visser [16] on the Strafunski
library [17]. Before we present the powerful and
reusable strategic functions providing control on tree traversals,
such as top-down, bottom-up, innermost, etc., let us show some simple
basic combinators that work at the zipper level, and are the building
blocks of our embedding.

We start by defining a function that expresses how a given
transformation function is elevated to the zipper level. In other
words, we define how a function that is supposed to operate directly
on one data type is converted into a transformation that operates on a

[13]::(Typeable a,Typeable b)[E]

[13]⇒(a→Maybe b)→TP c[E]

[B]zTryApplyM f=transM (join . cast . f . fromJust . cast)[E]

[13]::(Typeable a,Typeable b)⇒(a→Maybe b)→TP c[E]

[B]zTryApplyM f=transM (join . cast . f . fromJust . cast)[E]

The definition of  relies on transformation on zippers,
thus reusing the generic zipper library  function.
To build a valid transformation for the  function, we
use the  function, that tries to cast a given
data from type  to type . In this case, we use it to cast the
data the zipper is focused on into a type our original transformation
can be applied to.  Then, function  is applied and its result
is cast back to its original type. Should any of these casts, or the
function  itself, fail, the failure propagates and the resulting
zipper transformation will also fail. The use of the monadic version
of the zipper generic transformation guarantees the handling of such
partiality.  It should be noticed that failure can occur in two
situations: the type cast fails when the types do not match. Moreover,
the function  fails when the function itself dictates that no
change is to be applied.  Signaling failure in the application of
transformations is important for strategies where a transformation is
applied once, only.

returns a , in which  is a type for specifying
Type-Preserving transformations on zippers, and  is the type of the
zipper. For example, if we are applying transformations on a zipper
built upon the  data type, then those transformations are of type
. Very much like Strafunski, we also introduce the type  for Type-Unifying operations, which aim to gather data of type
into the data structure . For example, to collect in a list all the
defined names in a  expression, the corresponding type-unifying
strategy would be of type . We will present such a
transformation and implement it later in this section.

Next, we define a combinator to compose two transformations, building
a more complex zipper transformation that tries to apply each of the
initial transformations in sequence. Because each of the
transformations may fail, we have to skip transformations that fail.

[14](Typeable a,Typeable b)[E]

[14]TP e→(a→Maybe b)→TP e[E]

[B]adhocTP f g z=maybeKeep f (zTryApplyM g) z[E]

[14](Typeable a,Typeable b)⇒[43]
[43]TP e→(a→Maybe b)→TP e[E]

[B]adhocTP f g z=maybeKeep f (zTryApplyM g) z[E]

The  function receives transformations  and  as
parameters, as well as zipper . It converts  into a zipper
transformation, and it uses the auxiliary function  to try
to apply each of the transformations to the zipper , ignoring the
transformations that fail.  Note that  is of type , meaning
it is a transformation on zippers, while  is a normal
function. Because  is a non-zipper based function,  allows
the definition of transformations where we use simple (i.e.
non-zipper)  functions. Next, we show an example of the use of ,
written as an infix operator, which combines the zipper function
with our basic transformation  function:

Thus, we do not need to express type-specific transformations as
functions that work on zippers. It is the use of  in
that transforms a normal  function ( in this
case) to a zipper one, hidden from these definitions.

The function  is a pre-defined transformation that always
fails and  is the identity transformation that always
succeeds. They provide the basis for construction of complex
transformations through composition.  We omit here their simple

The functions we have presented already allow the definition of
arbitrarily complex transformations for zippers. Such transformations,
however, are always applied on the node the zipper is focusing on. Let
us consider a combinator that does navigate in the zipper.

[B]allTPright::TP a→TP a[E]

[B]allTPright f z=[19]
[19]𝐜𝐚𝐬𝐞 right z 𝐨𝐟[E]

[28]→return z[E]

[19]Just r[28]
[28]→fmap (fromJust . left) (f r)[E]

The code presented above is a combinator that, given a type-preserving
transformation  for zipper , will attempt to apply  to the
node that is located to the right of the node the zipper is pointing
towards. To do this, the zipper function  is used to try to
navigate to the right; if it fails, we return the original zipper. If
it succeeds, we apply transformation  and then we navigate
again. There is a similar combinator named  that will
perform the same logic but by navigating downwards and then upwards.

With all these tools at our disposal, we can define generic traversal schemes by combining them. Next, we define the traversal scheme used in the function  we defined at the start of the section. This traversal scheme navigates through the whole data structure, in a top-down approach.

[B]𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑃::TP a→TP a[E]

[B]𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑃 f=[16]
[16]allTPdown [28]
[28](𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑃 f)`seqTP`allTPright [62]
[62](𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑃 f)`seqTP`f[E]

We skip the explanation of the  operator as it is relatively
similar to the  operator we described before, albeit simpler;
we interpret this as a sequence operator. This function receives as
input a type-preserving transformation , and it (reading the code
from right to left) applies it to the focused node itself, then to the
nodes below the currently focused node, then to the nodes to the right
of the focused node. To apply this transformation to the nodes below
the current node, for example, we use the  combinator we
defined before, and we recursively apply  to the node
below. The same logic applies in regards to navigating to the right.

We can define several traversal schemes similar to this one by changing the combinators used, or their sequence. For example, by inverting the order in which the combinators are sequenced, we define a bottom-up traversal. By using different combinators, we can define choice, allowing for partial traversals in the data structure.

In fact, previously we defined a rewrite strategy where we use
to define a full, top-down traversal, which is not
ideal. Because we intend to optimize  nodes, changing one node
might make it possible to optimize the node above, which would have
already been processed in a top-down traversal. Instead, we define a
different traversal scheme, for repeated application of a
transformation until a fixed point is reached:

[12]::TP a→TP a[E]

[B]innermost s[14]
[17]repeatTP (𝑜𝑛𝑐𝑒_𝑏𝑢𝑇𝑃 s)[E]

We omit the definitions of  and  as they are
similar to the definitions presented already. The combinator
applies a given transformation repeatedly until a fixed point is
reached, that is, until the data structure stops being changed by the
transformation. The transformation being applied repeatedly is defined
with the  combinator, which applies  once, anywhere on
the data structure. When the application  fails,
understands a fixed point is reached. Because the
bottom-up combinator is used, the traversal scheme is , since
it always prioritizes the innermost nodes. The  function
is defined in a similar way, but using the  combinator

Let us return to our  running example. Obviously there are more
arithmetic rules that we may use to optimize let expressions. In
Figure <ref> we present the rules literally taken
from [14].

\begin{align}\label{eq:rules}
add(e, const(0)) &\rightarrow e \\
add(const(0), e) &\rightarrow e \\
add(const(a), const(b)) &\rightarrow const(a+b) \\
sub(e1, e2) &\rightarrow add(e1, neg(e2)) \\
neg(neg(e)) &\rightarrow e \\
neg(const(a)) &\rightarrow const(-a) \\
var(id) \mid (id, just(e)) \in env &\rightarrow e
\end{align}

Optimization Rules

In our previous definition of the function , we already defined
rewriting rules for optimizations $1$ and $2$. Rules $3$ through $6$
can also be trivially defined in :

[B]expr::Exp→Maybe Exp[E]

[B]expr (Add e (Const 0))[33]
[33]=Just e[E]

[B]expr (Add (Const 0) t)[33]
[33]=Just t[E]

[B]expr (Add (Const a) (Const b))[33]
[33]=Just (Const (a+b))[E]

[B]expr (Sub a b)[33]
[33]=Just (Add a (Neg b))[E]

[B]expr (Neg (Neg f))[33]
[33]=Just f[E]

[B]expr (Neg (Const n))[33]
[33]=Just (Const (-n))[E]

[B]expr [33]

Rule $7$, however, is context dependent and it is not easily expressed
within strategic term rewriting.  In fact, this rule requires that
the environment, where a name is used, is computed first (according to
the scope rules of the  language). We will return to this rule in
Section <ref>.

Having expressed all rewriting rules in function , now we need
to use our strategic combinators that navigate in the tree while
applying the rules.  To guarantee that all the possible optimizations
are applied we use an  traversal scheme. Thus, our
optimization is expressed as:

[7]::Zipper Let→Maybe (Zipper Let)[E]

[B]opt' [7]
[12]applyTP (innermost step) t[E]

[7]𝐰𝐡𝐞𝐫𝐞 step=failTP`adhocTP`expr[E]

Function  combines all the steps we have built until now. We
define an auxiliary function , which is the composition of the
default failing strategy with , the optimization
function; we compose them with .  Our resulting
Type-Preserving strategy will be , which applies
to the zipper as many times as possible until a fixed-point is
reached.  The use of  as the default strategy is required, as
reaches the fixed-point when  fails.
If we use  instead,  always succeeds, resulting
in an infinite loop. We apply this strategy using the function
which effectively applies a strategy to a zipper. This function is defined
in our library, but we omit the code as it is trivial.

Next, we show an example using a Type-Unifying strategy. More
concretely, we define a function  that collects all defined
names in a  expression. First, we define a function  that focus on
the  tree nodes where names are defined, namely,  and
. This function returns a singleton list (with the defined
name) when applied to these nodes, and an empty list in the other

[B]select::List→[1.5mu String1.5mu][E]

[B]select (Assign [19]
[19]s  )[27]
[27]=[1.5mu s1.5mu][E]

[B]select (NestedLet s  )[27]
[27]=[1.5mu s1.5mu][E]

[B]select [27]
[27]=[1.5mu 1.5mu][E]

Now,  is a Type-Unifying function that traverses a given
tree (inside a zipper, in our case), and produces a list with the
declared names.

[8]::Zipper Let→[1.5mu String1.5mu][E]

[B]names [8]
[8]r=applyTU (𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑈 step) r[E]

[8]𝐰𝐡𝐞𝐫𝐞 step=failTU`adhocTU`select[E]

The traversal strategy influences the order of the names in the
resulting list. We use a top-down traversal so that the list result
follows the order of the input. This is to say that  (a bottom-up strategy produces the reverse of this

As we have shown, our strategic term rewriting functions rely on
zippers built upon the data (trees) to be traversed. This results in
strategic functions that can easily be combined with a zipper-based
embedding of attribute grammars [21, 10], since both
functions/embedding work on zippers. In the next section we present in
detail the zipping of strategies and AGs.

There is, however, a key difference between both libraries: while
Strafunski operates directly on the data to be traversed,
relies on a zipper built upon that data. This results in strategic
functions that can easily be combined with a zipper-based embedding of
attribute grammars, since both functions/embedding work on zippers. We
will present in detail the zipping of AGs and strategies in
Section <ref>.

§ STRATEGIC ATTRIBUTE GRAMMARS

Zipper-based strategic term rewriting provides a powerful mechanism
to express tree transformations. There are, however, transformations
that rely on context information that needs to be collected
before the transformation can be applied. Our optimization rule $7$ of Figure <ref> is
such an example.

In this section we will briefly explain the Zipper-based embedding of attribute grammars, through the  example.
Then, we are going to introduce how to combine strategies and AGs, ending with an implementation of rule 7.

§.§ Zipper-based Attribute Grammars

The attribute grammar formalism is particularly suitable to specify
language-based algorithms, where context information needs to be first
collected before it can be used. Language-based algorithms such as
name analysis [21], pretty printing [32],
type inference [23], etc.  are elegantly
specified using attribute grammars.

Our running example is no exception and the name analysis task of
is a non-trivial one.  While being a concise example, it holds
central characteristics of software languages, such as (nested)
block-based structures and mandatory but unique declarations of
names. In addition, the semantics of  does not force a
declare-before-use discipline, meaning that a variable can be declared
after its first use. Consequently, a conventional  implementation of name analysis
naturally leads to a processor that traverses each block twice: once
for processing the declarations of names and constructing an
environment and a second time to process the uses of names (using the
computed environment) in order to check for the use of non-declared
identifiers. The uniqueness of identifiers is efficiently checked in
the first traversal: for each newly encountered name it is checked
whether that it has already been declared at the same lexical level
(block). As a consequence, semantic errors resulting from duplicate
definitions are computed during the first traversal and errors
resulting from missing declarations, in the second one. In fact,
expressing this straightforward algorithm is a complex task in most
programming paradigms, since they require a complex scheduling of tree
traversals[Note that only after building the environment of an
outer block, nested ones can be traversed for the first time: they
inherited that environment. Thus, traversals are intermingled.], and
intrusive code may be needed to pass information computed in
one traversal to a specific node and used in a following
one[This is the case when we wish to produce a list of errors
that follows the sequential structure of the input program [26].].

In the attribute grammar paradigm, the programmer does not need to be
concerned with scheduling of traversals, nor the use of intrusive code
to glue traversals together. As a consequence, AG writers do not need
to transform/adapt the clear and elegant algorithms in order to avoid
those issues.

Attribute grammars are context-free [13]. That is
to say that the root symbol does not have inherited attributes. Since
this not the case of symbol  (due to its nested occurrence in the
grammar/data types), we will add a root symbol to our grammar as

[B]𝐝𝐚𝐭𝐚 Root=Root Let[E]

Attribute Grammar Specifying the Scope Rules of

Instead of presenting the formal AG definition of , we will adopt
a visual notation that is often used by AG writers to sketch a first
draft of their grammars.  The scope rules of  are visually
expressed in Figure <ref>.

The diagrams in the figure are read as follows. For each production
(labeled by its name) we have the type of the production above and
below those of its children. To the left of each symbol we have the
so-called inherited attributes: values that are computed
top-down in the grammar. To the right of each symbol we have the
so-called synthesized attributes: values that are computed
bottom-up. The arrows between attributes specify the information flow
to compute an attribute. For example, in the production , to
compute the inherited attribute  in the third child (), we
take the value of the first child (a ) and insert it (with
) to the beginning of the attribute  of the parent. That is
to say that we are accumulating identifiers in  while descending
in the list of statements of let expressions.

Thus, the AG expressed in Figure <ref> is the following.
The inherited attribute  is used as an accumulator to
collect all  defined in a : it starts as an empty list in
the  production, and when a new name is defined (productions
and ) it is added to the accumulator. The total
list of defined  is synthesized in attribute , which at
the  node is passed down as the environment (inherited attribute
). The type of the three attributes is a list of pairs,
associating the  to its  expression definition[We
will use this definition to expand the  as required by
optimization rule .].

Very much like strategic term rewriting, AGs also rely on a generic
tree walk mechanism, usually called tree-walk
evaluators [2], to walk up and down the tree to evaluate
attributes. In fact, generic zippers [12] also offer the
necessary abstractions to express the embedding of AGs in a functional
programming setting [21, 10]. Next, we briefly describe
this embedding, and after that we present the embedded AG that express
the scope rules of . It also computes (attribute) , that is
needed by the optimization rule $7$.

To allow programmers to write zipper-based functions very much
like attribute grammar writers do, the generic
zippers library [1] is extended with the following set of
simple AG-like combinators:

* The combinator “child”, written as the infix function
to access the child of a tree node given its index (starting from

[B]()::Zipper a→Int→Zipper a[E]

* The combinator  to move the focus to the parent of a
tree node,

[B]::Zipper a→Zipper a[E]

* The combinators  (left) and  (right) navigate to the
i$^{th}$ sibling on the left/right of the current node:

[B](),()::Zipper a→Int→Zipper a[E]

Having presented these zipper-based AG combinators, we can now express
the scope rules of  expressions as an attribute grammar. To make
our definitions more AG friendly we define the following
(type) synonym:

[B]𝐭𝐲𝐩𝐞  a[16]
[16]=Zipper Root→a[E]

We start by defining the equations of the synthesized attribute
. For each definition of an occurrence of  we define an
equation in our zipper-based function. For example, in the diagrams of
the  and  productions we see that  is defined
as the  of the third child. Moreover, in production
attribute  is a copy of . This is exactly how such
equations are written in the zipper-based AG, as we can see in the
next function:

[B]dclo:: [1.5mu (Name,Zipper Root)1.5mu][E]

[B]dclo t=[11]
[11]𝐜𝐚𝐬𝐞 ( t) 𝐨𝐟[E]

[26]→dclo (t1)[E]

[26]→dclo (t3)[E]

[26]→dclo (t3)[E]

[26]→dcli t[E]

The function  and the constructors used in the case
alternatives is boilerplate code needed by the AG embedding. This code
has to be defined once per tree structure (i.e., AG), and can
be generated by using template  [27].  To
provide a full implementation of our example, we include such code in
Appendix <ref>.

We may use the default rule of a case statement to express similar AG
equations. Consider the case of defining the inherited attribute
. In most diagrams an occurrence of attribute  is defined as
a copy of the parent. There are two exceptions: in productions
and . In both cases,  gets its value from the
synthesized attribute  of the same non-terminal/type. Thus, the
function looks as follows:

[B]env:: [1.5mu (Name,Zipper Root)1.5mu][E]

[B]env t=[10]
[10]𝐜𝐚𝐬𝐞 ( t) 𝐨𝐟[E]

[18]→dclo t[E]

[18]→dclo t[E]

[18]→env ( t)[E]

Let us define now the accumulator attribute .  The zipper
function when visiting nodes of type , has to consider two
alternatives: the parent node can be a  or a  (the two
occurrences of  as a child in the diagrams). This happens because
the rules to define its value differ: in the  node it corresponds
to an empty list (our outermost  is context-free), while in a
nested block, the accumulator  starts as the  of the outer
block. Thus, the zipper-based function  is expressed as follows:

[B]dcli:: [1.5mu (Name,Zipper Root)1.5mu][E]

[B]dcli [7]
[7]t=𝐜𝐚𝐬𝐞 ( t) 𝐨𝐟[E]

[18][1.5mu 1.5mu][E]

[18]𝐜𝐚𝐬𝐞 ( ( t)) 𝐨𝐟[E]

[33][1.5mu 1.5mu][E]

[33]env [38]
[38]( t)[E]

[18]𝐜𝐚𝐬𝐞 ( ( t)) 𝐨𝐟[E]

[36]( ( t), t):(dcli ( t))[E]

[36]( ( t), t):(dcli ( t))[E]

[36]dcli ( t)[E]

In this AG function we use the function , which implements the
so-called syntactic references in attribute
equations [26]. In this case,  returns the
argument of constructors  and . This function is
other boilerplate code also included in appendix <ref>.

In order to specify the complete name analysis task of
expression we need to report which names violate the scope rules of
the language. In fact, we can modularly and incrementally extend our
zipper AG, and define a new (synthesized) attribute  which
reports such violations.
In Appendix <ref> we include its definition.

In the next section we will show how  can be
expressed as a strategic function and combined with our AG.

§.§ Strategic Attribute Grammars

By having embedding both strategic term rewriting and attribute
grammars in the same zipper-based setting,
and given that both are embedded as first-class citizens,
we can easily combine these
two powerful language engineering techniques. As a result, attribute
computations that do useful work on few productions/nodes can be
efficiently expressed via our  library, while rewriting
rules that rely on context information can access attribute values.

Acessing Attribute Values from Strategies:

As we said in Section <ref>, rule 7 of Figure <ref> cannot be implemented using a trivial strategy, since it depends on the context.
The rule states that a variable occurrence can be changed by its definition.
For this we need to compute an environment of definitions, which is what we have done with the attribute , previously.
Thus, if we have access to such attribute in the definition of a strategy, we would be able to implement this rule.

Given that both attribute grammars and strategies use the zipper to walk through the tree, such combinations can be easily performed if
the strategy exposes the zipper, in order to be used to apply the given attribute.
This is done in our library by the  combinator:
[13]::TP e→(a→Zipper e→Maybe b)→TP e[E]
Notice that instead of taking a function of type , as does the combinator  introduced in Section <ref>,
it receives a function of type , with the zipper as a parameter.

Then, we can define a function with this type, that implements rule 7:

[B]expC::Exp→Zipper Root→Maybe Exp[E]

[B]expC (Var x) z[17]
[20]𝐜𝐚𝐬𝐞 lookup x (env z) 𝐨𝐟[E]

[22]Just e[31]
[31]→ e[E]

[B]expC  z[17]
The variable  is searched in the environment returned by the  attribute;
in case it is found, the associated expression[The function  is another syntactic reference that in this case takes a  and, if it is focused on an , returns its expression.] is returned, otherwise the optimization is not performed.

Now we can combine this rule with the previously defined , that implements rules 1 to 6, and apply them to all nodes.

[8]::Zipper Root→Maybe (Zipper Root)[E]

[B]opt” [8]
[8]r=applyTP (innermost step) r[E]

[8]𝐰𝐡𝐞𝐫𝐞 step=failTP`adhocTPZ`expC`adhocTP`expr[E]

Synthesizing Attributes via Strategies:

We have shown how attributes and strategies can be combined by using the former while defining the latter.
Now we show how to combine them the other way around; i.e. to express attribute computations as strategies.
As an example, let us consider the  attribute, that returns
the list of names that violate the scope rules

following the structure of input program.
We want to evaluate
the following input

[18]𝐥𝐞𝐭 [23]

[29]𝐥𝐞𝐭 [34]

[29]𝐢𝐧 [34]

[18]𝐢𝐧 [23]

to the list .
Recall that errors occur in two
situations: First, duplicated definitions that are efficiently
detected when a new  (defined in nodes  and )
is accumulated in . Then the newly defined  must
not be in the environment  accumulated till that
definition/node. This is expressed by the following zipper function:

[B]decls::List→Zipper Root→[1.5mu Name1.5mu][E]

[B]decls (Assign [21]
[21]s  ) z[31]
[31]=mNBIn ( z,z) [54]
[54](dcli z)[E]

[B]decls (NestedLet [21]
[21]s  ) z[31]
[31]=mNBIn ( z,z) [54]
[54](dcli z)[E]

[B]decls  [31]
[31]=[1.5mu 1.5mu][E]

Invalid uses are detected when a  is used in an arithmetic
expression (). In this case, the  must be
in[Functions  and  are trivial lookup
functions. They are presented in Appendix <ref>.] the total
environment .

[B]uses::Exp→Zipper Root→[1.5mu Name1.5mu][E]

[B]uses (Var i) z[17]
[17]=mBIn ( z) (env z)[E]

[B]uses  [14]
[17]=[1.5mu 1.5mu][E]

Now, we define a type-unifying strategy that produces as result the
list of errors.

[B]errors::Zipper Root→[1.5mu Name1.5mu][E]

[B]errors [9]
[9]t=applyTU (𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑈 step) t[E]

[5]𝐰𝐡𝐞𝐫𝐞 step=failTU`adhocTUZ`uses`adhocTUZ`decls[E]

Although the step function combines  and  in this order,
the resulting list does not report duplications first, and invalid
uses after. The strategic function  does combine the two
and the default failing function
into one, which is applied while traversing (in a top-down
traversal) the tree. In fact, it produces the errors in the proper

In Appendix <ref> we show the zipper-AG definition of , where most
of the attribute equations are just propagating attribute values
upwards without doing useful work! In fact, a type unifying strategy
provides a better solution for specifying such synthesized
computations since it focus on the productions/nodes where interesting
work has to be defined.  This is particularly relevant when we
consider the  sub-language as part of a real programming language
(such as  with its 116 constructors across 30 data
types). The difference in complexity between the strategic definition
of  and its AG counterpart is much higher.

Attribute grammar systems provide the so-called attribute propagation
patterns to avoid polluting the specification with
copy-rules. In most systems, a special notation and pre-fixed
behavior is associated with a set of off-the-shelf patterns that can
be reused across AGs [11, 8]. For example, in the UUAG
system [8], the propagation patterns are the default rules
for any attribute. Thus, only the specific/interesting equations
have to be specified. However, being
a special notation, hard-wired to the AG system, makes the extension
or change of the existing rules almost impossible: the full system has
to be updated. Our embedding of strategic term rewriting provides a
powerful setting to express attribute propagation patterns: no special
additional notation/mechanism is needed.

§ THE  LIBRARY

As we have shown, zippers can express strategic term rewriting.  We
developed a full library, named .
Figure <ref> presents the full API, which is based on Strafunski's API,
but adding the possibility to manipulate the zipper that traverses the tree, in order to be able to, for example,
compute attributes.
We define two Strategy types,  and  which stand for Type-preserving and Type-Unifying. The former represents transformations, while the latter represents reductions.

We define Primitive Strategies that can be used as building blocks, such as identities ( and ), failing strategies  and , the  combinator which applies a transformation once if possible and always succeeds, and  which applies a transformation as many times as possible.
Strategy Construction combinators allow for composition of more complex transformations. The  combinators compose an existing strategy with a  function, and the  combinators produce a strategy out of one  function. There are variants that allow access to the zipper, denoted by a $Z$ suffix.

For the composition of traversals,  defines a sequence (perform both traversals) and  an alternative (perform just one traversal).
We use Traversal Combinators  and  to travel the zipper; the  variants always succeed and the  variants can fail.
Traversal Strategies are defined by combining the previous tools, and come in  (top-down) and  (bottom-up) variants. The  strategies traverse the whole tree, while  strategies perform at most one operation and  strategies stop cut off the traversal in a specific sub-tree when any operation in it succeeds. Finally,  and  perform a transformation as many times as possible, starting from the inside or outside nodes, respectively.

Strategy typesB@>l<@
[3]𝐭𝐲𝐩𝐞 TP a=Zipper a→Maybe (Zipper a)[E]

[3]𝐭𝐲𝐩𝐞 TU m d=(forall a . Zipper a→m d)[E]
Primitive strategiesB@>l<@
[13]::TP a[E]

[13]::d→TU m d[E]

[13]::TP a[E]

[13]::TU m d[E]

[13]::TP a→TP a[E]

[13]::TP a→TP a[E]
Strategy ConstructionB@>l<@
[13]::(a→Maybe b)→TP e[E]

[13]::(a→m d)→TU m d[E]

[13]::(a→Zipper e→Maybe b)→TP e[E]

[13]::(a→Zipper e→m d)→TU m d[E]

[13]::TP e→(a→Maybe b)→TP e[E]

[13]::TU m d→(a→m d)→TU m d[E]

[13]::TP e→(a→Zipper e→Maybe b)→TP e[E]

[13]::TU m d→(a→Zipper c→m d)→TU m d[E]
Composition / ChoiceB@>l<@
[13]::TP a→TP a→TP a[E]

[13]::TP a→TP a→TP a[E]

[13]::TU m d→TU m d→TU m d[E]

[13]::TU m d→TU m d→TU m d[E]

Traversal CombinatorsB@>l<@
[15]::TP a→TP a[E]

[15]::TP a→TP a[E]

[15]::TU m d→TU m d[E]

[15]::TP a→TP a[E]

[15]::TP a→TP a[E]

[15]::TU m d→TU m d[E]
Traversal StrategiesB@>l<@
[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TP a→TP a[E]

[14]::TU m d→TU m d[E]

[14]::TU m d→TU m d[E]

[14]::TU m d→TU m d[E]

[14]::TU m d→TU m d[E]

[14]::TU m d→TU m d[E]

[14]::TU m d→TU m d[E]

Full Ztrategic API

Let us show now the expressiveness of our  library in
implementing useful transformations of a real programming language
such as . We reuse the available support for parsing and
pretty printing as part of the  core libraries (in the
haskell-src package).

§.§ Do-notation elimination

We start by defining a refactoring that eliminates the syntactic sugar
introduced by the monadic do-notation. In fact, we used this
notation in , and we can rewrite in an applicative
functional style as expressed by the monadic binding function .

[B]sumBZero”::Maybe Exp[E]

[B]sumBZero”=down’ 𝑡_1down’rightgetHole[E]

In order to automate this refactoring, a type-preserving strategy is
used to perform a full traversal in the  tree, since such
expressions can be arbitrarily nested. The rewrite step
behaves like the identity function by default with a
type-specific case for pattern matching the  in the
syntax tree (nodes constructed by ).

[B]refactor::Zipper HsModule→Maybe (Zipper HsModule)[E]

[B]refactor [11]
[11]h=applyTP (innermost step) h[E]

[5]𝐰𝐡𝐞𝐫𝐞 step=failTP`adhocTP`doElim[E]

The following type-specific transformation function  just
expresses the refactoring we showed for the concrete  to
example. Obviously, it is expressed at abstract syntax
tree level. We omit here the details of its underlying representation
as  data types.

[11]::HsExp→Maybe HsExp[E]

[B]doElim (HsDo [1.5mu HsQualifier e1.5mu])[32]
[32]=Just e[E]

[B]doElim (HsDo (HsQualifier e:stmts))=Just ((HsInfixApp [58]

[9](HsQVarOp (hsSymbol 34 >>34)) (HsDo stmts)))[E]

[B]doElim (HsDo (HsGenerator  p e:stmts))=Just (letPattern p e stmts)) [E]

[B]doElim (HsDo (HsLetStmt decls:stmts))=Just (HsLet decls (HsDo stmts))[E]

[B]doElim [11]

§.§ Smells Elimination

Source code smells make code harder to comprehend. A smell is not an
error, but it indicates a bad programming practice. They do occur in
any language and  is no exception. For example, inexperienced
programmers often write  to check whether a list is
empty, instead of using the predefined  function.  Next, we
present a strategic function that eliminates several  smells
as reported in [7].

[12]::Zipper HsModule→Maybe (Zipper HsModule)[E]

[B]smellElim h=applyTP (innermost step) h[E]

[3]𝐰𝐡𝐞𝐫𝐞 step=[17]

where the type-specific transformations are described next.

*  detects patterns where list concatenations are
inefficiently defined; the pattern  is refactored to .

*  detects patterns where a list is checked for
emptiness. Patterns such as  and  are
refactored to .

*  detects redundant boolean checks, such as the
pattern  which is refactored to .

*  detects redundant usages of  clauses, such as
the pattern  which is refactored to .

The full implementation of these functions is included in
Appendix <ref>.

§.§ Ztrategic: Expressiveness and Performance

In order to evaluate our combined zipper-based embedding of attribute
grammars and strategic term-rewriting we consider two language
engineering problems: First, we express in Ztrategic the largest
language specification developed in this setting: the Oberon-0
language. The construction of a processor for Oberon-0 was proposed in
the LDTA Tool Challenge [33], and it was concisely and
efficiently specified using AGs and strategies in
Kiama [29]. Second, we evaluate the performance of our
library by comparing the runtime of our Ztrategic smell eliminator
with its Strafunski counterpart when processing a large set of smelly
Haskell programs.

Oberon-0 in Ztrategic:

The LDTA 2011 Tool Challenge [33] was a challenge focused on
the construction of a compiler for the Oberon-0 language, using the
tools of choice of the participants, with the goal of comparing the
formalisms and toolsets used in it. The challenge was divided into 5
tasks: parsing and pretty-printing, name binding, type checking,
desugaring and C code generation. These tasks were to be performed on
the Oberon-0 language, which in itself was divided into 5 increasingly
complex levels: (1) basic, (2) with if and while statements, (3) with
for and case statements, (4) with procedures and (5) with arrays and

We consider the L2 level of the Oberon-0 language, and we specified
the name binding, type checking and desugaring tasks in our Ztrategic
AG approach. We use attributes for contextual information when needed,
for example in name analysis to check whether a used name has been
declared. This level requires the desugaring of  and
statements, into semantically equivalent  and (nested)
statements. Such desugaring is implemented using Ztrategic type
preserving strategies, and the result is a (higher-order) tree that is
then decorated to perform name analysis and type checking via
ZippersAG. Because a  statement induces a new assignment (before
the ) whose variable needs to be added to the declarations
part of the original AST, we use attribute  which is a
synthesized attribute of the original tree.  Having the desugared AST
(represented by higher-order attributable attribute ) and the
number of for statements refactored, then we return the final
higher-order tree where the induced variables are properly declared.

[B]desugar m=[14]
[14]𝐥𝐞𝐭 [19]
[19]numberOfFors=numForsDown (toZipper m)[E]

[19]ata=fromJust (applyTP (innermost step) (toZipper m))[E]

[14]𝐢𝐧 [19]
[19]injectForVars numberOfFors (fromZipper ata)[E]

Next, we show the work that is performed when the  strategy
visits  nodes:

[B]desugarFor::Statement→Zipper Root→Maybe Statement[E]

[B]desugarFor [13]
[13](ForStmt idFor startFor dirFor stopFor stepFor ssFor) z=[E]

[13]Just (SeqStmt assign1 (SeqStmt assign2 loop))[E]

[B]𝐰𝐡𝐞𝐫𝐞 [9]
[23]=AssigStmt idFor startFor[E]

[23]=34 95 forCounter34show (numFors z)[E]

[23]=AssigStmt upperVarName stopFor[E]

[23]=WhileStmt whileExp whileStmt[E]

[23]=IntCmpExp op (IdExp ifFor) (IdExp upperVarName)[E]

[23]=𝐜𝐚𝐬𝐞 [31]
[31]dirFor 𝐨𝐟[E]

[23]=SeqStmt ssFor updateVar[E]

[23]=AssigStmt ifFor (IntBOpExp Plus (IdExp ifFor) (stepFor))[E]

[B]desugarFor  z=Nothing[E]

where, three new statements are produced: ,  and
, where the first two statements are assignments defining
variables for the initial and final values of the loop, respectively,
and  is the transformed While loop. We also use attribute
that counts the number of  loops that occur before this
loop, allowing us to identify this loop uniquely.

Next, we compare our approach to the results displayed
in [29], in terms of number of lines of code. For this,
we take their results for the L2 language level and compare it to

Ztrategic     Kiama     Strafunski
Oberon-0 Tree      57            99        –

Name analyser      50            222       –

Type analyser      34            117       –

Lifter             6             23        –

Desugarer          76            123       –

Oberon-0 Total     223           584       –

Do-notation        16            –        16

Haskell Smells     22            –        22

Numbers of Lines of Code for the previous tasks.

Task                  Ztrategic     Kiama
Oberon-0 Tree        57            99

Name analyser         50            222

Type analyser         34            117

Lifter                6             23

Desugarer             76            123

Total                 223           584

Numbers of Lines of Code for the Oberon-0 L2 tasks.

Next, we show the strategy for type checking an Oberon-0 program. We
rely on a full, top-down approach, as we do not need more than one
strategic traversal on the tree - we typecheck each node at most once.

[B]types::Zipper Root→[1.5mu String1.5mu][E]

[B]types r=applyTU (𝑓𝑢𝑙𝑙_𝑡𝑑𝑇𝑈 step) r[E]

[B]𝐰𝐡𝐞𝐫𝐞 step=failTU`adhocTUZ`typesExp`adhocTUZ`typesAssig[E]

We use the  and  functions to define our type analysis - we define  and ommit  as it is similar albeit more verbose.

[B]typesAssig::Statement→Zipper Root→[1.5mu String1.5mu][E]

[B]typesAssig (AssigStmt v e) z=mBSame (typeOf z) (typeOf$z2)[E]

[B]typesAssig  [28]
[28]z=[1.5mu 1.5mu][E]

We make use of a  attribute, which specifies the type of a variable or expression, to compare the types being matched here. More precisely, we compare the type of the assignment node itself (denoted by ) with the type of its righthand side expression (denoted by ), and we make use of the helper function  for this comparison, which will produce an error message when the types do not match. Note that for every new type of statement that gets introduced into the language, if it needs typechecking, then it should require one more line of code in this function, else the function remains unchanged, thus making this approach very compact.
The behaviour defined in the  function is similar but it uses more lines of code as there are more relevant type-checking rules for expressions that need to be handled. Should a new data type need type-checking, we can extend this code by adding a new function to the definition of  which handles the new data type.

I think we can omit this:
Note that the comparison between the two examples is not perfectly
linar - for example, both implementations for desugaring of for-loops
optimize the expressions of the cycle by introducing variables that
store the result of the computation, so that it is not repeated on
each iteration. However, the Kiama implementation uses the name
"_limit" for all cycle upper limits, therefore incorrectly reusing
said variable when in nested loops. Our implementation, for the
$N\textsuperscript{th}$ for-loop, will declare a "_forCounterN", and
thus we need to compute N, for which the attribute  is
used. Moreover, our implementation of syntax analyser and printer are
inefficient, as they were built only as supporting steps of our main
focus tasks.

– component - without emptylines - with emptylines
tree - 57 - 86
parser - 80 - 109
prettyprinter - 73 - 89

errors - 13 - 16 - (+attributes=37)

type - 13 - 15 (+attributes=21)

lifter - 6
desugarer - 39 - 47 (attributes=37)

In fact, the code smells these optimizations solve are typical mistakes of beginner  programmers. Through strategic application of these optimization functions, we can precisely define the transformations we intend to apply without needing to worry about boilerplate code.

This approach, of course, has the disadvantage
of having to build and maintain the zipper throughout the traversal of
the data structures. However, the loss in performance is compensated
by having more expressive power - for each node that is processed, the
context can be extracted by traversing the zipper. This will be
further explored in Section <ref>, by using a zipper-based
attribute grammar embedding.

Focus on the technical part
Show code - explain that zippers (down, left etc) + overhead of actual zipper = heavy
Tradeoff performance - usability (step function only applies at most once = better performance, but more inconvenient)

§.§ Benchmark? Repo?

Ztrategic Smell Elimination:

In order to assess the runtime performance of our zipper-based
strategic term rewriting implementation, we will compare it with the
state-of-the-art, fully optimized Strafunski system. A detailed
analysis of runtime performance of the zipper-based embedding of AGs
is presented in [10]. In this work we have also
incorporated memoization in order to avoid attribute recalculation. We
have executed several first and higher order zipper-based attribute
grammars with very large inputs, showing that our AG embedding is not
only concise and elegant, but is also efficient.

Let us consider the Haskell smell eliminator expressed both on
Ztrategic and Strafunski. To run both tools with large smelly
inputs, we consider 150 Haskell projects developed by first-year
students as presented in [3]. In these projects there are
1139 Haskell files totaling 82124 lines of code, of which exactly
1000 files were syntactically correct [The student projects
used in this benchmark are available at this work's repository.]. Both
Ztrategic and Strafunski smell eliminators detected and eliminated 850
code smells in those files.

To compare the runtime performance of both implementations, we computed
an average of 5 runs, on a Ubuntu 16.04 machine, i5-7200U Dual Core,
with 8 GB RAM.

In this case, the very first
version of Ztrategic is only 60% slower than the Strafunski library:

Ztrategic     Strafunski
Lines of Code                22            22

Runtime                      16.2s         10.2s

Average Memory Usage         6607.75Kb     6580.16Kb

Haskell Smell eliminators in Ztrategic and Strafunski.

§ RELATED WORK

The work we present in this paper is inspired by the pioneer work of
Sloane who developed Kiama [28]: an embedding of strategic
term rewriting and AGs in the Scala programming language.  In Kiama
attributes are defined as Scala functions, and strategic term
rewriting is expressed on Scala data structures via a set of strategic
While our
approach expresses both attribute computations and strategic term
rewriting as pure functions, Kiama caches attribute values in a global
cache, in order to reuse attribute values computed in the original
tree that are not affected by the rewriting. Such global cache,
however, induces an overhead in order to maintain it updated, that is,
attribute values associated to subtree discarded by the rewriting
process need to be purged from the cache [30]. In
our purely functional setting, we only compute attributes in the
desired rewritten tree (as is the case of the let example shown in
section <ref>).

Influenced by Kiama, Kramer and Van Wyk [14] present
strategy attributes, which is an integration of strategic term
rewriting into attribute grammars. Strategic rewriting rules can use
the attributes of a tree to reference contextual information during
rewriting, much like we present in our work. Their work is
materialized as an extension to the extensible AG system
Silver [34].  They present several practical application
examples, namely the evaluation of $\lambda$-calculus, a regular
expression matching via Brzozowski derivatives, and the normalization
of for-loops. All these examples can be directly expressed in our
setting. They also present an application to optimize translation of
strategies. Because our techniques rely on shallow embeddings, where
no data type is used to express strategies nor AGs, we are not able to
express strategy optimizations, without relying on meta-programming
techniques [27]. Nevertheless, our embeddings result
in very simple and small libraries that are easier to extend and
maintain, specially when compared to the complexity of extending and
maintaining a full language processor system such as Silver.

JastAdd is a reference attribute grammar based system [9]. It
supports most of AG extensions, namely reference and circular
AGs [31]. It also supports tree rewriting, with
rewrite rules that can reference attributes.  JastAdd, however,
provides no support for strategic programming, that is to say, there is
no mechanism to strategic control how the rewrite rules are applied.
The zipper-based AG embedding we integrate in  supports all
modern AG extensions, including reference and circular
AGs [21, 10]. Because strategies and AGs are first
class citizens we can smoothly combine any of such extensions with
strategic term rewriting.

In the context of strategic term rewriting, our  library
is inspired by Strafunski [16]. In fact,
already provides almost all Strafunski functionality. There is,
however, a key difference between these libraries: while Strafunski
accesses the data structure directly,  operates on
zippers. As a consequence, we can easily access attributes from
strategic functions and strategic functions from attribute equations.

The Stratego program transformation language (now part of the Spoofax Language Workbench <cit.>) supports the definition of rewrite rules and programmable rewriting strategies, and it is able to construct new rewrite rules at runtime, to propagate contextual information for concerns such as lexical scope. It is argued in [14] that contextual information is better specified through the usage of inherited attributes for issues such as scoping, name-binding, and type-checking. We present this same usage of inherited attributes in our attribute grammar examples.

§ CONCLUSION

This paper presented a zipper-based embedding of strategic term
rewriting. By relying on zippers, we combined it with a zipper-based
embedding of attribute grammars so that (zipper-based) strategies can
access (zipper-based) AG functional definitions, and vice versa. Thus,
zippers and strategies are first class citizens. We have developed the
strategic programming library and we have used
it to implement several language engineering tasks.

To assess the expressiveness of our approach we compared our Ztrategic
solution to the largest strategic AG developed by the state-of-the-art
Kiama system. In terms of runtime performance we compared our
Ztrategic library to the well established and fully optimized
Strafusnki solution. The preliminary results show that in fact zippers
provided a uniform setting to express both strategic term rewriting
and AGs that are in par with the state-of-the-art. Moreover, since
zippers do not rely on any advanced mechanism of our  hosting
language, namely lazy evaluation, they can be implemented in other
(non-lazy) declarative programming languages. As a consequence, our
joint embeddings can easily be ported to any programming settings
where zippers are available.

§.§ Future Work

To avoid the re-calculation of attribute values, memoized zippers have
been incorporated in the embedding of the zipper-based
AG [10]. This results in a considerable performance
improvement when we run the embedded AG. Our strategic combinators can
also be expressed as memoized zippers, which will provide an
incremental setting for both strategic term rewriting and attribute
grammars. This will result in the rewriting of the equal sub-trees to
be performed once, only.

Our  library can still be generalized to work with any
instead of being restricted to the  monad. In fact. Strafunski
generalizes the monadic infrastructure used in their combinators, by
using, for example, the  monad to gather state-dependent
information, such as number of nodes traversed or number of failed
transformation applications. We will extend our library to incorporate
this generalization, too.

[1]
Adams, M.D.: Scrap your zippers: A generic zipper for heterogeneous types. In:
WGP '10: Proceedings of the 2010 ACM SIGPLAN workshop on Generic programming.
pp. 13–24. ACM, New York, NY, USA (2010). 10.1145/1863495.1863499

[2]
Alblas, H.: Attribute evaluation methods. In: Alblas, H., Melichar, B. (eds.)
International Summer School on Attribute Grammars, Applications and Systems.
LNCS, vol. 545, pp. 48–113 (1991)

[3]
Almeida, J.B., Cunha, A., Macedo, N., Pacheco, H., Proença, J.: Teaching
how to program using automated assessment and functional glossy games
(experience report). Proc. ACM Program. Lang.  2(ICFP) (Jul 2018).
10.1145/3236777, <https://doi.org/10.1145/3236777>

[4]
Balland, E., Brauner, P., Kopetz, R., Moreau, P.E., Reilles, A.: Tom:
Piggybacking rewriting on java. In: Baader, F. (ed.) Term Rewriting and
Applications. pp. 36–47. Springer Berlin Heidelberg, Berlin, Heidelberg

[5]
van den Brand, M.G.J., Deursen, A.v., Heering, J., Jong, H.A.d., Jonge, M.d.,
Kuipers, T., Klint, P., Moonen, L., Olivier, P.A., Scheerder, J., Vinju,
J.J., Visser, E., Visser, J.: The asf+sdf meta-environment: A component-based
language development environment. In: Proceedings of the 10th International
Conference on Compiler Construction. p. 365–370. CC '01, Springer-Verlag,
Berlin, Heidelberg (2001)

[6]
Cordy, J.R.: Txl - a language for programming language tools and applications.
Electronic Notes in Theoretical Computer Science  110,  3–31
(2004). https://doi.org/10.1016/j.entcs.2004.11.006,
proceedings of the Fourth Workshop on Language Descriptions, Tools, and
Applications (LDTA 2004)

[7]
Cowie, J.: Detecting bad smells in haskell. Tech. rep., University of Kent, UK

[8]
Dijkstra, A., Swierstra, S.D.: Typing Haskell with an attribute grammar. In:
Vene, V., Uustalu, T. (eds.) Advanced Functional Programming. pp. 1–72.
Springer Berlin Heidelberg, Berlin, Heidelberg (2005)

[9]
Ekman, T., Hedin, G.: The JastAdd extensible Java compiler. SIGPLAN Not.
42(10),  1–18 (Oct 2007). 10.1145/1297105.1297029,

[10]
Fernandes, J.P., Martins, P., Pardo, A., Saraiva, J., Viera, M.: Memoized
zipper-based attribute grammars and their higher order extension. Sci.
Comput. Program.  173,  71–94 (2019).

[11]
Gray, R.W., Levi, S.P., Heuring, V.P., Sloane, A.M., Waite, W.M.: Eli: A
complete, flexible compiler construction system. Commun. ACM  35(2),
121–130 (Feb 1992). 10.1145/129630.129637,

[12]
Huet, G.: The Zipper. Journal of Functional Programming  7(5),
549–554 (Sep 1997)

[13]
Knuth, D.E.: Semantics of context-free languages. Mathematical systems theory
2(2),  127–145 (1968)

[14]
Kramer, L., Van Wyk, E.: Strategic tree rewriting in attribute grammars. In:
Proceedings of the 13th ACM SIGPLAN International Conference on Software
Language Engineering. p. 210–229. SLE 2020, Association for Computing
Machinery, New York, NY, USA (2020). 10.1145/3426425.3426943,

[15]
Kuiper, M., Saraiva, J.: Lrc - A Generator for Incremental Language-Oriented
Tools. In: Koskimies, K. (ed.) 7th International Conference on Compiler
Construction, CC/ETAPS'98. LNCS, vol. 1383, pp. 298–301. Springer-Verlag
(April 1998)

[16]
Lämmel, R., Visser, J.: Typed combinators for generic traversal. In:
Krishnamurthi, S., Ramakrishnan, C.R. (eds.) Practical Aspects of Declarative
Languages. pp. 137–154. Springer Berlin Heidelberg, Berlin, Heidelberg

[17]
Lämmel, R., Visser, J.: A strafunski application letter. In: Proceedings of
the 5th International Symposium on Practical Aspects of Declarative
Languages. p. 357–375. PADL '03, Springer-Verlag, Berlin, Heidelberg (2003)

[18]
Lämmel, R., Peyton Jones, S.: Scrap your boilerplate: A practical design
pattern for generic programming. vol. 38, pp. 26–37 (03 2003).

[19]
Luttik, S.P., Visser, E.: Specification of rewriting strategies. In:
Proceedings of the 2nd International Conference on Theory and Practice of
Algebraic Specifications. p. 9. Algebraic'97, BCS Learning & Development
Ltd., Swindon, GBR (1997)

[20]
Martins, P., Fernandes, J.P., Saraiva, J.: Zipper-based attribute grammars and
their extensions. In: Du Bois, A.R., Trinder, P. (eds.) Programming
Languages. pp. 135–149. Springer Berlin Heidelberg, Berlin, Heidelberg

[21]
Martins, P., Fernandes, J.P., Saraiva, J., Van Wyk, E., Sloane, A.: Embedding
attribute grammars and their extensions using functional zippers. Sci.
Comput. Program.  132(P1),  2–28 (Dec 2016).

[22]
Mernik, M., Korbar, N., Žumer, V.: Lisa: A tool for automatic language
implementation. SIGPLAN Not.  30(4),  71–79 (Apr 1995).
10.1145/202176.202185, <https://doi.org/10.1145/202176.202185>

[23]
Middelkoop, A., Dijkstra, A., Swierstra, S.D.: Iterative type inference with
attribute grammars. In: Proceedings of the Ninth International Conference on
Generative Programming and Component Engineering. p. 43–52. GPCE '10,
Association for Computing Machinery, New York, NY, USA (2010).
10.1145/1868294.1868302, <https://doi.org/10.1145/1868294.1868302>

[24]
de Moor, O., Backhouse, K., Swierstra, D.: First-class attribute grammars.
Informatica (Slovenia)  24(3) (2000),

[25]
Reps, T., Teitelbaum, T.: The synthesizer generator. SIGPLAN Not.
19(5),  42–48 (Apr 1984). 10.1145/390011.808247,

[26]
Saraiva, J.: Purely Functional Implementation of Attribute Grammars. Ph.D.
thesis, Utrecht University, The Netherlands (December 1999)

[27]
Sheard, T., Jones, S.P.: Template meta-programming for haskell. In: Proceedings
of the 2002 ACM SIGPLAN Workshop on Haskell. p. 1–16. Haskell '02,
Association for Computing Machinery, New York, NY, USA (2002).
10.1145/581690.581691, <https://doi.org/10.1145/581690.581691>

[28]
Sloane, A.M., Kats, L.C.L., Visser, E.: A pure object-oriented embedding of
attribute grammars. Electronic Notes in Theoretical Computer Science
253(7),  205–219 (2010). 10.1016/j.entcs.2010.08.043,

[29]
Sloane, A.M., Roberts, M.: Oberon-0 in kiama. Science of Computer Programming
114,  20–32 (2015).
lDTA (Language Descriptions, Tools, and Applications) Tool Challenge

[30]
Sloane, A.M., Roberts, M., Hamey, L.G.C.: Respect your parents: How attribution
and rewriting can get along. In: Combemale, B., Pearce, D.J., Barais, O.,
Vinju, J.J. (eds.) Software Language Engineering. pp. 191–210. Springer
International Publishing, Cham (2014)

[31]
Söderberg, E., Hedin, G.: Circular higher-order reference attribute
grammars. In: Erwig, M., Paige, R.F., Van Wyk, E. (eds.) Software Language
Engineering. pp. 302–321. Springer International Publishing, Cham (2013)

[32]
Swierstra, S.D., Azero Alcocer, P.R., Saraiva, J.: Designing and implementing
combinator languages. In: Swierstra, S.D., Oliveira, J.N., Henriques, P.R.
(eds.) Advanced Functional Programming. pp. 150–206. Springer Berlin
Heidelberg, Berlin, Heidelberg (1999)

[33]
van den Brand, M.: Introduction—the ldta tool challenge. Science of
Computer Programming  114,  1–6 (2015).
lDTA (Language Descriptions, Tools, and Applications) Tool Challenge

[34]
Van Wyk, E., Bodin, D., Gao, J., Krishnan, L.: Silver: an Extensible Attribute
Grammar System. Electronic Notes in Theoretical Computer Science
203(2),  103–116 (2008). 10.1016/j.entcs.2008.03.047,

[35]
Visser, E.: Stratego: A language for program transformation based on rewriting
strategies. In: Proceedings of the 12th International Conference on Rewriting
Techniques and Applications. p. 357–362. RTA '01, Springer-Verlag, Berlin,
Heidelberg (2001)

[36]
van Wijngaarcien, A., Mailloux, B.J., Peck, J.E.L., Kostcr, C.H.A., Sintzoff,
M., Lindsey, C.H., Meertens, L.G.L.T., Fisker, R.G.: Revised Report on
the Algorithmic Language Algol 68. SIGPLAN Not.  12(5),
1–70 (May 1977). 10.1145/954652.1781176,

§ THE  ATTRIBUTE GRAMMAR

The zipper-based AG function  specifies the computation, via a
synthesized attribute, of the list of names that violate  scope
rules. In Section <ref>, we have presented its
strategic counterpart definition that eliminates most of the copy (and gluing)

[B]errors:: [1.5mu String1.5mu][E]

[B]errors [9]
[9]t=𝐜𝐚𝐬𝐞 ( t) 𝐨𝐟[E]

[21]→errs (t1)[E]

[21]→(errs (t1))(errs (t2))[E]

[21]→(errs (t1))(errs (t2))[E]

[21]→(errs (t1))(errs (t2))[E]

[21]→[1.5mu 1.5mu][E]

[21]→[1.5mu 1.5mu][E]

[21]→mBIn ( t) (env t)[E]

[21]→mNBIn ( t,t) (dcli t)[E]

[24](errs (t2))(errs (t3))[E]

[21]→mNBIn ( t,t) (dcli t)[E]

[24](errs (t2))(errs (t3))[E]

To distinguish the same name declared at different nesting levels, we
define an (inherited) attribute : the outermost let has level $0$
and we increment the level when descending to a let node. The next
zipper-based AG straightforwardly specifies the necessary attribute

[B]lev::Zipper Root→Int[E]

[B]lev t=[10]
[10]𝐜𝐚𝐬𝐞 ( t) 𝐨𝐟[E]

[21](lev ( t))+1[E]

[21]lev ( t)[E]

Attribute grammars system usually provide a declarative language to
define auxiliary semantic functions. Functions  and
stand, respectively, for “must not be in" and
“must be in", are simple lookup functions. Function
needs the level to detect whether a name is erroneously defined at the
same level, or not. Obviously, we could store the level in the
environment. However, in our setting we can access attributes
decorating a tree in our semantic functions. Thus, these two functions
can be defined as follows:

[B]mBIn::String→[1.5mu (String,Zipper Root)1.5mu]→[1.5mu String1.5mu][E]

[B]mBIn name [1.5mu 1.5mu][23]
[23]=[1.5mu name1.5mu][E]

[B]mBIn name ((n,l):es)[23]
[23]=𝐢𝐟 (n≡name) [39]
[39]𝐭𝐡𝐞𝐧 [1.5mu 1.5mu][E]

[39]𝐞𝐥𝐬𝐞 mBIn name es[E]

[8]::(String,Zipper Root)→[1.5mu (String,Zipper Root)1.5mu][E]

[8]→[1.5mu String1.5mu][E]

[B]mNBIn tuple [1.5mu 1.5mu][18]
[21][1.5mu 1.5mu][E]

[B]mNBIn (a1,r1) ((a2,r2):es)[E]

[21]𝐢𝐟 (a1≡a2)∧(lev r1≡lev r2)[E]

[21]𝐭𝐡𝐞𝐧 [1.5mu a11.5mu] 𝐞𝐥𝐬𝐞 mNBIn (a1,r1) es[E]

Zipper-based AG supports most modern extensions of attribute
grammars. For example, in [21] these lookup functions are
expressed via higher-order attributes.

§.§ Boilerplate Code Induced by Data Types

The code in this subsection is boilerplate code that needs to be built
once for each attribute grammar. Note that this code can be
automatically generated through Template
Haskell [27].

A  data type is defined and it represents the data
constructor the zipper is focusing on and therefore must contain all
constructors in the data types.

[B]𝐝𝐚𝐭𝐚 Constructor[19]

The  function looks at the zipper and returns the
aforementioned  data value.

[B]::Zipper a→Constructor[E]

[B] ag=[E]

[4]𝐜𝐚𝐬𝐞 (getHole ag::Maybe Root) 𝐨𝐟[E]

[6]Just (Root )→$\mathit{Root_{P}}$[E]

[6]→𝐜𝐚𝐬𝐞 (getHole ag::Maybe Let) 𝐨𝐟[E]

[13]Just (Let  )→$\mathit{Let_{Let}}$[E]

[13]→𝐜𝐚𝐬𝐞 (getHole ag::Maybe List) 𝐨𝐟[E]

[20]Just (NestedLet   [44]

[20]Just (Assign   )[47]

[20]Just (EmptyList[42]

[26]𝐜𝐚𝐬𝐞 (getHole ag::Maybe Exp) 𝐨𝐟[E]

[26]Just (Add  )[42]

[26]Just (Sub  )[42]

[26]Just (Neg [39]

[26]Just (Var [39]

[26]Just (Const )[42]

[42]→error 34 Error34[E]

The functions  and  model syntactic references
in the AG, and they access information of certain nodes.

[B]::Zipper a→String[E]

[B] ag=[14]
[14]𝐜𝐚𝐬𝐞 (getHole ag::Maybe List) 𝐨𝐟[E]

[19]Just (Assign [35]
[35]v  )→v[E]

[19]Just (NestedLet v  )→v[E]

[26]𝐜𝐚𝐬𝐞 [32]
[32](getHole ag::Maybe Exp) 𝐨𝐟[E]

[32]Just (Var s)[46]

[46]→error 34 Error34[E]

[16]::Zipper a→Maybe Exp[E]

[B] [16]
[22]𝐜𝐚𝐬𝐞 (getHole ag::Maybe List) 𝐨𝐟[E]

[22]Just (Assign  e )[42]
[42]→Just e[E]

§ SMELL ELIMINATION

We define refactoring  through an  strategy that
applies a myriad of transformations, as many times as possible. The
use of  is necessary because performing one
refactoring can enable the application of another refactoring.

[9]::Zipper HsModule→Maybe (Zipper HsModule)[E]

[B]smells [9]
[9]h=applyTP (innermost step) h[E]

[9]𝐰𝐡𝐞𝐫𝐞 step=failTP[30]

These functions are simple in the sense that they try to match a
pattern and replace them with another. They are similar in nature to
we defined in Section <ref>, but the data types themselves
are more complex. We define a transformation to refactor the pattern
into .

[B]joinList::HsExp→Maybe HsExp[E]

[B]joinList [13]
[13](HsInfixApp [26]
[26](HsList [1.5mu h1.5mu]) [E]

[26](HsQVarOp (UnQual [45]
[45](HsSymbol 34 ++34))) [E]

[26](HsList t))[E]

[13]=Just [21]
[21](HsInfixApp [34]
[34]h [E]

[34](HsQConOp (Special HsCons)) [E]

[34](HsList t))[E]

[B]joinList [13]

Next, we find patterns of bad null checking of lists, which are refactored to . The patterns are , ,  and , each represented by one line of the function.
[B]nullList::HsExp→Maybe HsExp[E]

[B]nullList (HsInfixApp [23]
[23](HsApp [31]
[31](HsVar (UnQual[E]

[38](HsIdent 34 length34))) [E]

[31]a) [E]

[23](HsQVarOp (UnQual (HsSymbol 34 ==34))) [E]

[23](HsLit (HsInt 0)))[E]

[13]HsApp (HsVar (UnQual (HsIdent 34 null34))) a[E]

[B]nullList (HsInfixApp [23]
[23](HsLit (HsInt 0)) [E]

[23](HsQVarOp (UnQual (HsSymbol 34 ==34))) [E]

[23](HsApp (HsVar (UnQual[E]

[37](HsIdent 34 length34))) a))[E]

[3]=Just$HsApp (HsVar (UnQual (HsIdent 34 null34))) a[E]

[B]nullList [11]
[11](HsInfixApp [24]
[24]a [E]

[24](HsQVarOp (UnQual (HsSymbol 34 ==34))) [E]

[24](HsList [1.5mu 1.5mu]))[E]

[13]HsApp (HsVar (UnQual (HsIdent 34 null34))) a[E]

[B]nullList [11]
[11](HsInfixApp [24]
[24](HsList [1.5mu 1.5mu]) [E]

[24](HsQVarOp (UnQual (HsSymbol 34 ==34))) [E]

[13]HsApp (HsVar (UnQual (HsIdent 34 null34))) a[E]

[B]nullList =Nothing[E]

We remove redundant boolean checks, such as  and , by refactoring them to . Similarly,  and  are refactored to .

[B]redundantBoolean::HsExp→Maybe HsExp[E]

[B]redundantBoolean [19]

[19](HsCon (UnQual (HsIdent 34 True34)))[E]

[19](HsQVarOp (UnQual (HsSymbol 34 ==34)))[E]

[3]=Just a[E]

[B]redundantBoolean [19]

[19](HsQVarOp (UnQual (HsSymbol 34 ==34)))[E]

[19](HsCon (UnQual (HsIdent 34 True34))))[E]

[3]=Just a[E]

[B]redundantBoolean [19]

[19](HsCon (UnQual (HsIdent 34 False34)))[E]

[19](HsQVarOp (UnQual (HsSymbol 34 ==34)))[E]

[3]=Just$(HsApp (HsVar (UnQual (HsIdent 34 not34))) a)[E]

[B]redundantBoolean [19]

[19](HsQVarOp (UnQual (HsSymbol 34 ==34)))[E]

[19](HsCon (UnQual (HsIdent 34 False34))))[E]

[3]=Just$(HsApp (HsVar (UnQual (HsIdent 34 not34))) a)[E]

[B]redundantBoolean =Nothing[E]

Finally, we remove redundant usages of  clauses by refactoring  into  and, conversely,  into .

[B]reduntantIf::HsExp→Maybe HsExp[E]

[B]reduntantIf (HsIf [20]
[20]a [E]

[20](HsCon (UnQual (HsIdent 34 True34))) [E]

[20](HsCon (UnQual (HsIdent 34 False34))))[E]

[3]=Just a[E]

[B]reduntantIf (HsIf [20]
[20]a [E]

[20](HsCon (UnQual (HsIdent 34 False34))) [E]

[20](HsCon (UnQual (HsIdent 34 True34))))[E]

[3]=Just$HsApp (HsVar (UnQual (HsIdent 34 not34))) a[E]

[B]reduntantIf =Nothing[E]

We can easily extend  by implementing more refactor
transformations as simple  functions and appending them in
the definition of .