Browse Theses

Here we create a framework for handling the semantics of fully typed programming languages with imperative features, higher-order ALGOL-like procedures, block structure, and implicit conversions. Our approach involves the introduction of a new family of programming languages, the coercive typed (lamda)-calculi, denoted by L in the body of the dissertation. By appropriately choosing the linguistic constants (i.e. generators) of L, we can view phrases of variants of ALGOL as syntactically sugared phrases of L.This dissertation breaks into three parts. In the first part, consisting of the first chapter, we supply basic definitions and motivate the idea that functor categories arise naturally in the explanation of block structure and stack discipline. The second part, consisting of the next three chapters, is dedicated to the general theory of the semantics of the coercive typed (lamda)-calculus; the interplay between posets, algebras, and Cartesian closed categories is particularly intense here. The remaining four chapters make up the final part, in which we apply the general theory to give both direct and continuation semantics for desugared variants of ALGOL. To do so, it is necessary to show certain functor categories are Cartesian closed and to describe a category (SIGMA) of store shapes. An interesting novelty in the presentation of continuation semantics is the view that commands form a procedural, rather than a primitive, phrase type.