Introducing the P Combinator

Abstract

The language of combinatorial logic (also known as the λ|-calculus) is rich and computationally complete, with a set of 30 or so commonly accepted symbols that serve a variety of purposes. As the combinators mirror λ-terms (but with no variables), it is easy to manipulate the combinators in the context of one implicit argument. One area of awkwardness, however, is the ability to manipulate combinators carrying around two implicit arguments or to imbue a system with simultaneous alternatives. Being complete, such possibilities are, indeed, expressible, but usually after several transformations resulting in an exponential growth of participating combinators.

The P-combinator (mnemonically, the Proposition combinator, but which I have christened the penguin as its familiar ornithological pseudonym), described herein, provides a direct mechanism to represent (binary) alternatives simply and to transport a pair of implicit arguments throughout a set of combinators representing a system, allowing arguments to be curried twice without the associated explosion of the simpler combinators usually saddled with this responsibility.

History/Tutorial

Mathematics has a rich and diverse set of languages that may be used to express proofs and algorithms used both for philosophical and for pragmatic ends. One such widely-used and well-known mathematical language is the λ-calculus, that expresses formulae using λ-terms (or anonymous functions) and their application. Because it has only functions, the λ-calculus is described as a functional language. It, with its imperative or procedural equivalent (the Turing Machine) form the basis of most computer programming languages.

Another such mathematical language is Combinatory logic (also known as SKI-combinators (so named for the most used combinators in that language), and given a much wider audience with Smullyan's To Mock a Mockingbird, and the Unlambda and Lazy K programming languages), which, like the λ-calculus is semantically expressed by functions and their application. In fact, the λ-calculus and combinatory logic are equivalent: every λ-term may be equivalently expressed by an expression of combinators, and vice versa. The most noticeable difference between combinatory logic and the λ-calculus is that the latter has λ, variables and application (there are no given or axiomatic functions) and the former has only combinators and their application (there are no variables, as all parameters are implied). Examples of functions in each language are given in A Note on Syntax

Although combinatory logic has a much smaller audience than the λ-calculus, it does have its champions: Church, Rosser, and Curry (of λ-calculus fame) greatly expanded the field of combinatory logic after Shönfinkel developed it, and Turing made a significant contribution to the field by defining the U-combinator (also known, in the ornithological parlance, as a Turing bird). Because of its expression through combinators (of which approximately 30 are commonly accepted, but are unlimitted in number), vice variable capture (combinator logic has no variables), it is possible to express some functions more succinctly and expressively in combinator logic than in any other form, and, in fact, combinators, and supercombinators, have been used by the functional programming community (notably by Turner as a basis for is programming language Miranda, and then by the Haskell community) to investigate efficient programming language implementation.

The Problem

Each combinator in the language of combinatory logic has a distinct way of manipulating its given arguments to arrive at the functional result. The most widely known combinators fall into several families, based on their functional behavior: permuting birds (Such as T, V, and C), compositional birds (B, and its derivatives D and E), etc., and these families appear to cover the necessary mappings to obtain any possible solution. ⁵ It appears, however, that most combinators are developed with the mindset of (eventually, via currying) transforming one input into one result. Conjoining or composing two combinators to be applied to one argument is easy and natural.

Conjoining combinators where each combinator is to be applied to two deferred arguments is an entirely different situation. ⁶

This problem is unacceptably onerous when formulating propositional logic statements (or conditional statements) in general. So, given that we have expressions for "less than" and "choose" (we will assume there exists a combinator < for the former, and the latter is simply V), the simplest way to express "If A < B then A else B" is the λ-term:

λA.λB.``t``<AB``vAB

A sweet and simple solution. Unfortunately, as combinatorial logic does not have variables, inexpressible in the language, so the λ-terms must be translated into combinator equivalents, using a standard, mechanical, process:

1)	λA.λB.``t``<AB``vAB	⇒	λA.λB.```vAB``<AB	rule of T
2)		⇒	λA.``s``s``s`kv`kAi``s``s`k<`kAi	Eliminate B
3)		⇒	``s``s`ks``s``s`ks``s``s`ks``s`kk`kv    ``s`kki`ki``s``s`ks``s``s`ks``s`kk`k<``s`kki`ki	Eliminate A

Note the length of the resulting combinator expression. It is possible to have a smaller equivalent combinatorial function by applying the Turner reductions ⁷ at each step:

