The Design Recipe
08 Sep 2021
Changed in version 1.1: Thu Feb 3 17:02:46 EST 2022, responses to
feedback from Michael Ballantyne, Cameron Moy, and Jason Hemann
Changed in version 1.0: Thu Jan 20 11:49:54 EST 2022, initial release
Colleagues and students have occasionally asked where the design recipe comes from. Two sources inspired the design recipe: the approach to teaching of mathematics I experienced in my high school and Quine’s book on set theory. For the first, I am mostly grateful to Herr Dopfer’s strict style; for the second, I thank Nino Cocchiarella, one of many outstanding philosophy professors while I was at Indiana.
My hope is that writing down this background will improve people’s understanding of where I wish to go with the design recipe, and it may even eliminate some misunderstandings.
How to Teach Mathematics in Grade School and High School
Contemporary teaching of mathematics emphasizes the idea of a “correct answer.” Some teachers go as far as using multiple choice tests for mathematics problems. They state a problem, provide a number of feasible answers including the correct one, and students choose one of those. Grading such tests is easy; a machine can do it. But checking whether the student guessed the right answer or accidentally chose the wrong answer even while using the correct process becomes impossible.
The teachers of my high school (“Gymnasium” in Germany, grades 5 through 13)
used a rather different approach. From the very beginning, our teachers focused
on teaching a clean presentation of our thought processes that produced
the answer. In the beginning, the problems were simple, and having to follow a
process—
During my school time, a C was a rock-solid, average grade. What happened when students arrived at the wrong answer, following a systematic process and presenting their thoughts cleanly?
They got As.
And what happened to students who got the right answer but with a presentation that didn’t demonstrate a clear process?
They got Fs.
Did your teachers assign partial credit? Grades between A and F?
Yes they did, if elements of the presented process were correct and accessible.
the equation
why this step is correct
4 * x2 + 20
=
40
4 * x2
=
20
subtracting n from two equal numbers leaves them equal
x2
=
4
dividing two equal numbers by n != 0 leaves them equal
x
=
+2
the (positive) square root of two equal numbers is equal
The astute reader will have noticed the mistake in the third step:
dividing 20 by 4 is not 4. But the steps and their
justifications are correct otherwise. Hence the “student” deserves an A (or a
14/15 on the actual scale used) for this solution—
Now the very same line as the mistaken calculation comes with a blue markup in the justification part. Leaving off this constraint would partially invalidate the sentence, because dividing a number by 0 is pointless.
Finally, the last line comes with two green markups. Our teachers told
us the truth about square roots—
Our teachers did not insist on writing down these justifications for every
single problem. After getting it right a few times, leaving off the
justifications was okay—
the solution process
the ability to provide justifications for each step
a clean presentation that would imply a justification if it was omitted.
As a side effect, this form of teaching also avoid the only right-or-wrong idea about mathematics.
Presented this way, mathematics teaches people lessons for life, not just about
some basic mathematical facts (such as the Pythagorean theorem or the rules for
differentiating polynomials). Students would take a way that an orderly,
systematic search for solutions works; intermediate results are as important as
final products; and the ability to explain everything well—
Note on “Yes, we check their work.” In my experience with teaching 100s of teachers in the United States, I have often gotten the reply “of course we check the work of our students” when I presented an argument like the above. Every follow-up conversation revealed, however, that teachers meant “check the work if the answer is incorrect” so that they could assign partial credit. In other words, the emphasis is upsidw-down. Teachers in the US check the answer first and, if the answer is wrong, try to find “the work” to provide partial credit. By contrast, our teachers always started with the students’ solution process and check the answer only at the very end.
How to Study Set Theory According to Quine
Quine’s presentation of set theory and logic reinforced the idea of proceeding systematically at the level of an entire system of thought. He starts with a couple extremely basic axioms. Then he proves as much as possible, everything in the set of implications. Once the limits of this hull become clear, he agrees to add another axiom in order to be able to prove more theorems.
For example, induction is something we would like for the propositions on the
natural numbers. But the axioms to prove the induction theorem isn’t added until
almost halfway through the book—
Two Short Stories
Every major development has a casus belli, not just underlying reasons. The
development of the design recipe was triggered by two such events. The
design recipe for recursive data definitions had existed implicitly in
The Little Lisper; indeed, it had motivated the rewrite of the first to
the second edition. So when I taught a freshman course for the very first time
(F’1992), I used the existing bits to teach an extremely fast course, mixing
materials from Abelson and Sussman’s Structure and Interpretation with
Friedman and Wand’s Essentials. But other than mixing in the core
elements of the design recipe for recursive data, the course was still taught
with the typical “here’s some new syntax, here are some examples, go modify
them” style—
A day after we had handed out the grades for the final, we held office hours so students could complain. Nobody showed up for mine, so I joined Corky Cartwright, my co-instructor, who was in the middle of an argument with a student. I walked in to observe. In a nutshell, the argument was about one of the “warm up” problems on the final. The problem had asked for a simple recursive function, something on the order of factorial. The student’s answer consumed an entire letter-sized page, using every feature the course had covered: define, lambda, cons, set!, call/cc, and more. Corky had given a 0 for this answer, and the student tried to convince him of the correctness of the code. As I walked in Corky had finished entering it into Scheme and had begun exploring the function at the REPL. He could not find a mistake.
The course had emphasized writing “correct” solutions, and there was no pedagogic rationale to condemn this code as an abomination that nobody else should ever have to read.
What if we could make the slogan explicit and apply it to even the simplest function, say functions on Booleans, the simplest form of data? Why not start with those instead of lists and trees?
At first I was taken aback that Bruce would even consider abandoning the idea of
starting a course with functions on lists and ending it with a glimpse at the
kernel of an operating system and other key concepts from computer science. Once
I got over this shock—
I didn’t teach the freshman course for another year, but when I did, these two events were always on my mind.
The Design Recipe
The process axis adapts the mathematics teaching from How to Teach Mathematics in Grade School and High School.
The data axis adapts Quine’s way of explaining set theory from How to Study Set Theory According to Quine.
This essay emphasizes the instructor’s perspective. The design recipe also addresses a widely known student problem, namely, the “blank screen problem.” Many students don’t know how to get started, how to proceed when confronted with a word problem and a blank screen. The design recipe can help with this “stuck state” a lot.
the process step
the outcome
develop a data representation
data definitions & data examples
understand the function’s I/O
a function signature & purpose statement
illustrate the function’s purpose
worked input-output examples
collect all available information
the function’s template
fill in the holes of the template
the fill function definition
run the I/O examples
a unit-test suite
The first step of the design recipe is a difficult and an important step, and yet usually within grasp of almost all students. Every programming language has a sub-language for data (Booleans, chars, strings, integers, lists, arrays, and so on). To run programs, information from the real world must be represented with data in the chosen programming language. And that’s what is meant by “develop a data representation.”
If this new approach to teaching programming must bring across that functions
are created—
By implication, the driving force must be the complexity of data not the complexity of the features of the language. Indeed, adding complexity to data must determine the order in which features are introduced.
Hence the book starts with “atomic” data: booleans, numbers (but see below), chars, images, strings, symbols. Next it looks at enumerations and structure compositions of simple data, or as a modern programming language researcher would say “non-recursive algebraic types.” Self-referential data definitions come next, i.e., “recursive algebraic types.” To keep things simple, the initial examples are lists and natural numbers. Lazy lists or lazy data in general could be used like functions. Trees follow. Eventually functions are used as data to create (simple) abstractions.
To process basic, atomic data, functions use basic, atomic operations on these pieces of data. This is algebra. To make case distinctions for non-recursive algebraic datatypes, the language is equipped with conditionals. To deal with recursive types, the book reveals that functions can be recursive.
Program design isn’t as rigorous as set theory. So yes, the
development in the book comes with an occasional glitch that an ambitious
instructor may discover.
At each stage, the design recipe dictates what kind of functions students
can develop and which ones they cannot. The addition of new forms
of data expands this design space—
Note on “I have a design recipe for lists of numbers.” Contrary to
occasional statements in the literature, I do not think of the
(structural) design recipe (as presented above) as something that is tailored to
just a particular datatype or, worse, to one particular problem. For example,
there is one design recipe for lists and any form of tree. It applies to
classes of (shapes of) data definitions. But, even this statement is too narrow.
It is critical that the design recipe smoothly scales from simple classes of
definitions—
Note on the quality of design steps vs those of steps in a mathematical calculation. Two objections to raise here are that (1) the steps of the design recipe are not as small as those in mathematical calculations and (2) their justifications aren’t as simple either. Both of these objections are correct. It is also correct that the set of skills isn’t precisely defined by the data dimension in design recipe, though this is rarely a problem. As far as I am concerned, these objections merely point out that we may need additional work on the design recipe. They certainly don’t invalidate the idea of design recipes.
Systematic Design in HtDP
The design recipe isn’t all there is to “design” in the sense of the book’s
title. As a matter of fact, this particular function design recipe is useful
only for functions have one purpose—
The title of How to Design Programs uses the word “program,” and therefore the book includes two design recipes for complete programs. One is for simple batch programs, that is, programs that consume the content of a file and produce another file. In essence such programs compose string-processing functions, but the supporting software assists with viewing such files as lists and trees. The other one is for simple graphical-interactive programs, including programs that communicate with a server program. These kind of programs process events, and therefore they compose event-processing functions. Again, the supportive software simplifies event processing greatly compared to old-style frameworks, though systems such as React and Vue come close now.
The word “compose” refers to a generalization of the mathematical concept of function composition. For both cases, the book’s design suggestion is strict: the tasks are split along those lines and some mechanism(s) compose the functions that perform those tasks.
Finally there is also the idea that these string- and event-processing functions need to perform more than one task. Think of one that consumes lists of numbers and strings but is supposed to compute a property of just the numbers in this list. This abstract problem statement suggests two tasks, and the book tells students to design two functions and to then write a program that composes these two functions.
Design one function per task.
Design a composition function if it must perform many tasks.
Define abstractions instead of copying and modifying code.
My hope is to work out some form of “recipe” for these designs, too, for some future edition of How to Design Programs.