This is a summary of How to Design Programs: An Introduction to Programming and Computing, abbreviated HTDP.

The book has what I think is an interesting approach to teaching introductory CS. It is different from SICP enough, so I had to read it. (Saying “HTDP is like SICP but easier” is rather misleading for reasons you will see soon.)

Table of Contents

• SICP recap
• What do HTDP authors have to say about SICP?
• Diving into HTDP
  • Part I: Fixed-Size Data
    • The mechanics
    • The design recipe
    • Enumerations, intervals, itemizations
    • Adding structs
    • Space invader example
  • Part II: Arbitrarily Large Data
    • Structural recursion
    • Using a table to figure out recursions
    • Recursion on a natural number
    • Design by composition
    • Choosing representations wisely
    • Beyond cons
  • Part III. Abstraction
    • Functional abstraction
    • Generic types
    • How to use abstractions
  • Part IV: Intertwined Data
    • Extending part II’s design recipe
    • Simultaneous processing
  • Part V: Generative Recursion
  • Part VI: Accumulators

SICP recap

First, let’s do a quick walkthrough of the classic: Structure and Interpretation of Computer Programs, abbreviated SICP. Well… just the first two chapters really. This is to provide a reference for comparing HTDP to SICP. You can skip this section if you are already familiar with SICP. I also previously wrote a post on some cool things I learned from SICP.

The book can be accessed here.

The book was used as a textbook for an old version of MIT’s introductory programming class. Its approach is unusual by today’s standards. For one, it uses the Scheme programming language. It uses a relatively “functional” style of programming rather than the “imperative” style seen in most courses. It is also quite theoretical.

The book starts by discussing basic Scheme syntax, like defining constants, applying procedures, and using conditionals (§1.1). All functions at this point are pure¹, the book uses the substitution model, at least for the time being. This section uses approximating a square root as its main example.

We then investigate the shapes of the processes generated by similar-looking procedures (§1.2). Specifically, the book distinguishes recursion from iteration, more commonly known as tail recursion in other programming languages², using classic examples like factorial and Peano arithmetic addition. It also touches on recursion with exponential time and has a cool exercise on binary exponentiation.

Afterward, the book discusses higher-order functions as a way to abstract similar processes (§1.3). Higher-order functions are also used to make the meaning of some procedures clearer.

Concluding the first chapter, SICP introduces the idea of data abstraction (§2.1), which imposes a guideline: a user should be able to manipulate compound data objects without making any assumptions about the internal representation of the data. To this end, interfaces to abstract data types are exposed as procedures called constructors and selectors. The idea of the “abstraction barrier” is introduced. The book uses cons as its primitive for building compound data and shows how to build a rational number with it. With the abstraction, it is possible to change the internal representation of a rational number type so it simplifies the fraction when the numerator or the denominator is being extracted rather than when the fraction is created. It also has cool exercises on representing cons and natural numbers via Church encoding.

The next section (§2.2) goes into more complicated data structures like linked lists and trees. It also introduces conventional list manipulation functions like map and filter. The exercises go as far as asking the reader to solve the N Queen problem.

The rest of chapter 2 walks through complex examples like symbolic differentiation and Huffman encoding trees (§2.3). It explains how to implement a system that provides OOP and polymorphism-like features (§2.4-2.5).

The rest of the chapters deal with mutation and environmental model (§3.1-3.3), concurrency (§3.4), stream processing (§3.5), interpreter (§4.1), alternative language features like lazy evaluation and logic programming (§4.2-4.4), a model of register machines with an assembly-like language (§5.1-5.3), and compilation (§5.4-5.5). These topics, except mutations, are rather advanced by most “intro to CS” course standards. For this review, I’m not focusing on these because HTDP does not cover them. (Also, I’m just not as interested in teaching them as teaching the more basic content.)

One thing to note is that SICP sprinkles math applications and algorithms throughout, so students should be exposed to a wide range of canonical examples in computer science (e.g. binary search, trees).

What do HTDP authors have to say about SICP?

The authors of HTDP published a paper titled The Structure and Interpretation of the Computer Science Curriculum, accessible here. The paper puts forth a critique of SICP and explains, at a high level, how HTDP’s approach fixes SICP’s shortcomings.

A major problem with SICP is described pretty well there so let me just quote it.

While the course briefly explains programming as the definition of some recursive procedures, it does not discuss how programmers determine which procedures are needed or how to organize these procedures. While it explains that programs benefit from functions as first-class values, it does not show how programmers discover the need for this power. While SICP introduces the idea that programs should use abstraction layers, it never mentions how or when programmers should introduce such layers of abstraction. […]

