Fixed point combinator, Fixed point combinator - Example, Fixed point combinator - Existence of fixed point combinators, Fixed point combinator - Other fixed point combinators, combinatory logic, untyped lambda calculus, typed lambda calculus, anonymous recursion
In certain formalizations of mathematics, such as the untyped lambda calculus and combinatorial calculus, every expression can be considered a higher-order function. In these formalizations, the existence of a fixed-point combinator means that every function has at least one fixed point; a function may have more than one distinct fixed point.
In some other systems, for example the simply typed lambda calculus, a well-typed fixed-point combinator cannot be written -- in those systems any support for recursion must be explicitly ...
A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tr ...
A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tromp, is
Y = S S K (S (K (S S (S (S S K)))) K)
which corresponds to the lambda expres ...
Consider the factorial function (under Church encoding). The usual recursive mathematical equation is
fact(n) = if n=0 then 1 else n * fact(n-1)
We can express a "single step" of this recursion in lambda calculus as
F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x))),
where "f" is a place-holder argument for the factorial function to be passed to itself. The function F performs a single step in the evaluation of the recursive formula. A ...
To define the set of well typed lambda terms of a given type, we introduce typing contexts which are sequences of typing assumptions of the form x:σ where x is a variable. We introduce the judgment which means that t is a term of type σ in context Γ which is given by the following typing rules:
Examples of closed terms are:
(I),
(K), and
(S).
These are the typed lambda calculus represen ...
Programming languages can achieve some of the same algorithmic results as are obtained through higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. Unfortunately, there are significant drawbacks to this approach:
The argument code to be executed is usually not statically typed; these languages generally rely on dynamic typing to determine the well-formedness and safety of the code to be executed.
The argument is usually provided as a string, t ...
The types of the simply typed lambda calculus are constructed from base types (or type variables) and given types σ,τ we can construct . Church used only two base types o for the type of propositions and ι for the type of individuals. Frequently the calculus with only one base type, usually o, is considered.
associates to the right: we read as . To each type σ we assign a ...
