The University of Tokyo
Graduate School of Information Science and Technology
Department of Creative Informatics

博士論文

An Empirical Study and Code-Generation Techniques
for Fluent Interfaces(Fluent Interface のための実証研究とコード生成技術)

Doctoral Dissertation of:
Tomoki Nakamaru(中丸 智貴)Academic Advisor:
Shigeru Chiba(千葉 滋)

Abstract
This dissertation presents our research to improve the user experiences ofsoftware libraries with fluent interfaces, interfaces designed to be used bychaining method invocations. The dissertation includes three studies: (1)An empirical study of the use of fluent interfaces in the real world, (2) anempirical study to discover desirable language designs for the use of fluent
interfaces, and (3) the development of code-generation techniques to enable
quick construction of safe fluent interfaces.
Study (1) is a background study to quantitatively reveal the significanceof studying fluent interfaces. In previous studies on fluent interfaces, thesignificance has been claimed only qualitatively based on the abundance ofexisting fluent interfaces. To the best of our knowledge, no quantitative evidence has been provided to support the widespread use of fluent interfaces.
For our goal, we conducted repository mining of numerous git repositories.
Specifically, we collected 2,814 Java repositories on GitHub and analyzed
historical trends in the use of fluent interfaces in those repositories.
Study (2) aims to help language developers to design their language
appropriately for using fluent interfaces. To find such language designs,
we analyzed Java code snippets in the real world and mined problematic
code patterns for fluent interfaces. Our results are summarized as a listof desirable language designs and the statistically-estimated values of how
effective it would be to introduce each language design into Java. The
information we made is beneficial for language developers who attempt toimprove the user experiences of fluent interfaces in their language because
they can use the list and estimated impact values to smoothly discuss what
language design to be adopted.
Study (3) aims to enable library developers to quickly give misusedetection capabilities to their fluent interfaces, i.e., to quickly create safe
fluent interfaces. Although safe fluent interfaces have been known to benefit
their users, they are not widely developed in the real world due to their highdevelopment cost. While several code-generation techniques have been proi

ii
posed to reduce the cost, those existing techniques lack two essential features
for practical use: generics support and sub-chaining support. In Study (3),
we propose two novel code-generation techniques to address those problems.
All the studies presented in the dissertation include artifacts that offer
values to society, not only to academia. In Study (1) and Study (2), we analyzed real-world Java source code to benefit real-world programmers andbuilt a publicly available dataset to further investigate the real-world use offluent interfaces. The code-generation techniques in Study (3) are demonstrated in tools named Protocool and Silverchain, which allow real-world
library developers to test our techniques in real-world settings. Those tools
are openly available at GitHub.

Acknowledgements
I would first like to express my sincere gratitude to my supervisor, Prof.
Shigeru Chiba, for the continuous support throughout my Ph.D. program.
What leads me to this point is his kind, encouraging, and insightful advice.
Things I learned from him will be a compass for life as a researcher.
I would also like to thank the members of my thesis committee: Prof.
Takeo Igarashi, Prof. Masayuki Inaba, Prof. Mary Inaba, Prof. Ryota
Shioya, and Prof. Manabu Tsukada, for all the guidance and feedbacks thatthey gave me from the viewpoint of their specialties.
My gratitude extends to all the lab members I shared time with, notably Soramichi Akiyama, Kazuhiro Ichikawa, Tomomasa Matsunaga, Yutaro Orikasa, Daniel Perez, Antoine Tu, and Tetsuro Yamazaki. The conversations we had during coffee breaks were not only a precious memory but
also a driving force of my research.
Last but not least, I want to thank my parents and girlfriend for theirunlimited help and support outside of the lab. I would not have completed
this dissertation without them.

iii

iv

Contents
1 Introduction
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Importance of Libraries . . . . . . . . . . . . . . . . .
1.1.2 User Experiences of Libraries . . . . . . . . . . . . . .
1.1.3 Our Scope . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Acceptance of Fluent Interfaces . . . . . . . . . . . . . . . . .
1.3 Empirical Study of Language Desings . . . . . . . . . . . . .
1.4 Code generation for Safe Fluent Interfaces . . . . . . . . . . .
1.4.1 Lack of Generics Support . . . . . . . . . . . . . . . .
1.4.2 Lack of Sub-chaining Support . . . . . . . . . . . . . .
1.5 Organization and Contributions . . . . . . . . . . . . . . . . .

1
3
3
3
4
4
6
7
10
10
11

2 Fluent Interface
15
2.1 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Method Chaining . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Fluent Interface . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Safe Fluent Interface . . . . . . . . . . . . . . . . . . . 17
2.2 Existing Discussions on Fluent Interfaces . . . . . . . . . . . 17
2.2.1 Positive Opinions . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Negative Opinions . . . . . . . . . . . . . . . . . . . . 19
2.3 Existing Code-generation Algorithms . . . . . . . . . . . . . . 21
2.4 Misuse Detection Techniques . . . . . . . . . . . . . . . . . . 25
3 Method Chaining in the Real World27
3.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Definition of Chain Length . . . . . . . . . . . . . . . . . . . 29
3.3 Overall Trend . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 Power-law Distribution . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Bias in Frequency . . . . . . . . . . . . . . . . . . . . . . . . . 32v

vi

CONTENTS
3.6 Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Extremely Long Chains . . . . . . . . . . . . . . . . . . . . .
3.8 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34
38
40
40
42

4 Desirable Language Designs for Fluent Interfaces
45
4.1 NullExceptionAvoidance . . . . . . . . . . . . . . . . . . 46
4.2 RepeatedReceiver . . . . . . . . . . . . . . . . . . . . . . . 47
4.3 DownCast . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4 ConditionalExecution . . . . . . . . . . . . . . . . . . . . 49
4.5 Estimated Ratios . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . . 50
4.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 Generating Generic Fluent Interfaces
55
5.1 Problem of Existing Algorithms . . . . . . . . . . . . . . . . . 55
5.2 Our Code-generation Technique . . . . . . . . . . . . . . . . . 58
5.2.1 DFA Construction . . . . . . . . . . . . . . . . . . . . 61
5.2.2 Binding-time Analysis . . . . . . . . . . . . . . . . . . 62
5.2.3 Bodies of Generated Methods . . . . . . . . . . . . . . 65
5.2.4 Specification Validation . . . . . . . . . . . . . . . . . 67
5.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.1 Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.2 Reduction of Development Cost . . . . . . . . . . . . . 77
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6 Generating Fluent Interfaces with Sub-chaining81
6.1 Key Idea for Sub-chaining Support . . . . . . . . . . . . . . . 82
6.2 Our Code-generation Technique . . . . . . . . . . . . . . . . . 83
6.2.1 RPA and Its Table Representation . . . . . . . . . . . 85
6.2.2 Construction of RPAs . . . . . . . . . . . . . . . . . . 86
6.2.3 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . 90
6.2.4 Encoding into Class Definitions . . . . . . . . . . . . . 93
6.2.5 Limitation . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3 Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7 Conclusions

109

List of Figures
1.1
1.2
1.3
1.4
1.5
1.6

Connection between our studies and application development
Position of our research . . . . . . . . . . . . . . . . . . . . .
Architecture and examples of safe fluent query builder . . . .
Method completion . . . . . . . . . . . . . . . . . . . . . . . .
Architecture of naively-designed fluent query builder . . . . .
Positon of each chapter in PL and SE research . . . . . . . .

2
4
8
8
9
12

3.1 Number of repositories, files, and lines . . . . . . . . . . . . .
3.2 Method chains and their lengths . . . . . . . . . . . . . . . .
3.3 Frequency of method chaining . . . . . . . . . . . . . . . . . .
3.4 Distribution and trend of per-repository r . . . . . . . . . . .
3.5 Ratio containing chains longer than or equal to n . . . . . . .
3.6 Non-testing code vs. Testing code . . . . . . . . . . . . . . .
3.7 Accessor chains . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Builder chains . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Assertion chains . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Constitution ratio of each category . . . . . . . . . . . . . . .

29
30
31
32
33
34
35
36
36
37

5.1 DFA that accepts correct method sequences of OurAPI . . . .
5.2 Specification of OurAPI . . . . . . . . . . . . . . . . . . . . .
5.3 DFA constructed from class declaration in fig. 5.2 . . . . . . .
5.4 Class definitions generated from DFA in fig. 5.3 . . . . . . . .
5.5 NFA construction . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Incremental assignment of type parameters . . . . . . . . . .
5.7 Tree construction in generated library . . . . . . . . . . . . .
5.8 Handwritten evaluator implementation . . . . . . . . . . . . .
5.9 Handwritten visitor implementation . . . . . . . . . . . . . .
5.10 Invalid spec. with multiple type-consuming transitions . . . .
5.11 Invalid spec. with type- and method-consuming transitions .

57
59
59
60
61
63
65
66
66
68
69

vii

viii

LIST OF FIGURES
5.12 Syntax of our API specification language . . . . . . . . . . . .
5.13 Specification of our matrix library . . . . . . . . . . . . . . .
5.14 Specification for itemized document API . . . . . . . . . . . .
5.15 Specification of subset of AssertJ . . . . . . . . . . . . . . . .
5.16 Specification for EBNF emulation . . . . . . . . . . . . . . . .
5.17 Specification for DOT emulation . . . . . . . . . . . . . . . .

70
72
75
76
78
79

6.1 Grammar and example sentence of our DSL . . . . . . . . . . 84
6.2 Overview of our translation method (ni is a non-terminal). . 84
6.3 Example stack transition . . . . . . . . . . . . . . . . . . . . . 86
6.4 State diagram of Dlist . . . . . . . . . . . . . . . . . . . . . . 87
6.5 Selecting an edge for inline expansion . . . . . . . . . . . . . 92
6.6 Without decomposition into SCCs . . . . . . . . . . . . . . . 93
6.7 Class definitions generated from table 6.1 . . . . . . . . . . . 94
6.8 Definition of Q2 including method bodies . . . . . . . . . . . 97
6.9 Example implementation of library semantics . . . . . . . . . 98
6.10 Class definitions generated from table 6.5b . . . . . . . . . . . 102
6.11 Comparison in LINQ . . . . . . . . . . . . . . . . . . . . . . . 104
6.12 Comparison in DOT . . . . . . . . . . . . . . . . . . . . . . . 105
6.13 Result of experiments . . . . . . . . . . . . . . . . . . . . . . 106

List of Tables
1.1

Organization and correspondence . . . . . . . . . . . . . . . .

11

2.1

List of existing algorithms and tools . . . . . . . . . . . . . .

22

3.1
3.2

Groups of Method Chains . . . . . . . . . . . . . . . . . . . .
Materials published at Zenodo . . . . . . . . . . . . . . . . .

34
42

4.1
4.2

Estimated Ratio of Pattern . . . . . . . . . . . . . . . . . . .
Materials published at Zenodo . . . . . . . . . . . . . . . . .

50
52

5.1

Quantitative information of generated code . . . . . . . . . .

77

6.1
6.2
6.3
6.4
6.5
6.6
6.7

Table representation of Rlist . . . . . . . . . . . . . . . . . . . 85
Table representation of our RPA construction . . . . . . . . . 87
Tables appearing in RPAs construction . . . . . . . . . . . . . 90
Table violating Condition (a) and its modification . . . . . . 100
Table violating Condition (b) and its modification . . . . . . 101
Number of classes and methods . . . . . . . . . . . . . . . . . 102
Fitted parameters in y = ax + b . . . . . . . . . . . . . . . . . 106ix

x

LIST OF TABLES

Chapter 1

Introduction
Enabling computer programmers to create high-quality application software
in a shorter period of time, i.e., improving the productivity of application
programmers, is a mission given to researchers of programming languages
and software engineering. While approaches vary from study to study (e.g.,
exploration of theoretical properties, development of novel implementation
techniques, and statistical analysis of real-world source code), every study
in those fields aims to contribute to the mission in some way. The endeavor
towards the mission is beneficial for the entire society, not only for programmers, since higher productivity enables programmers to create or update
applications more quickly as requested by society.
Our research aims to contribute to the mission through improving theuser experiences of software libraries whose interfaces are designed in a stylecalled fluent interfaces. Fluent interfaces are library interfaces that are designed to be used by chaining method invocations [20, 32] as follows:
new Dialog().title("Warning").message("Are you sure?").show();
Methodinvocation

Methodinvocation

Methodinvocation

Chain of method invocations

Fluent interfaces are a common design. There are a number of libraries withfluent interfaces in various object-oriented languages such as Polly1 in C#,
the Stream API2 in Java, jQuery3 in JavaScript, the Finder Component ofSymfony4 in PHP, and Pretty Tensor5 in Python.
1

http://www.thepollyproject.org
https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html
3
https://jquery.com
4
https://symfony.com/doc/current/components/finder.html
5https://github.com/google/prettytensor
2

1

2

CHAPTER 1. INTRODUCTION
Language
Developer
creates

Application
Developer
creates

Empirical
Studysupports
Language suitable
for Fluent Intf.

Library
Developer
creates
Code-gen.
supports TechniqueApplication
SoftwareLibrary withSafe Fluent Intf.

Figure 1.1: Connection between our studies and application development
Our research does not directly improve the user experiences of fluent
interfaces; we conducted research that helps language and library developers
to improve it. Specifically,
1. we conducted an empirical study to reveal what language design helps
the use of fluent interfaces and to what extent effective it would be.
Such information helps language developers to appropriately design a
suitable language for fluent interfaces.
2. we developed code-generation techniques for safe fluent interfaces, aform of fluent interface that is known to be user-friendly but also
known to cost a lot for its construction. Such techniques enable library developers to construct safe (user-friendly) fluent interfaces withsmaller effort, which leads to more safe (user-friendly) fluent interfaces
to be developed in the real world.
Figure 1.1 illustrates the connection between our studies and application
development. In addition to the studies for better user experiences,
3. we conducted a background suvery to reveal the importance of improving the user experiences of fluent interfaces in a quantitative manner.
The importance have been argued only qualitatively in preceding studies.
In the following, we first illustrate the position of our studies in thecontext of research on programming languages and software engineering.
We then introduce three studies (one background suvery, and two studies
for better user experiences) presented in this dissertation. At the end of
this chapter, we summarize our contributions and present the organizationof this dissertation, along with the correspondence of the chapters and our
publications.

1.1. BACKGROUND

1.1

Background

1.1.1

Importance of Libraries

3

No one would avoid using libraries when developing application software.
Using libraries, one can save time for building common parts with otherapplications and concentrate on developing unique parts of their application.
As well as development speed, the use of libraries also improves the qualityof an application. A program collection provided as a library is usuallytested and maintained by many programmers. Therefore, it is very likely to
be more efficient, secure, and fault-tolerant than programs written on the
fly during their development. We can indeed learn and deeply understanda lot of concepts and techniques by reinventing the wheel instead of using
libraries. Still, that attitude is not appreciated when creating a fast andreliable application that everyone can use with confidence.
The importance of libraries can be observed in the language-selection
tendency; programmers often select a programming language to be used intheir development based on the presence (or absence) of suitable libraries
for the application. Python’s popularity in the machine learning field is agood example of such a selection. Most applications using machine learning
are written in Python now, but Python is not a language developed formachine learning nor one with rich features for it. In fact, the popularity
owes to well-maintained and well-documented libraries written in Python
such as Keras6 and PyTorch7 . According to the survery presented in theliterature [50], the availability of suitable libraries is the most influential
factor for language selection.

1.1.2

User Experiences of Libraries

Since libraries are always used in application development, improving theiruser experiences benefits all programmers. If a library is designed to be userfriendly or if a language is designed to support the use of a certain sort oflibrary, the users can quickly get started and build what they want using thatlibrary. Conversely, if not, the users need to spend much time on unessential
tasks for application development, such as reading the documents, visiting
QA sites, and writing code snippets to test the behavior.
6
7

https://keras.io
https://pytorch.org

4

CHAPTER 1. INTRODUCTION
PL Research

SE Research

On Software Libraries
On Fluent Interfaces

Our Research

Figure 1.2: Position of our research

1.1.3

Our Scope

In this research, we focus on libraries designed in a certain style known as
fluent interfaces and consider improving their user experiences, instead oftrying to support all types of libraries. This scope limitation is our choice
for better engineering research; we focus on specific cases and investigate
highly effective solutions for those cases, rather than seeking a generic but
less effective solution that works in all possible cases. Figure 1.2 illustrates
the position of our research in research on programming languages (PL) andsoftware engineering (SE).
Although we limit the scope of our research, the scope is broad to acertain degree. Fluent interfaces are not a design for specific domains suchas database operations and machine learning. As we have listed at the very
beginning of this chapter, there are fluent interfaces for various domains
in the real world: Polly for describing fault-handling policies, the Stream
API for processing data sequences, jQuery for HTML DOM traversal andmanipulation, the Finder Component for querying files in a filesystem, andPretty Tensor for building deep neural networks. Further, a fluent interface
does not require exceptional language designs that only a small number ofreal-world languages provide. It only requires the method invocation syntax,
which should be provided in an object-oriented language. Therefore, a fluent
interface can be created in almost all object-oriented languages.

1.2

Acceptance of Fluent Interfaces

In the previous section, we argued the broadness of our scope by describing
the high applicability of fluent interfaces. However, being able to adopt

1.2. ACCEPTANCE OF FLUENT INTERFACES

5

fluent interfaces only indicates their potential and does not indicate theiractual adoption in the real world. If fluent interfaces are less used in real
software development, our research – improving the user experiences of fluent
interfaces – hardly contributes to productivity improvement. The popularityof fluent interfaces has been claimed in the studies [28, 29, 42, 83, 84], but
those claims are based on qualitative discussions about the advantages offluent interfaces. Even worse, there are online materials that refer to fluent
interfaces as a problematic design style [7, 65].
This meta-concern leads us to an empirical study to reveal the realworld acceptance of fluent interfaces in a quantitative manner. To dispel
this concern, we collected Java repositories on GitHub8 and analyzed historical trends and frequent code patterns of method-chaining expressions(expected expressions using fluent interfaces). The analysis of historical
trends is crucial. Even if the use of fluent interfaces is seemingly high, ourresearch soon becomes ineffective when the use is shrinking over time. We
chose Java as the target language since Java has been widely used for a longtime and there are a number of repositories on GitHub from more than ten
years ago, which is a preferable property for analyzing the historical trends.
One may think that analyzing method-chaining expressions is an indirect or strange approach for revealing the real-world acceptance of fluent
interfaces. However, other approaches have fatal problems:Counting libraries with fluent interfaces. The main problem of thisapproach is that the increasing number of fluent interfaces does notindicate the increasing use of fluent interfaces. As we described above,
our concern is whether fluent interfaces are increasingly used or not.
Furthermore, without concrete use cases, it is difficult to objectively
judge if a library provides a fluent interface since many fluent interfaces
do not explicitly introduce themselves so. For instance, the documentation of the Stream API does not contain the word “fluent”.
Interviewing real-world programmers about fluent interfaces. The
primary problem of this approach is that it is difficult to answer aquestion about several years ago (e.g., how often were you using fluent
interfaces five years ago?). As the quantitative observation of historical changes is essential to investigate real-world acceptance, thisapproach is inadequate. Moreover, the answers are likely to be noised
by interviewees’ subjective since the definition of a fluent interface isa controversial topic (see chapter 2 about the controversy).
8

https://github.com

6

CHAPTER 1. INTRODUCTION

Note that we do not argue these alternative studies are completely useless.
We discuss these studies as future work in chapter 3 and chapter 4.

1.3

Empirical Study of Language Desings

The user experience of a library can be improved by designing a programming language appropriately. As an example, consider the following code
piece in Java:// Retrieving top - left value of table
int i = table . rowAt (0). valueAt (0). asInt ();If rowAt returns null in case where no row exists at the given index, this line
cause a null pointer exception. To avoid such a runtime error, a programmer
needs to split the method chain into two chains and insert the guard asfollows:
Value value ;Row row = table . getRowAt (0);if ( row != null ) {value = row . getValueAt (0)}value = null ;While the runtime error can be eliminated by splitting the chain as shown
above, such a separation is not appreciated in terms of the design concept offluent interfaces. The nullsafe type system and safe call syntax in Kotlin [59]makes the legibility better for this code pattern.
return table . rowAt (0)? // Safe call on nullable type. valueAt (0). asInt ();Other than the above-described design in Kotlin, several designs in advanced(but less popular) languages have been known to help the use of fluent
interfaces.
Our first study for better user experiences aims to reveal what language
design is useful to support the use of fluent interfaces and how large theimpact of introducing those designs is, through the examination of methodchaining expressions in the real world. Since we attempt to discover a language design, counting the use of some language designs is inappropriate.
Such an approach would reveal the impact of a certain language design but
does not lead to the discovery of unknown language designs.

1.4. CODE GENERATION FOR SAFE FLUENT INTERFACES

7

To this end, we manually analyzed method-chaining expressions that are
randomly sampled from collected Java repositories on GitHub. Specifically,
we investigated possible reasons why those invocations are not chained ina code piece and looked for language designs to transform the piece into asingle method-chaining expression. We chose Java since Java has a relatively
simple syntax and does not provide any special designs for the use of fluent
interfaces.

1.4

Code generation for Safe Fluent Interfaces

A safe fluent interfaces is a fluent interface that is designed to cause a typeerror when the user chains method invocations in an incorrect manner. No
difference exists in the appearance of source code between a safe fluent interface and a (regular) fluent interface. The difference is apparent only when
an incorrect method chain is type-checked. This feature of misuse detection
greatly improves the user experiences since the users can find misuses atcompile time without checking the documentation or writing test code.
The misuse-detection capability is achieved by setting the return type ofeach method based on which methods the user can invoke next. To illustrate
this more concretely, consider developing a Java library for composing the
SQL queries as follows:// SELECT name FROM users
new SQL (). select ( " name " ). from ( " users " ). execute ();Since this library is for emulating the SQL queries in Java, the following
chain should be incorrect:// Missing ` from () `; Invalid SQL query
new SQL (). select ( " name " ). execute ();This misuse can be detected in type-checking if the return type of select()
is a type that only has from(). The users are forced to invoke from()right after the invocation of select(). If they invoke execute() right after
select(), a type checker of a language emit a type error. Figure 1.3 shows
this safe architecture in more detail and how a type error occurs by example.
Safe fluent interfaces also improve programmers’ productivity while editing source code, not only at compile time. They cooperate well with amethod-completion system in an integrated development environment (IDE),
which usually suggests candidate methods based on the return type of amethod. Since the return type of each method is selected appropriately in

8

CHAPTER 1. INTRODUCTION

class SQL {SQL () { ... }SQL1 select () { ... }}class SQL1 {SQL2 from () { ... }}class SQL2 {SQL3 where () { ... }Result execute () { ... }}class SQL3 {Result execute () { ... }}(a) Architecture// Invalid statement causes compile error
new SQL (). select (" name ") // Returns ` SQL1 `. where (" id = 1") // ` SQL1 ` does not have ` where () `// Type error !
// Valid statement causes no error
new SQL (). select (" name ")// Returns ` SQL1 `. from (" users ")// Returns ` SQL2 `. where (" id = 1") // Returns ` SQL3 `. execute ();(b) Usage examples

Figure 1.3: Architecture and examples of safe fluent query builder

Figure 1.4: Method completion1.4. CODE GENERATION FOR SAFE FLUENT INTERFACES

9

class SQL {SQL () { ... }SQL select ( String columns ) { ...; return this ; }SQL from ( String table ) { ...; return this ; }SQL where ( String expression ) { ...; return this ; }Result execute () { ... }}Figure 1.5: Architecture of naively-designed fluent query builder

