What is a fixpoint?

Question

Could someone please explain me, what is a fix point?

I caught the minimum explanation about fix point from the website:

After infinitely many iterations we should get to a fix point where further iterations make no difference. It means that applying one more ExprF would't change anything -- a fix point doesn't move under ExprF. It's like adding one to infinity: you get back infinity.

But could not configure it out, what does it mean.
Can please someone explain me in a very easy for a dummy like me.

Answer 1

Putting it very simply, a fixed point is a point that, when provided to a function, yields as a result that same point. The term comes from mathematics, where a fixed point (or fixpoint, or "invariant point") of a function is a point that won't change under repeated application of the function.

Say that we have function $f(x) = 1/x$. For $x = 2$ we get result $\tfrac12$. If we applied the function again, we find $f(f(2))=2$. It's back to where we started, but we're alternating between these values. However, for $x = 1$ a single application of the function yields $1$ again. This means that $f(1) = f(f(1)) = f(... f(f(1))... )$. The value $1$ is a fixed point for function $f(x) = 1/x$.

A fixed point $x$ for a function $f(x)$ is some point that satisfies the equation $x = f(x)$. There might be no fixed points for a function, one, or multiple. For example, every $x$ is a fixed point for function $f(x) = x$ (which is actually the definition itself).

In computer science, more specifically combinatory logic, a fixed point for a function $f$ is some value that won't change under application of $f$ (or more precisely, that returns an identical value for $f$). For recursion, for example, it would be useless to apply a further recursive call to the function because the returned value would be identical to the argument. Another example of where it might hold meaning is in the gradient descent algorithm, where a fixed point would be the local minimum sought through the descent. Repeated applications of the algorithm would yield the same result every time, at which point we can stop because there will be no further refinement of the result.

Answer 2

Formal definition: a fixed point of a function $g : D \rightarrow D$ is an element $d : D$ such that $(g \ d) = d$ (source: Design Concepts in Programming Languages, p. 167).

Make it simple: a fixed point is simply a solution to the equation $f(x) = x$.

Intuitively: say $D = [0, 1]$. Then, imagine the unit square and its diagonal (which is the line $y = x$. If a function $g : [0, 1] \rightarrow [0, 1]$ does have a fixed point, it means that the graph of $g$ intersects the diagonal some way.

Say, for example, $g = x^2$. We know that the solution to $g(x) = x$ on $[0, 1]$ are $x = 0$ and $x = 1$. Thus, $x$ is a fixed point for $g$.

Why is it important for PL people? Everything in $\lambda$-calculus is anonymous, so, to do recursion, we need to have a function that gives back the function we recurse on every time we do a recursive call, i.e. one that has the recursive function as a fixed point. See this page for example.

For even more on fixed points, see, e.g., Design Concepts in Programming Languages, ch. 5.