Efficient Demand-driven Evaluation (I)
Original Publication Date: 1983-Sep-19
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Arvind, Keshav Pingali: AUTHOR [+2]
Efihcient Demand-driven Evaluation (I Reshav Pingali
Efihcient Demand-driven Evaluation (I
19 September 1983
Laboratory for Computer. Science
Massachusetts Institute sf Technology
We describe a program transkmation technique for pmgrms in a general stream language L whereby a data-driven evaluation of the tl-ansfomed program performs exactly
the same computation as a demand-driven evalui$tion of the original program. The
transformational technique suggests a simple denotational characterization of demand-
Key words: Data- driven evaluaeion, dataflow, demand-driven evaluation, demand propagation, farnc~ional languages, Bay evali.lmtion, least fix-points, progrm transforanalion, streams.
This research was oupported by the Defense Advanced Research Projects Agency of the Department of Defense and w ~ s
monitored by the Office of Naval Research under Contract No. N00014-75-C-0669.
Applicahive ?angu;lges give the programmer the pcrwes to cow'struct md apply functions.
In some applicative languages,, a e peogrmmer is also given certain base funcdons like i,
*, pt'-rken-else etc. An inrepreter for such a language is capable ssu" gsercasraning hsactisn application, .md, i:' the 1angra;ege has base: Fdnctions, can produce the result of the application of a base finctioo. Appllcative languages have the Church-Wosser progefly
- ie., m inteprerel- for appIIc2ti~e language can do tee fi~nc4ion applicabons in my order it chooses, because, other ban kminadsn, the outcome of fhe ineevre~tion does
not depend on tPe sequence in v.ihich the late~reter chooses to perfom fi~nction
applicalions. I"his pleasmi property sf applicaive languages has generated considerable interest in boadl ~hej
r C~es~y a ~ d
Pualielism in a program written in rn applicative language can be exploited by simultaneously evaluating dt the xhggumerits of a function applicadon. rmis idea can be applied recursivelg, if the uguments themselves art: fi~nction applications, wi~
that any cornputat on can be done a
soon as its inputs are available. This scheme can be
lssseay labeked dara- drive^ evaluacisn. An interpreter that hglements this r ~ l e of
evaluation is cakd a h~fa-driven inte~reter. mere are many varieties of data-driven interpreters in the literature - notably, the intepreters sf Dennis  a116 Arvind el a/ 121.
It is well-known that in the presence sf raou-s!.ricr" functions, a daQ-driven intepreter may
perfom some ronnputabons which are not required to produce the output of the program.
A function flx,y) is said to be s?ric& wi6h respec$ 10 orgurnenl x if the value of the function
application is undefined whenever the value of x is undefined. E...