A very minimal base for Concatenative Combinators

Introduction

In a previous article I described an abstraction algorithm for Concatenative Combinatory Logic (CCL) which uses a quite large base for convenience.

The reason was practical: the bigger the base, the shorter the abstracted expressions will be.

In 1, Brent Kirby provided examples of much smaller bases for CCL up to just two combinators and we might ask ourselves: "Does a smaller base exists?".

In other words, we are looking for a single combinator (let's call it 𝗯) from which we can derive any other concatenative combinator.

Of course, such combinator, if it exists, will equivalent to an expression using any of the other known bases.

In search of the single one

For our search, let's use the two-combinators base {𝘀',𝗸}:

          (𝑦) (𝑥) 𝗸  = 𝑥
  (𝑧) (𝑣) (𝑦) (𝑥) 𝘀' = ((𝑧) 𝑣) 𝑥 (𝑧) 𝑦

We are looing for a combinator 𝗯 from which we can calculate the two base combinators 𝘀' and 𝗸:

      𝗸  = (𝗯) 𝗯
      𝘀' = ((𝗯) 𝗯) 𝗯 = (𝗸) 𝗯 

If such combinator exists, it is a base for the Concatenative Combinatory Logic.

Using an helping hand

Before starting, let's assume that the 𝗯 has a certain structure:

    𝗯 = (𝛾) (𝛽) (𝛼) 𝘁 

where 𝘁 is a combinator such that:

  (𝑧) (𝑣) (𝑦) (𝑥) 𝘁 = (𝑣) (𝑦) (𝑥) 𝑧

Since {𝘀', 𝗸} is a base, we could abstract the free variables 𝑧, 𝑣, 𝑦, and 𝑥 from the left side expression and obtain a definition for 𝘁 which only contains 𝘀' and 𝗸 and no free variables. Due to the length of such definition, for convenience, we'll keep using 𝘁 in the following.

For the same reason, we'll use 𝗶 as a shorthand for the equivalent expression () (𝗸) () 𝘀' .

Searching ...

Let's start by finding combinators 𝛾, 𝛽, and 𝛼 such that (𝗸) 𝗯 = 𝘀':

  (𝗸) 𝗯 = (𝗸) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛼) 𝗸 
        = (𝛾) 𝛼 
        = 𝘀'

In other words, we need to find 𝛼 and 𝛾 such that (𝛾) 𝛼 = 𝘀'.

This can be simply achieved by choosing: 𝛼 = 𝗶 and 𝛾 = 𝘀':

   (𝛾) 𝛼 = (𝘀') 𝗶 = 𝘀' 

We also need (𝗯) 𝗯 = 𝗸, which means:

  (𝗯) 𝗯 = ((𝛾) (𝛽) (𝛼) 𝘁) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛼) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛾) (𝛽) (𝛼) 𝛼
        = 𝗸

Lookin at the last equality, it means that 𝛼, 𝛽, and 𝛾 must be such that:

  𝗸 = (𝛾) (𝛽) (𝛾) (𝛽) (𝛼) 𝛼

We already found 𝛼 and 𝛾, we can substitute them in the expression to obtain:

  𝗸 = (𝛾)  (𝛽) (𝛾)  (𝛽) (𝛼) 𝛼
    = (𝘀') (𝛽) (𝘀') (𝛽) (𝗶) 𝗶
    = (𝘀') (𝛽) (𝘀') (𝛽) 𝗶
    = (𝘀') (𝛽) (𝘀') 𝛽

Now, to satisfy the equality

  𝗸 = (𝘀') (𝛽) (𝘀') 𝛽

we need 𝛽 to be a combinator that deletes three arguments and replaces them with 𝗸.

It's easy to see that the following combinator does the trick:

  𝛽 = (((𝗸) 𝗸) 𝗸) 𝗸

In fact:

  (𝑧) (𝑦) (𝑥) 𝛽 = (𝑧) (𝑦) (𝑥) (((𝗸) 𝗸) 𝗸) 𝗸
                = (𝑧) (𝑦) ((𝗸) 𝗸) 𝗸
                = (𝑧) (𝗸) 𝗸
                = 𝗸

Which gives us a definition for 𝗯:

   𝗯 = (𝘀') ((((𝗸) 𝗸) 𝗸) 𝗸) (𝗶) 𝘁

Since, by definition, any expression using only combinators, is a combinator itself, we have found our single-combinator base.

Conclusion

We have proved that there exist a base {𝗯} for the Concatenative Combinatory Logic that is formed by a single combinator.

The result is not surprising as the same result is valid in the standard Combinatory Logic and comes from the fact that the two computational model are equivalent.

For how impractical it may be to use a single combinator as a base, this results may be of interest in some specific context.

Bibliography

(1) The Theory of Concatenative Combinators,
Brent Kerby (bkerby at byu dot net).
Completed June 19, 2002. Updated February 5, 2007.
((link)(http://tunes.org/~iepos/joy.html))