Scheme Design Recipe (from How to Design Programs)

Phase Goal                 Activity

Data
Analysis
and Design

To formulate a data definition

Develop an inductive data definition.
One alternative must not refer to the definition
Explicitly identify all self-references in the data. definition

Contract
Purpose and
Header

To name the function.
To specify its classes of
  input data and its
  class of output data.
To describe its purpose.
To formulate a header.

Name the function, the classes of input data, the class of output data, and specify its purpose:
 ;; name : in1 in2 ...--> out
 ;; to compute ... from x1 ...
 (define (name x1 x2 ...) ...)

Examples         

To characterize the input-
output relationship via examples.

Create examples of the input-output relationship.
Make sure there is at least one example per subclass

Template

To formulate an outline.

Develop a cond-expression with one clause per alternative add selector expressions to each clause.
Annotate the body with natural recursions.
The self-references in this template and the data definition match!

Body                 

To define the function.

Formulate a Scheme expression for each simple cond-line.
Explain for all other cond-clauses what each natural recursion computes according to the purpose statement.

Test                

To discover mistakes.
  (``typos'' and logic)

Apply the function to the inputs of the examples.
Check that the outputs are as predicted

  Designing a function for self-referential data