Daniel P. Friedman William E. Byrd Oleg Kiselyov

Drawings by Duane Bibby

To Mary, Sarah, Rachel, Shannon and Rob, and to the memory of Brian.

To Mom, Dad, Brian, Mary, and Renzhong.

(Preface ix)

((l. Playthings) 2)

((2. Teaching Old Toys New Tricks) 16)

((3. Seeing Old Friends in New Ways) 26)

((4. Members Only) 46)

((5. Double Your Fun) ((5. 60)

((6. The Fun Never Ends ...) 76)

((7. A Bit Too Much) 86)

((8. Just a Bit More) 108)

((9. Under the Hood) 130)

((10. Thin Ice) 144)

(Connecting the Wires 158)

(Welcome to the Club 162)

(Index 164))

The goal of this book is to show the beauty of relational programming. We believe that it is natural to extend functional programming to relational programming. We demonstrate this by extending Scheme with a few new constructs, thereby combining the benefits of both styles. This extension also captures the essence of Prolog, the most well-known logic programming language.

Our main assumption is that you understand the first eight chapters of The Little Schemer'. The only true requirement, however, is that you understand functions as values. That is, a function can be both an argument to and the value of a function call. Furthermore, you should know that functions remember the context in which they were created. And that's it we assume no further knowledge of mathematics or logic. Readers of the appendix Connecting the Wires, however, must also have a rudimentary knowledge of Scheme macros at the level of let, and, and cond.

In order to do relational programming, we need only two constants: #s and #u, and only three operators: , fresh, and conde. These are introduced in the first chapter and are the only operators used until chapter 6. The additional operators we introduce are variants of these three. In order to keep this extension simple, we mimicked existing Scheme syntax. Thus, #s and #u are reminiscent of the Boolean constants: #t and #f; fresh expressions resemble lambda expressions; and conde expressions are syntactically like cond expressions.

We use a few notational conventions throughout the text primarily changes in font for different classes of symbols. Lexical variables are in italics, forms are in boldface, data are in sans serif, and lists are wrapped by boldfaced parentheses `O'. A relation, a function that returns a goal as its value, ends its name with a superscript `o' (e.g., car° and nullo). We also use a superscript with our interface to Scheme, run, which is fully explained in the first chapter. We have taken certain liberties with punctuation to increase clarity, such as frequently omitting a question mark when a question ends with a special symbol. We do this to avoid confusion with function names that might end with a question mark.

In chapters 7 and 8 we define arithmetic operators as relations. The +° relation can not only add but also subtract; *° 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 (*° x y z) we can specify what we know about these numbers (their values, whether they are odd or even, etc.) and ask *° to find the unspecified values. We don't specify how to accomplish the task: rather, we describe what we want in the result.

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 partition Prolog's named relations into unnamed functions, while Venkatesh helped characterize the types in this early logic system. We thank them for their effort during this developmental stage.

There are many others we wish to thank. Mitch Wand struggled through an early draft and spent several days in Bloomington clarifying the semantics of the language, which led to the elimination of superfluous language forms. We also appreciate Kent Dybvig's and Yevgeniy Makarov's comments on the first few chapters of an early draft and Amr Sabry's Haskell implementation of the language.

We gratefully acknowledge Abdulaziz Ghuloum's insistence that we remove some abstract material from the introductory chapter. In addition, Aziz's suggestions significantly clarified the run interface. Also incredibly helpful were the detailed criticisms of Chung-chieh Shan, Erik Hilsdale, John Small, Ronald Garcia, Phill Wolf, and Jos Koot. We are especially grateful to Chung-chieh for Connecting the Wires so masterfully in the final implementation.

We thank David Mack and Kyle Blocher for teaching this material to students in our undergraduate programming languages course and for making observations that led to many improvements to this book. We also thank those students who not only learned from the material but helped us to clarify its presentation.

There are several people we wish to thank for contributions not directly related to the ideas in the book. We would be remiss if we did not acknowledge Dorai Sitaram's incredibly clever Scheme typesetting program, SLAT. We are grateful for Matthias Felleisen's typesetting macros (created for The Little Schemer), and for Oscar Waddell's implementation of a tool that selectively expands Scheme macros. Also, we thank Shriram Krishnamurthi for reminding us of a promise we made that the food would be vegetarian in the next little book. Finally, we thank Bob Prior, our editor, for his encouragement and enthusiasm for this effort.

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 appetit!

Daniel P. Friedman

William E. Byrd

Bloomington, Indiana

Oleg Kiselyov

Monterey, California

The Law of Fresh

If x is fresh, then (v x) succeeds and associates x with v.

The Law of -

(v w) is the same as (w v).

The Law of conde

To get more values from conde, pretend that the successful conde line has failed, refreshing all variables that got an association from that line.

Now go make yourself a peanut butter and jam sandwich.

This space reserved for

JAM STAINS!

This space reserved for

"Cons° the Magnificent°"

The First Commandment

To transform a function whose value is a Boolean into a function whose value is a goal, replace cond with conde and unnest each question and answer. Unnest the answer #t (or #f) by replacing it with #s (or #u).

Now go make yourself a peanut butter and marmalade sandwich.

This space reserved for

MARMALADE STAINS!

The Second Commandment

To transform a function whose value is not a Boolean into a function whose value is a goal, add an extra argument to hold its value, replace cond with conde, and unnest each question and answer.

Now go munch on some carrots.

This space reserved for

CARROT STAINS!

Now go make yourself a cashew butter and chutney sandwich.

This space reserved for

CHUTNEY STAINS!

The Law of conde

cond6 behaves like conde, except that its values are interleaved.

Have a slice of Key lime pie.

This is a good time to take a break.

This is

A BREAK

Before reading the next frame,

Treat Yourself to a Hot Fudge Sundae!

Now go make yourself a baba ghanoush pita wrap.

This space reserved for

BABA GHANOUSH STAINS!

Hold on! It's going to get subtle!

Time for a banquet; you've earned it.

THIS IS A NAPKIN!

The end, sort of. Time for vacation.

This space reserved for

PALM TREES!

The Law of condo

If the question of a condo line succeeds, pretend that the remaining cond" lines have been replaced by a single (else #u).

The Third Commandment

If prior to determining the question of a condo line a variable is fresh, it must remain fresh in the question of that line.

The Law of condo

cond behaves like cond°, except that a successful question succeeds only once.

Get ready to connect the wires.

A goal g is a function that maps a substitution s to an ordered sequence s°° of zero or more substitutions. (For clarity, we notate lambda as A, when creating such a function g.) Because the sequence of substitutions may be infinite, we represent it not as a list but a stream.

Streams contain either zero, one, or more substitutions.' We use (mzero) to represent the empty stream of substitutions. For example, #u maps every substitution to (mzero). If a is a substitution, then (unit a) represents the stream containing just a. For instance, #s maps every substitution s to just (unit s). The goal created by an invocation of the operator maps a substitution s to either (mzero) or to a stream containing a single (possibly extended) substitution, depending on whether that goal fails or succeeds. To represent a stream containing multiple substitutions, we use (choice a f ), where a is the first substitution in the stream, and where f is a function of zero arguments. Invoking the function f produces the remainder of the stream, which may or may not be empty. (For clarity, we notate lambda as AF when creating such a function f.)

When we use the variable a rather than s for substitutions, it is to emphasize that this representation of streams works for other kinds of data, as long as a datum is never #f or a pair whose cdr is a function in other words, as long as the three cases above are never represented in overlapping ways. To discriminate among the cases we define the macro case-.

The second case is redundant in this representation: (unit a) can be represented as (choice a ('F () #f)). We include unit, which avoids building and taking apart pairs and invoking functions, because many goals never return multiple substitutions. run converts a stream of substitutions s°° to a list of values using map-.

Two streams can be merged either by concatenating them using mplus (also known as streamappend) or by interleaving them using mplusi. The only difference between the definitions mplus and mplusi lies in the recursive case: mplusi swaps the two streams; mplus does not.

Given a stream s°° and a goal g, we can feed each value in s° to the goal g to get a new stream, then merge all these new streams together using either mplus or rnplus'. When using mplus, this operation is called monadic2 bind, and it is used to implement the conjunction all. When using mplus', this operation is called bind, and it is used to implement the fair conjunction all'. The operators all and all' are like and, since they are short-circuiting: the false value short-circuits and, and any failed goal short-circuits all and all'. Also, the let in the third clause of all-aux ensures that (all e), (all' c), (all e #s), and (all' c #s) are equivalent to e, even if the expression e has no value. The addition of the superfluous second clause allows all-aux expressions to expand to simpler code.

To take the disjunction of goals we define conde, and to take the fair disjunction we define cond. They combine successive question-answer lines using mplus and mplus', respectively. Two stranger kinds of disjunction are condo and cond. When a question go succeeds, both condo, and condo, skip the remaining lines. However, condo, chops off every substitution after the first produced by go, whereas condo, leaves the stream produced by go intact.

Here is a small collection of entertaining and illuminating books.

Carroll, Lewis. The Annotated Alice: The Definitive Edition. W. W. Norton & Company, New York, 1999. Introduction and notes by Martin Gardner.

Hein, Piet. Crooks. The MIT Press, 1960.

Hofstadter, Douglas R. Godel, Escher, Bach: an Eternal Golden Braid. Basic Books, Inc., 1979.

Nagel, Ernest, and James R. Newman. Godel's Proof. New York University Press, 1958.

Smullyan, Raymond. To Mock a Mockingbird. Alfred A. Knopf, Inc., 1985.

Suppes, Patrick. Introduction to Logic. Van Nostrand Co., 1957.

Italic page numbers refer to definitions.

1Friedrnan, Daniel P., and Matthias Felleisen. The Little Schemer, fourth ed. MIT Press, 1996.

'See Philip L. Wadler. How to replace failure by a list of successes: a method for exception handling, backtracking, and pattern matching in lazy functional languages. Functional Programming Languages and Computer Architecture, Lecture Notes in Computer Science 201, Springer, pages 113-128; J. Michael Spivey and Silvija Seres. Combinators for logic programming. The Fun of Programming. Palgrave; and Mitchell Wand and Dale Vaillancourt. Relating Models of Backtracking. Ninth International Conference on Functional Programming. 2004, pages 54-65.

2See Eugenio Moggi. Notions of computation and monads. Information and Computation 93(1):55-92, 1991; Philip L. Wadler. The essence of functional programming. Nineteenth Symposium on Principles of Programming Languages. 1992, pages 1-14; and Ralf Hinze. Deriving backtracking monad transformers. Fifth International Conference on Functional Programming. 2000, pages 186-197.

Table of Contents

(Preface ix)

((l. Playthings) 2)

((2. Teaching Old Toys New Tricks) 16)

((3. Seeing Old Friends in New Ways) 26)

((4. Members Only) 46)

((5. Double Your Fun) ((5. 60)

((6. The Fun Never Ends ...) 76)

((7. A Bit Too Much) 86)

((8. Just a Bit More) 108)

((9. Under the Hood) 130)

((10. Thin Ice) 144)

(Connecting the Wires 158)

(Welcome to the Club 162)

(Index 164))

Our main assumption is that you understand the first eight chapters of The Little Schemer'.

Streams contain either zero, one, or more substitutions.'

Given a stream s°° and a goal g, we can feed each value in s° to the goal g to get a new stream, the