Analyze the problem. The result of the analysis is a language definition and an interpretation. The latter explains what the various ASts represent. We often call this language definition a data definition.

Make up some sample phrases using the language definition. They come in handy for several of the following steps.

Formulate a purpose statement. A purpose statement is your concise description of the modeling (programming) task. One line of precise English per function suffices; if the project is large, add a paragraph for the entire project.

Also formulate a function signature (aka contract) using the language definition(s) from step 1.

Illustrate the concise purpose statement from step 2 with functional examples. The purpose of examples is to help you understand what the function actually computes.

Use the data definition from step 1 to design inputs. You should have one per language (non-terminal) clause and alternative. Use the purpose statement to figure out the expected values.

Create a function template, i.e., an outline of the function. An outline isn’t some informal pseudo-code essay, but a transformation of all the knowledge in the data definition into a code layout. See below for some examples; see HtDP for details.

Note: You are not required to show me your function templates in your homework solutions. I will be able to tell from your solution whether you can organize a function.

Define the function. Code.

In most cases this task requires little more than combining the pieces on the right-hand side of each clause of the template. These “combinators” are sometimes elements from the AST language, and sometimes you need simple Racket functions. For the latter, guess and experiment in the interactions area. Or look in the HelpDesk.

Turn the examples into unit tests. Tests confirm whether your functions produce the right outputs for the given inputs. If a test fails, you may have a mistake in the function, in the test, or in both.

Every program (collection of functions) needs a test suite. Whenever you edit your programs, re-run the test suite. Never turn in a program that doesn’t satisfy your test suite.

Atomic and unstructured data, e.g., symbols or chars or booleans, are at the bottom of the chain.

The nest simplest data definition enumerates a finite number of individual pieces of data. The Colors language is an example of this kind.

Next up are fixed-width combinations of data, called structures or records in many programming languages.

Of course, you can also enumerate structures now and mixes of structures and atomic data.

In the introduction to define-language we have already seen a self-referential data definition. You need those as soon as you want to deal with arbitrarily large data, including, for example, natural numbers (0, 1, 2, etc).

For the representation of programming languages, you most often need nests of mutually referential data definitions.