Fluent APIs in Functional Languages (full version)
Fluent APIs in Functional Languages

See a full version of this article <cit.> and the accompanying artifact <cit.>.

Ori Roth
Yossi Gil

<concept_desc>Software and its engineering API languages</concept_desc>
<concept_desc>Software and its engineering Functional languages</concept_desc>

[500]Software and its engineering API languages
[500]Software and its engineering Functional languages

§ INTRODUCTION

An API protocol dictates a set of rules for correct API usage.
Misusing an API to contrast its protocol may result in runtime errors or undefined behavior.
The Java FileReader API protocol, for example, states that

“once the stream has been closed, further [API] invocations will throw an IOException.”[<https://docs.oracle.com/javase/8/docs/api/java/io/InputStreamReader.html#close–>]

Although protocols usually come in written form as part of the API documentation, some protocols can be formalized as grammars.
Such grammar defines the language (set) of legal sequences of API invocations.
For example, the following regular expression describes the FileReader protocol:

Specifying API protocols using grammars or automata reduces the problem of protocol verification to formal language recognition.

APIs also use grammars and automata to specify domain-specific languages (DSLs).
A DSL is a specialized language tailored for the API's problem domain.
Many applications use DSLs:
A Python machine learning model uses SQL to load its dataset, a JavaScript frontend verifies textual forms with regular expressions, and a Standard ML (SML) HTTP server serves HTML webpages.
To integrate a DSL into an application, we can implement the DSL as an API in the host programming language.
The protocol of this embedded DSL (EDSL) is the syntax of the original DSL, i.e., EDSL invocations must describe well-formed DSL programs.

This paper presents methods to create smart and elegant APIs in functional programming languages.
These APIs enforce their protocols or DSL syntax at compile time by performing language recognition at the type level.
For example, <ref> demonstrates how we embed an HTML document as an SML expression using our methodology.

[float=ht,style=sml,caption=An HTML webpage embedded in SML,label=listing:html]
val webpage = ^^
<h1> `"National Parks" </h1>
<th> `"Park Description" </th>
<th> `"Park Picture" </th>
<td> <p> <b> `"Yosemite" </b> `"national park" </p> </td>
<td> <img src "https://tinyurl.com/yosemite5"/> </td>

Our HTML EDSL is elegant in the sense that embedded webpages closely resemble HTML, with minimal syntactic overhead imposed by the host programming language.
The EDSL is smart as it coerces the SML compiler into enforcing HTML's syntax, so invalid webpages do not compile.
The tags must appear in the correct order (<html> before <body>, <tr> inside <table>, and so on), every opening tag must have a matching closing tag, and all table rows must have the same number of columns.
Note that the additional requirement on table rows elevates HTML into a context-sensitive language.

Our API designs are based on fluent API, an object-oriented pattern for embedding DSLs.
Fluent API techniques typically rely on function overloading, a common object-oriented feature not supported by many functional type systems.
We adapt fluent APIs to functional settings by replacing overloading with parametric polymorphism and type inference.
Our fluent APIs do not rely on a specific language feature, so they are compatible with most statically-typed functional languages.

§.§ Related Work

A typestate <cit.> determines the type's set of permitted operations in a given program context.
The FileReader typestate, for example, disallows invoking read after close is called.
Typestates are used as a first-class abstraction for protocols <cit.>.
Another approach is to infer and verify typestates and API protocols statically <cit.>.
<cit.> developed a static analysis method for enforcing API protocols specified by context-free grammars.
Similarly, the current work uses automata specifications for API protocols.
Instead of using an external tool or a dedicated language feature, our fluent API designs use the host language compiler to enforce the protocol by ensuring that protocol violations result in type errors.

Language workbenches <cit.> such as Xtext <cit.>, MPS <cit.>, and MetaEdit+ <cit.> are development environments for creating DSL development tools.
The Spoofax language workbench, for instance, compiles DSL specifications into a full-fledged DSL IDE <cit.>.
SugarJ <cit.>, Polyglot <cit.>, and Racket <cit.> are examples of extensible programming languages in which the syntax of the language can be extended to incorporate DSLs.
By embedding the DSL as a fluent API, our techniques work out of the box in statically-typed functional languages.

Programming languages with powerful compile-time metaprogramming support provide a direct solution to DSL embedding <cit.>.
MetaML <cit.>, MetaOCaml <cit.>, and Template Haskell <cit.> extend existing programming languages with macro systems that enable DSL code generation at compile time.
Evidently, Haskell is expressive enough to embed DSLs even without templates.
Haskell supports ad hoc polymorphism through type classes <cit.>, shown to be useful for DSL embedding <cit.>.
EDSLs often employ Haskell's -statement and monadic comprehensions <cit.>, especially in parser combinator libraries <cit.>.
In contrast to previous approaches, functional fluent APIs do not rely on any macro system, language extension, or special control structure.
Some of the Haskell EDSL techniques are ad hoc, whereas our fluent API solutions support well-defined classes of DSLs, namely all regular and deterministic context-free languages.

Existing fluent API designs generally do not apply to functional languages because of their lack of function overloading.
Enhancing functional languages with ad hoc polymorphism, e.g., as proposed by <cit.>, <cit.>, and <cit.>, may enable these designs to work in functional settings.
<cit.> managed to encode fluent APIs in Haskell by using typeclasses and a few language extensions.
Their work and other modern fluent API designs are discussed in <ref>.
Our fluent APIs overcome the overloading problem by avoiding it altogether in favor of rudimentary functional features.

Indeed, we chose SML as the main language used throughout the paper for its relative simplicity.
Noting SML's rich module system <cit.>, we limit ourselves to core language constructs <cit.>.

Fluent API in SML is not a new concept:
<cit.> presented a fluent API-like EDSL eight years before the term was even coined <cit.>.

§.§ Contributions

We present different algorithms for encoding fluent APIs in functional languages.
Our fluent API designs support all regular and deterministic context-free API protocols and DSLs and can be implemented in most statically-typed functional languages.
This work is accompanied by an SML implementation of key algorithms.
The appendix includes a series of experiments conducted using the implementation.
The full paper <cit.> describes a series of experiments conducted using the implementation.

The rest of the paper is organized as follows.
<Ref> covers preliminary knowledge in automata theory and object-oriented fluent APIs.
The next three sections present three methods for encoding regular protocols as functional fluent APIs:
bit shuffling in <ref>, Church Booleans in <ref>, and tabulation in <ref>.
In <ref> we show how to extend these techniques to non-regular protocols.
<Ref> concludes with a discussion on functional fluent APIs and a comparison of the various encoding methods.

§ PRELIMINARIES

§.§ Automata and Formal Languages

We assume that the reader is familiar with the structure and operation of deterministic finite state machines (FSMs) and pushdown automata (DPDA).
Here we briefly review some definitions;
for the full theoretical background, we recommend <cit.>.

FSMs recognize the class of regular languages.
An FSM $M$ is a tuple $M=\langle Q, \Sigma, q_0, \delta, F \rangle$, where $Q$ is a finite set of states, $\Sigma$ is a finite set of input letters, $q_0 \in Q$ is the initial state, $\delta:Q\times\Sigma\rightarrow Q$ is the (partial) transition function, and $F \subseteq Q$ is the set of accepting states.
Let $\delta_\sigma:Q\rightarrow Q$ be $\delta$'s projection on $\sigma$, i.e., $\delta(q, \sigma)=p \Leftrightarrow \delta_\sigma(q)=p$.

The run of word $w=\sigma_1\sigma_2\ldots\sigma_n \in \Sigma^*$ on FSM $M$ is a sequence of states $\rho=p_0p_1\cdots p_n$ such that $p_0=q_0$ and for every $i=1,\ldots,n$, $\delta(p_{i-1}, \sigma_i) = p_i$.
We say that $M$ accepts $w$ if and only if $p_n \in F$; otherwise $M$ rejects $w$.
The language of $M$, $L(M)$ is the set of words $M$ accepts.
Consider, for example, the FSM depicted in <ref> in graph form.
This FSM recognizes the language $(a^4)^*$ containing all sequences of the letter $a$ whose length is a multiple of four.

[node distance=10ex]
[state,initial,accepting] (q0) $q_0$;
[state,right of=q0] (q1) $q_1$;
[state,below of=q1] (q2) $q_2$;
[state,below of=q0] (q3) $q_3$;
(q0) edge[above] node$a$ (q1)
(q1) edge[right] node$a$ (q2)
(q2) edge[below] node$a$ (q3)
(q3) edge[left] node$a$ (q0);

An FSM accepting the language $(a^4)^*$

A DPDA is an FSM that uses an auxiliary pushdown store
of stack symbols drawn from a finite set $\Gamma$.
The DPDA transition function is
\[
\delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma\rightarrow Q\times\Gamma^*
\]

In each computation step, the automaton reads symbol $\gamma \in \Gamma$ on the stack and replaces it with a (possibly empty) sequence of symbols $\boldsymbol\gamma \in \Gamma^*$.
If the the automaton tries to read from an empty stack, it gets stuck and rejects the input word.
A DPDA transition can consume an input letter $\sigma \in \Sigma$ or $\varepsilon$, the empty word.
These $\varepsilon$-transitions are used to modify the stack between input reads.
A DPDA without $\varepsilon$-transitions is called a real-time DPDA, as it makes exactly one operation for each input letter.
DPDAs recognize the class of deterministic context-free languages (DCFLs), a proper super-set of regular languages.
For instance, a DPDA can recognize the Dyck language of balanced brackets, but an FSM cannot.

§.§ Encoding Automata as Fluent APIs in Object-Oriented Programming Languages

The traditional study of compiler design <cit.> provides many parser generation techniques that take formal language specifications and convert them into parsers.
Similarly, the academic study of fluent APIs seeks DSL embedding techniques that encode DSL specifications (usually in automaton form) as fluent APIs.
We now review some of the existing fluent API encoding methods, designed primarily for object-oriented host languages.

Encoding an FSM as a fluent API is easy.
First, create class q for each state $q \in Q$.
Then, for each transition $\delta(q, \sigma)=p$, add the method $\sigma$:q$\rightarrow$p to class q.
This method receives an (implicit) parameter of type q and returns an instance of class p.
Finally, add a special method [literate=*D$1]D only to classes of accepting states $q_F \in F$ (its return type does not matter).
A fluent chain of API calls (chain for short) starts with an initial variable __ of type $q_0$, followed by a sequence of API calls $\sigma_1,\sigma_2,\ldots,\sigma_n\in\Sigma$, and ends with a call to [literate=*D$1]D:

\begin{equation}\label{eq:fluent}
\text{\inline[language=java,literate=*{D}{\textdollar}{1}]{__().$\sigma_1$().$\sigma_2$().$\ldots$.$\sigma_n$().D()}}
\end{equation}

For example, the fluent API in <ref> encodes the language $(a^4)^*$ as defined by the FSM in <ref>.
The fluent API is followed by several chain examples in the form of <ref>.
A given chain type checks if and only if the number of times it calls a() is a multiple of four.
We say that the fluent API enforces (encodes, specifies, recognizes) the language $(a^4)^*$.

[float=ht,language=java,caption=A Java fluent API encoding the language $(a^4)^*$,label=listing:fluent:a4]
interface q0  q1 a(); /* $\color{comment}\delta(q_0,a)=q_1$ */ void $(); /* $\color{comment}q_0 \in F$ */
interface q1  q2 a(); /* $\color{comment}\delta(q_1,a)=q_2$ */
interface q2  q3 a(); /* $\color{comment}\delta(q_2,a)=q_3$ */
interface q3  q0 a(); /* $\color{comment}\delta(q_3,a)=q_0$ */
q0 __ = null; // /* $\color{comment}q_0$ is the initial state
/* example chains */
__.$(); // compiles, $\varepsilon \in L((a^4)^*)$
__.a().a().a().a().$(); // compiles, $a^4 \in L((a^4)^*)$
__.a().a().a().$(); // does not compile, $a^3 \not\in L((a^4)^*)$

So, how does it work?
The chain <ref>
essentially simulates the FSM run $\rho=p_0p_1\cdots p_n$ of the word $w=\sigma_1\sigma_2\ldots\sigma_n$ encoded in the chain.
That is, the return type of $\sigma_i$() in <ref>, $i=1,2,\ldots,n$ is $p_i$.
Starting with the initial variable __ of type $q_0$, the initial state, adding a call to $\sigma_i$() yields the type $\delta(p_{i-1},\sigma_i)=p_i$.
The call $\sigma_n$() returns an instance of class $p_n$, so the next call, to the terminal function [literate=*D$1]D(), compiles if and only if $p_n \in F$, which is exactly the FSM membership condition.

Notice that method a in <ref> is overloaded, since it has four different signatures: a:q0$\rightarrow$q1, a:q1$\rightarrow$q2, a:q2$\rightarrow$q3,
and a:q3$\rightarrow$q0.
In general, this construction induces overloading whenever letter $\sigma \in \Sigma$ appears in more than one FSM transition.

Although challenging, it is possible to encode non-regular languages as fluent APIs <cit.>.
We focus on the “tree encoding” of DPDAs introduced by <cit.>.
Gil and Roth presented an algorithm for converting a DPDA $A$ into a tree encoding that can be written as a fluent API.
The resulting fluent APIs look very similar to what we saw in <ref>, except that they use parametric polymorphism (generics, type parameters).
<Ref> demonstrates how generics are used in the construction of a fluent API from tree encoding.
The listing contains a generic fluent API that recognizes the Dyck language—a well-known DCFL.
The chain examples that follow the fluent API compile if and only if they encode balanced left (L) and right (R) brackets.
The fluent API works by encoding the number of open brackets as a Peano number s<s<$\ldots$s<z>$\ldots$>> in the chain's return types.

[float=ht,language=java,caption=A Java fluent API encoding the Dyck language of balanced / brackets,label=listing:fluent:dyck]
interface z  s<z> L(); void $();
interface s<x>  s<s<x>> L(); x R();
z __ = null; // we only care about type checking at the moment
/* example chains */
__.L().L().L().R().R().R().$(); // compiles, the sequence ((())) is balanced
__.L().L().R().L().R().R().$(); // compiles, the sequence (()()) is balanced
__.L().R().R().$(); // does not compile, the sequence ()) is not balanced
__.L().L().R().$(); // does not compile, the sequence (() is not balanced

We see Gil and Roth's tree encoding algorithm as a black box.
We only care about the structure of the fluent APIs it yields, as demonstrated in <ref>.
In general, the tree encoding algorithm results in classes c0, c1, …, cm with zero or more type parameters, ci<x0, x1, $\ldots$, xn>.
Functions' return types are general terms over the available classes c0–cm and parameters x0–xn, e.g., c1<c2<x3, c3>, x1>.
Note that the tree encoding algorithm, as well as the encoding techniques proposed in the papers cited above, rely on overloading similarly to the FSM case.

§.§ A Note on Typeclasses and Fluent APIs

The object-oriented fluent API techniques mentioned above, including the more advanced designs of <cit.> and <cit.>, can be adapted to functional programming languages by substituting typeclasses for function overloading.
Typeclasses were introduced by <cit.> as a formalism for ad hoc polymorphism in Haskell and other functional programming languages.
Wadler and Blott defined the semantics of typeclasses by translating them to the standard Hindley-Milner type system.
This translation method was later called dictionary passing.
<Ref> demonstrates how to use dictionary passing to implement an “overloaded” function in SML.

[float=ht,style=sml,caption=Dictionary passing in SML,label=listing:dictionary:passing]
fun square (numD:  mul: 'a -> 'a -> 'a ) x = #mul numD x x (* an "overloaded" square function *)
fun mulInt (a: int) (b: int) = a * b (* multiplication of integers *)
val intD =  mul = mulInt  (* int dictionary *)
fun mulReal (a: real) (b: real) = a * b (* multiplication of real numbers *)
val realD =  mul = mulReal ; (* real dictionary *)
square intD 2; (* $\color{comment}\Rightarrow$ 4: int *)
square realD 3.0; (* $\color{comment}\Rightarrow$ 9.0: real *)

Function square in <ref> accepts integers and real numbers.
We tell square how to multiply numbers by passing it a dictionary numD that points to the appropriate multiplication method: intD for integers and realD for real numbers.

Although dictionary passing is semantically equivalent to typeclasses, it is not a viable alternative for function overloading.
Matching each argument type with a dictionary (intD, realD) takes the same effort from the programmer as having multiple functions (squareInt, squareReal).
In Wadler and Blott’s original design, the compiler infers the dictionary from the argument type, so the programmer doesn't have to specify it explicitly.

§ BIT SHUFFLING

The fluent API encoding techniques described in <ref> use function overloading and, therefore, cannot be used in functional languages such as SML.
This section presents bit shuffling, the first of our three alternative methods for encoding FSMs as functional fluent APIs.
This method is unique in that it does not rely on unification, resulting in relatively fast compilation even when enforcing highly complex API protocols.

The crux of the new design is seeing the FSM states as binary vectors and the FSM transitions as a collection of Boolean functions over these vectors.
The current FSM state is encoded using a tuple of types f and t that represent the bits 0 and 1.
Each API function applies a certain transformation onto this tuple by shuffling the bits comprising it:

\[
\inline{(f, t, f, t)} \implies \inline{(t, f, f, t)}
\]

If the shuffling is done correctly, the resulting tuple encodes the subsequent FSM state.

We start by constructing a fluent API for the language $(a^4)^*$, as defined by the FSM in <ref> (this will be our running example).
Then, we generalize the construction steps for any FSM and assemble them into <ref>.

First, however, we define some notations.
A Boolean bit $b$ is a member of $\{0, 1\}$.
We also denote Boolean bits as false, f, and F or true, t, and T.
A Boolean vector $v$ of length $n$ is a sequence of $n$ Boolean bits, $v \in \{0, 1\}^n$.
We write $v$ as $\langle b_n, \ldots, b_2, b_1 \rangle$ (indexed from the right to the left) or as $b_n\cdots b_2b_1$ for short.
An $n$-ary Boolean function $f:\{0, 1\}^n\rightarrow\{0, 1\}$ accepts a Boolean vector of length $n$ and returns one Boolean bit.
An $n$-ary Boolean vector function $\boldsymbol{f}:\{0, 1\}^n\rightarrow\{0, 1\}^n$ accepts a Boolean vector of length $n$ and returns a vector of the same length.
A Boolean vector function can be decomposed into $n$ Boolean functions $\boldsymbol{f}=\langle f_n, \ldots, f_2, f_1 \rangle$ such that $f_i$ computes the $i$bit of $\boldsymbol{f}$,
\[
\boldsymbol{f}(v) = \langle f_n(v), \ldots, f_2(v), f_1(v) \rangle
\]

The composition of Boolean function $g$ and vector function $\boldsymbol{f}$ is defined by

\begin{equation*}\label{eq:composition}
(g \circ \boldsymbol{f})(v)=g(\boldsymbol{f}(v))
\end{equation*}

Finally, the composition of Boolean vector functions $\boldsymbol{g}$ and $\boldsymbol{f}$ is defined as
\[
\boldsymbol{g} \circ \boldsymbol{f} = \langle g_n \circ \boldsymbol{f}, \ldots, g_2 \circ \boldsymbol{f}, g_1 \circ \boldsymbol{f} \rangle
\]

Note that $(\boldsymbol{g} \circ \boldsymbol{f})(v)=\boldsymbol{g}(\boldsymbol{f}(v))$.

We are now ready to describe the FSM encoding steps.

§.§ Step I: Binary Encoding of States and Transitions

Encode the automaton states $Q=\{q_0, q_1, q_2, q_3\}$ as Boolean vectors of length $\log(|Q|)=2$ using an arbitrary injective mapping $\beta: Q\rightarrow\{0, 1\}^2$:

\begin{equation*}\label{eq:beta}
\begin{aligned}
\beta(q_0)&=00 \\
\beta(q_1)&=01 \\
\beta(q_2)&=10 \\
\beta(q_3)&=11
\end{aligned}
\end{equation*}

Recall that $\delta_a$ is the projection of the transition function $\delta$ on letter $\sigma=a$.
Now, construct a Boolean vector function $\boldsymbol{f}^a$ such that $\boldsymbol{f}^a(\beta(q))=\beta(p) \Leftrightarrow \delta_a(q)=p$:

\begin{equation}\label{eq:f}
\begin{aligned}
\boldsymbol{f}^a(00)&=01 \\
\boldsymbol{f}^a(01)&=10 \\
\boldsymbol{f}^a(10)&=11 \\
\boldsymbol{f}^a(11)&=00
\end{aligned}
\end{equation}

Let $\boldsymbol{f}^a=\langle f^a_2, f^a_1 \rangle$.
Notice that $f^a_2$ is exclusive or (XOR), $f^a_2=\oplus$ and $f^a_1$ is negation (NOT) applied to the LSB, $f^a_1=\neg_1$, so we can write
\[
\boldsymbol{f}^a=\langle \oplus, \neg_1 \rangle
\]

Observe that we can describe the FSM run on word $w=a^n$ using a sequence of $n$ applications of $\boldsymbol{f}^a$:

\begin{equation*}\label{eq:shuffling:run}
(\boldsymbol{f}^a \circ \boldsymbol{f}^a \circ \ldots \circ \boldsymbol{f}^a)(\beta(q_0))=\beta(p_n)
\end{equation*}

where $p_n$ is the last state in $w$'s run
(this observation is proved by a simple induction on $n$).
We can say that $\boldsymbol{f}^a$ consolidates the four FSM transitions comprising $\delta_a$ into a single Boolean vector function.

Intuitively, the consolidation of FSM transitions into a single function helps us overcome the overloading problem, which arose in the first place because of the multiplicity of transitions.
It is not enough, however, to implement $\boldsymbol{f}^a$ as a function on Boolean vectors.

\begin{equation}\label{eq:shuffling:chain}
\text{\inline[literate=*{D}{\textdollar}{1}{C}{\textasciicircum}{1}]{CC a a\ $\ldots$ a D}}
\end{equation}

be a functional fluent chain, with [literate=*Cˆ1]CC replacing __ as the initial variable (now a function).
We want the chain <ref> to compile if and only if the number of times a is called is a multiple of four, i.e., if the chain encodes a word $w \in L((a^4)^*)$.
Yet, if we implement the fluent API as a product of Boolean vector functions, say,
val ^^ = (false, false) (* $\color{comment}\beta(q_0)=00$ *)
fun a (b2, b1) = (b2 xor b1, not b1) (* $\color{comment}\boldsymbol{f}^a=\langle\oplus,\neg_1\rangle$ *)
fun $ (b2, b1) = if not b2 andalso not b1 then () else raise Fail "!" (* $\color{comment}q \in F \Leftrightarrow \beta(q)=00$ *)

the bits b2 and b1 would be evaluated at run time, but the fluent API must inspect them at compile time in order to fail compilation (if needed).
To make the Boolean values available at compile time, we implement them as constants of different types:
datatype t = T (* 1, true Boolean *)
and f = F (* 0, false Boolean *)

The return type of [style=sml]fun a (b2, b1), now however, depends on the specific types of its arguments, which brings us back to the overloading problem.
We address this issue in Step II.

§.§ Step II: Direct Encoding of Boolean Function Evaluations

Consider the following Boolean functions:

\begin{equation}\label{eq:gs}
\begin{aligned}
g^1(b_2b_1) &= b_2 \wedge b_1 \\
g^2(b_2b_1) &= b_2 \wedge \neg b_1 \\
g^4(b_2b_1) &= \neg b_2 \wedge b_1 \\
g^8(b_2b_1) &= \neg b_2 \wedge \neg b_1
\end{aligned}
\end{equation}

Function $g^8$ can be used to check our FSM's acceptance condition, since
\[
q \in F \iff q=q_0 \iff g^8(\beta(q))=1
\]

In the bit shuffling method, the terminal function [literate=*D$1]D does not evaluate $g^8$ by itself, but instead receives its evaluation as an argument g8 (to replace b2 and b1).
Then, it is a simple matter to check that the type of g8 is t, i.e., that $g^8(\beta(p_n))=1$.

Let $w=a^n$ be the word encoded by the fluent chain <ref>, and let $\rho=p_0p_1\cdots p_n$ be its run.
The initial variable [literate=*Cˆ1]CC assigns g8=T, since
\[
\]

The API function a should receive in parameter g8 the evaluation of $g^8(\beta(p_i))$ and return the evaluation of $g^8(\beta(p_{i+1}))$.
Since $\boldsymbol{f}^a(\beta(q))=\beta(p) \Leftrightarrow \delta_a(q)=p$ (see <ref>), $g^8(\beta(p_{i+1}))$ can be computed as follows:
\[
g^8(\beta(p_{i+1})) =
g^8(\beta(\delta_a(p_i))) =
g^8(\boldsymbol{f}^a(\beta(p_i))) = \ldots
\]

Let $\beta(p_i)=b_2b_1$. We continue:
\[
\ldots =
g^8(\boldsymbol{f}^a(b_2b_1)) =
g^8(\langle b_2 \oplus b_1, \neg b_1\rangle) =
\neg(b_2 \oplus b_1) \wedge b_1 =
b_2 \wedge b_1 =
g^1(b_2b_1) =
\]

(Function $g^1$ is defined in <ref>.)
Overall, we get
\begin{equation}\label{eq:g8}
g^8(\beta(p_{i+1}))=(g^8 \circ \boldsymbol{f}^a)(\beta(p_i))=g^1(p_i)
\end{equation}

i.e., the evaluation of $g^8$ on the next state $p_{i+1}$ is equal to applying the composition $g^8 \circ \boldsymbol{f}^a$ to the current state $p_i$, which in turn equals the evaluation of another function $g^1$ on $p_i$.

We let a receive the value of $g^1(\beta(p_i))$ in yet another parameter g1.
We then continue recursively to compute $g^1(\beta(p_{i+1}))$, in a similar way to how $g^8(\beta(p_{i+1}))$ was computed:

\begin{equation}\label{eq:g1:g2:g4}
\begin{aligned}
g^1(\beta(p_{i+1}))=(g^1\circ \boldsymbol{f}^a)(\beta(p_i))=g^2(\beta(p_i)) \\
g^2(\beta(p_{i+1}))=(g^2\circ \boldsymbol{f}^a)(\beta(p_i))=g^4(\beta(p_i)) \\
g^4(\beta(p_{i+1}))=(g^4\circ \boldsymbol{f}^a)(\beta(p_i))=g^8(\beta(p_i))
\end{aligned}
\end{equation}

The recursion ends on $g^8(\beta(p_i))$, since this value is already given in parameter g8.
Let $\boldsymbol{g}=\langle g^1, g^2, g^4, g^8 \rangle$ (the ordering of functions in $\boldsymbol{g}$ does not matter).
<Ref> can be summarized as follows:

\begin{equation}\label{eq:g}
\boldsymbol{g} \circ \boldsymbol{f}^a = \langle g^2, g^4, g^8, g^1 \rangle
\end{equation}

Thus, function a receives a quadruple (g1, g2, g4, g8) representing the four evaluations of $g^j(\beta(p_i))$, $j=1, 2, 4, 8$, and returns the evaluations of $g^j(\beta(p_{i+1}))$ by shuffling the quadruple into (g2, g4, g8, g1) following <ref>.

The resulting fluent API is shown in <ref>.
The addition of parameter [style=sml]f' to functions [literate=*Cˆ1]CC and a allows us to call them in fluent form, i.e., from the left to the right as in <ref>.

[float=ht,style=sml,caption=A shuffling SML fluent API for the FSM of <ref>,label=listing:shuffle:a4]
datatype t = T (* 1, true Boolean *)
and f = F (* 0, false Boolean *)
fun ^^ f' = f' (F, F, F, T) (* $\color{comment}\langle g_1, g_2, g_4, g_8 \rangle(\beta(q_0))=\langle g_1(00), g_2(00), g_4(00), g_8(00) \rangle=0001$ *)
fun a (g1, g2, g4, g8) f' = f' (g2, g4, g8, g1) (* $\color{comment}\langle g_1, g_2, g_4, g_8 \rangle \circ \boldsymbol{f}^a = \langle g_2, g_4, g_8, g_1 \rangle$ *)
fun $ (_, _, _, T) = (); (* $\color{comment}q \in F \Leftrightarrow g_8(\beta(q))=1$ *)
(* chain examples: *)
^^ $; (* OK, $\color{comment}\varepsilon\in L((a^4)^*)$ *)
^^ a a a a $; (* OK, $\color{comment}a^4\in L((a^4)^*)$ *)
^^ a a a a a a a a $; (* OK, $\color{comment}a^8\in L((a^4)^*)$ *)
^^ a $; (* error, $\color{comment}a^1\not\in L((a^4)^*)$ *)
^^ a a $; (* error, $\color{comment}a^2\not\in L((a^4)^*)$ *)
^^ a a a a a $; (* error, $\color{comment}a^5\not\in L((a^4)^*)$ *)

The fluent API in <ref> is followed by a few fluent chain examples.
Notice that a chain compiles if and only if the number of a calls is a multiple of four, i.e., if the chain encodes $w \in L((a^4)^*)$.

§.§ The Bit Shuffling Encoding Algorithm

We now generalize the encoding steps described in <ref> and present an algorithm for any FSM $M$.
FSMs are, in general, more complicated than our example FSM, so we need to add some minor steps to the encoding process.
First off, notice that our example FSM, depicted in <ref>, has a total transition function $\delta$, i.e., every state has an outgoing edge for each input letter, and the number of states $|Q|=4$ is a power of two.
These properties make the Boolean vector function $\boldsymbol{f}^a$ well-defined, i.e., $\boldsymbol{f}^a(v)$ is defined for any Boolean vector of length $n=\log(|Q|)$.
Given an FSM $M$, we make its transition function total by adding a non-accepting sink state, to which the missing transitions are directed.
The sink state loops for any letter $\sigma\in\Sigma$.
We then complete the number of states to a power of two by, again, adding sink states.
These modifications result in automaton $M'=\langle Q', \Sigma, q_0, F, \delta'\rangle$ that accepts the same language as $M$, $L(M')=L(M)$.

Let $n=\log(|Q'|)$, $n\in\mathbb{N}$ be the number of bits in mapping $\beta$.
Our example fluent API required the evaluation of four Boolean functions, $g^1$, $g^2$, $g^4$, and $g^8$.
Instead of calculating which $g^i$ functions are required for $M'$, we just take all the Boolean functions on $n$ bits, $\boldsymbol{g}^n=\langle g^1, g^2, g^3, \ldots\rangle$ (there is a finite number of such functions).

In addition, notice that the example language $(a^4)^*$ uses only a single letter $a$, but we want to support alphabets $\Sigma$ of any finite size.
Given alphabet $\Sigma$ of arbitrary size, we simply repeat the encoding steps described above for each letter $\sigma \in \Sigma$, i.e., compute $\boldsymbol{f}^\sigma$ and $\boldsymbol{g}^n \circ \boldsymbol{f}^\sigma$ and encode the result in a function $\sigma$.

Finally, the example FSM specifies a single accepting state $F=\{q_0\}$, but FSMs in general may have multiple accepting states.
Therefore, we need to find a Boolean function $g^F$ such that $g^F(\beta(q))=1 \Leftrightarrow q \in F$.
There must be (exactly one) such function in $\boldsymbol{g}^n$.
The terminal function simply checks that the type of parameter gF, holding the evaluation of $g^F$, is t.

The complete bit shuffling algorithm is presented in <ref>.

The bit shuffling algorithm for encoding an FSM as an SML fluent API

[1]
FSM $M=\langle Q, \Sigma, q_0, F, \delta\rangle$
[style=sml]datatype t = T and f = F
Construct FSM $M'=\langle Q', \Sigma, q_0, F, \delta'\rangle$ from $M$ by making the transition function $\delta$ total and adding states until $|Q'|$ is a power of two (both using sink states)
$\boldsymbol{g}^n$all Boolean functions on $n$ bits
$\beta$an injective mapping $\beta:Q'\rightarrow \{0, 1\}^n$
[style=sml,literate=*Cˆ1]fun CC f' = f' $\boldsymbol{g}^n(\beta(q_0))$
$\boldsymbol{f}^\sigma$a mapping $\{0, 1\}^n\rightarrow\{0, 1\}^n$ such that $\boldsymbol{f}^\sigma(\beta(q))=\beta(p) \Leftrightarrow \delta_\sigma(q)=p$
[style=sml]fun $\sigma$ $\boldsymbol{g}^n$ f' = f' $\boldsymbol{g}^n \circ \boldsymbol{f}^\sigma$
$g^F$the (one and only) function in $\boldsymbol{g}^n$ such that $g^F(\beta(q))=1 \Leftrightarrow q \in F$
[style=sml,literate=*D$1Eto 1em...1]fun D (_, E, _, T, _, E, _) = () where T appears in the position of $g^F$ in $\boldsymbol{g}^n$

Some of the code excerpts printed in <ref> contain mathematical symbols—we now explain how these are rendered as text:

* A Boolean bit $b$ is rendered as T if $b=1$ or as F if $b=0$.

* A Boolean vector $v=\langle b_n, \ldots, b_2, b_1 \rangle$ is rendered as a tuple [literate=*Eto 1em...1]($b_n$, E, $b_2$, $b_1$).

* A Boolean function $g$ is rendered as g, i.e., we ignore its intent and print its name.

* A Boolean vector function $\boldsymbol{g}=\langle g_1, g_2, \ldots, g_n \rangle$ is rendered as a tuple [literate=*Eto 1em...1]($g_1$, $g_2$, E, $g_n$).

§.§ Encoding Improvements

We now propose two optional improvements of the bit shuffling algorithm as it is described in <ref>.
First, notice that <ref> computes all the binary functions on $n=\log(|Q'|)$ bits.
Overall, there are
\[
2^{2^n}=2^{|Q'|}\le 2^{2|Q|}=4^{|Q|}
\]
such functions, so the run time of the algorithm, as well as the size of the code it prints, are exponential in the size of the FSM.
Nevertheless, our example fluent API (<ref>) uses only four of these functions (out of 16), indicating that it might be possible to get rid of at least some functions.
To determine which functions are necessary and which can be omitted, we run the recursive procedure described in <ref>:
Start with $\boldsymbol{g}^n=\langle g^F\rangle$, and recursively add function $g$ if there exists $\sigma \in \Sigma$ and $g' \in \boldsymbol{g}^n$ such that $g' \circ \boldsymbol{f}^\sigma = g$.
From our experience, this construction of $\boldsymbol{g}^n$ reduces its size significantly for “reasonable” FSMs.
Determining the exact degree to which $\boldsymbol{g}^n$ is reduced and, specifically, whether or not its sizes stays exponential in $|Q|$, is left as an open problem.

The second improvement relates to the fluent API user experience.
The fluent API printed by <ref> allows any sequence of API calls to be made and checks whether or not it makes sense only in the terminal method [literate=*D$1]D.
Therefore, the programmer using the fluent API is not alerted when they call a wrong API method, and when they do (on calling [literate=*D$1]D), they are not told where the mistake is located.

\begin{equation}\label{eq:fluent:partial}
\text{\inline[literate=*{C}{\textasciicircum}{1}]{CC\ $\sigma_1$\ $\sigma_2$\ $\ldots$\ $\sigma_n$}}
\end{equation}

be a partial fluent chain encoding $w=\sigma_1\sigma_2\cdots\sigma_n$, and let $\rho=p_0p_1\cdots p_n$ be $w$'s run on the FSM.
To make our fluent API more user friendly, we ensure that a call to $\sigma_{n+1} \in \Sigma$ after <ref> will not compile if the resulting chain cannot be completed correctly by some sequence of API calls.
We call this property of fluent APIs early failure.

Let $R \subseteq Q$ be the set of states from which an accepting state is reachable (when viewing the FSM in graph form).
Then, the call to $\sigma_{n+1}$ should compile if and only if
\begin{equation}\label{eq:r}
\delta(p_n, \sigma_{n+1})\in R
\end{equation}

We can check this condition using the Boolean function $g^R$ (similar to $g^F$ used by [literate=*D$1]D) that holds
\[
g^R(\beta(q))=1 \iff q \in R
\]

We require that the evaluation of $g^R$, stored in parameter gR, is always true throughout the chain to achieve early failure.
Let $\sigma\in\Sigma$ be an API function, and let gi be the parameter it assigns in the position of gR in the shuffled tuple on function $\sigma$'s right-hand side, i.e., $g^R(\beta(p_{j+1}))=g_i(\beta(p_j))$.
If $g^R$ evaluates to false after calling $\sigma$, then our encoding ensures that gi is also false.
Function $\sigma$ should, accordingly, check that the type of gi is t by replacing the parameter gi with T, as done in function [literate=*D$1]D for parameter gF.

When the two improvements described above are applied together, the recursive construction of $\boldsymbol{g}^n$ should start with $\boldsymbol{g}^n=\langle g^F, g^R \rangle$ to ensure that the parameter gR is present in the final vector.

§ CHURCH BOOLEANS

This section describes our fluent API encoding method based on the Church encoding of Booleans.
In contrast to bit shuffling, presented in <ref>, the current technique relies on type inference and thus incurs longer compilation times.
Nevertheless, our technique demonstrates an application of the classic Church Booleans to API design which, we believe, is a fascinating concept whose full potential is beyond the scope of the current paper.

Recall that bit shuffling encodes FSM states as Boolean vectors and FSM transitions as functions over these vectors.
The same idea is at the base of our Church encoding.
But instead of pre-computing function evaluations, as done in bit shuffling, the new technique directly computes bit functions at compile time by replacing the true and false monotypes with the Church Booleans.
While Church Boolean circuits are usually applied in an untyped manner, they work mostly the same at the type level, except for a minor digression: duplicating a bit into two identical bits must be expressed explicitly using a fanout gate.

Before presenting the encoding, we review Church Booleans and how they can be implemented in SML:
fun T x y = x (* true, T : 'a$\color{comment}\rightarrow$'b$\color{comment}\rightarrow$'a *)
fun F x y = y (* false, F : 'a$\color{comment}\rightarrow$'b$\color{comment}\rightarrow$'b *)

True is a function that receives two arguments (Currying style) and returns the first;
False also receives two parameters but returns the latter.
The type of true is [style=sml]T:'a->'b->'a and the type of false is [style=sml]F:'a->'b->'b.

These are the Church Boolean functions:[If you try to run this code using SML/NJ, you will get “dummy types” instead of plain [style=sml]'a and [style=sml]'b type parameters. We ignore dummy types in the current discussion.]
fun Not b = b F T
fun Or (b2, b1) = b2 T b1
fun And (b2, b1) = b2 b1 F;
Not T; (* false, 'a$\color{comment}\rightarrow$'b$\color{comment}\rightarrow$'b *)
Or (And (T, F), And (T, T)); (* true, 'a$\color{comment}\rightarrow$'b$\color{comment}\rightarrow$'a *)

Can we use these simple Boolean functions to describe complex Boolean circuits?
The following attempt fails to compile:
fun Xor (b2, b1) = Or (And (b2, Not b1), And (Not b2, b1));
Xor (T, F); (* compilation error: circularity *)

Evidently, the SML compiler fails to assign reasonable types to the parameters of function Xor.
<cit.> explains that function Xor is problematic because it is non-linear, in the sense that it uses the bits b2 and b1 more than once in the same expression.
To restore linearity, Mairson proposes to explicitly implement a fanout gate Copy that takes a single bit and returns two equivalent bits:
fun Pair x y z = z x y
fun Copy p = p (Pair T T) (Pair F F)

Function Copy is used this way:
\[
\text{\inline[style=sml]{Copy b (fn b1 => fn b2 =>\ $e$)}}
\]

Copy evaluates the inner expression $e$ by assigning b's type (Boolean value) to b1 and b2.
Therefore, $e$ can use two instances b1 and b2 of the same Boolean bit b.
Let us re-implement Xor using Copy:
fun Xor (b2, b1) =
Copy b2 (fn b2_1 => fn b2_2 =>
Copy b1 (fn b1_1 => fn b1_2 =>
Or (And (b2_1, Not b1_1), And (Not b2_2, b1_2))
Xor (T, F); (* true, 'a->'b->'a *)
Xor (F, F); (* false, 'a->'b->'b *)

After learning how to compute complex Boolean circuits at compile time, we are ready to describe the Church encoding of fluent APIs.
Again, we start by encoding a fluent API for our example language $(a^4)^*$ and then generalize the construction for any FSM in <ref>.
The first step of the encoding is identical to Step I of bit shuffling (described in <ref>), so we can continue straight to the second step.

§.§ Step II: Encoding FSM States as Vectors of Church Booleans

In Step I (<ref>) we constructed mapping $\beta: Q \rightarrow \{0, 1\}^2$ from states to bit vectors.
Function $\beta$ is used to encode the FSM states $Q$ as Church Boolean vectors:
val q0 = (F, F) (* $\color{comment}q_0=00$, q0 : ('a->'b->'b) * ('c->'d->'d) *)
val q1 = (F, T) (* $\color{comment}q_1=01$, q1 : ('a->'b->'b) * ('c->'d->'c) *)
val q2 = (T, F) (* $\color{comment}q_2=10$, q2 : ('a->'b->'a) * ('c->'d->'d) *)
val q3 = (T, T) (* $\color{comment}q_3=11$, q3 : ('a->'b->'a) * ('c->'d->'c) *)

We also defined the vector function $\boldsymbol{f}^a:\{0, 1\}^2\rightarrow \{0, 1\}^2$ where
\[
\boldsymbol{f}^a(\beta(q))=\beta(p) \iff \delta_a(q)=p
\]

This function can be described as a composition of two Boolean functions $\boldsymbol{f}^a=\langle \oplus, \neg_1 \rangle$, i.e.,
\[
\boldsymbol{f}^a(b_2b_1)=\langle b_2 \oplus b_1, \neg b_1\rangle
\]

Function $\boldsymbol{f}^a$ can be encoded in SML using Church Booleans and Mairson's Copy function as follows:
fun a (b2, b1) = Copy b1 (fn b1_1 => fn b1_2 =>
(Xor (b2, b1_1), Not b1_2)

(for Not and Xor described above).
Let us see function a in action:
a q0; (* q1, ('a->'b->'b)*('c->'d->'c)  *)
a q1; (* q2, ('a->'b->'a)*('c->'d->'d)  *)
a q2; (* q3, ('a->'b->'a)*('c->'d->'c)  *)
a q3; (* q0, ('a->'b->'b)*('c->'d->'d)  *)

The type of a applied on qi is the type of qj where $\delta_a(q_i)=q_j$.
Therefore, we can simulate an FSM run by recursively applying a to q0.
Let $w=a^n$ and let $p_n$ be the last state in $w$'s run.
Then, applying function a to q0 $n$ times results in an expression of type $p_n$ (the inductive proof is simple).

The terminal function [literate=*D$1]D should check that the last state in the run is accepting.
Recall that in our example, this condition is verified by
\[
g^8(b_2b_1) = \neg b_2 \wedge \neg b_1
\]

as $g^8(\beta(q))=1 \Leftrightarrow q \in F$.
Since function $g^8$ is linear, it can be encoded simply as
\[
\inline[style=sml]{fun g8 (b2, b1) = And (Not b2) (Not b1)}
\]

Function [literate=*D$1]D applies $g^8$ to $b_2b_1$ and compels the result b to be true:
fun $ (b2, b1) = let val b = g8 (b2, b1) in (b 0 "") + 0 end

The expression (b 0 "") has type [style=sml]int if b is true or [style=sml]string otherwise, so by adding +0 we force b to be true, or else compilation will fail since a [style=sml]string cannot be added to an [style=sml]int in SML.

The full encoding of $(a^4)^*$ is shown in <ref>, together with a few example chains.

[float=ht,style=sml,caption=A Church-encoded SML fluent API for the FSM of <ref>,label=listing:church:a4]
fun T x y = x (* true, T : 'a->'b->'a *)
fun F x y = y (* false, F : 'a->'b->'b *)
fun Not b = b F T
fun Or (b2, b1) = b2 T b1
fun And (b2, b1) = b2 b1 F
fun Pair x y z = z x y
fun Copy p = p (Pair T T) (Pair F F)
fun Xor b1 b2 =
Copy b2 (fn b2_1 => fn b2_2 =>
Copy b1 (fn b1_1 => fn b1_2 =>
Or (And (b1_1, Not b2_1), And (Not b1_2, b2_2))
fun ^^ f' = f' (F, F) (* $\color{comment}\beta(q_0)=00$ *)
fun a (b2, b1) f' = f' (Copy b1 (fn b1_1 => fn b1_2 =>
(Xor b2 b1_1, Not b1_2)
)) (* $\color{comment}\boldsymbol{f}^a(b_2b_1)=\langle b_2 \oplus b_1, \neg b_1\rangle$ *)
fun g8 (b2, b1) = And (Not b2) (Not b1) (* $\color{comment}g^8(\beta(q))=1 \Leftrightarrow q=q_0$ *)
fun $ (b2, b1) = let val b = g8 (b2, b1) in (b 0 "") + 0 end; (* accepts only $\color{comment}b_2b_1=00=\beta(q_0)$ *)
(* chain examples: *)
^^ $; (* OK, $\color{comment}\varepsilon\in L((a^4)^*)$ *)
^^ a a a a $; (* OK, $\color{comment}a^4\in L((a^4)^*)$ *)
^^ a $; (* error, $\color{comment}a^1\not\in L((a^4)^*)$ *)
^^ a a $; (* error, $\color{comment}a^2\not\in L((a^4)^*)$ *)
^^ a a a a a $; (* error, $\color{comment}a^5\not\in L((a^4)^*)$ *)

§.§ The Church Boolean Encoding Algorithm

As in bit shuffling, the general Church Boolean encoding algorithm starts by converting the input FSM $M$ into an equivalent FSM $M'$ with a total transition function and whose number of states is a power of two.
The other generalization steps (to support multiple letters and multiple accepting states) are the same as in bit shuffling (see <ref>).
The full algorithm is shown in <ref>.

The Church Boolean algorithm for encoding an FSM as an SML fluent API

[1]
FSM $M=\langle Q, \Sigma, q_0, F, \delta\rangle$
The Church Booleans, Church Boolean functions, and Mairson's fanout gate, as written in lines 1–7 of <ref>
Construct FSM $M'=\langle Q', \Sigma, q_0, F, \delta'\rangle$ from $M$ by making the transition function $\delta$ total and adding states until $|Q'|$ is a power of two (both using sink states)
$v$$\langle b_n, \ldots, b_2, b_1 \rangle$
$\beta$a mapping $Q'\rightarrow \{0, 1\}^n$ that assigns a unique vector for each state
[style=sml,literate=*Cˆ1]fun CC f' = f' $\beta(q_0)$
$\boldsymbol{f}^\sigma$a mapping $\{0, 1\}^n\rightarrow\{0, 1\}^n$ such that $\boldsymbol{f}^\sigma(\beta(q))=\beta(p) \Leftrightarrow \delta_\sigma(q)=p$
[style=sml]fun $\sigma$ $v$ f' = f' $\boldsymbol{f}^\sigma(v)$
$g^F$the (one and only) Boolean function such that $g^F(\beta(q))=1 \Leftrightarrow q \in F$
[style=sml,literate=*D$1]fun D $v$ = ($(g^F(v))$ 0 "") + 0

As before, the code excerpts in <ref> contain mathematical symbols.
These are rendered in text as follows:

* A Boolean bit $b_i$ is rendered as T if $b_i=1$, as F if $b_i=0$, or as bi if it is a variable (lines 9 and 11).

* A Boolean vector $v=b_n\cdots b_2b_1$ is rendered as a tuple [literate=*Eto 1em...1]($b_n$, E, $b_2$, $b_1$).

* A Boolean vector function $g(v)$ is rendered as a circuit of Church Booleans using Mairson's fanout gate, as described above.

* A Boolean vector function $\boldsymbol{g}(v)$ decomposed to $\langle g_n(v), \ldots, g_2(v), g_1(v)\rangle$ is rendered as a tuple [literate=*Eto 1em...1]($g_n(v)$, E, $g_2(v)$, $g_1(v)$).

§ TABULATION

The last encoding technique, tabulation, organizes the FSM transition function in a table (2D array) and accesses it at compile time.
Tabulation is a flexible method that can be extended to enforce non-regular API protocols, as discussed in <ref>.
We show how to use tabulation to encode a fluent API for $(a^4)^*$, and then, in <ref>, we generalize the construction for any FSM.

Let type [literate=*D$1]DD denote FSM acceptance of the input word, and () (unit) denote its rejection:
\[
\inline[style=sml,literate=*{D}{\textdollar}{1}]{datatype DD = DD}
\]

Consider the following infinite expression:

\begin{equation}\label{eq:e}
e=\text{\inline[style=sml,literate=*{D}{\textdollar}{1}]{(DD, ((), ((), ((), (DD, ((), $\ \ldots$))))))}}
\end{equation}

Expression $e$ is an infinite cons-list of [literate=*D$1]DD and (), where [literate=*D$1]DD repeats every four nodes.
We can use $e$ to implement a (right to left) fluent API for $(a^4)^*$:
fun ^^ = $e$
fun a (_, e') = e'
fun $ ($$, _) = ()

Each call to a removes an item from $e$, and the terminal function [literate=*D$1]D can be called only on item [literate=*D$1]DD, i.e., once every four calls to a.
In SML, however, infinite expressions with infinite types cannot be described.
For example, the following attempt to define $e$ fails due to circularity:
\[
\inline[style=sml,literate=*{D}{\textdollar}{1}]{val e = let fun e' () = (DD, ((), ((), ((), e' ())))) in e' () end}
\]

We can describe expression $e$ <ref> using four expressions as follows:

\begin{equation}\label{eq:es}
\begin{aligned}
e_0 &= \text{\inline[literate=*{D}{\textdollar}{1}]{(DD,\ $e_1$)}} \\
e_1 &= \text{\inline{((),\ $e_2$)}} \\
e_2 &= \text{\inline{((),\ $e_3$)}} \\
e_3 &= \text{\inline{((),\ $e_0$)}} \\
e &= e_0
\end{aligned}
\end{equation}

We view expressions $e_0$ through $e_3$ as the rows of a $4\times2$ table, where the tuples' left-hand is the first column, and the right-hand side is the second column.
This tabular layout of $e$ reveals its tight connection to the underlying $(a^4)^*$ FSM (<ref>):
A table row $e_i$ encodes the corresponding FSM state $q_i$, where the first column encodes membership in $F$ using () ($e_i\not\in F$) and [literate=*D$1]DD ($e_i\in F$), and the second column encodes the output of the transition function $\delta_a(e_i)$.
For instance, expression $e_2=\text{\inline{((),\ $e_3$)}}$ encodes state $q_2$, since $q_2 \not\in F$ and $\delta_a(q_2)=q_3$ (encoded by $e_3$).
Let's explicitly place expressions $e_0$ through $e_3$ in a table:

\begin{equation}\label{eq:es:table}
\boldsymbol{e}=\langle e_0, e_1, e_2, e_3\rangle
\end{equation}

To untangle the recursive definition of expressions $e_0$ through $e_3$ <ref>, we replace each use of expression $e_j$ with its index in table $\boldsymbol{e}$ <ref>, which is $j$.
Instead of writing index $j$ as an integer, which cannot be evaluated at compile time, we write it as an indexing function I$j$ that returns the $j$entry of a (general) quadruple:
fun I0 (x0, x1, x2, x3) = x0
fun I1 (x0, x1, x2, x3) = x1
fun I2 (x0, x1, x2, x3) = x2
fun I3 (x0, x1, x2, x3) = x3
val e0 = ($$, I1)
val e1 = ((), I2)
val e2 = ((), I3)
val e3 = ((), I0)
val e = (e0, e1, e2, e3)

Now we can encode the API function a as follows:
fun a (_, I) = I e

Applying a to expression $e_i=\text{\inline[literate=*{D}{\textdollar}{1}]{($\cdot$, I$j$)}}$ evaluates to the $j$element of quadruple e, I$j$ e.
Since $j=(i+1)\bmod4$ for every expression $e_i$, this element is $e_{(i+1)\bmod4}$.
Therefore, function a correctly encodes the FSM transition function:
\[
\inline{a e$i$} = \inline{e$j$} \iff \delta_a(q_i)=q_j
\]

The full fluent API encoding is shown in <ref>.
The API is followed by several chain examples.

[float=ht,style=sml,caption=A tabulation SML fluent API for the FSM of <ref>,label=listing:projection:a4]
datatype $$ = $$
fun I0 (x0, x1, x2, x3) = x0
fun I1 (x0, x1, x2, x3) = x1
fun I2 (x0, x1, x2, x3) = x2
fun I3 (x0, x1, x2, x3) = x3
val e0 = ($$, I1) (* $\color{comment}q_0 \in F, \delta_a(q_0)=q_1$ *)
val e1 = ((), I2) (* $\color{comment}q_1 \not\in F, \delta_a(q_1)=q_2$ *)
val e2 = ((), I3) (* $\color{comment}q_2 \not\in F, \delta_a(q_1)=q_3$ *)
val e3 = ((), I0) (* $\color{comment}q_3 \not\in F, \delta_a(q_1)=q_0$ *)
val e = (e0, e1, e2, e3)
fun ^^ f' = f' e0 (* $\color{comment}q_0$ is the initial state *)
fun a (_, I) f' = f' (I e)
fun $ ($$, _) = ();
(* chain examples: *)
^^ $; (* OK, $\color{comment}\varepsilon\in L((a^4)^*)$ *)
^^ a a a a $; (* OK, $\color{comment}a^4\in L((a^4)^*)$ *)
^^ a $; (* error, $\color{comment}a^1\not\in L((a^4)^*)$ *)
^^ a a $; (* error, $\color{comment}a^2\not\in L((a^4)^*)$ *)
^^ a a a a a $; (* error, $\color{comment}a^5\not\in L((a^4)^*)$ *)

A general FSM with $n=|Q|$ states and $m=|\Sigma|$ letters is encoded by an $n \times (m+1)$ table, i.e., each letter is given its own column.
State $q_i$ (a table row) is encoded by the expression
val ei = ($a$, ($I^{(1)}$, $\ldots$, $I^{(m)}$))

where $a=\text{\inline[literate=*{D}{\textdollar}{1}]{DD}}$ if $q_i \in F$ or () otherwise and $I^{(j)}=\text{\inline{Ik}}$ where $\delta(q_i, \sigma_j)=q_k$.
If $\delta(q_i, \sigma_j)$ is not defined, set $I^{(j)}=\text{\inline{()}}$, making compilation fail whenever the underlying FSM gets stuck.
This means that in order to get the early failure property, described in <ref>, we simply need to remove from the FSM every state that cannot reach an accepting state.

The general tabulation encoding algorithm is described in <ref>.

The tabulation algorithm for encoding an FSM as an SML fluent API

[1]
FSM $M=\langle Q, \Sigma, q_0, F, \delta\rangle$
[style=sml,literate=*D$1]datatype DD = DD
Enumerate $Q=\{q_1, q_2, \ldots, q_n\}$
$j=1, 2, \ldots, n$
[style=sml,literate=*Eto 1em...1]fun I$j$ (x1, x2, E, x$n$) = x$j$
Enumerate $\Sigma=\{\sigma_1, \sigma_2, \ldots, \sigma_m\}$
$i=1, 2, \ldots, n$
$a$[literate=*D$1]DD if $q_i\in F$ or else ()
$j=1, 2, \ldots, m$
$I^{(j)}$$\text{\inline{I$k$}}$ where $\delta(q_i, \sigma_j) = q_k$
$I^{(j)}$$\text{\inline{()}}$ where $\delta(q_i, \sigma_j)$ is not defined
[style=sml,literate=*Eto 1em...1]val e$i$ = ($a$, ($I^{(1)}$, $I^{(2)}$, E, $I^{(m)}$))
[style=sml,literate=*Eto 1em...1]val e = (e1, e2, E, e$n$)
[style=sml,literate=*Cˆ1]fun CC f' = f' e$i$ where $q_i$ is the initial state
$j=1, 2, \ldots, m$
[style=sml,literate=*Eto 1em...1]val $\sigma_j$ (_, (_, E, I, E, _)) f' = f' (I e) where the inner tuple has $m$ entries and argument I appears in the $j$entry
[style=sml,literate=*D$1Eto 1em...1]fun D (DD, _) = ()

§ BEYOND REGULAR LANGUAGES

In <ref> we
described three methods for encoding FSMs as fluent APIs.
These methods can be used to embed regular DSLs in functional
programming languages.
This leaves us wondering about DSLs that are not regular.
It is actually not hard to come up with a fluent API that
recognizes a non-regular language.
For example, the fluent API shown in <ref>
recognizes the Dyck language of balanced / brackets,
known to be non-regular.
(This is a functional re-implementation of the object-oriented fluent API
in <ref>.)

[float=ht,style=sml,caption=An SML fluent API encoding the Dyck language of balanced / brackets,label=listing:functional:dyck]
datatype Z = Z
and 'x S = S of 'x
fun L x f' = f' (S x)
fun R (S x) f' = f' x
fun ^^ f' = f' Z
fun $ Z = ()
val w1 = ^^ L R $ (* compiles, `()' are balanced *)
val w2 = ^^ L L R L R R $ (* compiles, `(()())' are balanced *)
val w3 = ^^ L L R L R L $ (* does not compile, `(()()(' are not balanced *)

The current section introduces two fluent API encoding techniques
for non-regular languages.
The first technique integrates several simple APIs (as seen in <ref>)
into one, more complex API.
The second technique generalizes our tabulation encoding
(presented in <ref>) to support all DCFLs.

§.§ Product APIs

Consider the fluent APIs A2 and A3 shown in <ref>.
These APIs encode the languages $(a^2)^*$ and $(a^3)^*$, respectively, using shuffle encoding (cf. <ref>).

[float=ht,style=sml,caption=SML APIs for the languages $(a^2)^*$ and $(a^3)^*$,label=listing:original:apis]
datatype t = T and f = F
structure A2 = struct
fun ^^ f' = f' (T, F)
fun a (x1, x2) f' = f' (x2, x1)
fun $ (T, _) = ()
structure A3 = struct
fun ^^ f' = f' (T, F, F)
fun a (x1, x2, x3) f' = f' (x3, x1, x2)
fun $ (T, _, _) = ()

We create the product of APIs A2 and A3 by pairing the inputs and outputs
of each API function, as shown in <ref>.
For instance, the expression ((T, F), (T, F, F)) (line 2) is a tuple of the
respective expressions (T, F) in A2 and (T, F, F) in A3.
The resulting API A6 simulates the two original APIs simultaneously:
the simulation of A2 is managed on the left-hand side of each tuple and A3 on the right-hand side.

[float=ht,style=sml,caption=The product of the APIs in <ref>,label=listing:product:api]
structure A6 = struct
fun ^^ f' = f' ((T, F), (T, F, F))
fun a ((x1, x2), (x1', x2', x3')) f' = f' ((x2, x1), (x3', x1', x2'))
fun $ ((T, _), (T, _, _)) = ()

What, accordingly, is the language encoded by A6?
Intuitively, since the termination function $\texttt\$$ enforces the acceptance conditions
of both A2 and A3 simultaneously, the language encoded by A6 is the intersection of their languages:
\[
(a^2)^* \cap (a^3)^* = (a^6)^*
\]

In general, we can use this product method to encode a complex DSL $L$ by
describing it as the intersection of two simpler languages, $L=L_1 \cap L_2$,
encoding these languages as fluent APIs L1 and L2,
and  writing the product API of L1 and L2.

The / API presented at the start of this section (<ref>) recognizes a non-regular language by
simulating a stack machine (DPDA) at the type level.
We can use similar stack-based APIs in combination with our shuffle, Church, and tabulation encoding methods to create powerful product APIs.
For example, the (enhanced) HTML API discussed in <ref> is the product of a shuffle API and several stack machines.
The shuffle API enforces the order of the HTML tags, e.g., that <html> can be followed by <body> but never by <p>, but does not check that each tag has a matching closing tag.
Tag matching is verified in a separate stack-based API, that ignores the ordering of tags.
Yet another stack-based API is used to check that all the rows of an HTML table have the same number of columns.
Although each of these APIs alone encodes a nonsensical language, their product API exactly encodes enhanced HTML, a complex, context-sensitive language.

§.§ Functional Fluent APIs for DCFLs

<cit.> presented an algorithm for encoding DCFLs as fluent APIs
in object-oriented languages.
Their algorithm relies on a minimal set of common object-oriented type system features, including
parametric polymorphism and overloading.
For example, a method created by Gil and Roth's construction might look like this:
interface A<x>
B<C<x>, x> f();

We denote the signature of method f as follows:
\[
f: A(x) \rightarrow B(C(x), x)
\]

Note that $f$ explicitly accepts an object of the containing class A<x> as input.
There are no additional input parameters in the basic encoding.

In general, object-oriented fluent API methods have the following form:

\begin{equation}\label{eq:function}
\sigma:\gamma(\boldsymbol{x})\rightarrow\tau
\end{equation}

where $\sigma$ is the method name, $\gamma$ is the name of the containing class, $\boldsymbol{x}$ are its type parameters, and $\tau$ is the return type.
Type $\tau$ is a (possibly) non-grounded type comprising variables $\boldsymbol{x}$ and other API types.
The fluent API also includes an initial variable:

\begin{equation}\label{eq:initial}
\text{\lstinline/\^\^/}:t_0
\end{equation}

(for ground type $t_0$) and termination methods that return void (unit):

\begin{equation}\label{eq:termination}
\text{\texttt{\textdollar}}:\gamma(\boldsymbol{x})\rightarrow\text{\lstinline/()/}
\end{equation}

Observe that API method signatures <ref> are essentially tree rewrite rules.

Thus, we can see a fluent chain of method calls as a series of rewrites of the initial
tree (type) $t_0$ of the initial variable <ref>.
The termination methods <ref> simply separate the API types into
accepting and rejecting types, i.e., by checking whether or not $\text{\texttt\textdollar}$ accepts type $\gamma$ as input.

For example, the fluent API shown in <ref> in <ref>, which encodes an / Dyck language, defines the following signatures:

\begin{equation}\label{eq:functional:dyck}
\begin{array}{ll}
\text{\lstinline/\^\^/}: z & \text{(\textit{a})} \\
L: z \rightarrow s(z) & \text{(\textit{b})} \\
L: s(x) \rightarrow s(s(x)) \hspace*{3ex} & \text{(\textit{c})} \\
R: s(x) \rightarrow x & \text{(\textit{d})} \\
\text{\texttt{\$}}: z \rightarrow \text{\texttt{()}} & \text{(\textit{e})}
\end{array}
\end{equation}

The fluent API in <ref> overloads method $L$ and, therefore, cannot be directly encoded in a functional programming language.
It is definitely possible, however, to write an equivalent functional API—we saw one in <ref>.
We now describe the construction of another functional fluent API for the / Dyck language.
This time, we take a more methodological approach by converting the object-oriented fluent API in <ref> into a functional fluent API, and then generalize this method for all DCFLs.

The idea is to apply tabulation encoding, presented in <ref>,
on top of Gil and Roth's construction.
Recall that in the FSM case, we encoded each machine state as a table row (tuple)
\[
q\Rightarrow\text{\inline{($a$, ($I^{(1)}$, $\ldots$, $I^{(m)}$))}}
\]

where $a \in \{\text{\inline{()},\inline{$\text{\texttt{\textdollar\textdollar}}$}}\}$ indicates whether state $q$ is accepting and the $I$'s are indexing functions encoding the outgoing $q$ edges.
In the non-regular case, we encode generic types instead of states.
Instead of outgoing edges, we index the rewrite rules of API methods:
[b]eq:functional:dyck is $\rho_1$, [c]eq:functional:dyck is $\rho_2$,
and [d]eq:functional:dyck is $\rho_3$.
In addition, the encoding of generic type $\gamma(\boldsymbol{t})$ recursively includes the encodings of its type arguments $\boldsymbol{t}$.
Thus, type $\gamma(t_1, \ldots, t_k)$ is encoded as follows:
\[
\gamma(t_1, \ldots, t_k)\Rightarrow\text{\inline{($a$, ($I^{(1)}$, $\ldots$, $I^{(m)}$), ($e_1$, $\ldots$, $e_k$))}}
\]

where  $a$ indicates whether $\gamma$ is accepting,  $I_j$ is the index of $\sigma_j:\gamma(\boldsymbol{x})\rightarrow\tau$ in the table,
and  $e_1$ through $e_k$ are the encodings of types $t_1$ through $t_k$.

In our example, types $z$ and $s(x)$ are encoded as follows:
val z = ($$, (I1, ()), ())
fun s x = ((), (I2, I3), (x))

Type $z$ is accepting, $a=\text{\inline{$\text{\texttt{\textdollar\textdollar}}$}}$, by [e]eq:functional:dyck, but $s$ is rejecting since function $\text{\texttt{\textdollar}}$
does not accept $s$.
Functions I1, I2, and I3 are the indices of rules $\rho_1$, $\rho_2$, and
$\rho_3$ of the API methods $L$ and $R$.
Since $z:R\rightarrow\tau$ is not defined, we put () in $R$'s locations in the encoding of $z$.
Finally, type $z$ is non-generic and thus its encoding is a value.
On the other hand, $s$ has a type parameter $x$, so we encode it as a function with a single
parameter that captures $x$'s encoding.
Observe that by encoding generic types as functions, we can create the encodings of complex
types by writing them directly as expressions, e.g., the encoding of type $s(s(z))$
is given by the expression s(s(z)).

Next, we encode the rewrite rules $\rho_1$, $\rho_2$, and $\rho_3$ as functions and collect them in table r:
fun r1 () = s(z) (* $\text{\eref[b]{eq:functional:dyck}}$ *)
fun r2 (x) = s(s(x)) (* $\text{\eref[c]{eq:functional:dyck}}$ *)
fun r3 (x) = x (* $\text{\eref[d]{eq:functional:dyck}}$ *)
val r = (r1, r2, r3)

These functions do not specify the containing class $\gamma$, but are otherwise identical to the signatures from which they originated [b–d]eq:functional:dyck.

Finally, we can encode the fluent API functions.
The initial function simply returns the encoding of the initial type $t_0=z$ [a]eq:functional:dyck:
fun ^^ f' = f' z

Functions $L$ and $R$ are encoded as follows:
fun L (_, (I, _), X) f' = f' (I r X)
fun R (_, (_, I), X) f' = f' (I r X)

Each function extracts its respective index I from the type encoding, applies it to table r to get the appropriate rewrite function, and then applies this function to the type arguments X.
For instance, when we apply function L to encoding s(z), the index is $\inline{I}=\inline{I1}$, the rewrite function is $\inline{I r}=\inline{r2}$,
and the resulting expression $\inline{r2 s(z)}=\inline{s(s(z))}$ correctly encodes the application
of $L$ to type $s(z)$ in the original API [c]eq:functional:dyck.
The termination function $\text{\texttt\textdollar}$ simply verifies that $a=\text{\inline{$\text{\texttt{\textdollar\textdollar}}$}}$:
fun $ ($$, _, _) = ()

The complete functional fluent API is shown in <ref>.

[float=ht,style=sml,caption=The object-oriented fluent API in <ref> and <ref> converted to SML,label=listing:functional:dyck:2]
datatype $$ = $$
fun I1 (x1, x2, x3) = x1
fun I2 (x1, x2, x3) = x2
fun I3 (x1, x2, x3) = x3
val z = ($$, (I1, ()), ())
fun s x = ((), (I2, I3), (x))
fun r1 () = s(z)
fun r2 (x) = s(s(x))
fun r3 (x) = x
val r = (r1, r2, r3)
fun ^^ f' = f' z
fun L (_, (I, _), X) f' = f' (I r X)
fun R (_, (_, I), X) f' = f' (I r X)
fun $ ($$, _, _) = ()

The general DCFL encoding algorithm is presented in <ref>.
This algorithm starts by applying Gil and Roth's construction to produce an object-oriented fluent API, and then applies the (modified) tabulation encoding to remove overloading.

The tabulation algorithm for encoding a DPDA as an SML fluent API

[1]
DPDA $A$
Apply the tree encoding algorithm of <cit.> to convert $A$ into an object-oriented fluent API $P$ as specified in <ref>.
[style=sml,literate=*D$1]datatype DD = DD
Enumerate $P$'s API functions <ref> $R=\{\rho_1, \rho_2, \ldots, \rho_n\}$
$j=1, 2, \ldots, n$
[style=sml,literate=*Eto 1em...1]fun I$j$ (x1, x2, E, x$n$) = x$j$
Enumerate $P's$ API methods $\Sigma=\{\sigma_1, \sigma_2, \ldots, \sigma_m\}$
Enumerate $P$'s API types $\Gamma=\{\gamma_1, \gamma_2, \ldots, \gamma_l\}$
$i=1, 2, \ldots, l$
$a$[literate=*D$1]DD if $P$ includes the method $\text{\texttt{\textdollar}}:\gamma_i(\boldsymbol{x})\rightarrow\text{\texttt{()}}$ or else ()
$j=1, 2, \ldots, m$
$I^{(j)}$$\text{\inline{I$k$}}$ where $\rho_k=(\sigma_j:\gamma_i(\boldsymbol{x})\rightarrow \tau)\in P$
$I^{(j)}$$\text{\inline{()}}$ where $(\sigma_j:\gamma_i(\boldsymbol{x})\rightarrow \tau)$ is not defined in $P$
$\gamma_i$ is not generic
[style=sml,literate=*Eto 1em...1]val $\gamma_i$ = ($a$, ($I^{(1)}$, $I^{(2)}$, E, $I^{(m)}$), ())
[style=sml,literate=*Eto 1em...1]fun $\gamma_i$ ($\boldsymbol{x}$) = ($a$, ($I^{(1)}$, $I^{(2)}$, E, $I^{(m)}$), ($\boldsymbol{x}$))
$i=1, 2, \ldots, n$
r$i$ ($\boldsymbol{x}$) = $\tau$
[style=sml,literate=*Eto 1em...1]val r = (r1, r2, E, r$n$)
[style=sml,literate=*Cˆ1]fun CC f' = f' $t_0$ where $\text{\lstinline/\^\^/}:t_0$ is $P$'s initial variable
$j=1, 2, \ldots, m$
[style=sml,literate=*Eto 1em...1]val $\sigma_j$ (_, (_, E, I, E, _), X) f' = f' (I r X) where the inner tuple has $m$ entries and argument I appears in the $j$entry
[style=sml,literate=*D$1Eto 1em...1]fun D (DD, _, _) = ()

<Ref> accepts as input a DPDA accepting the target DCFL.
In line 1, it converts the input into an object-oriented fluent API using tree encoding.
In lines 8 through 16 the algorithm encodes the API types as functions and variables.
The tree rewrite rules are encoded in lines 17 through 20.
The tree pattern $\tau$ is printed as-is.
Finally, the algorithm prints the API functions in lines 21 through 24.

§ DISCUSSION

§.§ Functional vs. Object-Oriented Fluent APIs

Functional fluent APIs share many qualities with their object-oriented counterparts.
They provide a fluent DSL embedding method that employs a simple and uniform syntax devoid of host language control structures.
The simplicity of fluent API designs makes them compatible with a wide range of functional host languages.
Our encoding algorithms in <ref> show that functional fluent API constructions can be generalized to entire classes of DSLs, namely all regular languages and DCFLs.
These results are in line with recent advances in the study of object-oriented fluent APIs, focusing on fluent APIs for DCFLs <cit.>.

Nevertheless, there are two notable differences between object-oriented and functional fluent APIs.
First, the functional fluent style is cleaner because functions are called without the dot and parenthesis (x.f()) common to object-oriented languages.
This removes the last bit of host language syntax from the EDSL.
In combination with operator overloading, found in many popular functional languages, functional fluent APIs can produce extremely accurate DSL embeddings, as demonstrated by our HTML example in <ref>.

The second difference relates to embedding of DSL literals.
DSL literals are embedded as function arguments in the fluent API.
In our embedded HTML document in <ref>, for example, attribute src in the img tag receives a string argument specifying the image source:
<img src "https://tinyurl.com/yosemite5"/>

Although adding parameters to our fluent API designs is a technical matter, it has an inherent limitation.
The lack of overloading in functional settings means that the fluent APIs cannot overload argument types.
For instance, img can receive a string or a URL object, but not both.
This detail could possibly hinder certain EDSL designs and should be kept in mind when making functional fluent APIs.

§.§ A Plethora of Functional Fluent API Encoding Methods

<Ref> present no less than three different algorithms for encoding regular languages as functional fluent APIs.
The most promising method is probably bit shuffling, described in <ref>.
Bit shuffling fluent APIs do not employ unification, so they are expected to induce reasonable compilation times across various languages and compilers.
The bit shuffling improvements described in <ref> greatly enhance utility by reducing code size and improving error reporting.

The crux of the bit shuffling construction is to describe the FSM as a collection of circuits or logic gates.
In <ref> we showed how to implement these circuits at the type level using Church Booleans and Mairson:2004 fanout gate.
Compile-time circuits may have some additional implications for API design beyond fluent API.
For instance, they can be used to conduct numeric calculations in a type-safe physical dimensions library <cit.>.

Tabulation encoding (<ref>) is a flexible embedding method that can be generalized for non-regular DSLs (<ref>).
It provides the theoretical basis for a functional fluent API generator in the style of Fling <cit.> and TypeLevelLR <cit.>.
Such tools compile LL, LALR, and LR grammars into fluent APIs that validate the DSL syntax at compile time and produce abstract syntax trees (ASTs) at run time.

§.§ Functional Subchaining

A fluent API embeds a DSL program as a single chain of method calls.
This design can be limiting when we want to create excerpts of the DSL program.
In the HTML document of <ref>, we might decide, for example, to place the HTML table in a variable and then reference it in the complete webpage.
Recently, <cit.> presented a new generation method for object-oriented fluent APIs that supports subchains—fluent chains that embed DSL fragments.
Since our functional fluent API designs use curried functions, they come with subchaining (almost) out of the box.
<Ref> demonstrates functional subchaining using our HTML fluent API.

[float=ht,style=sml,caption=Subchaining with a functional fluent API,label=listing:subchaining]
fun sc a b = b a (* subchaining helper function *)
val table = fn f' => sc f' (* HTML table subchain *)
<tr> <th> `"Image" </th> </tr>
<tr> <td> <img src "https://tinyurl.com/yosemite5"/> </td> </tr>
val webpage = ^^ (* using the subchain in a complete embedding *)
table (* subchain usage *)

Function sc, defined in line 1 of <ref>, is an auxiliary function for creating subchains.
Our fluent API designs require no additions or modifications to support subchaining besides sc.
In lines 2 through 6, we define an HTML excerpt containing an HTML table.
The boilerplate code

[style=sml]fn f' => sc f'

in line 2 must precede every subchain.
Variable table containing the HTML table is used as part of a complete HTML embedding in lines 7 through 13.

At the type level, using a subchain is equivalent to inlining its code, so the fluent API correctly reports API misuses in subchains.
However, the error messages are displayed where the subchain is referenced and not at the error's actual location.
We speculate that more sophisticated fluent API designs could force the compiler to check the correctness of subchains at the place of definition.

§.§ Implementation and Experiments

This work is accompanied by Flunct <cit.>, an SML implementation of the bit shuffling, Church, and tabulation encoding techniques.
Flunct compiles a given FSM $M$ into a functional fluent API that validates $M$ at compile time.
In <ref> we demonstrate how Flunct can be used to embed a DSL in SML.
We used Flunct to conduct a series of experiments to measure the code size and compilation time of the various fluent API constructions described in the paper.
The results of these experiments are described in <ref>.
In the full paper <cit.>, we demonstrate how Flunct can be used to embed a DSL in SML.

We used Flunct to conduct a series of experiments to measure the code size and compilation time of the various fluent API constructions described in the article.
For example, the graph in <ref> compares the compilation times of bit shuffling, Church, and tabulation fluent APIs using the MLton SML compiler.
Our experiments suggest that bit shuffling, together with the improvements described in <ref>, performs the best in terms of code size and compilation time, which is expected considering that bit shuffling is the only technique that doesn't rely on unification.
A full description of the experiments is found in the full paper.

xlabel=Chain size (#calls),
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
[l]Bit Shuffling (<ref>)
+ improvements (<ref>)
] coordinates
Church (<ref>)
] coordinates
Tabulation (<ref>)

Chain length vs. compilation time of bit shuffling, Church, and tabulation fluent APIs using MLton

§ FLUNCT—A FUNCTIONAL FLUENT API GENERATOR

Flunct embeds a DSL specified by an FSM as a functional fluent API using the bit shuffling, Church Boolean, and tabulation techniques described in <ref>.
In this appendix, we show how to use Flunct to embed a DSL in SML.
The running example DSL is the Command-Line Interface (CLI) Builder, a DSL for creating command-line applications.
For instance, we can use the CLI Builder DSL to create an “ice cream machine” command-line application:
[caption=The ice cream machine CLI,label=listing:icecream]
icecream –flavors chocolate vanilla –container cup > ice1.cream
icecream –flavors pistachio –toppings caramel  > ice2.cream
icecream –help
¢Ice Cream Machine¢
¢  Makes customized ice cream.¢
¢  –flavors, -f [list]¢
¢    list of ice cream flavors¢

The CLI Builder supports the following properties:

* : Application name.

* : Application description (optional).

* A list of zero or more arguments comprising:

* : Argument name.

* : Makes the argument optional (optional).

* : A list of zero or more argument aliases.

* : The type of values accepted by the argument (optional); has a list of zero or more type aliases:

* : If specified, the argument type is an enumeration of all type aliases.

* : Argument description (optional).

We can formally define the CLI Builder DSL using a regular expression:

\begin{equation*}
\texttt{name description? (optional? argument alias$^*$ (argtype alias$^*$)? description)$^*$}
\end{equation*}

Flunct does not support regular expressions at present.
Hence, the first step in embedding the CLI Builder DSL is to encode it as an FSM, as shown in <ref>.

[node distance=10ex]
[state,initial] (q0) at (0,0) $q_0$;
[state,accepting] (q1) at (2.5,0) $q_1$;
[state,accepting] (q2) at (5,0) $q_2$;
[state] (q3) at (7.5,0) $q_3$;
[state,accepting] (q4) at (7.5,-2.5) $q_4$;
[state,accepting] (q5) at (5,-2.5) $q_5$;
(q1) edge[bend right=20] (q3)
(q1) edge[bend left=10] (q4)
(q2) edge[bend left=10] (q4)
(q4) edge[bend left=10] (q2)
(q4) edge[bend left=20] (q3)
(q4) edge[loop below] (q4)
(q5) edge[bend right=20] (q4)
(q5) edge (q3)
(q0) edge node[above]name (q1)
(q1) edge node[above]description (q2)
(q2) edge node[above]optional (q3)
(q3) edge node[right]argument (q4)
(q4) edge[loop right] node[right]alias (q4)
(q4) edge node[above]argtype (q5)
(q5) edge node[left]description (q2)
(q5) edge[loop left] node[left]alias (q5);

An FSM describing the CLI Builder interface. Some edges are grayed-out for readability.

We can use Flunct's interface to describe the FSM of <ref> in SML.
First, we write the FSM alphabet:
val name = Letter ("name", ["string"])
val description = Letter ("description", ["string"])
val optional = Letter ("optional", [])
val argument = Letter ("argument", ["string"])
val alias = Letter ("||", ["string"])
val argtype = Letter ("argtype", ["string"])

The Letter constructor accepts the API function name and the list of its argument types.
Most functions in our CLI Builder example accept a single string argument.
Notice that we chose to encode the  function as an operator, ||.

Next, we define the FSM depicted in <ref>:
val fsm = Fsm (
State 0, (* initial state *)
[State 1, State 2, State 4, State 5], (* accepting states *)
[ (* FSM transitions *)
Transition (State 0, name, State 1),
Transition (State 1, description, State 2),
Transition (State 1, optional, State 3),
Transition (State 1, argument, State 4),
Transition (State 2, optional, State 3),
Transition (State 2, argument, State 4),
Transition (State 3, argument, State 4),
Transition (State 4, description, State 2),
Transition (State 4, optional, State 3),
Transition (State 4, alias, State 4),
Transition (State 4, argument, State 4),
Transition (State 4, argtype, State 5),
Transition (State 5, description, State 2),
Transition (State 5, optional, State 3),
Transition (State 5, argument, State 4),
Transition (State 5, alias, State 5)

The FSM includes an initial state (line 2), a set of accepting states (line 3), and a set of FSM transitions (lines 5 to 20).
Each transition comprises a source state, input letter, and a target state.
For example, line 7 defines that the FSM moves from state $q_1$ to state $q_3$ when reading .

To convert the FSM into an SML fluent API we simply call
print (flunct_api "CLI" fsm Sparse)

The last argument specifies the encoding method.
Flunct supports four methods: Shuffle (bit shuffling), Church (Church Booleans), Tabulation, and Sparse (improved bit shuffling as per <ref>).
Running this line produces a complete fluent API for the CLI builder in [style=sml]struct CLI.

We can now define the ice cream machine CLI inside SML:
val icecream_cli = let
open CLI
name "Ice Cream Machine"
description "Makes customized ice cream."
argument "–flavors" || "-f"
argtype "@list"
description "list of icecream flavors"
optional argument "–toppings" || "-t"
argtype "@list"
description "list of icecream flavors"
optional argument "–container" || "-c"
argtype "cone" || "cup" || "Styrofoam"

The fluent API catches API misuses at compile time.
If, for instance, we write optional twice in line 10, the code does not compile:
Error: operator and operand don't agree [tycon mismatch]
in expression: ((((<exp> <exp>) description) "list of icecream flavors") optional) optional

The embedded program produces a list of tokens:
val icecream_cli = [Name "Ice Cream Machine", Description "Makes customized ice cream.",
Argument "–flavors", @|| "-f", ...] : call list

When the CLI Builder application is completed, its backend would parse and process these tokens.

§ CODE SIZE AND COMPILATION TIME EXPERIMENTS

This appendix describes a series of experiments measuring the code size and compilation time of the different fluent API constructions described throughout the paper.
Most of the experiments were conducted using Flunct, our functional fluent API generator introduced in <ref>.
The purpose of these experiments is to give us a general idea about the feasibility of fluent APIs in different situations.
In particular, the results may vary when switching the underlying DSLs.

A logarithmic scale is applied to all graph axes in this appendix.
All compilation times are averaged over five runs.

§.§ The Ring Experiment

A ring is an FSM with $n$ states that recognizes the language $(a^n)^*$, as depicted in <ref>.
The ring's states are organized in a circle with each state having a single edge to the state on its right, and the initial state being the only accepting state.
For example, the article's running example FSM from <ref> is a 4-state ring.
We use rings as a simple and scalable FSM design.

[scale=.8,every node/.style=scale=.8]
[state,initial,accepting] (q0) at (120:2) $q_0$;
[state] (q1) at (75:2) $q_1$;
[state] (q2) at (30:2) $q_2$;
[state] (q3) at (-15:2) $q_3$;
[state] (q4) at (-60:2) $q_4$;
(d1) at (-105:2) ;
(d2) at (-116.25:2) $\bullet$;
(d3) at (-127.5:2) $\bullet$;
(d4) at (-138.75:2) $\bullet$;
(d5) at (-150:2) ;
[state] (qn) at (-195:2) $q_n$;
(q0) edge[bend left=10] node[above]$a$ (q1)
(q1) edge[bend left=10] node[above]$a$ (q2)
(q2) edge[bend left=10] node[right]$a$ (q3)
(q3) edge[bend left=10] node[right]$a$ (q4)
(q4) edge[bend left=10] node[below]$a$ (d1)
(d5) edge[bend left=10] node[left]$a$ (qn)
(qn) edge[bend left=10] node[left]$a$ (q0);

A ring FSM with $n$ states

In the ring experiment, we compiled rings of different sizes into fluent APIs using different encoding methods.
Recall that the Sparse encoding method is bit shuffling augmented by the improvements described in <ref>.
We then measured the compilation times of these fluent APIs on chains of various length with different compilers and languages.
A chain of length $k$ is a fluent expression with $k$ calls to a:

\begin{equation*}
\text{\inline[literate=*{D}{\textdollar}{1}{C}{\textasciicircum}{1}{E}{\hbox to 1em{.\hss.\hss.}}{1}]{CC a a E a DD}}
\end{equation*}

xlabel=FSM size (#states),
ylabel=Fluent API size (#characters),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
] coordinates
] coordinates
] coordinates

Ring FSM size vs. fluent API size

xlabel=Chain size (#calls),
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
] coordinates
] coordinates

Chain length vs. compilation time with 16-state Ring FSM and MLton

xlabel=FSM size (#states),
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
] coordinates
] coordinates

Ring FSM size vs. compilation time of the empty chain ([literate=*D$1Cˆ1]CC DD) with MLton

xlabel=Chain size (#calls),
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
] coordinates
] coordinates

Chain length vs. compilation time with 4-state Ring FSM and SML/NJ

<Ref> depicts the fluent APIs' code size.
As expected, the size of bit shuffling fluent APIs is exponential in the ring size.
There are two variables to be considered when measuring compilation time: the FSM size and chain length.
<Ref> shows the compilation times of chains of various lengths using the MLton SML compiler and a constant 16-state ring.
<Ref> depicts the compilation times of the empty chain (zero length) on rings of various sizes using MLton.
The SML/NJ interpreter is not quite suitable for these kind of experiment since it cannot function as a compiler.
Nevertheless, it is possible to approximate the compilation time of SML/NJ on individual expressions.
<Ref> shows the compilation times of chains of various lengths using the SML/NJ interpreter and a constant 4-state ring.
These compilation times are calculated on the chains alone, without the fluent APIs.
Note that SML/NJ gets stuck for quite some time when compiling chains longer than the ones used in <ref>.

§.§ The HTML Experiment

In this experiment we measured the compilation time of our HTML API, introduced in <ref>.
As explained in <ref>, the HTML fluent API is the product of a bit shuffling API with a 61-state FSM and several stack machines.
We used this API to embed the HTML webpage in <ref> and added the following table after line 15:
<tr> <th> `"nested table" </th> </tr>
(nested_table (table_depth - 1))

The expression (inner_table (table_depth - 1)) (line 20) was replaced by an identical nested table of variable depth, yielding increasingly complex embeddings.
A table of zero depth was replaced by

<Ref> depicts the compilation time of HTML documents with tables of variable nesting levels using MLton.

§.§ The DCFL Experiment

In this experiment we measured the compilation time of the fluent API in <ref> encoding a DCFL.
Recall that this fluent API was created using (extended) tabulation encoding as described in <ref>.
We used chains of variable lengths and repeated the experiment in two languages:
Once in SML with MLton and once in the ELM programming language <cit.> using the ELM compiler.
The results are shown in <ref>.

§.§ Technical Details

The experiments described in this appendix were conducted on a (fairly old) laptop with the following properties:

* Operating system: Ubuntu 20.04.

* Processor: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz

* MLton version: 20130715

* SML/NJ version: v110.79

* ELM version: 0.19.1

xlabel=Nesting level,
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates

Example HTML size vs. compilation time with MLton

xlabel=Chain size (#calls),
ylabel=Compilation time (seconds),
legend pos=outer north east,
log basis x=2,
log basis y=2,
] coordinates
] coordinates

Chain length vs. compilation time when compiling the fluent API in <ref> in SML and ELM