1)	λA.λB.``t``<AB``vAB	⇒	λA.λB.```vAB``<AB	rule of T
2)		⇒	λA.``s``s``s`kv`kAi``s``s`k<`kAi	Eliminate B
3)		⇒	λA.``s``s`k`vAi``s`k`<Ai	Turner reductions: ``s`kx`ky ⇒ `k`xy
4)		⇒	λA.``s`vA`<A	Turner reductions: ``s`kxi ⇒ x
5)		⇒	``s``s`ks``s`kvi``s`k<i	Eliminate A
6)		⇒	``s``s`ksv<	Turner reductions: ``s`kxi ⇒ x
7)		⇒	``s``bsv<	Turner reduction: ``s`kxy ⇒ ``bxy

Thank goodness for Turner's observations: the end result is more succinct than the original λ-term. There are several drawbacks, however. First, one must choose the mechanical translation which results in a long expression or embed the Turner reductions that which result in a concise expression, after a prolonged translation. Second, S(BSx)y works for a simple boolean choice statement (the key is the T combinator at the head is simply eliminated by reversing the boolean and choice binary combinators), but this does not work for a compound boolean statements, and furthermore, building a correct Turner reduction system is not one of the simplest tasks in the field. Third, I use combinators to eliminate the time and the code to build auxiliary predicates used as the functional arguments of mapping or folding functions. In that light, a combinator must be available for immediate use, otherwise I will resort to a λ-term, an auxiliary predicate, or some equivalent.

The Problem Statement

So, the problem is, generally, how to process two input values through two different auxiliary combinators and then unify the results through an output binary combinator. S(BSx)y does the job in only a very specialized case (where the output combinator is just an application), we need a new combinator when the output combinator is something more.

A Simple Example: Near some number X (Compound Conditionals)

A simple min or max functional (as above) is small enough, through Turner simplification, so that a new predicate combinator is not demonstrably necessary, but what about some more complex logic? In this example, we will create an anded-boolean conditional to see if some input number is near some number X, where nearness is determined by some input ε. One way to express this conditional is:

N - ε ≤ X ∧ N + ε ≥ X

Let us start with a simple example and then generalize it into a more complex case. To demonstrate the above "near" condition, we will fix ε and treat it as (an arbitrary) constant. We will also assume combinators exist for numbers⁸ (of type N) and for addition, subtraction (of type N -> N -> N) and comparison (of type N -> N -> Boolean⁹) of numbers. We know from commonly used logical connectives in CL¹⁰ that ∧ is usually taken as `r`ki. Given these conventions, the above condition simplifies to the following CL term:

```p`r`ki``b≤``c-ε``b≥`+ε

Fixing ε arbitrarily to 1, we find with the following input values for N and X the above predicate behaves as expected:

N	X		Reduces to
3	5	⇒	`ki (false)
4	5	⇒	k (true)
5	5	⇒	k (true)
6	5	⇒	k (true)
7	5	⇒	`ki (false)

If we did not have the P combinator available, what would the combinatory expression for the above be? Off the top of my head, I'm not sure, so, to find out what it is, we will walk through the steps necessary to convert a λ-term into combinators, performing Turner reductions along the way.

We start with the λ-term for the above condition (given ε is fixed, as before) and proceed by eliminating the variables via standard transformations:

1.	λN.λX.```r`ki``≤``-NεX``≥``+NεX ⇒ λN.``s``s`k`r`ki``s`k`≤``-Nεi``s`k`≥``+Nεi	Eliminate X
2.	λN.``s``s`k`r`ki``s`k`≤``-Nεi``s`k`≥``+Nεi ⇒ λN.``s``s`k`r`ki`≤``-Nε``s`k`≥``+Nεi	Turner reduction: ``s`kκi ⇒ κ
3.	λN.``s``s`k`r`ki`≤``-Nε``s`k`≥``+Nεi ⇒ λN.``s``s`k`r`ki`≤``-Nε`≥``+Nε	Turner reduction: ``s`kκi ⇒ κ
4.	λN.``s``s`k`r`ki`≤``-Nε`≥``+Nε ⇒ λN.``s``b`r`ki`≤``-Nε`≥``+Nε	Turner reduction: ``s`kκe ⇒ ``bκe
5.	λN.``s``b`r`ki`≤``-Nε`≥``+Nε ⇒ ``s``s`ks``s`k`b`r`ki``s`k≤``s``s`k-i`kε``s`k≥``s``s`k+i`kε	Eliminate N
6+7.	``s``s`ks``s`k`b`r`ki``s`k≤``s``s`k-i`kε``s`k≥``s``s`k+i`kε ⇒ ``s``s`ks``s`k`b`r`ki``s`k≤``s-`kε``s`k≥``s+`kε	2 Turner reductions: ``s`kκi ⇒ κ
8+9.	``s``s`ks``s`k`b`r`ki``s`k≤``s-`kε``s`k≥``s+`kε ⇒ ``s``s`ks``s`k`b`r`ki``s`k≤``c-ε``s`k≥``c+ε	2 Turner reductions: ``se`kκ ⇒ ``ceκ
10+11.	``s``s`ks``s`k`b`r`ki``s`k≤``c-ε ``s`k≥``c+ε ⇒ ``s``s`ks``s`k`b`r`ki``b≤``c-ε ``b≥``c+ε	2 Turner reductions: ``s`kκe ⇒ ``bκe
12.	``s``s`ks``s`k`b`r`ki``b≤``c-ε``b≥``c+ε ⇒ ``s``s`ks``b`b`r`ki``b≤``c-ε``b≥``c+ε	Turner reduction: ``s`kκe ⇒ ``bκe
13.	``s``s`ks``b`b`r`ki``b≤``c-ε``b≥``c+ε ⇒ ``s``bs``b`b`r`ki``b≤``c-ε``b≥``c+ε	Turner reduction: ``s`kκe ⇒ ``bκe

So, after 13 steps (2 variable eliminations and 11 Turner reductions) we have arrived at an equivalent combinatorial expression of the "near" conditional. This one (``s``bs``b`b`r`ki``b≤``c-ε``b≥``c+ε) has 17 applications and 9 substituting/composing/permuting (or "housekeeping") combinators, whereas the P-combinator variant (```p`r`ki``b≤``c-ε``b≥`+ε) has only 12 applications and only 4 housekeeping combinators to obtain the same result.

The P-combinator is already showing its merit, just because of the reduced number of applications and housekeeping combinators used. But it also has a semantic benefit: it is relatively easy to see what the P-combinator is doing ("apply ∧ to the results of two composed compare operations"), but a simple description of the derived SBC-combinator is less straightforward ("apply the composition of the application to the composition of the composition of ∧ with two composed comparison operators" -- got it?). Once the use of P-combinator is understood, it is much faster to grasp what is happening in the context of a combinatory expression using it.

A More Complex Example: Near Some X (composed condition)

The above example gave the problem statement and solution a good deal to show a real-world benefit of the P-combinator with some simplified constraints: we fixed (made arbitrarily constant) ε and were given combinators to represent numbers, arithmetic, and compound comparisons. This example tightens up the scenario a bit by disallowing the ≤ and ≥ comparison combinators, giving simple comparison operators as a replacement. The next example will finish off the scenario by freeing ε as a λ-term. We leave converting the given number, arithmetic and comparison combinators to their more traditional counterparts as a research project for the reader: combinator representations of arithmetic and recursion are outside the scope of this paper.

Combinators are rare birds, with each different combinator defined aimed at serving a specialized goal, so, having a combinator ≤ overlaps overly much with the combinators < and =, as the former compound combinator can be represented as the disjunction of the latter two. Put another way:

X ≤ Y ≡ (X < Y ∨ X = Y)

