Home

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.

By Anton van Straaten at 2018-09-24 04:29 | Type Theory | other blogs | 78161 reads

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?

By James McCartney at Fri, 2018-11-09 16:57 | login or register to post comments

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.

By xkapastel at Sat, 2018-11-10 13:41 | login or register to post comments

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 can quantify over 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.

By Charles Stewart at Tue, 2018-11-13 10:40 | login or register to post comments

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."

By James McCartney at Tue, 2018-11-13 20:59 | login or register to post comments

Having trouble with the writing style

Perhaps I'm just being dense, but unfortunately I find the writing style opaque. For example, on page 3 we have:

"Then 'atom is an Atom because 'atom is an atom." (with two or more fonts used in the actual book).

I assume the goal is to let the reader infer the language / notation rules by exposure to many examples. But if so, it's not entirely clear which details are significant in that system: typeface? capitalization? Something else? And without having names for the several different things that the word "atom" represents here, my decoding effort is made more difficult by all forms of "atom" having basically the same pronunciation, which makes it harder to differentiate during my contemplation.

I'm not sure if I'm just failing some IQ requirement for this book, or if I lack some crucial background knowledge (this is my first attempt to study type systems), or if I'm approaching the book in the wrong way.

By DoofusOfDeath at Tue, 2018-12-18 12:46 | login or register to post comments

Unfortunately ...

It's not just you; the field is fairly insular.

By cpurdy at Wed, 2018-12-19 02:41 | login or register to post comments

How big of a learning curve

How big of a learning curve must be climbed by a typical computer scientist, with no background in formal type theory, in order for The Little Typer to be readable?

I'm interested in learning more about dependent types, but I can't justify hundreds of hours of background study for it.

By DoofusOfDeath at Wed, 2018-12-19 21:30 | login or register to post comments

Fairly steep learning curve

The first thing you would do to grasp this pseudo-formal notation of type systems is to learn Standard ML (or OCAML, I guess).

Then study Lambda Calculus.

This document seems helpful: Quick Introduction to Type Systems https://www.cs.princeton.edu/courses/archive/spring12/cos320/typing.pdf

This is the book I'm working through on the topic: https://smile.amazon.com/gp/product/0262162091/

By cpurdy at Fri, 2018-12-21 17:38 | login or register to post comments

Thanks very much for the

Thanks very much for the suggestion, I'll give it a shot.

I've done some work in SML / MLTON before, so I guess I'll finally bite the bullet and study up on the lambda calculus.

By DoofusOfDeath at Fri, 2018-12-21 18:48 | login or register to post comments