the safe fluent design, the methods appearing in the candidate list are correct methods and the users can quickly build an expression just by selectingfrom those correct candidates. Figure 1.4 is the screenshot showing the difference of the candidate methods in the safe fluent design and in the naive
design (shown in fig. 1.5).
Although safe fluent interfaces offer the above-mentioned advantages tothe users, it is not widely used in the real world due to its development cost.
The library developers need define a number of classes and wire them bycarefully selecting the return type of each method, to give the safe property
to the interfaces. As seen in the comparison of fig. 1.3 and fig. 1.5, thesafe design requires four class definitions whereas the naive design requires
only one class definition. When a library provides more features than our
example SQL library, the number often becomes so large that the developers
cannot manage by hand.
To address the problem of the development cost, several studies havebeen published on the code generation of safe fluent interfaces [28, 29, 32,
42, 83, 84]. The key idea is to regard the correct order of method invocations
as the syntax of a method chain. From this viewpoint, the construction of asafe fluent interface can be modeled as the construction of a parser on topof a type system. The code generation of safe fluent interfaces is to generate
source code of the type-level parser from a given grammar.
However, those studies rather focus on the theoretical aspects of this
topic. Roughly speaking, they focus on extending the grammar class thatcan be generated by the algorithms. From the viewpoint of practical applicability, two problems remain unaddressed in the code-generation algorithms:
Lack of sub-chaining support and generics support. In the rest of this section, we describe these problems.

10

1.4.1

CHAPTER 1. INTRODUCTION

Lack of Generics Support

It is popular to define generic methods – methods including type parameters in their definition – when creating a library in the real world. For
instance, the Stream API in Java is an example of such a generic interface. It provides generic methods such as map(Function<? super T, ?
extends R> mapper). A generic method uses a type parameter to checkthe semantic constraints of the interfaces; for example, to check whether acorrect value type is passed through a stream.
However, in preceding studies, the role of a type parameter was limited
to the internal representation of a stack element of the parser built on thetype system. That is, library developers cannot use type parameters fortheir library interfaces. The problem of the existing algorithms can be described as the lack of the binding-time analysis of type parameters, which
we illustrate by example at the very beginning of chapter 5.

1.4.2

Lack of Sub-chaining Support

