Introducing the P Combinator
Easy Two Parameter Currying
or the Functional If-Then-Else
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.
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``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``<ABrule of T 2) ⇒ λA. ``s``s``s`kv`kAi``s``s`k<`kAiEliminate 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``vAB⇒ λA.λB. ```vAB``<ABrule of T 2) ⇒ λA. ``s``s``s`kv`kAi``s``s`k<`kAiEliminate B 3) ⇒ λA. ``s``s`k`vAi``s`k`<AiTurner reductions: ``s`kx`ky ⇒`k`xy4) ⇒ λA. ``s`vA`<ATurner reductions: ``s`kxi⇒ x5) ⇒ ``s``s`ks``s`kvi``s`k<iEliminate A 6) ⇒ ``s``s`ksv<Turner reductions: ``s`kxi⇒ x7) ⇒ ``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
Boolean
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:
```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εiEliminate 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εiTurner 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`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κ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 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``=XYEnλification 2. λX.λY. ```tk``<XY``=XY
⇒ λX.``s``s`k`tk``s`k`<Xi``s`k`=XiEliminate 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=iEliminate 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 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+iEliminate ε 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κ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 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,10 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
Unlambda1.
So, for example, the list of the B
(bluebird) and C (cardinal) combinators using the V (vireo) combinator is
represented thusly:
``vbcSo, 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`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+iEnλ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κ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)
