Scrap Your Boilerplate with Object Algebras
Haoyuan Zhang
Zewei Chu
Bruno C. d. S. Oliveira

Tijs van der Storm














    






 
     

 








The University of Hong Kong, China{hyzhang,jason91,bruno}@cs.hku.hk

Centrum Wiskunde & Informatica (CWI), The
Netherlands
storm@cwi.nl  



Abstract

1.

Traversing complex Abstract Syntax Trees (ASTs) typicallyrequires large amounts of tedious boilerplate code. For many
operations most of the code simply walks the structure, andonly a small portion of the code implements the functionality that motivated the traversal in the ﬁrst place. This paper
presents a type-safe Java framework called Shy that removes
much of this boilerplate code. In Shy Object Algebras areused to describe complex and extensible AST structures. Using Java annotations Shy generates generic boilerplate codefor various types of traversals. For a concrete traversal, usersof Shy can then inherit from the generated code and override only the interesting cases. Consequently, the amount ofcode that users need to write is signiﬁcantly smaller. Moreover, traversals using the Shy framework are also much morestructure shy, becoming more adaptive to future changes orextensions to the AST structure. To prove the effectivenessof the approach, we applied Shy in the implementation ofa domain-speciﬁc questionnaire language. Our results showthat for a large number of traversals there was a signiﬁcantreduction in the amount of user-deﬁned code.

Various language processing tools or libraries for programming languages, domain-speciﬁc languages, mark-up languages like HTML, or data-interchange languages like XML
or JSON require complex Abstract Syntax Tree (AST) structures. In those applications ASTs are the key data structureneeded to model the various constructs of these languages.
Such ASTs have various different types of nodes, which canrange from a few dozen to several hundred kinds of nodes(for example in the ASTs of languages like Java or Cobol).
Static types are helpful to deal with such complex ASTs.
Static types formalize the distinction between different kindsof nodes. Furthermore the distinctions are helpful to ensurethat traversals over these ASTs have an appropriate piece ofcode that deals with each different type of node. This canprevent a large class of run-time errors that would not be
detected otherwise.
Unfortunately, when traversing such ASTs, the number ofnodes and the enforced type distinctions between nodes canlead to so-called boilerplate code [11]: code that is similar
for most types of nodes and which essentially just walks the
structure. Operations where the “interesting” code is limited
to only a small portion of nodes are called structure shy [17].
A typical example is computing the free variables of an
expression in some programming language. In this case, theinteresting code occurs in the nodes representing the binding
and variable constructs. In all other cases, the code would
just deal with walking the structure. In ASTs with dozens or
hundreds of kinds of nodes, having to explicitly write codefor each kind of node is both tedious and error-prone.
The boilerplate problem in implementing traversals hasreceived considerable attention in the past. For example,
both Adaptive Object-Oriented Programming (AOOP) [17]and Strategic Programming [3, 26] are aimed partly at solving this problem. Most approaches to AOOP and strategic programming use some meta-programming techniques,
such as code generation or reﬂection. The use of metaprogramming offers programmers an easy way to avoid having to write boilerplate code. This has important beneﬁts:
users have to write much less code; and the code becomesmuch more adaptive to changes. Nevertheless, such meta-

Categories and Subject Descriptors D.3.2 [Programming
Languages]: Language Classiﬁcations—Object-Oriented
Programming; F.3.3 [Logics and Meanings of Programs]:
Studies of Program Constructs
General Terms Languages
Keywords Object algebras, boilerplate code, Java, adaptive
object-oriented programming

This is the author’s version of the work. It is posted here for your personal use. Not forredistribution. The definitive version was published in the following publication:

OOPSLA’15, October 25–30, 2015, Pittsburgh, PA, USA
c 2015 ACM. 978-1-4503-3689-5/15/10...
http://dx.doi.org/10.1145/2814270.2814279

127

Introduction

programming based approaches usually come at the cost ofother desirable properties, such as type-safety, extensibilityor separate compilation. The functional programming community has also studied the problem. For instance, the popular “Scrap your boilerplate” [11] approach supports typesafety and separate compilation. Most of the techniques usedin functional languages, however, cannot be easily ported tomainstream OO languages like Java, and are limited in termsof extensibility.
This paper presents a Java framework called Shy thatallows users to deﬁne type-safe and extensible structureshy operations. Shy uses Object Algebras [19] to describe
ASTs, and to write operations over ASTs in a style similar
to writing folds in functional programming. However unlike
standard folds in functional programming, Object Algebras
are extensible: when new kinds of nodes are introduced in
the data type, the operations can be extended as well, withoutchanging existing code.
In Shy Object Algebra interfaces are combined with Java
annotations to generate generic traversal code automatically.
The generated code accounts for four different types of traversals: queries; transformations; generalized queries; andcontextual transformations. Each of these four types of traversals is implemented as an Object Algebra. Programmers
who want to implement structure-shy traversals can then inherit from one of these four Object Algebras, and override
only the cases that deal with the interesting parts of thetraversal. Consequently traversals written in Shy are:tails in Section 11) show that for a large number of traversals there was a signiﬁcant reduction in the amount of userdeﬁned code: only 4% to 21% of the AST cases had to be
implemented in comparison with code written without Shy.
Although Shy’s functional programming inspired idioms
are new to mainstream Java programmers, the use of standard Java constructs and techniques makes Shy easy to implement, integrate in existing environments, and use. Moreover, although Java was chosen as the implementation language for Shy, our approach should apply to any objectoriented language with support for generics and annotations.
In summary, the contributions of this paper are:
• Design patterns for generic traversals. We provide a

set of design patterns for various types of traversals using Object Algebras, including: queries, transformations,generalized queries and contextual transformations.
• The Shy Java framework. We show that those design
patterns can be automatically generated for a given Object Algebra interface. The Shy framework1 realizes thisidea by using Java annotations to automatically generate
generic traversals.
• Applications and examples: We show various examplesof traversals, such as free variables and substitution operations, implemented concisely with Shy. Moreover we
illustrate how certain kinds of desugarings can be implemented using transformations, and how multiple transformations can be chained together in a pipeline.
• Case study. We illustrate the beneﬁts of Shy using a casestudy based on the QL domain-speciﬁc language. The
results of our case study show signiﬁcant savings in terms
of user-deﬁned traversal code. The case study also showsthat Shy does not incur signiﬁcant performance overhead
compared to a regular AST-based implementation.

• Small in size: With Shy the amount of code that pro-grammers need to write a structure-shy traversal is signiﬁcantly smaller. Often traversals in Shy are implementable in just a few lines of code, even for complex
ASTs with hundreds of different types of nodes.
• Adaptive and structure shy: Traversals written with
Shy can omit boilerplate code, making traversals more
adaptive to future changes or extensions to the data type.
• Type-safe: Shy traversals are directly written in Java andthe Java type-system ensures type-safety. No run-timecasts are needed for generic traversal code or for userdeﬁned traversal code.
• Extensible with separate compilation: Traversals inherit type-safe extensibility from Object Algebras. Bothtraversals and the AST structures are extensible. Thus it ispossible to reuse traversal code for ASTs extended withadditional node types. Furthermore Shy traversals support separate compilation.
• Implemented in plain Java: Shy traversals do not require a new tool or language. The approach is library
based and only uses Java annotations.

2.

Background: Object Algebras

Object Algebras capture a design pattern to solve the Expression Problem [29]. As a result Object Algebras support
modular and type-safe extensibility in two dimensions: data
variants and operations. Object Algebras can be used conveniently to model recursive data types, such as ASTs. Here
we brieﬂy introduce Object Algebras using the example of asimple expression language.
interface ExpAlg<E> {E Lit(int n);
E Add(E l, E r);}

The above code shows an Object Algebra interface whichmodels literal and addition expressions. The interface resembles an abstract factory interface, but instead of constructing
objects of a concrete type, the result is abstract through thetype parameter E. A concrete Object Algebra will implement
such an interface by instantiating the type parameter with

