Editing Fixed-point combinator (section)

==<span class="anchor" id="Y combinator"></span>''Y'' combinator in lambda calculus==
In the classical untyped [[lambda calculus]], every function has a fixed point. A particular implementation of <math>\mathrm{fix}</math> is [[Haskell Curry]]'s paradoxical combinator ''Y'', given by<ref name="Barendregt.1985">{{cite book |author=Henk Barendregt |author-link=Henk Barendregt |title=The Lambda Calculus &ndash; Its Syntax and Semantics |location=Amsterdam |publisher=North-Holland |series=Studies in Logic and the Foundations of Mathematics |volume=103 |year=1985 |isbn=0444867481}}</ref>{{rp|131}}<ref group=note>Throughout this article, the syntax rules given in [[Lambda calculus#Notation]] are used, to save parentheses.</ref><ref group=note>According to Barendregt p.132, the name originated from Curry.</ref>

: <math>Y = \lambda f. \ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))</math>
(Here using the standard notations and conventions of lambda calculus: ''Y'' is a function that takes one argument ''f'' and returns the entire expression following the first period; the expression <math>\lambda x.f\ (x\ x)</math> denotes a function that takes one argument ''x'', thought of as a function, and returns the expression <math>f\ (x\ x) </math>, where <math>(x\ x)</math> denotes ''x'' applied to itself. Juxtaposition of expressions denotes [[function application]], is left-associative, and has higher precedence than the period.)

===Verification===
The following calculation verifies that <math>Y g</math> is indeed a fixed point of the function <math>g</math>:
:{| cellpadding="0"
| <math>Y\ g\ </math>
| <math>= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g\ \ \  </math>
| by the definition of <math>Y</math>
|-
|
| <math>= (\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x))\ </math>
| by [[β-reduction]]: replacing the formal argument ''f'' of ''Y'' with the actual argument ''g''
|-
|
| <math>= g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))\ </math>
| by β-reduction: replacing the formal argument ''x'' of the first function with the actual argument <math>(\lambda x.g\ (x\ x))</math>
|-
|
| <math>= g\ (Y\ g)</math>
| by second equality, above
|}

The lambda term <math>g\ (Y\ g)</math> may not, in general, [[Β-reduction|β-reduce]] to the term <math>Y\ g</math>. However, both terms β-reduce to the same term, as shown.

===Uses===
Applied to a function with one variable, the ''Y'' combinator usually does not terminate. More interesting results are obtained by applying the ''Y'' combinator to functions of two or more variables. The added variables may be used as a counter, or index. The resulting function behaves like a ''while'' or a ''for'' loop in an imperative language.

Used in this way, the ''Y'' combinator implements simple [[recursion (computer science)|recursion]]. The lambda calculus does not allow a function to appear as a term in its own definition as is possible in many [[programming language]]s, but a function can be passed as an argument to a higher-order function that applies it in a recursive manner.

The ''Y'' combinator may also be used in implementing [[Curry's paradox]]. The heart of Curry's paradox is that untyped lambda calculus is unsound as a deductive system, and the ''Y'' combinator demonstrates this by allowing an anonymous expression to represent zero, or even many values. This is inconsistent in mathematical logic.

===Example implementations===
An example implementation of ''Y'' in the language [[R (programming language)|R]] is presented below:<syntaxhighlight lang="r">
Y <- \(f) {
  g <- \(x) f(x(x))
  g(g)
}
</syntaxhighlight>This can then be used to implement factorial as follows:<syntaxhighlight lang="r">
fact <- \(f) \(n)
  if (n == 0) 1 else n * f(n - 1)
  
Y(fact)(5) # yields 5! = 120
</syntaxhighlight>Y is only needed when function names are absent. Substituting all the definitions into one line so that function names are not required gives:<syntaxhighlight lang="r">
(\(f) (\(x) f(x(x)))(\(x) f(x(x)))) (\(f) \(n) if (n == 0) 1 else n * f(n - 1)) (5)
</syntaxhighlight>This works because R uses [[lazy evaluation]].

Languages that use [[strict evaluation]], such as [[Python (programming language)|Python]], [[C++]], and other [[strict programming language]]s, can often express Y; however, any implementation is useless in practice since it [[infinite loop|loops indefinitely]] until terminating via a [[stack overflow]].