Church numerals (was: Joy, Lambdas, ...)

[iepos@tunes.org]

> I don't know of the Church Numerals, but they seem interesting. Perhaps you 
> could point in some directions?
> 
> bineng

The basic idea is this: a church numeral is a combinator that
takes a function "f" and yields a function that applies "f"
a certain number of times (how many times "f" is applied
depending on the church numeral).

For instance, the church numeral for 2 is a function that
takes a function "f" and yields a function that applies "f"
two times. Applying "Z2" (the church numeral for 2, as it
sometimes called) to a "father" function would yield a
"grandfather" function. Applying "Z3" to a "father"
function would yield a "great-grandfather" function.

Traditionally, church numerals are only used for natural
numbers (0, 1, 2, etc.). But, it would make some sense
to generalize them to all numbers... The church numeral
for "-1" could be thought of as a function that given "f",
yields a function that "takes away" an "f"; in other words,
the church numeral for "-1" could be thought of as a
function-inverter function.

Similarly, the church numeral for "1/2" (one half) could
be thought of as a function that given "f", yields a function
that does "half" an "f"; doing such a half an "f" twice
would be the same as doing a whole "f". For instance,
applying the church numeral for "1/2" to the "grandfather"
function would yield the "father" function. On the
other hand, applying it to the "father" function
would not really make any sense.

Dealing with church numerals other than those for natural
numbers can be a bit weird, since some functions have
multiple inverses and "halves" or none at all...

(as Fare has suggested, an inverter function could be an
interesting way to found a system that has non-determinism;
i.e., a system that can cleanly deal with expressions
with multiple meanings or none at all).

More information on church numerals could probably be found
in most texts on lambda-calculus and such... There
is a bit more information on my site (http://www.tunes.org/~iepos)
under the section "Iterators".

- "iepos" (Brent Kerby)