Some Puzzles Regarding Combinatorial Birds

Table of Contents

• "Once upon a time..."


• Rules of the forest
  
  
  
  1. Rule 1: order
  
  
  2. Rule 2: normal order
  
  
  
  


• Six Species of Birds
  
  
  
  1. Identity Bird
  
  
  2. Mockingbird
  
  
  3. Kestrel
  
  
  4. Cardinal
  
  
  5. Bluebird
  
  
  6. Starling
  
  
  
  


• A walk in the forest: Examples
  
  
  
  1. Example 1: the Kestrel-identity bird
  
  
  2. Example 2: the Kite
  
  
  
  


• Puzzles
  
  
  
  1. Puzzle 1: the Identity-Kestrel bird
     
     • Exercise 1: IKCB bird
     
     
  
  
  2. Puzzle 2: the Kite, reprised
     

     
     

     An Interlude, with intriguing
     experiments

     
     

     
     
     1. Experiment 1: an egocentric bird
     
     
     2. Experiment 2: a hopelessly egocentric bird
     
     

     
     

     
     
  
  
  3. Puzzle 3: Three little birdies...
  
  
  4. Puzzle 4: the Quartet

«It était un fois...» OR "Once upon a time..." there was a magical forest inhabited by singing birds.¹ What was magical about this forest was not the birds, as one can find birds that sing most anywhere, and the species of the birds of this magical forest can also be found in many forests around the world. No, it was the songs of the birds that were magical, for a birds song would remain present in the air, present, as if it were a thing unto itself. Furthermore, a bird's song, when joined by other bird songs, could, and often did, change into another bird song (bird songs affected the sound of other bird songs), and a bird song could change the birds in the area, causing them to fly away, or to change their position on the branch, or (this is truly amazing) to become an entirely different species of bird.

The magic properties of the bird songs of this forest obeyed a set of rules. The first rule is that the order in which birds sing is important and affects the combined bird song produced. The second rule is that birds' songs are combined to produce a new bird song in a very specific order ... the normal order is that the first bird singing is first one to be combined into the resulting bird song, but this norm may be changed by the specific bird singing, as you will see below. Let us observe six species of birds to get a feel for these rules.

1. The simplest of birds in the forest is the identity bird. When it sings, and another bird joins it in song, only that second bird's song is present. It is as if only that second bird is singing.²





2. The second bird behaves very much like the identity bird, but the results are by no means simple. The mockingbird, when it sings, and other bird sings in response, mimics the other bird's song exactly. It is if two birds of the same species are singing together.





3. The first two birds sing along with only one other bird. The kestrel sing along with two other birds. When the kestrel sings, joined by one other bird's song, and then the singing is joined by a second, then the kestrel flies off with the second bird, leaving the first bird singing alone. It is as if the only the first bird were singing and the other two (the kestrel and the second singer) had never come to sing.





4. The cardinal, besides being a very pretty bird to look at, participates with three other singing birds. The effect of the cardinal's song is rather difficult to describe but rather simple in its results: when the cardinal sings, and three other birds join in order (let us call them 'a', 'b', and 'c' simply to identify them), the resulting bird song is a combination of a's song, followed by c's song and then followed by b's song. Simply put, the last two of the three birds' songs are reversed in their order.

   
   
   

   So, normally (as per the second rule), the three birds singing together would produce the 'abc' song, but the cardinal-abc song is different: it is the 'acb' song.





5. Hang onto your hats, because it gets a wee bit harder from here, for now we meet the bluebird. The bluebird, like the cardinal, sings with three other bird, and, like the cardinal, the last two birds of the three other birds sing differently: a bluebird, joined by birds a, b, and c, have a combined song as if a's song is joined by the song produced by first combining the songs of b and c (in order) together.

   
   
   

   So, normally (again, as per the second rule), the three birds singing together would, again, produce the 'abc' song, but the bluebird-abc song is the song of two birds: the bird 'a' and the bird 'bc' which, for simplicity's sake we will write as the 'a(bc)' song.

   
   
   

   Do you see the magic of the bluebird? Four birds are singing together (the bluebird and birds a, b, and c), but when the bluebird flies away, it leaves behind two birds (not three), the first is as it was, but the second bird is an entirely different bird than the other two birds that it has somehow magically replaced.





