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):

Report Date:

1983-09-01

Pagination or Media Count:

56.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE