The Reasoned Schemer

Guess what I stumbled across at my local bookstore?

Previously mentioned on LtU, and now available... When the book was announced, Ehud said:

Authored by two of my favorites, Dan Friedman and Oleg, I have such high expectations, that however great the book is going to be, I am sure to be disappointed...

After working through the first five chapters (and sneaking a look at the implementation at the end), I'm pleased to announce that no one is likely to be disappointed... It's a real tour de force.

As expected, the focus this time is logic programming, in the form of a new set of primitives elegantly implemented around a backtracking monad in Scheme. Of course the format is familiar and comfortable, and of course it's charmingly illustrated by Duane Bibby.

So, get your copy today, and congratulations to the authors on a job well done!

And yes...

I meant to confirm that the system in the book is (once again as expected) based on KANREN. The full code for miniKANREN is linked from that page along with the rest of the code from the book.

Have fun!

By Matt Hellige at Tue, 2005-11-08 21:13 | login or register to post comments

Quick Review

It was Alan Perlis who said "You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program." Dan Friedman exemplifies this quote in the way he combines programming language research and teaching. The Little books (coauthored with Matthias Felleisen) are unique in the way they combine deep and subtle ideas with hands on humorous presentation. The Reasoned Schemer, the latest book in the series, is no exception. Coauthored by Friedman, William Byrd and Oleg Kiselyov, the book provides a unique presentation of many of the ideas behind logic programming.

Logic programming, as developed here, is a natural - though subtle - extension of functional programming. Relations and goals are used, in addition to regular functions. The book continues in the tradition of using the Scheme programming language to introduce and explain new programming constructs.

Fans of the Little books are sure to enjoy this latest member of the family. However, the book is perhaps more advanced then before and the ideas a little harder to grasp.

One of the great things about the Little books is that you can follow the text working on your own machine. Since the language used in TRS is an extension of standard Scheme, you will not be able to do so this time - unless you install the required files, which can be downloaded here.