More generally, SICP doesn’t state how to program and how to manage the design of a program. It leaves these things implicit and implies that students can discover a discipline of design and programming on their own. The course presents the various uses and roles of programming ideas with a series of examples. Some exercises then ask students to modify this code basis, requiring students to read and study code; others ask them to solve similar problems, which means they have to study the construction and to change it to the best of their abilities. In short, SICP students learn by copying and modifying code, which is barely an improvement over typical programming text books.

HTDP solves this issue by adopting a different approach.

First, its explicit goal is to teach the necessary skills for students to succeed in computer science. These include understanding problem statements and mapping them, systematically, to code. HTDP also requires good habits like testing.

[S]tudents must learn that programming requires far more than writing down code and running it on some haphazardly chosen examples afterwards.

Second, it provides a detailed “design recipe” that students can follow to design their programs rather than relying on ad-hoc insights as SICP does. The design recipe and the templates are driven by the structure of data given by the problems. Language constructs are introduced as needed to represent increasingly complex information.

“[W]hen we teach how to program, we should let data drive the syllabus.”

HTDP also addresses the issue with SICP’s dependence on mathematical and engineering examples, which can be intimidating for students as they cannot distinguish actual programming knowledge from domain knowledge, by avoiding those topics and explicitly indicating if something is domain knowledge. HTDP teaches how to write interactive programs with graphical interfaces (“world programs”), which is more exciting to students.

The paper did not mention this, but it is important to note: HTDP requires students to work with resources like DrRacket stepper (somewhat like a debugger; for expanding expressions mechanistically) and library references/documentation. The exercises practice these skills. I think this is pretty nice.

Diving into HTDP

The book’s prologue is a whirlwind tour on how one could write a program that animates a static image of a rocket, landing. The introduction uses an informal tone and concludes that despite having seen all of this, the reader should not consider themselves a programmer yet. What one really needs to learn in programming is how to design programs, not just how to hack together pieces of code to make something work.

The main chunk of the book is organized by the complexity of data in the sample problems throughout the book. Of all six parts of the book, each part refines the design recipe and the corresponding templates, introducing new control constructs whenever natural. The parts go like this:

1. Fixed-Size Data
2. Arbitrarily Large Data
3. Abstraction
4. Intertwined Data
5. Generative Recursion
6. Accumulators Between each part of the book, there is an “intermezzo” that dives into nitty-gritty details like Racket’s quoting mechanism, scoping, and exact/inexact number representations. The first of these intermezzos describes the syntax and semantics of Racket³ relatively formally. The semantics is based on substitution rather than closures and environments.

The rest of this blog post is a walkthrough of HTDP’s contents. I spend the most time describing the first two parts, specifically the design recipe and the templates, as these are the novel, pedagogical ideas presented by this book. The last four parts are skimmed over.

Part I: Fixed-Size Data

The mechanics

The first chapter describes the built-in data types: numbers, strings, images, and booleans. It shows how to define constants and apply built-in functions. Images are manipulated via the book’s library (or “teachpack”) 2htdp/image which has primitive operations like circle, line, image-width, place-image, overlay, beside, above, save-image, etc. The chapter also discusses predicates for verifying data types and properties.

The second chapter teaches function definition and application in detail, walking through a series of substitutions/reductions on simple examples. It illustrates a sample batch program that manipulates text files and a graphical, interactive program (“world program”) using the 2htdp/universe teachpack. At a high level, world programs are structured as state machines. The reader needs to supply an initial state, a state transition function, a function for rendering a state, and functions to handle events like clicks/keystrokes. The first world program looks something like this.

(define BACKGROUND (empty-scene 100 100))
(define DOT (circle 3 "solid" "red"))
 
(define (main y)
  (big-bang y
    [on-tick sub1]
    [stop-when zero?]
    [to-draw place-dot-at]
    [on-key stop]))
 
(define (place-dot-at y)
  (place-image DOT 50 y BACKGROUND))
 
(define (stop y ke)
  0)

The design recipe

We finally get into the meat in chapter 3 as it introduces the design recipe and provides plenty of drills for the reader to practice. First, chapter 3 discusses the design recipe for designing a function.

Step 1 asks the reader to identify the information given in the problem. The reader should decide how to represent the information using data and write down how to interpret the data as information. The book calls this “data definition.” An example would be something like this:

; A Temperature is a Number. 
; interpretation: represents Celsius degrees

Step 2 is writing down a signature, a statement of purpose, and a function header. The purpose statement should let people reading the program understand what the function does without having to look at the implementation. The purpose statement may refer to parameter names.

Step 3 is writing some functional examples. These could be written as comments, or as taught in the later sections, check-expect statements.

Step 4, which is the most interesting suggestion in this book, is to write a template that includes all the givens. At this point in the process of designing area-of-square, students should have code that looks like this:

; Number -> Number
; computes the area of a square with side len 
; given: 2, expect: 4
; given: 7, expect: 49
(define (area-of-square len)  (... len ...))

