The Little Typer

A new introductory book about dependent types, involving some familiar names:

The Little Typer

by Daniel P. Friedman and David Thrane Christiansen.

Foreword by Robert Harper.

Afterword by Conor McBride.

An introduction to dependent types, demonstrating the most beautiful aspects, one step at a time.

A program's type describes its behavior. Dependent types are a first-class part of a language, and are much more powerful than other kinds of types; using just one language for types and programs allows program descriptions to be as powerful as the programs they describe. The Little Typer explains dependent types, beginning with a very small language that looks very much like Scheme and extending it to cover both programming with dependent types and using dependent types for mathematical reasoning. Readers should be familiar with the basics of a Lisp-like programming language, as presented in the first four chapters of The Little Schemer.

The first five chapters of The Little Typer provide the needed tools to understand dependent types; the remaining chapters use these tools to build a bridge between mathematics and programming. Readers will learn that tools they know from programming—pairs, lists, functions, and recursion—can also capture patterns of reasoning. The Little Typer does not attempt to teach either practical programming skills or a fully rigorous approach to types. Instead, it demonstrates the most beautiful aspects as simply as possible, one step at a time.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Question..

I have a question, if anyone here is reading this.
Are these statements not contradictory?

p. 53: "U, ..., is short for universe, because it describes all the types (except for itself)."

p. 55: "not every type is described by U."

Are the types not described by U only those that contain U? Or are there others?

Universe levels?

I haven't actually read it, but I imagine they've got a hierarchy of universes, since they said U does not contain itself. So you'd have U0, U1, U2... as described in this StackExchange answer.

Right

This is how universes are done in Martin-Löf type theory, which homotopy type theory is based on. It's called predicative universes.

In systems with quantification over types such as Coq, you effectively have universes that contain themselves. I think there are quite a few people who find such systems a bit "less constructive" than MLTT.

MLTT admits a straightforward interpretation in set theory, and indeed there is a constructive fragment of set theory, called CZF, that roughly corresponds to MLTT, in that there is a two-way correspondence between them. Systems with quantification over types don't admit natural set-theoretic interpretations, for reasons expounded by John Reynolds, Polymorphism is not set-theoretic.

There is some mention of

There is some mention of universe levels in a footnote, but also that they are not needed since they are using only one level. "Here, a single U is enough because U is not described by a type."