To prove the effectiveness of the approach, we have applied
Shy in the implementation of QL, a domain-speciﬁc language (DSL) for deﬁning questionnaires that has been used
before as a benchmark language [7, 9]. Our results (see de-

1 Available at: https://github.com/JasonCHU/SYBwithOA

128

a type that constructs objects for a particular purpose. For
instance, evaluation of expressions can be implemented asfollows:

form DriverLicense {
name: "What is your name?" string
age: "What is your age?" integer
if (age >= 18)
license: "Have a driver’s license?" boolean}

class Eval implements ExpAlg<Integer> {public Integer Lit(int n) {return n;}
public Integer Add(Integer l, Integer r) {return l + r;}}

Figure 1. Example QL questionnaire: driver’s license.
Users can then pass instances of Object Algebras to thosestructures for applying operations:println(makeExp(new Eval()));
println(makeExp(new Print()));
println(makeMul(new MulEval()));

Using this algebra to create expressions will immediately
evaluate the expression to its result. To add another operation
the interface ExpAlg is implemented again. As an example,
the class Print presented below shows a simple printing
operation on expressions. Both examples illustrate extension
in the dimension of operations.

The results are “5”, “2 + 3” and “20”, respectively.
In summary, Object Algebra interfaces describe recursive data types, and implementations of those interfaces represent operations. Extending the interface allows developers to extend the data type with new data variants, and(re)implementing the interface allows developers to deﬁneoperations. Finally, extension in both dimensions is fully
type-safe and does not compromise separate compilation.

class Print implements ExpAlg<String> {public String Lit(int n) { return "" + n; }public String Add(String l, String r) {return l + " + " + r;}}

The other dimension of extensibility (adding data variants) is realized by extending the Object Algebra interface
itself. For instance, the interface MulAlg deﬁned below extends the original ExpAlg with multiplication expressions.

3.

An Overview of Shy

This section starts by illustrating the problem of boilerplatecode when implementing traversals of complex structures. It
then shows how Shy addresses the problem using a combination of Object Algebras [19] and Java annotations.

interface MulAlg<E> extends ExpAlg<E> {E Mul(E l, E r);}

3.1

The key feature of Object Algebras is that the existing operations (evaluation and printing) can now be extended tosupport multiplication without having to change the existing
Eval and Print classes. For example, evaluation is extended
with multiplication as follows:

Traversing Object-Oriented ASTs

We start by introducing the problem of boilerplate code byconsidering a simpliﬁed variant of the QL language used inour case study [9], called MiniQL. Just like QL, MiniQL canbe used to describe interactive questionnaires.
An example MiniQL program is shown in Figure 1. The
questionnaire ﬁrst asks for the user’s name and age, and then,if the age is greater than or equal to 18, asks if the user has adriver’s license. Because of the conditional construct, the last
question will only appear when the user is actually eligible
to have driver’s license.
MiniQL’s abstract syntax contains forms, statements (ifthen and question) and expressions (only literals, variables
and greater-than-or-equal). A traditional OO implementationis shown on the left Figure 2. A form (class Form) has a nameand consists of a list of statements. Statements are conditionals (If) which contain an expression and a statement body,and questions (Question) which have a name, label and type.
Expressions are standard, but limited to literals (Lit), variables (Var) and greater-than-or-equal (GEq).
The code in Figure 2 also shows a query over MiniQL
structures, namely the collection of used variables. The operation is deﬁned using the method usedVars, declared in
the abstract superclasses Stmt and Exp (omitted for brevity),
and implemented in the concrete statement and expression
classes. As can be seen, the only interesting bit of code isclass MulEval extends Eval
implements MulAlg<Integer> {public Integer Mul(Integer l, Integer r) {return l * r;}}

Client code The client code below shows how structures
are created and operations are applied using Object Algebras. For example, The generic interface ExpAlg is used tocreate a structure as follows:<E> E makeExp(ExpAlg<E> alg) {return alg.Add(alg.Lit(2), alg.Lit(3));}

Such a structure represents the expression “2 + 3”. Similarly, the extended interface MulAlg supporting multiplication
creates the expression “(2 + 3) * 4” as follows:<E> E makeMul(MulAlg<E> alg) {return alg.Mul(alg.Add(alg.Lit(2), alg.Lit(3)),
alg.Lit(4));}

129

class Form {String name; List<Stmt> body;
Set<String> usedVars() {Set<String> vars = new HashSet<>();
body.forEach(s -> vars.addAll(s.usedVars()));
return vars;}}

class UsedVars implements
QLAlg<Set<String>, Set<String>, Set<String>> {Set<String> Form(String n, List<Set<String>> b) {Set<String> vars = new HashSet<>();
b.forEach(s -> vars.addAll(s));
return vars;}

class If extends Stmt {Exp cond; Stmt then;
Set<String> usedVars() {Set<String> vars=new HashSet<>(cond.usedVars());
vars.addAll(then.usedVars());
return vars;}}

Set<String> If(Set<String> c, Set<String> t) {Set<String> vars = new HashSet<>(c);vars.addAll(t);return vars;}
Set<String> Question(String n,String l,String t) {return Collections.emptySet();}class Question extends Stmt {String name, label, type;
Set<String> usedVars() { return emptySet(); }}Set<String> Lit(int x) {return Collections.emptySet();}class Lit extends Exp {int n;
Set<String> usedVars() { return emptySet(); }}Set<String> Var(String x) {return Collections.singleton(x);}Set<String> GEq(Set<String> l, Set<String> r) {Set<String> vars = new HashSet<>(l);vars.addAll(r);return vars;}

class Var extends Exp {String x;
Set<String> usedVars() { return singleton(x); }}}class GEq extends Exp {Exp lhs, rhs;
Set<String> usedVars() {Set<String> vars = new HashSet<>(lhs.usedVars());
vars.addAll(rhs.usedVars());
return vars;}}

Figure 2. Implementing the “used variables” operation using traditional ASTs (left) and Object Algebras (right).
the usedVars method in class Var. All other implementations
merely deal with aggregating results of their child nodes, or
returning a default empty set.
The boilerplate code exhibited in the usedVars query
often also applies to transformations. Consider for example
a rename transformation which takes a Form and returns
another form where the occurrences of the speciﬁed variable
are renamed. Again, the only interesting cases would be in
the Var and Question classes, where the actual renaming
is applied. All other classes, however, require boilerplate
to recreate the structure. The full code in Appendix A.1.1
contains a simple example of such a rename operation as
well.
In addition to the signiﬁcant amount of boilerplate code,
there is another drawback to the traditional OO solution,
which is that it does not support extensibility along the di-mension of operations. Each new operation requires pervasive changes across the AST classes.
3.2

Modeling MiniQL with Object Algebras

The right-hand side of Figure 2 shows the used variables operation implemented using Object Algebras. The operation
is a class implementing the Object Algebra interface (QLAlg)
shown in Figure 3.
The UsedVars class provides an implementation for eachof the methods in the object algebra interface, which together deﬁne the full used variables operation. Since the result ofcollecting those variables is Set<String>, all the type parameters are set to that type. Most of the method implementations simply traverse the child nodes and accumulate
the variable names. That is the case, for example, for Form.
Again, the only method implementation that does something
different is Var, which returns the x argument.

130

@Algebra
public interface QLAlg<E, S, F> {F Form(String name, List<S> body);
S If(E cond, S then);
S Question(String name,String label,String type);
E Lit(int n);
E Var(String x);
E GEq(E lhs, E rhs);}

class UsedVars implements QLAlgQuery<Set<String>> {public Monoid<Set<String>> m() {return new SetMonoid<String>();}public Set<String> Var(String name) {return Collections.singleton(name);}}

Figure 4. MiniQL used variables, implemented with Shy.

Figure 3. Object Algebra interface of the MiniQL abstract
syntax.
class Rename<E, S, F> extends QLAlgTrans<E, S, F> {String from, to;Rename(QLAlg<E,S,F> alg, String from, String to) {super(alg);this.from = from;this.to = to;}public S Question(String n, String l, String t) {n = n.equals(from) ? to : n;return qLAlg().Question(n, l, t);}public E Var(String x) {x = x.equals(from) ? to : x;
return qLAlg().Var(x);}}Unlike the standard OOP implementation, Object Algebras support adding operations without changing existingcode. For instance, the renaming operation mentioned above
could be realized as follows:class Rename<E, S, F> implements QLAlg<E, S, F> {QLAlg<E, S, F> alg;
String from, to;
F Form(String n, List<S> b) {return alg.Form(n, b);}
S Question(String n, String l, String t) {n = n.equals(from) ? to : n;return alg.Question(n, l, t);}...
E Var(String x) {x = x.equals(from) ? to : x;
return alg.Var(x);}Figure 5. MiniQL renaming, implemented with Shy.

The two types of traversals are, for instance, sufﬁcient tocapture the used variables and renaming operations.
With Shy, programmers just need to add the @Algebra annotation to the deﬁnition of QLAlg to get the code for genericqueries and transformations. An example of that annotationis already shown in Figure 3. Triggered by the annotation,
Shy generates base traversal interfaces with Java 8 default
methods which can then be overridden to implement specific behavior. For instance, for the MiniQL algebra, Shy generates interfaces QLAlgQuery and QLAlgTrans which can beused to implement UsedVars and Rename in only a fraction of
the code2 .
The Shy-based implementation of both operations isshown in Figure 4 and 5. In contrast to Figure 2, the code in
Figure 4 is much shorter. By implementing the QLAlgQueryand QLAlgTrans interface, only the methods Question and
Var need to be overridden: all the other methods perform basic accumulation for queries and basic reconstruction in thecase of transformations. For queries the only extra thing a
programmer has to do is to provide an instance of a monoid,
which is used to specify how to accumulate the results during
the traversal. Similarly, for transformations, the programmer
needs to pass an algebra for providing the constructors forcreating the result of a transformation.

}

Each constructor reconstructs a new node using an auxiliary MiniQL algebra alg. Almost all the method implementations reconstruct the structure with no changes using themethods of alg. For instance, the Form method just recreates the form in the algebra alg. The other boilerplate cases
are omitted for brevity; the full code can be found in Appendix A.1.2. The two exceptions are the methods Question
and Var, where the identiﬁers with the given name from arerenamed to to.
Although the Object Algebra encoding of MiniQL solves
the problem of extensibility, the traversal code still contains
boilerplate code. In both UsedVars and Rename, the onlyinteresting code is in a small number of cases. Ideally, we
would like to write only the code for the interesting cases,
and somehow “inherit” the tedious traversal code.
3.3

Shy: An Object Algebra Framework for Traversals

To deal with the boilerplate problem we created Shy: a Java
Object Algebras framework, which provides a number ofgeneric traversals at the cost of a single annotation. The key
idea in Shy is to automatically create highly generic Object
Algebras, which encapsulate common types of traversals. In
particular Shy supports generic queries and transformations.

2 The generated code is available in Appendix A.1.3 and A.1.4.

131

Client code To use the queries and operations on a questionnaire like the one in Figure 1, we need a function to create a structure using the generic MiniQL interface:interface FreeVars extends ExpAlg<Set<String>> {default Set<String> Var(String s) {return Collections.singleton(s);}default Set<String> Lit(int i) {return Collections.emptySet();}default Set<String> Add(Set<String> e1,
Set<String> e2) {return Stream.concat(e1.stream(), e2.stream()).collect(Collectors.toSet());}}<E, S, F> F makeQL(QLAlg<E, S, F> alg) {return alg.Form("DriverLicense", Arrays.asList(
alg.Question("name", "Name?", "string"),
alg.Question("age", "Age?", "integer"),alg.If(alg.GEq(alg.Var("age"),alg.Lit(18)),
alg.Question("license","License?", "boolean"))));}

Figure 6. Free variables as an Object Algebra.
Since both queries and transformations are implementations of the MiniQL interface, they can be passed to the
makeQL function deﬁned above:

4.1

Figure 6 shows a standard approach for computing free variables using Object Algebras3 . A set of strings is used to collect the names of the free variables. The Var method returns
a singleton set of s, whereas the Lit method returns an empty set. The more interesting case is in the Add method, where
the two sets are joined into one.
The typical pattern of a query is to collect some information from some of the nodes of the structure, and to aggregate the information that comes from multiple child nodes.
For example, in the case of free variables, the strings fromthe Var nodes are collected, and in the Add nodes the information from multiple children is merged into a single set.
An important observation about queries is that the codeto aggregate information tends to be the same: if we hada subtraction node, the code would be essentially identicalto Add. Moreover, there are only very few types of nodes
that contain relevant information for the query. For nodes
that contain information that is not relevant to the query,
we simply return a neutral value (such as the empty set in
Lit). Nonetheless, a programmer has to write this boringboilerplate code handling the traversals. While for the small
structure presented here this may not look too daunting, in alarge structure with dozens or even hundreds of constructors
such code becomes a signiﬁcant burden.

println(makeQL(new UsedVars()));
println(makeQL(new Rename<>(new UsedVars(),"age", "AGE")));

This code prints out [age] and [AGE], which are the set ofused variables before and after renaming, respectively. Note
how the Rename transformation transforms the questionnaire
into the UsedVars algebra.
The remainder of the paper provides the details and implementation techniques used in Shy. Besides basic queries
and transformations, Shy also supports two generalizationsof these types of traversals called generalized queries andcontextual transformations.

4.

Boilerplate Queries

QueriesThis section shows the ideas behind generic queries and how
they are implemented in Shy. A query is an operation thattraverses a structure and computes some aggregate value.
The inspiration for queries comes from similar types oftraversals used in functional programming libraries, such as“Scrap your Boilerplate” [11].
The following code shows a variant of the type of expressions shown in Section 2, represented as the Object Algebrainterface ExpAlg.

4.2

Generic Queries

A better approach would be to abstract the generic traversal and accumulation code for queries. This way, when programmers need to implement query operations, they can
simply reuse the generic traversal code and focus only on
dealing with the nodes that do something interesting.
The code that captures the aggregation and collectionof information can be captured by a well-known algebraic
structure called a monoid. Monoids are commonly used infunctional programming for such purposes, but they are per-@Algebra
interface ExpAlg<Exp> {Exp Var(String s);
Exp Lit(int i);
Exp Add(Exp e1, Exp e2);}

We will use this minimal Object Algebra interface throughout the rest of the paper to illustrate the various different
types of traversals supported by Shy. Three different kindsof nodes exist: a numeric literal, a variable or the addition of
two expressions. Queries are illustrated by implementing an
operation to compute the free variables in an expression.

3 Here and in the following we will use interfaces with default-methods(as introduced in Java 8) to combine queries and transformations using
multiple inheritance.

132

There are two important differences to the implementationin Figure 6. The ﬁrst difference is that the monoid to be usedneeds to be speciﬁed. However, the code for the monoid
is still quite short (only requires two method implementations) and, more importantly, it is highly reusable. Indeed
the SetMonoid is reused throughout the paper on various examples of queries. Because monoid instances are so general purpose, the Shy library already contains many common
monoid implementations. Users do not usually have to deﬁne these instances themselves. The second difference is thatnow only the case for variables needs to be deﬁned: the othercases are inherited from ExpAlgQuery.
The traversal code in ExpAlgQuery is entirely mechanicaland can be automatically generated. This is precisely what
Shy does. Annotating algebra interfaces, such as ExpAlg,
with the annotation @Algebra, triggers automatic generationof generic query interfaces, such as ExpAlgQuery. The general template in Shy for an algebra Alg<X1 , ..., Xn >, withconstructors f1 , ..., fm is shown next:

interface ExpAlgQuery<Exp> extends ExpAlg<Exp> {Monoid<Exp> m();default Exp Var(String s) { return m().empty(); }default Exp Lit(int i) { return m().empty(); }default Exp Add(Exp e1, Exp e2) {return m().join(e1, e2);}}

Figure 7. Generic queries using a monoid.
haps less commonly known in object-oriented programming.
The interface of a monoid is deﬁned as follows:interface Monoid<R> {R join(R x, R y);
R empty();}

Intuitively, the join() method is used to combine the information from substructures, and empty() is an indicator of“no information”. Using the monoid operations alone, it ispossible to write a generic query. Figure 7 shows how this isachieved. In nodes that contain child nodes, such as Add, theinformation is aggregated using join. In nodes that containother information, such as Var and Lit, the query returns
empty. This allows concrete queries to be implemented byoverriding methods from multiple, different algebras.
4.3

interface AlgQ <R> extends Alg<R,...,R> {Monoid<R> m();default R fi () {return m().empty();}default R f j (R p1 , ..., R pk ) {return m().join(p1 , m().join(p2 , ..., m().join(pk−1 , pk )...)));}

Free Variables with Generic Queries...

The ExpAlgQuery interface provides an alternative way to deﬁne the free variables operation. Instead of directly deﬁning
the free variables operation, ExpAlgQuery can be inherited,
provided that the method m() is implemented. In the case of
free variables, the monoid returned by m() is an implementation of the Monoid interface for sets:}