Note that (... len ...) in the function body tells us that the answer should be some function of len. The template seems unexciting right now, but as the book introduces more complex data, the template becomes an extremely useful pedagogical tool. We’ll see this soon.

Step 5 is to fill in the body, then finally, the last step is to test and fix the function.

This design recipe is to be applied to all functions. World programs usually require defining the “world state” data type and designing multiple functions required by big-bang, like a function to be executed on every clock cycle. The world state should be based on properties that change over time. The rest can be constants.

Please take a look at the code here. This is what a complete program should ideally look like, according to the book. The problem here is to animate a car moving to the right. There should be a stationary tree. Also, if the user clicks somewhere on the canvas, the car should teleport there. In the code, observe that:

• WorldState is carefully defined.
• All functions, including tock, render, and end? are designed and tested. The examples for functions with graphical inputs/outputs may need to be determined via experimentation in the REPL.

The book emphasizes separating the “model” from the “view.” It has exercises that explore alternative state definitions. For example, if the state is defined as “the number of clock ticks since the program starts,” it is possible to animate the car moving to the right but more substantially difficult to teleport the car on user clicks.

Enumerations, intervals, itemizations

The rest of part 1 (chapters 4-7) dive into information that cannot be represented with just the built-in data types introduced so far. It discusses a very mechanistic way of dealing with different kinds of data.

An enumeration defines a collection of data as a finite number of pieces of data, each spelled out explicitly. For example,

; A TrafficLight is one of the following Strings:
; – "red"
; – "green"
; – "yellow"
; interpretation: the three strings represent the three 
; possible states that a traffic light may assume 

Whenever one designs a function taking an enumeration as an input, they should use a conditional template that covers all exactly the cases as defined in the enumeration.

; TrafficLight -> TrafficLight
; yields the next state given current state s
(check-expect (traffic-light-next "red") "green")
(define (traffic-light-next s)
  (cond
    [(string=? "red" s) ...]
    [(string=? "green" s) ...]
    [(string=? "yellow" s) ...]))

An interval defines classes of numbers via boundaries. The data definition and the corresponding template would look something like this:

; A WorldState is a Number.
; interpretation: number of pixels between the top and the UFO
; A WorldState falls into one of three intervals: 
; – between 0 and CLOSE
; – between CLOSE and HEIGHT
; – below HEIGHT

; WorldState -> WorldState
(define (f y)
  (cond
    [(<= 0 y CLOSE) ...]
    [(<= CLOSE y HEIGHT) ...]
    [(>= y HEIGHT) ...]))

Itemization is a way of including elements from both finite and infinite classes. It describes a data type as the sum of all the subclasses. See this in the next section on the space invader game.

Adding structs

The design recipe mandates that the user thinks of and writes functional examples for all subclasses of the input (and covers the boundary cases in case of intervals). It is also possible to divide the function into multiple functions, one per subclass. The conditional statement in the top-level function would act as a dispatcher.

The book also introduces structs in Racket. Structs can be defined via the syntax (define-struct structname [field1 field2 ...]) like (define-struct posn [x y]) for example. This would automatically generate a constructor (named make-structname) and selector procedures (named structname-fieldk). It would also generate a predicate for checking if an object belongs to this struct type (named structname?). For the posn example above, we would get the functions make-posn, posn-x, posn-y and posn? with the following properties:

∀ x y,  (posn-x (make-posn x y)) = x
∀ x y,  (posn-y (make-posn x y)) = y
∀ z,    (∃ x y, z = (make-posn x y)) ↔ (posn? z) = true

The programmer should create data examples to ensure that the data definition is robust enough to represent the information needed for the problem.

; An R3 is a structure:
;   (make-r3 Number Number Number)
(define-struct r3 [x y z])
 
(define ex1 (make-r3 1 2 13))
(define ex2 (make-r3 -1 0 3))

When a function takes in a struct as input, its template should contain all selector expressions to remind us that those are the data given to us.

; R3 -> Number 
; determines the distance of p to the origin 
(define (r3-distance-to-0 p)
  (... (r3-x p) ... (r3-y p) ... (r3-z p) ...))

Space invader example

The demonstrating example in the book is creating a space invader game: A UFO spawns at a random horizontal position and descends from the top of the screen. A tank at the bottom of the screen can be moved left or right by the player. The user can press the space bar to “shoot” one bullet. A natural data definition of the game state would have two cases:

; A SIGS (short for Space Invader Game State) is one of: 
; – (make-aim UFO Tank)
; – (make-fired UFO Tank Missile)
; interpretation: represents the complete state of a  space invader game

(define-struct aim [ufo tank])
(define-struct fired [ufo tank missile])

UFO, Tank and Missile are defined further like this.

; A UFO is a Posn. 
; interpretation: (make-posn x y) is the UFO's location 
; (using the top-down, left-to-right convention)
 
