Many people would regard this as being two books in one. One book is an introduction to programming, teaching you basic concepts of organizing data and the programs that operate over them, ending in the investigation of universally useful algorithms. The other book is an introduction to programming languages: a study, from one level up, of the media by which we structure these data and programs.
Obviously, these are not unrelated topics. We learn programming through one or more languages, and the programs we write then become natural subjects of study to understand languages at large. Nevertheless, these are considered sufficiently different topics that they are approached separately. This is how we approached them, too.The one noble exception to this separation is the best computer science book ever written, The Structure and Interpretation of Computer Programs.
We have come to realize that this separation is neither meaningful nor helpful. The topics are deeply intertwined and, by accepting that interleaving, the result is likely to be a much better book. This is my experiment with that format.
There are many ways to organize the study of programming and programming languages. My central theme is the concept of predictability.
Programs are typically static: they live on the moral equivalent of a
paper, unmoving and unchanging. But when we run a program, it produces
a complex, dynamic behavior that yields utility, pleasure, and
(sometimes) frustration. Everyone who writes programs ultimately
Predictability has a bad rap. Under the guise of “program reasoning”, it came to be viewed simultaneously as both noble and mind-numbingly boring. It is certainly noble, but we will try to present it a way that will hopefully seem utterly natural, indeed entirely obvious (because we believe it is). Hopefully you’ll come away from this study reasonably convinced about the central place of predictability in your own work, and as a metric for programming language design.
Unlike some other textbooks, this one does not follow a top-down narrative. Rather it has the flow of a conversation, with backtracking. We will often build up programs incrementally, just as a pair of programmers would. We will include mistakes, not because we don’t know better, but because this is the best way for you to learn. Including mistakes makes it impossible for you to read passively: you must instead engage with the material, because you can never be sure of the veracity of what you’re reading.
At the end, you’ll always get to the right answer. However, this non-linear path is more frustrating in the short term (you will often be tempted to say, “Just tell me the answer, already!”), and it makes the book a poor reference guide (you can’t open up to a random page and be sure what it says is correct). However, that feeling of frustration is the sensation of learning. We don’t know of a way around it.
At various points you will encounter this:
This is an exercise. Do try it.
This is a traditional textbook exercise. It’s something you need to do on your own. If you’re using this book as part of a course, this may very well have been assigned as homework. In contrast, you will also find exercise-like questions that look like this:
There’s an activity here! Do you see it?
When you get to one of these, stop. Read, think, and formulate
an answer before you proceed. You must do this because this is
actually an exercise, but the answer is already in the
This book uses a new programming language called Pyret. Pyret is the outgrowth of our deep experience programming in and designing functional, object-oriented, and scripting languages, as well as their type systems, program analyses, and development environments.
The language’s syntax is inspired by Python.Unlike Python, Pyret will enforce indentation rather than interpret it: that is, indentation will simply become another syntax well-formedness criterion. But that hasn’t been implemented yet. It fits the niche missing in computer science education of a simple language that sheds both the strange corner-cases (of which there are many) of Python while adding important features that Python lacks for learning programming (such as algebraic datatypes, optional annotations on variables, design decisions that better enable the construction of development environments, and strong support for testing). Beginning programmers can rest in the knowledge they are being cared for, while programmers with past acquaintance of the language menagerie, from serpents to dromedaries, should find Pyret familiar and comfortable.
This book has benefited from the attention of many.
Special thanks to the students at Brown University, who have been
drafted into acting as a crucible for every iteration of this
book. They have supported it with unusual grace, creating a welcoming
and rewarding environment for pedagogic effort. Thanks also to our
Abhabongse Janthong, Alex Kleiman, Athyuttam Eleti, Benjamin S. Shapiro, Cheng Xie, Dave Lee, Ebube Chuba, Harrison Pincket, Igor Moreno Santos, Iuliu Balibanu, Jason Bennett, Jon Sailor, Josh Paley, Kelechi Ukadike, Kendrick Cole, Marc Smith, Raymond Plante, Samuel Ainsworth, Samuel Kortchmar, frodokomodo (on github).
Dorai Sitaram, John Palmer, Kartik Singhal, Kenichi Asai, Lev Litichevskiy.
This book is completely dependent on Pyret, and thus on the many people who have created and sustained it.
We thank Matthew Butterick for his help with book styling (though the ultimate style is ours, so don’t blame him!).
Many, many years ago, Alejandro Schäffer introduced SK to the idea of nature as a fat-fingered typist. Alejandro’s fingerprints are over many parts of the first half of this book, even if he wouldn’t necessarily approve of what has come of his patient instruction.
This book is written in Scribble, the authoring tool of choice for the discerning programmer.
We thank cloudconvert for their free conversion tools.