The Little Typer

by Daniel P. Friedman, David Thrane Christiansen, Duane Bibby (Illustrator)

Overview

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.

Product Details

ISBN-13:	9780262536431
Publisher:	MIT Press
Publication date:	09/18/2018
Series:	The MIT Press
Pages:	424
Sales rank:	758,119
Product dimensions:	7.00(w) x 9.00(h) x 0.74(d)
Age Range:	18 Years

About the Author

Daniel P. Friedman is Professor of Computer Science in the School of Informatics, Computing, and Engineering at Indiana University and is the author of many books published by the MIT Press, including The Little Schemer and The Seasoned Schemer (with Matthias Felleisen); The Little Prover (with Carl Eastlund); and The Reasoned Schemer (with William E. Byrd, Oleg Kiselyov, and Jason Hemann).

David Thrane Christiansen is a member of the technical staff at Galois, Inc., in Portland, Oregon.

Robert Harper is a Professor of Computer Science at Carnegie Mellon University.

Table of Contents

Foreword ix

Preface xi

1 The More Things Change, the More They Stay the Same 2

2 Doin' What Comes Naturally 32

Recess: A Forkful of Pie 62

3 Eliminate All Natural Numbers! 68

4 Easy as Pie 92

5 Lists, Lists, and More Lists 108

6 Precisely How Many? 128

7 It All Depends On the Motive 142

Recess: One Piece at a Time 164

8 Pick a Number, Any Number 170

9 Double Your Money, Get Twice as Much 196

10 It Also Depends On the List 218

11 All Lists Are Created Equal 244

12 Even Numbers Can Be Odd 264

13 Even Haf a Baker's Dozen 278

14 There's Safety in Numbers 294

15 Imagine That … 316

16 If It's All the Same to You 342

Appendix

A The Way Forward 356

B Rules Are Made to Be Spoken 362

Afterword 395

Index 396