blogahige

the little racketeer – 02

Written by

neilcj

in

,

a collection of notes from reading the little schemer but using racket instead

previously: the little racketeer – 01

chapter 02 – do it, do it again, and again, and again …

This chapter introduces define and λ/lambda, allowing us to specify a procedure with λ and give it a name with define. A procedure needs a name to be used by another procedure. The amazing thing about this chapter is that the authors immediately dive into a procedure that calls itself: lat?.

The motivating question question is: given a list l, is l a list of atoms?

In my head, I call lists that don’t contain other lists “flat” lists.

This is a good motivator for what LISPs are at their absolute core: list processing. We have a list. We have a question about the list. We’re going to check the members of the list and ask that question about each item. Then we’re going to report the answer. Simple.

We have a function that asks the main question: is x an atom? So we just have to ask that of every member of l. There are two strategies for doing this, and the little schemer starts with recursion. Diving a little deeper, I suggest that this is why they introduce define here.

To use recursion, a procedure must call itself. To call itself, it needs a name. To have a name, it needs to be defined. That is, we are introduced to define because we need it in the specification of the single procedure lat?. If we iterated through the list, the procedure wouldn’t necessarily need a name.

(define lat?
  (λ (l)
    (cond
      ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f))))

The first control flow operator we’re introduced to is cond, which is like a child of if and switch/case. Just give it a list of yes/no questions, and code to execute when one is true.

My absolute favorite part of this chapter is their definition of else.

else is a question to which the answer is always “true”

I have no idea why I never clocked this before. “Else Considered Smelly” came to my attention the same week I read this chapter, so I found this definition doubly interesting, as it negates the “smell” the author of that essay found (else is not the inverse of all of the other conditions, it is a question whose answer is always “true”).

We get some operators to combine yes/no questions in and and not, and then we get a First Commandment (Preliminary) which is to always ask null? as the first question, because the null list is a sign that you’ve reached the end of a list. This gives us a little recursive function scaffolding:

(define _
  (λ (l)
    (cond
      ((null? l) _)
      (...)
      (else _))))

next: Chapter 03 – cons the Magnificent

More posts