By Robert Laing
A longstanding hobby project of mine — developing an AI system which can read the rules and play just about any strategy game (chess, checkers, …), interacting with a human player via the web — has taught me the importance of systematic design. I’ve done a lot of MooCs and worked through lots of beginner tutorials on various programing languages, and found many of them leave students myopic by focusing on little problems (usually pointless ones because they involve re-doing stuff already done better by built-in functions), instead of teaching the big picture thinking required to develop proper software applications.
This is why I found a freely available textbook, How To Design Programs, really eye-opening in that it distilled the best ideas from Agile, specifications, templates or patterns… lots of different methodologies.
The How To Design Programs 6-step recipe can be summarised by this table.
|1. problem analysis||data definition||Develop a data representation for the information; create examples for specific items of information and interpret data as information; identify self-references.|
|2. header||signature; purpose; dummy definition||Write down a signature using defined names; formulate a concise purpose statement; create a dummy function that produces a constant value from the specified range.|
|3. examples||examples and tests||Work through several examples, at least one per clause in the data definition.|
|4. template||function template||Translate the data definition into a template: one cond clause per data clause; selectors where the condition identifies a structure; one natural recursion per self-reference.|
|5. definition||full-fledged definition||Find a function that combines the values of the expressions in the cond clauses into the expected answer.|
|6. test||validated tests||Turn them into unit tests and run them.|
Applying these techniques to various programing languages (besides Dr Racket, a Lisp-dialect Racket packaged with an IDE used by How To Design Programs to keep things novice friendly) requires getting to grips with various tools — which I’ve often found harder to learn than a given language itself.
Let us change our traditional attitude to the construction of programs: Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do. — Donald E. Knuth
The design of a program proceeds in a top-down planning phase followed by a bottom-up construction phase. We explicitly show how the interface to libraries dictates the shape of certain program elements. In particular, the very first phase of a program design yields a wish list of functions. — How To Design Programs
The How To Design Programs gives a six step recipe which is handy, but needs a quite a lot of tweaking and elaboration. It also involves getting to grips with various tools in different programing languages.
- Data Definitions: Formulate data definitions and illustrate them with examples.
- Signature, Purpose Statement, Header (this bundles together what is commonly in function's structured comment)
- State what kind of data (type) the desired function consumes and produces.
- Formulate a concise answer to the question what the function computes.
- Define a stub that lives up to the signature.
- Functional Examples: Work through examples that illustrate the function’s purpose.
- Function Template: Translate the data definitions into an outline of the function.
- Function Definition: Fill in the gaps in the function template. Exploit the purpose statement and the examples.
- Testing: Articulate the examples as tests and ensure that the function passes all.
The above can be thought of as a fractal process in top-down design, since we need to start with a big picture sketch — as in what libraries, or modules, or packages… we need, and the drill down into what functions and helper functions they need.
Successful design is based on a principle known since the days of Julius Caesar: Divide and conquer. — Structured Design
Many of the benefits of object-oriented programing seem to blur with modularity which can be applied as easily to functional programing.
Wish Lists (aka interfaces)
One of the benefits of modularisation is it ties in with good design practices, what How To Design Programs calls a wish list:
We recommend keeping around a list of needed functions or a wish list. Each entry on a wish list should consist of three things: a meaningful name for the function, a signature, and a purpose statement. — From Functions to Programs, How To Design Programs
Before you put a function on the wish list, you should check whether something like the function already exists in your language’s library or whether something similar is already on the wish list.
1. Meaningful names for functions
There are different types of functions, which in turn are related to the types they produce. How To Design Programs in Defining Structure Types lists various types of functions and their naming conventions:
- structure constructor
- structure selector
- structure predicate
foo?These are generally type tests such as
- equality predicate
case(foo) :- ...
- type converters
number->stringThese are sometimes called typecasters or coercers. The SWI Prolog equivalent is number_string(?Number, ?String)
Lisp allows kebab-case and using ? in variable names, which no other programing language I know of does.
How To Design Programs defines a predicate as a function that returns a boolean, and encourages the style of making these easy to spot by ending the with question marks. An alternative convention is to prefix predicates with is.
1.1 Meaningful names for variables
List names are plural, and their elements singular. eg xs is a list of x.
State what kind of data the desired function consumes and produces.
Good specifications will always improve programmer productivity far better than any programming tool or technique. — Milt Bryce
Here we think in terms of types (programming jargon for sets).
3. Purpose Statements
A purpose statement is a BSL comment that summarizes the purpose of the function in a single line. If you are ever in doubt about a purpose statement, write down the shortest possible answer to the question
what does the function compute?
Every reader of your program should understand what your functions compute without having to read the function itself.
When you formulate a purpose statement, it is often useful to employ the parameter names to clarify what is computed. For example,