Book contents
- Frontmatter
- Contents
- Preface to the Second Edition
- Preface to the First Edition
- Part I Judgments and Rules
- Part II Statics and Dynamics
- Part III Total Functions
- Part IV Finite Data Types
- Part V Types and Propositions
- 12 Constructive Logic
- 13 Classical Logic
- Part VI Infinite Data Types
- Part VII Variable Types
- Part VIII Partiality and Recursive Types
- Part IX Dynamic Types
- Part X Subtyping
- Part XI Dynamic Dispatch
- Part XII Control Flow
- Part XIII Symbolic Data
- Part XIV Mutable State
- Part XV Parallelism
- Part XVI Concurrency and Distribution
- Part XVII Modularity
- Part XVIII Equational Reasoning
- Part XIX Appendices
- References
- Index
12 - Constructive Logic
from Part V - Types and Propositions
Published online by Cambridge University Press: 05 March 2016
- Frontmatter
- Contents
- Preface to the Second Edition
- Preface to the First Edition
- Part I Judgments and Rules
- Part II Statics and Dynamics
- Part III Total Functions
- Part IV Finite Data Types
- Part V Types and Propositions
- 12 Constructive Logic
- 13 Classical Logic
- Part VI Infinite Data Types
- Part VII Variable Types
- Part VIII Partiality and Recursive Types
- Part IX Dynamic Types
- Part X Subtyping
- Part XI Dynamic Dispatch
- Part XII Control Flow
- Part XIII Symbolic Data
- Part XIV Mutable State
- Part XV Parallelism
- Part XVI Concurrency and Distribution
- Part XVII Modularity
- Part XVIII Equational Reasoning
- Part XIX Appendices
- References
- Index
Summary
Constructive logic codifies the principles of mathematical reasoning as it is actually practiced. In mathematics a proposition is judged true exactly when it has a proof, and is judged false exactly when it has a refutation. Because there are, and always will be, unsolved problems, we cannot expect in general that a proposition is either true or false, for in most cases, we have neither a proof nor a refutation of it. Constructive logic can be described as logic as if people matter, as distinct from classical logic, which can be described as the logic of the mind of god.
From a constructive viewpoint, a proposition is true when it has a proof.What is a proof is a social construct, an agreement among people as to what is a valid argument. The rules of logic codify a set of principles of reasoning that may be used in a valid proof. The valid forms of proof are determined by the outermost structure of the proposition whose truth is asserted. For example, a proof of a conjunction consists of a proof of each conjunct, and a proof of an implication transforms a proof of its antecedent to a proof of its consequent. When spelled out in full, the forms of proof are seen to correspond exactly to the forms of expression of a programming language. To each proposition is associated the type of its proofs; a proof is then an expression of the associated type. This association between programs and proofs induces a dynamics on proofs. In this way, proofs in constructive logic have computational content, which is to say that they are interpreted as executable programs of the associated type. Conversely, programs have mathematical content as proofs of the proposition associated to their type.
The unification of logic and programming is called the propositions as types principle. It is a central organizing principle of the theory of programming languages. Propositions are identified with types, and proofs are identified with programs. A programming technique corresponds to a method of proof; a proof technique corresponds to a method of programming. Viewing types as behavioral specifications of programs, propositions are problem statements whose proofs are solutions that implement the specification.
- Type
- Chapter
- Information
- Practical Foundations for Programming Languages , pp. 95 - 103Publisher: Cambridge University PressPrint publication year: 2016