The Design Recipe🔗

by Matthias Felleisen

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.

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 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.

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.

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.

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🔗

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 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.

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—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.

My hope is to work out some form of “recipe” for these designs, too, for some future edition of How to Design Programs.