Three Inadequate Models

Abstract

The connection between operational and denotational semantics is of longstanding interest in the study of programming languages. One naturally seeks positive results. For example in [FP94, Sim99] adequacy results are given for models in a variety of categories. Again, the failure of full abstraction in the standard models constructed using complete partial orders and continuous functions [Plo77, Mil77] prompted the exploration of other categories (see, e.g., [BCL85, FJM96, AM98, AC98]) with varying degrees of success. In this paper we interest ourselves in counterexamples in order to make a case that these natural avenues of research had a degree of necessity. To this end, we construct inadequate models and investigate whether one can do better than the standard model, but still stay in the category of complete partial orders. (In contrast, an inadequate standard model of PCF is given in [Sim99]—but in a specially constructed category.)