Review/Summary: How to Design Programs (HTDP vs. SICP)
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
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^{1}, 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 similarlooking procedures (§1.2). Specifically, the book distinguishes recursion from iteration, more commonly known as tail recursion in other programming languages^{2}, 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 higherorder functions as a way to abstract similar processes (§1.3). Higherorder 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 polymorphismlike features (§2.42.5).
The rest of the chapters deal with mutation and environmental model (§3.13.3), concurrency (§3.4), stream processing (§3.5), interpreter (§4.1), alternative language features like lazy evaluation and logic programming (§4.24.4), a model of register machines with an assemblylike language (§5.15.3), and compilation (§5.45.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 firstclass 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 adhoc 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:
 FixedSize Data
 Arbitrarily Large Data
 Abstraction
 Intertwined Data
 Generative Recursion
 Accumulators Between each part of the book, there is an “intermezzo” that dives into nittygritty details like Racket’s quoting mechanism, scoping, and exact/inexact number representations. The first of these intermezzos describes the syntax and semantics of Racket^{3} 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: FixedSize Data
The mechanics
The first chapter describes the builtin data types: numbers, strings, images, and booleans. It shows how to define constants and apply builtin functions. Images are manipulated via the book’s library (or “teachpack”) 2htdp/image
which has primitive operations like circle
, line
, imagewidth
, placeimage
, overlay
, beside
, above
, saveimage
, 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 (emptyscene 100 100))
(define DOT (circle 3 "solid" "red"))
(define (main y)
(bigbang y
[ontick sub1]
[stopwhen zero?]
[todraw placedotat]
[onkey stop]))
(define (placedotat y)
(placeimage 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, checkexpect
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 areaofsquare
, 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 (areaofsquare 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 bigbang
, 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
, andend?
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 47) dive into information that cannot be represented with just the builtin 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
(checkexpect (trafficlightnext "red") "green")
(define (trafficlightnext 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 toplevel function would act as a dispatcher.
The book also introduces structs in Racket. Structs can be defined via the syntax (definestruct structname [field1 field2 ...])
like (definestruct posn [x y])
for example. This would automatically generate a constructor (named makestructname
) and selector procedures (named structnamefieldk
). 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 makeposn
, posnx
, posny
and posn?
with the following properties:
∀ x y, (posnx (makeposn x y)) = x
∀ x y, (posny (makeposn x y)) = y
∀ z, (∃ x y, z = (makeposn 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:
; (maker3 Number Number Number)
(definestruct r3 [x y z])
(define ex1 (maker3 1 2 13))
(define ex2 (maker3 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 (r3distanceto0 p)
(... (r3x p) ... (r3y p) ... (r3z 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:
; – (makeaim UFO Tank)
; – (makefired UFO Tank Missile)
; interpretation: represents the complete state of a space invader game
(definestruct aim [ufo tank])
(definestruct fired [ufo tank missile])
UFO
, Tank
and Missile
are defined further like this.
; A UFO is a Posn.
; interpretation: (makeposn x y) is the UFO's location
; (using the topdown, lefttoright convention)
; A Tank is a structure:
; (maketank Number Number).
; interpretation: (maketank x dx) specifies the position:
; (x, HEIGHT) and the tank's speed: dx pixels/tick
(definestruct tank [loc vel])
; A Missile is a Posn.
; interpretation (makeposn x y) is the missile's place
This means the rendering function should have a template that looks like
(define (sirender s)
(cond [(aim? s)
(... (aimtank s) .. (aimufo s) ...)]
[(fired? s)
(... (firedtank s) ... (firedufo x) ... (firedmissle s) ...)]))
See the code here for the implementation. Note that sirender
makes calls to tankrender
, uforender
, and missilerender
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 (ufomove1 u)
(... (ufoloc u) ... (ufovel u) ...))
; Posn Vel > Posn
; adds v to p
(define (posn+ p v) ...)
;; Don't do this:
; UFO > UFO
; ...
(define (ufomove1 u)
(... (posnx (ufoloc u)) ...
... (posny (ufoloc u)) ...
... (veldeltax (ufovel u)) ...
... (veldeltay (ufovel 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 Listofstrings is one of:
; – '()
; – (cons String Listofstrings)
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 builtins.)
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 Listofstrings
, we note that we will use the answer from the recursive call, (howmany (rest alos))
.
; Listofstrings > Number
; determines how many strings are on alos
(define (howmany alos)
(cond
[(empty? alos) ...]
[(cons? alos) ;or `else`
(... (first alos) ...
... (howmany (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 (howmany (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 subinputs, 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 subinputs.
For example, consider the list (cons "x" (cons "b" (cons "a" '())))
. The table would look like this.
alos 
(first alos) 
(rest alos) 
(howmany (rest alos)) 
(howmany alos) 

(cons "a" '()) 
"a" 
'() 
0 
1 
(cons "b" (cons "a" '())) 
"b" 
(cons "a" '()) 
1 
2 
(cons "x" (cons "b" (cons "a" '()))) 
"x" 
(cons "b" (cons "a" '())) 
2 
3 
From this table, we can conclude that the answer in the recursive case is (+ 1 (howmany (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 > Listofstrings
; creates a list of n copies of s
(checkexpect (copier 0 "hello") '())
(checkexpect (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.
; Listofnumbers > Listofnumbers
; rearranges alon in descending order
(checkexpect (sort> '()) '())
(checkexpect (sort> (list 3 2 1)) (list 3 2 1))
(checkexpect (sort> (list 1 2 3)) (list 3 2 1))
(checkexpect (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 Listofnumbers > Listofnumbers
; 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 nonempty 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 NEListoftemperatures is one of:
; – (cons CTemperature '())
; – (cons CTemperature NEListoftemperatures)
; interpretation: nonempty lists of Celsius temperatures
The template will look like this.
; NEListoftemperatures > Number
; computes the sum of the given temperatures
;; tests omitted
(define (sum nel)
(cond
[(empty? (rest nel)) (... (first nel) ...)]
[else
(... (first nel) ... (sum (rest nel)) ...)]))
Note how we use (empty? (rest nel))
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 nel)
. For the recursive case, we use (first nel)
and recurses on (rest nel)
.
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
; – (makelayer String RD)
(definestruct layer [color doll])
;; a data example satisfying the data definition for RD
(define exrd (makelayer "pink" (makelayer "black" "white")))
The template would similarly use the appropriate selectors. Specifically, for the recursive case, we have access to (layercolor anrd)
and (layerdoll anrd)
. We likely apply the function recursively, so we write (depth (layerdoll anrd))
in the template.
; RD > Number
; how many dolls are a part of anrd
(define (depth anrd)
(cond
[(string? anrd) ...]
[(layer? anrd)
(... (layercolor anrd) ...
... (depth (layerdoll anrd)) ...)]))
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 fixedsize 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 [Listof ITEM] is one of:
; – '()
; – (cons ITEM [Listof ITEM])
How to use abstractions
The book then changes its focus from creating abstractions to using abstractions. It discusses conventional, higherorder 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 wellknown 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:
; [Listof Posn] > Image
; adds the Posns on lop (short for list of positions) to the empty scene
(checkexpect (dots (list (makeposn 12 31)))
(placeimage DOT 12 31 EMPTYSCENE))
(define (dots lop)
EMPTYSCENE) ; 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 [Listof X] > Y
; foldl : {X Y} [X Y > Y] Y [Listof 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 (addonedot p scene)
(... (posnx p) ... (posny p) ... scene ...))]
(foldr addonedot EMPTYSCENE 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 (addonedot p scene)
(placeimage DOT
(posnx p)
(posny p)
scene))]
(foldr addonedot EMPTYSCENE 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)
(placeimage DOT
(posnx p)
(posny p)
scene))
EMPTYSCENE 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 Sexpressions, similar to Racket’s.
; An Sexpr is one of:
; – Atom
; – SL
; An SL (short for S list) is one of:
; – '()
; – (cons Sexpr 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 Sexpression sexp
. We should create three functions, count
, countatom
, and countsl
.
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 countsl
, in the nonempty case, we need to have access to (first sl)
and (rest sl)
.
Since (first sl)
is of type Sexpr
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 (countsl (rest sl) sy)
.
(define (count sexp sy)
(cond
[(atom? sexp) ...]
[else ...]))
(define (countsl sl sy)
(cond
[(empty? sl) ...]
[else
(...
(count (first sl) sy)
...
(countsl (rest sl) sy)
...)]))
(define (countatom 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.
; Sexpr Symbol > N
; counts all occurrences of sy in sexp
(define (count sexp sy)
(cond
[(atom? sexp) (countatom sexp sy)]
[else (countsl sexp sy)]))
; SL Symbol > N
; counts all occurrences of sy in sl
(define (countsl sl sy)
(cond
[(empty? sl) 0]
[else
(+ (count (first sl) sy) (countsl (rest sl) sy))]))
; Atom Symbol > N
; counts all occurrences of sy in at
(define (countatom 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:
countsl
andcountatom
can be made local tocount
. Since
SL
is just a list,countsl
can be implemented with existing abstractions, in this case,map
andfoldl
. countatom
can also be simplified a bit. Finally, we can inline
countsl
andcountatom
so there is no need for local scopes. Although, in this case, it might be better not to inlinecountatom
.
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:
; [Listof Number] [Listof Number] > [Listof Number]
; replaces the final '() in front with end
(define (replaceeolwith 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 coordinatewise. 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.
; [Listof Number] [Listof Number] > [Listof 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.
; [Listof Symbol] N > Symbol
; extracts the nth symbol from l;
; signals an error if there is no such symbol
(define (listpick 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:
(listpick (rest l) (sub1 n))
(listpick l (sub1 n))
(listpick (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 (listpick (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 length1 strings (i.e. characters) into a list of lengthn
strings.
; [Listof 1String] N > [Listof 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")
(checkexpect (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
andn
by assuming they have the same size and proceeding in lockstep. This is close, butbundle
clearly has to resetn
periodically.  Treating both
s
andn
as independent decouples the arguments too much.
This problem requires generative recursion, which is more adhoc than structural recursion. It is called generative recursion because it generates subproblems using a nonstructural 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 (generativerecursivefun problem)
(cond
[(triviallysolvable? problem)
(determinesolution problem)]
[else
(combinesolutions
... problem ...
(generativerecursivefun
(generateproblem1 problem))
...
(generativerecursivefun
(generateproblemn 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 nontrivial case generates the subproblem
(bundle (drop s n) n)
(Note the lack of(first s)
and(rest s)
in this solution.)
; [Listof 1String] N > [Listof 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))]))
; [Listof X] N > [Listof X]
; keeps the first n items from l if possible or everything
(define (take l n) ...)
; [Listof X] N > [Listof 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 problemsolving.
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:
; [Listof Number] > [Listof 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 restofl
(relative>absolute (rest l)))
(define adjusted
(addtoeach (first l) restofl))]
(cons (first l) adjusted))]))
(checkexpect (relative>absolute '(50 40 70 30 30))
'(50 90 160 190 220))
; Number [Listof Number] > [Listof Number]
; adds n to each number on l
(define (addtoeach n l)
(map (lambda (x) (+ n x)) l))
(checkexpect (cons 50 (addtoeach 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 subinput 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 accudist
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 accudist
as an extra argument^{4}.
; [Listof Number] > [Listof Number]
; converts a list of relative to absolute distances
; the first number represents the distance to the origin
(checkexpect (relative>absolute.v2 '(50 40 70 30 30))
'(50 90 160 190 220))
(define (relative>absolute.v2 l0)
(local (
; [Listof Number] Number > [Listof Number]
; accumulator: accudist is the sum of distances seen so far
(define (relative>absolute/a l accudist)
(cond
[(empty? l) '()]
[else
(local ((define accu (+ (first l) accudist)))
(cons accu
(relative>absolute/a (rest l) accu)))])))
(relative>absolute/a l0 0)))
The book suggests the following steps when solving any given problem:
 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.
 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.

Pure functions do not have any side effects and always return the same output given the same input. ↩

Scheme (as taught) does not have looping constructs like
for
orwhile
. Iteration has to be done through tail recursion. ↩ 
Or rather, a modified subset of Racket called BSL (Beginner Student Language), made for this book. ↩

To state the invariant more precisely: For all lists
l
and valuesaccudist
,(addtoeach accudist l)
gives the same result as(relative>absolute/a l accudist)
. A formal proof of this function in Coq can be found here on Github. (I had too much fun writing this.) ↩