Designing with functions

Stepwise refinement

From the statement to a main of a few lines

The programs of unit 4 were written entirely inside main. While they fit on one screen, that is tolerable; however, a two-hundred-line program written that way demands keeping everything in one’s head at once, and it can only be tested as a whole. Stepwise refinement, or top-down design, inverts the order of the work: first one writes what the program does, in the language of the problem, as a sequence of calls to functions that do not exist yet; then one takes each of those functions as a new, smaller problem, and repeats the procedure until reaching functions so simple that their body is written without decomposing anything.

The following problem serves as an example. An integer $n \geq 1$ is perfect if the sum of its proper divisors (the positive ones other than $n$) is equal to $n$, deficient if it is smaller and abundant if it is larger: $28 = 1 + 2 + 4 + 7 + 14$ is perfect; 8, with $1 + 2 + 4 = 7$, is deficient; 12, with $1 + 2 + 3 + 4 + 6 = 16$, abundant. We want a program that reads $n$ and writes the sum of its proper divisors and its kind. The first level of the design is main, and it is written before anything else:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Sum of the positive divisors of n.// Precondition: n >= 1.// Postcondition: returns the sum of all the positive divisors of n, including n.std::int64_t divisorSum(int n);​// Kind of n according to the sum of its proper divisors.// Precondition: n >= 1.// Postcondition: returns deficient, perfect or abundant as the sum is less than, equal to or greater than n.Kind classify(int n);​// Name of a kind, for writing it.// Precondition: none.// Postcondition: returns “deficient”, “perfect” or “abundant”.std::string kindName(Kind kind);​int main(){    int n{};    std::cin >> n;    std::println("Sum of the proper divisors of {}: {}", n, divisorSum(n) - n);    std::println("{} is {}", n, kindName(classify(n)));}

/usr/bin/x86_64-linux-gnu-ld.bfd: main.o: in function `main':main.cpp:27:(.text+0x22a): undefined reference to `divisorSum(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x3fd): undefined reference to `classify(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x40d): undefined reference to `kindName[abi:cxx11](Kind)'collect2: error: ld returned 1 exit status

The program compiles without any warning, because each call agrees with its declaration, which is the only thing the compiler checks, as the lesson Functions taught. What fails is linking: the linker looks for the definitions and does not find them (“undefined reference”; the addition [abi:cxx11] is an internal mark of GCC for functions that return std::string). That state is exactly the state of the design at this point: the interfaces are decided, the bodies are not. If this is so, main already reads as the specification of the program, and the three declarations are the pending tasks, each one smaller than the original problem.

The decomposition tree

The second level descends into each declaration. kindName is a three-case decision. classify relies on divisorSum: a number is perfect when the sum of all its divisors is $2n$. And divisorSum is the loop over the divisors in pairs $(d, n/d)$ from the lesson Numerical algorithms, which stops at $\sqrt{n}$. The result is drawn as a tree: the root is the complete problem; the children of each node, the subproblems that solve it; the leaves, operations that the language already offers.

With the tree complete, the definitions are written from the bottom up, so that each function relies on others already written:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Sum of the positive divisors of n.// Precondition: n >= 1.// Postcondition: returns the sum of all the positive divisors of n, including n.std::int64_t divisorSum(int n){    std::int64_t sum{0};    for (int d{1}; d <= n / d; ++d) {        if (n % d == 0) {            sum += d;            if (d != n / d) {                sum += n / d;            }        }    }    return sum;}​// Kind of n according to the sum of its proper divisors.// Precondition: n >= 1.// Postcondition: returns deficient, perfect or abundant as the sum is less than, equal to or greater than n.Kind classify(int n){    const std::int64_t proper{divisorSum(n) - n};    if (proper < n) {        return Kind::deficient;    }    if (proper == n) {        return Kind::perfect;    }    return Kind::abundant;}​// Name of a kind, for writing it.// Precondition: none.// Postcondition: returns “deficient”, “perfect” or “abundant”.std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "deficient";    }    if (kind == Kind::perfect) {        return "perfect";    }    return "abundant";}​int main(){    int n{};    std::cin >> n;    std::println("Sum of the proper divisors of {}: {}", n, divisorSum(n) - n);    std::println("{} is {}", n, kindName(classify(n)));}

28

Sum of the proper divisors of 28: 2828 is perfect

Three features of the result are due to the method. First, main did not change when what lies below was written. Second, the sum is returned as std::int64_t (from <cstdint>, the 64-bit integer that the lesson Recursion also uses), because for $n$ close to the maximum of int the sum of its divisors can exceed it, and deciding this in the interface protects everyone who calls. Third, each function is checked separately: divisorSum(28) must give 56, divisorSum(1) must give 1 and divisorSum(36) must give 91, where the pair $(6, 6)$ is counted only once; the last part of the lesson turns those checks into a program.