| A Conflict Between Call-by-Need Computation and Parallelism (1994) | |||||||||||||||
Abstract | |||||||||||||||
| . In functional language implementation, there is a folklore belief that there is a conflict between implementing call-by-need semantics and parallel evaluation. In this note we illustrate this by proving that reduction algorithms of a certain general and commonly used form which give call-byneed semantics offer very little parallelism. The analysis of lazy pattern-matching which leads to the above result also suggests an efficient sequential algorithm for the evaluation of a class functional programs satisfying certain constraints, an algorithm which respects the mathematical semantics of the program considered as a term rewrite system. 1 Introduction Huet and L'evy [Huet and L'evy, 1979, Huet and L'evy, 1991] have considered the problem of call by need computation of normal forms in orthogonal term rewrite systems. Call by need here means that no redex is ever reduced unless it must be reduced in order to compute the normal form. In general, such a redex cannot be effectiv... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||