Computing Square Root, Fixed Point Iteration & Lisp

A function is said to have reached a fixed point when f(y) = y.
We can use this to find the square root of a function.

• Guess a value for the square root , say y
• Find the value of Avg(y, x/y ). If it is same as y, then we are done.
• Else assign Avg(x/y, y ) to y ( the new improved value ). Go back to Step 2.

Note that when y = Avg(x/y, y) the value of y that is possible is sqrt(x).So when the fixed point for the above function is reached, the value y is the square root.

So, if we have a black box which computes the fixed point of any function, then
we can pass to this black box , the function Avg(x/y, y ) & find it's fixed point.

Thus, in terms of a functional language , if we have a function for computing the fixed point, we can pass any function ( Avg in this case ) to it to be able to get the desired value. In terms of LISP, this would imply we write a higher-order procedure which takes in another procedure as input [ function here being a first class value ] and returns the fixed point.

Note that fixed point iteration that we use here is exactly the same as that used for data flow analysis in any control flow graph [ lattice of functions ? ]

As an aside , the kinds of abstraction that LISP supports : Black Box Abstraction (Higher order procedures ), Conventional Interfaces ( Generics, OOPs ), Meta-linguistic Abstraction ( being able to write other programming languages in LISP ,eg logic programming language, register machines )

[Reference]