
Strictness Analysis in 4D
Kei Davis
Philip Wadler
Dept. of Computing Science
University of Glasgow
Glasgow G12 8QQ
United Kingdom
Abstract
Strictness analysis techniques can be classified along four different dimensions: firstorder vs. higherorder, flat vs. nonflat, low fidelity vs. high fidelity, and forward vs. backward. Plotting a table of the positions of known techniques within this space reveals that certain regions are densely occupied while others are empty. In particular, techniques for highfidelity forward and lowfidelity backward analysis are well known, while those for lowfidelity forward and highfidelity backward analysis are lacking. This paper fills in the gaps: the lowfidelity forward methods provide faster analyses than the highfidelity forward methods, at the cost of accuracy, while the highfidelity backward methods provide more information than the lowfidelity backward methods, at the cost of time.
1 Introduction
Strictness analysis is an important part of many compilers for lazy functional languages, and a wide variety of strictness analysis techniques have been proposed. It is not clear how all of the various techniques are related; this paper is in part an attempt to organise some of these methods, by determining their positions in a space of four properties. The second goal of the paper is to give analysis techniques for the heretofore unrepresented points in this space. The properties we consider are as follows.
Firstorder vs. higherorder. Analysis techniques may be applicable only to firstorder languages, or more generally to higherorder languages. The ability to analyse higherorder expressions is important because higherorder programming is an essential part of the functional style.
Flat vs. nonflat. A flat semantic domain (e.g. the domain of integers or the domain of booleans) may be usefully abstracted to the twopoint domain, since there are only two possible degrees of definedness: completely defined or completely undefined. This abstraction is too coarse for lazy data structures, for which it may be useful to differentiate between various degrees of definedness of the toplevel structure (e.g. the spine of a list), and independently, between degrees of definedness of its subcomponents (e.g. the elements of a list). Analyses using only flat abstract domains will be called flat, while those using deeper domains will be called nonflat.
Low fidelity vs. high fidelity. The terms low fidelity and high fidelity are used to indicate how analyses are done with respect to either the free variables of an expression, or the formal parameters of a function definition. A lowfidelity analysis is one in which a separate analysis is done with respect to each free variable or formal parameter, and the