To take advantage of method chaining in various situations, a fluent interface should provide sub-chaining interfaces, commonly provided interfaces inreal-world libraries to compose a part of a method chain as another method
chain:
select ( " name " ). from ( " user " ). where (col ( " id " ). eq (1) // Sub - chain);
Sub-chaining interfaces allow programmers to build an entire chain fromsemantically grouped partial chains. Without sub-chaining interfaces, programmers need to handle strange types and write less readable code whenchanging a part of a chains or when creating a function for reusing a partof a chain:
PartialQuery q = select ( " name " ). from ( " user " ). where ();PartialQuery r ;if ( findById ) { // findById : Given boolean valuer = q . col ( " id " ). eq (1);} else {r = q . col ( " name " ). eq ( " John " );}r . execute ();1.5. ORGANIZATION AND CONTRIBUTIONS

11

Table 1.1: Organization and correspondence

Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7

Topic

Publication

Overview
Review on fluent interfaces
Acceptance of Fluent Interfaces
Empirical study of language designs
Code-generation for generics support
Code-generation for sub-chaining support
Summary and future work

–
–
[53]
[53]
[52]
[55, 56]–

The above code can be a more readable form that reflects the essential
structure of an expression if sub-chaining interfaces are provided:
WhereClause w1 = col ( " id " ). eq (1);
WhereClause w2 = col ( " name " ). eq ( " John " );select ( " name " ). from ( " user " ). where ( findById ? w1 : w2 ). execute ();However, the existing generators do not generate fluent interfaces withrich sub-chaining support. They are specialized to generate flat-chaining
interfaces from a given grammar. If library developers separately generate
every sub-chaining interface using those generators, it is possible to obtain
fluent interfaces with rich sub-chaining support. However, library developers
need to give the generators a lot of grammar definitions that overlap eachother. To realize the generation of fluent interfaces with rich sub-chaining
support, we need to develop a code-generation technique that automaticallygenerates sub-chaining interfaces besides flat-chaining interfaces.

1.5

Organization and Contributions

This dissertation is a compilation of our publications on fluent interfaces,
specifically the literatures [52, 53, 55, 56]. Table 1.1 summarizes the topic
of each chapter and its correspondence to our publication, and fig. 1.6 illustrates the position of each chapter in the context of PL and SE research.
The next chapter details our discussion on fluent interfaces at the end ofsection 1.1 and the beginning of section 1.2. It includes the terminologies,
review on existing opinions, and comparison to other technologies in terms

12

CHAPTER 1. INTRODUCTION

Chapter 4

Language
Developer

Chapter 3

Chapter 5
Chapter 6

Application
Developer

Library
Developer

Figure 1.6: Positon of each chapter in PL and SE researchof embedded domain-specific languages (EDSLs) [37]. It also examines thesafe fluent design in contrast to other misuse detection techniques.
Chapter 3 presents our meta-study that investigates the significance ofthe study of fluent interfaces, which we have introduced in section 1.2. This
chapter is the first half of our paper published at the Mining Software Repositories conference 2020. The contribution presented in this chapter is asfollows:• We present, to the best of our knowledge, the first quantitative study
on the use of method chaining and fluent interfaces that is based on alarge set of source code in the real world.
• We empirically show the increasing use of method chaining and fluent
interfaces in Java, which has been claimed without empirical evidence
in preceding studies [28, 29, 42, 83, 84].
Chapter 4 statistically analyzes language designs that support the use offluent interfaces. The chapter is the second half of our paper published at
the Mining Software Repositories conference 2020. The contribution of thisstudy, the importance of the concrete list, is as described as follows:• We present a concrete list of language designs (and alternative interface
designs) that support method chaining and fluent interfaces.
• We present our statistical estimation on how effective each design
would be in the real world. This quantitative information is usefulfor language and library developers to objectively judge whether adesign should be introduced into a language or library.
In chapter 5 and chapter 6, we present our code-generation techniques forsafe fluent interfaces. As we have briefly discussed in section 1.4, the existing1.5. ORGANIZATION AND CONTRIBUTIONS

13

studies do not support generics and sub-chaining, both of which are necessary to use the code-generation in the real world. Chapter 5 corresponds tothe paper published at the Art, Science, and Engineering of Programming.
Chapter 6 corresponds to our paper published as an article in Journal ofComputer Languages, which is the extended version of our another paper
published at the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences. The following summarizes
our contibutions presented in chapter 5 and chapter 6:• We have developed a code-generation technique that can generate
generic fluent interfaces. To realize this, we developed an algorithm
that analyzes binding time of type parameters in a deterministic finitestate automaton (DFA). Since the necessity of such an analysis is newly
discovered by our study, there is no similar methods as far as we know.
• We have developed a code-generation technique that supports rich subchaining interfaces. The generation technique is modeled as the construction of single-state real-time deterministic pushdown automata(RPAs). Our RPA-construction method is different from the literatures [34, 64] in that it does not add or remove non-terminals from agiven grammar, which is an essential property to generate sub-chaining
interfaces as specified in the grammar.
Chapter 7 concludes our research. Specifically, we highlight the resultsof empirical studies and summarize the overview of our code-generation
techniques. In this chapter, we also discuss possible directions of future
work to complement our empirical results and bring the code-generation
into the real world.

14

CHAPTER 1. INTRODUCTION

Chapter 2

Fluent Interface
2.1

Terminologies

The word “fluent interface” is coined by Evans and Fowler [20] in 2005.
At that time, fluent interfaces were not a common design according to theliterature [20]. In 2010, fluent interfaces were referred to as a promising
design style of library interfaces that is known in industry but less known
in the research community [83]. In 2020, fluent interfaces can be considered
as a knwon term even in the research community thanks to the studies inrecent years [5, 9, 28, 29, 32, 41, 42, 84].
However, the definition of a fluent interface and the ones of related terms
have not been fixed yet. The meaning of each term differs from one material to another although they share the basic concepts. Such a fluctuationin terminologies is often seen in the definition of a design style of software
components. Although the fluctuation may be inevitable since many designs were firstly born and raised in real-world software development as bestpractices and later named by some opinion leaders or researchers, the discussion about a style often fails to reach an agreement because of mutual
misunderstandings.
To avoid misunderstandings, we begin this chapter with our terminologies in this dissertation. Concretely, we (roughly) define three terms: Method
chaining, fluent interface, and safe fluent interface.

2.1.1

Method Chaining

Method chaining is a programming style in which multiple method invocations are chained in a single expression as follows:15

16

CHAPTER 2. FLUENT INTERFACE

Value topLeft = table . getRowAt (0). getValueAt (0);Method chaining is often interchangeably used with method cascading, but
we distinguish one from the other: Method chaining is a chain of method invocations connected by method invocation operators such as the dot symbolin Java and the arrow symbol (->) in PHP; method cascading is a chain connected by special operators for cascading such as the semicolon operator in
Smalltalk [3] and the double-dot operator (..) in Dart [49]. While method
chaining requires a method invocation to return an object, the method cascading syntax allows programmers to chain a method that does not return
any object.

2.1.2

Fluent Interface

As we described at the very beginning of this dissertation, fluent interfaces
are a design style of library interfaces that is designed to be used by method
chaining. This definition is almost the same as the one introduced by Grigore [32]:We say that it has a fluent interface when it encourages its users
to chain method calls
Grigore’s definition is slightly different from our understandings1 of the definition of Fowler [20]. Fowler’s definition is more narrow than Grigore’s inthat Fowler’s rejects method names like setFoo in fluent interfaces. However, real-world fluent interfaces often contain method named like setFoo.
Therefore, we define fluent interfaces as mentioned above.
Note that, as mentioned in the blog post by Fowler [20], method chaining
and fluent interfaces are not equivalent although they are often confused inmany materials. Method chaining is about how programmers write source
code, whereas fluent interfaces is about how library developers design theinterface of a library. Technically, any method invocations can be chained
as long as they return objects. Therefore, most object-oriented libraries
can be used in the method-chaining style, but using a non-fluent library –whose interfaces are not designed for the method-chaining style – would betroublesome. On the other hand, a fluent interface can be used without
chaining method invocations.
1

In our understanding, Fowler did not give a clear definition of a fluent interface. Instead,he showed examples of what he think fluent interfaces are and describes the difference
from mere method chaining.

2.2. EXISTING DISCUSSIONS ON FLUENT INTERFACES

2.1.3

17

Safe Fluent Interface

In this dissertation, we refer to a fluent interface with the misuse-detectablearchitecture as a safe fluent interface. We use this term to explicitly distinguish ones with the misuse-detectable architecture (e.g., fig. 1.3) fromnaively-designed ones (e.g., fig. 1.5). When the safeness is obvious from thecontext, we refer to safe fluent interfaces as simply fluent interfaces. For example, we say “code-generation for fluent interfaces”, not “code-generation
for safe fluent interfaces”, since the code-generation techniques discussed inthis dissertation are always for safe fluent interfaces. In the studies [28, 29,
32, 42, 84], safe fluent interfaces are simply called fluent interfaces since thesafe property is prerequisite for thier studies.

2.2

Existing Discussions on Fluent Interfaces

While the advantage of fluent interfaces is described from various perspectives, all arguments essentially claim the high readability of source code
written with fluent interfaces, i.e., expressions in the method-chaining style.
In other words, the advantage of fluent interfaces is actually the advantage
of method chaining.
The readability of source code has a significant impact on the productivity of programmers. In the book [46], Martin puts the importance of
readable code as follows:
Indeed, the ratio of time spent reading versus writing is well over
10 to 1. We are constantly reading old code as part of the effort
to write new code. ...(Therefore,) making it easy to read makes
it easier to write.
While the precise ratio is arguable, the readability is certainly important as
we do not write a line without reading code around that line. A lot of studies
have been conducted to develop code-readability and code-quality metrics [8,66, 71], but no metric system is designed for scoring the readability of asingle expression, to the best of our knowledge. Existing metrics are rather
for measuring code quality of a set of source code in a project. Due tothis difficulty, the positive opinions on fluent interfaces are subjective andqualitative, which leads us to the background survey presented in the next
chapter.
The negative opinions on fluent interfaces and method chaining are not
only about code readability. For instance, in the thread on Stack Overflow [60], many programmers claim the disadvantages of fluent interfaces

18

CHAPTER 2. FLUENT INTERFACE

and method chaining from the viewpoint of code readability, tool supports,
and potential risks using fluent interfaces or method chaining. The online
materials [7, 65] discusses the disadvantages from library developers’ perspective.
In the rest of this section, we detail existing discussions of both sides.
As we described in the previous section, the terminologies are often different
from ours; Some materials blame fluent interfaces (their terminology), butthey blame method chaining in our terminologies. To avoid confusion, we
rephraze the original sentences and review the opinions.

2.2.1

Positive Opinions

Method chaining is a programming style to eliminate redundant temporary
variables and code repetitions [60]. It assembles related method invocations
in a single expression [83]. The following code snippet in Java illustrates
these benefits:// Method chaining
new AlertDialog (). setTitle ( " Warning " ). setMessage ( " Are you sure ? " ). show ();// Without method chaining
AlertDialog dialog = new AlertDialog ();dialog . setTitle ( " Warning " );dialog . setMessage ( " Are you sure ? " );dialog . show ();As we see, the temporary variable dialog is not used in the method chaining
style. All the method invocations for the dialog construction are assembled
into a single expression. Fewer occurrences of temporary variables contributeto the code readability since they allow the programmers to keep only fewer
variables in mind [60]. These apparently small improvements on source code
affect a lot when dealing with many objects in the real-world settings.
The materials [20, 7, 83, 5] claim that a chain of method invocations areoften easy to read from left to right as natural-language texts. For example,
we can easily read the following code from left to right and understand thatthe elements of strList are filtered out and a function is applied to theremaining elements:
strList . filter ( s -> s != " " ). map ( s -> s + " . " );2.2. EXISTING DISCUSSIONS ON FLUENT INTERFACES

19

In the functional nesting style, the same computation is expressed in thereverse order, which possibly impose a cognitive burden on the programmers:map ( filter ( strList , s -> s != " " ) , s -> s + " . " );Some libraries such as jOOQ2 make good use of the left-to-right property toembed a domain-specific language (DSL, relatively small language designed
for a specific domain) in an object-oriented language:// " SELECT name FROM user WHERE id = 1" with jOOQ
select ( field ( " name " )). from ( table ( " user " )). where ( field ( " id " ). eq (1));
As demonstrated by jOOQ, fluent interfaces is a popular means of implementing DSLs inside an (general-purpose) object-oriented language. However, it is not the only option that introduces a domain-specific notation into
general-purpose programs, for which syntax extension is a well-known solution. SugarJ [17] provides a method for extending Java syntax. ProteaJ [38],Wyvern [58], and Honu [68] are programming languages that natively support syntax extension. Using these syntax extension mechanisms, domainspecific notation can be embedded as is. When embedding a language asa fluent interface, such notation needs to be transformed into a method
chain that differs slightly from the original notation. However, their powerful features are realized by their underlying language mechanism such astype systems, so it is difficult to introduce a similar system to a languagethat is currently used in practice. A fluent interface, on the other hand, isa technique that can be applied to a number of general-purpose languages
since it is just a class library. Moreover, it only requires method invocation
syntax such as obj.method(...), which is offered by most object-oriented
languages.
Although the cognitive ease of the left-to-right readability is less insisted
explicitly, library developers have been aware of its advantage before Fowler
gives the name to fluent interfaces. Source code in Smalltalk, a programming
language born in 1970s, heavily relies on method cascading that offers theleft-to-right readability. The iostream library3 uses the the shift operators(<< and >>) to send multiple messages to the same object.

2.2.2

Negative Opinions

The readability improvement by method chaining is, however, controversial. In the thread on StackOverflow [60], several posts claim that method
23

https://www.jooq.org
http://www.cplusplus.com/reference/iostream/

20

CHAPTER 2. FLUENT INTERFACE

chaining rather worsens the readability. For example, a post says:
If you do everything in a single statement then that is compact,
but it is less readable (harder to follow) most of the times thandoing it in multiple statements.
The same post also mentions that a long statement has to be split into multiple lines with indentations. The resulting code is not more readable than
the non-chaining style. However, the readability is highly subjective as we
mentioned at the beginning. The results of our background survey show theincreasing use of the method-chaining style in the real world. Considering
those results, most programmers would not see method chaining as a badpractice that should be avoided as much as possible.
Another post in the thread [60] mentions that method chaining is notreconcilable with the debuggers of most modern IDEs, which allows line-level
breakpoints:
You can’t put the breakpoint in a concise point so you can pause
the program exactly where you want it - If one of these methods
throws an exception, and you get a line number, you have noidea which method in the “chain” caused the problem.
A simple workaround is to split a line to give a different line number to eachmethod invocation. Another workaround is to set a breakpoint not on thecaller site but on the callee site, which is the body of the called method.
However, these workarounds complicate debugging. Our background surveythat shows the increasing use of method chaining would be a quantitativebasis for developing a special debugging feature for this situation.
Several posts on the thread [60] claim that method chaining violates adesign guideline for developing a loosely coupled software known as the lawof Demeter [43]:For all classes C, and for all methods M attached to C, allobjects to which M sends a message must be• M ’s argument objects, including the self object or• The instance variable objects of C.
(Objects created by M , or by functions or methods which M
calls, and objects in global variables are considered as argumentsof M .)

2.3. EXISTING CODE-GENERATION ALGORITHMS

21

In the empirical study [33], the violation of this law has a negative impact on
software quality. However, a fluent interface usually does not violate the law
although it depends on the implementation of a fluent interface. Therefore,
the law of Demeter is not a guideline that discourages fluent interfaces.
A post in the thread [60] says that method chaining often leads to unexpected a NullPointerException, an exception thrown on null dereferencing. This potential risk discourages method chaining, but not fluent interfaces since methods in naively-designed fluent interfaces (e.g., fig. 1.5) do no
return a null pointer. Methods of safe fluent interfaces do not either. Furthermore, a special language design is implemented in advanced languages
such as Kotlin or Swift to reduce this sort of exceptions. In section 4.1,
we discuss the impact of introducing the design into Java in a statisticalmanner.
The blog posts [7, 65] point out the drawbacks of fluent interfaces: A
fluent library cannot be extended using inheritance, a common extension
mechanism in an object-oriented language [65]. The post [7] also blames fluent interfaces since the library developers need to pay more costs to maintaina fluent library than a non-fluent library. Those problems exists in many
languages, but not in increasingly-used languagegs such as Kotlin and Swift.
The solutions by language designs are discussed further in chapter 4.

2.3

Existing Code-generation Algorithms“Keep it simple” is a famous motto in tool and system design. The UNIXphilosophy [70] states it as follows: Write programs that do one thing anddo it well. Although the statement is about command line programs, it canbe applied to the design of class libraries. A small and simple method that
performs only a single task is easier to understand for its users and is easier
to manage for its creators, compared to a large and complex method that
does multiple tasks at once. Furthermore, a collection of small methods ismore flexible. Library users can express a combinatory number of processesor specifications by combining small methods, whereas they cannot executea part of a large method. Method chaining is a suitable style for combining
a lot of method invocations since it reduces temporary variables and coderepetitions (as disussed in section 2.2.1).
The problem of the keep-it-simple style is that a combination is not always correct; for example, some method needs to be invoked before anothermethod. The safe design of a fluent interface is a technique to check the violation of rules on a combination of method invocations using a type system.

22

CHAPTER 2. FLUENT INTERFACE
Table 2.1: List of existing algorithms and tools

fluflu4
TS4J [5]EriLex [83]Fajita [42]Alg. of Gil and Levy [28]Alg. of Gil and Roth [29]TypelevelLR [84]ScaLALR5
Alg. of Grigore [32]Grammar class

Output language

Regular grammar
Regular grammar
LL(1) grammar
LL(1) grammar
LR grammar
LR grammar
LR grammar
LR grammar(Turing-complete)

Java
Scala
Java
Java
Java
C++, Scala, Haskell
Scala
Java

Unfortunatelly, the true origin of the safe design is ambiguous. As far as weknow, the material explicitly describing the idea is the post by Fowler [20].
The important idea in the code-generation of fluent interfaces is to express the rules on the combination by a grammar (or by describing statemachines). Although the true origin of this idea is not clear either, the firstacademic study based on the view is published by Xu [83] in 2010. Since
then, a number of studies and tool development have been conducted. Table 2.1 summarizes those studies and tools. In the rest of this section, we
explain each of them and discuss the difference from our studies presented
in chapter 5 and chapter 6.

fluflu and TS4J
Fluflu is the first – as far as we know – code generator for fluent interfaces.
The input to fluflu is Java source code that describes finite-state machines,
which is equivalent to the descriptions in the regular grammar. The projectis deprecated now, but the successor Java::Geci6 have been developed by
the same developer.
TS4J [5] generates fluent interfaces from a regular grammar. For thegeneration, it builds a deterministic finite-state automaton (DFA) from agiven grammar and encode the DFA into Java class definitions.
4

https://github.com/verhas/fluflu
https://github.com/phenan/scalalr
6
https://github.com/verhas/javageci5

2.3. EXISTING CODE-GENERATION ALGORITHMS

23

EriLexEriLex [83] is the first fluent interface generator presented as a research
artifact. It generates fluent interfaces from a given grammar by encoding areal-time deterministic pushdown automaton (RDPA) into class definitions.
As EriLex uses RDPA in its encoding process, the supported grammar classis the LL(1) grammar. Although the output is a set of Scala class definitions,the core technique used in EriLex-generated definitions can be exported
into Java since the generated definitions do not use Scala-specific features.
Fajita [42] is a tool that demonstrates it is in fact exportable into Java.
The drawback of EriLex is that the input needs to be LL(1) in Greibach
normal form [31], which is a form that most of manually written grammars
do not follow. Furthermore, there is no algorithm to rewrite a grammar into
the form required by EriLex as far as we know. Whether given grammar
can be rewritten into that form is undecidable [69].

Algorithm of Gil and Levy
Levy and Gil proposed an algorithm to translate an LR grammar to a fluent
interface [28]. It first builds a jump-stack single-state real-time deterministic
pushdown automaton (JRDPA) and then encodes the automaton into Javaclass definitions. Since a JRPA can recognize deterministic context-freelanguages [12] and this class of languages is larger than the class that RPAs
can recognize [34].
However, with a set of definitions generated by the algorithm of Levy
and Gil, the compilation time of a method chain grows exponentially to thelength of the chain in the worst case. This is caused by the exponential
growth of the size of the type at the end of a chain, as Levy and Gil showedin their experiment using Java 8.

Algorithm of Gil and RothIn the literature [29], Gil and Roth have proposed another algorithm for an
LR grammar to overcome the compilation time problem of their previous
algorithm [28]. The newer algorithm uses a compact DAG representationof the tree encoding data structure to emulate a deterministic pushdown
automaton on real-time devices such as the Java type system.

24

CHAPTER 2. FLUENT INTERFACE

TypelevelLR and ScaLALR
TypelevelLR [84] is a tool for translating an LR grammar into a safe fluent
interface in Scala, Haskell, and C++. The generated definitions in Scalaand Haskell use type classes to encode  transitions of an LR parser into
type definitions. The generated definitions in C++ uses C++ templates
to encode the  transitions. ScaLALR7 is the predecessor of TypelevelLR,
which builds an LALR parser and generates Scala source code for safe fluent
interface.
One drawback of TypelevelLR and ScaLALR is the clever use of advanced type systems. Since most widely-used languages do not offer typesystems that are strong as Scala, Haskell, and C++, the technique in those
tools is less portable to other languages.

Algorithm of Grigore
Grigore demonstrated that Java’s type system is Turing complete [32]. Using
this result, he illustrated that a CYK parser [10, 85, 40] can be constructedusing Java types. Although he discovered the theoretical upper bound ofgrammar classes that can be checked by Java’s type system, his techniquerequires a large memory size. This is because it builds the parser on top of
the Turing machine implemented by the Java types. The similar approach
can be applied to C++ since the type-system of C++ is also known to be
Turing-complete [81].

Summary and Comparison to Our Techniques
As we have explained so far, recent research on the code-generation of safe
fluent interface has focused on the syntax-checking capability. The study
by Xu presented an algorithm to translate LL grammar into a safe fluent
interface [83]; Gil and Levy proposed an algorithm to translate LR grammar
into a safe fluent interfaces [28], which is later improved by Gil and Roth[29]. The study by Grigore [32] shows the Turing-coompleteness of of theJava type system, which indicates that the Java type system can even check
context-sensitive grammar.
Their key concept for checking context-free structures was using nested
generics (parameterized types) to represent a stack structure on top of thetype system. The role of a type parameter is to represent a stack element.
7

https://github.com/phenan/scalalr

2.4. MISUSE DETECTION TECHNIQUES25

Such a role differs from the ones in real-world fluent interfaces such as AssertJ8 , jOOQ, and j2html9 . In those manually written fluent interfaces, typeparameters are used to eliminate boilerplate code in classes for APIs. For
example in AssertJ, type parameters are used to store the type of this inJava [16] and help the developers to implement methods that have the same
signature but a different return type.
The essential differences from the preceding studies and our techniques
is the support for generics and sub-chaining. As we have described in section 1.4, those two types of support is indispensable for real-world use of thecode-generation techniques.
In theory, as we demonstrate in section 5.3.1, our technique can generate
fluent interfaces with context-free rules by explicitly using type parameters
to represent a stack structure. However, the generation of such fluent interfaces is excessively tedious since the users of our technique need to encodea pushdown automaton into the specification manually. (The encoding of apushdown automaton has been automated in previous studies.)

2.4

Misuse Detection Techniques

Although we focused only on the syntax correctness of a DSL sentence inthis chapter, techniques for semantic checking have also been studied. For
example, AraRat [27] uses C++ template metaprogramming to allow its
users to compose SQL queries that are syntactically correct and type-safewith respect to the database schema. The integration of such semantic
checking and our library generation technique is left for future research. We
also focused on fluent interfaces in this chapter, but other host language’s
mechanism such as operator overloading can be used to emulate a DSL
sentence in a GPL program (e.g., sqlpp10 . The advantage of method chainingis that it requires only method invocation syntax, which should exist in an
object-oriented language, to the host language.
Typestate analysis [74] is a form of program analysis that verifies whether
an operation sequence performed on an object follows specified rules (orprotocols). Objects with typestates occur quite frequently. According to
the literature [4], 7.2% of Java types define protocols. Various techniques
have been proposed to realize typestate analysis. Plaid [75] is a languagethat inherently provides features for typestate analysis. Because typestate8

https://joel-costigliola.github.io/assertj/
https://j2html.com
10
https://github.com/rbock/sqlpp11926

CHAPTER 2. FLUENT INTERFACE

analysis is a type of static code analysis, it can be achieved by using generalpurpose code analyzers such as FindBugs11 , PMD12 , and QL [2]. Techniques
for mining typestate specifications have also been studied to overcome thedifficulty of completely defining the specification by hand [13, 67, 25, 24].
Generating a fluent interface can be regarded as a technique for realizing
typestate analysis with the type system of a language. It encodes each stateof a type into a concrete type definition of a target language. The validityof the operation sequences is checked by the type system of that language.
Such a generative approach causes two problems that do not occur whenusing external analyzers. Firstly, strange names are given to intermediate
states, which may confuse API users. Secondly, performance deterioration
may occur owing to the increase in the type definitions. These problems
have not been studied yet as far as we know and their investigation will
form part of our future work. Although the generative approach suffers fromthese disadvantages, it offers advantages that are not immediately provided
by external analyzers. It aids API users in that a method completion system
becomes state aware [83, 56], and it is also beneficial to library developers.
As the type checker rejects code violating the protocol, developers do notneed to add the implementation for handling such cases.

1112

http://findbugs.sourceforge.net
https://pmd.github.io

Chapter 3

Method Chaining
in the Real WorldAs we described in chapter 1, we analyze method-chaining expressions in
the real world to reveal the significance of studying fluent interfaces; we
do not count the number of libraries that provide fluent interfaces since
the increasing number of existing fluent interfaces does not indicate theincreasing use of fluent interfaces. The analysis of the use of fluent interfaces
is presented as a part of the analysis of method-chaining expressions in
section 3.6.
This chapter is organized as follows: We first describe the materials
and methods used in our analysis in section 3.1 and section 3.2. We thenshow and discuss the results of our analysis from section 3.3 to section 3.7.
Section 3.8 argues the threats to validity, and section 3.9 relates our workand preceding studies. Finally, section 3.10 summarizes this chapter anddiscusses future work.

3.1

DatasetTo build our dataset, we collected 2,814 Java repositories on GitHub. Those
repositories are the ones that were listed at least once in the most-starred
1,000 Java repositories on GitHub between Nov. 10th, 2019 and Dec. 21st,2019. We collected them by monitoring the response of the GitHub API1
every day during that period.
We built our dataset by extracting syntactically valid .java files from1

https://api.github.com/search/repositories?q=language:java&sort=stars

27

28

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD

Algorithm 3.1 Dataset construction
Input: Set of repositories Repositories
Output: Dataset Dataset
1: for each repository ∈ Repositories do
2:
N ame ← Name of repository
3:
Revisions ← Year-end revisions of repository4:for each revision ∈ Revisions do
5:year ← Year of revision
6:
for each .java file f ile in revision do
7:code ← Content of f ile
8:
Add (code, name, year) to Dataset

the year-end revisions of each repository in the most-starred repository set.
The year-end revision of a year is the latest revision made in that year.
We classified a .java file as syntactically valid when JavaParser2 , a parser
often used both in industry and academia, successfully parses the content
of that file. To find year-end revisions, we use the command git rev-list<branch>, which lists all the revisions reachable from <branch>. We set<branch> to the default branch3 of the repository. The default branch of arepository is different depending on the configuration of the repository on
GitHub, but it is master in most repositories.
An entry of the dataset is a tuple (code, name, year), where code is thecontent of a source file, name is the name of the repository to which thefile belongs, and year is the year of the revision to which the file belongs.
Algorithm 3.1 shows pseudocode for constructing our dataset from a given
set of repositories. The set of the most-starred repositories were used as the
input to this algorithm.
Our dataset contains over three million Java files (approximately seven
hundred million source-code lines) in total. Figure 3.1 shows the number ofrepositories, files, and lines in each year. As seen in the figures, the amountof the collected code considerably varies from year to year. This propertyof our dataset indicates that it is inappropriate to directly compare the raw
numbers in each year.

2
3

https://javaparser.org
https://help.github.com/en/articles/setting-the-default-branch

3.2. DEFINITION OF CHAIN LENGTH

1.5
1.0

0.0

1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018

0.5

7
6
5
4
3
2
1
0

1e5

1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018

2.0 1e3(a) Number of repositories(b) Number of files

1e8

1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018

1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

29

(c) Number of lines

Figure 3.1: Number of repositories, files, and lines

3.2

Definition of Chain Length

We define a method chain as a sequence of one or more method invocations
joined by the “.” symbol. We define the length of a method chain as thenumber of invocations in the sequence. For example, the Java code snippet
shown in fig. 3.2 contains five chains of length 1, one chain of length 2, andone chain of length 3. We used JavaParser to parse a Java file and mined
the parsing result for method chains.
We first enumerated the chains of length 1 (non-chained method invocations) from our dataset to obtain the baseline values. If the number of
non-chained invocations increases at the same pace as the number of method
chains longer than one, we cannot argue that the use of method chaining is
growing. Note that, for convenience, we below regard a non-chained invocation as a method chain of length 1.

30
1
2
3
4
5
6
7
8
9
10
11
12

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD

List < String > list = new ArrayList ();list . add (cr ea te Ra nd om St ri ng () // Length = 1); // Length = 1
list . stream (). map ( s -> {return s . replace ( " foo " , " bar " ). replace ( " baz " , " qux " ); // Length = 2}). forEach ( s ->int n = s . split ( " \ n " ). length // Length = 1
String t = String . format ( " % d " , n ); // Length = 1
System . out . println ( t ); // Length = 1); // Length = 3
Figure 3.2: Method chains and their lengths

3.3

Overall Trend

We measure the frequency of method chaining to judge whether it is widelyused in the real world. In our analyses, we use only the code that is newer
than or in 2010. 2010 is the year in which the number of repositories exceeds
250 and in which the number of files exceeds 105 for the first time. We adopt
this criterion to avoid that the programming styles of a small number of old
repositories overly affect our analysis.
We use the following two indicators fn and r to measure the frequency:
fn = mn /m1 ,r = (Σ2≥n nmn )/(Σ1≥n nmn ),where mn is the raw number of method chains of length n. The indicator fn
is the relative occurrence of chains of length n. The indicator r is the ratioof the method invocations that are part of method chains longer than 2,
among all the method invocations. For example, the f2 value of the code in
fig. 3.2 is 1/5 (= 0.2) since the code includes five chains of length 1 and one
chain of length 2. The r value of the example code is 5/10 (= 0.5) since thecode includes ten method invocations in total and five of them constitutethe method chains of length 2 or 3.
Figure 3.3a shows the plot of fn for the code in 2010 and 2018. (The fnvalues are computed over the total dataset and not the averages of per-filevalues.) The horizontal axis shows the value of n and the vertical axis shows3.4. POWER-LAW DISTRIBUTION
100

2018
2010

10 2

0.20
0.15

10 4

0.10

(a) fn in 2010 and 2018

2018

2017

2016

2015

2014

2013

103

2012

102

2011

0.00
101

2010

0.05

10 6
10 8 0
10

31

(b) r

Figure 3.3: Frequency of method chaining
the value of fn . Note that we use logarithmic scales for both vertical andhorizontal axes. Figure 3.3b shows the plot of r from 2010 to 2018. Although
we omit the plot of fn values from 2011 to 2017, similar distributions areobserved in those years.
Both charts in fig. 3.3 show the increasing use of method chaining. The
relative number of method chains has increased from 2010 to 2018 in almost
all lengths. The r value has increased from 16.0% to 23.1%. Further, themaximum length of a chain has also been increased from 2010 to 2018.

3.4

Power-law Distribution

As seen in fig. 3.3, fn decreases almost linearly in the log-log scale plot. Sucha linear decrease is observed when a distribution has a heavy tail [57]. The
heavy tail indicates that extremely long chains often appear and their occurrences are not exceptional, unlike a normal distribution. Such distributions
are found in several measures of source code such as change sizes [30, 44, 82],
component sizes [35], in-degree and out-degree in dependency networks [45],and the number of subclasses [79].
We performed the Kolmogorov-Smirnov (KS) test to see whether theright tail of fn in 2018 is generated by a power-law distribution, a wellknown heavy-tailed distribution. The test reported 9 for xmin and 0.937
for p-value. The p-value is greater than the commonly used significancelevel 0.05. These results of the KS test indicate that it is consistent toassume that the observed values for n ≥ 9 are generated by a power-law
distribution. Although it is interesting to discover the generation model ofsuch a distribution, we leave it for future work.

0.30

2018
2014
2010

q3
q2
q1

0.25
0.20
0.15
0.10

(a) Distribution

2018

2017

1.0

2016

0.8

2015

0.6

2014

0.4

2013

0.00
0.2

2012

0.05
2011

70
60
50
40
30
20
10
0
0.0

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD

2010

32

(b) Trend of quartiles

Changes of quartiles from 2010 to 2018
1st quartile

2nd quartile

3rd quartile

Average+1.71%+4.27%+7.34%+7.08%

Figure 3.4: Distribution and trend of per-repository r

3.5

Bias in Frequency

Since the two indicators shown in fig. 3.3 represent average values for therepositories in our dataset, we observed only average trends in our dataset.
In this section, we examined the following hypothesis: Only a small numberof large repositories in our dataset might contain a large number of method
chains and increase the total number of chains in our dataset, while others
contain a small number of chains. To reveal the bias of the increase foundin fig. 3.3, we computed the r value for each repository and carried out theanalysis on their distribution.
Figure 3.4a shows the histograms of per-repository r in 2010, 2014, and2018. The horizontal axis shows the value of r and the vertical axis shows
the number of repositories. Figure 3.4b shows the trend of their quartiles.
All the information in Figure 3.4 shows that the overall r value is increased not only by a few repositories. If the increase has occurred only ina small number of repositories, we would not have observed changes in thefirst and second quartiles. However, the increase of overall r value is increased significantly by repositories containing a lot of method chains since
the change in the third quartile is much larger than the change in the firstquartile.

3.5. BIAS IN FREQUENCY
1.0

33
2018
2010

0.8
0.6
0.4
0.2
0.0
100

101

102

n

un in 2018

un in 2010

1
8
9
41
42

100%
50.1%
44.1%
5.10%
4.98%

100%
42.7%
38.0%
4.31%
4.31%

103

Figure 3.5: Ratio containing chains longer than or equal to n

To see the widespread use from a different perspective, we calculated thefollowing value:
un : The ratio of repositories that contain one or more method chains whose
length is longer than or equal to n.
The left chart in fig. 3.5 shows the plot of un in 2010 and 2018. The horizontal axis shows the value of n and the vertical axis shows the value of un .
Note that we use a logarithmic scale for the horizontal axis. The table on
the right shows the values that we refer to in later analyses.
Figure 3.5 shows that more than 50% of repositories contain at least
one chain longer than length 7. Since chains of length 8 are unlikely to becomposed by programmers who tend to avoid method chaining, this result
is another supportive evidence for the widespread use of method chaining.
We also investigated the difference in the use of method chaining between
testing code and non-testing code. Figure 3.6 shows the plot of fn values
and the changes in r values in those code sets.
The figures show that the testing code contains more method chains
longer than 2. The increasing amount in the testing code (+8.57%) is larger
than the one in the non-testing code (+5.37%). On the other hand, themaximum length in the non-testing code is longer than the one in the testingcode. Although there are those differences, the increasing trends and theheavy-tailed distributions can be seen in both code sets. From these results,
we concluded that method chaining is used not only in either code set but
in both sets.

34

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD

100

100

2018
2010

10 2

10 2

10 4

10 4

10 6

10 6

10 8 0
10

101

102

2018
2010

10 8 0
10

103

101

(a) fn of non-testing code
0.30

102

103

(b) fn in testing code

non-test
test

0.25
0.20
0.15
0.10

2018

2017

2016

2015

2014

2013

2012

2011

0.00

2010

0.05

(c) r

Figure 3.6: Non-testing code vs. Testing code
Table 3.1: Groups of Method Chains

Length range# of chains in 2018
# of chains in 2010

3.6

Short

Long

ExtLong

1 < len. ≤ 83,343,781
384,549

8 < len. < 42
19,0841,106

42 ≤ len.
280
27

Categories

To better understand the trends in method chaining, we manually categorized the method chains in 2018 and 2010 by their behaviors (the actionthat a method chain performs). The manual inspection is required since itis hard to automatically categorize a method chain by its behavior.

3.6. CATEGORIES

35// Accessjfc . getCategoryPlot (). getRangeAxis ();miniCluster . getNameNode (). getNamesystem (). getBlockManager (). g etD at an od eM an ag er (). getNumStaleNodes ();histogram . getBuckets (). get (0). getKey ();g e t S u b s c r i p t i o n A t t r i b u t e s (). getIn terest Policy (). isCacheContent ();// Access for operationindex . getLibraries (). add ( libIndex );getS u pp o r t Ac t i on B a r (). s e t D i s p l a y S h o w T i t l e E n a b l e d ( false );Accessor. A chain where all methods perform data access except for thelast method. Although a chain in this category violates the law of Demeter [43], it frequently appears in the real world code.
Figure 3.7: Accessor chains

For this analysis, we divided the set of method chains into three groups
by their length: Short, Long, and ExtLong. Table 3.1 shows the rangeof lengths and the number of chains for each group. We chose the borderlength 8 and 42 in consideration of un values, the ratio of repositories that
contain one or more method chains whose length is longer than or equal
to n. In 2018, more than 50% of repositories contain chains longer than 8,
and less than 5% of repositories contain chains longer than 42, as shown infig. 3.5.
Since it is not feasible to manually inspect all the chains in Short andLong, we analyze randomly-sampled 280 method chains in each of thosegroups. We analyze all the chains in ExtLong.
We categorized a method chain into either of Accessor, Builder, Assertion, and Others. Figure 3.7, fig. 3.8, and fig. 3.9 describe the first
three of them by example. Others is the category for chains that do notmatch any of Accessor, Builder, and Assertion.
Figure 3.10 illustrates the ratios of each category in Short and Long.
The black bars in the figure indicate the margin of errors due to the samplingat a 95% level of confidence. Since we did not find any Accessor chain in
the samples of Long, no blue bars are drawn in Long. The error bar for

36

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD// java . lang . StringBuilder
sb . append ( " New " ). append ( kindName ). append ( " Array " );// com . google . common . base . MoreObjects
MoreObjects . toStringHelper ( this ). add ( " iLine " , iLine ). add ( " lastK " , lastK ). add ( " spacesPending " , spacesPending ). add ( " newlinesPending " , newlinesPending ). add ( " blankLines " , blankLines ). add ( " super " , super . toString ()). toString ()Builder. A chain that builds an object. It often ends with the invocationof a method named like buildFoo or toFoo.
Figure 3.8: Builder chains// Mockito
when ( myHttpClient . execute ( capt . capture ())). thenReturn ( myHttpResponse );verify ( map ). containsKey ( " testOk " );// AssertJ
assertThat ( kunaTimeTicker . getTicker ()). isNotNull ();Assertions. assertThat ( actualObj . has ( " outline_colors " )). isTrue ();Assertion. A chain that describes expected behaviors of an object. Understandably, such chains are written in test code. We found usages of thetwo libraries Mockito and AssertJ in the sampled set for this category.
Figure 3.9: Assertion chains3.6. CATEGORIES

0.8
0.6

37

2018

2010

Accessor
BuilderAssertion
Others

2010
2018

0.4

2010
2018

0.2
2010
0.0

2018 20102018
2010

Short

2018

2018

2010
Long

Figure 3.10: Constitution ratio of each category

Assertion in Long in 2010 is not drawn since the number of chains is too
low to compute its valid margin. All the chains in ExtLong are categorized
into Builder in both 2010 and 2018.
Figure 3.10 shows that approximately 80% of chains in Short are categorized into Accessor in 2010. In 2018, the ratio of Accessor decreases
to approximately 55%, and the ratios of Builder and Assertion increase
accordingly. These changes in the ratios could be explained by the general
acceptance of fluent interfaces, API design that encourages its users to chain
method invocations [20, 32]. An Accessor chain can be composed evenwhen the library is not fluent. On the other hand, a Builder/Assertion
chain needs a fluent interface to compose. In Java, object building andassertions are used to be written in the non-chaining style as follows:// new Builder (). setFoo (" a "). setBar (" b "). build ();Builder b = new Builder ();b . setFoo ( " a " );b . setBar ( " b " );Object o = b . build ();// assertThat ( list ). contains (" a "). contains (" b ");assert list . contains ( " a " );assert list . contains ( " b " );Thus, the increase in the ratio of Builder/Assertion chains indicates

38

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD

the increasing use of fluent interfaces. The same trends can be seen in thechanges in Long. The ratio of Others considerably decreases as the useof Builder and Assertion chains increases. The increasing use of fluent
interfaces is supportive evidence for the wide acceptance of method chaining.
Although we expected to frequently encounter the use of the Stream
API in Others, we found only two such chains (0.71%) in Short andthree chains (1.07%) in Long in 2018. We found no Stream API usages in2010 as the API is not yet introduced into Java in 2010.

3.7

Extremely Long Chains

Since we did not immediately see why and how such long chains exist in thereal-world code, we conducted further inspection of the chains in ExtLong
in 2018.

How much of the ExtLong chains are in testing code?
We found 140 chains (50% of ExtLong) in testing code. As mentioned
above, all the chains in ExtLong are composed to build an object. Thus,
half of the ExtLong chains build objects for testing.

Are the ExtLong chains machine-generated?
We found only five generated chains (1.79% of ExtLong). All of thosechains are generated by aws-java-sdk-code-generator. Most chains in
ExtLong are very likely to be written by human programmers, as far as
we can see from the git history.

Which libraries produce the ExtLong chains?
To answer this question, we checked the package name of the first method
invocation of each chain. We found 71 different package names, which indicates that various libraries are used to compose extremely long chains.
However, a large bias exists in the number of appearances of each library:
53.5% of the libraries are used only once; three libraries constitute 43.9% of
the appearances. The following summarizes the most-used three libraries:
Elasticsearch4 We found 75 chains (26.8%) using XContentFactoryor XContentBuilder in this library. Those classes are for building data
4

https://github.com/elastic/elasticsearch3.7. EXTREMELY LONG CHAINS

39

used in Elasticsearch, which is a distributed search and data-analytics
engine.
Guava5 We found 30 chains (10.7%) using immutable collection builders(e.g., ImmutableSet.Builder and ImmutableList.Builder) in thislibrary.
Java Std. Lib. We found 18 chains (6.43%) using StringBuilder
or StringBuffer in java.lang, both of which represent a mutablesequences of characters in Java.

Are the ExtLong chains styled nicely?
To improve the readability of extremely long chains, programmers often
introduce semantical indentations as follows:6
String jsonString = new PrettyJSON (). array (). object (). key ( " method " ) . value ( " POST " ). key ( " to " ). value ( " ... " ). key ( " body " ). object (). key ( " key " ). value ( " ID " ). key ( " value " ). value ( " fra " )... # Our comment : Omitted. endObject (). key ( " id " ). value (0). endObject ()... # Our comment : Omitted. endArray (). toString ();Another technique is to insert empty lines and comments to group semantically related part as follows:7
return new SpacingBuilder (settings , Ba llerin aLangu age . INSTANCE )5https://github.com/google/guava
https://github.com/neo4j/neo4j/blob/a43b26fac61c59da813ec9302a24dd86f6657537/co
mmunity/server/src/test/java/org/neo4j/server/rest/BatchOperationIT.java#L501
7
https://github.com/ballerina-platform/ballerina-lang/blob/27292e84b9f661da89b6c
66840802f2196decb0d/tool-plugins/intellij/src/main/java/io/ballerina/plugins/idea/for
matter/BallerinaFormattingModelBuilder.java#L328
6

40

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD// Keywords. around ( IMPORT ). spaceIf ( true ). around ( AS ). spaceIf ( true ). around ( CHECK ). spaceIf ( true )# Our comment : Empty line for segmentation. around ( ABORTED ). spaceIf ( true ). around ( COMMITTED ). spaceIf ( true ). around ( LISTENER ). spaceIf ( true )... # Our comment : Omitted

We counted the number of chains that are styled nicely as shown above.
Our inspection revealed that 184 chains are nicely-styled, which is 66.9% ofhandwritten chains.

3.8

Threats to Validity

Internal Validity
The validity of ratios shown in section 3.6 and section 3.7 highly depends on
our manual inspection of method chains. To openly discuss the validity, we
made our results of the inspection publicly available at Zenodo, a generalpurpose open-access repository. The details on the publicly-available data
is provided at the end of this chapter.

External Validity
We did not apply any filter (e.g. filter by project domains) to the collected
repositories. This supports the generalizability of our results. However,
the trends in other languages would be different especially when a language
provides special constructs to build a domain-specific language (DSL). Since
method chaining is often regarded as a technique to design a DSL embedded
in a host language, method chaining may not be used if the language provides
such special constructs (e.g., the literature [14, 36]). Our results are more
likely to be applied to a language that does not provide such a construct(e.g. PHP and JavaScript). The empirical study of this hypothesis is importfuture work.

3.9

Related Work

Heavy-tailed distributions are found in a number of source code measures[44, 45, 79, 82, 35, 30, 11, 51]. For example, the study [30] shows that such

3.9. RELATED WORK

41

distributions are found in the lexical properties of source code such as thenumber of lines and changed lines. The studies [45, 79] show that they arefound in the structural properties such as the number of subclasses and thein-degree and out-degree in dependency networks. The paper [44] says
if one were to analyze the distribution of another measure ofsoftware, it would be most surprising to find it not following a
power law or other heavy-tailed distribution.
However, none of those empirical results can describe the power-law distribution we observed in the number of method chains.
While a number of power-law distributions have been reported, the generation model of those distributions is less studied. Turnu et al. proposeda modified Yule process to model the evolution of object-oriented systemproperties [79]. Lin and Whitehead proposed a model based on preferential
attachment and self-organized criticality [44]. The model proposal for thenumber of method chains is future work that is needed to deeply understandmethod chaining.
The use of language features is often empirically studied. In Java, theuse of generics [15, 62], lambda expressions [48], annotations [15], and castoperators [47] has been studied. In the study on lambda expressions [48],Mazinanian et al. investigated not only the use in the real-world code but
also the reason by interviewing the authors of the source code. Such a study
would be beneficial to better understand the advantages and disadvantagesof method chaining. In the literature [76], Tanaka et al. analyze the use of
method chaining from the view point of functional idioms in Java.
The study [33] empirically shows that the violation of the law of Demeterhas a negative impact on software quality. As pointed out in the Stackoverflow thread [60], chaining method invocations violates the law in most cases.
Considering these facts, our results imply that real-world software increasingly becomes error-prone. However, method chaining is said to cooperate
well with method completion systems in IDEs and let programmers write
code easily and quickly [83, 56]. Further research needs to be carried outthat inspects problems and merits in method chaining for the future development of language features and static analyzers addressing those problems.
High development cost is a well-known drawback of a fluent interface [7].
The cost becomes significantly higher when the developers choose to implement typed chaining [22] since a number of class definitions are required toachieve typed chaining. The tools and techniques proposed in the paper [5,9, 83, 28, 42, 56, 29] help library developers to create a fluent interface
instantly from grammar definitions of method chains.

42

CHAPTER 3. METHOD CHAINING IN THE REAL WORLD
Table 3.2: Materials published at Zenodo

File name

Description

data.txt
metadata.txt
rq1 short 2010.md
rq1 short 2018.md
rq1 long 2010.md
rq1 long 2018.md
rq1 extlong 2010.md
rq1 extlong 2018.md
rq1 2010.csv
rq1 2018.csv

List of all the collected chains
List of files and the number of lines for each file
Short chains (2010)
Short chains (2018)
Long chains (2010)
Long chains (2018)
ExtLong chains sampled (2010)
ExtLong chains sampled (2018)
Result of our manual inspections (2010)
Result of our manual inspections (2018)

3.10

SummaryThis chapter presented our empirical study of method chaining in Java.
Our analysis quantitatively revealed the widespread and increasing trend of
method chaining, which indicates the potential demands of fluent interfaces.
The collected method chains and the results of our manual inspections
are publicly available as an archive file [54]. Table 3.2 lists the files related
to this chapter in that archive file.

Highlights of Our Results
Method chaining is increasingly used in the real world. In 2018, 23.1% of
method invocations are part of chains longer than 2, while 16.0% are such
invocations in 2010. More than 50% of repositories contain at least one
chain that is longer than seven. Approximately 5% of repositories containchains that are longer than 42. Further, the increase is not caused by a few
repositories that heavily use method chaining.
We also observed the increasing use of fluent interfaces, which is a supportive result for the wide acceptance of method chaining. In 2010, approximately 80% of chains are accessor chains, those that can be composed
without fluent interfaces. The ratio of accessor chains decreased to approximately 55% in 2018, and the ratio of builder/assertion chains – those that
require fluent interfaces to compose – increased accordingly.
All the chains longer than 42 are builder chains. 98.2% of them are very
likely to be handwritten, and 65.7% are styled nicely with indentations,3.10. SUMMARY

43

empty lines, and comments. The variety of such extremely long chains is
unexpectedly wide. We found that 71 packages are used for composing 280
extremely long chains.

Implications
Our results are supportive evidence for the wide acceptance of method chaining in the real world. If method chaining is commonly considered as a badpractice, the use of method chaining would be the same or decreasing. However, to clearly state that method chaining is accepted, user studies need tobe conducted. Such studies are our primary future work.
The above-mentioned implication will motivate the developers of fundamental software such as languages, libraries, and IDEs. It will be a supportive and quantitative ground in the discussion of adding new functions
for method chaining. For example, library developers can claim that adding
fluent interfaces is beneficial for their users; IDE developers can discuss thepriority of supporting breakpoints between method invocations in a chain
and of a code formatting feature for long chains. The answer also motivates
researchers of tools for developing safe fluent interfaces [28, 29, 42, 56, 52,83]. The researchers can quantitatively state that their tools and further
studies on the tools are beneficial for a number of real-world programmers.

44

CHAPTER 3. METHOD CHAINING IN THE REAL WORLDChapter 4

Desirable Language Designs
for Fluent Interfaces
This chapter presents our empirical study of desirable language designs that
support the use of fluent interfaces (i.e., that support method chaining).
Although we aim to present a concrete list of such language designs first andforemost in this study, we also present alternative API designs (the designsof library interfaces). Changing API costs less than changing a language.
We attempt to find language designs for fluent interfaces by investigating
real-world Java code pieces that contain non-chained method invocations.
Specifically, we (1) pick a code piece with non-chained invocations, (2) findpossible reasons why those invocations are not chained, and (3) look for
language designs to transform the piece into the method-chaining style. We
selected Java for this study since its syntax is relatively simple and does notprovide any special language designs for method chaining. Note that thestep (2) and (3) are not always feasible; we could not find clear reasons or
language designs for some code pieces.
The code pieces that we investigate are randomly sampled from thedataset described in the last chapter. We manually analyzed randomlysampled 385 chains and the code around them. Since we are interested inwhy method invocations are not chained and how to support by language
designs, the population of the random sampling was the chains of all lengths(including non-chained invocations) in 2018. Since our analysis process includes reasoning of code pieces, it cannot be done mechanically for all thechains in our dataset.
In the following four sections, we present code patterns that we found in
our analysis with their examples and discuss appropriate language designs
45

46

CHAPTER 4. DESIRABLE LANG DESIGNS FOR FLUENT INTF

or API design for those patterns. In section 4.5, we summarize the statistically estimated ratios of those patterns in the population. Section 4.6 andsection 4.7 discuss the validity of our results and related work, respectively.
We summarize language and API designs that we find in our investigationin section 4.8.

4.1

NullExceptionAvoidance

When a method invocation may return null, a programmer cannot chain
all related method invocations; for example, as follows:1
JAXBMapping mapping = jaxbModel . get ( qname );if ( mapping == null ){return null ;}return mapping . getType (). getTypeAnn ();A NullPointerException may be thrown by get(qname) if one simply
chains all the method invocations get(qname), getType(), and getTypeAnn().
We classified a chain into NullExceptionAvoidance when null-checking
has to be performed on the receiver side of the first invocation in a chain.
We found nine chains (2.34%) of this pattern in the sampled dataset.
The safe call syntax in Kotlin [59] is helpful for this pattern.
return jaxbModel . get ( qname )? // Safe call
. getType (). getTypeAnn ();The code above invokes getType() only when get(qname) returns a nonnull object. With this syntax, a programmer can group semantically related
invocations into a single chain. Furthermore, the following negative opinions
in the thread on StackOverflow [60] can be addressed by introducing the safe
call syntax:
Chaining different objects can also lead to unexpected null errors. ...there’s no guarantee (as an outside developer looking at
the code) that getSchedule will actually return a valid, non-nullschedule object.
Equivalent syntax also exists in Swift [61] and TypeScript [80]. The syntax
is called optional chaining syntax in those languages.
1

https://github.com/corretto/corretto-8/blob/32a35a24e2791bc810a0b4d89ad685c97e
4485fa/src/jaxws/src/share/jaxws classes/com/sun/tools/internal/ws/processor/model
er/wsdl/JAXBModelBuilder.java#L1194.2. REPEATEDRECEIVER

47

Library developers can also provide better user experience by using
Optional<T> for methods that possibly return null. The example codeof this pattern can be transformed into the following if get(qname) returns
Optional<JAXBMapping>:
return jaxbModel. get ( qname ) // returns Optional < JAXBMapping >. map ( qname -> qname . getType (). getTypeAnn ()). orElse ( null );Since all the related invocations are grouped into a chain, the code above
would be easier to understand.

4.2

RepeatedReceiver

Different methods are often invoked on the same object as follows:2
event . getPresentation (). setEnabled ( true );event . getPresentation (). setVisible ( true );This code repeats the expression event.getPresentation(). This repetition is not preferable in terms of code readability. We classified a chain as
RepeatedReceiver when the receiver of the last invocation is the sameas the previous/next chain. We excluded a chain from this pattern if the receiver is this or a class since no code repetition exists in such cases. We also
excluded chains where programmers avoid chaining on purpose; for example
as follows:3// These two statements can be written as a chain ,// however , they are written separately .
// sb : java . lang . StringBuilder
sb . append ( " hasFilter : " );sb . append ( this . hasFilter );In the sampled dataset, we found 33 chains (8.57%) of this pattern.
The method cascading syntax in Smalltalk [3] and Dart [49] is usefulfor removing such repetitions. With this syntax, the example code of thispattern can be written as follows:2

https://github.com/eclipse/che/blob/e4d0f9987db58f3d46a3a727b88e601e84a5749b/ide/che-core-ide-app/src/main/java/org/eclipse/che/ide/processes/actions/StopProcessA
ction.java#L73
3
https://github.com/apache/incubator-pinot/blob/09eb0150dec47a28d5a4517e4930183e
b5dfd0af/pinot-common/src/main/java/com/linkedin/pinot/common/request/Query
Type.java#L567

48

CHAPTER 4. DESIRABLE LANG DESIGNS FOR FLUENT INTF

event . getPresentation (). setEnabled ( true ).. setVisible ( true ); // Dart - style syntax
The repetition of a receiver object can also be removed by setting the return value of setEnabled(...) to this. However, when considering thedescriptive role of return types, some may think that it is not desirable toreturn a value in a method named like setFoo. In that case, it might be agood convention to name a normal setter (returning nothing) as setFoo anda fluent setter (returning this) as withFoo. A notable library using thatnaming convention is TemporaryCredential in AWS SDK4 .

4.3

DownCast

When the invocation of a method needs downcasting, a chain is frequently
split as follows5 to make code easily understandable:
firstBtn = ( Button ) findViewById ( R . id . firstBtn );firstBtn . setText ( START );If a programmer wants to write a single chain for this operation, one needs
to write nested parentheses as follows:(( Button ) findViewById ( R . id . firstBtn )). setText ( START );However, the nested parentheses worsen the readability. We classified achain as DownCast when it contains cast operations. Six chains (1.56%)of this category are found in the sampled dataset.
Providing a method for downcasting relieves the problem in the DownCast chains. The following lines show example usage of the downcasting
methods:// When destination types are practically known
findViewById ( R . id . firstBtn ). asButton (). setText ( START );// When destination types are unknown
findViewById ( R . id . firstBtn ). as ( Button . class ). setText ( START );4

https://github.com/aws/aws-sdk-java/blob/dafccf5a1241b5655c542a45eae05a582c
3225de/aws-java-sdk-opsworks/src/main/java/com/amazonaws/services/opsworks/mo
del/TemporaryCredential.java#L186
5
https://github.com/yaowen369/DownloadHelper/blob/a27944d175cc48ddbe06151db8a
d7cb415e9fa60/sample/src/main/java/com/yaoxiaowen/download/sample/MainActivi
ty.java#L144

4.4. CONDITIONALEXECUTION

49

As seen above, an expression can be read from left to right easily. Although
the solution described here is for library developers, it would be unnecessary
if the top type Object provides the downcasting method as(...). This isa candidate for language extension to Java for supporting method-chaining
style.

4.4

ConditionalExecution

Some methods are invoked only when certain conditions are satisfied; forexample as follows:6
if ( buildLogger . isInfoEnabled ()) {buildLogger . info ( message , throwable );}We classified a chain as ConditionalExecution when it is conditionally
executed as shown above. We found nine chains (2.34%) of this pattern inthe sampled dataset.
The code in this pattern can be transformed into a single chain if thelibrary provides a method that takes a lambda expression as its argument:
buildLogger . ifInfoEnabled (logger -> logger . info ( message , throwable ));This workaround is largely adopted in the JavaParser library, and other Javalibraries could adopt this workaround. Although we could not find syntax
for this pattern in other languages, a syntactic sugar like the following would
be useful for this pattern:// Possible syntactic sugars//( not in any existing languages )buildLogger. isInfoEnabled () = > . info ( message , throwable );buildLogger. isInfoEnabled ()?? . info ( message , throwable );4.5

Estimated Ratios

We statistically estimated the ratio in the population (i.e., whole dataset)from the results obtained from the analysis of the randomly-sampled dataset.
6

https://github.com/raphw/byte-buddy/blob/9364421492e830b883d10d9718d6586480e
35747/byte-buddy-dep/src/main/java/net/bytebuddy/build/BuildLogger.java#L535

50

CHAPTER 4. DESIRABLE LANG DESIGNS FOR FLUENT INTF
Table 4.1: Estimated Ratio of Pattern
PatternRatio

c = 95%c = 99%NullExceptionAvoidance
RepeatedReceiver
DownCast
ConditionalExecution

2.34%
8.57%
1.56%
2.34%

±1.51%±2.80%±1.24%±1.51%±1.98%±3.67%±1.98%

14.8%±3.55%±4.66%

Table 4.1 summarizes the estimated ratios. The columns “c = n%” show
margins of errors at n% level of confidence. We put the symbol “-” when
the ratio in the sampled dataset is too low to compute the valid margin oferrors at that level of confidence. The last row of the table shows the values
for the sum of those discovered patterns.
As shown in the table, approximately 15% of chains can be combined intoa single chain with other invocations around that chain if the appropriate
language designs or API design are provided. We counted the number ofchains conservatively. For example, we did not classify the following chain
as NullExceptionAvoidance:
JAXBMapping mapping = jaxbModel . get ( qname );updateFoo (); // Possibly changes states
if ( mapping == null ){return null ;}return mapping . getType (). getTypeAnn ();By exchanging the first and second statements, the above code can be transformed into a single chain if the safe call syntax is available. However, thisexchange possibly changes the semantics of the code, so we did not countsuch code for NullExceptionAvoidance. This conservative counting implies that the real ratios might be larger than the values shown in the table.

4.6

Threats to Validity

The internal validity of our results (shown in section 4.5) highly depends on
our manual inspection of method chains. To publicly discuss the validity,
we made our results of the inspection available at Zenodo (see table 4.2 atthe end of this chapter for more details). The external validity is the same

4.7. RELATED WORK51

as the one in the last chapter (section 3.8) since the dataset we use in thischapter is the same as the one used in the last chapter.

4.7

Related Work

There are more features that help programmers to chain method invocations
although only a small number of languages provide those features. D [23]and Nim [63] have the uniform function call syntax, which allows chaining
the invocation not only of methods but also functions. The scope functions
in Kotlin [72] can be used to compose a chain with conditional statements
and loops without storing an intermediate state into a temporary variable.
Class-extension mechanisms without inheritance help programmers to
use a fluent library to mitigate the extensibility problem pointed out in theblog posts [7, 65]. Assume that we provide the library for counting numbers
implemented as follows:class Counter {n = 0;Counter increment () { n ++; return this ; }}The user of this library can count up a number by chaining the method callincrement(). Suppose that the user need to add the method decrement()
to this library. Programmers would use inheritance, a feature implemented
in most object-oriented languages, to extend existing code:class ExtCounter extends Counter {ExtCounter decrement () { n - -; return this ; }}However, this approach does not work as expected since increment() returns an instance of Counter:
new ExtCounter (). increment () // Returns Counter. decrement (); // Method not found !
The user can avoid this problem by overwriting the existing methods in
Counter, but it is too tedious to overwrite all the existing methods whena given library provides tens of methods. With class-extension mechanisms
provided in Swift [19] and Kotlin [18], the user can add decrement() as
expected.

52

CHAPTER 4. DESIRABLE LANG DESIGNS FOR FLUENT INTF
Table 4.2: Materials published at Zenodo

4.8

File name

Description

rq2.mdrq2.csv

Sampled chains for manual inspection
Result of our manual inspections

Summary

We found four code patterns that disturb programmers to chain more method
invocations and listed language designs that eliminate the disturbers. Somereaders might think it is obvious that those designs are useful for method
chaining. However, what is important in our study is that our analyses quantitatively revealed how effective they are if adopted. Out results shows thatat least 10% of non-chained invocations can be transformed into a chain.
This quantitative result will be a basis for the design decision when adding
those features or adopting the library design.
The results of our manual inspections in this chapter are publicly available at Zenodo [54] as an archive file. Table 4.2 describes the files related tothis chapter in that archive file.

Highlights of Our Results
Language designers can effectively save the development effort of their users
by implementing the safe call syntax and method cascading syntax. The
users can write compact code by chaining method invocations with such
syntax. In Java, which is a language that does not support the syntax,
approximately 10% of chains suffer from null-checking and writing receiverobjects repeatedly.
The following summarizes best practices that we propose for Java librarydevelopers:• Return Optional<T> when a method may return null.
• When creating a method returning a boolean value such as isFoo(),create the method ifFoo(...) that takes lambda expressions.
• When creating a setter method such as setFoo(...), return this inthat method instead of returning nothing.
• When creating a public non-final class, provide methods for downcasting such as as(...).

4.8. SUMMARY

53Tool developers can save these efforts of library developers by creating code
generators for the boilerplate code.

54

CHAPTER 4. DESIRABLE LANG DESIGNS FOR FLUENT INTF

Chapter 5Generating Generic
Fluent Interfaces
In this chapter, we present a code-generation technique of generic fluent
interfaces. As we discussed in chapter 1, the support for generics is indispensable to use the generative approach in the real world since the use oftype parameters is common in real-world library development.
We first illustrate the problem of existing code-generation algorithms by
example in section 5.1. We then overview our technique and its demonstration tool named Protocool in section 5.2. The detailed description of
our technique follows the overview from section 5.2.1 to section 5.2.4. To
evaluate our technique, we generated several generic fluent interfaces anddiscuss their use cases. We also measured the number of generated lines
using our demonstration tool. The results of our evaluation are discussed
in section 5.3.1 and section 5.3.2. Section 5.4 summarizes this chapter andbriefly discusses future work.

5.1

Problem of Existing Algorithms

Consider creating a generic fluent interface for constructing an instance of
Map<K, V> in Java. Our example API allows its users to construct a map
with any key/value type by chaining the method invocations, as follows:
Map < Integer , String > map= OurAPI . newMap (). put (1 , " foo " ) // Associate " foo " with key 1. put (2 , " bar " ) // Associate " bar " with key 2. build ();55

56

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

In our API, the key and value types are inferred from the types of theargument provided to the first invocation of put(...) in the chain. Users
cannot create an entry with an inconsistent key/value type. A type error isreported if such an entry is created:
OurAPI . newMap (). put (1 , " foo " ) // key : Integer , value : String. put ( " bar " , 2) // key : String , value : Integer// = > Type error !
. build ();Our API also has syntactical rules regarding the order of the method
invocations in a chain. Users first need to invoke newMap() to begin a map
construction. Thereafter, they can create entries by chaining an arbitrary
number of put(...). They need to invoke build() to complete the construction and obtain an instance of Map<K, V>. The syntax described above
can be summarized as follows, in the form of a regular expression:
newMap()put(K key, V value) ∗ build()

The asterisk denotes zero or more occurrences of the preceding element. K
and V are type parameters that represent the key and value types, respectively.
Consider reporting the violation to the syntax as a type error so thatusers can identify their misuse at compile-time. This safe property can beachieved by setting the return type of each API method based on what theusers can chain next. For example, a duplicate invocation of newMap() canbe prevented by setting the return type of newMap() to a class providing
only put(...):
OurAPI . newMap ()// Returns a type//that provides only ` put (...) `. newMap (); // This line causes a type error ;//Cannot resolve method ' newMap 'It is known that such a safe property can be achieved by: (1) building
a state machine that accepts only a syntactically correct method sequence,and (2) encoding the machine into Java class definitions [5, 28, 83]. Recall
that the syntax of our API is expressed by a regular expression. Therefore, a
DFA is capable of recognizing the syntax. Figure 5.1 illustrates the DFA that
accepts method sequences conforming to the syntax. The left-most state in
the figure is the initial state of the DFA. The double circle represents an5.1. PROBLEM OF EXISTING ALGORITHMS

0

newMap()1

build()

57

2

put(K key, V value)
Figure 5.1: DFA that accepts correct method sequences of OurAPI
accepting state. The number in each state is simply an index of the state
for later references.
A problem arises when encoding the DFA into class definitions. According to the previous studies [5, 28, 83], we obtain the class definitions byencoding each state into a class, and encoding each transition into a method.
Consider encoding the loop transition consuming put(...) into a method.
A naive idea is to encode it into the following:// Corresponds to the state 1 in the diagram
class State1 <K , V > {State1 put ( K key , V value ) { /* method body */ }...
}Unfortunately, this encoding does not generate our example API as expected. In this encoding, all invocations of put(...) refer to types that arebound to the type parameters K and V. However, no invocations of put(...)
bind the argument types to K or V. The type parameters are never bound to
types. Thus, the API generated by this encoding is broken.
Another idea is to encode the loop transition as follows:class State1 {<K , V > State1 put ( K key , V value ) { ... }...
}Using this encoding, an invocation of put(...) binds the argument types toK and V. However, this encoding does not generate our example API either.
In this encoding, K and V are bound at every invocation of put(...). As no
invocations refer to a previously bound type, the map entry types becomeinconsistent. The users of the generated API can put any type of item into
the map.
The problem is that, in the state machine naively constructed from syntactical rules, it is not clear which type parameters are already bound in eachstate. A type parameter in a method chain is bound at the first method

58

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

invocation that uses the type parameter. The successive method invocations refer to that bound type. In our API, the type parameters K and V arebound to the argument types provided to the first invocation of put(...).
Successive invocations of put(...) refer to those bound types for theirarguments.
The binding rule of a type parameter in a chain is not specific to ourAPI. For example, the type parameter in the Stream API is bound to a
type, as described above:
Stream. of ( " a " , " aa " , " aaa " )// Bind String to T of Stream <T >. filter ( s -> s . length () > 1)// Refer to the bound type (= String ). forEach ( s -> System . out . println ( s ));// Refer to the bound type (= String )To generate a generic fluent interface correctly, an algorithm needs to construct a state machine that knows which type parameters are bound in eachstate. If the bound type parameters in each state are clear, the encoding
algorithm can identify whether or not a generated method newly binds types
to type parameters.

5.2

Our Code-generation Technique

To address the problem discussed in the previous section, we have developed
a code-generation technique that correctly handles type parameters in afluent interface. As described in chapter 1, the code generation of fluent
interfaces is the translation from a grammar into class definitions. In thetranslation, a grammar is first converted into a state machine that accepts
sequences derived from the grammar, and the machine is encoded into classdefinitions for fluent interfaces. Although our technique also follows thisprocess, it constructs a special DFA for generics support.
Our technique is implemented as a demonstration tool named Protocool, and we describe our technique as the process implemented in Protocool. Although the core contribution is the development of an algorithm for the binding-time analysis of type parameters, which we explain
in section 5.2.2, we describe all parts from the start for readers to better
understand the core contribution.
Protocool receives the API specification written in Java-like syntax.
Figure 5.2 illustrates the specification of OurAPI, which is the example API

5.2. OUR CODE-GENERATION TECHNIQUE

59

1 class OurAPI {2// Defines syntax
3static Map <K ,V > newMap () put ( K key , V value )* build ();4// Define type parameters for this class
5
K; V;
6 }
Figure 5.2: Specification of OurAPI
newMap()build()

Map<K, V>

K, V

K, V

build()

put(K key, V value)put(K key, V value)

Figure 5.3: DFA constructed from class declaration in fig. 5.2
described in the previous section. The statement on line 3 in fig. 5.2 isa chain declaration, which defines the syntactically correct chaining of the
API methods. The keyword static merely indicates that the first methodof a chain is a static method. The generated API is used as follows if weremove static:// " new OurAPI (). newMap ()"//instead of " OurAPI . newMap ()"Map < Integer , String > map= new OurAPI (). newMap (). put (1 , " foo " ). build ();The statements on line 5 declare the type parameters used in the API.
According to the given specification, Protocool constructs a DFA in
which each state is annotated with the type parameters bound in that state.
Figure 5.3 illustrates the DFA constructed by Protocool from the specification in fig. 5.2. The symbols indicated inside a state circle are the typeparameters bound in that state. The DFA consumes a method or type ateach step. It reaches an accepting state by consuming the method sequence
defined in the chain declaration, and then by consuming the return type. A
transition consuming a type identifies which type is instantiated by chaining
methods. The construction of such a DFA consists of two steps. The firststep is the naive construction of a DFA from the given syntactical rules. The
second step is the modification of the naively constructed DFA. These two

60
1
2
3
4
5
6
7
8
9
10
11
12
13
14

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES// Corresponds to the initial stateclass OurAPI {static State1 newMap () { . . . }}// Corresponds to the second state from the leftclass State1 {<K , V > State2 <K , V > put ( K key , V value ) { . . . }<K , V > Map <K , V > build () { . . . }}// Corresponds to the third state from the leftclass State2 <K , V > {State2 <K , V > put ( K key , V value ) { . . . }Map <K , V > build () { . . . }}Figure 5.4: Class definitions generated from DFA in fig. 5.3

steps for constructing a DFA are described in section 5.2.1 and section 5.2.2.
Protocool generates a safe fluent interface by encoding the constructed
DFA into Java class definitions. Figure 5.4 illustrates the class definitions
generated from the DFA in fig. 5.3. A state is encoded into a class if thestate does not have a transition consuming a type and the state is not an
accepting state. In fig. 5.3, only those states colored with red are encoded
into classes, as the others have a type-consuming transition or are an accepting state. The initial state is encoded into a class with the same nameas the class declaration. In our example, the initial state is encoded into aclass named OurAPI, as indicated on line 2 in fig. 5.4. Other states are encoded into classes named, for example, StateN. A transition is encoded intoa method if the transition consumes a method. The return type of a method
depends on the destination state of the original transition. If the destination
state includes a type-consuming transition, the return type is that consumed
type. In our example, the return type of build() is Map<K, V>, as indicatedon line 8 and line 13. Otherwise, the return type is the class corresponding
to the destination state. The generated method includes its type parameter
declaration when the type parameters bound in the source state differ fromthose that are bound in the destination state. Note that, if no put(...) is
invoked in a chain, K and V are inferred from the type information outsideof the chain. For example, if the return value of OurAP.newMap().build()

5.2. OUR CODE-GENERATION TECHNIQUE
s1,1
..
.

sn,1

s1,2
..
.

sn,2

···

···

61

s1,l1
sn,ln

r1
..
.

rn

..
.

(a) Set of chain automata

s1,1

sn,1

s1,2
..
.

sn,2

···

···

s1,l1
sn,ln

r1
..
.

rn

(b) NFA

Figure 5.5: NFA construction
is assigned to a variable, K and V are inferred from the type of that variable:// K and V are bound to Integer and String
Map < Integer , String > m = OurAP . newMap (). build ();5.2.1

DFA Construction

Suppose that a given specification has the following class declaration:
class c {r1 s1,1 s1,2 . . . s1,l1 ;... ;rn sn,2 sn,2 . . . sn,ln ;}Here, c is a class name, ri is a return type, and si,j is a method signature.
In fig. 5.2, OurAPI is c, Map<K,V> is r1 , newMap() is s1,1 , put(K key, V
value) is s1,2 , and build() is s1,3 . Note that c, ri , and si,j include typeparameters. For instance, r1 corresponds to Map<K,V> on line 3 in fig. 5.2,
not only Map. Later in section 5.2.2, we define a function π(si,j ) that retrieves
the set of type parameters appearing in si,j . We omit static and typeparameter declarations (line 5 in fig. 5.2) since they are irrelevant to our
DFA construction. The keyword static only indicates that the first methodof a chain should be a static method, and type parameter declarations is todistinguish type parameter names (e.g., K and V) from type names (e.g.,

62

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

OurAPI and Map). We also omit regular-expression operators such as * here.
The support for those operators are discussed at the end of this sub-section.
Protocool first constructs a non-deterministic finite-state automaton(NFA) from the class declaration. It achieves this by combining a set of chain
automata, each of which is constructed from a chain declaration. A chain
automaton reaches an accepting state by consuming the method sequence ofits corresponding chain declaration, and then by consuming the return type.
Figure 5.5a illustrates the set of chain automata obtained from the above
class declaration. Our algorithm constructs the NFA presented in fig. 5.5bby merging the initial states and accepting states of the chain automata in
fig. 5.5a. Such an NFA is always constructed successfully from a given classdeclaration.
Protocool then converts the constructed NFA into a DFA using Brzozowski’s algorithm [6]. To judge the equality between two transitions,
our algorithm uses the function that takes two transitions as its input andreturns a boolean value, as follows:• returns true if both transitions consume methods and have the same
signature;• returns true if both transitions consume the same type; and• returns false otherwise.
This conversion is necessary to generate a valid Java class definition, as
non-determinism produces duplicate method definitions in a class. The conversion always succeeds because any NFA can be converted into a DFA.
The use of regular-expression operators in a input grammar can be supported by using Thompson’s algorithm [78] to construct a chain automaton.
Although a chain automaton constructed by the algorithm may not be deterministic, Protocool still can obtain a DFA from a NFA that is constructedby merging chain automata.

5.2.2

Binding-time Analysis

Protocool finally analyzes the binding times of the type parameters todetermine which type parameters are already bound in a state. It incrementally assigns a set of type parameters to each state of the DFA, and modifies
the DFA constructed at the previous step during the analysis if necessary.
The modification of the DFA is essential to successfully encode a DFA
into class definitions with type parameters. Without the modification, theencoding of the DFA causes problems discussed in section 5.1.

5.2. OUR CODE-GENERATION TECHNIQUE∅

newMap()build()

63

Map<K, V>put(K key, V value)(a) Assign empty set to initial state∅

newMap()∅build()

Map<K, V>put(K key, V value)(b) Assign empty set to second statebuild()∅

newMap()∅put(K key, V value)build()
put(K key, V value)

Map<K, V>(c) Clone second statebuild()∅

newMap()∅

Map<K, V>build()
put(K key, V value)put(K key, V value)(d) Change loop transition destination

Figure 5.6: Incremental assignment of type parameters

The algorithm for our binding time analysis can be described as follows.
The algorithm first assigns the set of type parameters appearing in the classname to the initial state. In the example case, it assigns an empty set ∅ tothe initial state, as illustrated in fig. 5.6a, because OurAPI does not have any
type parameters in its name. Suppose that a set of type parameters Pi issalready assigned to a state qi , and qi includes a transition t : qi →− qj . If any
set has not been assigned to qj , our algorithm assigns Pi ∪ π(s) to qj , whereπ(s) is a function to retrieve the set of type parameters appearing in s. In
the example case, the algorithm assigns ∅ to the second state, as illustrated
in fig. 5.6b, because no set is yet assigned to the second state. If a set of

64

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

Algorithm 5.1 Binding time analysis of type parameters
Input: A DFA D
Output: A DFA with type parameter information
1: Q ← An empty queue
2: q0 ← The initial state of D
3: Assign the set of type parameters of the declared class to q0
4: Enqueue all transitions outgoing from q0 to Q
5: while Q is not empty dos− qj ) ← Dequeue from Q
6:(t : qi →7:
if s is a method then8:
Pi ← The set assigned to qi
9:
if No set is assigned to qj then10:
Assign Pi ∪ π(s) to qj
11:
Enqueue all transitions outgoing from qj to Q
12:
else
13:
Pj ← The set assigned to qj
14:
if Pj 6= Pi ∪ π(s) then15:
if π(s) = ∅ then16:
Assign Pi ∪ π(s) to qj
17:
else
18:
qj0 ← γ(qj , D)
19:
Assign Pi ∪ π(s) to qj0
20:
Change the destination of t to qj0
21:
Enqueue all transitions outgoing from qj0 to Q

type parameters Pj has already been assigned to qj and Pj 6= Pi ∪ π(s), ouralgorithm changes the destination of t to a state qj0 and assigns Pi ∪ π(s)to qj0 . Here, qj0 is a newly added state that is obtained by cloning (copying
a state including the transitions outgoing from that state) qj . The cloned
state qj0 has the same set of transitions as that of qj . Figure 5.6c and fig. 5.6d
illustrate the cloning process in our example case. The algorithm continues
to assign the bound type parameters to a state until all states are annotatedwith their bound type parameters.
Algorithm 5.1 presents the pseudo-code of our algorithm. It takes a
DFA D as its input and emits a modified DFA as its output. The function
γ(q, D) on line 18 is the function that clones a state q (in a DFA D) andthe transitions outgoing from q. The red state in fig. 5.6c is the state madeby the function gamma, which is cloned from the second state on the left

5.2. OUR CODE-GENERATION TECHNIQUE

65

Object Map
Method newMap Method put Method put Method build
1 "foo"2 "bar"Figure 5.7: Tree construction in generated libraryof the red state. Because the cloning process does not add a transition,but only changes its destination, the modified automaton is still finite anddeterministic. The binding time analysis does not repeat infinitely. Onlya finite number of type parameters exist in a class declaration. A state ismapped to a subset of the set of those type parameters. Therefore, thenumber of states is also finite.

5.2.3

Bodies of Generated Methods

Protocool generates method bodies, not only source code for library interfaces, as do the existing fluent interface generators [29, 84]. The generation of
method bodies helps generator users to implement the actions of a generated
API. Without the body generation, users need to deal with the laborious
task of restoring previously implemented actions when they regenerate their
API to update the API specification. This problem in code-regeneration
is well-kown and the separation of generated code and handwritten code is
known as the pattern called generation gap [21].
The generated method bodies construct a tree that represents a method
chain composed by the API user. For example, the tree illustrated in fig. 5.7
can be constructed from the following chain:
OurAPI . newMap (). put (1 , " foo " ). put (2 , " bar " ). build ();Each node of the tree represents either an object construction or a method
invocation. In fig. 5.7, the root node Object Map represents an object construction, while the child nodes such as Method newMap represent a method
invocation. The child nodes of an object construction node are method invocation nodes, each of which represents a method that is invoked to construct
the object. The child nodes of a method invocation node are the arguments
passed to that method.
Library developers (that is, Protocool users) can access the tree byspecifying a tree evaluator through a return clause; for example, as follows:

66

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

1 class Evaluator {2static <K , V > Map <K , V > buildMap (3
Object_Map <K , V > node ) {4
BuildMapVisitor <K , V > visitor
5= new BuildMapVisitor <K , V >();
6
visitor . visit ( node );7
return visitor . map ;8}
9 }Figure 5.8: Handwritten evaluator implementation
1 class BuildMapVisitor <K , V > extends Visitor {2
Map <K , V > map = new HashMap ();3
void visitMethod_put ( Method_put <K , V > node ) {4
map . put ( node . key , node . value );5}
6void visitObject_Map ( Object_Map <K , V > node ) {7super . v i s i t C o n s t r u c t i o n _ L a y e r ( node );8}
9void v is it Me th od _n ew Ma p ( Method_newMap node ) {}10
void vi sitMet hod_bu ild ( Method_build node ) {}11 }Figure 5.9: Handwritten visitor implementation

class OurAPI {static Map <K , V >newMap () put ( K key , V value )* build ()return Evaluator . buildMap ;K; V;}In this case, Evaluator.buildMap is a static method defined by hand outsideof the generated code. The constructed tree is passed to the static method
placed after the keyword return:Map <K , V > build () {// Create and store a new method node

5.2. OUR CODE-GENERATION TECHNIQUE

67

Method_build method_build = new Method_build ();...
// Create a new object construction node
Object_Map <K , V > object_map = new Object_Map <K , V >();...
// Pass the tree to the evaluator method//
and return the return value of the evaluator
return Evaluator . buildMap ( object_map );}Using this design, library developers can implement the actions of the generated API separately from the generated code. The generated tree nodes
support the visitor pattern. Figure 5.8 and fig. 5.9 present example implementations of the actions that construct a HashMap<K, V> instance using
the visitor pattern.

5.2.4

Specification Validation

Protocool throws an error and does not generate Java class definitions
when it detects that a state with a type-consuming transition also has another transition. This is because the specification producing such a DFA
cannot be translated into valid Java class definitions, or the specification istranslated into unexpected Java classes. In the following, we describe thetwo cases where Protocool throws an error along with the reasons forsuch behaviors.
Multiple Type-consuming Transitions
Figure 5.10a presents an example specification that produces a state withmultiple type-consuming transitions. The specification states that the usersof the generated API can write both of the following:
List < String > list = Collection . of ( " foo " ). create ();Set < String > set = Collection . of ( " bar " ). create ();Figure 5.10b illustrates the DFA constructed from the specification presented in fig. 5.10a. The state colored in red has two transitions that consume types.
Although Protocool can construct a DFA from the specification in
fig. 5.10a, this DFA cannot be translated into valid Java classes. The second
state is encoded into the following Java class:

68

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES
class S i ng l e to n C ol l e ct i o n {static List <E > of ( E elem ) build ();static Set <E > of ( E elem ) build ();E;}(a) Specification

List<E>of(E elem)build()
Set<E>(b) DFA

Figure 5.10: Invalid spec. with multiple type-consuming transitionsclass State1 <E > {List <E > build () { ... }Set <E > build () { ... }}In Java, methods with the same signature must return the same type. Therefore, the class definition above is invalid Java code. Protocool throws anerror not to generate a broken API. Note that this error is due to the incompatibility between the given specification and the Java type system, notto our DFA-construction method.
Type-consuming and Method-consuming Transitions
Figure 5.11a presents an example specification that produces a state withboth type-consuming and method-consuming transitions. It states that theusers can write the following:
Map < String , String > map = StrMapBuilder. newMap (). add ( " foo " , " bar " ). add ( " bar " , " baz " );Figure 5.11b illustrates the DFA constructed from the specification presented in fig. 5.11a. The state colored in red has both type-consuming andmethod-consuming transitions.
Although a DFA can be constructed by Protocool, the encoding of
this DFA is problematic. The initial state is encoded into the following

5.3. EVALUATION

69

class StrMapBuilder {static Map < String , String >newMap () add ( String k , String v )*;}(a) Specification

add(String k, String v)
newMap()
Map<String, String>(b) DFA

Figure 5.11: Invalid spec. with type- and method-consuming transitionsclass, as the destination of the build() transition has a type-consuming
transition:
class StrMapBuilder {static Map < String , String > newMap ();}However, the users of the generated API cannot chain the method add(...),
because Map<String, String> in Java does not provide add(...):
Map < String , String > map = StrMapBuilder. newMap () // Returns Map < String , String >. add ( " foo " , " bar " ); // Type error !
// Cannot resolve method ' add 'Protocool throws an error and do not generate code to prevent the generated API from being an unexpected API. Note that, if the output language
provides a mechanism to extend existing classes (e.g., the mechanism provided in Kotlin [18] and Swift [19]), this problem can be addressed, andProtocool does not need to throw an error to this case.

5.3

Evaluation

5.3.1

Use Cases

In this section, we illustrate the ability and limitations, as well as several
features that are introduced for the practical applicability of Protocool,through the generation of three example APIs.

70

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES< spec >→ < class >+ ;< class >→ < class - head > < class - body > ;< class - head >→ " class " NAME < type - param - list >? ;< type - param - list >→ " <" < type - param > ( " ," < type - param > )* " >" ;< class - body >→ "{" < chain - or - type - param >* "}" ;< chain - or - type - param >→ ( < chain > | < type - param > ) ";" ;< type - param >→ NAME < type - param - bound >? ;< type - param - bound >→ " extends " < type - ref - list > ;< type - ref - list >→ < type - ref > ( " ," < type - ref > )* ;< chain >→ " static "? < type - ref > < chain - expr > < tree - eval >? ;< chain - expr >→ < chain - term > ( "|" < chain - term > )* ;< chain - term >→ < chain - fact >+ ;< chain - fact >→ < chain - elem > ( "?" | "*" | "+" )? ;< chain - elem >→ < method > | "(" < chain - expr > ")" ;< method >→ NAME "(" < method - param - list >? ")" < method - action >? ;< method - param - list >→ < method - param > ( " ," < method - param > )* ;< method - param >→ < type - ref > "..."? NAME ;< method - action >→ "{" < qual - name > ";" "}" ;< type - ref >→ < qual - name > ( " <" < type - ref - list > " >" )? "[]"* ;< tree - eval >→ " return " < qual - name > ;< qual - name >→ NAME ( "." NAME )* ;NAME : [a - zA - Z_ ][ a - zA - Z0 -9 _ ]* ;Figure 5.12: Syntax of our API specification language

5.3. EVALUATION71

The concrete syntax and semantics of our API specification language arepresented in fig. 5.12. Parentheses are used to group elements. An asterisk
represents zero or more occurrences, a plus sign represents one or more
occurrences, and a question sign represents zero or one occurrence of thepreceding element. A colon is used to define a lexical token. The left-handside of a colon is the name of the token, while the right-hand side is theregular expression that the token should follow.
Matrix Computation API
The support for type parameters enables examination of a relatively complex
API protocol. As an example, we demonstrate the generation of a matrix
computation API that reports an incompatible computation as a type error.
Our matrix computation API provides two classes, namely IntMat and
FltMat, which represent an integer matrix and a float matrix, respectively.
The API supports matrix addition and multiplication. Only a matrix computation between integer matrices returns an integer matrix. Other computation (e.g., addition between an integer matrix and a float matrix) returns
a float matrix.
Figure 5.13 illustrates the specification of our matrix computation API.
The type parameters ROW and COL are the row and column sizes of a matrix,
respectively. The boundings for these parameters are written in a similarmanner to that of Java on line 10 and line 11 in fig. 5.13. (The keyword
extends defines the upper bound of a type parameter.) The boundary type
Size is a type that is defined manually, as follows:
abstract class Size { abstract int getIntVal (); }The API users can define any matrix size by subclassing Size outside of
the Protocool-generated code. For example, they can use 128-by-256
matrices and 256-by-128 matrices in their computation by defining the twoclasses Size128 and Size256. The abstract method getIntVal is used in
the tree evaluator (i.e., visitor; see section 5.2.3 for details) to obtain the
integer value represented by a concrete Size class.
The users of our matrix computation API proceed as follows:// class Size128 extends Size { ... }Size128 size128 = new Size128 ();// class Size256 extends Size { ... }Size256 size256 = new Size256 ();FltMat < Size128 , Size128 > matrix1

72

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

1 class MatrixBuilder {2// Size is upper bound of parameter ROW
3
ROW extends Size ;4
COL extends Size ;5static IntMat < ROW , COL >6
randInt () row ( ROW row ) col ( COL col );7static FltMat < ROW , COL >8randFlt () row ( ROW row ) col ( COL col );9 }10 class IntMat < ROW extends Size , COL extends Size > {11
NEW_COL extends Size ;12IntMat < ROW , COL > plus ( IntMat <R , COL > m );13
FltMat < ROW , COL > plus ( FltMat <R , COL > m );14
IntMat < ROW , NEW_COL > mult ( IntMat < COL , NEW_COL > m );15
FltMat < ROW , NEW_COL > mult ( FltMat < COL , NEW_COL > m );16
int [][] toArray () return Evaluator . toIntArray ;17 }18 class FltMat < ROW extends Size , COL extends Size > {19
NEW_COL extends Size ;20
FltMat < ROW , COL > plus ( IntMat < ROW , COL > m );21
FltMat < ROW , COL > plus ( FltMat < ROW , COL > m );22
FltMat < ROW , NEW_COL > mult ( IntMat < COL , NEW_COL > m );23
FltMat < ROW , NEW_COL > mult ( FltMat < COL , NEW_COL > m );24
float [][] toArray () return Evaluator . toFloatArray ;25 }Figure 5.13: Specification of our matrix library= MatrixBuilder . randFlt (). row ( size128 ). col ( size128 );IntMat < Size128 , Size256 > matrix2= MatrixBuilder . randInt (). row ( size128 ). col ( size256 );FltMat < Size128 , Size256 > matrix3= matrix1 . mult ( matrix2 );The following statements throw type errors, as they do not conform to theprotocol of our API:
FltMat < Size128 , Size128 > matrix1= MatrixBuilder . randFlt (). row ( size128 ). col ( size128 );IntMat < Size128 , Size256 > matrix2

5.3. EVALUATION

73= MatrixBuilder . randInt (). row ( size128 ). col ( size256 );// Cause type errors ( incompatible sizes )matrix2 . mult ( matrix1 ); // [128 , 128] * [256 , 128]
matrix1 . plus ( matrix2 ); // [128 , 256] + [128 , 128]// Cause type errors ( incompatible element types )// FltMat * IntMat returns FltMat
IntMat f2x3 = matrix1 . mult ( matrix2 );When using our matrix computation API in Scala 2.13, users can avoid
defining a custom-sized class by using literal singleton types [73], whichallows programmers to use a literal value as a type. To use the litaral types
in our API, the following helper function and class need to be defined byhand:
def size [ T <: Singleton ]( v : T ): SizeForScala [ T ] {new SizeForScala [ T ]( t )}class SizeForScala [ T <: Singleton ]( v : T ) extends Size {override def getIntVal : Int = v . asInstanceOf [ Int ]}The function size creates an instance of SizeForScala[T], which extends
the abstract class Size illustrated above. As the parameter T is bounded toSingleton, the type of v is inferred as a literal singleton type. For example,
the return type of size(100) is the literal type 100, which is a subclass of
scala.Int. Using the helper function and class illustrated above, users canwrite their computation as follows:
val matrix1 = MatrixBuilder. randFlt (). row ( size (128)). col ( size (128));
val matrix2 = MatrixBuilder. randInt (). row ( size (128)). col ( size (256));
val matrix3 = matrix1 . mult ( matrix2 ); // No type error
matrix2 . mult ( matrix1 ); // Causes a type error

Itemized Document API
As Protocool allows its users to specify how to use type parameters intheir API, Protocool users can use type parameters to check context-free

74

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

grammar. As an example of APIs with context-free grammar, consider an
API that emulates itemization of LATEX, as follows:
begin (). item ( " Item A " ). begin (). item ( " Item A .1 " ). end ()
. end ()
. asTeXStr ();// \ begin { itemize }//\ item Item A//\ begin { itemize }//\ item Item A .1//
\ end { itemize }// \ end { itemize }The API requires its users to invoke only a pair of begin() and end() in achain. A type error occurs when the API users attempt to obtain a stringfrom the itemization with an unbalanced invocation of begin() and end():
begin (). item ( " Item A " ). begin (). item ( " Item A .1 " ). end ()
. asTeXStr (); // Causes a type error ;// Cannot resolve method ' toTeXStr 'In the API, the item type is inferred from the first argument provided toitem(...). A type error occurs when users input an item with an inconsistent type:
begin (). item (100). item ( " 200 " ) // Causes a type error. end (). asTeXStr ();The itemized document API described above can be generated from thespecification illustrated in fig. 5.14. The API uses the first type parameter torepresent the stack of a pushdown automaton, in a matter that is describedin the literature [56]. The second type parameter represents the type of theitems in the document.
Although it is possible to check context-free rules in the Protocoolgenerated API, it is often excessively tedious to specify such checking in thespecification. To achieve such checking, Protocool users need to encodea pushdown automaton into the specification manually. The encoding of apushdown automaton has been automated in previous studies.
However, this limitation will not greatly degrade the practical applicability of Protocool, because context-free rules are not common in fluent

5.3. EVALUATION

75

class API {ITEM ;
static Nested < EndOfDoc , ITEM > begin ( ITEM item ) ;}class Nested <X , ITEM > {Nested < Nested <X , ITEM > , ITEM > begin ( ITEM item ) ;X end ( ITEM item ) return Evaluator . end ;}class EndOfDoc {String asTeXStr ();}Figure 5.14: Specification for itemized document APIinterfaces. The nesting structure is often emulated with a feature that isavailable in the host language, such as method invocation syntax:// Nesting is emulated by passing sub - chains// With varargs :itemize (item ( " Item A " ) ,itemize ( item ( " Item B " ))). asTeXStr ();// Without varargs :itemize (). elem ( item ( " Item A " )). elem ( itemize ( item ( " Item B " ))). asTeXStr ();This type of sub-chaining technique is frequently used in a real-world library such as j2html1 . One problem with techniques using variable-length
arguments is that all arguments need to be of the same type. The problem does not occur when using techniques without variable-length arguments, but the latter emulation requires somewhat redundant invocationsof elem(...). Finding a succinct emulation with the ability to take different argument types can be investigated in future work. In relatively new
languages, special syntactic sugars are provided that can be used to emulate
nesting structures [36, 14].
1

https://j2html.com

76

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

1 class Assertions {2
PredicateAssert assertThat ( String s );3 }4 class PredicateAssert {5PredicateAssert startsWith ( String s ) {6
Action . startsWith ;7}
8
PredicateAssert endsWith ( String s ) {9Action . endsWith ;
10
}
11 }
Figure 5.15: Specification of subset of AssertJ
Assertion API
As described in section 5.2.3, the semantics of a Protocool-generated API
are designed to be added by creating a tree evaluator (i.e., visitor). This
style is known as the deep embedding style [26]. In this style, the execution
is postponed until the API user invokes a tree evaluation method, such asbuild() in OurAPI. However, an API often does not provide such a tree
evaluation method. AssertJ2 is an example of such an API. It does not
require its users to invoke a method such as runAssertions() at the endof the chain: every method call immediately runs an assertion.
String str = . . . ;assertThat ( str ). startsWith (" A ") // Runs assertion immediately. endsWith (" Z "); // Runs assertion immediately
This style of implementing semantics is known as the shallow embedding
style [26].
Protocool supports the shallow embedding style. Figure 5.15 illustrates the specification of the subset of AssertJ that uses the feature forthe shallow embedding style. The {} block written after a method specifies
an action invoked in that method. Protocool inserts the action directly
before the return statement in the generated method body, as follows:
PredicateAssert startsWith ( String s ) {2

http://joel-costigliola.github.io/assertj/

5.3. EVALUATION

77

Table 5.1: Quantitative information of generated code
Spec.

Gen. (API)Gen. (TREE)

Gen.

12
24
21
54

158
257
138
443

141
238
198
629

299
495
336
1072

NeuralNetwork
MatrixEBNF
DOT

NeuralNetwork
MatrixEBNF
DOT
AverageGen./ Spec.

Gen. (TREE) / Gen.

24.9
20.6
16.0
19.9
19.8

0.47
0.48
0.59
0.59
0.54

// Tree construction
Ob j e c t _ P r e d i c a t e A s s e r t node = . . . ;// Inserted action
Action . startsWith ( node );return new PredicateAssert ( node );}The constructed tree is provided to the inserted action. Unlike the returnclause described in section 5.2.3, the action return value is discarded even if
the inserted method returns a value.

5.3.2

Reduction of Development Cost

Table 5.1 summarizes the number of lines of several specifications andthe generated code. NeuralNetwork and Matrix in the table refer to thespecifications we have shown in fig. 5.2 and fig. 5.13. EBNF and DOT referto the specifications in fig. 5.16 and fig. 5.17, respectively.The latter two
specifications are translated into the libraries that allow their users to compose EBNF/DOT programs inside Java code. We counted the number oflines for two groups of classes: API and TREE. The group API contains
the classes that the library users interact with and the code for the tree
construction. The group TREE contains only the tree node classes. The
last two columns of table 5.1 shows the ratio obtained from the values in
the first four columns of table 5.1. The column “Gen./ Spec.” shows the

78

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

class API {Grammar rules ( Rule ... rules );Expr expr ( Term ... terms );Term term ( Fact ... facts );TSym tsym ( String text );NSym nsym ( String text );}class Grammar {}class Rule {}class Expr {}class Term extends Expr {}class Fact extends Term {}class Sym extends Fact {Fact repeat0 ();Fact repeat1 ();}class TSym extends Sym {}class NSym extends Sym {Rule eq ( Expr expr );}Figure 5.16: Specification for EBNF emulation
magnification of the generated code over its original specification. The column “Gen. (TREE) / Gen.” shows the proportion of tree node classes in
the generated code.
As shown in table 5.1, a specification is translated into a considerablylarge amount of Java code. This magnification is due not only to many classdefinitions for protocol inspection but also to the generation of boilerplatecode such as tree node classes and their construction. The large proportion(approximately one half of the generated code) of the tree classes indicatesthat our tree generation would help library developers a lot in terms of thedevelopment cost.

5.4

Summary

In this chapter, we have proposed Protocool, a tool for generating ageneric fluent interface in Java. The contribution of this study is the development of the translation algorithm implemented in Protocool. Unlike
the methods of previous studies, our algorithm analyzes the binding timesof type parameters in a method chain. The analysis is the key techniqueenabling the generation of a generic fluent interface. Support for genericmethods is essential for introducing safe fluent interface generation into thereal world, as generic methods are frequently used to make an API statically type safe. It is possible to check context-free rules in the Protocoolgenerated API, as the use of type parameters is completely the decision of
the Protocool users.
Further investigation into experience with using Protocool will be
our primary future work. In particular, studying the effects on library userclass Stmt {}class Graph {Graph stmts ( Stmt ... stmts );}class Subgraph extends Stmt {Subgraph stmts ( Stmt ... stmts );}class Node {NodeStmt attrs ( Attr ... attrs );Edge to ( Node node );Edge to ( Subgraph subgsraph );}class EdgeStmt extends Stmt {Edge attrs ( Attr ... attrs );}class NodeStmt extends Stmt {}class Attr extends Stmt {}class AttrStmt extends Stmt {AttrStmt attrs ( Attr ... attrs );}class Port {}class CompassPt {}Figure 5.17: Specification for DOT emulation

class API {Graph graph ( Stmt ... stmts );Graph digraph ( Stmt ... stmts );Graph strict () graph ( Stmt ... stmts );Graph strict () digraph ( Stmt ... stmts );Graph graph ( String id , Stmt ... stmts );Graph digraph ( String id , Stmt ... stmts );Graph strict () graph ( String id , Stmt ... stmts );Graph strict () digraph ( String id , Stmt ... stmts );Port port ( String id );Port port ( String id , CompassPt pt );Port port ( CompassPt pt );CompassPt NORTH ();CompassPt NORTHEAST ();... // Other 8 CompassPt directions
Node node ( String id );Node node ( String id , Port port );Attr attr ( String k , String v );AttrStmt node ( Attr ... attrs );AttrStmt graph ( Attr ... attrs );AttrStmt edge ( Attr ... attrs );Subgraph subgraph ( String id , Stmt ... stmts );}5.4. SUMMARY79

80

CHAPTER 5. GENERATING GENERIC FLUENT INTERFACES

experiences caused by strange type names, and the time and space overheads caused by the code bloat, will be useful for discussing the practicalapplicability of Protocool and other fluent interface generators.

Chapter 6

Generating Fluent Interfaces
with Sub-chaining
This chapter discusses our code-generation technique that supports the generation of sub-chaining APIs. As well as the generics support described in
the last chapter, the sub-chaining support is favorable to use of the generative approach in the real world. Our technique is implemented as a tool
named Silverchain.
The chapter is organized as follows: We first describe our key idea
for sub-chaining support in section 6.1. We then overview our translation
method from a give grammer into class definitions (i.e., code-generation
technique) in the beginning of section 6.2. In section 6.2.1, we introduce theformal definition and the table representation of an single-state real-time
deterministic pushdown automaton (RPA), which we need for describing
our technique in more detail from section 6.2.2 to sec:rpa-encoding. Section 6.2.2 describes the central part of our technique, and section 6.2.3 describes the preprocessing part, which rewrites a given grammar into a form
that the central part can process. In section 6.2.4, we describe the encodingof RPAs and discuss how to implement the semantics of a generated library.
In section 6.2.5, we discuss the limitation of our construction method anddescribes Silverchain’s approach to address that limitation. The last two
sections present the use cases for evaluating our technique and summary ofthis chapter, respectively.
81

82

6.1

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

Key Idea for Sub-chaining Support

Recall that the code generation of fluent interfaces is the translation from agrammar into class definitions. More specifically, a grammar is first turned
into a state machine that accepts sequences derived from the grammar, andthen the machine is encoded into class definitions for fluent interfaces. Our
technique also follows this process from a grammar into class definitions, but
it constructs a special state machine for sub-chaining support. In the resetof this section, we describe our idea and the constraint on the state-machine
construction caused by applying our idea to the code-generation.
A sub-chaining API allows programmers to devide a chain into semantically grouped pieces. As we described in chapter 1, such an API is usefulwhen composing a long chain or changing a part of chain dynamically; forexample as follows:// Sub - chains
WhereClause w1 = col ( " id " ). eq (1);
WhereClause w2 = col ( " name " ). eq ( " John " );boolean findById = ... ;select ( " name " ). from ( " user " ). where ( findById ? w1 : w2 ) // Switch where - clause. execute ();Since a sub-chaining API corresponds to a semantical group for human programmers, it is impossible to automatically determine where a subchaining API should be provided in a fluent interface. The point wherea sub-chaining API is provided is up to the (human) library developers.
Therefore, a code-generation algorithm needs to retrieve information about
where to create a sub-chaining API from a grammar given by (human) library developers.
Our key idea for the sub-chaining support is to map a non-terminal in agiven grammar to a sub-chaining API. By mapping so, the library developers
can tell a code-generation algorithm where to generate a sub-chaining API
by defining (or not defining) a non-terminal in their grammar. The following
indicates users of the generated fluent interface can use the sub-chaining API
for where-clause:// `? ` indicates zero or one ocurrence//of preceding element< query > -> select from < where - clause >? ;< where - clause > -> col eq ;

6.2. OUR CODE-GENERATION TECHNIQUE

83

If library developers do not want to provide the sub-chaining API, they canspecify it by not defining the non-terminal <where-clause> in the grammar:< query > -> select from ( col eq )? ;Technically, a non-terminal is just a group of syntactical elements and does
not always represent a semantical group. However, the library developers
can write an input grammar so that a non-terminal represents a semanticalgroup.
Mapping a non-terminal to a sub-chaining API imposes a constraint on
the construction of a state machine: An algorithm cannot add or remove a
non-terminal from a given grammar during the construction of a state machine. In the ordinal setting, it is allowed to rewrite grammar (i.e., add ordelete non-terminals) in the translation from a grammar to a state machine.
However, since a non-terminal is mapped to a sub-chaining API, the addition of a non-terminal produces a sub-chaining API that is not specified bylibrary developers. The deletion, on the other hand, does not produce a subchaining API that is specified by the developers. To allow library developers
to control where to create sub-chaining APIs, a code-generation algorithm
need to keep the set of non-terminals as specified by library developers. This
constraint leads us to the development of a new code-generation algorithm.

6.2

Our Code-generation Technique

To illustrate our translation method concretely, we use a DSL for writing
itemized documents whose syntax is defined by the grammar in fig. 6.1a.
Parentheses are used to group elements, and a plus sign represents one
or more occurrences of the preceding element. Figure 6.1b shows a usage
example of this DSL.
Figure 6.2 illustrates the overview of our translation. Our technique first
constructs a set of RPAs, each of which corresponds to a non-terminal of agiven grammar. It then encodes those RPAs into class definitions to obtaina fluent interface. For clarity, in the following, we denote an RPA for a
non-terminal n by Rn .
Rn accepts all the symbol sequences derived from a non-terminal n,
including a sequence that contains a non-terminal, not only sequences ofterminals. For example, Rlist (the RPA for <list> in fig. 6.1a) accepts thefollowing sequences:
begin < text > < list > end
begin < text > begin < text > end end

84

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING< list > -> " begin " ( < text > < list >?)+ " end ";< text > :: String ; // Refers to a group of values//
i . e . , type(a) Grammar

begin" Item 1"
begin " Item 1.1" " Item 1.2" end" Item 2"
begin " Item 2.1" " Item 2.2" endend(b) Example sentence

Figure 6.1: Grammar and example sentence of our DSL
n1

RPA for n1

Class Defs

n2
..
.
nk

RPA for n2..
.
RPA for nk

Class Defs..
.

GrammarSet of RPA

Classes for fluent interface

Construction of RPA

Class Defs

Encoding to Class Defs

Translation
Figure 6.2: Overview of our translation method (ni is a non-terminal).

The first sequence is derived by applying the production rule of <list>
once. The second sequence is derived by applying the rule recursively. Morespecifically, it is derived by inlining <list> in the first sequence with thesequence begin <text> end, which is also derived from <list>. Note thatan accepted sequence contains not only terminals but also non-terminals.
The RPAs are encoded into class definitions in a way that an accepted
sequence is emulated by chaining method calls of the generated classes. For
example, the symbol sequences above are emulated by the following chains:6.2. OUR CODE-GENERATION TECHNIQUE

85

Table 6.1: Table representation of Rlist

begin<text><list>
end
$list

list
q0

q1

q2

q3

q4

q1 q4
-

q2
-

q1 q3
q2
q3

-

q2

-



begin (). text ("..."). list (...). end ();begin (). text ("..."). begin (). text ("..."). end (). end ();Each symbol in a sequence is encoded into a method. The argument of amethod depends on the kind of a symbol. If a symbol is a terminal such as
begin, a symbol is encoded into a method with no argument. Otherwise, asymbol is encoded into a method that takes one argument. If a symbol isa typed terminal such as <text>, the argument is an instance of the typespecified on the right-hand side of the rule. If a symbol is a non-terminal
such as <list>, the argument is a sub-chain that emulates a production ofthat non-terminal:
begin (). text ("..."). list (begin (). text ("..."). end ()). end ();6.2.1

RPA and Its Table Representation

An RPA is a 4-tuple (Σ, Γ, z0 , δ), where Σ is a finite set of input symbols, Γ
is a finite set of stack elements, z0 is the initial stack element, δ : (Σ × Γ) 7→Γ∗ is a transition function, and Γ∗ is the set of all finite sequences of theelements in Γ. In the beginning, the stack is filled with z0 . At every step,an RPA consumes one input symbol, pops the top of its stack, and pushes
zero or more elements into its stack. An RPA stops when it consumes
all input symbols or when it becomes unable to consume an input symbol
anymore with its defined transitions. An input sequence is accepted if thestack becomes empty by consuming the last symbol of a given sequence. A
sequence is rejected if an RPA stops before consuming the last symbol.
An RPA can be described by a table since the transition function ofan RPA is a binary function. Table 6.1 shows the table representation of

86

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

q1
q4

q0
begin

q1
q3
q4

q2
q4
<text>

begin

q2
q3
q4
<text>

q3
q4
end

q4
end

Figure 6.3: Example stack transition
Rlist . The table has all input symbols in its rows and all stack elements
in its columns. A transition (s, q) → Q is represented by the cell value Q
in row s of column q. When pushing elements, the rightmost element of
Q is pushed into the stack first. The symbol - in a cell indicates that notransition is defined, and the symbol  indicates that no element is pushed
into the stack on that transition. The initial stack element is indicated byadding the non-terminal name on the column top of that element.
Rn , an RPA for a non-terminal n, conforms to the following rules on
the number of elements to push into its stack: When Rn consumes the firstsymbol of a nested construct in a sequence, it pushes two elements; WhenRn consumes the last symbol of a nested construct, it pushes no element;
Rn pushes one element otherwise. Figure 6.3 shows how the stack content
of Rlist changes at each step when the input sequence is as follows:
begin < text > begin < text > end end
More specifically, Rlist pushes two elements when consuming begin, pushes
no element when consuming end, and pushes one element when consuming
other symbols such as <text>. When consuming the first symbol of a nested
construct, Rlist firstly pushes an element that will appear on the stack top
after consuming the last symbol of that nested construct. For instance,
when Rlist consumes the first begin in fig. 6.3, it first pushes q4 , which isthe element on the top after consuming the last end.

6.2.2

Construction of RPAs

The central part of our RPA construction consists of two steps: For each
non-terminal n, our method first constructs the RPA that accepts only direct productions of n; It then extends that RPA into Rn . Here, a direct
production of n refers to a sequence that matches the regular expression on
the right-hand side of n’s production rule. Note that the right-hand side
can be considered as a regular expression on symbol sequences. For clarity,
we denote the RPA accepting only direct productions of n by Rn0 .

6.2. OUR CODE-GENERATION TECHNIQUE

87<text>
start

q0

begin

q1

<text>

q2

q3<list>

end

q4

end

<text>
Figure 6.4: State diagram of Dlist

Table 6.2: Table representation of our RPA construction(a) Table of Rn0 (Initial table)

begin<text><list>
end
$list

list
q0

q1

q2

q3

q4

q1
-

q2
-

q2
q3
q4
-

q2
q4
-



(b) Intermediate tablebegin<text><list>
end
$list

list
q0

q1

q2

q3

q4

q1 q4
-

q2
-

q2
q3

-

q2

-



(c) Table of Rn (Final table)

begin<text><list>
end
$list

list
q0

q1

q2

q3

q4

q1 q4
-

q2
-

q1 q3
q2
q3

-

q2

-



The first step constructs Rn0 from a deterministic finite automaton (DFA)that accepts n’s direct productions. Such a DFA (hereinafter denoted by
Dn ) can be obtained by using well-known algorithms [6, 78] since the expression on the right-hand side is a regular expression that matches the
direct productions. Figure 6.4 shows the state diagram of Dlist . Rn0 is constructed by converting Dn to an equivalent RPA. The following describes
the conversion from Dn to Rn0 :(1.1) Enumerate all input symbols (including $n ) and all states of Dn acrossthe rows and the columns, respectively. A state of Dn is converted to

88

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING
a stack element of Rn0 .

(1.2) Put qi in row s of column qj if Dn can transition from qj to qi by
consuming s. A transition of Dn from qj to qi is converted to an
action of Rn0 that pops qj and pushes qi into the stack.
(1.3) Put n on the top of the column whose header is the initial state of Dn .
The initial state of Dn is converted to the initial stack element of Rn0 .
(1.4) Put  in row $n of a column whose header is an accepting state of Dn .
An accepting state of Dn is converted to an element that allows Rn0 to
make its stack empty by consuming $n
0 , which is obtained from D
Table 6.2a is the table representation of Rlist
list .
Since a DFA can be regarded as an RPA whose stack depth is limited toone, the table of Rn0 can always be constructed from Dn .
The second step extends Rn0 to Rn to fill the following two gaps. While0
Rn always pushes one element for every consumption, Rn pushes two elements when consuming the first symbol of a nested construct and pushes noelement when consuming the last symbol. Rn0 differs from Rn also in that,while Rn0 accepts only direct productions, Rn accepts not only direct productions but also indirect productions. An indirect production is a sequence
derived by replacing a non-terminal occurrence in the direct production witha production of that non-terminal.
The second step assumes that every application of a production rule
introduces a nested construct into a sequence. Under this assumption, thefirst and last symbol of a nested construct is the first and last symbol on theright-hand side of the production rule. Although most grammars are not inthis form, the preprocessing part of our algorithm, which is described later,
rewrites a given grammar into this form.
To fix the number of pushed elements, the second step changes cell values
in the rows of the first and last symbols of nested constructs. In our example
case, our method changes cell values in row begin and row end. Let en be
an element whose column contains  in row $n . en is the element pushed
when Rn0 consumes the last symbol of the nested construct. The number ofpushed elements is fixed by the following process:(2.1) Replace all occurrences of en with . By this modification, Rn0 pushes
no element when consuming the last symbol.
(2.2) Append en to cell values in the column of the initial stack element forn. By this modification, Rn0 pushes two elements when consuming thefirst symbol of a nested construct.

6.2. OUR CODE-GENERATION TECHNIQUE

89

In the example case, en is q4 and Step (2.1) replaces all occurrences of q4
with . Step (2.2) appends q4 to the value in row begin of column q0 .
Table 6.2b shows the intermediate table obtained by applying the above
process to table 6.2a.
To accept indirect productions, the second step puts new values to thetable. Since a non-terminal m introduces a nested construct under ourassumption, Rn pushes two elements when it consumes the first symbolof an inlined sequence derived from m. The first pushed element is theelement that appears on the stack top after consuming the last symbol of
the inlined sequence, that is, the element pushed when consuming m. The
second pushed element is the next stack top, that is, the element pushed byconsuming the first symbol of m’s production rule. Let Cm be the collectionof actions that consume m and let Pm be the collection of actions that pop
the initial stack element for m. The following describes this process to accept
indirect productions:(2.3) Put qk qj in row s of column qi for each ((x, qi ) → qj , (s, y) → qk z) ∈Cm × Pm . Here, x, y, and z are placeholders that are not related to
the newly put value.
When m is <list>, Cm is {(<list>, q2 ) → q3 } and Pm is {(begin, q0 ) → q1 }.
Step (2.3) adds (begin, q2 ) → q1 q3 . Table 6.2c shows the table obtained byapplying the above process to table 6.2b.
To show how our method works when an input grammar contains multiple non-terminals, consider a new example grammar:<doc > -> " beginDoc " < list >* " endDoc ";< list > -> " beginLst " ( < text > < list >?)+ " endLst ";< text > :: String ;From this grammar, our method first constructs table 6.3a. In table 6.3a,
Rdoc and Rlist are shown as one table, but the representation is the same as
the case where the table describes only one RPA. Our method then defines
em , Cm , and Pm as follows:
edoc = q2 , elist = q7 ,Cdoc = ∅, Clist = {(<list>, q1 ) → q1 , (<list>, q5 ) → q6 } ,Pdoc = {(beginDoc, q0 ) → q1 q2 } , Plist = {(beginLst, q3 ) → q4 q7 } ,where ∅ denotes an empty set. In Step (2.1), our method first replaces q2
and q7 with . In Step (2.2), our method then appends q2 and q7 to the cellvalues in column q0 and q3 , respectively. In Step (2.3), our method finally

90

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING
Table 6.3: Tables appearing in RPAs construction00(a) Rdoc
and Rlist

doc
q0

q1

q2

list
q3

q4

q5

q6

q7

q1
-

q1
q2
-


-

q4
-

q5
-

q5
q6
q7
-

q5
q7
-



beginDocbeginLst<text><list>
endLstendDoc$doc$list(b) Rdoc and Rlist

beginDocbeginLst<text><list>
endLstendDoc
$doc
$list

doc
q0

q1

q2

list
q3

q4

q5

q6

q7

q1 q 2
-

q4 q1
q1

-


-

q4 q 7
-

q5
-

q4 q6
q5
q6

-

q5

-



adds two actions (beginLst, q1 ) → q4 q1 and (beginLst, q5 ) → q4 q6 , which
are derived from Clist × Plist . (No new actions are derived from Cdoc × Pdoc
since Cdoc × Pdoc is ∅.) table 6.3b is the table representation of Rdoc andRlist , which is obtained by modifying table 6.3a.

6.2.3

Preprocessing

The preprocessing part rewrites a given grammar into a form where every
non-terminal has a direct recursion, as we assumed in the previous subsection . To obtain that form, the preprocessing part expands all the occurrences of non-terminals in the right-hand side of a production rule. They

6.2. OUR CODE-GENERATION TECHNIQUE

91

are replaced with the right-hand side of their production rule. For example,
consider the following grammar that has an indirect recursion:<doc >< list >< item >< text >

->
->
->
::

" beginDoc " < list >* " endDoc ";" beginLst " < item >+ " endLst ";< text > < list >?;String ;The preprocessing part expands <item> in the second line since it makes
mutual recursion:<doc > -> " beginDoc " < list >* " endDoc ";< list > -> " beginLst "( < item > | < text > < list >?)+
" endLst ";< item > -> < text > < list >?;< text > :: String ;The replaced non-terminals are ignored when building Cm in the central
part since those occurrences have already been inlined by the preprocessing.
In the case shown above, the occurrence of <item> on the right-hand sideof the rule of <list> is ignored.
The preprocessing part does not expand all the occurrences of nonterminals since infinite regression will occur when the non-terminals aredefined recursively. It selects non-terminals to be expanded by examining refer-to relations among non-terminals. A refer-to relation from a nonterminal ns to a non-terminal nd indicates that the rule for ns contains one
or more un-expanded nd on its right-hand side. For example, the example
grammar contains three references from <doc> to <list>, from <list> to<item>, and from <item> to <list>. Our preprocessing is performed asfollows:(I) Create a graph G that represents refer-to relations among non-terminals.
A node in G represents a non-terminal in the given grammar. An edge
(ns , nd ) in G represents a relation from ns to nd .
(II) Find an edge (ns , nd ) such that the following sub-process returns true:(i) Create a subgraph G0 of G by removing ns and the edges with ns
on their source or destination.
(ii) Decompose G0 into strongly connected components (SCCs) and
let the component containing nd be C [77].

92

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING<doc><list><item>(a) Initial reference relation graph<doc><list><item>(b) The edge (<doc>, <list>) is not selected since the SCC containing <list>
consists of two nodes.

<doc><list><item>(c) The edge (<list>, <item>) is selected since the SCC containing <item> consists
only of one node without a self-loop.

<doc><list><item>(d) Updated graph after expanding <item> in the rule for <list>

Figure 6.5: Selecting an edge for inline expansion(iii) Return true if C consists of a single node without a self-loop, andfalse otherwise.
(III) Apply inline expansion to the production rule for ns . All the occurrences of nd in the rule are expanded.
(IV) Update G to reflect the inline expansion at (iii). The selected edge
(ns , nd ) is removed from G and new edges are added to G to represent
refer-to relations in the expanded production rule.
In Step (I), the preprocessing part constructs the graph shown in fig. 6.5afrom the example grammar. In Step (II), it then selects (<list>, <item>)through the sub-processes shown in fig. 6.5b and fig. 6.5c. In Step (III),<list> will be expanded into the following as we have seen before:" beginLst " ( < item > | < text > < list >?)+ " endLst ";By Step (IV), G is updated to the graph in fig. 6.5d. Our preprocessing
repeats the above process until no edges found in Step (II). An edge further
from the node for the start symbol is examined earlier.

6.2. OUR CODE-GENERATION TECHNIQUE<doc><list><item>(a) Expanding (<doc>, <list>)

<doc>

93

<list><item>(b) Expanding (<doc>, <item>)Figure 6.6: Without decomposition into SCCs
The decomposition into SCCs in Step (II) is required to avoid an infinite regression of inline expansion caused by mutual recursion in the given
grammar. Suppose that the edge (<doc>, <list>) in fig. 6.5a is selected
for expansion. The dotted edge is removed, and the red edge is added asshown in fig. 6.6a. Then the edge (<doc>, <item>) in fig. 6.6a is selected
for expansion and the graph is updated to fig. 6.6b, where the dotted edge
is removed and the red edge is added. Figure 6.6b is equivalent to fig. 6.5a.
Further inline expansions will cause infinite regression. By the decomposition, Silverchain selects an edge composing a mutual-recursion cycle earlier
than other edges. Such an edge is expanded, and the cycle is transformed
into non-cyclic edges and self-loops. Which edge is first selected among
cyclic edges does not matter to resolve infinite regression.

6.2.4

Encoding into Class Definitions

Our method encodes each snapshot of an RPA into a nested generics. Since
an RPA has only one state, a snapshot of the RPA is the stack content. For
example, when the stack contains qi and qj from its top, the stack is encoded
into the type Qi<Qj<Bottom>>. A transition (s, q) → Q is encoded into amethod whose name is s and whose owner is the class for q. The return typeof that method is a type that represents Q. In the following, we describe
our encoding scheme as the encoding from a table into class definitions.
The class definition shown in fig. 6.7 shows the classes generated fromtable 6.1. (For better readability, we put table 6.1 on the bottom of fig. 6.7.)
The generated classes are categorized into two kinds. One is a set of classes
each of which corresponds to a column of the table. The classes named Qn
in the figure belong to this category. A class in this category has one typeparameter except the class corresponding to the initial stack element. The
type parameter of Qn is used to represent the stack content below the stackelement corresponding to Qn. The other category consists of two auxiliary
classes: the class corresponding to a non-terminal and the class representing
the stack bottom. In fig. 6.7, List and Bottom belong to this category.

94

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Classes each of which//corresponds to a row
class Q0 {static Q1 < Q4 < Bottom > > begin () { ... }}class Q1 <T > {Q2 <T > text ( String text ) { ... }}class Q2 <T > {Q1 < Q3 <T > > begin () { ... }Q2 <T > text ( String text ,String ... textArray ) { ... }Q3 <T > list ( List list ) { ... }T end () { ... }}class Q3 <T > {Q2 <T > text ( String text ) { ... }T end () { ... }}class Q4 <T > extends List {}// Auxiliary classes :// Class corresponding to < list >class List{}// Class for the stack bottom
class Bottom {}

begin<text><list>
end
$list

list
q0

q1

q2

q3

q4

q1 q4
-

q2
-

q1 q3
q2
q3

-

q2

-



Figure 6.7: Class definitions generated from table 6.1

6.2. OUR CODE-GENERATION TECHNIQUE

95

Each method in the generated class corresponds to a table cell. A method
is defined in the class corresponding to column q when the method corresponds to a cell in column q. For example, the method of Q1 on Line 7
corresponds to the cell in row <text> of column q1 . A method is modified
with static if the owner class corresponds to the initial stack element. By
adding static, the users of the library can invoke the first method of a chain
directly without writing the receiver class using a static import statement.
Instead of encoding a cell in row $n into a method, the cell is encoded into
an extend clause. In the case of the example, Q4 extends List as shown onLine 20 since column q4 has a value in row $list . By this special encoding,a chain representing a syntactically correct sequence can be assigned to avariable whose type is the class corresponding to the source non-terminal.
The return type of a method is determined by the corresponding cellvalue. A method returns a nested generics if the cell value is not . Classes
are nested in a way that the leftmost element of the value is the outermost
class of the nested generic. The innermost class is Bottom if the method
is modified with static. Otherwise, the innermost class is the type parameter of the owner class. For example, q1 q4 in column q0 is encoded
into Q1<Q4<Bottom>> as shown on Line 4. A method returns just the typeparameter if the cell is filled with  such as the method on Line 14. The argument of a method depends on the kind of the input symbol on the columnof the corresponding cell. A method takes no argument if the symbol on thecolumn is a terminal, and takes one argument otherwise. As we mentioned
earlier, the type of that argument depends on the kind of a symbol. If thesymbol is a typed terminal, the argument type is as specified on the rightof the operator ::. Otherwise, the argument type is the class corresponding
to the symbol.
As a manually developed fluent interface often provides several convenience methods using variable-length arguments, Silverchain also generates
such methods to improve the user experiences of the generated library. The
method on Line 11 is such a convenience method and takes multiple String
objects as its arguments. The following lines show the example usage ofthat convenience method:
begin (). text (" Item 1" ," Item 2" ," Item 3"). end ();// begin ()//. text (" Item 1")//. text (" Item 2")//. text (" Item 3")// . end ();Silverchain generates such a method with variable length arguments when

96

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

it finds two actions (s, qi ) → qj and (s, qj ) → qj .
Figure 6.8 shows the generated code for Q2 including the method bodies.
Each method appends the object representing an invoked method to a list
shared among state instances. Each method first appends a Method instance,
which is an instance that holds the name and arguments of the method
invocation, to the list. Line 9 in fig. 6.8 is the line that appends suchan instance. A method appends multiple Method instances at once when
it takes a sub-chain as its argument as shown on Line 16. The method
then creates and return an instance that is used as the receiver of the next
method invocation. The list of invoked methods is shared by passing it as
the argument to the constructor as shown on Line 11. We need a little
trick for generated methods to return a nested parametric type as shown
from Line 26 to Line 31. Instead of executing new T(), Silverchain calls
newInstance on a class object representing T. Since a type parameter is nota first-class entity in Java, the generated library uses the reflection API andexplicitly passes a type parameter as a class object.
We showed the method bodies only in Q2, but the method bodies in
the other classes are very similar to the ones in Q2. For example, the bodyof text(String) in Q1 is the same as the one in Q2. There is only one
difference in the body of Q0.begin(). Since the method is modified withstatic and invoked at the beginning of a chain, it does not have a context
to be passed. Therefore, it has to create a new list to record the invokedmethods and a stack to store class objects as follows:
static Q1 < Q4 < Bottom > > begin () {ArrayList < Method > methodList = new ArrayList < >();
Stack < Class <? > > classStack = new Stack < >();
methodList . add ( new Method (" begin " , null ));classStack . push ( Q4 . class )return new Q1 < >( methodList , classStack );}Library developers (i.e., the Silverchain users) can add semantics to thegenerated library by implementing an evaluation method, a method thatinterprets a written chain. Figure 6.9 shows an example implementationthat constructs an itemized document in TEX from a written chain. In this
implementation, each method in methodList is converted into a token of
TEX. The Silverchain users can put all semantic actions into one method
rather than editing method bodies scattered over the generated code. Thisapproach to implement the semantics reduces the library developers’ task
when updating and re-generate a modified library. They do not have to edit

6.2. OUR CODE-GENERATION TECHNIQUE

97

1 class Q2 <T > {2
ArrayList < Method > methodList ;3
Stack < Class <? > > classStack ;4
Q2 ( ArrayList < Method > list , Stack < Class <? > > stack ) {5methodList = list ;6classStack = stack ;7}
8
Q1 < Q3 <T > > begin () {9methodList . add ( new Method (" begin " , null ));10classStack . push ( Q3 . class );11
return new Q3 < >( methodList , classStack );12}
13
Q2 <T > text ( String text , String ... textArray ) {14methodList . add ( new Method (" text " , text ));15
for ( String t : textArray ) {16methodList . add ( new Method (" text " , t ));17}
18
return new Q2 < >( methodList , classStack );19}
20
Q3 <T > list ( List list ) {21
methodList . addAll ( list . methodList );22
return new Q3 < >( methodList , classStack );23}
24
T end () {25
methodList . add ( new Method (" end " , null ));
26
try {
27
return ( T ) classStack . pop ()28. getDeclaredConstructor (29
ArrayList . class , Stack . class )30. newInstance ( methodList , classStack );31} catch ( Exception e ) {}
32
}
33 }
Figure 6.8: Definition of Q2 including method bodies

98

CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

String toTeX () {String tex = "";for ( Method m : this . methodList ()) {if ( m . name == " begin ")tex += "\ begin { itemize }";else if ( m . name == " end ")tex += "\ end { itemize }";else if ( m . name == " text ")tex += "\ item " + m . argument ;}return tex ;}Figure 6.9: Example implementation of library semantics
a number of parts of the generated code.
The flattened list of invoked methods (e.g. Q2.methodList) helps librarydevelopers when the library is just an embedded interface to an external DSL
such as SQL and TEX. However, such a list does not help the developers
when building actions for the DSL that does not have an external execution system, or when the developers apply optimization to generated DSL
code. In those cases, the developers may prefer tree-structured data over aflattened list of invoked methods. However, it would be better to generates
method bodies that construct tree-structured data from a written chain forthe library developers. The generation of better method bodies is a future
work that is required to use Silverchain in practice.

6.2.5

Limitation

Silverchain can generate regular (flat) chaining APIs for all parts when every
nested construct in a given grammar begins and ends explicitly. If-else
syntax with dangling-else is a common syntax component that does nothave such explicit symbols:< ifelse > -> " if " < cond > < stmts > ("else" <stmts>)? " fi ";< stmts >-> ( < ifelse > | < stmt >)*;
Since else corresponds to if, those two symbols introduce a nested construct into a sequence. However, that nesting may end implicitly since elseis optional. Try-catch-finally syntax with dangling-finally is also an example

6.2. OUR CODE-GENERATION TECHNIQUE

99

of such a syntax component:<TCF >-> " try " < stmts > " catch " <err >("finally" <stmts>)?;< stmts > -> ( < TCF > | < stmt >)*;In this case, try and finally introduce a nested construct, but that nesting
may end implicitly without finally.
Silverchain fails to generate flat chaining APIs since Rn pushes the element that will appear on the stack top after a nested construct ends. If agiven grammar contains a recursive structure without explicit ending symbols, our method cannot determine which element will appear on the stack
top after a nested construct ends. This limitation can be stated as follows
in terms of the table representation of Rn0 :(a) Only one column contains  in row $n .
(b) No value exists in row s of column q for all ((∗, q) → ∗, (s, ∗) → ∗) ∈Cm × Pm , where ∗ is a placeholder that is not related to this condition.
When given grammar represents a visibly pushdown language (VPL) [1],Condition (a) and (b) is satisfied. A VPL has the property that symbols to
begin/end a nesting structure are not used anywhere else.
When the table of Rn0 violates Condition (a), our method cannot perform
Step (2.2) successfully. Table 6.4a is an example table that does not satisfy
Condition (a), which is constructed from the following grammar:< nest > -> " begin " < nest > " end "? | < text >;< text > :: String ;Table 6.4a has two columns that contain  in row $nest . To fix the numberof pushed elements in Step (2.2), our method needs to find en , the element
to append to the value in row begin. When the table contains multiple
columns that contain  in row $n , our method needs to choose either of
those elements since a cell can contain only one value. However, the RPA
obtained by appending one those elements accepts only a part of sequencesthat should be accepted. If our method chooses q2 as en and perform Step
(2.1) and Step (2.2) as shown in table 6.4b, the RPA does not accept thefollowing:< text >On the other hand, if our method chooses q3 as en and perform Step (2.1)
and Step (2.2) as shown in table 6.4c, the RPA does not accept the following:

100 CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING
Table 6.4: Table violating Condition (a) and its modification(a) Table of Rnest

begin<nest>
end<text>$nest(b) en = q2

nest
q0

q1

q2

q3

q1
q3
-

q2
-

-



q3


begin
<nest>
end<text>
$nest

nest
q0

q1

q2

q3

q1 q2
q3
-


-

-



q3


(c) en = q3

begin
<nest>
end<text>
$nest

nest
q0

q1

q2

q3

q1 q3

-

q2
-

-






begin < nest >When the table of Rn0 violates Condition (b), our method cannot construct Rn correctly. Table 6.5a is an example of such tables, which is constructed from the following grammar:< nest > -> " begin " ( < nest > | " begin " < text >) " end ";< text > :: String ;Our method fixes the number of pushed elements in Step (2.1) and Step(2.2) as shown table 6.5b. It then constructs Cnest and Pnest as follows:
Cnest = {(<nest>, q1 ) → q2 } , Pnest = {(begin, q0 ) → q1 q4 } .
In Step (2.3), our method put q1 q2 in row begin of column q1 as shown intable 6.5c. However, the RPA described by table 6.5c does not accept thefollowing:
begin begin < text > end

6.2. OUR CODE-GENERATION TECHNIQUE

101

Table 6.5: Table violating Condition (b) and its modification(a) Table of Rnest

begin<nest>
end<text>$nest(b) Fixed table of Rnest

nest
q0

q1

q2

q3

q4

q1
-

q3
q2
-

q4
-

q4
-



begin
<nest>
end<text>
$nest

nest
q0

q1

q2

q3

q4

q1 q4
-

q3
q2
-


-


-



(c) Incorrect update

begin<nest>
end<text>
$nest

nest
q0

q1

q2

q3

q4

q1 q4
-

q1 q 2
q2
-


-


-



If our method skips Step (2.3) to avoid overwriting cell values, the constructed RPA for a non-terminal n does not accept indirect productions ofn.
Silverchain skips the second step in our RPA construction method when
it finds the violation of Condition (a) or (b). Since the second step is theprocess to make RPAs accept indirect productions, RPAs remain to accept
only direct productions. This results that the generated fluent interface
allows its users to use only sub-chaining APIs for certain parts of a chain.
For example, consider encoding table 6.5b into class definitions. Figure 6.10
shows the classes generated from the table and the library users can write
the following chains:
begin (). begin (). text ("..."). end ();begin (). nest (begin (). begin (). text ("..."). end ()). end ();The users cannot write the following chain that uses regular chaining APIs:

102 CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Q0 {static Q1 < Q4 < Bottom > > begin () { ... }}class Q1 <T > {Q3 <T > begin () { ... }Q2 <T > nest ( Nest nest ) { ... }}class Q2 <T > {T end () { ... }}class Q3 <T > {T text ( String text ) { ... }}class Q4 <T > extends Nest {}class Nest {}class Bottom {}Figure 6.10: Class definitions generated from table 6.5b

Table 6.6: Number of classes and methods

LINQ
DOT

#Symbols#Non-terminals#Classes(Generated)#Methods(Generated)

32
40

17
15

132
389

323
1687

#Classes(Hand-written)#Methods(Hand-written)

16
25

44
337

LINQ
DOT

begin (). begin (). begin (). text ("..."). end (). end ();This limitation is problematic from the viewpoint of DSL emulation since
sub-chaining APIs introduce redundant parts into a chain.

6.3. USE CASES

6.3

103

Use Cases

In this section, we compare Silverchain-generated fluent interfaces and popular hand-written libraries, using LINQ1 and DOT2 as examples. LINQ is a
DSL for operating collection data, and DOT is a DSL for describing graphs.
We chose coollection3 as a popular library for LINQ and graphviz-java4 as
one for DOT. Besides, we experimentally investigate how the length of acomposed chain affects the compilation time since a Silverchain-generated
library heavily uses generics.
Table 6.6 summarizes the numbers of classes and methods generated fromthe grammars of those DSLs. The values in the first and second columns are
the numbers of unique symbols and non-terminals in the grammar, respectively. The values in the third column to the sixth column are the numbersof classes and methods in the generated libraries and the hand-written libraries. When counting classes and methods, we picked up only public ones
since our primary concern is API but not non-public implementations. As
seen from the table, the numbers of generated definitions are too large tohandle by hand although the grammars of those languages are relatively simple. Those numbers are significantly small in hand-written libraries. This
smallness is mainly because the hand-written libraries allow their users tocompose syntactically incorrect chains as follows:// Multiple ORDER BY clauses
from ( users ). orderBy (" age " , Order . DESC ). orderBy (" age " , Order . ASC );No support of non-subchaining APIs also reduces the numbers of classes andmethods of the hand-written libraries.
Figure 6.11 and fig. 6.12 show example sentences and their embedded
versions of LINQ and DOT, respectively. As seen from these examples, thecode written with the generated libraries are similar to the one written withhand-written libraries in most parts. Figure 6.11c is similar to fig. 6.11b,
and fig. 6.12c and fig. 6.12d are similar to fig. 6.12b.
The first drawback is that code written with the generated libraries tends
to contain redundant method calls. For instance, from().collection(...)
in fig. 6.11c is expressed in a shorter way by from(...) in fig. 6.11b. Similarly, beginGraph() in fig. 6.12c is omitted in fig. 6.12b. These redundant1

http://programminglinq.info/tag/bnf/
http://www.graphviz.org/content/dot-language
3
https://github.com/19WAS85/coollection
4
https://github.com/nidi3/graphviz-java2

104 CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING
from u in users
from ( users )where u . age > 2. where (" age " , gt (2))
orderby u . age descending. orderBy (" age " , Order . DESC )select u ;. all ();(a) Example sentence(b) With coollection

from (). collection ( users ). where (). field (" age "). gt (). value (2). orderBy (" age "). descending (). select ();(c) With generated library

Figure 6.11: Comparison in LINQ

methods are generated since our translation method encodes every token ofa DSL into a method. Those methods can be omitted by using information
obtained from the table representation of RPAs. A method can be omitted if it is the only transition that exists between states and no ambiguity
arises after omitting that transition. However, if such automatic omission isapplied naively, a method chain with the generated libraries might be unreadable for programmers. Some redundant symbols in a DSL are necessary
for programmers to read and understand written sentences. To avoid thisproblem, Silverchain does not apply that automatic omission.
Another drawback is that programmers can hardly edit those classes tomake APIs better since generated libraries use mechanically named classes
such as Q1 and Q2. The APIs of coollection and graphviz-java are designed
using the domain-specific knowledge that is not represented in the grammar.
For instance, coollection uses enum to specify the order as shown in fig. 6.11b
and graphviz-java uses enum to specify attributes of a node as shown infig. 6.12e. However, to add such methods reflecting domain-specific knowledge, the developers of a library need to fix scattered parts of generated
classes. The generation of such methods is difficult since our translation
method naively encodes every token of a sentence into a method. Findinga smarter way of encoding is important future work to put Silverchain into
practical use.
To investigate the relation between the compilation time and the lengthof a chain, we measured the compilation time of a chain of various length,
using the generated library for DOT. In our experiments, we compiled chains6.3. USE CASES

105

graph (" G "). directed (). with (node (" A "). link ( node (" B ")) ,node (" B "). link ( node (" C ")) ,node (" C "). link ( node (" A ")));digraph G {A -> B
B -> CC -> A}(b) Using graphviz-java(a) Example sentencedigraph (). id (" G "). beginGraph (). edge (node (" A "). arrow (). node (" B ") ,node (" B "). arrow (). node (" C ") ,node (" C "). arrow (). node (" A ")). endGraph ();(c) Usage with sub-chaining

digraph (). id (" G "). beginGraph (). node (" A "). arrow (). node (" B "). node (" B "). arrow (). node (" C "). node (" C "). arrow (). node (" A "). endGraph ();(d) Usage without sub-chaining// With graphviz - java
node (" X "). with (Shape . RECTANGLE ,Style . FILLED);// With generated librarynode (" X "). beginAttr (). shape (). eq (). rectangle (). style (). eq (). filled (). endAttr ();(e) Difference between generated library and graphviz-java

Figure 6.12: Comparison in DOT

0.28

0.38

0.27

0.37

0.26

Compilation time (s)Compilation time (s)106 CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

0.25
0.24
0.23
0.22
0.21
0.2
0.19

0.35
0.34
0.33
0.32
0.31
0.3
0.29

0.18
0.17

0.36

0

50

100

150

200

250

300

350

400

450

500

Chain length

0.28

0

50

100

150

200

250

300

350

400

450

500

Chain length(a) Java 8(b) Java 9

Figure 6.13: Result of experiments
Table 6.7: Fitted parameters in y = ax + b

Java 8Java 9ab1.61 × 10−4 ± 2.52 × 10−6
1.66 × 10−4 ± 2.67 × 10−6

1.19 × 10−1 ± 7.30 × 10−4
2.90 × 10−1 ± 7.72 × 10−4that contain various numbers of subgraph().beginSubgraph() as follows:digraph (). id (" G "). beginGraph (). subgraph (). beginSubgraph (); // Length = 5
digraph (). id (" G "). beginGraph (). subgraph (). beginSubgraph (). subgraph (). beginSubgraph (); // Length = 7
Since a call to beginSubgraph starts a new nested construct, the type sizeat the end of a chain increases as the chain becomes longer. Here, the size ofa type is defined by the number of type names in the textual representationof the type. (The size of G<T,S> is three for example.) Our experiments are
performed on a machine with Intel Core i7 3.3 GHz processor and 16 GB
memory, using javac 1.8.0 114 and javac 9. Two versions of Java wereused in our experiments since Java 9 has a new type-checking strategy [39].
We used javac -verbose to compile chains and extracted total compilation
time from its output.
Figure 6.13 shows the results of this experiment. We measured the compilation time five times for each length of a chain, and the averages areshown in the figures. The blue line in each figure is the linear regression lineof data. The fitted parameters are summarized in table 6.7. As seen from

6.4. SUMMARY

107

these results, with a library generated by Silverchain, the compilation time
grows linearly to the length of a chain even in the worst case.

6.4

Summary

We presented Silverchain, which generates safe fluent interfaces that support
both sub-chaining and non-subchaining style. The input to Silverchain is
the grammar of a generating fluent interface. Since the DSL for the input
grammar is similar to BNF, a fluent interface for an external DSL can beeasily generated from the grammar of the DSL with Silverchain. However,for some grammars, Silverchain fails to generate a fluent interface that fully
supports non-subchaining style.
First future work is to extend the range of grammars that Silverchain
can generate non-subchaining style API for without exponential growth ofcompilation time. Another future work is to improve the emulation of DSLs
by using the mechanism in the host language. For example, DSL sentences
are currently emulated only by method chaining, but they could be emulated
in a better way by mapping a part of DSL’s syntax to the similar syntax ina host general-purpose language (e.g. if-else syntax in a DSL to the same
syntax in a host language). The properties of an emulated DSL other thansyntactic rules could also be statically checked if the DSL’s type system orname binding system is also mapped to host language mechanism.

108 CHAPTER 6. GENERATING FLUENT INTF W. SUB-CHAINING

Chapter 7

Conclusions
This dissertation presented our studies to improve the user experiences offluent interfaces. As we have discussed in chapter 2, fluent interfaces are
considered as a promising design style of library interfaces. Therefore, thescope of our studies is broad to a certain degree. However, the increasing useof fluent interfaces in the real world is not empirically verified as far as weknow. Chapter 3 addresses this lack of empirical evidence by mining 2,814
Java repositories on GitHub. Our results shown in chapter 3 empiricallyreveal that the method-chaining style and fluent interfaces are increasingly
used in the real world.
In chapter 4, we discovered desirable language designs for the use of fluent
interfaces, through mining real-world repositories hosted on GitHub. We
also statistically estimated the impact of introducing those designs. As wesummarized in section 4.8, we found four language/library designs and theirintroduction would help method chaining in 14.8% of method invocations.
The primary contribution of the study discussed in the chapter is that the
impact is measured in a quantitative manner. Since language development
often proceeds conservatively, such quantitative data is important to claim
the need for the designs in language development.
Chapter 5 proposed a code-generation technique to generate generic fluent interfaces. Our technique is demonstrated by the code generator Protocool. Unlike the previous study, the users of Protocool can include
generic methods in an input grammar. Our translation algorithm implemented for Protocool is modeled as the construction of deterministic
finite automaton (DFA) with type parameter information. Each state of theDFA holds information about which type parameters are already bound inthat state. The information is used to identify whether a method invocation
109

110

CHAPTER 7. CONCLUSIONS

in a chain newly binds a type to a type parameter, or refers to a previously bound type. The identification is required since a type parameter ina chain is bound at a particular method invocation, and that bound type isreferred to in the following method invocations. Our algorithm constructs
the DFA by analyzing the binding time of type parameters and their propagation among the states in a DFA that is naively constructed from the given
grammar.
Chapter 6 presented another code-generation technique to realize thesub-chaining support in the fluent interface generation. We implemented
a tool named Silverchain to demonstrate our technique. Our translation ismodeled as the construction of deterministic pushdown automata without
-transitions called single-state real-time deterministic pushdown automata(RPAs). The class definitions of a fluent interface are generated by encoding
those RPAs. Our RPA-construction method is different from the literature[34, 64] in that it does not add or remove non-terminals from the given grammar. This property is essential to generate sub-chaining APIs as specified
by Silverchain users (i.e., library developers). Our technique can generate afluent interface from any context-free grammar, but the interface generated
from some grammars require sub-chaining APIs to compose certain parts ofsentences. This limitation is due to our RPA-construction method.

Future WorkThe results presented in chapter 3 are supportive evidence for the acceptanceof the method-chaining style and fluent interfaces in the real world. However, true acceptance cannot be derived directly from them. To claim so,
we need to conduct interviews with real-world programmers whether they
accept the style and interfaces. Such interviews are helpful to strengthen
the background of our studies in chapter 4, chapter 5, and chapter 6. It isalso beneficial for a better understanding of method chaining to investigate
why real-world programmers prefer (or do not prefer) method chaining. The
issues mentioned in the StackOverflow thread [60] would be good starting
points of such an investigation. Although we conducted analyses only ofJava code for the study in chapter 3, conducting the same study on otherobject-oriented languages would also be valuable to strengthen the background of studying fluent interfaces.
In chapter 4, we presented several language/library designs but did not
implement them into Java. The desirable language designs for the patterns
NullExceptionAvoidance, RepeatedReceiver, and DownCast are

111
implemented in other languages such as Kotlin., Therefore, there would not
be serious problems in the actual implementation of those designs although
the implementation would cost a lot. The pattern ConditionalExecution can be relieved by introducing syntactic sugar into Java. Thus, theimplementation would not include a serious problem either. However, these
discussions are based on our (optimistic) observation. It is beneficial to implement them into Java, to discover new problems that PL/SE researchers
need to tackle.
While a lot of studies have been done for fluent interface generation(including our studies), the implementation side is not well studied yet. By
generating interface code, the programmer experiences would be improved.
However, the code bloat would decrease the runtime performance and would
increase the size of a program. Related to this point, how the semantics oflibraries are implemented is interesting enough to study. When creating a
relatively small library, the deep embedding style is too tedious. On theother hand, the shallow embedding makes the implementation complicatedwhen developing relatively large libraries.
The user studies of our demonstration tools Protocool and Silverchain
are another important future work to test the availability of the generative
approach in the real world. To the best of our knowledge, there is no fluent
interface generator that is widely used in the real world, i.e., the generative
approach has never been truly evaluated in real-world settings. (Note thatmany use cases are shown in the papers discussing the approach, including
our papers.) The generative approach would not be completely useless since
there are widely-used code generators for specific libraries such as AssertJ
and jOOQ. The user studies would help the promotion of the approach andthe discovery of new problems that we need to solve.

112

CHAPTER 7. CONCLUSIONS

Bibliography[1]

Rajeev Alur and P. Madhusudan. “Visibly Pushdown Languages”. In:
Proceedings of the Thirty-sixth Annual ACM Symposium on Theory ofComputing. 2004.

[2]

Pavel Avgustinov et al. “QL: Object-oriented Queries on Relational
Data”. In: 30th European Conference on Object-Oriented Programming. 2016.

[3]

Kent Beck. “Smalltalk Best Practice Patterns”. In: 1997, pp. 183–188.

[4]

Nels E. Beckman, Duri Kim, and Jonathan Aldrich. “An Empirical
Study of Object Protocols in the Wild”. In: Proceedings of the 25th
European Conference on Object-oriented Programming. 2011.

[5]

Eric Bodden. “TS4J: A Fluent Interface for Defining and Computing
Typestate Analyses”. In: Proceedings of the 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis.
2014.

[6]

Janusz A Brzozowski. “Canonical regular expressions and minimal
state graphs for definite events”. In: Mathematical theory of Automata(1962).

[7]

Yegor Bugayenko. Fluent Interfaces Are Bad for Maintainability. https://www.yegor256.com/2018/03/13/fluent-interfaces.html. (Accessedon 01/07/2021).

[8]

R. P. L. Buse and W. R. Weimer. “Learning a Metric for Code Readability”. In: IEEE Transactions on Software Engineering (2010).

[9]

Arvid Butting et al. “Deriving Fluent Internal Domain-specific Languages from Grammars”. In: Proceedings of the 11th ACM SIGPLAN
International Conference on Software Language Engineering. 2018.

113

114

BIBLIOGRAPHY[10]John Cocke. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York
University, 1969.

[11]

S. Cook, R. Harrison, and P. Wernick. “A simulation model of selforganising evolvability in software systems”. In: IEEE International
Workshop on Software Evolvability. 2005.

[12]

Bruno Courcelle. “On jump-deterministic pushdown automata”. In:
Mathematical systems theory (1977).

[13]

Valentin Dallmeier et al. “Generating Test Cases for Specification Mining”. In: Proceedings of the 19th International Symposium on Software
Testing and Analysis. 2010.

[14] Domain-Specific Languages. http://docs.groovy-lang.org/docs/latest/
html/documentation/core-domain-specific-languages.html. (Accessedon 01/07/2021).
[15]

Robert Dyer et al. “Mining Billions of AST Nodes to Study Actualand Potential Usage of Java Language Features”. In: Proceedings ofthe 36th International Conference on Software Engineering. 2014.

[16] Emulating “self types” using Java Generics to simplify fluent API implementation. https://gist.github.com/esfand/dd79511ede7e48a0e88e.
(Accessed on 01/07/2021).
[17]

Sebastian Erdweg et al. “SugarJ: Library-based Syntactic Language
Extensibility”. In: Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications. 2011.

[18] Extensions - Kotlin Programming Language. https://kotlinlang.org/
docs/reference/extensions.html. (Accessed on 01/07/2021).
[19] Extensions - The Swift Programming Language (Swift 5.1). https://
docs . swift . org / swift - book / LanguageGuide / Extensions . html. (Accessed on 01/07/2021).
[20]

Martin Fowler. FluentInterface. https://www.martinfowler.com/bliki/
FluentInterface.html. (Accessed on 01/07/2021).

[21]

Martin Fowler. Generation Gap. https://martinfowler.com/dslCatalog/
generationGap.html. (Accessed on 01/07/2021).

BIBLIOGRAPHY
[22]

115

Steve Freeman and Nat Pryce. “Evolving an Embedded Domain-specific
Language in Java”. In: Companion to the 21st ACM SIGPLAN Symposium on Object-oriented Programming Systems, Languages, and Applications. 2006.

[23] Functions - D Programming Language. https : / / dlang . org / spec /function.html. (Accessed on 01/07/2021).
[24]

Mark Gabel and Zhendong Su. “Symbolic Mining of Temporal Specifications”. In: Proceedings of the 30th International Conference on
Software Engineering. 2008.

[25]

Carlo Ghezzi, Andrea Mocci, and Mattia Monga. “Synthesizing Intensional Behavior Models by Graph Transformation”. In: Proceedings ofthe 31st International Conference on Software Engineering. 2009.

[26]

Jeremy Gibbons and Nicolas Wu. “Folding domain-specific languages:
Deep and shallow embeddings (Functional Pearl)”. In: Proceedings of
the ACM SIGPLAN International Conference on Functional Programming. 2014.

[27]

Yossi Gil and Keren Lenz. “Simple and safe SQL queries with C++
templates”. In: Science of Computer Programming (2010).

[28]

Yossi Gil and Tomer Levy. “Formal Language Recognition with theJava Type Checker”. In: 30th European Conference on Object-Oriented
Programming. 2016.

[29]

Yossi Gil and Ori Roth. “Fling — A Fluent API Generator”. In: Proceedings of 30th European Conference on Object-Oriented Programming. 2019.

[30]

AA Gorshenev and Yu M Pis’mak. “Punctuated Equilibrium in Software Evolution”. In: Physical review. E, Statistical, nonlinear, and soft
matter physics (2005).

[31]

Sheila A. Greibach. “A New Normal-Form Theorem for Context-Free
Phrase Structure Grammars”. In: Journal of the ACM (1965).

[32]

Radu Grigore. “Java Generics Are Turing Complete”. In: Proceedingsof the 44th ACM SIGPLAN Symposium on Principles of Programming
Languages. 2017.

[33]

Y. Guo et al. “An Empirical Validation of the Benefits of Adheringto the Law of Demeter”. In: 18th Working Conference on Reverse
Engineering. 2011.

116

BIBLIOGRAPHY[34]

Michael A. Harrison and Ivan M. Havel. “Real-Time Strict Deterministic Languages”. In: SIAM Journal on Computing (1972).

[35]

L. Hatton. “Power-Law Distributions of Component Size in General
Software Systems”. In: IEEE Transactions on Software Engineering(2009).

[36] Higher-Order Functions and Lambdas - Kotlin Programming Language.
https://kotlinlang.org/docs/reference/lambdas.html. (Accessed on
01/07/2021).
[37]

Paul Hudak. “Building Domain-Specific Embedded Languages”. In:
ACM Computing Surveys (1996).

[38]

Kazuhiro Ichikawa and Shigeru Chiba. “User-Defined Operators Including Name Binding for New Language Constructs”. In: The Art,
Science, and Engineering of Programming (2017).

[39] JEP 215: Tiered Attribution for javac. http://openjdk.java.net/jeps/
215. (Accessed on 01/07/2021).
[40]

Tadao Kasami. An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Tech. rep. DTIC Document, 1965.

[41]

Martin Kellogg et al. “Verifying Object Construction”. In: Proceedings of the ACM/IEEE 42nd International Conference on Software
Engineering. 2020.

[42]

Tomer Levy. “A Fluent API for Automatic Generation of Fluent APIsin Java”. PhD thesis. Israel Institute of Technology, 2017.

[43]

K. Lieberherr, I. Holland, and A. Riel. “Object-oriented Programming:
An Objective Sense of Style”. In: ACM SIGPLAN Notices (1988).

[44]

Z. Lin and J. Whitehead. “Why Power Laws? An Explanation from
Fine-Grained Code Changes”. In: 2015 IEEE/ACM 12th Working
Conference on Mining Software Repositories. 2015.

[45]

Panagiotis Louridas, Diomidis Spinellis, and Vasileios Vlachos. “Power
Laws in Software”. In: ACM Transactions on Software Engineeringand Methodology (2008).

[46]

Robert C Martin. Clean code: a handbook of agile software craftsmanship. Pearson Education, 2009.

[47]

Luis Mastrangelo, Matthias Hauswirth, and Nathaniel Nystrom. “Casting about in the Dark: An Empirical Study of Cast Operations in Java
Programs”. In: Proceedings of the ACM on Programming Languages(2019).

BIBLIOGRAPHY
[48]

117

Davood Mazinanian et al. “Understanding the Use of Lambda Expressions in Java”. In: Proceedings of the ACM on Programming Languages(2017).

[49] Method Cascades in Dart. http://news.dartlang.org/2012/02/methodcascades-in-dart-posted-by-gilad.html. (Accessed on 01/07/2021).
[50]

Leo A. Meyerovich and Ariel S. Rabkin. “Empirical Analysis of Programming Language Adoption”. In: Proceedings of the 2013 ACM
SIGPLAN International Conference on Object Oriented Programming
Systems Languages and Applications. 2013.

[51]

Chris Myers. “Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs”. In: Physicalreview. E, Statistical, nonlinear, and soft matter physics (2003).

[52]

Tomoki Nakamaru and Shigeru Chiba. “Generating a Generic Fluent
API in Java”. In: The Art, Science, and Engineering of Programming(2020).

[53]

Tomoki Nakamaru et al. “An Empirical Study of Method Chaining inJava”. In: Proceedings of the 17th International Conference on Mining
Software Repositories. 2020.

[54]

Tomoki Nakamaru et al. Data - An Empirical Study of Method Chaining in Java. Version 1.0.0. Zenodo, Mar. 2020. doi: 10.5281/zenodo.
3697939. url: %5Curl%7Bhttps://doi.org/10.5281/zenodo.3697939%
7D.

[55]

Tomoki Nakamaru et al. “Generating fluent embedded domain-specificlanguages with subchaining”. In: Journal of Computer Languages (2019).

[56]

Tomoki Nakamaru et al. “Silverchain: a fluent API generator”. In:
Proceedings of the 16th ACM SIGPLAN International Conference on
Generative Programming: Concepts and Experiences. 2017.

[57]

Mark EJ Newman. “Power laws, Pareto distributions and Zipf’s law”.
In: Contemporary physics (2005).

[58]

Ligia Nistor et al. “Wyvern: A Simple, Typed, and Pure Objectoriented Language”. In: Proceedings of the 5th Workshop on MechAnisms for SPEcialization, Generalization and inHerItance. 2013.

[59] Null Safety - Kotlin Programming Language. https://kotlinlang.org/
docs/reference/null-safety.html. (Accessed on 01/07/2021).

118

BIBLIOGRAPHY[60] OOP - Method chaining - why is it a good practice, or not? - Stack
Overflow. https : / / stackoverflow . com / questions / 1103985 / method chaining-why-is-it-a-good-practice-or-not. (Accessed on 01/07/2021).
[61] Optional Chaining - The Swift Programming Language (Swift 5.1).
https://docs.swift.org/swift-book/LanguageGuide/OptionalChaining.
html. (Accessed on 01/07/2021).
[62]

Chris Parnin, Christian Bird, and Emerson Murphy-Hill. “Java Generics Adoption: How New Features are Introduced, Championed, or Ignored”. In: Proceedings of the International Working Conference on
Mining Software Repositories. 2011.

[63]

Dominik Picheta. “Nim in Action”. In: 2017, pp. 3–21.

[64]

Jan Pittl and Amiram Yehudai. “Constructing a realtime deterministic pushdown automaton from a grammar”. In: Theoretical Computer
Science (1983).

[65]

Marco Pivetta. Fluent Interfaces are Evil. https://ocramius.github.
io/blog/fluent-interfaces-are-evil/. (Accessed on 01/07/2021).

[66]

Daryl Posnett, Abram Hindle, and Premkumar Devanbu. “A Simpler
Model of Software Readability”. In: Proceedings of the 8th Working
Conference on Mining Software Repositories. 2011.

[67]

Michael Pradel and Thomas R. Gross. “Automatic Generation of Object Usage Specifications from Large Method Traces”. In: Proceedingsof the 2009 IEEE/ACM International Conference on Automated Software Engineering. 2009.

[68]

Jon Rafkind and Matthew Flatt. “Honu: Syntactic Extension for Algebraic Notation Through Enforestation”. In: Proceedings of the 11th
International Conference on Generative Programming and Component
Engineering. 2012.

[69]

D. J. Rosenkrantz and R. E. Stearns. “Properties of Deterministic Top
Down Grammars”. In: Proceedings of the First Annual ACM Symposium on Theory of Computing. 1969.

[70]

Peter H Salus. A quarter century of UNIX. ACM Press/AddisonWesley Publishing Co., 1994.

[71]

Simone Scalabrino et al. “A comprehensive model for code readability”. In: Journal of Software: Evolution and Process (2018).

[72] Scope Functions - Kotlin Programming Language. https://kotlinlang.
org/docs/reference/scope-functions.html. (Accessed on 01/07/2021).

BIBLIOGRAPHY

119[73] SIP-23 - LITERAL-BASED SINGLETON TYPES. https : / / docs .
scala-lang.org/sips/42.type.html. (Accessed on 01/07/2021).
[74]

Robert Strom and Shaula Yemini. “Typestate: A programming language concept for enhancing software reliability”. In: IEEE Transactions on Software Engineering (1986).

[75]

Joshua Sunshine et al. “First-class State Change in Plaid”. In: Proceedings of the 2011 ACM International Conference on Object Oriented
Programming Systems Languages and Applications. 2011.

[76]

Hiroto Tanaka, Shinsuke Matsumoto, and Shinji Kusumoto. “A Studyon the Current Status of Functional Idioms in Java”. In: IEICE Transactions on Information and Systems (2019).

[77]

Robert Tarjan. “Depth-first search and linear graph algorithms”. In:
SIAM journal on computing (1972).

[78]

Ken Thompson. “Programming Techniques: Regular Expression Search
Algorithm”. In: Communications of the ACM (1968).

[79]

I. Turnu et al. “A modified Yule process to model the evolution of some
object-oriented system properties”. In: Information Sciences (2011).

[80] TypeScript 3.7 · TypeScript. https://www.typescriptlang.org/docs/
handbook/release-notes/typescript-3-7.html. (Accessed on 01/07/2021).
[81]

Todd L. Veldhuizen. C++ Templates are Turing Complete. Tech. rep.
2003.

[82]

J. Wu, R. C. Holt, and A. E. Hassan. “Empirical Evidence for SOC
Dynamics in Software Evolution”. In: 2007 IEEE International Conference on Software Maintenance. 2007.

[83]

Hao Xu. “EriLex: An Embedded Domain Specific Language Generator”. In: Objects, Models, Components, Patterns. 2010.

[84]

Tetsuro Yamazaki et al. “Generating a fluent API with syntax checking
from an LR grammar”. In: The ACM Conference on Object-Oriented
Programming Systems, Languages, and Applications. 2019.

[85]

Daniel Younger. “Recognition and parsing of context-free languages
in time n3 ”. In: Information and Control (1967).