The Reasoned Schemer

Dec. 19, 2005
By Daniel P. Friedman, William E. Byrd, and Oleg Kiselyov
ISBN: 0262562146
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

    If you're interested in logic programming, you might also like these books:

    Sponsored Recommendations

    Highly Integrated 20A Digital Power Module for High Current Applications

    March 20, 2024
    Renesas latest power module delivers the highest efficiency (up to 94% peak) and fast time-to-market solution in an extremely small footprint. The RRM12120 is ideal for space...

    Empowering Innovation: Your Power Partner for Tomorrow's Challenges

    March 20, 2024
    Discover how innovation, quality, and reliability are embedded into every aspect of Renesas' power products.

    Article: Meeting the challenges of power conversion in e-bikes

    March 18, 2024
    Managing electrical noise in a compact and lightweight vehicle is a perpetual obstacle

    Power modules provide high-efficiency conversion between 400V and 800V systems for electric vehicles

    March 18, 2024
    Porsche, Hyundai and GMC all are converting 400 – 800V today in very different ways. Learn more about how power modules stack up to these discrete designs.

    Comments

    To join the conversation, and become an exclusive member of Electronic Design, create an account today!