Higher-order chaotic iteration sequences

Chaotic iteration sequences is a method for approximating fixpoints of monotonic functions proposed by Patrick and Radhia Cousot. It may be used in specialisation algorithms for Prolog programs and in abstract interpretation when only parts of a fixpoint result is needed to perform program optimisations. In the first part of this paper we reexamine the definition of chaotic iteration sequences and show how a number of other methods to compute fixpoints may be formulated in this framework. In the second part we extend the technique to higher-order functions. The method of expressing solutions to problems in a recursive style has a long history in Computer Science. Often a solution algorithm may use itself on a subproblem and an imple-mentation may be based on recursion. At times it is more natural to express the solution as a fixpoint equation in which well-definedness is only guaranteed using a fixpoint theorem. This is common in abstract interpretation, data flow analysis, “first ” and “follow ” computation, etc. In strictness analysis [11] we may construct functions over the domain 2 = {0, 1} with 0 ≤ 1. If we want to evaluate the functio