From dynamic binding to state via modal possibility

In this paper we propose a typed, purely functional calculus for state (with second-class locations) in which types reflect the dichotomy between reading from and writing into the global store. This is in contrast to the usual formulation of state via monads, where the primitives for reading and writing introduce the same monadic type constructor. We hope to argue that making this distinction is useful, simple, and has strong logical foundations. Our type system is based on the proof-term calculus for constructive modal logic S4, which has two modal type operators: for neces-sity and 3 for possibility. We extend this calculus with the notion of names (which stand for locations) and generalize to indexed fami-lies of modal operators (indexed by sets of names). Then, the modal type CA classifies computations of type A which read from store locations listed in the set C. The dual type 3CA classifies compu-tations which first write into the locations from C and than use the changed store to obtain a value of type A. There are several benefits to this development. First, the necessita-tion fragment of the language is interesting in its own: it formulates a calculus of dynamic binding. Second, the possibility operator 3 is a monad, thus forcing the single-threading of memory writes, but not of memory reads (as these are associated with ). Finally, the different status of reads and writes gives rise to a natural way of expressing the allocation of uninitialized memory while also pro-viding guarantees that only initialized locations are dereferenced