Correctness of Monadic State: An Imperative Call-by-Need Calculus

The extension of Haskell with a built-in state monad combines mathematical elegance with operational efficiency: •Semantically, at the source language level, constructs that act on the state are viewed as functions that pass an explicit store data structure around.•Operationally, at the implementation level, constructs that act on the state are viewed as statements whose evaluation has the side-effect of updating the implicit global store in place.There are several unproven conjectures that the two views are consistent. Recently, we have noted that the consistency of the two views is far from obvious: all it takes for the implementation to become unsound is one judiciously-placed beta-step in the optimization phase of the compiler. This discovery motivates the current paper in which we formalize and show the correctness of the implementation of monadic state. For the proof, we first design a typed call-by-need language that models the intermediate language of the compiler, together with a type-preserving compilation map. Second, we show that the compilation is semantics-preserving by proving that the compilation of every source axiom yields an observational equivalence of the target language. Because of the wide semantic gap between the source and target languages, we perform this last step using a number of intermediate languages. The imperative call-by-need lambda-calculus is of independent interest for reasoning about system-level Haskell code providing services such as memo-functions, generation of new names, etc, and is the starting point for reasoning about the space usage of Haskell programs.