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.