Introducing the P Combinator
Easy Two Parameter Currying
or the Functional IfThenElse
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 Pcombinator (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 widelyused and
wellknown 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 SKIcombinators (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 Ucombinator (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.
^{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
situation.
^{6}
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``v
AB
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``v
AB⇒ λA.λB. ```v
AB``<
ABrule of T 2) ⇒ λA. ``s``s``s`kv`k
Ai``s``s`k<`k
Ai
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
^{7} at each step:
1) λA.λB. ``t``<
AB``v
AB⇒ λA.λB. ```v
AB``<
ABrule of T 2) ⇒ λA. ``s``s``s`kv`k
Ai``s``s`k<`k
Ai
Eliminate B 3) ⇒ λA. ``s``s`k`v
Ai``s`k`<
Ai
Turner reductions: ``s`k
x`k
y ⇒`k`
xy4) ⇒ λA. ``s`v
A`<
ATurner reductions: ``s`k
xi
⇒ x5) ⇒ ``s``s`ks``s`kvi``s`k<i
Eliminate A 6) ⇒ ``s``s`ksv<
Turner reductions: ``s`k
xi
⇒ x7) ⇒ ``s``bsv<
Turner reduction: ``s`k
xy ⇒``b
xy
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 andedboolean 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^{8} (of type N
)
and for addition, subtraction (of type N > N > N
) and
comparison (of type N > N >
^{9}) of numbers. We know from
Boolean
commonly used logical connectives in CL^{10} 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κ
e5. λN. ``s``b`r`ki`≤``
Nε`≥``+
Nε
⇒``s``s`ks``s`k`b`r`ki``s`k≤``s``s`ki`kε``s`k≥``s``s`k+i`kε
Eliminate N 6+7. ``s``s`ks``s`k`b`r`ki``s`k≤``s``s`ki`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: ``s
e`kκ
⇒``c
eκ
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κ
e12. ``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κ
e13. ``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 Pcombinator variant (```p`r`ki``b≤``cε``b≥`+ε
) has only 12 applications and only 4 housekeeping combinators to obtain the same result.
The Pcombinator 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 Pcombinator is doing ("apply ∧ to the results of two composed compare operations"), but a simple description of the derived SBCcombinator 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 Pcombinator 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 realworld benefit of the Pcombinator 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 Pcombinator, 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 Pcombinatorial expression:
```p`r`ki``b≤``cε``b≥`+ε
⇒```p`r`ki``b```p`tk<=``cε``b```p`tk>=`+ε
The SKBCrepresentation 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``=
XYEnλ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`<
XX
`=2 Turner reductions: ``s`kκi
⇒κ
5. λX. ``s``s`k`tk`<
X`=
X
⇒
λX.``s``b`tk`<
X`=
XTurner reduction: ``s`kκ
e ⇒``bκ
e6. λ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κ
e10. ``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 SBcombinatorial expression for ≤ with 8 applications and 5 housekeeping combinators. The equivalent Pcombinatorial expression (```p`tk<=
) has only 4 applications and only 1 housekeeping combinator (P itself). The entire SBcombinatorial 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 Pcombinator, this time more obviously so: the above SBcombinatorial expression has a total of 31 applications and 19 housekeeping combinators; on the other hand, the Pcombinatorial 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 hardcoding 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`ci``s`k`b```p`tk>=``s`k+i
Eliminate ε 3+4. ``s``s`k`p`r`ki``s`k`b```p`tk<=``s`k`ci``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κ
e7. ``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 Pcombinator is not immune from the combinatorial explosion the other combinators exhibit during abstractionelimination. This is correct: when used appropriately (currying two parameters), the Pcombinator 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 Pcombinatorial expression is much smaller than the equivalent SBcombinatorial expression. The Pcombinatorial expression has 22 applications and 10 housekeeping combinators. The equivalent SBcombinatorial 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 Pcombinator 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 Mcombinator (Mx = xx), what is a plainlanguage 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 wellknown as
the Ycombinator) 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 backtick
("`"). This departure follows the convention (but not the combinator
symbols) established by
Unlambda^{1}.
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,
^{2}
the elements may be
extracted from the above list
thusly:
^{3}
```vbck
⇒ b
```vbc`ki
⇒ c
The equivalent representations in lambda terms are as
follows:
^{4}
(λx.((λyz.zxy) c
)b
)= list (λxy.x) = fst (λxy.y) = snd (list fst) ⇒ b
(list snd) ⇒ c
Appendix B
The Turner Reductions
``s`k
xi
⇒ x ``s`k
x`k
y⇒ ``k
xy``s`k
xy⇒ ``b
xy``s
x`k
y⇒ ``c
xy
Appendix C
Parameterizing ε in an SBcombinatorial 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`ci``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`ci``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κ
e6. ``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κ
e7. ``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κ
e8. ``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
^{1}  Also, I am following another  
^{2}  Both Smullyan's To Mock a  
^{3}  The usual syntax (pervasive in the
 
^{4}  Strictly speaking, the λcalculus
 
^{5}  This appearance  
^{6}  I have found that the more general case  
^{7}  As relayed by At any rate, I've listed the Turner reductions  
^{8}  There are many valid representations for  
^{9}  Booleans in CL are almost always  
^{10}  Given the standard boolean

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