6. Finally (best for last, as they say), the starling also sings along with three other birds, but the resulting song is quite different than the songs of the bluebird or cardinal: a starling-abc song is the song of a singing with c and that song is joined by the combined song of b singing with c, or, put simply, the starling-abc song is 'ac(bc)'.

   
   
   

   The starling's song is somewhat like the cardinal's song: the first bird remains, and the third bird takes second position. And its song is somewhat like the bluebird's: the second and third bird combine their song to form a new bird song, but it's also more complicated than both the cardinal's song and the bluebird's song taken alone or, for that matter, those two birds' songs combined in any way.³

A walk in the forest (two examples explained)

Example 1: the kite song...

So, now that we are acquainted with some birds, let us look at a few properties and some differences of combined bird songs. We saw above that the kestrel-ab song results in just a's song, in effect choosing a's song over b's song. We will now meet the kite. The effect of the kite's song is to choose the second bird's song. The amazing thing about this bird is that it is the result of two other birds singing: the kestrel and the identity bird.

... as a kestrel-identity bird song

Come, join me for a walk into the forest to see how this comes to be. Ah, here is a tree upon which a kestrel is perched on one of its branches! Let's wait for an identity bird to land.

While we're waiting, let me remind you that it's important that you do not whistle while you wait (nor, for that matter, "whistle while you work"), because your whistling will combine with any bird's song in the air, possibly having very strange affects on you!

