Fluent Interface Grammars: Part III (Nesting)

Last time, we saw the properties of fluent interfaces that use method-chaining only. Namely, they can express any regular language not containing the empty string. We also saw an example of a non-regular language. The language accepts any string with a run of a's followed by an equal number of b's, i.e. ab, aabb, aaabbb, etc...

S ::= a B
S ::= a S B
B ::= b

Today, in Part III of our saga, we examine fluent interfaces that use nesting exclusively (Steve Asher discusses nested interfaces here). Just as one cannot implement this language as chaining interface,

a().b()
a().a().b().b()
a().a().a().b().b().b() // (Can't do this.)

the most obvious nested interface for this language is also impossible, for similar reasons.

a(b())
a(a(b(b())))
a(a(a(b(b(b()))))) // (Can't do this either.)

However, it is quite easy to express this (slightly uglier) version:

a(b())
a(a(b()),b())
a(a(a(b()),b()),b()) // (Yucky, but possible.)

This is done with the following nested interface.

public static class S {}
public static class B {}
public static S a(B arg1) { return new S(); }
public static S a(S arg1, B arg2) { return new S(); }
public static B b() { return new B(); }

Thus, we find that there exists at least one non-regular language expressible with nested interfaces. What else can we do?

All context-free grammars can be reduced to Greibach normal form, which only allows production rules of two types:

1. S ::= $
2. A ::= a X

... where A is any non-terminal, a is any terminal, and X is a list of zero or more non-terminals. Rules of type 1 cannot be expressed because our grammars cannot accept the empty string (as noted in Part II). The rules of type 2 become top-level methods in this fashion:

// A ::= a
public static A a() {return new A();}
// A ::= a B
public static A a(B arg1) {return new A();}
// A ::= a BCD
public static A a(B arg1, C arg2, D arg3) {return new A();}

Does this mean that any context-free grammar (that doesn't accept the empty string) can be mapped to a nested fluent interface? Not quite—there is one more caveat. No two rules may have the same right-hand side, because they would yield two top-level methods with competing signatures. The question then becomes: Can any context-free grammar be reduced to a Greibach normal form without duplicate right-hand sides? After afew minutes on a whiteboard, I'm leaning toward no.

Let us now extend our grammar notation to indicate parameter lists.

S ::= a(B)
S ::= a(S B)
B ::= b()

This will make the transition from grammar to code more obvious. Additionally, it will prepare us for the next chapter: mixed interfaces.