Note that interface AlgQ extends Alg so that all type parameters are uniﬁed as type R. All arguments to a constructor
f j are combined with join from the monoid m(). Argumentswith primitive types, like int, boolean or String, are ignored
by default.

class SetMonoid<X> implements Monoid<Set<X>> {public Set<X> empty() {return Collections.emptySet();}public Set<X> join(Set<X> x, Set<X> y) {Set<X> tmp = new HashSet<>(x);tmp.addAll(y);return tmp;}}

5.

Generalized Queries

The previous section introduced simple queries where eachconstructor contributes to a single monoid. Recursive datatypes, however, often have multiple syntactic categories, forinstance expressions and statements. In such multi-sorted
Object Algebras each sort is represented by a different typeparameter in the algebra interface. In this section we present
generalized queries, where each such type parameter can beinstantiated to different monoids. It turns out that, for some
operations, this generalized version of queries is needed.

The method empty() corresponds to the empty set, and join() is implemented as union. Using this monoid the freevariables operation is deﬁned as follows:interface FreeVars extends ExpAlgQuery<Set<String>>{
default Monoid<Set<String>> m() {return new SetMonoid<String>();}default Set<String> Var(String s) {return Collections.singleton(s);}}Example: Data Dependencies. A simple example of a generalized query is the extraction of the data dependencies
between assignment statements and variables in simple imperative programs. To express this query, the simple ExpAlg
is ﬁrst extended with statements using the StatAlg interface
deﬁned as follows:133interface G_StatAlgQuery<Exp, Stat>
extends StatAlg<Exp, Stat> {interface DepGraph extends
G_ExpAlgQuery<Set<String>>,
G_StatAlgQuery<Set<String>, Set<Pair<String,
String>>> {default Monoid<Set<String>> mExp(){
return new SetMonoid<>();}
default Monoid<Set<Pair<String, String>>> mStat(){return new SetMonoid<>();}
default Set<String> Var(String x){
return Collections.singleton(x);}default Set<Pair<String, String>>
Assign(String x, Set<String> e){
Set<Pair<String, String>> deps = new HashSet<>();
e.forEach(y -> deps.add(new Pair<>(x, y)));return deps;}}

Monoid<Exp> mExp();
Monoid<Stat> mStat();default Stat Assign(String x, Exp e) {return mStat().empty();}default Stat Seq(Stat s1, Stat s2) {return mStat().join(s1, s2);}}

Figure 8. Default implementation of generalized queries
over many-sorted statement algebra.

@Algebrapublic interface StatAlg<Exp, Stat> {Stat Seq(Stat s1, Stat s2);
Stat Assign(String x, Exp e);}

Figure 9. Dependency graph with a generalized query.
Client code A structure using the generic interfaces ExpAlg
and StatAlg is created as follows:

