Demand-Driven Higher-Order Fixpoint Iteration

Abstract. Our aim is to show that techniques from higher-order strict-ness analysis may be used as a general algorithmic principle in a func-tional programming language. Certain problems may be expressed as the search for the least solution that satisfy certain given properties. This is often done using some kind of fixpoint iteration. We will present a fixpoint operation that can be used for second-order functions and extend this to higher-order functions. The technique is based on using partial function graphs to represent higher-order objects. The main problem in finding fixpoints for higher-order functions is to es-tablish a notion of neededness so as to restrict the iteration to those parts of the function that may influence the result. This is here done through a uniform extension of the domain of values with need information. The result is an iteration strategy which will terminate if base domains are finite.