|
|
Programming with Equations - A Framework for Lazy Parallel EvaluationHuet and Levy pioneered lazy sequential evaluation of equational programs based on the concepts of strong-sequentiality and needed redexes. Natural extensions of their strategy are not well-suited for parallel evaluation since they do not support independent searches for needed redexes along different paths in the input term. Furthermore, the size of compiled code can be exponential in program size. We therefore propose a different notion of sequentiality called path-sequentiality that overcomes these drawbacks and thus provides a natural framework for lazy parallel evaluation. We present a sound and complete algorithm for lazy parallel normalization of path-sequential systems. We show that our algorithm is optimal in the sense that its time complexity is bounded only by the time required to perform the needed reductions. Although this paper deals only with systems without priorities among rules, our results are applicable to systems that permit priorities (most notably, functional languages) as well through the transformation of Laville. |
|
Maintained by Sekar, sekar@cs.sunysb.edu |