|
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) =x2 - 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
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. |
where
