On modeling program behavior

This is a paper about the history of the set model for program behavior. It traces briefly the origins and bases of the idea and some of the results subsequently obtained. The physical context is a hierarchical memory system consisting of a severely limited quantity of main (directly-addressable) storage and an essentially unlimited quantity of secondary (backup) storage. In this context, the intuitive notion of working as the set of words which are (or should be) loaded in main memory at any given time in order that a program may operate efficiently is as old as programming itself. The sharply increased interest in program models since the mid-1960s is a direct consequence of the widening use of virtual memory and multiprogramming techniques, which have shifted the responsibility of memory management from programmers to machines. I am assuming here that the purpose of memory management is ensuring that an active program's information is present in main memory, and the purpose of a program model is providing a basis for determining a program's information at a given time and predicting what it will be at a future time.