Editing Fixed-point combinator (section)

==General information==
Because fixed-point combinators can be used to implement recursion, it is possible to use them to describe specific types of recursive computations, such as those in [[fixed-point iteration]], [[iterative method]]s, [[recursive join]] in [[relational database]]s, [[data-flow analysis]], FIRST and FOLLOW sets of non-terminals in a [[context-free grammar]], [[transitive closure]], and other types of [[closure (mathematics)|closure]] operations.

A function for which ''every'' input is a fixed point is called an [[identity function]]. Formally:
: <math>\forall x (f\ x = x)</math>
In contrast to universal quantification over all <math>x</math>, a fixed-point combinator constructs ''one'' value that is a fixed point of <math>f</math>. The remarkable property of a fixed-point combinator is that it constructs a fixed point for an ''arbitrary given'' function <math>f</math>.

Other functions have the special property that, after being applied once, further applications don't have any effect. More formally:
: <math>\forall x (f\ (f\ x) = f\ x)</math>
Such functions are called [[idempotent]] (see also [[Projection (mathematics)]]). An example of such a function is the function that returns ''0'' for all even integers, and ''1'' for all odd integers.

In [[lambda calculus]],<!-- applying a generic fixed-point operator to a function known to be identity or an idempotent function is generally not interesting and yields trivial results.{{discuss}} F-->from a computational point of view, applying a fixed-point combinator to an identity function or an idempotent function typically results in non-terminating computation. For example, obtaining
: <math>(Y \ \lambda x.x) = (\lambda x.(\lambda x.x)(x\ x)) \ (\lambda x.(\lambda x.x)(x\ x))</math>
where the resulting term can only reduce to itself and represents an infinite loop.

Fixed-point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in [[simply typed lambda calculus]].

The Y combinator allows [[recursion (computer science)|recursion]] to be defined as a set of [[production (computer science)|rewrite rule]]s,<ref>{{cite book |last1=Friedman |first1=Daniel P. |author1-link=Daniel P. Friedman |last2=Felleisen |first2=Matthias |author2-link=Matthias Felleisen |year=1986 |title=The Little Lisper |publisher=[[Science Research Associates]] |chapter=Chapter 9 - Lambda The Ultimate |page=179 |quote=In the chapter we have derived a Y-combinator which allows us to write recursive functions of one argument without using define.}}</ref> without requiring native recursion support in the language.<ref>{{cite web |last1=Vanier |first1=Mike |url=https://mvanier.livejournal.com/2897.html |date=14 August 2008 |title=The Y Combinator (Slight Return) or: How to Succeed at Recursion Without Really Recursing |url-status=live |archive-url=https://web.archive.org/web/20110822202348/http://mvanier.livejournal.com/2897.html |archive-date=2011-08-22 |quote=More generally, Y gives us a way to get recursion in a programming language that supports first-class functions but that doesn't have recursion built in to it.}}</ref>

In programming languages that support [[anonymous function]]s, fixed-point combinators allow the definition and use of anonymous [[Recursion|recursive]] functions, i.e., without having to [[Name binding|bind]] such functions to [[identifier]]s. In this setting, the use of fixed-point combinators is sometimes called ''[[anonymous recursion]]''.<ref group=note>This terminology appears to be largely [[mathematical folklore|]], but it appears in:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, {{ISBN|1-59059-873-3}}, p. 462—463. Derived substantially<!--gives him credit!--> from [http://www.linkedin.com/pub/wes-dyer/2/727/a39 Wes Dyer]'s blog (see next item).
* Wes Dyer [https://docs.microsoft.com/en-us/archive/blogs/wesdyer/anonymous-recursion-in-c Anonymous Recursion in C#], February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.</ref><ref name=ifworks>The If Works [https://blog.jcoglan.com/2008/01/10/deriving-the-y-combinator/ Deriving the Y combinator], January 10, 2008</ref>