; A Tank is a structure:
;   (make-tank Number Number). 
; interpretation: (make-tank x dx) specifies the position:
; (x, HEIGHT) and the tank's speed: dx pixels/tick
(define-struct tank [loc vel])
 
; A Missile is a Posn. 
; interpretation (make-posn x y) is the missile's place

This means the rendering function should have a template that looks like

(define (si-render s)
  (cond [(aim? s)
         (... (aim-tank s) .. (aim-ufo s) ...)]
        [(fired? s)
         (... (fired-tank s) ... (fired-ufo x) ... (fired-missle s) ...)]))

See the code here for the implementation. Note that si-render makes calls to tank-render, ufo-render, and missile-render helper functions, which are also developed using the design recipe as well.

At this point, it should be clear to any functional programmers that we are creating algebraic data types, though recursion is currently out of the picture. This functional approach makes it very natural for students to turn any given problem statement into suitable data definitions. It’s also quite aesthetically pleasing.

There are a few things to note. First, the book suggests that “[i]f a function deals with nested structures, develop one function per level of nesting.”

;; Do this:
; UFO -> UFO
; ...
(define (ufo-move-1 u)
  (... (ufo-loc u) ... (ufo-vel u) ...))
; Posn Vel -> Posn 
; adds v to p 
(define (posn+ p v) ...)

;; Don't do this:
; UFO -> UFO
; ...
(define (ufo-move-1 u)
  (... (posn-x (ufo-loc u)) ...
   ... (posn-y (ufo-loc u)) ...
   ... (vel-deltax (ufo-vel u)) ...
   ... (vel-deltay (ufo-vel u)) ...))

Second, sometimes a function takes multiple arguments, not all of which need to be deconstructed. In that case, treat those arguments as atomic data.

On Teaching How to Design Programs: Observations from a Newcomer discusses common issues that show up in students’ code. Two of which are “stubborn sum” and “stubborn structure,” where an itemization or a struct is deconstructed (via conditionals and selectors), but the entire object is also passed to the helper functions, requiring the object to be deconstructed over and over (see pg.6).

When developing a class, we should ensure that the design recipe is followed exactly. The templates should be checked by instructors, and ideally, the students should learn to recognize code that deviates from the template as well.

Part II: Arbitrarily Large Data

Structural recursion

The second part of the book deals with recursive data types. It introduces a list with the following data definition:

; A List-of-strings is one of: 
; – '()
; – (cons String List-of-strings)

Note that (first (cons x y)) = x and (rest (cons x y)) = y. (We could have created our pair struct instead if we wanted but it is good to use existing built-ins.)

Though the definition is recursive, the book shows that the same design recipe applies, with slight modifications. For the template, we note that there must be a conditional statement distinguishing between each case in the data definition, as usual. The body of each case should have appropriate selector expressions. For recursive cases, it is likely that the recurring structure is used as an argument to the function we are writing.

See this example. To write a function that finds the length of a list of strings, we need to distinguish between the '() case and the recursive case. For the recursive case, we note that (first alos) and (rest alos) might appear in the answer. Since (rest alos) is also a List-of-strings, we note that we will use the answer from the recursive call, (how-many (rest alos)).

; List-of-strings -> Number
; determines how many strings are on alos
(define (how-many alos)
  (cond
    [(empty? alos) ...]
    [(cons? alos)  ;or `else`
     (... (first alos) ...
      ... (how-many (rest alos)) ...)]))

If the input is a complex itemization, it might be good to write helper functions specialized to all cases.

The programmer should not attempt to expand (how-many (rest alos)) when working through an example as that would be confusing. Instead, the programmer should rely on the purpose statement to figure out the result of that expression.

Note that this style of recursion is called “structural recursion,” and not all problems can be solved with this. This is, however, the most natural and common form of recursion, and I think the book made the right decision to focus on this.

Using a table to figure out recursions

The book suggests a method for solving recursive problems. First, come up with an example input. Then, create a table where the columns are: the input, the fields of the input (via selector expressions), the expected answer for recursive sub-inputs, and the expected answer for this input. This table should contain a row with the example input and as many rows as needed for all sub-inputs.

