Scheming

In reading the excellent book, The Little Schemer (see blog posting below) and writing the code for the exercises, I've come across something in Chapter 6 that is puzzling me. It appears that the book's code for numbered? is wrong. (Yes, I know it's not. Just stick with me while I try to figure out what I'm missing.) Here it is:

(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
((eq? (car (cdr aexp)) '+)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) 'X)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) '^)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))))))

As I have done with all of the exercises in the book, I coded up the solution (using Dr. Scheme, which is great, by the way) before looking at the answer. I was pretty disappointed to see that the book's solution was much smaller than mine. As I reasoned my way through their solution I was confused at how it could work. I was right to be confused; it doesn't work.

Let's try it from Dr. Scheme's interactive toplevel.

> (numbered? '(1 + 2))
true

Great!

> (numbered? '(1 + a))
false

OK, fine. Let's try something a bit more complicated.

> (numbered? '((1 X 2) + 3))
true

Still good. How about a bit more complicated?

> (numbered? '(1 + 2 X (3 + 4) ^ 5))
true

OK, but let's try one that should fail.

> (numbered? '(1 + 2 X (3 + 4) ^ a))
true

Uh, oh.

> (numbered? '(1 + 2 X (3 + 4) ^ a + + ))
true

That's not good.

> (numbered? '(+ 1 + 2))

Well? We're waiting! (No result was returned.)

It turns out that there is a problem in communication. I didn't read the definitions carefully enough, and I'd argue that they weren't clear. First of all, they make the assumption that the argument to the function is an arithmetic expression, so things like (numbered? '(+ 1 + 2) aren't allowed. OK, but what about (numbered? '(1 + 2 X (3 + 4) ^ a))? Well, here's the definition of an arithmetic expression from the book: "For the purpose of this chapter, an arithmetic expression is either an atom (including numbers) or two arithmetic expressions combined by +, X or ^". Now, I thought that would include something like (1 + 2 + 3), since 2 + 3 is an arithmetic expression, and 1 is an arithmetic expression. Since this book is all about recursion and defining things recursively, my mind sort of skipped over the fact that although 1 is an arithmetic expression, 1 + is not. So (for the purpose of this chapter) (1 + 2 + 3) isn't an arithmetic expression.

This is something I hadn't figured out when I started writing this blog post. It turns out that for me, completely understanding what happened required writing about it. So thanks for listening, internet people.

I'd also like to note that such a terse explanation really isn't so good in this case because "arithmetic expression" is a term loaded with meaning already. Their explanation wasn't enough to make me realize that I needed to recalibrate my thinking. Possibly what is happening here is that "arithmetic expression" expression is a common term in academic Computer Science, something of which I am not knowledgeable. But then, this book makes no assumptions about the readers previous experience.

While I'm complaining, I'll mention that I didn't really understand what this question and answer meant, either: "Question: Why do we ask (number? aexp) when we know that aexp is an atom? Answer: Because we want to know if all arithmetic expressions are numbers." Huh? I guess they mean, "Because we want to know if each arithmetic expression is a number", which makes sense but seems to be circular reasoning. This might seem like a pretty minor thing to trip oneself up on, but the rest of the book has been so precise that I was assumed there had to be more meaning. That's a testament to how good this book is.

It goes very strongly against my experience in software development to write brittle programs. numbered? is just the most egregious of those so far, really most of the code in the book doesn't handle bad input. Yes, I completely realize that this is meant to be a learning experience about recursion, lambda calculus and so forth, and not about practical stuff like error handling, and I'm glad of it. The problem is that it's hard for me to get myself completely unwrapped from my practical experience. My brain has a hard time not coming up with code that tries to deal with this.

Anyway, for what it's worth, here's my version of numbered?, which works for a more broad definition of arithmetic expressions:

(define numbered?
(lambda (aexp)
(cond
( (number? (car aexp))   (or (null? (cdr aexp)) (and (operator? (car (cdr aexp))) (numbered? (cdr aexp) ))))
( (operator? (car aexp)) (and (or (number? (car (cdr aexp))) (not (atom? (car (cdr aexp))))) (numbered? (cdr aexp))))
( (not (atom? (car aexp))) (and (or (null? (cdr aexp)) (operator? (car (cdr aexp)))) (numbered? (car aexp)) (numbered? (cdr aexp))))
( else (write "else") #f))))

Which requires this helper function:

(define operator?
(lambda (op)
(cond
((eq? op '+) #t)
((eq? op 'X) #t)
((eq? op '^) #t)
(else #f))))

And I should mention that since the book's version assumes that the input is an arithmetic expression, they simplify it to:

(define numbered-simplified?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
(else (and (numbered-simplified? (car aexp)) (numbered-simplified? (car (cdr (cdr aexp)))))))))

which is impressive.

What all books ought to be.

The Little Schemer was first published (then called "The Little LISPer") over two decades ago, it uses an dialect of a somewhat obscure programming language that's been around since 1958, and it's the best computer book I've ever read. It's the best textbook I've ever read. In fact, it's the best book I've ever read to learn something. Maybe it's just the best book. Why? Look at the first page of text (courtesy Amazon):





Where's the text? Where's the explanation of what I'm supposed to learn? Where's the material? Well, it there, but it's just questions and answers. You read a question and you try to answer it. You probably know this as the Socratic method of teaching, or it would be called that if there were a teacher in the flesh asking the questions. You would think that such a style of learning would rely upon the teacher carefully monitoring the student's understanding and tailoring the questions accordingly. But I guess not. Or that is, I guess you don't need to customize the questions, you just need to get the questions exactly right. They did.


(Even if this book weren't socratic, I'd be in my top ten of computer books just for jumping into the subject right off the bat instead of starting with fifty pages of the usual filler followed by a "gentle" introduction to the topic at hand. If I had a dollar for every book I own that has: "Chapter One: The History of Java" and "Chapter Two: Why Should I learn Java?" and "Chapter Three: Java and the World Wide Web" I could save myself the time of selling them on Amazon. Though I could make, in many cases, as much as double that.)


The really great thing about this book is that actually the material mostly isn't there, not in print. The most important part of the "read a question, try to answer" cycle is "figure out what the writers wanted you to learn from it". For the best questions, you don't figure out all the intent until several questions later. Or maybe even several chapters later, I don't know yet. I'll keep you posted.

So are there any other "socratic" books? Yes. The authors of The Little Schemer (Daniel P. Friedman and Matthias Felleisen) later wrote a similarly styled book about Java (and though I haven't read it, I know Java very well, and I'm pretty sure that what the reader learns is far inferior in that book). This book in turn collected an imitator (I mean no disrespect) directed at teaching Ruby. Only a few chapters of the Ruby book have been written, but on the plus side, they are freely available. Shouldn't there be books written in this style in other subjects? There must be, right?

In raving about socratic books, I have left something out. I implied above that the subject matter of the book is a drag on it's greatness, that the book is good in despite that it's a Lisp book. And I would be pretty impressed with such a book no matter what the topic. But in fact I am working my way through the book entirely *because* it's teaching me Lisp (in this case the Scheme dialect of Lisp), or using Lisp to teach me how to program in the Lisp style. And Lisp is good.