Game Semantics for Good General References

Abstract

We present a new fully abstract and effectively presentable denotational model for RefML, a paradigmatic higher-order programming language combining call-by-value evaluation and general references in the style of ML. Our model is built using game semantics. In contrast to the previous model by Abramsky, Honda and McCusker, it provides a faithful account of reference types, and the full abstraction result does not rely on the availability of spurious constructs of reference type (bad variables). This is the first denotational model of this kind, preceded only by the trace model recently proposed by Laird.