A Modern Perspective on Type Theory: From Its Origins Until Today

ISBN-13: 9781402023347 / Angielski / Twarda / 2004 / 360 str.

Fairouz D. Kamareddine; Twan Laan; Rob Nederpelt

Opis

Towards the end of the nineteenth century, Frege gave us the abstraction principles and the general notion of functions. Self-application of functions was at the heart of Russell's paradox. This led Russell to introduce type theory in order to avoid the paradox. Since, the twentieth century has seen an amazing number of theories concerned with types and functions and many applications. Progress in computer science also meant more and more emphasis on the use of logic, types and functions to study the syntax, semantics, design and implementation of programming languages and theorem provers, and the correctness of proofs and programs. The authors of this book have themselves been leading the way by providing various extensions of type theory which have been shown to bring many advantages. This book gathers much of their influential work and is highly recommended for anyone interested in type theory. The main emphasis is on:

- Types: from Russell to Ramsey, to Church, to the modern Pure Type Systems and some of their extensions.

- Functions: from Frege, to Russell to Church, to Automath and the use of functions in mathematics, programming languages and theorem provers.

- The role of types in logic: Kripke's notion of truth, the evolution and role of the propositions as types concept and its use in logical frameworks.

- The role of types in computation: extensions of type theories which can better model proof checkers and programming languages are given.

The first part of the book is historical, yet at the same time, places historical systems (like Russell's RTT) in the modern setting. The second part deals with modern type theory as it developed since the 1940s, and with the role of propositions as types (or proofs as terms), but at the same time, places another historical system (the proof checker Automath) in the modern setting. The third part uses this bridging in the first two parts between historical and modern systems to propose new systems that bring more advantages together. This book has much to offer to mathematicians, logicians and to computer scientists in general. It will have considerable influence for many years to come.' - Henk Barendregt

Recenzje

"This book has evolved from a number of projects by the authors ... into aspects of the evolution of calculus and type theory in Logic, Mathematics and Computation. ... The crown of this collaboration is this very rich and well written book ... . This book not only gives a nice and concise overview ... but also a mathematically precise and faithful reconstruction of the different type theories ... . I expect the book will be a major work of reference ... ." H.C.M. De Swart, Journal of Logic, Language and Information, Vol. 15, 2006

Spis treści

Preface. Preliminaries. Overview of this book. Acknowledgements. Introduction. I: The Evolution of Type Theory until the 1940s. 1. Prehistory. 1.a. Paradox threats. 1.b. Paradox threats in formal systems. 2. Type theory in Pricipia Mathematica. 2.a. Principia's propositional functions. 2.b. The Ramified Theory of Types RTT. 2.c. Properties of RTT. 2.d. Legal propositional functions. Conclusions. 3. Deramification. 3.a. History of the deramification. 3.b. The Simple Theory of Types STT. 3.c. Are orders to be blamed? Conclusions. II: Propositions as Types, Pure Type Systems, AUTOMATH. 4. Propositions as Types and Pure Type Systems. 4.a. Propositions as types and proofs as terms (PAT). 4.b. Lambda calculus. 4.c. Pure type systems. 5. The pre-PAT and STT in PAT-style. 5.a. RTT in PAT-style. 5.b. STT in PAT-style. 6. A correspondence between RTT and the system Nuprl. 6.a. On the role of orders. 6.b. The Nuprl type system. 6.c. RTT in Nuprl. Conclusions. 7. Automath. 7.a. Description of AUTOMATH. 7.b. From AUT-68 towards a PTS. 7.c. lambda68. 7.d. More suitable pure type systems for AUTOMATH. Conclusions. III: Extensions of Pure Type Systems. 8. Pure type systems with definitions. 8.a. Definitions in contexts. 8.b. Definitions in the terms and the contexts. 9. The Barendregt cube with parameters. 9.a.On parameters in the Barendregt cube. 9.b. The Barendregt cube refined with parameters. 10. Pure Type Systems with parameters and definitions. 10.a. Parametric constraints and definitions. 10.b. Properties of terms. 10.c. Properties of legal terms. 10.d. Restrictive use of parameters. 10.e. Systems in the redefined Barendregt cube. 10.f. First-order predicate logic. Conclusions: yet another extension of PTSs? Practical motivation. The heart of type theory. Future work. A: Type Systems in this Book. A.a. Pure Type Systems. A.b. The Barendregt cube. A.c. The Ramified Theory of Types. A.d. The Simple Theory of Types. A.e. Church's simply typed lambda-calculus lambda-->Church. A.f. A fragment of Nuprl in PTS-style. A.g. AUTOMATH. A.h. Pure Type Systems with definitions. A.i. Pure Type Systems with parametric constants. A.j. A CD-PTS and its subsystems. Bibliography. Subject Index. Name Index. List of Figures.