Author: neilcj

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

Chapter 05 – *Oh My Gawd*: It’s Full of Stars

The first part of this chapter introduces us to the concept of recurring through deeper lists by iterating on the previously written procedure rember, which removed instances of a given atom from a list, but only worked on what I call “flat lists” (lists which contain only atoms). They prompt with a scaffold after two examples, about which I have a little extended discussion.

With this one, I noticed my solutions are starting to differ more from the text. In this example, the text uses a nested cond block:

(define rember*
  (lambda (a l)
    (cond
      ((null? l) '())
      ((atom? (car l)
        (cond
          ((eq? (car l) a)
           (rember* a (cdr l)))
          (else (cons (car l)
                  (rember* a (cdr l))))))
      (else (cons (rember* a (car l))
                  (rember* a (cdr l)))))))

My solution

(define myrember*
  (λ (a l)
    (cond
      ((null? l) '())
      ((list? (car l))
       (cons (myrember* a (car l)) 
             (myrember* a (cdr l))))
      ((eq? a (car l)) (myrember* a (cdr l)))
      (else (cons (car l) (myrember* a (cdr l)))))))

null? is a terminating condition, so test that first. then testing if the first element of l is itself says if it is, basically recur through that sub-list and combine the results with (cdr l), but if (car l) is not a list or null, then it is atomic (if the input follows The Law of Cons), so we can remove that if it is equal to a. Finally else leads to the natural recursion. No need for nested cond blocks.

Since the text uses atom? and I used list?, I thought that my solution might not be correct. I wrote a little test to see how myrember* and rember* deal with non-list pairs. It turns that that either procedure works for the examples in the text, and both fail if you put a non-list pair inside l because both procedures assume that (cdr l) is always a list in the recursive calls of myrember*/rember*.

📌When is a pair that is not a list useful?

Non-list pairs are used intentionally, sometimes. For example, the make-hash function takes a list of pairs, where the car of each pair is a key and the cdr is an arbitrary value.

The Racket Guide: 2.4 Pairs, Lists, and Racket Syntax

This chapter “finalizes” the First Commandment:

When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.

When recurring on a number, n, ask two questions: (zero? n) and else.

When recurring on a list of S-expressions, l, ask three questions: (null? l), (atom? (car l)), and else.

My intuition leads me to ask (list? l). Is there a good reason not to?

The Fifth Commandment is finalized as:

Always change at least one argument while recurring. When recurring on a list of atoms, lat, use (cdr lat). When recurring on a number, n, use (sub1 n). And when recurring on a list of S-expressions, l, use (car l) and (cdr l) if neither (null? l) or (atom? (car l)) are true.

It must be changed to be closer to termination. The changing argument must be tested in the termination condition:

When using cdr, test termination with null? and when using sub1, test termination with zero?.

Finally, we get a Sixth Commandment warning us against premature optimization:

Simplify only after the function is correct.

The remaining procedures in the chapter are straightforward adaptations of older procedures into versions that accept lists of S-expressions, but repetition is good for the brain.

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

Chapter 04 – Number Games (additional comments)

The last page of number games gives you this question:

Write the function one? where (one? n) is #t if n is 1 and #f (i.e., false) otherwise.

The text then provides two examples of how to write this procedure, both of which are baffling to me:

(define one?
  (λ (n)
    (cond
      ((zero? n) #f)
      (else (zero? (sub1 n))))))

(define one?
  (λ (n)
    (cond
      (else (= n 1)))))

This seems unrealistic, or maybe my mind just doesn’t work this way. While an “answer” procedure earlier was “almost right” to introduce a logical idea, I don’t see how I would ever have thought to do this in this way. They follow this up with the obvious answer:

(define one?
  (λ (n) (= n 1)))

Perhaps the reasoning is that all previous example procedures used cond, and it’s use is implied in the Commandments introduced so far. This is not quite true, as the extra procedures (atom?, add1, and sub1) needed to complete these exercises do not use cond. I am just not sure that there is much value to that exercise. If I edited this, I’d recommend prompting to write the procedure without cond.

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

chapter 04 – numbers games

As noted in the first post in this series, the little schemer uses three procedures that are not in the racket spec (or scheme spec), atom?, add1, and sub1. This is the chapter that introduces the latter two procedures, which take one argument return the argument incremented or decremented respectively, and then use the structure introduced in the previous three chapters to deal with numeric operations.

The authors update the first and fourth “commandments” to recommend using the zero? question (instead of null?) to find the termination condition when recurring through a number. They also bring in mathematical identities for the terminating values (zero for addition, one for multiplication).

They also introduce recurring over two lists or two numbers simultaneously.

The most interesting part of this chapter is the construction of recursive comparative functions for greater-than, less-than, and equal-to, by recurring through two numbers and consider which one reaches zero first. The ordering of the zero? tests matters, and can have you easily writing a greater-than-or-equal-to procedure instead of greater-than.

testing sidebar

It was while reading this chapter that I decided to learn how to do unit testing more systematically. The motivation is that I wanted to write the tests before the implementation, and separating tests from implementation let you do that without getting name errors for trying to reference a procedures before they are defined. So I split my “test” logic into a separate file, and then found RackUnit.

Racket ships with RackUnit. RackUnit tests can be run from the command line with raco test or from within emacs. So, here’s a quickstart to getting some tests running.

First, you’ll have to use the provide keyword to make the procedures you want to test visible to other modules.

(provide procedure1 procedure2 ... procedureN)

Now, make a new racket file, and import rackunit and your source module.

(require rackunit "source-file.rkt")

One basic test is check-equal? which has three arguments: two S-expressions to compare and a message. The text works us through creating a recursive replacement for the expt function. I made some tests for this procedure based on the text and added a test case for 0 to be sure that x^0 = 1:

(check-equal? (expt 10 0) 1 "expt: 10^0 == 1")

Other basic checks are check-eq? and check-eqv?, and each of these three checks has a negative check: check-not-eq?, check-not-equal? and check-not-eqv?.

You can run this in a terminal with:

> raco test test.rkt

To run your tests in emacs, you have to wrap your tests in a submodule:

(module+ test
  (tests...))

You can then run these tests with C-c C-t, which will open a Racket-REPL buffer and run the tests in your test submodule. The return will be empty if all tests pass. You can also use raco to run those tests which will open a shell buffer and run raco test on your test submodule.

further reading:

RackUnit docs

raco test docs

emacs racket-mode docs

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

previously: the little racketeer – 02

chapter 03 – cons the Magnificent

This chapter moves on from just asking questions to building lists recursively. In it, we write some procedures to operate on “flat lists” as I call them–lists of atoms. In the previous chapter, the reader is guided to a procedure that asks “is atom a a member of list l?” We recursively search through the list and as soon as we find a in the list, answer “yes!”

In this chapter, we start out with a procedure that asks the same question of each member of the list, but answers with the same list without the (first instance of the) provided atom. We build the return list with cons, and this is where “The Law of Cons” really first shines. If you always provide a list as the second argument to cons, your recursive list-building will usually work on your first attempt.

Since cdr always returns a list, you end up with a pattern:

(cons some_atom (cdr some_list))

The authors formalize this pattern with three new commandments in this chapter. The Second Commandment is simply: use cons to build lists. The Third Commandment is when building lists, describe the first “typical” element of the list, then cons it onto the “natural recursion.” For lists, the natural recursion is cdr. The Fourth Commandment is to always change one element while recurring, to change it towards termination (make it smaller), to test it with the termination condition, and that if that change is cdr, to test termination with null?.

These commandments give us a couple little mental templates for recursively building lists:

(cond
  ((null? l) '())
  (test (cons (typical_element (cdr l))))
  (else recursive_call (cdr l)))

or:

(cond
  ((null? l) '())
  ((test (recursive_call (cdr l)))
  (else (cons typical_element (cdr l))))

The procedures in this chapter do things that have frequent applications in string processing: search, remove, insert, and replace. They start out with operating on just the first instance of a given atom in a given list, and the chapter closes by rewriting the procedures to operate on every instance of the given element in the given list.

next: chapter 04 – numbers games

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