Chapter 9 Assignments for Applicative Languages
Vipin Swarup, Uday S. Reddy, Evan Ireland · 1997
We propose a theoretical framework for adding assignments and dynamic data to functional languages without violating their semantic properties. Our approach differs from semi-functional languages like SCHEME and ML in that values of expressions remain static and side-effect-free. A new form of abstraction called observer is designed to encapsulate state-oriented computation from the remaining purely applicative computation. The type system ensures that observers are combined linearly, allowing an implementation in terms of a global store. The utility of this extension is in manipulating shared dynamic data embedded in data structures. Evaluation of well-typed programs is Church-Rosser. Thus, programs produce the same results whether an eager or lazy evaluation order is used (assuming termination).