The StatAlg interface deﬁnes statement constructors forsequential composition (Seq) and assignment (Assign). Theinterface does not extend the ExpAlg interface; we rely on
multiple inheritance of Java interfaces to combine implementations of these interfaces later (see Figure 9).
The generated default implementation of queries overstatements is shown in Figure 8, while the generated code forexpressions (G_ExpAlgQuery) is presented in Appendix A.1.5.
Note that the interface declares two monoids, one for each
sort. Since the Assign and Seq constructors create statements, they return elements of the mStat() monoid. Furthermore, because it is impossible to automatically join a
monoid over one type with a monoid over another type, thee argument in Assign is ignored. As a result, a concrete implementation normally has to override this case to deal withthe transition from expressions to statements.
Data dependencies are created by assignment statements:
for a statement Assign(String x, Exp e) method, the variable x will depend on all variables appearing in e. The resultof extracting such dependencies can be represented as binary
relation (a set of pairs). In expressions we need to collect thefree variables, which can be stored in a set of strings. Thusin this traversal two monoids are involved: a monoid for aset of pairs of strings; and a monoid for a set of strings.
To implement the extraction of data dependencies only
two cases have to be implemented: the variable (Var) casefrom the ExpAlg signature; and the assignment (Assign) casefrom the StatAlg signature. The implementation is shownin Figure 9. Note that the Assign case takes the input Set<
String> e and uses it to create the dependency relation. The
propagation of dependencies across sequential composition
is automatic, as is the propagation of the set of variables
through the different types of expressions.

<E, S, A extends ExpAlg<E> & StatAlg<E, S>>
S makeStat(A a) {return a.Seq(
a.Assign("x", a.Add(a.Var("x"), a.Lit(3))),a.Assign("y", a.Add(a.Var("x"), a.Var("z"))));}

Note that here the argument of makeStat must implement
both ExpAlg and StatAlg. To achieve this in Java, makeStat
has a type parameter A which is required to implement
both interfaces. Using makeStat we can pass an instanceof DepGraph to compute the dependencies of the statement.
println(makeStat(new DepGraph(){}));The result is [<x, x>, <y, x>, <y, z>], as expected.

6.

Transformations

Queries are a way to extract information from a data structure. Transformations, on the other hand, allow data structures to be transformed into new structures. Just as with
queries, we can distinguish code that deals with traversing
the data structure from code that actually transforms the
structure. In this section we show how to avoid most traversal boilerplate code in the context of transformations using
Shy.
6.1

Transformations, Object Algebra Style

A simple example of a transformation algebra, using the
Object Algebra interface ExpAlg, is substituting expressions
for variables. A manual implementation based on Object
Algebras is shown in Figure 10.
The expression to be substituted, and the variable to substitute for are provided by the methods e() and x() respectively. The method expAlg() is an instance of ExpAlg on134interface SubstVar<Exp> extends ExpAlg<Exp> {ExpAlg<Exp> expAlg();
String x(); Exp e();default Exp Var(String s) {return s.equals(x())? e(): expAlg().Var(s);}default Exp Lit(int i) { return expAlg().Lit(i); }default Exp Add(Exp e1, Exp e2) {return expAlg().Add(e1, e2);}}interface ExpAlgTransform<Exp> extends ExpAlg<Exp> {ExpAlg<Exp> expAlg();
default Exp Var(String s) {return expAlg().Var(s);}default Exp Lit(int i) { return expAlg().Lit(i); }default Exp Add(Exp e1, Exp e2) {return expAlg().Add(e1, e2);}}

Figure 11. Traversal-only base interface for implementing
transformations of expressions.

Figure 10. A normal algebra-based implementation of variable substitution.

interface AlgT <X1 ,...,Xn > extends Alg<X1 ,...,Xn > {Alg<X1 , ..., Xn > alg();

which the transformation is based. Since Object Algebras arefactories, the transformation is executed immediately during
construction of tree structures. For instance, calling Var("x") on a SubstVar object with x() returning "x" immediately
returns the result of e() (the original variable expression isnever created). In the other cases, the original structure isrecreated in the algebra expAlg().
The following code shows how the transformation could
be used:default Xi f j (X1p p1 , ..., Xkp pk ) {return alg().f j (p1 , ..., pk );

}

...
}

Figure 12. Generic template for generating boilerplate oftransformations.

FreeVars fv = new FreeVars() {};SubstVar<Set<String>> subst =new SubstVar<Set<String>>() {public ExpAlg<Set<String>> expAlg() {return fv;}
public String x() { return "x"; }public Set<String> e() {return fv.Add(fv.Lit(1),fv.Var("y"));}};Set<String> res = subst.Var("x");forming the traversal (shown in Figure 11). A concrete transformation can then selectively override the cases of interest.
Variable substitution can now be implemented as follows:interface SubstVar<Exp>
extends ExpAlgTransform<Exp> {String x(); Exp e();default Exp Var(String s) {return s.equals(x())? e(): expAlg().Var(s);}}In this case, only the method Var() is overridden.
Just like in the case of queries, the traversal code in
ExpAlgTransform is entirely mechanical and can be automatically generated by Shy. Figure 12 shows the general template for the generated code. Here AlgT extends Alg with thesame type parameters and the base algebra alg() is declaredinside.

The SubstVar interface is instantiated with expAlg() returning an instance of the FreeVars algebra deﬁned earlier(e.g., Figure 6). The x() method returns the variable to be
substituted ("x"). Finally, the e() returns a new expression
1 + y over the fv algebra. When expressions are created on
the subst algebra, the result is the set of free variables after
the substitution has taken place. As a result, res will contain
only "y".
Note that this allows pipelining of transformations: there
is no reason expAlg() cannot return yet another transformation algebra, for instance, a another instance of SubstVar realizing a different substitution. We elaborate on composing
transformations this way in Section 11.2.
Unfortunately, we again observe the problem of traversalonly boilerplate code: the Lit and Add methods of Figure 10
simply delegate to the base algebra expAlg(), without doing
any real work.
6.2

7.

Contextual Transformations

The previous section introduced a simple template for deﬁning transformations. Transformations in this style may only
depend on global context information (e.g., x(), e()). Manytransformations, however, require context information thatmight change during the traversal itself. In this section we
instantiate algebras over function types to obtain transformations which pass information down during traversal. Insteadof having the algebra methods delegate directly to base algebra (e.g., expAlg()), this now happens indirectly throughclosures that propagate the context information.
Figure 13 shows the general template for an Alg<X1, X2, ..., Xn>, with constructors f1, ..., fm. Note that inter-

Generic Traversal CodeThe boilerplate code in transformations can be avoided bycreating a super-interface containing default methods per-135

interface AlgCT <C,X1 ,...,Xn >extends Alg<Function<C,X1 >,...,Function<C,Xn >> {Alg<X1 , ..., Xn > alg();

interface DeBruijn<E> extends
G_ExpAlgTransform<List<String>, E>,
G_LamAlgTransform<List<String>, E> {default Function<List<String>, E> Var(String p0) {return xs ->expAlg().Var("" + (xs.indexOf(p0) + 1));}

default Function<C, Xi > f j (Function<C,X1p > p1 , ...,
Function<C,Xkp > pk ) {return (c) -> alg().f j (p1 .apply(c), ..., pk .apply(c));

default Function<List<String>, E> Lam(String x,
Function<List<String>, E> e) {return xs ->lamAlg().Lam("", e.apply(cons(x, xs)));
}

}

...
}

Figure 13. Generic template for generating boilerplate ofcontextual transformations.

}Figure 14. Converting variables to De Bruijn indices.
face AlgCT extends Alg and instantiates the type parameters
to Functions from the context argument C to the corresponding sort Xi . Each constructor method now creates an anonymous function which, when invoked, calls the functions received as parameters (p1 to pk ) and only then creates a structure over the alg() algebra.
7.1

DeBruijn<String> deBruijn = new DeBruijn<String>() {PrintExpLam alg = new PrintExpLam();public ExpAlg<String> expAlg() { return alg; }public LamAlg<String> lamAlg() { return alg; }};println(makeLamExp(deBruijn).apply(Collections.emptyList()));

Example: Conversion to De Bruijn Indices

The printed output is “\.\.(2 + 1)”, which corresponds tooriginal lambda term, but without variables.

An example of a contextual transformation is converting
variables to De Bruijn indices in the lambda calculus [6].
Using De Bruijn indices, a variable occurrence is identiﬁedby a natural number equal to the number of lambda terms between the variable occurrence and its binding lambda term.
Lambda terms expressed using De Bruijn indices are useful
because they are invariant with respect to alpha conversion.
The conversion to De Bruijn indices uses an object algebra interface LamAlg with constructors for lambda abstraction (Lam) and application (Apply). See below:

8.

Desugaring Transformations

In Section 6, we presented transformations, as well as thegeneric traversals generated by Shy. Although different
constructors can be used in transforming a data structure,
the generic transformations generated by Shy are typepreserving: they transform structures over one type (e.g.,
expressions) to different structures in the same type.
Desugaring transformations eliminate syntactic constructs
by transforming them to a combination of constructs in asmaller base language. In this section we describe how Shy
can be applied to implement compositional desugarings ina type-safe and extensible manner. In particular, the typesystem will enforce that the resulting language is indeed“smaller”, and that consequently the desugared construct isguaranteed to be fully eliminated.
As an example, consider extending ExpAlg with a doubling construct which multiplies its argument expression by
two. The Object Algebra interface that implements doublingis deﬁned as follows:@Algebrapublic interface LamAlg<Exp> {Exp Lam(String x, Exp e);
Exp Apply(Exp e1, Exp e2);}

