The Analysis of Programming Structure

This paper has explored three examples of good semantical analyses of programming structures. The three examples share two characteristics: the semantic models are abstract enough to be applicable in many situations, and the models lead to proofs of non-computability. Other examples of programming structures have been omitted from this short essay: foundations for object-oriented languages, descriptions of languages with local variables, and the theory of database query languages. Each of these examples have corresponding semantical theories that enjoy the two characteristics above. The richness of programming structure suggests a corollary: it is folly to look for one universal model to explain all programming structures. Of course, as a theoretical subject, semantics benefits from the reduction of many concepts to a primitive, common level. Nevertheless, reduction must often be resisted. We have seen how computability theory loses all kinds of relevant distinctions. Another example is the naive semantics of PCF based on dcpos: the model is not abstract enough