8.13.0.5

### 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—not to speak of writing it down in a readable manner—seemed pointless. But soon the topics and problems became complicated, and without a systematic process and a clean presentation, students couldn’t get anywhere.

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.

Yes they did, if elements of the presented process were correct and accessible.

Take a look at an extremely simple example, something that might show up in grades 6 and 7:
 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—if everything else is correct.

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—the positive and negative numbers work out—but initially insisted that we’d consider only positive outcomes. An A+ student would say so in the rationale.

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—if the presentation of the solution process implied them and could be checked with a simple glance. Every day teachers would quickly scan the (many) homework solutions in class, and they might call on someone to explain every step for some problem.

In sum, teaching mathematics insisted on these points:
• the solution process

• the ability to provide justifications for each step

• a clean presentation that would imply a justification if it was omitted.

The curriculum started with algebra and geometry (mixed), including 2d shape, 3d bodies plus some trigonometry; moved on to cover the very basics of rings, fields, vector spaces, linear algebra, isomorphisms, homomorphisms; got analysis (differentiation, integration); then used calculus to teach us the basics of optimizations; and ended with functions on Rn and a bit of toy material on complex functions. At every point, the teaching was all about processes and presentation of processes. Answer mattered little.

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—to reflect—matters.

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—because it is possible to prove so much without the axiom. Similarly, transfinite induction makes a late appearance, only after the axiom about infinite unions is admitted.

#### 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 style that is popular and wrong to this day.

This was the point where I intervened. I told Corky and the student that correctness didn’t matter here. What mattered was that an experienced programmer had been unable to read the solution to a simple problem in a reasonable amount of time (during the grading session). So if anybody had solved this kind of problem with such code in reality, a maintainer would have to throw away this code and start from scratch. However, this explanation revealed the meta-problem:

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.

I left the office wondering how I could improve the introductory course so that it would teach good coding habits while still aiming for “obviously correct” code.

Some time later I relayed this story to another colleague, Bruce Duba, who had also taught this Scheme-based freshman course. I shared how frustrated I was that our simplistic design slogan of the time—“function definitions follow the shape of the data they process”—couldn’t easily be used to give this student’s code a failing grade. Bruce’s responded with a question:

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—many weeks later—I began to consider the idea in depth and realized that focusing on the systematic design of functions and developing this idea for increasingly complex situations would truly amplify my Little Lisper thinking.

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 design recipe is a two-dimension grid: one axis describes the design process for individual functions, and the other axis describes the complexity of the data definition(s) that specify the function’s signature:

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.

Let’s briefly look at each of these points. A systematic process must yield intermediate products and must enable students to explain how to get from one product to the next. Similarly, it must help instructors diagnose a student’s progress on a problem via the inspection of the intermediate products—but without focusing on the specifics of the problem. Now recall the basic six steps for designing a one-task function:
 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
It is possible to swap the second with the third and fourth step. Every step is small. Every step has a well-defined outcome. Every step is based on the outcomes of the preceding steps. And How to Design Programs supplies a universal justification for each step. That is, like the justifications of steps in mathematical problems, How to Design Programs’s do not depend on the specific problem at hand, but students can easily tailor them to a problem and a specific design step.

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—and therefore understood—in a systematic manner, it must introduce data as carefully as the mathematics curriculum introduces more and more complex concepts and as carefully as Quine adds axioms about sets.

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—the skill set of students to design functions properly—because programs can process new forms of information and the expanded design recipe explains how to create such functions systematically.

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—say enumerations of strings—to complex forms—say recursive enumerations. There is never a need for taking away existing hints in the design recipe—just like Quine never removes an axiom.

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.

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—or in more traditional terms, perform one task. So there is more.

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.

A gap of How to Design Programs’s systematic design approach is that it does not explain (too much) how to come up with systematic separation of tasks and compositions of the respective functions. Instead it tells students to follow certain slogans. Here are the three most important ones: These wordings are not verbatim from the book.
• 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.