E-Book Overview
Category theory is a mathematical subject whose importance in several areas of computer science, most notably the semantics of programming languages and the design of programs using abstract data types, is widely acknowledged. This book introduces category theory at a level appropriate for computer scientists and provides practical examples in the context of programming language design.
E-Book Content
CATEGORIES TYPES AND STRUCTURES An Introduction to Category Theory for the working computer scientist
Andrea Asperti Giuseppe Longo
I
INTRODUCTION 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 is one of the reasons for the increasing role of category theory in the semantic investigation of programs if compared, say, to the set-theoretic approach. However, the influence of this mathematical discipline on computer science goes beyond the methodological issue, as the categorical approach to mathematical formalization seems to be suitable for focusing concerns in many different areas of computer science, such as software engineering and artificial intelligence, as well as automata theory and other theoretical aspects of computation. 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 selfcontained introduction to general category theory (part I) and at a categorical understanding of the mathematical structures that constituted, in the last twenty or so years, the theore