FAST STRICTNESS ANALYSIS BASED ON DEMAND PROPAGATION

Strictness analysis is a well-known technique used in compilers for op timization of sequential and parallel evaluation of lazy functional pr ogramming languages. Ever since Mycroft's pioneering research in stric tness analysis, there have been substantial research efforts in advanc ing the basic technique in several directions such as higher-order fun ctions, nonflat domains, etc. While almost all of these methods define strictness based on denotational semantics, in 1990 we proposed an op erational method called ee-analysis. Operational methods directly addr ess the primary aspect of the strictness analysis problem, namely nont ermination of evaluation, and can yield simplicity both in formulation and computational algorithms. Moreover, the use of operational approa ch has led us to a simple and natural treatment of polymorphism, While ee-analysis reasoned about normal-form evaluation herein we extend it s power substantially so as to deal with other degrees of evaluation t hat are intermediate between normal and head-normal form. An interesti ng aspect of our approach is our formulation of a strictness property as a constraint that relates the demand placed on the output of a func tion to the demands placed on its arguments. Strictness properties are then computed using symbolic constraint-solving techniques. An import ant advantage of constraint-driven analysis is that it captures intera rgument dependencies accurately. Moreover, the analysis performance is relatively insensitive to domain size. Based on our implementation of this method, we show that our analysis techniques are efficient, as w ell as effective.