For example, consider the list (cons "x" (cons "b" (cons "a" '()))). The table would look like this.

From this table, we can conclude that the answer in the recursive case is (+ 1 (how-many (rest alos))). ((first alos) turns out to be unnecessary here.)

Recursion on a natural number

This part of the book also defines a natural number using Peano’s construction.

; An N is one of: 
; – 0
; – (add1 N)
; interpretation: represents the counting numbers

One could think of 0 as analogous to '(), positive numbers N as analogous to cons cells, where sub1 acts as a selector analogous to rest.

This makes it possible to perform recursion on a natural number while still following the design recipe. For example, this function turns a string into a list of this string repeated n times.

; N String -> List-of-strings 
; creates a list of n copies of s
 
(check-expect (copier 0 "hello") '())
(check-expect (copier 2 "hello")
              (cons "hello" (cons "hello" '())))
 
(define (copier n s)
  (cond
    [(zero? n) '()]
    [(positive? n) (cons s (copier (sub1 n) s))]))

Design by composition

Sometimes, while designing a function, we must design an auxiliary function using the same design recipe as well. For example, when designing a sort function using structural recursion, we get a template that looks like this.

; List-of-numbers -> List-of-numbers 
; rearranges alon in descending order

(check-expect (sort> '()) '())
(check-expect (sort> (list 3 2 1)) (list 3 2 1))
(check-expect (sort> (list 1 2 3)) (list 3 2 1))
(check-expect (sort> (list 12 20 -5))
              (list 20 12 -5))

(define (sort> alon)
  (cond
    [(empty? alon) ...]
    [else (... (first alon) ...
           ... (sort> (rest alon)) ...)]))

We must assume that (sort> (rest alon)) already gives us a sorted version of (rest alon). We have to combine this with (first alon) somehow to get the final answer. This suggests that we need insert.

; Number List-of-numbers -> List-of-numbers
; inserts n into the sorted list of numbers alon
(define (insert n alon)
  ...)

This allows us to fill in the implementation of sort> like this.

(define (sort> alon)
  (cond
    [(empty? alon) '()]
    [else
     (insert (first alon) (sort> (rest alon)))]))

Of course, insert will be designed using structural recursion on alon as well.

The book also walks through another example where it is sometimes necessary to generalize the function arguments so we have enough data to work with when performing structural recursion.

Choosing representations wisely

There is some amount of creativity involved in choosing data representations. For example, suppose we want to design a function that takes in a non-empty list of temperatures. We could use the standard definition of lists and requires additionally as a precondition that the list is not empty, but it is not quite clear how the template should look like.

Here is an alternative representation where empty lists are simply not representable:

; An NEList-of-temperatures is one of: 
; – (cons CTemperature '())
; – (cons CTemperature NEList-of-temperatures)
; interpretation: non-empty lists of Celsius temperatures 

The template will look like this.

; NEList-of-temperatures -> Number
; computes the sum of the given temperatures
;; tests omitted

(define (sum ne-l)
  (cond
    [(empty? (rest ne-l)) (... (first ne-l) ...)]
    [else
     (... (first ne-l) ... (sum (rest ne-l)) ...)]))

Note how we use (empty? (rest ne-l)) to figure out whether we are in the base case or the recursive case. For each case, we write down the appropriate selector expressions. Specifically, for the base case, it only makes sense to use (first ne-l). For the recursive case, we use (first ne-l) and recurses on (rest ne-l).

Beyond cons

Of course, we should remember that it is possible to define algebraic data types with structs rather than cons as well. One example in the book involves representing Russian dolls.

; An RD (short for Russian doll) is one of: 
; – String 
; – (make-layer String RD)
(define-struct layer [color doll])

;; a data example satisfying the data definition for RD
(define ex-rd (make-layer "pink" (make-layer "black" "white")))

The template would similarly use the appropriate selectors. Specifically, for the recursive case, we have access to (layer-color an-rd) and (layer-doll an-rd). We likely apply the function recursively, so we write (depth (layer-doll an-rd)) in the template.

; RD -> Number
; how many dolls are a part of an-rd 
(define (depth an-rd)
  (cond
    [(string? an-rd) ...]
    [(layer? an-rd)
     (... (layer-color an-rd) ...
      ... (depth (layer-doll an-rd)) ...)]))

The rest of part 2 is just variations on these ideas, e.g. itemizations with lists, lists with structs, and recursive structs with lists.

Part III. Abstraction

Functional abstraction

Having covered both fixed-size data and arbitrarily large data, the book takes a detour and discusses functional abstraction. This is obviously different from SICP, which starts with functional abstraction followed by data abstraction later.

First, part III shows how one might see similarities in the implementations of two functions and extract them by abstracting the similarities. This results in functions that take in other functions as arguments. A canonical example is sort, which takes in a comparison function.

Generic types

We also discuss how the function signature, i.e. the type of the function, can be abstracted. For example, we can define parameterized list types as follows:

; A [List-of ITEM] is one of: 
; – '() 
; – (cons ITEM [List-of ITEM])

How to use abstractions

The book then changes its focus from creating abstractions to using abstractions. It discusses conventional, higher-order functions like map, filter, sort, andmap, ormap, and introduces the local special form which allows creating a local scope. This is used to create functions/predicates that are fed into those well-known abstractions. The lambda form is also introduced a bit after this.

As with previous chapters, HTDP provides a design recipe for using abstractions. We follow the same design recipe, but the details are slightly different. The first three steps involve defining the data, writing the purpose statement for the function, and creating examples. For this example, we try to create an image consisting of the given dots. The first three steps yield this:

; [List-of Posn] -> Image 
; adds the Posns on lop (short for list of positions) to the empty scene 
 
(check-expect (dots (list (make-posn 12 31)))
              (place-image DOT 12 31 EMPTY-SCENE))
 
(define (dots lop)
  EMPTY-SCENE)  ; dummy result

The fourth step is to write a template. To do this, we must choose an abstraction that is best suited to the problem. This can be done by observing the function signature and seeing if we can potentially plug in our data types and make things work according to the purpose statement of the candidate abstraction. In this example, good candidates are foldr and foldl:

; foldr : {X Y} [X Y -> Y] Y [List-of X] -> Y
; foldl : {X Y} [X Y -> Y] Y [List-of X] -> Y

It seems that we could substitute X with Posn and Y with Image. This means the abstraction will take

• A function of type Posn Image -> Image
• A starting Image

and it will output an Image.

Since we want to start with an empty image and gradually add dots to the image, the template thus looks like this:

(define (dots lop)
  (local [; Posn Image -> Image 
          (define (add-one-dot p scene)
            (... (posn-x p) ... (posn-y p) ... scene ...))]
    (foldr add-one-dot EMPTY-SCENE lop)))

The fifth and sixth steps are as usual: fill in the body and test the function. This is the final result.

(define (dots lop)
  (local [; Posn Image -> Image 
          ; adds a DOT at p to scene
          (define (add-one-dot p scene)
            (place-image DOT
                         (posn-x p)
                         (posn-y p)
                         scene))]
    (foldr add-one-dot EMPTY-SCENE lop)))

The last chapter of this part introduces the lambda form, allowing us to avoid the local form and shorten the code into:

(define (dots lop)
  (foldr (lambda (p scene)
           (place-image DOT
                        (posn-x p)
                        (posn-y p)
                        scene))
         EMPTY-SCENE lop))

Part IV: Intertwined Data

Extending part II’s design recipe

This part is simply an extension of Part II. The data definitions here contain mutual recursion. The design recipe thus requires the reader to design multiple functions, specialized to each definition, at the same time.

An example used in this part is representing S-expressions, similar to Racket’s.

; An S-expr is one of: 
; – Atom
; – SL
 
; An SL (short for S list) is one of: 
; – '()
; – (cons S-expr SL)

; An Atom is one of: 
; – Number
; – String
; – Symbol 

Suppose we want to create a function count that counts the occurrences of symbol sy in a given S-expression sexp. We should create three functions, count, count-atom, and count-sl.

The function count acts as a dispatcher, so the template (which is just the full implementation) is easy to fill.

The other two are specialized to SL and Atom and actually do the work. These have to contain the appropriate selector expressions. Specifically, for count-sl, in the non-empty case, we need to have access to (first sl) and (rest sl).

Since (first sl) is of type S-expr and we need to count the symbol occurences in it, we write (count (first sl) sy) in our template. Since (rest sl) is of type SL, we can write (count-sl (rest sl) sy).

(define (count sexp sy)
  (cond
    [(atom? sexp) ...]
    [else ...]))
 
(define (count-sl sl sy)
  (cond
    [(empty? sl) ...]
    [else
     (...
      (count (first sl) sy)
      ...
      (count-sl (rest sl) sy)
      ...)]))

(define (count-atom at sy)
  (cond
    [(number? at) ...]
    [(string? at) ...]
    [(symbol? at) ...]))

Filling in the functions involves the same process as in earlier parts. We get the following code.

; S-expr Symbol -> N 
; counts all occurrences of sy in sexp 
(define (count sexp sy)
  (cond
    [(atom? sexp) (count-atom sexp sy)]
    [else (count-sl sexp sy)]))
 
; SL Symbol -> N 
; counts all occurrences of sy in sl 
(define (count-sl sl sy)
  (cond
    [(empty? sl) 0]
    [else
     (+ (count (first sl) sy) (count-sl (rest sl) sy))]))
 
; Atom Symbol -> N 
; counts all occurrences of sy in at 
(define (count-atom at sy)
  (cond
    [(number? at) 0]
    [(string? at) 0]
    [(symbol? at) (if (symbol=? at sy) 1 0)]))

Because the process is rather mechanical, students should be able to arrive at this solution if they follow the design recipe carefully. It would have been difficult to ask students to design something like this if we did not provide an overarching pattern that can be internalized and generalized.

The chapter also remarks that after doing all this work, we can simplify the code in multiple steps:

• count-sl and count-atom can be made local to count.
• Since SL is just a list, count-sl can be implemented with existing abstractions, in this case, map and foldl.
• count-atom can also be simplified a bit.
• Finally, we can inline count-sl and count-atom so there is no need for local scopes. Although, in this case, it might be better not to inline count-atom.

The next few chapters in part III are just a lot of exercises/projects, including writing an interpreter for a subset of Racket using the newly introduced environmental model.

Simultaneous processing

This chapter explicitly considers functions that take in two arguments or more, both of which are structurally recursive. There are three cases to consider.

Case 1: Treat the other argument as atomic. We have seen this previously in the book. Reading the purpose statement and functional examples, the programmer should determine which variable to recurse on. Consider this example:

; [List-of Number] [List-of Number] -> [List-of Number]
; replaces the final '() in front with end
(define (replace-eol-with front end)
  front)

The purpose statement suggests that we need to recurse on front, while end can be treated atomically. Therefore, the corresponding template only has conditionals and selectors on the first argument. (This function is analogous to append or list concatenation.)

Case 2: The arguments are of equal length. A function may take in two lists with equal length and perform an operation that pairs up the list elements coordinate-wise. In this case, the template’s conditional can act on either argument. The selector expressions should select from both arguments. Make sure to call the function recursively on smaller inputs.

; [List-of Number] [List-of Number] -> [List-of Number]
; multiplies the corresponding items on hours and wages/h 
; assume the two lists are of equal length 
(define (wages* hours wages/h)
  (cond
    [(empty? hours) ...]
    [else
     (... (first hours)
      ... (first wages/h) ...
      ... (wages*.v2 (rest hours) (rest wages/h)))]))

Case 3: The arguments are independent. In this case, we write down the cases for each argument, then find the Cartesian product. We fill in the template, just like we have always done, for all cases.

; [List-of Symbol] N -> Symbol
; extracts the nth symbol from l; 
; signals an error if there is no such symbol
(define (list-pick l n)
  (cond
    [(and (= n 0) (empty? l))
     ...]
    [(and (> n 0) (empty? l))
     (... (sub1 n) ...)]
    [(and (= n 0) (cons? l))
     (... (first l) ... (rest l)...)]
    [(and (> n 0) (cons? l))
     (... (sub1 n) ... (first l) ... (rest l) ...)]))

Unlike previous examples, it is unclear how we should make recursive calls in the last case, the one satisfying (and (> n 0) (cons? l)). There are three possibilities:

• (list-pick (rest l) (sub1 n))
• (list-pick l (sub1 n))
• (list-pick (rest l) n)

Because this cannot be determined, we move on to the next step of the design recipe which is to fill in the implementation. By using the table technique from part II, the programmer should be able to determine quickly that the answer is simply (list-pick (rest l) (sub1 n)).

This recipe can sometimes yield code that is longer than necessary. We can systematically simplify the implementation afterward.

Part V: Generative Recursion

The first chapter of part V explores problems that cannot be solved with just structural recursion. Consider the design of bundle, which chunks a list of length-1 strings (i.e. characters) into a list of length-n strings.

; [List-of 1String] N -> [List-of String]
; bundles chunks of s into strings of length n (or less)
(define (bundle s n)
  '())

;; Note that (implode "abcdefg") outputs
;; (list "a" "b" "c" "d" "e" "f" "g")
(check-expect (bundle (implode "abcdefg") 3)
              (list "abc" "def" "g"))

If we walk through all three cases presented in the previous chapter carefully, we will see that none of the approaches can work.

• We definitely cannot consider any one of the arguments atomic because, from the example test case, we have to take apart both arguments.
• We cannot recurse on s and n by assuming they have the same size and proceeding in lockstep. This is close, but bundle clearly has to reset n periodically.
• Treating both s and n as independent decouples the arguments too much.

This problem requires generative recursion, which is more ad-hoc than structural recursion. It is called generative recursion because it generates sub-problems using a non-structural mean.

For this kind of recursion, the design recipe is modified as follows:

• When writing the purpose statement of the function, we should also write how we plan to compute the result.
• The corresponding template will be based on whether the given arguments are trivially solvable. All algorithms have roughly this organization:

(define (generative-recursive-fun problem)
  (cond
    [(trivially-solvable? problem)
     (determine-solution problem)]
    [else
     (combine-solutions
       ... problem ...
       (generative-recursive-fun
         (generate-problem-1 problem))
       ...
       (generative-recursive-fun
         (generate-problem-n problem)))]))

• We need to consider the following questions to fill in the implementation. Here are the questions, copied verbatim from the book.

• What is a trivially solvable problem?
• How are trivial problems solved?
• How does the algorithm generate new problems that are more easily solvable than the original one? Is there one new problem that we generate or are there several?
• Is the solution of the given problem the same as the solution of (one of) the new problems? Or, do we need to combine the solutions to create a solution for the original problem? And, if so, do we need anything from the original problem data?

• Finally, we should write a termination argument, explaining why our function eventually terminates. If the function does not terminate for all inputs, we should restrict the acceptable inputs.

For the example problem, bundle, from earlier, the solution looks like the code below. Observe:

• the idea and the termination argument in the comment above bundle
• the trivial case is when (empty? s) is true
• the non-trivial case generates the subproblem (bundle (drop s n) n) (Note the lack of (first s) and (rest s) in this solution.)

; [List-of 1String] N -> [List-of String]
; bundles chunks of s into strings of length n
; idea: take n items and drop n at a time
; termination: (bundle s 0) loops unless s is '()
(define (bundle s n)
  (cond
    [(empty? s) '()]
    [else
     (cons (implode (take s n)) (bundle (drop s n) n))]))

; [List-of X] N -> [List-of X]
; keeps the first n items from l if possible or everything
(define (take l n) ...)

; [List-of X] N -> [List-of X]
; removes the first n items from l if possible or everything
(define (drop l n) ...)

Other classical examples include quicksort, binary search, and all kinds of mathematical examples like Euclidean’s algorithm, and Newton’s method.

Since SICP uses these examples from the very start (when introducing recursion), it is harder for beginners to extract general principles that they can use to inform their coding process. By focusing on structural recursion first, HTDP gets the easy stuff out of the way and makes it explicit when students need to do some creative problem-solving.

Part VI: Accumulators

Structural recursion has the issue of the loss of knowledge: when a function recurses on a smaller list, it does not know whether this is the complete input or actually just a piece of another list. It loses knowledge about the context of this computation. This loss of knowledge could result in unnecessary, redundant computations. Even worse, it may be impossible to develop a working function at all.

This part of the book introduces the idea of an accumulator variable, which helps mitigates this loss of knowledge. An accumulator variable is a variable that is passed alongside the usual input arguments. It satisfies an invariant, useful to this specific problem.

Consider this example problem: We want to write a function relative->absolute that converts a list of relative to absolute distances by listing out the prefix sums. One solution is the following:

; [List-of Number] -> [List-of Number]
; converts a list of relative to absolute distances
; the first number represents the distance to the origin
(define (relative->absolute l)
  (cond
    [(empty? l) '()]
    [else (local [(define rest-of-l
                    (relative->absolute (rest l)))
                  (define adjusted
                    (add-to-each (first l) rest-of-l))]
            (cons (first l) adjusted))]))
(check-expect (relative->absolute '(50 40 70 30 30))
              '(50 90 160 190 220))
 
; Number [List-of Number] -> [List-of Number]
; adds n to each number on l
(define (add-to-each n l)
  (map (lambda (x) (+ n x)) l))
(check-expect (cons 50 (add-to-each 50 '(40 110 140 170)))
              '(50 90 160 190 220))

This solution, however, has a running time of $O(n^2)$.

To solve problems using accumulators, we need to figure out what the accumulator should represent, then we use the following template.

; Domain -> Range 
(define (function d0)
  (local (; Domain AccuDomain -> Range
          ; accumulator invariant ...
          (define (function/a d a)
            ...)) ; expression involving a and sub-input of d
  (function/a d0 a0)))

Note that instead of designing function directly, we use the design recipe to design the accumulator version of the function, function/a. We would do structural recursion or generative recursion on the input arguments as usual, but the function should take extra arguments representing the accumulators. We can use the accumulators in the computation of the results if we assume and maintain appropriate invariants.

For the example from above, relative->absolute, we use the accumulator accu-dist to keep track of the sum of the elements seen up until this point. We implement relative->absolute/a by performing structural recursion on the list l but also taking in accu-dist as an extra argument⁴.

; [List-of Number] -> [List-of Number]
; converts a list of relative to absolute distances
; the first number represents the distance to the origin
 
(check-expect (relative->absolute.v2 '(50 40 70 30 30))
              '(50 90 160 190 220))
 
(define (relative->absolute.v2 l0)
  (local (
    ; [List-of Number] Number -> [List-of Number]
    ; accumulator: accu-dist is the sum of distances seen so far
    (define (relative->absolute/a l accu-dist)
      (cond
        [(empty? l) '()]
        [else
          (local ((define accu (+ (first l) accu-dist)))
            (cons accu
                 (relative->absolute/a (rest l) accu)))])))
    (relative->absolute/a l0 0)))

The book suggests the following steps when solving any given problem:

1. Try to solve the problem with structural recursion. “If a structurally recursive function traverses the result of its natural recursion with an auxiliary, recursive function, consider the use of an accumulator parameter.” This is to optimize the solution’s time complexity.
2. If the problem has to be solved with generative recursion, an accumulator may be required to obtain a correct, terminating algorithm. (For example, traversing a graph requires that we keep track of the visited notes, so we do not get stuck in a cycle.)

Taken to its extreme, this style becomes analogous to “iteration” (tail recursion) as taught in SICP.