Thursday, January 27, 2005

Introducing the P (Penguin) Combinator

Introducing the P Combinator

Easy Two Parameter Currying

or the Functional If-Then-Else


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

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.


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

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
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
5 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

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


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``<ABrule 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

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
7 at each step:

1)λA.λB.``t``<AB``vAB λA.λB.```vAB``<ABrule 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
numbers8 (of type N)
and for addition, subtraction (of type N -> N -> N) and
comparison (of type N -> N ->
9) of numbers. We know from
commonly used logical connectives in CL10 that ∧ is usually taken
as `r`ki. Given these conventions,
the above condition simplifies to the following CL term:


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

NX Reduces to
35`ki (false)
45k (true)
55k (true)
65k (true)
75`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:


⇒ λN.``s``s`k`r`ki``s`k`≤``-Nεi``s`k`≥``+Nεi
Eliminate X

⇒ λN.``s``s`k`r`ki`≤``-Nε``s`k`≥``+Nεi
Turner reduction: ``s`kκiκ

⇒ λN.``s``s`k`r`ki`≤``-Nε`≥``+Nε
Turner reduction: ``s`kκiκ

⇒ λN.``s``b`r`ki`≤``-Nε`≥``+Nε
Turner reduction: ``s`kκe ⇒ ``bκe

Eliminate N

2 Turner reductions: ``s`kκiκ

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

Turner reduction: ``s`kκe ⇒ ``bκe

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<=

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:


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

2 Turner reductions: ``s`kκiκ

Turner reduction: ``s`kκe ⇒ ``bκe
6. λX.``s``b`tk`<X`=X

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κ

Turner reduction: ``s`kκe ⇒ ``bκe

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:



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 ...



Eliminate ε

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>=+

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!


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,10 and the M-combinator (Mx = xx), what is a plain-language description of the following predicate?


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

So, for example, the list of the B
(bluebird) and C (cardinal) combinators using the V (vireo) combinator is
represented thusly:


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

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

The equivalent representations in lambda terms are as

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

Appendix B

The Turner Reductions

``s`kx`ky ``kxy
``sx`ky ``cxy

Appendix C

Parameterizing ε in an SB-combinatorial predicate


Enλify and then eliminate ε

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

Turner reduction: ``s`kκe ⇒ ``bκe

Turner reduction: ``s`kκe ⇒ ``bκe

Turner reduction: ``s`kκe ⇒ ``bκe

End Notes


Also, I am following another

convention: all combinators are currently only one
character. This seems standard; the early combinators were all labelled
with a single letter (Roman and then Greek), and Unlambda is still
relatively young. My system only has the convention, not a rule, of
using one character combinators.


Both Smullyan's To Mock a
and the paper called
To Dissect a
give examples of representing theorems of
propositional calculus with combinators. I found the following sections
to be particularly helpful: chapters 23 (logic), 24 (arithmetic) and
25 (Gödel's incompleteness theorem) of the former reference, and
the appendix on logic in the latter.


The usual syntax (pervasive in the
literature) for the functions I've used as illustrations are as

My example In standard Combinatory Logic syntax
```vbc`ki VBC(KI)


Strictly speaking, the λ-calculus
does not allow any representation outside of a λ-term, so the
last two expressions, given that the B combinator has a
λ-equivalent representation of λxyz.x(yz) and the C
combinator has a λ-equivalent representation of λxyz.xzy,
would be written by an adherent as the following:

(list fst) (λxyz.zxy)(λxyz.x(yz))(λxyz.xzy)(λxy.x)
(list snd) (λxyz.zxy)(λxyz.x(yz))(λxyz.xzy)(λxy.y)


This appearance
is correct: combinatory logic has been shown to be Turing


I have found that the more general case
holds as well: (functional) programming languages that rely on
currying or sequential composition/application compose and conjoin
functions that are applied to a single argument very easily, but any
attempt to conjoin functions that expect to operate on the same two
arguments separately is much more difficult.


As relayed by
Davie's An Introduction to Functional Programming Systems Using
(p. 156). And grudgingly (un)recommended by the

site (the anti-recommendation comes in light of the fact
that Unlambda has of "feature" of allowing side-effects ... as some
argue that side-effecting code opens Pandora's Box to a host of
potential bugs, perhaps, one can argue, that its inventor, David Madore,
used the side-effective programming style to obfuscate it further).

At any rate, I've listed the Turner reductions


There are many valid representations for
in CL: the most common is Church numerals, but, personally,
I prefer the Peano representation. There are also works that
demonstrate binary representations that can be applied to make n-ary
(even decimal) representations of numbers. So long as the number
system is consistent, including the operators for the zero-test and
transition, then any representation works.


Booleans in CL are almost always
represented by the combinators k (for true) and
`ki (for false). I have read one paper that allowed
only the s and k combinators and so used
`sk for false (as it is extentionally equivalent to
`k``skk (`ki in the sk-basis)
and obtains the result with fewer reductions). This document follows
the more-common usage: k as true and `ki as


Given the standard boolean
the following combinators act as logical connectives:

Logical connective Combinator
¬ (not)``v`kik
⇒ (implies)`rk
∧ (and)`r`ki
∨ (or)`tk
≡ (equivalent)``cs``v`kik

Copyright © 2005, Cotillion Group, Inc. All rights reserved.
Author: Douglas M. Auclair (

Friday, January 7, 2005

Combinatory Logic Miscellanea

Combinatory logic treats all arguments ("variables") as implicit and does a very good job of handling implied arguments one at a time (via 'currying'). There also exist several standard combinatorial expressions to represent propositional logic relations (and, or, implies, not, etc.) Many logic relations are binary: handling more than one implicit argument at a time tends to cause combinatory expressions to grow exponentially in size. In the following paper I introduce a new combinator (the P-combinator) that is designed to curry two arguments across multiple using combinators at linear (not exponential) cost in size.

I've provided a series of puzzles, thematically linked, on combinatory logic. Try your skill at solving these Bird Puzzles.

Implementing the 'v' functor of Unlambda (also known in the literature as a hopelessly egocentric bird) using only s, k, and i poses an interesting challenge. I have written a paper entitled Meditations on the Void that shows various attempts at this task as well as a successful implementation.