20220202211446-how_to_design_programs.org

How to Design Programs

tags

Racket

Book by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi. Available online.

There are solutions to the exercises from the community:

• https://github.com/eareese/htdp-exercises (partial)
• https://github.com/adaliu-gh/htdp
• Check my own solutions here.

Related:

• Supplemental materials
• How to Design Worlds

lang

Just a temporary memo for the #lang syntax:

#lang htdp/bsl
#lang htdp/bsl+
#lang htdp/isl
#lang htdp/isl+
#lang htdp/asl

Design recipe

I prefer to define constants when I feel like it during the design recipe.

1. Express how you wish to represent information as data.

   When the problem statement distinguishes different classes of input information, you need carefully formulated data definitions.

   A data definition must use distinct clauses for each sub-class of data or in some cases just individual pieces of data. Each clause specifies a data representation for a particular sub-class of information. The key is that each sub-class of data is distinct from every other class, so that our function can proceed by analyzing disjoint cases.

   This step might be optional if information is data. Example: function acting on the structure of a string.

   Symbolic definitions are better (see ex. 61).

2. Create the wish-list of functions.

   Write down a name, a signature, a statement of purpose, and a function header. The header should return an obvious instance of the target type.

   In the case of world programs, I like to write the main function at this moment.

   Then I run the definitions just to check everything is in order.

3. Illustrate the signature and the purpose statement with some functional examples in the form of tests. To construct a functional example, pick one piece of data from each input class from the signature and determine what you expect back. Pick at least one example from each sub-class in the data definition. Also, if a sub-class is a finite range, be sure to pick examples from the boundaries of the range and from its interior.

   I personally prefer to write the tests right next to the function and them move them in a test section for readability.

4. Take inventory.

   This is particularly interesting in the case of the conditional template. This template mirrors the organization of sub-classes with a cond.

   The function’s body must be a conditional expression with as many clauses as there are distinct sub-classes in the data definition. If the data definition mentions three distinct sub-classes of input data, you need three cond clauses; if it has seventeen sub-classes, the cond expression contains seventeen clauses. Second, you must formulate one condition expression per cond clause. Each expression involves the function parameter and identifies one of the sub-classes of data in the data definition:

5. Code.

   Start from the various cond lines. Assume that the input parameter meets the condition and so you exploit the corresponding test cases. To formulate the corresponding result expression, you write down the computation for this example as an expression that involves the function parameter.

6. Run the tests.