Shy automatically generates traversal code for transformation for both LamAlg and ExpAlg: G_LamAlgTransform and
G_ExpAlgTransform, respectively. The generated transformation code can be found in Appendix A.1.6. Using these interfaces, the conversion to De Bruijn indices is realized asshown in Figure 14. Note again that only the relevant cases
are overridden: Var (from ExpAlg) and Lam (from LamAlg).
Client code A structure using the generic interfaces ExpAlg
and LamAlg is created as follows:@Algebrapublic interface DoubleAlg<E> {E Double(E e);}<E, A extends ExpAlg<E> & LamAlg<E>>
E makeLamExp(A alg) {return alg.Lam("x", alg.Lam("y",alg.Add(alg.Var("x"), alg.Var("y"))));}An expression Double(e) can be desugared to Add(e,e).
The following code realizes this transformation by extending
the ExpAlgTransform interface, generated by Shy:

It simply generates “λ x.λ y. x + y” as a generic lambda
expression. By instantiating the DeBruijn interface with a
PrintExpLam algebra (shown in Appendix A.1.8) passed inas the base algebra, we can write the client code as follows:interface Desugar<E> extends DoubleAlg<E>,
ExpAlgTransform<E> {default E Double(E e) {return expAlg().Add(e, e);136

query from scratch, it is possible to modularly extend theexisting FreeVars query:}}

The interface Desugar exports the language DoubleAlg
and ExpAlg, but expAlg() (which is used as a factory for
output expressions) has type ExpAlg. Since ExpAlg does notcontain Double, the Double constructor cannot be used toconstruct the output. As a result, the algebra Desugar transforms into is guaranteed to be without any occurrences ofDouble.
Expressions are created over the combined languages
DoubleAlg and ExpAlg:

interface FreeVarsWithLambda extends FreeVars,
LamAlgQuery<Set<String>> {default Set<String> Lam(String x,Set<String> f) {return f.stream().filter(y -> !y.equals(x)).collect(toSet());}}

The interface FreeVarsWithLambda extends both the original FreeVars query and the base query implementation thatwas generated for the LamAlg interface deﬁning the language
extension. Note again, that only the relevant method (Lam)needs to be overridden.
For transformations the pattern is similar. To illustrate extension of transformation, consider the simple transformation that makes all variable occurrences unique, to distinguish multiple occurrences of the same name:<E, Alg extends DoubleAlg<E> & ExpAlg<E>>
E makeExp(Alg a) {return a.Add(a.Lit(5), a.Double(a.Var("a")));}

To illustrate the use of the Desugar algebra, here is thecode to print an expression in desugared form:
ExpAlg<String> print = new PrintExp();
Desugar<String> desugar = new Desugar<String>() {@Override
public ExpAlg<String> expAlg() {return print;}};
System.out.println(makeExp(desugar));interface Unique<E> extends ExpAlgTransform<E> {int nextInt();
default E Var(String s) {return expAlg().Var(s + nextInt());}}

The Unique transformation uses a helper method nextInt
which returns consecutive integers on each call. The basic
transformation simply renames Var expressions. If, again,
the expression language is extended with lambda constructs,
the transformation needs to be updated as well to makethe variable in the binding position of lambda expression
unique. The following code shows how this can be done in amodular fashion:

The kind of desugarings presented in this section are limited to bottom-up, compositional desugaring, corresponding
to factory methods directly invoking methods in a different algebra. As a result, these desugarings are executed in abottom-up fashion: the arguments are always desugared before an expression itself is transformed. Because the transformations are generic with respect to the carrier object of
the argument (as indicated by the type parameter E) it is
impossible to look at the arguments. This prevents desugarings to perform complex, deep pattern matching on theargument structure. An added beneﬁt, however, is that thedesugaring is automatically deforested: intermediate expression trees are never created.

9.

interface UniqueWithLambda<E> extends Unique<E>,
LamAlgTransform<E> {default E Lam(String x, E e) {return lamAlg().Lam(x + nextInt(), e);}}Note that the transformation uses the lamAlg() algebra (from
LamAlgTransform), to create lambda expressions.
Figure 15 and 16 give a high level overview of query andtransformation extension using the examples for FreeVars
and Unique, respectively. In the case of queries, the abstract m() method will be shared by both the FreeVars and
FreeVarsWithLambda interfaces. On the other hand, transformations are based on multiple base algebras, for sets of data
type constructors (e.g., expAlg() and lamAlg()).
Note ﬁnally that, in the current implementation of Shy
transformations, it is assumed that the language signatures
ExpAlg and LamAlg are completely independent. This is however, not an essential requirement. An alternative design
could have LamAlg be a proper extension of ExpAlg (i.e.
LamAlg<E> extends ExpAlg<E>). In that case, the generated
LamAlgTransform would need to reﬁne the return type of the
expAlg() method.

Extensible Queries and Transformations

Shy queries and transformations inherit modular extensibility from the Object Algebra design pattern. New transformations or queries are simply added by extending the interfaces
generated by Shy. More interestingly, however, it is also possible to extend the data type with new constructors. Here webrieﬂy describe how queries and transformations can be extended in this case.
9.1

Linear Extensibility

Consider again the extension of the expression languagewith lambda and application constructs (cf. Section 7). Thisrequires changing the free variables query, since variables
bound by Lam expressions need to be subtracted from the setof free variables of the body. Instead of reimplementing the137mentations of the combined interface need to provide concrete implementations for nextInt(), expAlg() and lamAlg():
class Combine<E> implements Unique<E>,UniqueLam<E> {public int nextInt() { ... }public ExpAlg<E> expAlg() { ... }public LamAlg<E> lamAlg() { ... }}For queries the pattern is the same, except that only aconcrete implementation of m() has to be provided for the
combined interface.

10.

Shy is implemented using the standard Java annotations
framework (javax.annotation) packaged in the Java Development Kit. All of the generic traversals are automaticallygenerated by Shy for Object Algebra interfaces annotatedwith @Algebra. When an Object Algebra interface is annotated with @Algebra, Shy retrieves the required informationfrom the interface (such as the names and types of factory methods) using reﬂection. Shy then generates the code
based on the templates shown earlier. Furthermore, the Shyframework includes the Monoid interface as well as several
useful implementations of it.
A major advantage of using standard Java annotations isthat the code generation of the generic traversals can be donetransparently: users do not need to use or install a tool togenerate that code. As a result Shy is as simple to use as aconventional library. With little conﬁguration effort, the code
generation is automatically enabled in IDEs like Eclipse orIntelliJ. Finally, the framework is very small (around 885
source lines of code), so it can be easily be customized, if
needed.

Figure 15. Extension of the FreeVars query.

Figure 16. Extension of the Unique transformation.
9.2

Shy Implementation

Independent Extensibility

11.

Both Figure 15 and Figure 16 show extensions of queries andtransformations where the extensions directly inherit fromthe concrete implementation of the operations (i.e. FreeVars
and Unique, respectively). It is also possible to make theextensions more independent using multiple inheritance ofinterfaces with default methods.
For instance, the Unique transformation for the LamAlg
language could also have been implemented independentlyof Unique:

Case Study

To illustrate the utility of Shy we have implemented a number of queries and transformations in the context of QL, a
DSL for questionnaires which has been implemented using
Object Algebras before [9]. QL is similar to MiniQL, exceptthat it additionally features an if-then-else construct, computed questions (which will appear read only), and a richer
expression language. For more information on the features
of QL we refer to [7].

interface UniqueLam<E> extends LamAlgTransform<E> {int nextInt();
default E Lam(String x, E e) {return lamAlg().Lam(x + nextInt(), e);
}
}

11.1

QL Queries and Transformations

The queries extract derived information from a QL program,
such as the set of used variables, the data and control dependencies between questions, and the global type environment. The transformations include two transformations oflanguage extensions to the base language. The ﬁrst realizes
a simple desugaring of “unless(c)...” to “if(not(c))...”. The
second desugaring statically unfolds a constant bound loop
construct (“repeat (i)...”) and renames variables occurring
below it accordingly. Finally, we have implemented a sim-

Note that this interface declares the required dependency on nextInt(). Both transformations are combined independently through multiple inheritance of interfaces. Both
Unique and UniqueLam declare the method nextInt(), butsince the declarations are abstract, they are identiﬁed. Imple-

138

Exp (18)1

11

Stmt (5)Form (1)

3
4
2
2
4
1
3

1
1

%
4%
17%
21%
8%
13%
17%
4%
16%

Control dependencies
0.035

AST
Linear (AST)
Shy
Linear (Shy)

0.03
0.025
Running time (s)Operation
Collect variables
Data dependencies
Control dependencies
Type environment
Rename variable
Inline conditions
Desugar “unless”
Desugar “repeat”

Table 1. Number of overriden cases per query and transformation in the context of the QL implementation.

0.02
0.015
0.01
0.005

ple rename variable operation, and a ﬂattening normalizer
which inlines the conditions of nested if-then constructs.
Table 1 shows the number of cases that had to be overridden to implement each particular operation. The top row
shows the number of constructs for each syntactic category
in QL (Exp, Stmt, and Form). As can be seen, none of theoperations required implementing all cases. The last column
shows the number of overridden cases as a percentage. For
this set of queries and transformations, almost no expression cases needed to be overridden, except the “Var” casein collect variables, rename variable and desugar “repeat”4 .
The cases required for desugaring include the case of thelanguage extension (e.g. Unless and Repeat, respectively).
These cases are not counted in the total in the ﬁrst row but
are used to compute the percentage.
11.2

0

0

20000

40000

60000
80000
Input size (bytes)

