Constructive Type theory
has been a topic of research interest to computer scientists, mathematicians, logicians and philosophers for a number of years. For computer scientists it provides a framework which brings together logic and programming languages in a most elegant and fertile way: program development and verification can proceed within a single system. Viewed in a different way, type theory
is a functional programming language with some novel features, such as the totality of all its functions, its expressive type system allowing functions whose result type depends upon the value of its input, and sophisticated modules and abstract types whose interfaces can contain logical assertions as well as signature information. A third point of view emphasizes that programs (or functions) can be extracted from proofs in the logic.
The book can be thought of as giving both a first and a second course in type theory. It begins with introductory material on logic and functional programming, and follow this by presenting the system of type theory itself, together with many examples. As well as this, this book goes further, looking at the system from a mathematical perspective, thus elucidating a number of its important properties. This book then takes a critical look at the profusion of suggestions in the literature about why and how type theory could be augmented. In doing this, this book is aiming at a moving target; it must be the case that further developments will have been made before the book reaches the press. Nonetheless, such an survey can give the reader a much more developed sense of the potential of type theory, as well as giving the background of what is to come.
The first three chapters
survey the three fields upon which type theory depends: logic, the lambda-calculus and functional programming and constructive mathematics. The surveys are short, establishing terminology, notation and a general context for the discussion; pointers to the relevant literature and in particular to more detailed introductions are provided. In the second chapter
this book discusses some issues in the lambda-calculus and functional programming which suggest analogous questions in type theory.
The fourth chapter
forms the focus of the book. This book gives the formal system for type theory, developing examples of both programs and proofs as we go along. These tend to be short, illustrating the construct just introduced - Chapter 6
contains many more examples.
The system is expressive, as witnessed by the previous chapter, but are programs given in their most natural or efficient form? Chapter 7
provides a host of proposals of how to augment the system.
examines the foundations of the system: how it compares with other systems for constructive mathematics, how models of it are formed and used and how certain of the rules, the closure rules, may be seen as being generated from the introduction rules, which state what are the canonical members of each type. The book ends with a survey of related systems, implemented or not, and some concluding remarks.