The Design Recipe, in Python

One of the goals of CSC 202 is to give you a structured and reliable design process that you can use in order to design and implement functions in a way that will minimize the time you spend reworking and debugging your functions. Put differently: I want to save you time.

The idea of the design recipe comes from the textbook "How To Design Programs", an excellent work that I recommend highly. It does not use Python as its language of instruction; I would otherwise use it as my principal textbook.

Choice of language notwithstanding, the basic elements of the design recipe apply well to CSC 202 development.

Here are the steps of the design recipe:

1. Data Definitions (if needed)

2. Purpose Statement and Header, including types

3. Test cases

4. Template

5. Fill in the Function

6. Test, iterate

Let’s go over these one at a time.

1 Data Definitions

Python has some built-in forms of data: integers, floating-point numbers, strings, booleans, et cetera.

Python also has compound data: objects, dictionaries, lists, and others.

For many different kinds of problems in data structures and elsewhere, it makes sense to define our own kinds of data. Specifically, in CSC 202 we are using primitive data, classes, and unions of these. This is generally speaking a "good fit" for functional, algebraic data structures. Here’s the first example, a linked list:

IntList : TypeAlias = Union[None,"Node"]

@dataclass(frozen=True)

class Node:

first : int

rest : IntList

There will be many more examples in the class, but this is a nice first one.

2 Purpose Statement and Header, including types

Each function you develop should come with a one-line comment stating its purpose.

This comment can immediately precede the function, or appear as a "docstring" as the first element of the function.

The header—essentially, the first line of the function—is also a part of step two. In addition to the name of the function and of the parameters, it should also include types associated with each parameter, and a return type.

Types in Python are a long-ish topic, but PEP 484 gives us a fairly clear way to specify most types, after importing all bindings from the typing library.

3 Test Cases

Step three is to write some test cases.

There’s a reason that step three comes before steps four and five: you should do it first!

That is: write your test cases before developing code for the function’s body.

Why? Your test cases are essentially a key part of your function’s specification. As you develop your test cases, you will find yourself exploring the meaning of your function without the function’s code in front of you, a far better position from which to consider the behavior and meaning of the function. It’s a common experience for developers—even very experienced developers—to discover as they sit down to write test cases that they hadn’t considered certain elements of the design that will wind up impacting the design of the function, and possibly even require a redesign of the function’s parameters and return type.

4 Template

Step four requires you to choose and write down a template.

We will talk about a whole bunch of different templates in CSC202, but the essence of a template is that it is a "code skeleton" that is derived from the type of your input data, and ensures that you consider all possible shapes that a value of that type might take on.

The template is clearest and most obviously helpful for data definitions such as the list class given above, and for related structures such as binary trees. In these cases, the template can be described as follows: the template for a union type must first use a conditional to determine which of the types in the union the data belongs to. Once this is done, the template must contain code that extracts each of the fields of the given object, and makes a recursive call on any elements whose type is the same as the type originally given as the input.

So, for the list data definition specified above, the template for a function called (say) list_fun that accepts a single IntList would be as follows:

def list_fun(l: IntList):

if (l is None):

return ...

else:

return ... l.first ...

... list_fun(l.rest) ...

Note that there’s no purpose statement here, and no return type. That’s because the template is not specific to the function being developed: this is the list template, and it’s probably the right template for most functions that take an IntList as an input.

5 Fill in the Rest of the Function

Okay, finally you get to fill in the rest of the function: go do it!

In particular, it’s generally fine to "use up" the template, by filling it in. This means that your final solution generally will not contain a copy of the template, because you filled it in. If a problem specifically requires you to include the template, then you should make a copy of it before editing it.

6 Test, Iterate

If you’re like me, your functions probably won’t work. At this point, your job is to assess what the problem is, and how far back in the design recipe you have to back up. If you’re lucky, the problem was in step five, and you can just adjust your function definition and be done. Otherwise, maybe you have to go back further.

7 Conclusion

At the end of the day, the goal here is simple: adopt a structured process that allows you to generate correct programs more efficiently.