Church Numeral Article Index for
Church 		Shopping
Encoding 		Website Links For
Church 		 

Information About

Church Numeral
  CATEGORIES ABOUT CHURCH ENCODING
   
lambda calculus
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to Higher-order Function s under Church encoding; from the Church-Turing Thesis we know that any computable operator (and its operands) can be represented under Church encoding.

Many students of mathematics are familiar with Gödel Numbering members of a set; Church encoding is an equivalent operation defined on Lambda Abstraction s instead of natural numbers.


CHURCH NUMERALS


Church numerals are the representations of Natural Number s under Church encoding. The Higher-order Function that represents natural number n is a function that maps any other function f to its ''n''-fold Composition f^n = f \circ f \circ \ldots \circ f.


Definition

Church numerals 0, '''1''', '''2''', ..., are defined as follows in the Lambda Calculus :
: 0 ≡ λf.λx. x
: 1 ≡ λf.λx. f x
: 2 ≡ λf.λx. f (f x)
: 3 ≡ λf.λx. f (f (f x))
: ...
: n ≡ λf.λx. f''n'' x
: ...

That is, the natural number n is represented by the Church numeral n, which has property that for any lambda-terms F and X,

: n F X =β F''n'' X


Computation with Church numerals

In the lambda calculus, numeric functions are representable by corresponding functions on Church numerals. These functions can be implemented in most functional programming languages (subject to type constraints) by direct translation of lambda terms.

The addition function plus(m,n)=m+n uses the identity f^{(m+n)}(x)=f^m(f^n(x)).

: plus ≡ λm.λn.λf.λx. m f (n f x)

The successor function succ(n)=n+1 is β-equivalent to (plus '''1''').

: succ ≡ λn.λf.λx. f (n f x)

  • n uses the identity f^{(m---n)} = (f^m)^n.


: mult ≡ λm.λn.λf. n (m f)

The exponentiation function exp(m,n)=m^n is straightforward given our definition of church numerals.

: exp ≡ λm.λn. n m

The predecessor function pred(n) = \begin{cases} 0 & \mbox{if }n=0, \ n-1 & \mbox{otherwise}\end{cases} works by generating an n-fold composition of functions that each apply their argument g to f; the base case discards its copy of f and returns x.

: pred ≡ λn.λf.λx. n (λg.λh. h (g f)) (λu. x) (λu. u)


Translation with other representations

Most real-world languages have support for machine-native integers; the ''church'' and ''unchurch'' functions (given here in Haskell ) convert between nonnegative integers and their corresponding church numerals. Implementations of these conversions in other languages are similar.

:type Church a = (a -> a) -> a -> a

:church :: Integer -> Church a
:church 0 = -> \x -> x
:church n = -> \x -> f (church (n-1) f x)

:unchurch :: Church Integer -> Integer
:unchurch n = n (\x -> x + 1) 0


CHURCH BOOLEANS


Church Boolean s are the Church encoding of the boolean values ''true'' and ''false.'' Some programming languages use these as implementation model for boolean arithmetic; examples are Smalltalk and Pico . The boolean values
are represented as functions of two values that evaluate to one or the other of their arguments.

Formal definition in Lambda Calculus :

: true ≡ λa.λb. a
: false ≡ λa.λb. b

Functions of boolean arithmetic can be derived for Church booleans:

: and ≡ λm.λn.λa.λb. m (n a b) b
: or ≡ λm.λn.λa.λb. m a (n a b)
: not ≡ λm.λa.λb. m b a


SEE ALSO



EXTERNAL LINKS