B Flat

B Flat

Paradigm(s)	functional
Designed by	User:Blashyrkh
Appeared in	2026
Computational class	Turing complete
Reference implementation	Github
Influenced by	Lazy K
File extension(s)	.bb, .Bb

B Flat (B♭) is a Lazy K derivative with additional B combinator. What's the catch? Parentheses are not allowed!

Syntax and I/O

B Flat syntax is quite simple: the program consists of letters I, K, S and B. Everything from # symbol until the end of line is a comment. Whitespace is ignored. All other characters outside comments are not allowed.

Combinators have standard definition:

I x = x
K x y = x
S x y z = x z (y z)
B x y z = x (y z)

I/O model is exactly as of Lazy K.

Introduction to compositors

The most interesting part of the language specification is parentheses. Particularly, they are strictly forbidden. To change the order of evaluation we suggest to use flat compositor as the program prefix. The suggested approach is by no means the only one: you're free to use any flat linear (or even non-linear) combinator. You may even devise specific bracket abstraction algorithm that would produce flat expressions. But we're going to explore flat compositor approach first because that's how the idea of the language came into existence.

A compositor is a combinator that introduce parentheses. It doesn't change relative order of its arguments nor does it duplicate or destroy them. The following combinators are compositors:

B  x y z                                        = x (y z)
B₁ x y z w       = B B B x y z w                = x (y z w)
D  x y z w       = B B x y z w                  = x y (z w)
D₁ x y z w v     = B (B B) x y z w v            = x y z (w v)
E  x y z w v     = B (B B B) x y z w v          = x y (z w v)
Ê  x y z w v u t = B(BBB)(B(BBB)) x y z w v u t = x (y z w) (v u t)

Flat compositor is a compositor which can be written without parentheses in a given basis of combinators. B, B1 and D are flat compositors in the B basis (we shall call them B-flat for short). In fact, D1 and E are B-flat compositors too: D1 = B B B B and E = B B B B B B B. But Ê is not.

It's known fact that every compositor can be expressed in terms of B combinator only. Systematic construction of such expressions is demonstrated by Raymond Smullyan. Unfortunately, not every compositor is B-flat. In fact, there are only 9 distinct B-flat compositors:

                 B x y z       = x (y z)
               B B x y z w     = x y (z w)
             B B B x y z w     = x (y z w)
           B B B B x y z w v   = x y z (w v)
         B B B B B x y z w     = x (y (z w))
       B B B B B B x y z w v   = x (y z) (w v)
     B B B B B B B x y z w v   = x y (z w v)
   B B B B B B B B x y z w v   = x (y z w v)
 B B B B B B B B B x y z w v u = x y z w (v u)

If we add one more B, we get B B B B B B again, and so on...

Conjecture: every compositor is SB-flat.

This would be very promising: just find a compositor exactly for your program's structure and make it flat in one step. Unfortunately, Lazy K programs are often large and branchy, whereas number of possible tree structures grows exponentially. Brute force search is unable to find required composition structure in a reasonable amount of time, and systematic construction of SB-flat compositors is not yet known to us. Nevertheless, several hours of brute force search on an ordinary laptop produced all possible compositors of ranks up to 8. Also, this approach demonstrated its power by successful translation of the Empty program from Lazy K to B Flat.

Theorem: every Lazy K program can be transformed to equivalent B Flat program.

To prove the Theorem let's introduce special compositor ℬ_m,n and study its properties.

ℬ_m,n and its properties

Let's define a compositor ℬ_m,n (m≥1, n≥2):

ℬm,n x1 ... xm+n = x1 ... xm(xm+1 ... xm+n)

Property 1:

ℬm+1,n+1 = Chm B (Chn B) = S Chm Chn B

Here and later in the text Ch_i is a Church numeral.

Property 2 (special case):

ℬ1,n+1 = Chn B

Property 3 (special case):

ℬm+1,2 = Chm B B

Property 4:

ℬm,n I = ℬm-1,n

Lemma: All ℬ_m,2 are SBI-flat.

