Accession Number : ADA133879

Title :   Efficient Demand-Driven Evaluation (II).

Descriptive Note : Interim research rept.,


Personal Author(s) : Pingali,Keshav ; Arvind,

Report Date : SEP 1983

Pagination or Media Count : 56

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.

Descriptors :   *Data rate, *Data transmission systems, *Compilers, *Programming languages, Computer programs, Streams, Input, Transformations(Mathematics), Computations, Algorithms, Computer programming, Flow charting

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE