Fixed point of a Function is defined as an input that is
equal to its output. If ** f(x) =x **for a particular value of x,
then that value of x is a fixed point of the function f(x). Some functions
have no fixed points, some have one and some have many fixed points. Fix(f)
denotes the set of fixed points of a function f. Example- f(x) =x^{2} - 2 has
fixed points at x=(-1,2). When the input x is not a number but a function,
the output also becomes a function at the fixed points if any and such
functions are called **Functionals**. Hence functionals are functions that
take a function for its input. **Functional is also defined as a
function from a vector space into its underlying scalar field, or a
set of functions to the real numbers. If it is a Linear function from a
linear vector space into its underlying scalar field, it is called linear
functional. **In other words, it is a function that takes a vector as
its input argument, and returns a scalar. Commonly the vector space is a
space of functions, thus the functional takes a function for its input
argument, then it is sometimes considered a function of a function.
Functionals are additive -> f(x+y) =f(x) + f(y).
Functional derivatives are used in Lagrangian mechanics. Functional
integrals were used by Feynman for path integral formulation of his
quantum mechanics. Suppose in real coordinate space, the vector x is
represented as column vector then the linear functional f(x) is
where
Using the concept of functionals and fixed
points, one can eliminate explicit recursion for a function through 2
steps--
(1) Find a functional whose fixed point is the recursion
function we select.
(2) Find the fixed point of a function without recursion.
A simple source transformation takes care of 1st method and Y
combinator takes care of the 2nd step. Y combinator is expressed through
**λ calculus** which is a programming language but contains only
anonymous functions, function applications and variable references.
Remarkably, this language is Turin -complete. The notation** λ ν
, e **stands for the function that maps input **ν
**to** **output** e. **Javascript supports anonymous
functions. ** λ ν. e = **function(ν)
{returns e;}. So if we can find a way to express Y Combinator in the
**λ **calculus, we can express it in
JavaScript too. F ->a function, Y -> Y combinator, then Y(F) = F(Y(F)), in
JavaScript function, Y(F) {returns FY(F) ;}. If we try to use it, it would
never work because the function Y immediately calls itself leading to
infinite incursion.We use **λ **calculus
to wrap the call to Y such that Y(F) = F(**λx,(Y(F))(x)).
**When we invoke the function Y, it immediately calls function F
and passes it as **λx.(Y(F))(x)) **which
is equivalent to Fixed point. This function will actually find fixed point
of a functional and we could use it to eliminate recursion. We have not
eliminated recursion but shifted it to function Y. |