How Much Non-Strictness Do Lenient Programs Require?

Lenient languages, such as Id90, have been touted as among the best functional languages for massively parallel machines [AHN88]. Lenient evaluation combines non-strict semantics with eager evaluation [Tra9 1]. Non-strictness gives these languages more expressive power than strict semantics, while eager evaluation ensures the highest degree of parallelism. Unfortunately, non-strictness incurs a large overhead, as it requires dynamic scheduling and synchronization. As a result, many powerful program analysis techniques have been developed to statically determine when non-strictness is not required [CPJ85, Tra91, Sch94]. This paper studies a large set of lenient programs and quantifies the degree of non-strictness they require. We identify several forms of non-strictness, including functional, conditional, and data structure non-strictness. Surprisingly, most Id90 programs require neither functional nor conditional non-strictness. Many benchmark programs, however, make use of a limited form of data structure non-strictness. The paper refutes the myth that lenient programs require extensive non-strictness.