DeepRead
Cover of Proofs and types

Proofs and types

Jean-Yves Girard · 1989

Programming and computer science › Lisp and Scheme

#3,788 most recommended

About the book

An introduction to the relationship between logical proofs and typed lambda calculus, covering second-order propositional logic and the type system known as System F. It is aimed at readers who have finished basic logic and want a more mathematical treatment of type theory and proof theory. The book presents the Curry-Howard correspondence, in which proofs and typed programs are the same objects and cut elimination corresponds to program execution. Its central technical result is a proof that well-typed terms in the second-order system terminate, obtained with the method of reducibility candidates. It positions this as an alternative to Martin-Löf's approach to type theory, with proof normalization as the source of computational content.

Written by Claude from what it knows of this book.

What Hacker News says 60% recommend · 10% critical

02.5520102015202020262010 peak · 2
This bookAverage book in Lisp and Scheme

In the commenters’ own words

  • Arguing over such definitions is futile and silly, because there's bound to be some approximation, some papering-over at some point. Let's start with the…

    pron · 2017 · in Lisp is not functional (2010)

  • A similar book to Concrete Semantics, which I love, is Formal Reasoning about Programs by the same group the OP link comes from…

    nextos · 2020 · in Untangling Mechanized Proofs

What Open Library readers say

No Open Library reader has rated it yet.

  • 1 want to read
  • 0 reading
  • 0 have read

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

The threads it came up in

Details

First published
1989
ISBN
9780521371810
Editions known
2 at Open Library
Open Library
OL16965641W

CalculusComputer programmingLambda calculusProof theorySymbolic and mathematical LogicType theory

Explore in the mosaic

Read next: its neighbours on the mosaic