An example parenthesization defined purely using the B combinator and composition.

Arbitrary Parenthesization

Using only the B combinator

I recently wondered whether the B combinator alone is capable of producing any parenthesization. My intuition was that this should be the case, but I found more or less nothing solid or concise about it, let alone an explicit construction. I’m sure this floats around somewhere, but anyways: The goal of this post is to be discoverable. To be short and intuitive instead of a deep dive.

I certainly had fun figuring all of the following out, so consider not reading the solution if you enjoy a good puzzle!

Problem

Imagine a list of terms t1, t2, t3, t4, … and it is your job to write a function f such that f t1 t2 t3 t4 … results in those same terms, but with a specific parenthesization, e.g. t1 (t2 t3) t4. Specifics:

• Imagine a functional/lambda world where the implicit parenthesization of t1 t2 t3 t4 is (((t1 t2) t3) t4) since function application is left associative. The example above is really ((t1 (t2 t3)) t4). In this post, I always omit implicit parentheses to improve readability.
• f must be constructed by using only function application and combinator B, defined as B x y z = x (y z). For instance, the example behavior above can be achieved by defining f = B.

Solution

All we need to build arbitrary parenthesizations are the following three observations:

1. f = B groups the 2nd and 3rd argument of f (see above).
2. f = B f' results in the same parenthesization as f', but shifted one to the right. For example, f = B B groups the 3rd and 4th parameter of f.
3. f = B f' f'' applies the parenthesization of f', followed by the one of f''. For example, f = B B B groups the 2nd until 4th parameter of f, because B t1 t2 t3 t4 = t1 (t2 t3) t4 and B t1 (t2 t3) t4 = t1 ((t2 t3) t4) = t1 (t2 t3 t4).

Arbitrary parenthesizations can be composed this way. Rule 3 can be used to enlarge a grouped region (move ) to the right). Rule 2 moves everything to the right. Rule three allows multiple groups to be introduced, whether explicitly nested or not. The following example demonstrates both.

Example

Let’s find f with f t1 t2 t3 t4 t5 t6 = t1 (t2 t3) (t4 (t5 t6)). There are three (non-implicit) parentheses, so we can decompose f = B (B f' f'') f''' or f = B f' (B f'' f''') and focus on finding f', f'' and f'''.

Which one of these is responsible for which pair of parentheses is our choice, except that the grouping of t5 and t6 must happen prior to the grouping with t4 as there is no way to “break open” already parenthesized terms. Note also that the earlier groupings can influence later ones in terms of argument indices: If f' groups t2 and t3, then f'' sees (t2 t3) as the 2nd argument, t4 as the 3rd, and so on.

Here I pick

• f' t1 t2 t3 t4 t5 t6 = t1 t2 t3 t4 (t5 t6)
• f'' t1 t2 t3 t4 t5 = t1 t2 t3 (t4 t5)
• f''' t1 t2 t3 = t1 (t2 t3)

This is all just B shifted right by 3, 2 and not at all, respectively:

• f' = B (B (B B))
• f'' = B (B B)
• f''' = B

So f = B (B (B (B B))) (B (B (B B)) B). (Side note: This is not the smallest possible construction. For instance, choosing f’ = B makes the other two components shorter due to mentioned argument grouping effect.)

Let’s put it to the test, one reduction step at a time. Terms participating in the next reduction are highlighted bold:

B (B (B (B B))) (B (B (B B)) B) t1 t2 t3 t4 t5 t6
B (B (B B)) (B (B (B B)) B t1) t2 t3 t4 t5 t6
B (B (B B)) (B (B B) (B t1)) t2 t3 t4 t5 t6
B (B B) (B (B B) (B t1) t2) t3 t4 t5 t6
B (B B) (B B (B t1 t2)) t3 t4 t5 t6
B B (B B (B t1 t2) t3) t4 t5 t6
B B (B (B t1 t2 t3)) t4 t5 t6
B B (B (t1 (t2 t3))) t4 t5 t6
B (B (t1 (t2 t3)) t4) t5 t6
B (t1 (t2 t3)) t4 (t5 t6)
t1 (t2 t3) (t4 (t5 t6))

Deconstruction and Minimalism

It is worth noting that observations 1 to 3 above are “complete” in the sense that we can also use them to deconstruct and interpret arbitrary B-terms: They must either fall under one of the three cases or have the form B x y z ... and hence be reducible. Repeated reduction of B-terms terminates since each reduction reduces the total number of Bs by one. In other words, fully reduced B-terms are recursively interpretable via case analysis.

Note also that this completeness implies that the parenthesization algorithm introduced here is capable of producing a term that uses the minimal number of Bs to achieve its goal. However, note that we did not provide a deterministic way to retrieve this minimal term; the order in which observations 1 to 3 are applied matters.

Conclusion

B is a one-point basis for arbitrary parenthesizations.

However, ironically, the “empty” parenthesization (identity function) is not expressible using any combination of Bs. That seems like an acceptable exception, since doing nothing can also be achieved by not applying any f at all, i.e. by using zero Bs.