The book follows the standard presentation style used in all the Little books and each chapter is composed of short questions and answers. Because of the subtle nature of the language constructs introduced in this book, one may find this style a bit confusing. The last chapter, aptly titled Connecting the Wires, is a masterful implementation (by Ken Shan) of the constructs presented in the book. This chapter is intended for PLT mavens and the implementation makes use of ideas from several papers we discussed over the last couple of years, which are even referenced by footnotes (how's that for a Little book?!) When you read the book be sure to search for the discussions of the papers and authors on LtU!

A nice aspect of this book is the use of naming conventions and typographical styles to make the code more readable. This might take some getting used to, and be a bit confusing if you have poor eyesight ("were the parenthesis in bold?!"), but is undoubtedly a good idea.

To the uninitiated some of the thank you notes scattered along the way might be puzzling (e.g., on page 8 (frame 30) we find this footnote: "Thank you, Thoralf Albert Skolem (1887-1963)"). Fans are likely to see these notes as an added bonus. I predict people will spend more time trying to figure some of these "in jokes" than following the code...

I was taken by surprise by chapters 7 and 8. The authors manage to escape using well known examples from the logic programming world, and concentrate on building arithmetic operations using the tools of digital design (i.e., half- and full-adders etc.) T allows them to integrate arithmetic into goal directed programming to some degree, something that is problematic when you use regular arithmetic in Prolog.

Overall this a remarkable book. It is oriented towards fans, however, and might disappoint newcomers who might find it a bit frustrating a times. Don't send it to your grandma for Christmas...

Since LtU readers should be fans, I'll end this review with a small challenge: Try to implement the Sequence Program discussed by Apt here using the system presented in the book.

Grab it while it's hot!

P.S

Frame 4 in chapter 1 refers to us, right?

By Ehud Lamm at Thu, 2005-11-17 18:20 | login or register to post comments

The challenge

No one wants to try?

By Ehud Lamm at Sat, 2005-11-19 22:26 | login or register to post comments

Challenge Solved

I solved the challenge problem, but I suspect I'm not eligible for the Grand Prize. ;-)

Frame 4 in chapter 1 refers to us, right?

Of course!

By Will Byrd at Sun, 2005-11-20 01:15 | login or register to post comments

More challange

To make it more like a real world problem, lets make the maximum number (9 in this example) and the count of each number (3 in this example) variable.

I did a simple implementation in JavaScript. Some observations:

For count=3: 9 and 10 give results, 1 to 8 and 11 don't.
For count=2: 3,4,7,8,11 and 12 give results, 5,6,9 and 10 don't.
For count=4 and 5 my js implementation cannot find solutions.

Implementations in faster languages (or faster algorithms) should give more results. It doesn't seem to be a boring matrix of results!

By Sjoerd Visscher at Sun, 2005-11-20 18:44 | login or register to post comments

that's a nice challenge

miniKanren is proving fun to program in, as it's nice to be able to mix in regular scheme code with the logic declarations.
My solution is here.

By namin at Fri, 2008-02-22 11:44 | login or register to post comments

Credit due

Actually, the implementation in Appendix A is not by me, only helped by me.

By Chung-chieh Shan at Mon, 2005-11-21 17:51 | login or register to post comments

Thanks for the clarification.

I am glad that by making this mistake I managed to get you to post again...

New comers may not know that Ken and Oleg are among the first to contribute to LtU.

By Ehud Lamm at Mon, 2005-11-21 18:30 | login or register to post comments

Best way to work through the book?

What's the best way to work through a book like this? Trying the examples out in a running scheme system as you go or reasoning through what the results would be? I've not seen the other schemer books so the style is quite different to what I'm used too!

By doublec at Fri, 2005-11-25 06:55 | login or register to post comments

It depends

I tend to read away from the computer. I usually know what's going on, and if not the answer or the following questions clarify the situation. Some things seem too good to be true, so I feel like trying them out on the computer, but mostly I use the implementation to try variations on a theme, by taking some example and playing around with it, changing it etc.

By Ehud Lamm at Fri, 2005-11-25 07:33 | login or register to post comments

My advice...

I'd strongly suggest that you try to think through each example before running it. Generally the answers are given anyway, so running the examples just verifies what's already in the book. One of the main purposes of the presentation is to help you develop a robust new intuition, largely guided by examples. If you're too quick to let the interpreter do the work, you're likely to miss out on that.

Don't blame yourself if you can't figure them all out, though. New primitives are sometimes introduced with a question, and while it might be productive to guess at their meaning, you won't be sure until you've looked at the answer. Also, some of the fun parts involve exploring the boundaries of your newly developed intuition, finding out where things aren't quite the way you expect.

By Matt Hellige at Mon, 2005-11-28 05:43 | login or register to post comments

I want my money back

I have a lot of respect for the authors, but, frankly, the "pedagogical style" of the book is not to my liking. It proceeds backwards starting from examples using unexplained primitives. It is highly repetitive and moves at an extremely slow pace. I find all questions fall into two categories: either it is impossible to know the answer based on reading the book until that point or the question is a rehash of a previous question and it is trivial. I find this a boring book. I'd much rather read a 10-15 page academic paper on the design and semantics of the underlying logic programming library or a book length extension of such a paper. The only chapter that comes even remotely close to that is "Connecting the Wires", but instead of 10-15 page article it is just a one short page of text and two pages of code.

My opinion: Waste of time. I want my money back.

Again, this is my opinion of the book. Feel free to have another opinion.

By Vesa Karvonen at Thu, 2006-06-08 13:27 | login or register to post comments

Re: Connecting the Wires

What paper is that / where might I find it? I'm curious... Thanks!

By raould at Thu, 2006-06-08 21:51 | login or register to post comments

Re: Connecting the Wires

You might enjoy From Variadic Functions to Variadic Relations: A miniKanren Perspective, a thirteen-page paper that Dan Friedman and I will be presenting in September at the 2006 Scheme Workshop. We give an annotated implementation of miniKanren, which is a variant of the language used in The Reasoned Schemer. We also present an overview of miniKanren, and show how to use Scheme's higher-order functions to create relational abstractions. The workshop proceedings will be published as a University of Chicago technical report--I'll post a link as soon as it is available.

By Will Byrd at Mon, 2006-08-21 04:28 | login or register to post comments

Re: Connecting the Wires

The proceedings of the 2006 Scheme Workshop are now online (PDF).

By Will Byrd at Sat, 2006-09-02 00:18 | login or register to post comments

Lambda the Ultimate

User login

Navigation