Primitives for resource management in a demand-driven reduction model

Graph reduction has recently become well-known as a suitable technique for implementing applicative languages. However, its use hitherto has been primarily in implementing determinate programs. This paper is concerned with extensions to a demand-driven graph reduction language for performing resource management, and entail indeterminate operations. Our focus is on primitives for programming the synchronization and scheduling of resources, as found, for example, in operating systems. We propose queueing operators and operators for controlling the order of execution of operations. We show that demand-driven graph reduction simplifies the implementation of resource management, especially in obviating explicit protocols for task creation and deletion, and for busy waiting. The language FGL (Function Graph Language) is first introduced, and the primitives are presented in this language. A number of examples are then presented to show the versatility of these primitives. The paper concludes with a brief sketch of a higher-level notation, called resource expressions, for specifying synchronization properties.