Abstract: A cost is defined for demand paging algorithms with respect to a formal stochastic model of program behavior. This cost is shown to exist under rather general assumptions, and a computational procedure is given which makes it possible to determine the optimal cost and optimal policy for moderate size programs, when the formal model is known and not time dependent. In this latter case it is shown that these computational procedures may be extended to larger programs to obtain arbitrarily close approximations to their optimal policies. In previous models either unwarranted information is assumed beyond the formal model, or the complete stochastic nature of the model is not taken into account.

Publication: Journal of the ACM Vol.: 21 No.: 1 ISSN: 0004-5411

ID: CaltechAUTHORS:20161107-155825897

]]>

Abstract: The aim of this report is to show that, within the limits of what we know how to do efficiently with computers, it is possible to design a system of types that, to a good degree, models the conceptual hierarchies that we use in our everyday discourse. A method is presented for representing sets of objects by types and for representing relations among objects by relations among types. In the definition of types we can use variables (called formal variables) that range on types, and methods are provided for binding such variables to particular types. Types are either primitive, or formal variables, or obtained from types by the application of definitional operators. Relations are established among types to express that their instances have the same physial representation, or to express, possibly with additional requirements, that the set of instances of a type is a subset of the set of instances of another. These relations are used to assure that assignments and procedure calls preserve the membership of objects to the sets that are denoted by their types. By the use of formal variables we achieve the ability to abstract, in particular contexts, from details of objects.

Vol.: 2
ID: CaltechAUTHORS:20161107-161002615

]]>