For a small book (169 pages), The Reasoned Schemer will make you think. It is a must-read for someone interested in relational programming and artificial intelligence (AI), but I think the mental gymnastics it generates will appeal to embedded developers looking for a challenge.
The Reasoned Schemer uses a unique question-and-answer style that was used in prior book, such as The Little Schemer. The latter is an introduction to Scheme Lisp programming whereas The Reasoned Schemer deals with logic programming. The book mixes humor with logic and therefore lightens the otherwise keen concentration needed to see the relationship between the questions and answers.
Interestingly enough, you can read this book without having a background in Lisp or Scheme, although you might be more comfortable with the numerous parenthesis if you have thebackground. In fact, only the very last chapter really deals with Scheme directly. The rest of the book covers aspects of logic programming like goal seeking and unification.
I’d drop a few examples on you, but the book uses some interesting symbols with lots of super and subscripts. In fact, you can download the source code from the Kanren Sourceforge project noted below. Some differences are easy. For example, the book uses the function conde while the source uses conde.
Differences aside, the book is surprisingly easy to understand even though some of the concepts are a bit esoteric. It starts with the idea of goals and success or failure and moves quickly to the idea of unification. The latter allows an expression like:
(== (a b c 4) (1 2 3 4))
to succeed if the variables a, b, and c are “fresh” (unbound) or equal to 1, 2, and 3, respectively. If the variables are fresh, then they are now associated with the appropriate values. Note that 4 matches 4. The book actually does a much better job explaining the process, but an expression like this is often combined with a question and you deduce the overall meaning from the usually terse answer.
The book moves onto more complex functions and even implements binary arithmetic. Although this is a simple process, it reveals the methodology behind logic programming in a fashion that most programmers can comprehend.
One of the more interesting aspects of the implementation is the bi-directional nature of the defined functions, resulting from the way unification comes into play. For example, the following syntax is used for adding two numbers together:
(+o a b c)
Here a + b = c. Unlike a conventional programming language, you can provide values for any two and generate the third. Likewise, provide all three values and the expression will succeed or fail. (+0 1 1 3) fails. Read the book to find out how to take advantage of this type of feature.
Letting you know what to do with your newfound knowledge is one thing the book does not cover. I’ll just give you a few hints. Building goal-seeking algorithms is often easier using logic programming. This is one reason Lisp and Prolog have been used in expert systems and robotics.
Don’t think that these techniques can only be used in an AI lab. Just think Java. Actually, Java and Kawa. The latter is an implementation of Scheme that generates Java bytecodes directly. Kawa runs the relational language presented in the book. You can find out more on Scheme at the Schemers website and there is a free, standalone version of the DRScheme development environment available.
Relational programming is a necessary tool for some and an interesting exercise for others. Either way, you will find this to be a useful addition to your technical library.
- DRScheme
www.drscheme.org - Kanren Sourceforge Project
kanren.sourceforge.net - Kawa
www.gnu.org/software/kawa/
Schemerswww.schemers.org