Proof: Let's build higher-rank ℬ_m,2 from low-rank ones using two interleaved superexponentially growing sequences x_n+2=2^x_n (starting with two arbitrarily chosen x₁ and x₂). Such choice of growing sequence is by no means optimal and practical for real programs' translation. But it gives a theoretical upper limit that can be improved in the future.

Let:

x1 = 16
x2 = 256
C1 = Chx1 = SBSSBBBSSSISBI
C2 = Chx2 = BSSSSBSSSBISSBI
L1 = len(C1) = 14
L2 = len(C2) = 15

The choice for x₁ and x₂ is somewhat arbitrary. C₁ and C₂ were brute-forced. Let: xi = 2xi-2 for all i>2. Then:

Ci = Chxi = Chxi-2Ch2 = Ci-2((SB)I) = ...

let's apply ℬ_?,2 to decompose ((SB)I) application. Our choice is ℬ_xi-2+1,2 padded with necessary amount of I combinators:

... = Ci-2 | B | B | I-padding1 | Ci-2 | (SB) | I = ...

let's apply ℬ_?,2 to decompose (SB) application. Our choice is ℬ_xi-1+1,2 padded with necessary amount of I combinators

... = Ci-1 | B | B | I-padding2 | Ci-2 | B | B | I-padding1 | Ci-2 | S | B | I

I-padding1 is a sequence of I combinators of length 1+x_i-2-L_i-2.

I-padding2 is a sequence of I combinators of length 1+x_i-1-(1+L_i-2+x_i-2)

The above holds true as long as both paddings have non-negative length. For i=3 it is so due to the choice of x₁ and x₂:

len(I-padding13) = 3
len(I-padding23) = 226

For higher i it is so due to the choice of the sequence growth rate. Let's calculate L_i (i>2):

Li = Li-1+2+1+xi-1+3 = 6+Li-1+xi-1

So, the length of constructed Ch_xi has a magnitude of x_i-1. It guarantees that the I-paddings are always needed. And that's the main reason why this construction is not practical.

We have proved that some arbitrary large Church numerals are SBI-flat. Hence, all ℬ_m,2 are SBI-flat due to properties 3 and 4.

Q.E.D.

Translation from Lazy K to B Flat

Translation of Lazy K program to B Flat (suppose that the source program is non-empty and is written in CC notation):

1. A term is either a single-character combinator or an application of terms. The source program is a term. Initialize:

TAIL := [] : <list of terms>

HEAD := [<source program>] : <list of terms>

The source program is put into HEAD as a single term.

2. If HEAD is empty, STOP. The result is the content of TAIL list.
3. Extract the rightmost term of HEAD:

T := pop_back(HEAD)

4. If T contains single combinator character (I, K or S):

TAIL := T | TAIL

So, all single-character combinators are moved from the right end of HEAD to the left end of TAIL and do not participate in further process of translation.

5. If T is an application of L to R, and HEAD is non-empty:

m := len(HEAD)

According to the Lemma, there is ℬ_m,2 = (...((ℰ₁ℰ₂)ℰ₃)...ℰ_k).

HEAD := ℰ1 | ℰ2 | ... | ℰk | HEAD | L | R

This step decomposes one application of the source program. Since the source program is finite, the process eventually finishes.

6. If T is an application of L to R, and HEAD is empty:

HEAD := L | R

7. Back to step 2.

This algorithm is a (constructive) proof of the Theorem.

Translation from B Flat to Lazy K

Just replace every B with (S(KS)K).

Examples

Empty Program

33 bytes:

SSSSSSSSBSBBSSIBBBBBBBKKSSSIIISBI

The program was constructed by flattening the following non-flat expression:

K(K(S(SSI)I(SBI)))

A compositor required to flatten this structure was found by brute force search.

Implementation

• Multi-language interpreter (supports Lazy K, Crazy J, BLC, BLC8, The Church, and now B Flat): https://github.com/rs-blashyrkh/lazy-k

See also

• Lazy K
• Combinatory logic