Last year I gave a talk at a symposium in honour of Matthias Felleisen‘s 60th birthday. My inspiration for the talk was his influential textbook How to Design Programs (“HtDP”), co-authored with Robby Findler, Matthew Flatt, and Shriram Krishnamurthi.
One of the main arguments of HtDP is that data structure determines program structure; consideration of the structure of the data being processed takes you some considerable way towards the design of the program. The point of my talk was that this works not only for the structure of input data, but also for output data. This observation leads to some natural design recipes that merit common use but are omitted from the book.
This post is a summary of my talk. I will illustrate with some examples; Matthias’s predilections notwithstanding, I will use Haskell syntax for those examples. There is a longer version of this post on my own blog.
Design Recipes
One key aspect of HtDP is the emphasis on design recipes for solving programming tasks. A design recipe is a template for the solution to a problem: a contract; a statement of purpose; a function header; example inputs and outputs; and a code skeleton. Following the design recipe entails completing the template, fleshing out the code skeleton, and finally testing using the examples.
The primary strategy for problem solving in the book is via analysis of the structure of the input. When the input is composite, like a record, the skeleton should name the available fields as likely ingredients of the solution. When the input has “mixed data”, such as a union type, the skeleton should enumerate the alternatives, leading to a case analysis in the solution. When the input is of a recursive type, the skeleton encapsulates structural recursion—a case analysis between the base case and the inductive case, the latter case entailing recursive calls.
The motivating example for structural recursion is Insertion Sort: recursing on the tail of a non-empty list and inserting the head into the sorted subresult.
![\displaystyle \begin{array}{@{}ll} \multicolumn{2}{@{}l}{\mathit{insertsort} :: [\mathit{Integer}] \rightarrow [\mathit{Integer}]} \\ \mathit{insertsort}\;[\,] &= [\,] \\ \mathit{insertsort}\;(a:x) &= \mathit{insert}\;a\;(\mathit{insertsort}\;x) \medskip \\ \multicolumn{2}{@{}l}{\mathit{insert} :: \mathit{Integer} \rightarrow [\mathit{Integer}] \rightarrow [\mathit{Integer}]} \\ \mathit{insert}\;b\;[\,] &= [b] \\ \mathit{insert}\;b\;(a:x) \\ \qquad \mid b \le a &= b : a : x \\ \qquad \mid b > a &= a : \mathit{insert}\;b\;x \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Barray%7D%7B%40%7B%7Dll%7D+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Binsertsort%7D+%3A%3A+%5B%5Cmathit%7BInteger%7D%5D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D%7D+%5C%5C+%5Cmathit%7Binsertsort%7D%5C%3B%5B%5C%2C%5D+%26%3D+%5B%5C%2C%5D+%5C%5C+%5Cmathit%7Binsertsort%7D%5C%3B%28a%3Ax%29+%26%3D+%5Cmathit%7Binsert%7D%5C%3Ba%5C%3B%28%5Cmathit%7Binsertsort%7D%5C%3Bx%29+%5Cmedskip+%5C%5C+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Binsert%7D+%3A%3A+%5Cmathit%7BInteger%7D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D%7D+%5C%5C+%5Cmathit%7Binsert%7D%5C%3Bb%5C%3B%5B%5C%2C%5D+%26%3D+%5Bb%5D+%5C%5C+%5Cmathit%7Binsert%7D%5C%3Bb%5C%3B%28a%3Ax%29+%5C%5C+%5Cqquad+%5Cmid+b+%5Cle+a+%26%3D+b+%3A+a+%3A+x+%5C%5C+%5Cqquad+%5Cmid+b+%3E+a+%26%3D+a+%3A+%5Cmathit%7Binsert%7D%5C%3Bb%5C%3Bx+%5Cend%7Barray%7D+&bg=ffffff&fg=000000&s=0&c=20201002)
A secondary, more advanced, strategy is to use generative recursion, otherwise known as divide-and-conquer. The motivating example is QuickSort: dividing a non-empty input list into two parts using the head as the pivot, recursively sorting both parts, and concatenating the results with the pivot in the middle.
![\displaystyle \begin{array}{@{}ll} \multicolumn{2}{@{}l}{\mathit{quicksort} :: [\mathit{Integer}] \rightarrow [\mathit{Integer}]} \\ \mathit{quicksort}\;[\,] & = [\,] \\ \mathit{quicksort}\;(a:x) &= \mathit{quicksort}\;y \mathbin{{+}\!\!\!{+}} [a] \mathbin{{+}\!\!\!{+}} \mathit{quicksort}\;z \\ & \qquad \mathbf{where}\; \begin{array}[t]{@{}ll} y &= [ b \mid b \leftarrow x, b \le a ] \\ z &= [ b \mid b \leftarrow x, b > a ] \end{array} \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Barray%7D%7B%40%7B%7Dll%7D+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Bquicksort%7D+%3A%3A+%5B%5Cmathit%7BInteger%7D%5D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D%7D+%5C%5C+%5Cmathit%7Bquicksort%7D%5C%3B%5B%5C%2C%5D+%26+%3D+%5B%5C%2C%5D+%5C%5C+%5Cmathit%7Bquicksort%7D%5C%3B%28a%3Ax%29+%26%3D+%5Cmathit%7Bquicksort%7D%5C%3By+%5Cmathbin%7B%7B%2B%7D%5C%21%5C%21%5C%21%7B%2B%7D%7D+%5Ba%5D+%5Cmathbin%7B%7B%2B%7D%5C%21%5C%21%5C%21%7B%2B%7D%7D+%5Cmathit%7Bquicksort%7D%5C%3Bz+%5C%5C+%26+%5Cqquad+%5Cmathbf%7Bwhere%7D%5C%3B+%5Cbegin%7Barray%7D%5Bt%5D%7B%40%7B%7Dll%7D+y+%26%3D+%5B+b+%5Cmid+b+%5Cleftarrow+x%2C+b+%5Cle+a+%5D+%5C%5C+z+%26%3D+%5B+b+%5Cmid+b+%5Cleftarrow+x%2C+b+%3E+a+%5D+%5Cend%7Barray%7D+%5Cend%7Barray%7D+&bg=ffffff&fg=000000&s=0&c=20201002)
No program structures other than structural recursion and generative recursion are considered.
Co-programs
My thesis is that HtDP has missed an opportunity to reinforce its core message, that data structure determines program structure. Specifically, I believe that the next design recipe to consider after structural recursion, in which the shape of the program is determined by the shape of the input, should be structural corecursion, in which the shape of the program is determined instead by the shape of the output.
More concretely, a function that generates “mixed output”—a union type, or simply a boolean—might be defined by case analysis over the output; for example, a program that may fail, such as division, can be guarded so as to return an alternative value in the failing case. A function that generates a record might be composed of subprograms that generate each of the fields of that record; for example, separate bits of code to generate the day, month, and year of a date. A function that generates a recursive data structure from some input data might be defined with a case analysis as to whether the result is trivial, and for non-trivial cases with recursive calls to generate substructures of the result. For example, the best explanation of “zipping” together two input lists to a list of pairs—taking [1,2,3] and [4,5,6] to [(1,4),(2,5),(3,6)], and for simplicity let’s say pruning the result to the length of the shorter input—is by case analysis on the output. When is the output empty? (When either input is empty.) If it isn’t empty, what is the head of the output? (The pair of input heads.) And from what data is the tail of the output recursively constructed? (The pair of input tails.)
![\displaystyle \begin{array}{@{}ll} \multicolumn{2}{@{}l}{\mathit{zip} :: [\alpha] \rightarrow [\beta] \rightarrow [(\alpha,\beta)]} \\ \mathit{zip}\;x\;y &= \begin{array}[t]{@{}l} \mathbf{if}\; \mathit{null}\;x \lor \mathit{null}\;y \;\mathbf{then}\; [\,] \;\mathbf{else}\; (\mathit{head}\;x,\mathit{head}\;y) : \mathit{zip}\;(\mathit{tail}\;x)\;(\mathit{tail}\;y) \end{array} \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Barray%7D%7B%40%7B%7Dll%7D+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Bzip%7D+%3A%3A+%5B%5Calpha%5D+%5Crightarrow+%5B%5Cbeta%5D+%5Crightarrow+%5B%28%5Calpha%2C%5Cbeta%29%5D%7D+%5C%5C+%5Cmathit%7Bzip%7D%5C%3Bx%5C%3By+%26%3D+%5Cbegin%7Barray%7D%5Bt%5D%7B%40%7B%7Dl%7D+%5Cmathbf%7Bif%7D%5C%3B+%5Cmathit%7Bnull%7D%5C%3Bx+%5Clor+%5Cmathit%7Bnull%7D%5C%3By+%5C%3B%5Cmathbf%7Bthen%7D%5C%3B+%5B%5C%2C%5D+%5C%3B%5Cmathbf%7Belse%7D%5C%3B+%28%5Cmathit%7Bhead%7D%5C%3Bx%2C%5Cmathit%7Bhead%7D%5C%3By%29+%3A+%5Cmathit%7Bzip%7D%5C%3B%28%5Cmathit%7Btail%7D%5C%3Bx%29%5C%3B%28%5Cmathit%7Btail%7D%5C%3By%29+%5Cend%7Barray%7D+%5Cend%7Barray%7D+&bg=ffffff&fg=000000&s=0&c=20201002)
HtDP should present explicit design recipes to address these possibilities, as it does for program structures determined by the input data.
Generative recursion, aka divide-and-conquer
Only once this dual form of program structure has been explored should students be encouraged to move on to generative recursion, because this exploits both structural recursion and structural corecursion. For example, the QuickSort algorithm that is used as the main motivating example is really structured as a corecursion build to construct an intermediate tree, followed by structural recursion flatten over that tree to produce the resulting list:
![\displaystyle \begin{array}{@{}ll} \multicolumn{2}{@{}l}{\mathit{quicksort} :: [\mathit{Integer}] \rightarrow [\mathit{Integer}]} \\ \mathit{quicksort} & = \mathit{flatten} \cdot \mathit{build} \medskip \\ \multicolumn{2}{@{}l}{\mathbf{data}\;\mathit{Tree} = \mathit{Empty} \mid \mathit{Node}\;\mathit{Tree}\;\mathit{Integer}\;\mathit{Tree}} \medskip\\ \multicolumn{2}{@{}l}{\mathit{build} :: [\mathit{Integer}] \rightarrow \mathit{Tree}} \\ \mathit{build}\;[\,] & = \mathit{Empty} \\ \mathit{build}\;(a:x) &= \mathit{Node}\;(\mathit{build}\;y)\;a\;(\mathit{build}\;z) \\ & \qquad \mathbf{where}\; \begin{array}[t]{@{}ll} y &= [ b \mid b \leftarrow x, b \le a ] \\ z &= [ b \mid b \leftarrow x, b > a ] \end{array} \medskip \\ \multicolumn{2}{@{}l}{\mathit{flatten} :: \mathit{Tree} \rightarrow [\mathit{Integer}]} \\ \mathit{flatten}\;\mathit{Empty} & = [\,] \\ \mathit{flatten}\;(\mathit{Node}\;t\;a\;u) &= \mathit{flatten}\;t \mathbin{{+}\!\!\!{+}} [a] \mathbin{{+}\!\!\!{+}} \mathit{flatten}\;u \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Barray%7D%7B%40%7B%7Dll%7D+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Bquicksort%7D+%3A%3A+%5B%5Cmathit%7BInteger%7D%5D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D%7D+%5C%5C+%5Cmathit%7Bquicksort%7D+%26+%3D+%5Cmathit%7Bflatten%7D+%5Ccdot+%5Cmathit%7Bbuild%7D+%5Cmedskip+%5C%5C+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathbf%7Bdata%7D%5C%3B%5Cmathit%7BTree%7D+%3D+%5Cmathit%7BEmpty%7D+%5Cmid+%5Cmathit%7BNode%7D%5C%3B%5Cmathit%7BTree%7D%5C%3B%5Cmathit%7BInteger%7D%5C%3B%5Cmathit%7BTree%7D%7D+%5Cmedskip%5C%5C+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Bbuild%7D+%3A%3A+%5B%5Cmathit%7BInteger%7D%5D+%5Crightarrow+%5Cmathit%7BTree%7D%7D+%5C%5C+%5Cmathit%7Bbuild%7D%5C%3B%5B%5C%2C%5D+%26+%3D+%5Cmathit%7BEmpty%7D+%5C%5C+%5Cmathit%7Bbuild%7D%5C%3B%28a%3Ax%29+%26%3D+%5Cmathit%7BNode%7D%5C%3B%28%5Cmathit%7Bbuild%7D%5C%3By%29%5C%3Ba%5C%3B%28%5Cmathit%7Bbuild%7D%5C%3Bz%29+%5C%5C+%26+%5Cqquad+%5Cmathbf%7Bwhere%7D%5C%3B+%5Cbegin%7Barray%7D%5Bt%5D%7B%40%7B%7Dll%7D+y+%26%3D+%5B+b+%5Cmid+b+%5Cleftarrow+x%2C+b+%5Cle+a+%5D+%5C%5C+z+%26%3D+%5B+b+%5Cmid+b+%5Cleftarrow+x%2C+b+%3E+a+%5D+%5Cend%7Barray%7D+%5Cmedskip+%5C%5C+%5Cmulticolumn%7B2%7D%7B%40%7B%7Dl%7D%7B%5Cmathit%7Bflatten%7D+%3A%3A+%5Cmathit%7BTree%7D+%5Crightarrow+%5B%5Cmathit%7BInteger%7D%5D%7D+%5C%5C+%5Cmathit%7Bflatten%7D%5C%3B%5Cmathit%7BEmpty%7D+%26+%3D+%5B%5C%2C%5D+%5C%5C+%5Cmathit%7Bflatten%7D%5C%3B%28%5Cmathit%7BNode%7D%5C%3Bt%5C%3Ba%5C%3Bu%29+%26%3D+%5Cmathit%7Bflatten%7D%5C%3Bt+%5Cmathbin%7B%7B%2B%7D%5C%21%5C%21%5C%21%7B%2B%7D%7D+%5Ba%5D+%5Cmathbin%7B%7B%2B%7D%5C%21%5C%21%5C%21%7B%2B%7D%7D+%5Cmathit%7Bflatten%7D%5C%3Bu+%5Cend%7Barray%7D+&bg=ffffff&fg=000000&s=0&c=20201002)
The structure of both functions build and flatten is determined by the structure of the intermediate Tree datatype, the first as structural corecursion and the second as structural recursion. A similar explanation applies to any divide-and-conquer algorithm; for example, MergeSort is another divide-and-conquer sorting algorithm, also with an intermediate tree shape, but this time with a simple splitting phase and all the comparisons in the recombining phase.
Having identified the two parts, structural recursion and structural corecursion, they may be studied separately; separation of concerns is a crucial lesson in introductory programming. Moreover, the parts may be put together in different ways: whereas divide-and-conquer consists of structural corecursion to generate a call tree followed by structural recursion to consume that tree, a metamorphism consists of structural recursion to consume structured input into some intermediate value, followed by structural corecursion to generate a different structured output.
None of this depends on laziness; it would all work as well in ML or Racket as in Haskell. HtDP already stipulates a termination argument in the design recipe for generative recursion; the same kind of argument should be required for structural corecursion (and is easy to make for the sorting examples given above).
Structured programming
HtDP actually draws on a long tradition on relating data structure and program structure, which is a theme dear to my own heart (and indeed, the motto of my blog). The book credits Jackson Structured Programming as partial inspiration for the design recipe approach. As Michael Jackson wrote:
The central theme of this book has been the relationship between data and program structures. The data provides a model of the problem environment, and by basing our program structures on data structures we ensure that our programs will be intelligible and easy to maintain.
and
The structure of a program must be based on the structures of all of the data it processes.
(my emphasis). In a retrospective lecture in 2001, he clarified:
program structure should be dictated by the structure of its input and output data streams
So even way back in 1975 it was clear that we need to pay attention to the structure of output data as well as to that of input data.
Ad-hockery
HtDP apologizes that generative recursion (which it identifies with the field of algorithm design)
is much more of an ad hoc activity than the data-driven design of structurally recursive functions. Indeed, it is almost better to call it inventing an algorithm than designing one. Inventing an algorithm requires a new insight—a “eureka”.
It goes on to suggest that mere programmers cannot generally be expected to have such algorithmic insights:
In practice, new complex algorithms are often developed by mathematicians and mathematical computer scientists; programmers, though, must th[o]roughly understand the underlying ideas so that they can invent the simple algorithms on their own and communicate with scientists about the others.
I say that this defeatism is a consequence of not following through on the core message, that data structure determines program structure. QuickSort and MergeSort are not ad hoc. Admittedly, they do require some insight in order to identify structure that is not present in either the input or the output. But having identified that structure, there is no further mystery, and no ad-hockery required.
Bio: Jeremy Gibbons is Professor of Computing at the University of Oxford, where he leads the Algebra of Programming research group and is former Deputy Head of Department. He served as Vice Chair then Past Vice Chair of ACM SIGPLAN, with a particular focus on Open Access. He is also Editor-in-Chief of the Journal of Functional Programming, SC Chair of ICFP, on the Advisory Board of PACMPL, an editor of Compositionality, and former Chair of IFIP Working Group 2.1 on Algorithmic Languages and Calculi.
Disclaimer: These posts are written by individual contributors to share their thoughts on the SIGPLAN blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGPLAN or its parent organization, ACM.
