|
Church encoding is a means of embedding data and operators into the lambda calculus, the most familiar form being the Church numerals, a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded data in the lambda calculus this way. Image File history File links Merge-arrow. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
‹ The template below (Expand) is being considered for deletion. ...
Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to higher-order functions under Church encoding; from the Church-Turing thesis we know that any computable operator (and its operands) can be represented under Church encoding. In mathematics and computer science, higher-order functions are functions which can take other functions as arguments, and may also return functions as results. ...
In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
Many students of mathematics are familiar with Gödel numbering members of a set; Church encoding is an equivalent operation defined on lambda abstractions instead of natural numbers. In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ...
A lambda abstraction is an abstract lambda expression. ...
Church numerals
Church numerals are the representations of natural numbers 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. In simpler terms, the "value" of the numeral is equivalent to the number of times the function encapsulates x. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
In mathematics and computer science, higher-order functions are functions which can take other functions as arguments, and may also return functions as results. ...
In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...
Definition Church numerals 0, 1, 2, ..., are defined as follows in the lambda calculus: The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
- 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. fn 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 =β Fn X The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
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  uses the identity f(m + n)(x) = fm(fn(x)).
- plus ≡
λm.λn.λf.λx. m f (n f x) The successor function  is β-equivalent to (plus 1). The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
- succ ≡
λn.λf.λx. f (n f x) The multiplication function  uses the identity f(m * n) = (fm)n. - mult ≡
λm.λn.λf. n (m f) The exponentiation function  is straightforward given our definition of church numerals. - exp ≡
λm.λn. n m The predecessor function  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. Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
type Church a = (a -> a) -> a -> a church :: Integer -> Church achurch 0 = f -> &# 0;> xchurch n = f -> &# 0;> f (church (n-1) f x) unchurch :: Church Integer -> Integerunchurch n = n (&# 0;> x + 1) 0 The same code as above, here given in F# F# (pronounced F sharp) is a functional and object oriented programming language for the Microsoft . ...
let rec church n = fun f x -> match n with| 0 -> x| n -> f (church (n-1) f x) let unchurch f = f (fun x -> x + 1) 0 In the case of church, the keyword rec is required to allow recursion in F#.
Church booleans Church booleans are the Church encoding of the boolean values true and false. Some programming languages use these as an 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. For other uses, see Small talk. ...
Pico is a programming language developed at the PROG lab at the Vrije Universiteit Brussel. ...
Formal definition in lambda calculus: The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
- true ≡
λa.λb. a - false ≡
λa.λb. b Note that this definition allows predicates (i.e. functions returning logical values) to directly act as if-clauses, e.g. if predicate is a unary predicate, - predicate x then-clause else-clause
evaluates to then-clause if predicate x evaluates to true, and to else-clause if predicate x evaluates to false.
Functions of boolean arithmetic can be derived for Church booleans:
- and ≡
λm.λn. m n m - or ≡
λm.λn. m m n - not ≡
λm.λa.λb. m b a - xor ≡
λm.λn.λa.λb. m (n b a) (n a b) Some examples: - and true false ≡
(λm.λn. m n m) (λa.λb. a) (λa.λb. b) ≡ (λa.λb. a) (λa.λb. b) (λa.λb. a) ≡ (λa.λb. b) ≡ false - or true false ≡
(λm.λn. m m n) (λa.λb. a) (λa.λb. b) ≡ (λa.λb. a) (λa.λb. a) (λa.λb. b) ≡ (λa.λb. a) ≡ true - not true ≡
(λm.λa.λb. m b a) (λa.λb. a) ≡ (λa.λb. (λa.λb. a) b a) ≡ (λa.λb. b) ≡ false
Church pairs Church pairs are the Church encoding of the pair (two-tuple) type. The pair is represented as a function that takes a function argument. When given its argument it will apply the argument to the two components of the pair. CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...
Formal definition in lambda calculus: The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
- pair ≡
λx.λy.λz.z x y - fst ≡
λp.p (λx.λy.x) - snd ≡
λp.p (λx.λy.y) An example: - fst (pair a b) ≡
λp.p (λx.λy.x) ((λx.λy.λz.z x y) a b) ≡ λp.p (λx.λy.x) (λz.z a b) ≡ (λz.z a b) (λx.λy.x) ≡ (λx.λy.x) a b ≡ a
See also The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
System F is a typed lambda calculus. ...
References
External links - Some interactive examples of Church numerals
| 
Feeds |
Contact