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. higher-order, flat vs. non-flat, 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 high-fidelity forward and low-fidelity backward analysis are well known, while those for low-fidelity forward and high-fidelity backward analysis are lacking. This paper fills in the gaps: the low-fidelity forward methods provide faster analyses than the high-fidelity forward methods, at the cost of accuracy, while the high-fidelity backward methods provide more information than the low-fidelity 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.

First-order vs. higher-order. Analysis techniques may be applicable only to first-order languages, or more generally to higher-order languages. The ability to analyse higherorder expressions is important because higher-order programming is an essential part of the functional style.

Flat vs. non-flat. A flat semantic domain (e.g. the domain of integers or the domain of booleans) may be usefully abstracted to the two-point 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 top-level 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 non-flat.

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 low-fidelity analysis is one in which a separate analysis is done with respect to each free variable or formal parameter, and the