How Much Non-strictness do Lenient Programs Require?

Lenient languages, such as Id90, have been touted as among the best functionallanguages for massively parallel machines [ArvindHN88]. Lenient evaluationcombines non-strict semantics with eager evaluation [Traub91]. Non-strictnessgives these languages more expressive power than strict semantics, while eagerevaluation ensures the highest degree of parallelism. Unfortunately,non-strictness incurs a large overhead, as it requires dynamic scheduling andsynchronization. As a result, many powerful program analysis techniques havebeen developed to statically determine when non-strictness is not required[ClackP85,Traub91,Schauser94].This paper studies a large set of lenient programs and quantifies the degree ofnon-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 conditionalnon-strictness. Many benchmark programs, however, make use of a limited formof data structure non-strictness. The paper refutes the myth that lenientprograms require extensive non-strictness.