Accession Number : ADA133879
Title : Efficient Demand-Driven Evaluation (II).
Descriptive Note : Interim research rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
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