100000120000140000Figure 17. Performance comparison of control dependencies query.
Since inlining is a contextual transformation, the resultof constructing this simple questionnaire is a function object
representing the “to be inlined” representation of the questionnaire after desugaring. The IFormatWithPrecedence andIFormat types are formatting operations, respectively representing expressions and statements; these types originate
from the Format algebra passed to Rename.
Calling the function with a boolean expression representing true will trigger inlining of conditions and renaming.
The result is then a formatting object (IFormat) which canbe used to print out the transformed questionnaire:

Chaining Transformations

A typical compiler consists of many transformations chained
together in a pipeline. Shy transformations support this pattern by passing transformation algebras as the base algebra to the implementation of another transformation. For instance, the desugar unless transformation desugars the “unless” statement to “if” statements in another algebra. The
latter can represent yet another transformation.
In the context of QL, “unless” desugaring, condition inlining and variable renaming can be chained together as follows:form myForm { if (true && !y) y "X?" boolean }As can be seen, the variable x has been renamed to y. The(renamed) condition y is now negated, because of the desugaring of “unless”. Finally, the result of inlining conditions
can be observed from the conjunction in the if statement.
11.3

Shy Performance vs Vanilla ASTs

We compared the performance characteristics of the operations implemented using Shy with respect to vanilla implementations based on ordinary AST classes with ordinary methods representing the transformations and queries.
In the vanilla implementation, the program was parsed into
an AST structure, and then the operation was invoked andmeasured. In the case of the Shy queries, constructing the“AST” corresponds to executing the query, so we measured
that. For context-dependent transformations, however, building the “AST” corresponds to constructing the function to
execute the transformation, hence we only measured invoking this function. The vanilla query implementations use thesame monoid structures as in Shy.
The operations were executed on progressively larger QL
programs (up to 140Kb). The QL programs represent questionnaires describing a binary search problem (a number

alg = new Desugar<>(new Inline<>(new Rename<>(Collections.singletonMap("x", "y"),new Format())));

The chained transformation alg ﬁrst desugars “unless”,
then inlines conditions, and ﬁnally renames xs to ys. The
Rename transformation gets as base algebra an instance ofFormat, a pretty printer for QL.
The algebra alg can now be used to create questionnaires:
Function<IFormatWithPrecedence, IFormat> pp= alg.form("myForm", Arrays.asList(
alg.unless(alg.var("x"),alg.question("x", "X?", new TBoolean()))));
4 Note, however, that the dependency extraction queries reuse the collectvariables query on expressions.

139

Component
Inline conditions
0.0012AST
Linear (AST)
Shy
Linear (Shy)

Running time (s)0.001

0.00080.00060.00040.0002

0

0

20000

40000

60000
80000
Input size (bytes)

100000120000Object Algebra interfaces
Collect variables
Data dependencies
Control dependencies
Type environment

71
10
30
58
15

Rename variable
Inline conditions
Desugar “unless”
Desugar “repeat”

27
48
10
35

Total Shy-based operations
AST based implementation

304
661

140000

Table 2. Source Lines of Code (SLOC) statistics: Shy implementation vs Vanilla AST implementation.

Figure 18. Performance comparison of inline conditionstransformation.

required in the vanilla implementation. Note also that Shy
supports a much more modular design, where both the AST
data type and the set of operations can be extended without
having to modify existing code.

guessing game) and are automatically generated, with increasing search spaces. The benchmarks were executed on
a 2.6GHz MacBook Pro Intel Core i5 with 8GB memory.
The JVM was run in 64bit server mode and was given 4Gbof heapspace to minimize the effect of garbage collection
pauses. Each benchmark was run without measuring ﬁrst, towarm-up the JVM. The measurements presented here do notinclude warm-up time.
The comparison of the control dependencies query is
shown in Figure 17. The plot shows that the performanceis quite comparable. On average, the Shy implementationof the query seems a little slower. This is probably causedby the extensive use of interfaces in the Shy framework,whereas the AST-based implementation only uses abstract
and concrete classes. For transformations the performancedifference is slightly more pronounced. Figure 18 shows theperformance comparison of the inline conditions transformation. The greater difference can be explained by the factthat creating a new structure in a Shy transformation involves dynamically dispatched method calls instead of statically bound constructor calls.
11.4

SLOC

12.

Related Work

Structure-shy traversals have been an active research topic.
Our approach to structure shy traversal is unique in that itsupports separate compilation, modular type checking anddata type extension. Furthermore, it can be applied in mainstream languages such as Java. While some approaches support some of these features, to the best of our knowledge, noapproach supports all of them.
Adaptive Object-Oriented Programming (AOOP) AOOP
is an extension of object-oriented programming aimed at increasing the ﬂexibility and maintainability of programs [17].
AOOP promotes the idea of structure-shyness to achieve
those goals. In AOOP it is possible to select parts of a structure that should be visited. This is useful to do traversals oncomplex structures and focus only on the interesting partsof the structure relevant for computing the ﬁnal output. The
original approach to AOOP was based on a domain-speciﬁclanguage [17]. DJ is an implementation of AOOP in Java
using reﬂection [22]. More recently DemeterF [5] improved
previous approaches to AOOP by providing support for typesafe traversals, generics and data-generic function generation. Shy shares with AOOP the use of structure-shyness
as a means to increase ﬂexibility and adaptability of programs. Most AOOP approaches, however, are not type-safe.
The exception is DemeterF where a custom type system wasdesigned to ensure type-safety of generic functions. Unlike
DemeterF, which is a separate language, Shy is a Java library. Moreover, compilation of DemeterF programs is implemented through static weaving, and thus appears to preclude separate compilation.

Shy vs Vanilla Regarding Code Size

The percentages shown in Table 1 illustrate the structureshyness of queries and transformations implemented using
Shy. Table 2 shows the absolute number of source lines ofcode (SLOC, lines of code without counting empty lines andcomments). For the vanilla AST-based implementation we
only show the total SLOC count, since all operations arescattered over the respective AST classes. For the Shy implementation, each query and operation is realized a separate class or interface, extending the interfaces generated by
Shy. In total, one can observe that the Shy-based implementation requires less than half of the number of lines of code140Strategic Programming Strategic programming is an approach to data structure traversal, which originated in term
rewriting. Visser et al. extended the rewriting strategiesof [3] with generic one-level traversal operators [27] enabling a style of term rewriting where computations are represented by simple, conditional rewrite rules, but the application of such rules is controlled separately using the concept of a strategy. Strategies can be primitive (e.g., “fail”)
or composed using combinators (e.g., “try s else s ”). Theseand other combinators were formalized in a core language
for strategic rewriting in [26].
The strategy concept has since then been ported to otherparadigms. JJT RAVELER is an OO framework for strategic
programming [28]. Lämmel et al. introduced typed strategy
combinators in Haskell [14]. The relation between strategic
programming and AOOP has been explored in [16].
The key tenet of strategic programming is separation ofconcerns: actual computation and traversal are speciﬁed separately. In Shy, the traversal of a data structure is also speciﬁed separately (in a super-interface), however, it is ﬁxed
for speciﬁc styles of queries and transformations. For instance, both queries and transformations employ an innermost, bottom-up strategy.
The distinction between queries and transformations also originates from existing work in strategic programming.
Lämmel et al. [14] discuss type unifying and type preserving
traversals. Type unifying traversals correspond to queries,
where all data type constructors are uniﬁed into a single
monoid. Analogously, Shy transformations are type preserving in the sense that a transformation is an algebra whichmaps constructor calls to another algebra of the same type.
The A SF +S DF program transformation system distinguishes transforming and accumulating traversals, whichcorrespond to our transformations and queries, respectively [25]. Furthermore, an accumulating transforming traversal combines both styles, by tupling the accumulated result and the transformed tree. This combination could easily
be generated by Shy by having the boilerplate code construct the monoid and the transformed term in parallel (seeFig. 19).

interface AccuTrafoExp<M,E> extends
ExpAlg<Pair<M,E>> {Monoid<M> m(); ExpAlg<E> expAlg();
default Pair<M,E> Var(String s) {return new Pair<>(m().empty(),
expAlg().Var(s));}
default Pair<M,E> Lit(int i) {return new Pair<>(m().empty(),
expAlg().Lit(i));}
default Pair<M,E> Add(Pair<M,E> e1, Pair<M,E> e2){
return new Pair<>(m().join(e1.fst(), e2.fst()),
expAlg().Add(e1.snd(), e2.snd()));}}

Figure 19. Combining query and transformation.
methods, or in the Visitors themselves (which only allow
static specialization). A challenge not addressed by JJT RAVELER is type safety of traversal code: either the combinators
needs to be redeﬁned for each data type, or client code needs
to cast the generic objects of type AnyVisitable to the speciﬁc type. Even if speciﬁc combinators would be generated,
however, the traversed data types would not be extensible.
Another approach to improve upon the standard Visitor pattern is presented in Palsberg et al. [23]. This work
particularly addressed the fact that traditional Visitors operate on a ﬁxed set of classes. As a result, the data type
can not be extended without changing all existing Visitors
as well. The proposed solution is a generic Walkabout classwhich accesses sub-components of arbitrary data structuresusing reﬂection. Unfortunately, the heavy use of reﬂection
make Walkabouts signiﬁcantly slower than traditional Visitors. The authors state that the Walkabout class could be generated to improve performance, but note that the addition of aclass could trigger regeneration. As a result the pattern does
not support separate compilation. Our solution obtains thesame kind of default behavior for traversal, without losing
extensibility, type safety, or separate compilation.
Whereas the Walkabout provides generic navigation overan object structure, this navigation can be programmed explicitly using guides [4]. Guides insert one level of indirection between recursing on the children of a node in visit
methods: the guide decides how to proceed the traversal.
Since guides needs to deﬁne how to proceed for each typethat will be visited, they suffer from the same extensibility
problem as ordinary Visitors. Generic guides, on the other
hand, are dynamically typed and use reﬂection to call appropriate visit methods. The Walkabout can be formulated assuch a generic guide.

Structure-Shy Traversals with Visitors A standard way toremove boilerplate in OOP is to use default visitors [18].
Default visitors can be used in similar ways to our generictraversals. Many programmers using the visitor pattern create such default visitor implementations to avoid boilerplatecode. There are two important differences to our work. Firstly conventional visitors are not extensible in a type-safe way.
Secondly, with Shy the code for generic traversals is automatically generated, whereas with default visitors such code
usually has to be implemented by hand.
Visser [28] adapted the strategy combinators of Stratego [26, 27] to combinators that operate on object-oriented
Visitors [8]. The resulting framework JJT RAVELER solves
the problem of entangling traversal control within the accept

Structure-Shy Traversals in Functional Programming In
functional programming there has been a lot of researchon type-safe structure-shy traversals. Lämmel and Peyton

141

Object Algebras Shy traversals are based on Object Algebras [19]. The original motivation for object algebras was asa design pattern for OO programming that allowed improved
extensibility and modularity of programs. Using object algebras it is possible to solve the well-known “Expression
Problem” [29]. Later work [21, 24] has explored the use of
Object Algebra combinators, and generalizations of object
algebras to improve expressiveness and modularity. In particular it has been claimed that Object Algebras can be used
to do feature-oriented programming [21], and to encode attribute grammars [24]. One domain where Object Algebras
are especially useful is in the implementation of (extensible)
languages. The QL language used in our case study is basedon Gouseti et al. [9]. That work provides a realistic implementation of an extensible domain-speciﬁc language using
Object Algebras. In contrast to our work, which focus on removing boilerplate code, previous work on Object Algebras
was mostly motivated by improved programming support forextensibility and modularity. The combination of extensibility (inherited for free from Object Algebras) and structureshy type-safe traversals adds a new dimension to our work
that, as far as we know, has not been explored previously.

Jones’ “Scrap your Boilerplate” (SyB) [11–13] series introduced a practical design pattern for doing generic traversals in Haskell. The simple queries and transformations in
Shy were partly inspired by SyB. However SyB and Shy
use very different implementation techniques. SyB is implemented in Haskell and relies on a run-time type-safe castmechanism. This approach allows SyB traversals to be encoded once-and-forall using a single higher-order function
called gfoldl. In contrast, in Shy Java annotations are used
to generate generic traversals for each structure.
A drawback of SyB traversals is that they are notoriously
slow, partly due to the use of the run-time cast [1]. Anothernotable difference between SyB and Shy is with respect
to extensibility. While Shy supports extensibility of bothtraversals and structures, the original SyB approach did notsupport any extensibility. Only in later work, Lämmel and
Peyton Jones proposed an alternative design for SyB, basedon type classes [30]. This design supports extensibility oftraversals, but not of the traversed structures.
Closest to Shy is an approach proposed by Lämmel etal. [15] for dealing with the so-called “large bananas”. A
large banana corresponds to the fold algebra of a complex
structure. Object Algebras, which we use in our work, are an
OO encoding of fold algebras [19, 20]. However Lämmel
et al. work has not dealt with extensibility. Interestingly
in their future work Lämmel et al. did mention that theywould like “to cope with incomplete or extensible systemsof datatypes”.

13.

Conclusion

This paper showed how various types of default traversals
for complex structures can be automatically provided by
Shy. Shy traversals are written directly in Java and are typesafe, extensible and separately compilable. There has always
been a tension between the correctness guarantees of static
typing, and the ﬂexibility of untyped/dynamically-typed approaches. Shy shows that even in type systems like Java’s,
it is possible to get considerable ﬂexibility and adaptability
for the problem of boilerplate code in traversals of complex
structures, without giving up modular static typing.
There are many avenues for future work. One area of research is to extend Shy traversals to support ﬂexible traversal strategies, similarly to strategic programming [3, 25, 26].
Another line of work worth exploring is to adopt generalizations of object algebras [21] for added expressiveness of
Shy traversals.

Language Extensions for Queries Inspired by XPath/XQuery there has been some work on adding support for similar types of queries on object-oriented structures. For example the work on Cω [2] extends C# with generalized member
access, which allows simple XPath-like path expressions.
Thus in Cω it is possible to express queries quite concisely. However, in contrast to Shy Cω is a language extension
and it does not deal with transformations.
Eliminating Boilerplate in Design Patterns Design patterns [8] improve the design and modularity of objectoriented programs. However, the implementation of design
patterns sometimes requires signiﬁcant amounts of boilerplate code. There has been some work on implementing
design patterns in AspectJ to achieve reusability and modularity [10], and thus eliminate some of the boilerplate code.
A challenge with traditional design patterns, however, is thatthe boilerplate code is not always mechanical, due to many
possible implentation choices. Our work proposes a number of design patterns for traversals. Because implementing
these design patterns by hand would be quite tedious, we automatically generate the code for such design patterns using
Shy. Fortunatelly, in contrast to many of the traditional design patterns, the code for generic traversals is highly regularand easy to generate, and can be completely eliminated.

Acknowledgments
We would like to thank T. H. Tse for valuable feedback on
previous drafts of this work. This work has been sponsoredby the Hong Kong Research Grant Council Early Career
Scheme project number 27200514 (“ALGEBRA: A Programming Language for Developing Software Product Lines
based on Object Algebras”).

References[1] M. D. Adams and T. M. DuBuisson. Template your boilerplate: Using Template Haskell for efﬁcient generic programming. In Proceedings of the 2012 ACM SIGPLAN Haskell
symposium, Haskell ’12, pages 13–24, 2012.

142

[21] B. C. d. S. Oliveira, T. van der Storm, A. Loh, and W. R.
Cook. Feature-oriented programming with object algebras.
In ECOOP ’13, 2013.

[2] G. M. Bierman, E. Meijer, and W. Schulte. The essence ofdata access in comega. In ECOOP, 2005.
[3] P. Borovanskỳ, C. Kirchner, H. Kirchner, P.-E. Moreau, and
M. Vittek. ELAN: A logical framework based on computational systems. Electronic Notes in Theoretical Computer
Science, 4:35–50, 1996.

[22] D. Orleans and K. J. Lieberherr. DJ: Dynamic adaptive programming in Java. In Reﬂection 2001. Springer-Verlag, 2001.
[23] J. Palsberg and C. B. Jay. The essence of the visitor pattern.
In COMPSAC’98, 1998.

[4] M. Bravenboer and E. Visser. Guiding visitors: Separating navigation from computation. Technical Report UU-CS2001-42, Institute of Information and Computing Sciences,
Utrecht University, 2001.

[24] T. Rendel, J. I. Brachthäuser, and K. Ostermann. From object
algebras to attribute grammars. In OOPSLA ’14, 2014.

[5] B. Chadwick and K. Lieberherr. Weaving generic programming and traversal performance. In AOSD’10, 2010.

[25] M. G. J. van den Brand, P. Klint, and J. J. Vinju. Term
rewriting with traversal functions. ACM Trans. Softw. Eng.
Methodol., 12(2):152–190, Apr. 2003.

[6] N. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae (Proceedings), 75(5):381–392, 1972.

[26] E. Visser and Z.-e.-A. Benaissa. A core language for rewriting. Electronic Notes in Theoretical Computer Science, 15:422–441, 1998.

[7] S. Erdweg, T. van der Storm, M. Völter, M. Boersma,
R. Bosman, W. R. Cook, A. Gerritsen, A. Hulshout, S. Kelly, A. Loh, et al. The state of the art in language workbenches.
In Software Language Engineering. Springer, 2013.

[28] J. Visser. Visitor combination and traversal control. In OOPSLA ’01, 2001.

[27] E. Visser, Z.-e.-A. Benaissa, and A. Tolmach. Building program optimizers with rewriting strategies. In ICFP’98, 1998.

[29] P. Wadler. The Expression Problem. Email, Nov. 1998.
Discussion on the Java Genericity mailing list.

[8] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design
Patterns: Elements of Reusable Object-oriented Software.
Addison-Wesley Longman Publishing Co., Inc., Boston, MA,
USA, 1995. ISBN 0-201-63361-2.

[30] P. Wadler and S. Blott. How to make ad-hoc polymorphism
less ad hoc. In POPL ’89, 1989.

[9] M. Gouseti, C. Peters, and T. v. d. Storm. Extensible language implementation with Object Algebras (short paper). In
GPCE’14, 2014.

A.

Appendix[10] J. Hannemann and G. Kiczales. Design pattern implementation in Java and aspectJ. In OOPSLA ’02, 2002.

A.1

Complete Code

A.1.1 OO Approach for usedVars and rename[11] R. Lammel and S. P. Jones. Scrap your boilerplate: A practicaldesign pattern for generic programming. In TLDI’03, 2003.

Below is the complete code for Fig. 2 (left). It implements
usedVars and rename in the QL example, as an OO approach.