Aha! I see an identity bird coming to land on the branch now, and look what is happening to to bird song in the air: it was the kestrel bird song, but now it has become the kestrel-identity bird song (or, as we have said, it has now become the kite bird song, but we will refer to this particular song as the 'kestrel-identity' bird song and see how, with two more birds joining in, that it is the same song as the kite's).

Now that the kestrel-identity bird song is in the air, let us see what happens when two more birds join in with their songs. Here comes a cardinal now: it has perched itself besides the other two birds and begun singing. But, what's this! The kestrel and the cardinal have just now flown off together; just as the effect of the kestrel song has dictated. So, now, only the identity bird remains.

So, the final bird, which happens to be a bluebird, has come to land and has begun singing with the identity bird. And, we see the identity bird fly away, leaving the bluebird happily alone to sing its song.

Example 2: the kestrel-identity bird song is a kite song

In short, the kestrel-identity-cardinal-bluebird song is the same as the bluebird song. Is the kite-cardinal-bluebird song also the bluebird song? Let's go to another tree, where a kite is singing by itself and see if this is indeed the case.

Here's a nicely-aged cypress where we can watch the birds without them observing us, and, fortunately, there is a kite singing in one of its many tangled branches. By the way, isn't it nice and cool in the shade of this cypress? I particularly like the sweet smell it imparts to the surrounding air.

Flying in to perch next to our kite is a cardinal, just as we had hoped, and it joins in singing with the kite. And, close on its wings (do birds have heels, I wonder?) comes a bluebird.

Yes, the kite and the cardinal have flown off as soon as the bluebird started singing. Leaving just the bluebird to sing its song alone. So, the kite-cardinal-bluebird song is the same as the bluebird song itself. And, more generally, the kite bird song and the kestrel-identity bird song always behave equivalently.

Puzzles

Puzzle 1: The identity-kestrel bird song

From the rules of bird song above, we know that the order in which birds sing is important. So, we may guess that the identity-kestrel bird song is not an equivalent song of the kestrel-identity bird song (the latter song is equivalent to the kite's song). So, puzzle 1: what (sole) bird's song is equivalent to the identity-kestrel bird song?

Exercise 1: list the four birds' songs, in their simplest representations (i.e. using the fewest number of birds possible to describe the bird song), when the following four birds fly up in order to perch on yonder apple tree branch: an identity bird, then a kestrel, then a cardinal and finally a bluebird.

1. identity bird song (so, this first song is a freebie)




2. identity-kestrel song:




3. identity-kestrel-cardinal song:




4. identity-kestrel-cardinal-bluebird song:

Puzzle 2: a kite by any other name...

We've seen that the kestrel-identity bird song is equivalent to the kite's. Here's a paradoxical puzzle: if there are no identity birds in the forest, what two birds from the birds of the other five species (which are the mockingbird, the kestrel, the cardinal, the bluebird, and the starling) when combining their bird song have an equivalent song to the kite's?

Please note! This puzzle allows for only two birds to equate the kite's song. Specifically, multiple birds from two species of birds may equate to the kite's song, but will not give the correct answer to this puzzle.

Interlude

Birds of a feather ...

... may flock together, but that means very little to the bird songs produced by multiple birds of the same species.

... may produce the same song ...

But first, a counter-example: we see that one species of bird that can have any number of birds sing together and still produce the same song is the identity bird. We have seen that identity bird is fond of any bird: even of itself. We will now see that if our magical forest has only one species, the identity bird species, that the songs produced are egocentric (even hopelessly so) as well as being fond.

An egocentric bird song is a song that when combined with the song of the same species of bird produces its own bird song. So, if bird x sings an egocentric song, the bird song xx is x (whereas instead if bird x were fond of bird y, the bird song xy would be y).

A hopelessly egocentric
bird song is one that, no matter what other bird joins in the singing, it is as if the new bird were shouted down into silence.

So, back to our magical-identity-bird-only forest we see that the bird songs produced are fond (an identity-identity bird song produces the latter bird song ... which so happens to be an identity bird song), as well as egocentric (an identity-identity bird song produced the identity bird song), and even hopelessly egocentric (no matter what bird joins in the singing ... and in this particular forest, the bird joining will always be an identity bird ... the result is always the first bird who sings, which so happens, again, to be the identity bird).

All this goes to show that no matter how many identity birds sing together, the song will always be the same. This is very often not the case for other birds of the same species singing together, as we shall now see.

... but probably will produce different songs...

Let us look at a flock of kites. When two kites sing together, we get an identity bird's song! Let's see how this occurs.

We're back in the forest under that old cypress, again. The kite has returned, and it is soon joined by another kite. They sing together, and their song attracts a cardinal that lands next to them and begins to sing, too. As soon as the cardinal sings, the first kite flies off, taking the second one with it. Only the cardinal remains, singing its song. The two kites singing together is equivalent to the identity bird's song.

So, the second puzzle was called paradoxical because it is impossible for a forest not to have an identity bird when the forest has kites: when an even number of kites sing together, the bird song is inevitably an identity bird's.

In short, two kites singing together does not produce a kite's song, as one would expect, but, because of the magic of this forest, the resulting song is the identity bird's song. We have already stated this more generally: given a kite and two other birds, x and y, the bird song kite-xy is y's bird song -- or, for any x, kite-x is fond fond of any and every bird.

The one-two punch-line

The purpose of this interlude was to show that two or more birds of the same species do not necessarily produce the same song. We have also introduced two new properties (the egocentric property and the hopelessly egocentric property) that we will not use directly in these puzzles ...

But these properties are rather intriguing. So, if you'd like to pursue some experiments here are a couple of areas to explore:⁴

1. Find an egocentric bird song other than the identity-identity bird song. One such song is made of three birds of two species.





2. Find a hopelessly egocentric bird song in our magical forest that allows all the birds under discussion.⁵

   
   
   

   A hint: the kestrel is only fond of hopelessly egocentric birds.

   
   

   
   
   

Puzzle 3: three little birdies sitting on a tree...

Enough of that interlude! Let us return to the central theme. For this
puzzle we will be looking for birds that produce songs that give us one of three birds that land on the branch to join in the song. As an aid, you may work with the following three birds that land and begin singing in order: a starling, a mockingbird and a cardinal. But, remember: the birds you find to produce the appropriate bird song should work correctly with any set of three birds.

1. Find a bird song that produces only the first bird's song (in this case, the starling's, or, put another way: the bird song you find combined with the song of the starling, then the mockingbird, and finally the cardinal will produce the starling's song). I found it with three birds of two species.





2. Find a bird song that produces only the second bird's song (here, the mockingbird's). I found two such songs, each song had two birds.





3. Find a bird song that produces only the third bird's song (the cardinal's). I found a song with two species of birds.

Puzzle 4: Four calling birds