And, we have a combinator, the P-combinator, in fact, that allows this equivalence directly (the standard combinatorial representation of ∨ is `tk):

X < Y ∨ X = Y ≡ ```p`tk<=

and

X > Y ∨ X = Y ≡ ```p`tk>=

So, we need simply substitute these new predicates for the disallowed compound comparison combinators to obtain a new compound P-combinatorial expression:

```p`r`ki``b≤``c-ε``b≥`+ε ⇒ ```p`r`ki``b```p`tk<=``c-ε``b```p`tk>=`+ε

The SKBC-representation of the same (explicit) compound comparison is less obvious. Again, it is necessary to convert a λ-term in order to obtain the combinatorial expression:

1.	X < Y ∨ X = Y	≡	λX.λY.```tk``<XY``=XY	Enλification
2.	λX.λY.```tk``<XY``=XY ⇒ λX.``s``s`k`tk``s`k`<Xi``s`k`=Xi			Eliminate Y
3+4.	λX.``s``s`k`tk``s`k`<Xi ``s`k`=Xi ⇒ λX.``s``s`k`tk`<X `=X			2 Turner reductions: ``s`kκi ⇒ κ
5.	λX.``s``s`k`tk`<X`=X ⇒ λX.``s``b`tk`<X`=X			Turner reduction: ``s`kκe ⇒ ``bκe
6.	λX.``s``b`tk`<X`=X ⇒ ``s``s`ks``s`k`b`tk``s`k<i``s`k=i			Eliminate X
7+8.	``s``s`ks``s`k`b`tk``s`k<i ``s`k=i ⇒ ``s``s`ks``s`k`b`tk< =			2 Turner reductions: ``s`kκi ⇒ κ
9.	``s``s`ks``s`k`b`tk<= ⇒ ``s``s`ks``b`b`tk<=			Turner reduction: ``s`kκe ⇒ ``bκe
10.	``s``s`ks``b`b`tk<= ⇒ ``s``bs``b`b`tk<=			Turner reduction: ``s`kκe ⇒ ``bκe

So, again, after 10 steps (2 variable eliminations and 8 Turner reductions) we have an SB-combinatorial expression for ≤ with 8 applications and 5 housekeeping combinators. The equivalent P-combinatorial expression (```p`tk<=) has only 4 applications and only 1 housekeeping combinator (P itself). The entire SB-combinatorial expression grows at a steeper rate when the subexpression is substituted for the disallowed compound comparison combinators:

``s``bs``b`b`r`ki``b≤``c-ε``b≥``c+ε

⇒ ``s``bs``b`b`r`ki``b``s``bs``b`b`tk<=``c-ε``b``s``bs``b`b`tk>=``c+ε

Again we see the advantage of the P-combinator, this time more obviously so: the above SB-combinatorial expression has a total of 31 applications and 19 housekeeping combinators; on the other hand, the P-combinatorial expression (```p`r`ki``b```p`tk<=``c-ε``b```p`tk>=`+ε) has only 20 applications and only 6 housekeeping combinators.

Final Example: Parameterized "nearness" to X

Fixing ε is all well and good for one throwaway example or for one project, but suppose, instead of hard-coding a ground ε we free that value for the user of the combinatorial expression to determine how near N and X can be. The obvious way to go about this would be to abstract ε from the entire combinatorial expression ...

1.	```p`r`ki``b```p`tk<=``c-ε``b```p`tk>=`+ε ⇒ λε.```p`r`ki``b```p`tk<=``c-ε``b```p`tk>=`+ε	Enλification
2.	λε.```p`r`ki``b```p`tk<=``c-ε``b```p`tk>=`+ε ⇒ ``s``s`k`p`r`ki``s`k`b```p`tk<=``s`k`c-i``s`k`b```p`tk>=``s`k+i	Eliminate ε
3+4.	``s``s`k`p`r`ki``s`k`b```p`tk<=``s`k`c-i``s`k`b```p`tk>=``s`k+i ⇒ ``s``s`k`p`r`ki``s`k`b```p`tk<=`c-``s`k`b```p`tk>=+	2 Turner reductions: ``s`kκi ⇒ κ
5+6.	``s``s`k`p`r`ki``s`k`b```p`tk<=`c- ``s`k`b```p`tk>=+ ⇒ ``s``s`k`p`r`ki``b`b```p`tk<=`c- ``b`b```p`tk>=+	2 Turner reductions: ``s`kκe ⇒ ``bκe
7.	``s``s`k`p`r`ki``b`b```p`tk<=`c- ``b`b```p`tk>=+ ⇒ ``s``b`p`r`ki``b`b```p`tk<=`c-``b`b```p`tk>=+	Turner reduction: ``s`kκe ⇒ ``bκe

... which actually makes ε the outermost (first) parameter. This transformation also demonstrates that the P-combinator is not immune from the combinatorial explosion the other combinators exhibit during abstraction-elimination. This is correct: when used appropriately (currying two parameters), the P-combinator manages expression growth very well, but when used for more than two parameters, it suffers the same fate as other combinators when they are used to curry more than one parameter.

Even with this additional parameter, the growth of the P-combinatorial expression is much smaller than the equivalent SB-combinatorial expression. The P-combinatorial expression has 22 applications and 10 housekeeping combinators. The equivalent SB-combinatorial expression has 37 applications and 25 housekeeping combinators!

Conclusion

Combinators in CL curry single arguments very well, but have suffered from an exponential explosion in sizes of their expressions when currying more than one argument. The P-combinator reduces growth to linear size when currying two arguments and is therefore very useful in that domain, making (for example) compound logic statements tractable in CL.

Epilogue: A question

Given the expressions for logical relations,¹⁰ and the M-combinator (Mx = xx), what is a plain-language description of the following predicate?

```p`tk`mb``b``v`kik`mb

Appendix A

A Note on Syntax used herein

Combinatorial logic has an unlimitted alphabet (usually capital Roman and Greek letters, asterics, and subscripts) and each combinator may be one or more letters in length (the more fundamental combinators are one letter). Application proceeds from left to right in a combinatory expression, with parentheses used to group subexpressions. The combinator representation used in Smullyan is widely adopted (with the noteable change: the Θ-combinator is more well-known as the Y-combinator) and is used here (they are listed at Combinator Birds), with a major departure: all combinators are lowercase, and parentheses are disallowed -- all application is made explicit with a prefix applicator, the back-tick ("`"). This departure follows the convention (but not the combinator symbols) established by Unlambda¹. So, for example, the list of the B (bluebird) and C (cardinal) combinators using the V (vireo) combinator is represented thusly:

``vbc

So, using the K (kestrel, or true, or left, or first) and the KI (kite, or false, or right, or second) combinators, ² the elements may be extracted from the above list thusly: ³

```vbck	⇒	b
```vbc`ki	⇒	c

The equivalent representations in lambda terms are as follows: ⁴

(λx.((λyz.zxy) c) b)	=	list
(λxy.x)	=	fst
(λxy.y)	=	snd
(list fst)	⇒	b
(list snd)	⇒	c

Appendix B

The Turner Reductions

``s`kxi	⇒	x
``s`kx`ky	⇒	``kxy
``s`kxy	⇒	``bxy
``sx`ky	⇒	``cxy

Appendix C

Parameterizing ε in an SB-combinatorial predicate

1.	λε.``s``bs``b`b`r`ki``b``s``bs``b`b`tk<=``c-ε``b``s``bs``b`b`tk>=``c+ε ⇒ ``s``s`ks``s`k`bs``s`k`b`b`r`ki``s`k`b``s``bs``b`b`tk<=``s`k`c-i``s`k`b``s``bs``b`b`tk>=``s`k`c+i	Enλify and then eliminate ε
2+3.	``s``s`ks``s`k`bs``s`k`b`b`r`ki``s`k`b``s``bs``b`b`tk<=``s`k`c-i``s`k`b``s``bs``b`b`tk>=``s`k`c+i ⇒ ``s``s`ks``s`k`bs``s`k`b`b`r`ki``s`k`b``s``bs``b`b`tk<=`c-``s`k`b``s``bs``b`b`tk>=`c+	2 Turner reductions: ``s`kκi ⇒ κ
4+5.	``s``s`ks``s`k`bs``s`k`b`b`r`ki``s`k`b``s``bs``b`b`tk<=`c- ``s`k`b``s``bs``b`b`tk>=`c+ ⇒ ``s``s`ks``s`k`bs``s`k`b`b`r`ki``b`b``s``bs``b`b`tk<=`c- ``b`b``s``bs``b`b`tk>=`c+	2 Turner reductions: ``s`kκe ⇒ ``bκe
6.	``s``s`ks``s`k`bs``s`k`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+ ⇒ ``s``s`ks``s`k`bs``b`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+	Turner reduction: ``s`kκe ⇒ ``bκe
7.	``s``s`ks``s`k`bs``b`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+ ⇒ ``s``s`ks``b`bs``b`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+	Turner reduction: ``s`kκe ⇒ ``bκe
8.	``s``s`ks``b`bs``b`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+ ⇒ ``s``bs``b`bs``b`b`b`r`ki``b`b``s``bs``b`b`tk<=`c-``b`b``s``bs``b`b`tk>=`c+	Turner reduction: ``s`kκe ⇒ ``bκe

End Notes

Copyright © 2005, Cotillion Group, Inc. All rights reserved.
Author: Douglas M. Auclair (dauclair.at.hotmail.dot.com)