[12] R. Lämmel and S. P. Jones. Scrap more boilerplate: Reﬂection, zips, and generalised casts. In ICFP ’04, 2004.

class Form {String name;
List<Stmt> body;Form(String id, List<Stmt> body) {this.name = id;this.body = new ArrayList<Stmt>(body);}
Set<String> usedVars() {Set<String> vars = new HashSet<>();
body.forEach(s -> vars.addAll(s.usedVars()));
return vars;}
Form rename(String n1, String n2) {List<Stmt> ss = new ArrayList<>();for (Stmt s: body) ss.add(s.rename(n1, n2));
return new Form(name, ss);}}

[13] R. Lämmel and S. P. Jones. Scrap your boilerplate with class:
Extensible generic functions. In ICFP ’05, 2005.
[14] R. Lämmel and J. Visser. Typed combinators for generictraversal. In Practical Aspects of Declarative Languages,
pages 137–154. Springer, 2002.
[15] R. Lämmel, J. Visser, and J. Kort. Dealing with large bananas. In J. Jeuring, editor, Workshop on Generic Programming, Ponte de Lima, July 2000. Technical Report UU-CS2000-19, Universiteit Utrecht.
[16] R. Lämmel, E. Visser, and J. Visser. Strategic programmingmeets adaptive programming. In AOSD ’03, 2003.
[17] K. J. Lieberherr. Adaptive Object Oriented Software: The
Demeter Method with Propagation Patterns. PWS Publishing,
1996.

abstract class Stmt {abstract Set<String> usedVars();
abstract Stmt rename(String n1, String n2);}[18] M. E. Nordberg. Variations on the visitor pattern, 1996.
[19] B. C. d. S. Oliveira and W. R. Cook. Extensibility forthe masses, practical extensibility with object algebras. In
ECOOP ’12, 2012.

class If extends Stmt {Exp cond;
Stmt then;If(Exp cond, Stmt then) {[20] B. C. d. S. Oliveira, M. Wang, and J. Gibbons. The visitor
pattern as a reusable, generic, type-safe component. In OOPSLA’08, 2008.

143

this.cond = cond;
this.then = then;

GEq(Exp lhs, Exp rhs) {this.lhs = lhs;
this.rhs = rhs;}
Set<String> usedVars() {Set<String> vars = new HashSet<>(lhs.usedVars());
vars.addAll(rhs.usedVars());
return vars;}
GEq rename(String n1, String n2) {return new GEq(lhs.rename(n1, n2),
rhs.rename(n1, n2));}}
Set<String> usedVars() {Set<String> vars =new HashSet<>(cond.usedVars());
vars.addAll(then.usedVars());
return vars;}
If rename(String n1, String n2) {return new If(cond.rename(n1, n2),then.rename(n1, n2));}}}class Question extends Stmt {String name, label, type;
Question(String n, String l, String t) {this.name = n;this.label = l;this.type = t;}
Set<String> usedVars() {return emptySet();}Question rename(String n1, String n2) {String newN = name.equals(n1) ? n2 : name;return new Question(newN, label, type);
}
}

A.1.2

Rename implementing the QLAlg interface

The following code gives the implementation of Rename that
implements QLAlg in Section 3.2.
class Rename<E, S, F> implements QLAlg<E, S, F> {private QLAlg<E, S, F> alg;private String from, to;public Rename(QLAlg<E, S, F> alg, String from,
String to) {this.alg = alg;this.from = from;this.to = to;}public F Form(String id, List<S> stmts) {return alg.Form(id, stmts);}
public S If(E c, S t) {return alg.If(c, t);}public S Question(String n, String l, String t) {n = n.equals(from) ? to : n;return alg.Question(n, l, t);}public E Lit(int n) {return alg.Lit(n);}public E Var(String x) {x = x.equals(from) ? to : x;
return alg.Var(x);}public E GEq(E l, E r) {return alg.GEq(l, r);}}abstract class Exp {abstract Set<String> usedVars();
abstract Exp rename(String n1, String n2);}class Lit extends Exp {int n;
Lit(int n) {this.n = n;}
Set<String> usedVars() {return emptySet();}Lit rename(String n1, String n2) {return new Lit(n);}}class Var extends Exp {String x;
Var(String name) {this.x = name;}Set<String> usedVars() {return Collections.singleton(x);}Var rename(String n1, String n2) {String newN = x.equals(n1) ? n2 : x;
return new Var(newN);
}
}

A.1.3

QLAlgQuery: generated code

The generated code for QLAlgQuery by Shy in Fig. 4.
public interface QLAlgQuery<R>
extends QLAlg<R, R, R> {Monoid<R> m();default R Form(java.lang.String p0,
java.util.List<R> p1) {R res = m().empty();res = m().join(res, m().fold(p1));
return res;}class GEq extends Exp {Exp lhs, rhs;

144

return qLAlg().Var(p0);default R Geq(R p0, R p1) {R res = m().empty();res = m().join(res, p0);
res = m().join(res, p1);
return res;}}}public class QLAlgTrans<A0, A1, A2>
implements QLAlgTransform<A0, A1, A2> {default R If(R p0, R p1) {R res = m().empty();res = m().join(res, p0);
res = m().join(res, p1);
return res;}private QLAlg<A0, A1, A2> alg;
public QLAlgTrans(QLAlg<A0, A1, A2> alg) {this.alg = alg;}
public QLAlg<A0, A1, A2> qLAlg() {return alg;}

default R Lit(int p0) {R res = m().empty();return res;
}

}

A.1.5

default R Question(java.lang.String p0,
java.lang.String p1, java.lang.String p2) {R res = m().empty();return res;}

G_ExpAlgQuery: generated code

The generated code for G_ExpAlgQuery by Shy in Fig. 9.
public interface G_ExpAlgQuery<A0>
extends ExpAlg<A0> {Monoid<A0> mExp();

default R Var(java.lang.String p0) {R res = m().empty();return res;}default A0 Add(A0 p0, A0 p1) {A0 res = mExp().empty();res = mExp().join(res, p0);
res = mExp().join(res, p1);
return res;
}

}

A.1.4

QLAlgTransform and QLAlgTrans: generated code

default A0 Lit(int p0) {A0 res = mExp().empty();return res;}

The code for QLAlgTransform and its class representation
QLAlgTrans for use, generated by Shy. See Fig. 5.
public interface QLAlgTransform<A0, A1, A2>
extends QLAlg<A0, A1, A2> {default A0 Var(java.lang.String p0) {A0 res = mExp().empty();return res;}

QLAlg<A0, A1, A2> qLAlg();
default A2 Form(java.lang.String p0,
java.util.List<A1> p1) {return qLAlg().Form(p0, p1);
}

}

A.1.6
default A0 Geq(A0 p0, A0 p1) {return qLAlg().Geq(p0, p1);}

G_ExpAlgTransform and G_LamAlgTransform:

generated code
Below is the generated code for G_ExpAlgTransform and
G_LamAlgTransform by Shy in Fig. 14.

default A1 If(A0 p0, A1 p1) {return qLAlg().If(p0, p1);}

public interface G_ExpAlgTransform<A, B0>
extends ExpAlg<Function<A, B0>> {ExpAlg<B0> expAlg();

default A0 Lit(int p0) {return qLAlg().Lit(p0);}default <B> List<B> substListExpAlg(List<Function<
A, B>> list, A acc) {List<B> res = new ArrayList<B>();for (Function<A, B> i : list)
res.add(i.apply(acc));return res;}default A1 Question(java.lang.String p0,
java.lang.String p1, java.lang.String p2) {return qLAlg().Question(p0, p1, p2);}
default A0 Var(java.lang.String p0) {145

default Function<A, B0> Add(Function<A, B0> p0,
Function<A, B0> p1) {return acc -> expAlg().Add(p0.apply(acc),
p1.apply(acc));}return acc -> lamAlg().Lam(p0, p1.apply(acc));
}
}

A.1.7

default Function<A, B0> Lit(int p0) {return acc -> expAlg().Lit(p0);}Util.cons: an auxiliary method

The auxiliary method Util.cons is implemented as follows,
for the De Bruijn example in Fig. 14.

default Function<A, B0> Var(java.lang.String p0) {return acc -> expAlg().Var(p0);}public class Util {public static <X> List<X> cons(X x, List<X> l) {l = new ArrayList<>(l);l.add(0, x);
return l;}}}public interface G_LamAlgTransform<A, B0>
extends LamAlg<Function<A, B0>> {A.1.8

LamAlg<B0> lamAlg();

PrintExpLam: a pretty printer for ExpAlg and
LamAlgdefault <B> List<B> substListLamAlg(List<Function<
A, B>> list, A acc) {List<B> res = new ArrayList<B>();for (Function<A, B> i : list)
res.add(i.apply(acc));return res;}

The class PrintExpLam used in Section 7.1.
class PrintExpLam implements ExpAlg<String>,
LamAlg<String> {public String Lam(String x, String e) {return "\\" + x + "." + e;}
public String Apply(String e1, String e2) {return "(" + e1 + " " + e2 + ")";}
public String Var(String s) { return s; }public String Lit(int i) { return i + ""; }public String Add(String e1, String e2) {return "(" + e1 + " + " + e2 + ")";}}

default Function<A, B0> Apply(Function<A, B0> p0,
Function<A, B0> p1) {return acc -> lamAlg().Apply(p0.apply(acc),
p1.apply(acc));}
default Function<A, B0> Lam(java.lang.String p0,
Function<A, B0> p1) {146