Skip to content
Topos Uranos
English

Synthesis and challenges: functions

Summary

This lesson closes the fifth unit of the course, devoted to functions. It reconstructs the chain of concepts that runs from the declaration of a function to recursion, by way of the call stack, the contract, parameter passing, the scope and the storage duration of variables, and design by stepwise refinement; it separates what of all this holds in any language from what is specific to C++; it gathers the undefined behavior of the unit, with what the compiler warns about, what the sanitizer stops and what nobody flags; it repeats in its exit assessment the skills of the entry assessment; and it ends with six challenges that combine the whole unit.

Learning objectives

  1. Decompose a problem into functions, each with its interface and its contract (precondition and postcondition), and test them separately.
  2. Choose the passing mode of each parameter and the way of returning the results, and justify the choice.
  3. Solve a problem by recursion and prove its correctness by induction and its termination with a decreasing measure, estimating its cost in calls.
  4. Recognize the undefined behavior of the unit (the path without return, the dangling reference, the result that overflows, the exhausted stack) and rewrite the program without it.
  5. Separate, in what was learned in the unit, what holds in any language from what is specific to C++.

What the unit achieved

The unit set out to teach how to decompose a problem into named parts, each with an interface and a contract, and how to solve problems by recursion. The purpose has been fulfilled relying only on what the introduction declared it took for granted: the loops of unit 4, with their invariant and their variant, the specification of lesson 1.1 and the memory model of unit 2. The amicable numbers program, whose copied loop added up the divisors of the wrong number, is now written with a single function, verified once against its contract.

Functions

The lesson Functions taught how to declare, define and call a function, and it separated three moments: at compile time, each call is checked against a declaration seen earlier; at link time, the definition is looked up; at run time, the arguments are computed, a frame is created on the call stack and control jumps to the body. It showed that reaching the end of a function that is not void without a return is undefined behavior, and it closed with the contract, the precondition and the postcondition, which divides the responsibilities between the caller and the function.

Parameters and scope

The lesson Parameters and scope studied the paths by which data enter and results leave: the parameter by value is a copy; the parameter by reference, a second name for the caller’s cell; the const reference reads without copying. From this follows the rule of choice (value for what is small, const reference for what is large and only read, reference only if modifying is the purpose) and, for several results, std::pair and std::tuple with structured bindings. It distinguished the scope of a name, a property of the text, from the storage duration of a variable, a property of the execution, and it ended with the reference that outlives its cell.

Designing with functions

The lesson Designing with functions taught how to decide which functions to write, by stepwise refinement: a short main that calls functions that are only declared, and the descent into each of them, so that the decomposition is drawn as a tree. It set the criteria of a good interface and the rule “one function, one task”, with its warning signs (the conjunction in the name, the function that does not fit on a screen, the flag) and hidden effects, such as the global variable; it presented overloading, with its order of preference and the ambiguous call; and it rewrote the algorithms of unit 4 as functions tested separately.

Recursion

The lesson Recursion taught that a function can call itself to solve a smaller instance of the problem. It proved correctness by induction, assuming the smaller call correct, and termination with a decreasing natural measure; it followed with the stack the frames that pile up and unwind, and showed how the stack is exhausted; it warned that the type of the result overflows long before the stack does; and it compared recursive and iterative Fibonacci: 2 692 5372\,692\,537 calls against 29 additions for F30F_{30}.