John Pinto

Terms and Conditions:

Giuseppe Longo wrote:This book is currently out of print and downloadable upon kind permission of the M.I.T. Press.

Book Excerpts:

The main methodological connection between programming language theory and category theory is the fact that both theories are essentially "theories of functions." A crucial point, though, is that the categorical notion of morphism generalizes the set-theoretical description of function in a very broad sense, which provides a unified understanding of various aspects of the theory of programs.

This book is mostly inspired by this specific methodological connection and its applications to the theory of programming languages. More precisely, as expressed by the subtitle, it aims at a self-contained introduction to general category theory (part I) and at a categorical understanding of the mathematical structures that constituted the theoretical background of relevant areas of language design (part II). The impact on functional programming, for example, of the mathematical tools described in part II, is well known, as it ranges from the early dialects of Lisp, to Edinburgh ML, to the current work in polymorphisms and modularity. Other applications, such as CAML, which will be described, use categorical formalization for the purposes of implementation.

Category theory may be presented in a very abstract way: as a pure game of arrows and diagrams. It is useful to reach the point where acquaintance with the formal (essentially, equational) approach is so firm that it makes sense independently of any "structural" understanding. This book, though, stresses the role of structures, and always try to give an independent meaning to abstract notions and results. Each definition and fact will be exemplified, or even derived, from applications or structures in some way indebted to computing. However, in order to stress the role of the purely equational view, the last chapters of each part (essentially chapters 7 and 11) will be largely based on a formal, computational approach. Indeed, even if mathematically very abstract, the equational arguments turn out to be particularly relevant from a computer science perspective.

Intended Audience:

The first part of this book should encourage even the reader with no specific interest in programming language theory to acquire at least some familiarity with the categorical way of looking at formal descriptions. The explicit use of deeper facts is a further step, which becomes easier with access to this information. Part II and some chapters in part I are meant to take this further step, at least in one of the possible directions, namely the mathematical semantics of data types and programs as objects and morphisms of categories.