David Keenan

Its like a version of math where you're representation of "2" is "++" so the expression 2 + 2 becomes "++" + "++".

"It is a wonderfully bizarre fact that each song of a combinatory bird is not merely the name of another bird but is actually a complete description of the internal plumbing of that other bird. That is, each song is actually a brain map of some bird. Since a song is a complete description of how some bird will respond when it hears another bird, and the only important thing about a combinatory bird is how it responds when it hears another bird, we see that songs and singers are interchangeable. So we can say that the birds sing birds to each other, or we can equally say that what we have is a bunch of songs that sing songs to each other! Combinatory birds exist at an almost mystical level. Their language has no distinction between verbs and nouns. A description of action can equally well be a name."

https://dkeenan.com/Lambda/

The bird K was defined as True, and KI as False (try not to think about the fact True(x) / False(x) evaluates to something).

The claim is that the bird M is logical OR. We can test this exhaustively. M repeats the first word twice, K omits the 2nd word, and I is just there. Leftmost bird is always the next in line for evaluation.

or(false,false): M(KI)(KI) : (KI)(KI)(KI) : I(KI)(KI) : (KI)(KI): I(KI) : (KI) = false

or(true,false): MK(KI) : KK(KI) : K = true

or(false,true): M(KI)K : (KI)(KI)K: I(KI)K : (KI)K : IK : K =…

Just a warning: at least for me, once I got started, it became addictive to try, Oulipo-like (http://en.wikipedia.org/wiki/Oulipo), to write simple programmes in these ever-more-restrictive languages. I was helped along immensely by Hindley–Seldin (http://www.cambridge.org/us/academic/subjects/computer-science/programming-languages-and-applied-logic/lambda-calculus-and-combinators-introduction-2nd-edition) and, for, as one would expect, a more friendly but still thoroughly mathematical introduction, Smullyan (http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird). I am not alone in my admiration for the latter; see, for example, http://www.angelfire.com/tx4/cus/combinator/birds.html.

EDIT to add: Speaking of 'Mockingbird' articles, you may be interested in Appendix A of http://dkeenan.com/Lambda/index.htm, whose author discusses another interpretation, attributed there to Barendregt, of Booleans and numerals. For someone who regards the Church encoding as 'intuitive', they were very surprising!

In pure functional programming, so well mentioned in some PG's articles, you have only functions - no numbers. You can make numbers from functions, though. Then, you may have a basis - a set of functions which are sufficient to represent arbitrarily complex algorithm, i.e., Turing complete set; see here - http://dkeenan.com/Lambda/ .

Such a set may consist from only one function. So, the whole program is a structure of calling that function. Writing down such a program, we obviously don't need to write the function - it comes by default; we only need to write the structure, which can be represented by ( and ) . In a different way, than what I see here, but still - one bit per parenthesis, very simple processor, lots of memory and lots of steps for simple operations - a Turing tarpit...