The Design of Programs

The Functional Analysis Design Method

One way to organize our thinking about the program (solution) is to begin at the highest level and ask the question:

What will the program start with and what will it need to produce?

This amounts to the question: What are its inputs and outputs? Fig. ¿fig:functional-design-a? illustrates this high-level conception of the program as a block that transforms inputs into outputs.

This is the beginning of the functional analysis design method. We have treated the program as a function, which, like a mathematical function, maps inputs to ouputs. The next step is to consider the question:

How can the program achieve this transformation of its inputs to its outputs?

Many techniques may be explored, but often they can be separated into subfunctions. The subfunctions can themselves have subfunctions. This way of breaking down the problem into functions and subfunctions is the key to the power of the functional analysis design method. We see that, at all levels, the paradigm of mapping of inputs to outputs through functions applies, as illustrated in fig. ¿fig:functional-design-b?. Drawing these functional blocks and connecting their inputs and outputs is a crucial step in a program design process.

In Python program design, we have Python functions (section 1.9) and methods (section 1.5) to perform the role of the function blocks in the functional analysis design method. Inputs are passed as input arguments (or objects) and outputs are the returned values (or mutated objects). If we begin by sketching a functional diagram of inputs, outputs, and functional blocks from the highest level to the lowest, the programming of the corresponding Python functions and methods becomes a matter of implementing a structure we have already thoroughly considered. This technique is a great way to overcome the anxiety of the “blank page.”

Algorithm Representation via Pseudocode

At a certain depth, the functional blocks of subsection 2.7.1 have reached a level that is best treated as indivisible. It is not always obvious when this point is reached, but we can always iterate later. From here, simple functional blocks can be implemented directly in Python functions. For complex functions, a more complex sequence of steps may be necessary. We call a sequence of steps like this an algorithm.²

It is often useful to outline an algorithm schematically in a language we call pseudocode. This is a loose but programming-like language used to describe the algorithm without concern for syntax and implementation details. That is, pseudocode is used to express in structured natural language the semantics of a program without concern for its syntax in any specific programming language. The term “structured” here means some familiar programming structures—such as assignments, branches, loops, and functions—appear in pseudocode.

A sorting algorithm is an algorithm for sorting the elements of a list (e.g., numbers) by some metric (e.g., magnitude) such that the input list is returned ordered. There are many sorting algorithms with different efficiencies, but a relatively simple one is called bubble sort. For the sake of simplicity, we consider a list of \(n\) distinct numbers to be ordered such that they have increasing value. This algorithm repeatedly passes through the list, comparing adjacent elements and swapping their positions if they are out of order. After a single pass through the list, the greatest element will be in the last position because in every pairing, it is the greater. After the second pass, the second-greatest element will be in the penultimate position. After \(n-1\) passes, the list should be sorted.

In pseudocode, we can describe the algorithm more precisely, as shown in .

Can you think of a way to improve this algorithm? Often, when we write out the algorithm in pseudocode, it becomes more clear and improvements suggest themselves.

Once the algorithm for all complex functions are written in pseudocode, it is time to implement them as Python functions or methods. The functional analysis design diagrams of subsection 2.7.1 and the pseudocode algorithms from this section will help us rationalize this process and greatly improve our programs.