Browse Prior Art Database

Efficient Demand-driven Evaluation (I) Disclosure Number: IPCOM000149100D
Original Publication Date: 1983-Sep-19
Included in the Prior Art Database: 2007-Mar-30
Document File: 68 page(s) / 3M

Publishing Venue

Software Patent Institute

Related People

Arvind, Keshav Pingali: AUTHOR [+2]


Efihcient Demand-driven Evaluation (I Reshav Pingali

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 68

Efihcient Demand-driven Evaluation (I

Reshav Pingali


19 September 1983

 Laboratory for Computer. Science
Massachusetts Institute sf Technology


Massachuset.ts 02139


 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-

driven evduarion.

 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.

[This page contains 1 picture or other non-text object]

Page 2 of 68

[This page contains 1 picture or other non-text object]

Page 3 of 68

1 $Introduction
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~

the result

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 [6] 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...