Efficient Demand-Driven Evaluation (II).
Abstract
In Part I of this paper, we presented a scheme whereby a compiler could propagate demands through programs in a powerful stream language L. A data-driven evaluation of the transformed program performed exactly the same computation as a demand-driven evaluation of the original program. In this paper, we explore a different transformation which trades the complexity of demand propagation for a bounded amount of extra computation on some data lines. We showed that a lazy progam can be associated with any LD program and explored the concept of safe LD programs which were LD programs that performed a bounded amount of extra computation over that performed by their corresponding lazy programs. Since the set of safe programs is not closed under composition, we defined strongly-safe programs as being that subset of safe programs which is closed under composition. A class of strongly-safe programs is the set of all LD programs that are safe and input-output equivalent to their corresponding lazy programs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1983
- Accession Number
- ADA133879
Entities
People
- Arvind
- Keshav Pingali
Organizations
- Massachusetts Institute of Technology