The Reasoned Schemer Second Edition Daniel P. Friedman William E. Byrd Oleg Kiselyov Jason Hemann Drawings by Duane Bibby Foreword by Guy Lewis Steele Jr. and Gerald Jay Sussman Afterword by Robert A. Kowalski The MIT Press Cambridge, Massachusetts London, England © 2018 Massachusetts Institute of Technology Library of Congress Cataloging-in-Publication Data Names: Friedman, Daniel P., author. Title: The reasoned schemer / Daniel P. Friedman, William E. Byrd, Oleg Kiselyov, and Jason Hemann ; drawings by Duane Bibby ; foreword by Guy Lewis Steele Jr. and Gerald Jay Sussman ; afterword by Robert A. Kowalski. Description: Second edition. — Cambridge, MA : The MIT Press, [2018] — Includes index. Identifiers: LCCN 2017046328 — ISBN 9780262535519 (pbk. : alk. paper) Subjects: LCSH: Scheme (Computer program language) Classification: LCC QA76.73.S34 F76 2018 — DDC 005.13/3–dc23 LC record available at https://lccn.loc.gov/2017046328 ((Contents) (Copyright) (Foreword) (Preface) (Acknowledgements) (Since the First Edition) (1. Playthings) (2. Teaching Old Toys New Tricks) (3. Seeing Old Friends in New Ways) (4. Double Your Fun) (5. Members Only) (6. The Fun Never Ends … ) (7. A Bit Too Much) (8. Just a Bit More) (9. Thin Ice) (10. Under the Hood) (Connecting the Wires) (Welcome to the Club) (Afterword) (Index)) Foreword In Plato’s great dialogue Meno, written about 2400 years ago, we are treated to a wonderful teaching demonstration. Socrates demonstrates to Meno that it is possible to teach a deep truth of plane geometry to a relatively uneducated boy (who knows simple arithmetic but only a little of geometry) by asking a carefully planned sequence of leading questions. Socrates first shows Meno that the boy certainly has some incorrect beliefs, both about geometry and about what he does or does not know: although the boy thinks he can construct a square with double the area of a given square, he doesn’t even know that his idea is wrong. Socrates leads the boy to understand that his proposed construction does not work, then remarks to Meno, “Mark now the farther development. I shall only ask him, and not teach him, and he shall share the enquiry with me: and do you watch and see if you find me telling or explaining anything to him, instead of eliciting his opinion.” By a deliberate and very detailed line of questioning, Socrates leads the boy to confirm the steps of a correct construction. Socrates concludes that the boy really knew the correct result all along—that the knowledge was innate. Nowadays we know (from the theory of NP-hard problems, for example) that it can be substantially harder to find the solution to a problem than to confirm a proposed solution. Unlike Socrates himself, we regard “Socratic dialogue” as a form of teaching, one that is actually quite difficult to do well. For over four decades, since his book The Little LISPer appeared in 1974, Dan Friedman, working with many friends and students, has used superbly constructed Socratic dialogue to teach deep truths about programming by asking carefully planned sequences of leading questions. They take the reader on a journey that is entertaining as well as educational; as usual, the examples are mostly about food. While working through this book, we each began to feel that we already knew the results innately. “I see—I knew this all along! How could it be otherwise?” Perhaps Socrates was right after all? Earlier books from Dan and company taught the essentials of recursion and functional programming. The Reasoned Schemer goes deeper, taking a gentle path to mastery of the essentials of relational programming by building on a base of functional programming. By the end of the book, we are able to use relational methods effectively; but even better, we learn how to erect an elegant relational language on the functional substrate. It was not obvious up front that this could be done in a manner so accessible and pretty—but step by step we can easily confirm the presented solution. You know, don’t you, that The Little Schemer, like The Little LISPer, was a fun read? And is it not true that you like to read about food and about programming? And is not the book in your hands exactly that sort of book, the kind you would like to read? Guy Lewis Steele Jr. and Gerald Jay Sussman Cambridge, Massachusetts August 2017 Preface The Reasoned Schemer explores the often bizarre, sometimes frustrating, and always fascinating world of relational programming. The first book in the “little” series, The Little Schemer, presents ideas from functional programming: each program corresponds to a mathematical function. A simple example of a function is square, which multiplies an integer by itself: square(4) = 16, and so forth. In contrast, The Reasoned Schemer presents ideas from relational programming, where programs correspond to relations that generalize mathematical functions. For example, the relation squareo generalizes square by relating pairs of integers: squareo(4, 16) relates 4 with 16, and so forth. We call a relation supplied with arguments, such as squareo(4, 16), a goal. A goal can succeed, fail, or have no value. The great advantage of squareo over square is its flexibility. By passing a variable representing an unknown value—rather than a concrete integer—to squareo, we can express a variety of problems involving integers and their squares. For example, the goal squareo(3, x) succeeds by associating 9 with the variable x. The goal squareo(y, 9) succeeds twice, by separately associating −3 and then 3 with y. If we have written our squareo relation properly, the goal squareo(z, 5) fails, and we conclude that there is no integer whose square is 5; otherwise, the goal has no value, and we cannot draw any conclusions about z. Using two variables lets us create a goal squareo(w, v) that succeeds an unbounded number of times, enumerating all pairs of integers such that the second integer is the square of the first. Used together, the goals squareo(x, y) and squareo(−3, x) succeed—regardless of the ordering of the goals—associating 9 with x and 81 with y. Welcome to the strange and wonderful world of relational programming! This book has three themes: how to understand, use, and create relations and goals (chapters 1–8); when to use non-relational operators that take us from relational programming to its impure variant (chapter 9); and how to implement a complete relational programming language on top of Scheme (chapter 10 and appendix A). We show how to translate Scheme functions from most of the chapters of The Little Schemer into relations. Once the power of programming with relations is understood, we then exploit this power by defining in chapters 7 and 8 familiar arithmetic operators as relations. The +o relation can not only add but also subtract; ∗o can not only multiply but also factor numbers; and logo can not only find the logarithm given a number and a base but also find the base given a logarithm and a number. Just as we can define the subtraction relation from the addition relation, we can define the exponentiation relation from the logarithm relation. In general, given (∗o x y z) we can specify what we know about these numbers (their values, whether they are odd or even, etc.) and ask ∗o to find the unspecified values. We don’t specify how to accomplish the task; rather, we describe what we want in the result. This relational thinking is yet another way of understanding computation and it can be expressed using a tiny low-level language. We use this language to introduce the fundamental notions of relational programming in chapter 1, and as the foundation of our implementation in chapter 10. Later in chapter 1 we switch to a slightly friendlier syntax—inspired by Scheme’s equal?, let, cond, and define—allowing us to more easily translate Scheme functions into relations. Here is the higher-level syntax: (≡ t t ) (fresh (x … ) g … ) (conde (g … ) … ) (defrel (name x … ) g … ) 0 1 The function ≡ is defined in chapter 10; fresh, conde, and defrel are defined in the appendix Connecting the Wires using Scheme’s syntactic extension mechanism. The only requirement for understanding relational programming is familiarity with lists and recursion. The implementation in chapter 10 requires an understanding of functions as values. That is, a function can be both an argument to and the value of a function call. And that’s it—we assume no further knowledge of mathematics or logic. We have taken certain liberties with punctuation to increase clarity. Specifically, we have omitted question marks in the left-hand side of frames that end with a special symbol or a closing right parenthesis. We have done this, for example, to avoid confusion with function names that end with a question mark, and to reduce clutter around the parentheses of lists. Food appears in examples throughout the book for two reasons. First, food is easier to visualize than abstract symbols; we hope the food imagery helps you to better understand the examples and concepts. Second, we want to provide a little distraction. We know how frustrating the subject matter can be, thus these culinary diversions are for whetting your appetite. As such, we hope that thinking about food will cause you to stop reading and have a bite. You are now ready to start. Good luck! We hope you enjoy the book. Bon appétit! Daniel P. Friedman Bloomington, Indiana William E. Byrd Salt Lake City, Utah Oleg Kiselyov Sendai, Japan Jason Hemann Bloomington, Indiana Acknowledgements We thank Guy Steele and Gerry Sussman, the creators of Scheme, for contributing the foreword, and Bob Kowalski, one of the creators of logic programming, for contributing the afterword. We are grateful for their pioneering work that laid the foundations for the ideas in this book. Mitch Wand has been an indispensable sounding board for both editions. Duane Bibby, whose artwork sets the tone for these “Little” books, has provided several new illustrations. Ron Garcia, David Christiansen, and Shriram Krishnamurthi and Malavika Jayaram kindly suggested the delicious courses for the banquet in chapter 10. Carl Eastlund and David Christiansen graciously shared their type-setting macros with us. Jon Loldrup inspired us to completely revise the first chapter. Michael Ballantyne, Nada Amin, Lisa Zhang, Nick Drozd, and Oliver Bračevac offered insightful observations. Greg Rosenblatt gave us detailed comments on every chapter in the final draft of the book. Amr Sabry and the Computer Science Department’s administrative staff at Indiana University’s School of Informatics, Computing, and Engineering have made being here a true pleasure. The teaching staff and students of Indiana University’s C311 and B521 courses are always an inspiration. C311 student Jeremy Penery discovered and fixed an error in the definition of logo from the first edition. Finally, we have received great leadership from the staff at MIT Press, specifically Christine Savage and our editor, Marie Lee. We offer our grateful appreciation and thanks to all. Will thanks Matt and Cristina Might, and the entire Might family, for their support. He also thanks the members of the U Combinator research group at the University of Utah, and gratefully acknowledges the support of DARPA under agreement number AFRL FA8750-15-2-0092. Acknowledgements from the First Edition This book would not have been possible without earlier work on implementing and using logic systems with Matthias Felleisen, Anurag Mendhekar, Jon Rossie, Michael Levin, Steve Ganz, and Venkatesh Choppella. Steve showed how to