Some algorithms are clearly fixed-point based. For instance, those algorithms sorting lists or simplifying expressions.
To illustrate this topic, let A denote a sorting algorithm that works by transposing two list-elements that A finds in wrong order. Indeed, if L is an ordered list, then A does nothing on L, that is to say, A(L) = L and L is a fixed-point for A. Otherwise, A is iterated until it the list becomes a fixed point.
The advantage of this algorithm consists of working as a test for its own result, that is to say, that L is a fixed-point, means that A cannot find any non-ordered element-pair in L. Thus, A is also a test for the output fitness. In other words, A is a self-testing algorithm.
After these considerations, any programming paradigm, based on fixed-point algorithms, will be bug-free ones. This is why, I think that it is worth to create such a paradigm.
Perhaps not every algorithm can be performed in this way. Nevertheless, there are no pure paradigms. For instance, Haskell programming language is said to be pure functional with no side-effects. This is not true. In this paradigm, IO-actions like IO-references are not pure and have side-effects. However, separating both kind of functions is compulsory; hence pure and non-pure functions live in separate rooms. In any case, the language encourages to use pure functions as far as possible.
Dear Peter,
The algorithm I have mentioned is as elementary that it is known by every programmer. It is recursive. In each step the algorithm only swaps the first pair that finds in wrong order. In your example the sequence is
1 3 0 2 -> 1 0 3 2 -> 0 1 3 2 -> 0 1 2 3.
Now, I will show that the only condition to perform any algorithm in this way is the existence of a testing one.
Let P be a problem and A_0 an algorithm testing if some object X is a solution for P.
Denoting as S the solution set, we can say A_0 to be a test for the membership statement X ∈ S. Suppose that you can measure the truth-value of this relation by means of a function µ. Thus, if µ(X) = 1, then X∈S is true and X is a solution for P.
Now, suppose that A_1 is another algorithm satisfying the relation µ(X) ≤ µ(A_1(X)), for every X. The combination of A_0 and A_1 can give rise to a recursive sequence X, X_1, X_2 ... such that µ(X) ≤ µ(X_1) ≤ µ(A_2)....which tends to a fixed-point.
Of course, not every problem can fit into this pattern, but it is a known fact that there is neither a universal algorithm nor a universal pattern. Not only algorithm can be split into pure functions; however Haskell is said to be pure, because, in this case pure means as pure as it is possible. Similar criterion can be applied here.
I know this kind of algorithm not always is succesful. However, if you eliminate every heuristic procedure from human thought, humans become robots. Perhaps, introducing heuristic procedures in programming paradigms, machines become more man-like objects.
Dear Peter
In general, I agree with you; however take into account that every iteration-based algorithm can be performed in this paradigm. In fact, most of numerical algorithms are iteration-based and the result is assumed to be a solution when A(X) = X + epsilon,
that is to say, solutions are fuzzy fixed-points. The required result occurs in a finite step sequence in those discrete algorithms, like the Euclidean one to find g.c.d of two integers.
Fortunately, there are a lot of problems to be solved; otherwise computer engineers will lose their jobs.
The equilibrium point between difficulties and profits must be found. Depending on its position the idea can be accepted or rejected.
In any case, the advantages of fixed-point based algorithms are the self-testing nature. A weak point is that it can work without success. In any case, frequently, "no risk" leads to "no profit."
There are programming paradigms, like pure functional, that in spite of preferring other programming method, you will be a better programmer if you know their features and advantages. Knowledge, never harms.
Kind regards
Juan-Esteban.
Dear Peter,
The use of the function µ is only one among all possible procedures. In the case of sorting algorithms, if you consider every swap as a single step in a composite procedure A, the function µ works fine.
For instance consider your example 1302. If the whole sequence must be treated by A in each stage, then in the first application we have
A(1302) = 1023
that corresponds to three iterations of the single-step procedure.
That is to say, A compares each figure with the following until the last one is found. Accordingly the symbol A above denotes three iterations of the symbol A defined in previous messages. If µ evaluates the number of well ordered pairs, then
µ(1302) = 2 while µ(1023) = 2.
In the second iteration
A(1023) -> 0123
and µ(1023)= 2 while µ(0123) = 3.
Perhaps, what causes your disagreement is that you take into account the whole sequence 1302 to define µ, while you define the function A swapping a single pair. In other words, if you consider all figures of the sequence 1203 to calculate µ, then you must also consider a procedure A working over the whole figure sequence. You cannot use a function defined at every pair of the sequence 1302 to evaluate a procedure working over a single pair of this sequence. In any case, if you prefer a procedure A acting on a single pair, you must evaluate µ after the algorithm A has examined every pair in the considered sequence.
Dear Peter,
Please. Do not confuse an example-illustration as if it were a theory. Lattice is a good device, but when a natural ordering is not obvious, can be simulated by µ.
When I have illustrated the idea with the sorting algorithm I was thinking in a well known theorem that claims that every permutation is the product of a finite set of transpositions. Accordingly, the success is guaranteed. By no means a simple example must be considered as the corner stone of a theory, however it helps to better understanding. I think that it is more interesting, contributing with some reasons against or pro the considered paradigm than analyzing a simple illustration.
Your arguments about lattice are useful to this aim. Indeed, it is possible to build other useful tools.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Programming Languages