Now you have the ability, given a pair of birds, to find the first or the last (second) bird of that pair (using the kestrel and the kite), or, given three birds, to find the first, second or last bird (using the ... oops! you found that out yourself, anyway, so there's no need for me to tell you). Let us take those mad-skilz (yo!) of yours to single out birds in a quartet.

In keeping with the quartet theme, and to add a modicum of confusion by mixing metaphors, the four birds that fly up to join in the bird songs you discover are, in order, suprano, alto, tenor, and bass. We may not know what affect these birds' songs have, but I must say, they do make lovely music, indeed!

1. Find a bird song that results in the suprano singing an aria -- perhaps "The Spring" by Sir Theopholus Pinkum?




2. It's a rare thing indeed, but, what is a song that has the alto singing a solo?

   
   
   

   I suppose there's always a solo for the contralto in a Gilbert&Sullivan vehicle. And, as the word 'alto' is viewed with some scorn in that community, such singers often refer to themselves as 'mezzo-suprano' ... an interesting euphamism, that: Mahler's Second Symphony has about two seconds where the alto mezzo-suprano sings unaccompanied by the suprano.





3. It is an unfortunate happenstance that there are an overabundance of tenor solos (in fact, one such album containing a plethora of such showtunes sung by three such tenors come to mind as I write this section) that we must be forced to sit through maintaining a façade of rapt admiration and attention. Please find a bird song that furthers this entrenchment.





4. The bassist ... unless we mean bassist as in the player of that big-ole violin in the jazz ensemble ... suffers much of same fate as the 'alto' soloist (and, according to Peter Schickele, also known as P.D.Q. Bach, the bassist in a jazz ensemble should suffer that fate): the only two songs in the repetoire must be "Old Man River" and "Thus Says the Lord" (and I don't think Handel was thinking about the Mississippi when he composed the Messiah ...): let's give the poor guy a helping hand, shall we? What is a bird song that allows our bass bird to sing his heart out uninterrupted? (Remember: bass is not spelt: 'H-A-M').

---

Endnotes

1	Opening strongly inspired by [S85]: the introduction to chapter 9.
2	This property of two birds songs combined to produce the second's bird song is called fondness. The indentity bird is fond of any and every bird; other birds, that do not equate to the identity bird, may have a fondness to one or a few birds, but not all birds -- the identity bird is special in this regard.
3	Even more significantly: a starling cannot be produced from any combination of the bluebird, cardinal and identity bird. So, there are some (other) magical forests that contain only bluebirds, cardinals, identity birds and starlings.
4	[S85], chapter 11, §3 and §4
5	I would be flattered if you arrive at the same bird that I did, but you may find the meditations on the subject amusing, rather convoluted, or, dare I write, hopelessly egocentric. Besides, the previous endnote shows a much more straightforward way of finding a hopelessly egocentric bird song.

---

Works consulted

[S85]

To Mock a Mockingbird and other logic puzzles including an amazing adventure in combinatory logic, by Raymond Smullyan, Alfred A. Knopf (pub), New York, 1985.

---

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

Introducing the P (Penguin) Combinator

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

1	Also, I am following another Unlambda 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.
2	Both Smullyan's To Mock a Mockingbird and the paper called To Dissect a Mockingbird 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.
3	The usual syntax (pervasive in the literature) for the functions I've used as illustrations are as follows: My example In standard Combinatory Logic syntax ```vbck ≡ VBCK ```vbc`ki ≡ VBC(KI)
4	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)
5	This appearance is correct: combinatory logic has been shown to be Turing complete.
6	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.
7	As relayed by Davie's An Introduction to Functional Programming Systems Using Haskell (p. 156). And grudgingly (un)recommended by the Unlambda 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 above
8	There are many valid representations for numbers 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.
9	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 false.
10	Given the standard boolean representation9 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 (dauclair.at.hotmail.dot.com)

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.

Definite Clause Grammars

Not Just for Parsing Anymore

Abstract

Definite Clause Grammars (DCG) have proved to be a
system to build parsing systems simply and
effectively. Unfortunately, DCG are so effective as a parser
building tool, that their other uses are too often ignored -- it
seems that DCG have been pigeon-holed into a parser building
niche. This paper demonstrates the common usage of DCG and then
expands these common usage patterns into areas other than
parsing, showing that DCG are effective means of increasing
programming efficiency while simultameously maintaining (or even
clarifying) declarative semantics.

Introduction to DCG

Definite Clause Grammars (DCG) are syntactic extentions to
Prolog that allow a subset of definite programs
¹ to
be written as Prolog programs. DCGs, and the definite programs
they represent, facilitate, among other things, an almost
unchanged translation of grammars defined in Bacchus-Naur Form
(BNF) into (parts of) Prolog programs -- DCG is a useful tool
for generating parsers and scanners.

Take, for example, a simple command-control language for,
e.g. a robot-arm,
² issuing
commands as per the following:

up down up up down

An example representation of the above grammar in BNF for the
above language is as follows ...

< move > ::= < step > < move >

< move > ::= < step >

< step > ::= up

< step > ::= down

... and the equivalent Prolog program using DCG is the
following:

move --> step, move.

move --> step.

step --> [up].

step --> [down].

This nearly direct translation is simply amazing, especially as
compared to other programming language families. It is
inconceivable in other programming languages to
construct a scanner for the above language so concisely in the
native representation. The other amazing facet, not discussed
here, is that the scanners and parsers scale with the grammar's
complexity linearly ... writing scanners and parsers in
other programming languages becomes much more difficult with
increasing complexity, because, usually, such scanners and
parsers increase in complexity polymonially or even
exponentially to the complexity of the grammar.

Unfortunately, perhaps, because the above scanner and
associated parsers are so facilitated by DCGs, the other uses
of DCGs are too often overlooked. Let's step back from the
application of DCGs and examine the essentials -- DCGs provide a
system: accepting some atoms and updating the state of the world
or rejecting others and backtracking to find a match, so DCGs
provide (in other words, guarantee) a limited subset symbols and
associated actions on those symbols.

Type systems can be viewed in a similar fasion: they accept
some inputs (compiling and executing on accepted instantiated
values) and reject others (causing a compilation failure). The
advantages of typeful systems has been covered exhaustively in
the literature, and programming systems developed recently
accept programming with types as a matter of course. Viewing
DCGs in a similar light of types can convey the advantages of
types in a programming language without types.

One of the oft-trumpeted advantages of programming with
(static) types is that programs with type declarations execute
faster than equivalent programs without types (or with dynamic
typing). Why? Types form a duality: those things acceptable
to perform computations, and those other things that are not to
be used in the computation. Given that duality, the system can
perform the computation in the safety that all the values are
valid (in that they conform to the formal type). Under a
dynamic typing system, the system must first check the type of
each value, ensuring that the value's type is acceptable, before
it can perform any computation. In a statically typed system,
every check is compiled away (verified) before execution
occurs.

Definite Clause Grammars can provide the same service that
static typing does. In the usual case, a scanning/parsing
system receives a language (set of data) that (we hope) conforms
to the grammar. However, we can build a system where we control
the grammar definition AND the input data set. A good example
to examine where this approach yields effective results is in
the domain of generate-and-test problem-solvers.

SEND + MORE = MONEY

(Cryptarithmic problem solvers)

Cryptarithmic problem solvers take a trivially encrypted
mathematical problem and determine what that problem
represents. The most general case is that a symbol stands for
any digit at each position, e.g.:

       6 . .
     x # . .
-------------
       # . .
   # . . .
+ # 5 . 5
-------------
 # . 5 . 4 .

where	# stands for any digit other than 0, and
	. stands for any digit

The above problem solved in the usual manner would take the
generate-and-test approach:

digit(0). digit(1). digit(2). digit(3). digit(4).
digit(5). digit(6). digit(7). digit(8). digit(9).

first_digit(X) :- digit(X), X > 0.

And would provide ways to construct representations of
(composite) numbers and translations to and from these
representations and the "actual" numbers they represent (so, for
example, the system can use the standard operators to perform
arithmetic):

as_number(Digits, Number) :- as_number_aux(Digits, 0, Number).

% an auxilary pred to make the above interface pred tail recursive3
as_number_aux([], Num, Num).
as_number_aux([Digit|Digits], Num, Result) :-
 NewSum is Digit * 10 * Num,
 as_number_aux(Digits, NewSum, Result).

as_list(0, []).
as_list(N, [Digit|Rest]) :-
 N > 0,
 Digit is N mod 10,
 Remainder is N // 10,
 as_list(Remainder, Rest).

Then, using the above, one converts the problem as written into
the equivalent representations and asks the system to find the
solution (note that the above list representation puts numbers
in reverse order: units are the first element of the list):

dots([SixNum, Multiplier, Ones, Tens, Hundreds,  Solution]) :-
 digit(A), digit(B),
 as_number([B, A, 6], SixNum),
 digit(C), digit(D), first_digit(E),
 as_number([C, D, E], Multiplier),
 Ones is SixNum * C, Ones < 1000,
 Tens is 10 * D * SixNum, Tens < 100000,
 Fivers is SixNum * E, as_list(Fivers, [5, _, 5, _]),
 Hundreds is Fivers * 100,
 Solution is Ones + Tens + Hundreds,
 as_list(Solution, [_, 4, _, 5, _, _]).

A Pentium Windows system using SWI Prolog
solves this problem
in 0.79 seconds, or 476,919 inferences in 0.79 seconds (602827
Lips). Pretty impressive, and, for this
general type of problem there's no need to improve on this
generic generate-and-test methodology.

What happens with a cryptarithmic problem with more stringent
constraints, such as uniqueness? To solve the equation ...

 SEND
+ MORE
------
MONEY

... one could use the generate-and-test approach, and enforce
that each letter represents an unique digit:

send_more_money([Send, More, Money]) :-
 first_digit(S), first_digit(M),
 digit(E), digit(N), digit(D), digit(O), digit(R), digit(Y),
 all_different([S, E, N, D, M, O, R, Y], []),
 Send is S * 1000 + E * 100 + N * 10 + D,
 More is M * 1000 + O * 100 + R * 10 + E,
 Money is M * 10000 + O * 1000 + N * 100 + E * 10 + Y,
 Money is Send + More.

all_different([], _).
all_different([Num|Rest], Diffs) :-
 not(member(Num, Diffs)),
 all_different(Rest, [Num|Diffs]).

And such an approach, as above, is simple to implement, and
easy to understand, but the runtime cost is enormous -- it took
1,571,755,688 inferences in 1817.34 seconds (864865 Lips) to
find the solution. Instead, let us
reexamine the problem constraint (uniqueness) and use it to
provide information to the problem solver so as to facilitate
its effort, and at the same time retain the clarity of the
declarative syntax.

The uniqueness constraint tells us that each letter must
represent an unique digit. This can be described inductively:

• S can be any first_digit, or [1..9];


• E can be any digit except the digit captured by S,
  or [0..9] - [S];


• N can be any digit except the digits captured by S and E,
  or [0..9] - [S, E];


• ... etc.

Looking at the above inductive description of the unique
constraints shows a consumer pattern very much like how a DCG
system consumes symbols from a list. So, we'll implement just
such a system; in this particular case the symbols of the list
are digits. As we rewrite the system to use DCG to replace the
generate-and-test predicates, the digit/1 predicate
becomes a definite predicate that consumes a digit from the
(input) digit list and the first_digit/1 predicate
becomes definite, as well:

takeout(X, [X|Y], Y).
takeout(X, [H|T], [H|R]) :- takeout(X, T, R).

digit(X) --> takeout(X).4
first_digit(X) --> digit(X), { X > 0 }.

Then the solution predicate changes in that it now operates
under the structure of DCG with the input list being the
enumerated ten digits (and we also include an interface
predicate so that the user is not burdened with providing the
digits):

send_money_quickly([Send, More, Money]) :-
 do_send_moola([Send, More, Money], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _).

do_send_moola([Send, More, Money]) -->
 first_digit(S), first_digit(M),
 digit(E), digit(N), digit(D), digit(O), digit(R), digit(Y),
 { Send is (S * 1000) + (E * 100) + (N * 10) + D,
   More is (M * 1000) + (O * 100) + (R * 10) + E,
   Money is (M * 10000) + (O * 1000) + (N * 100) + (E * 10) + Y,
   Money is Send + More }.

Did you notice that the above code now has no uniqueness
check? By translating the code into a definite
predicate, we guarantee that each logical variable
holds an unique digit at unification! What is occuring here, by
using DCG to assign unique digits is equivalent to creating a
type for each logical variable, and each successive type is more
restrictive than its predecessor. The code (algorithm) changed
very little structurally, but what does this DCG-as-types
modification buy us?

Quite a bit. The reduction in cost at runtime is astounding!
This new system solves the equation using only 8,215,467
inferences in 36.91 seconds (222562 Lips). This is nearly
fifty times faster than the fully nondeterministic
version presented first. By iteratively restricting the search
space with DCG we have simulated a type system that allows the
system to find a solution much more efficiently without
sacrificing the clarity of the declarative semantics of the
problem description.

Summary for DCGs as Types

The above example demonstrates when one needs to search a
restricted solution space, DCG can provide runtime benefits over
pure nondeterminism without sacrificing clarity of code (as so
many other "optimization" techniques do). The above example
also demonstrates that if the search space becomes more
restrictive in a predictable way over the duration of the
search, DCG can provide enormous runtime benefits.

DCG Implementation of Dynamic Programming

DCGs are effective parser generators and are commonly used as
such, we've also seen that DCGs can simulate types and reap the
benefits of static type systems in a dynamically typed
environment. DCGs have other uses as well. One such use is to
simulate dynamic programming,
⁵ which
computes solutions from an iterative bottom-up approach instead
of (usual for Prolog and other languages that rely on recursion)
the recursive top-down approach.

Dynamic programming shines where the solution must be
approached incrementally from a known-good set of states,
usually these are situations were a declarative top-down
description of the solution leads to a combinatorial explosion
of attempted solutions that can overwhelm any computational
resource. An excellent example of such a problem is computing
the nth Fibonacci number.

Only some Fibonacci numbers declaratively

Below is the formula to find the nth Fibonacci number:

fib n | n == 0    = 1
     | n == 1    = 1
     | otherwise = fib (n-1) + fib (n-2)

Or, as translated (naively) into Prolog:

naive_fib(0, 1).
naive_fib(1, 1).
naive_fib(X, Y) :-
 X > 1,
 Idx1 is X - 1,
 Idx2 is X - 2,
 naive_fib(Idx1, A),
 naive_fib(Idx2, B),
 Y is A + B.

This is all very well and good, but, unfortunately, the above
specification is exponentially recursive ... not only does it
take a long time to find a solution, but it can only find the
first few decades of solutions before running out of available
computational resources (memory). A query of
naive_fib(20, X) takes 65,671 inferences in 4.54
seconds (14476 Lips) to find the
solution, but a call for the 30th
Fibonacci number causes an "out of local stack" error.

The problem with the top-down approach is that it attempts
to find the solution by finding the two previous (unknown)
solutions, until it locates a known answer. Unfortunately, the
bottom is too far down to be reached with the resources
available, and the problem does not make conversion into a
tail-recursive solution practicable.

Any Fibonacci, quickly, with DCGs

DCGs solve this problem by simulating dynamic programming
... approach the solution from a set of known states, and keep
building from that known state until the system finds the
solution. This approach has the additional advantage that since
it is iterative, it eliminates the exponential recursive
explosion that the previous declarative approach suffered.

The idea is use a list⁶
to memoize
the result set as the solution space grows, until the system
reaches the desired solution;
⁷ that is
where DCGs assist us in maintaining a declarative description
while controlling resources. Declaratively, then, if the
requested Fibonacci number is at the head of the solution list,
then return it:

fibonacci(X, [X|_]) --> [].

Otherwise, if we're at then end of the list and still have not
found the solution, push the next two Fibonacci numbers onto the
result set and keep searching:

fibonacci(X, [A, B]) -->
 next_fib(X, A, B, Fib1),
 next_fib(X, B, Fib1, Fib2),
 fibonacci(X, [Fib1, Fib2]).

Finally, if we're in the middle of the result set and have not
found the solution, keep searching:

fibonacci(X, [A, B|Rest]) -->
 succ_push(X, A),
 fibonacci(X, [B|Rest]).8

The DCG housekeeping methods are what one would expect:

% Ensures the current fib is not the one we need, generates a new
% one, and pushes the current one onto the result set.
next_fib(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
 succ_push(X, fib(Idx1, Num1)),
 { Idx3 is Idx2 + 1,
   Num3 is Num1 + Num2 }.

% add a definite branch to gt that pushes the compared-to element
% onto the end of the list (transformed into a difference list)
succ_push(A, B, Old, New) :-
 gt(A, B),
 concat([Old|T1] - T1, [B|T2] - T2, New).9

As before, we retain the declarative nature using DCGs to solve
the problem, but we also obtain the benefit of much more
powerful computational ability with much less runtime cost,
¹⁰ to wit:
quick_fib(1450, X) finds the
solution using 12,327 inferences in
0.02 seconds (615464 Lips) -- out-of-reach and impossibly fast
for the top-down standard predicate.¹²

Conclusion

Definite Clause Grammars (DCGs) have long been known to be an
effective tool to generate scanners and parsers. In this
article, we explore alternative uses for DCGs, such as emulating
static type system and implementing dynamic programming system.
We have seen that, unlike other "optimization" techniques, DCGs
maintain or even improve the clarity of declarative
specifications while at the same time providing the benefits
of these other systems. These benefits are manifested as
improvements by orders of magnitude in both computational power
and the speed at which the runtime achieves desired
solutions.

---

Endnotes

1	Definite programs and Prolog programs using DCG to model definite programs is discussed in detail in [DM93].
2	This example is developed in [Bratko01], chapter 21, with two alternative BNF representations offered.
3	A naive version of as_number/2 would be ... as_number([], 0). as_number([Digit|Digits], Result) :- as_number(Digits, Rest), Result is Digit + 10 * Rest. ... but this is not tail recursive, an so may not benefit from optimization from the Prolog system. In general, this kind of transformation from a "naive" recursive system to one that uses an accumulator is known as folding, and is the result of the fruits of research in the functional programming community.
4	We use takeout/3 instead of delete/3 because delete/3 is not reversible, eliminating the desired backtracking to explore alternate solutions. The definition, use, and a wonderful explanation of takeout/3 come from [Fisher99], § 2.7.
5	Dynamic programming is discussed in detail in [RL99], which provides an implementation of a generic dynamic programming algorithm in the Haskell programming language.
6	Actually, [RL99] uses a dictionary, not a list, as the data structure to memoize the known state, but the difference list approach was so effective that it was unnecessary to use a different data structure.
7	As each Fibonacci number is computed from the previous two Fibonacci numbers, I found it most convenient to use (specifically) a difference list as the data structure to memoize the results.
8	We have two iteration branches for this predicate. The first adds two more Fibonacci numbers when we've come to the final two Fibonacci numbers in the result set; the second continues iteration because there are more than two remaining Fibonacci numbers. As we need two Fibonacci numbers to compute the next Fibonacci number, these two branches guarantee that we perform that computation when we reach the last two numbers, and not before. This approach forms the basis of this dynamic programming system.
9	The implementation of concat/3 is straight from [Bratko01], § 8.5.3. (concat(A1-Z1, Z1-Z2, A1-Z2)).
10	Not only that, but this solution also provides the history of all the Fibonacci numbers prior to the requested one in a difference list by calling fibonacci/4 directly;11 the traditional top-down solution provides no such history.
11	The resulting difference list can be converted into human-readable form with the following predicate: simple_list([]) --> []. simple_list([H, Datum|Diff] - Diff, L0, List) :- simple_list(H, [Datum|L0], List).
12	An implementation using monads in Haskell for the fibonacci computer is available at logicaltypes.blogspot.com

Works Consulted

[Bratko01]	Prolog Programming for Artificial Intelligence, 3rd ed. Ivan Bratko, Pearson Education Limited, Essex, England, 2001.
[DM93]	A Grammatical View of Logic Programming, Pierre Deransart and Jan Mal/uszyn'ski, MIT Press, Cambridge, Massachusetts, 1993.
[Fisher99]	prolog :- tutorial, J. R. Fisher, http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html, 1999.
[RL99]	Algorithms: A Functional Programming Approach, Fethi Rabhi and Guy Lapalme, Addison-Wesley, Essex, England, 1999

Definitions

backtrack(ing):	exploring alternate solutions by attempting new values before the point of failure.
BNF:	Bacchus Naur Form is a system to describe grammars of (programming) languages.
DCG:	Definite Clause Grammar(s)
difference list:	Difference lists are list that allow access to elements within the list directly; they avoid the need to "cdr down" (a Lisp term mean to walk the list from its first element to the desired element) the list to reach the desired elements.
Lips:	Logical Inferences Per Second
memoize:	To memoize a result is to keep that result locally active so that it is not necessary to recompute it.

Solutions to Problems

The dots problem has the following
(only) solution:

    645
  x 721
  -----
    645
  12900
+ 451500
--------
 465045

The solution to SEND + MORE =
MONEY is 9567 + 1085 = 10652.

The 20th Fibonacci number is
10946 (computed from fibonacci(fib(20, X), [fib(1,1), fib(0,1)], A, B)).

The 1450th Fibonacci number is
7.79078e+302; the 1500th Fibonacci number causes a
floating-point overflow error.

---

Last modified: Mon Aug 09 16:15:25 Eastern Daylight Time 2004
Copyright © 2003, 2004, Cotillion Group, Inc. All rights reserved.