Procedural Abstraction

Abstract¶

The goal of procedural abstraction is code reuse, which enables programmers to efficiently solve a class of related problems without duplicating code. To make abstraction effective, programmers follow design principles such as encapsulation, which hides implementation details and exposes only necessary interfaces, and modularization, which organizes code into independent, reusable components. To achieve these principles, several techniques are employed: argument passing (by value or reference) controls how data flows into functions; function overloading enables multiple functions with the same name to handle different types or numbers of arguments; and closures capture local state for flexible, thread-safe code; recursion allows functions to call themselves so that the solution of a complex problem can be easily obtained by combining solutions for simpler subproblems. Together, these techniques make procedural abstraction a powerful tool for building maintainable and robust software systems.

from __init__ import *
!mkdir -p private

Motivation¶

With imperative programming, we compose different programs to solve different problems by designing the flow of control. However, for problems that are closely related, we often end up with duplicate code, making it difficult to maintain and extend the solutions over time. Procedural abstraction addresses this challenge by allowing us to define a piece of code that can be reused across different programs to solve similar problems.

To motivate the concept, recall the program for computing the GCD in Lecture 3:

int c;
while (a) {
    b = b % a;
    c = b;
    b = a;
    a = c;
}
if (b<0) b=-b;

Note that a local variable c is used to swap the values of a and b:

int c;
...
    c = b;
    b = a;
    a = c;
...

This can be simplified into one line using the function std::swap from <utility>:

%%cpp
int a=2*3*4, b=3*4*5; // input

cout << format("gcd({}, {})=", a, b);
while (a) {
    b = b % a;
    swap(a, b);   // swap the values of a and b  
}
if (b<0) b=-b;
cout << b << "\n"; // final answer

gcd(24, 60)=12

We can further simplify the program into nearly one line by defining a function:

%%cpp
int gcd(int a, int b) {
    return a? gcd(b%a, a): (b>0? b: -b);  // tail recursion
}  // function body must be a compound statement, i.e., enclosed by braces {}.

To use the function, we call/invoke it with two integers, whose values are passed to the parameters a and b in the function parameter scope:

%%cpp
int a=2*3*4, b=3*4*5; // input

cout << format("gcd({}, {})={}\n", a, b, gcd(a, b));  // function invocation

gcd(24, 60)=12

The function can even be used by a different programming language! Play with it using the ipywidgets in Python below:

@interact(a="2*3*4", b="3*4*5")
def print_gcd(a, b):
    print("gcd({}, {})={}".format(a:=eval(a), b:=eval(b), ROOT.gcd(a, b)))

For instance, change the input box for a to 2*3*4*5 to see the new GCD value instantly.

Code Reuse¶

How to reuse code?¶

Recall the program for computing the inverse square root in Lecture 3:

constexpr auto threehalfs = 1.5, rel_tol = 1e-9;
const auto x2 = x*0.5;
double x_, gap, abs_x, abs_x_;
do {
    y = y * (threehalfs - (x2 * y * y));
    x_=1/y/y; gap=(x>x_)?(x-x_):(x_-x); abs_x=(x>0?x:-x); abs_x_=(x_>0?x_:-x_);
} while (y<0 || x!=x && gap > rel_tol*(abs_x>abs_x_?abs_x:abs_x_));

The code contains long declarations with similar use of conditional operations:

...
..., gap, abs_x, abs_x_;
do {
    ...
    ... gap=(x>x_)?(x-x_):(x_-x); abs_x=(x>0?x:-x); abs_x_=(x_>0?x_:-x_);
} while (...);

We can improve the program using std::fabs from <cmath> and std::max from <algorithm>:

%%cpp
double x = 10./3;  // input

auto i = *(int64_t *) &x;
i = 0x5fe6eb50c7b537a9 - (i >> 1);
auto y = *(double *) &i;

constexpr auto threehalfs = 1.5, rel_tol=1e-9;
const auto x2 = x*0.5;
double x_;
do y = y * (threehalfs - (x2 * y * y));
while (y<0 || (x_=1/y/y)!=x && fabs(x-x_) > rel_tol*max(fabs(x),fabs(x_))); // <cmath> and <algorithms>
cout << format("rsqrt({})={}.\n", x, y); // final answer

rsqrt(3.3333333333333335)=0.547722557271348.

The code is more readable and easier to maintain.

Why not package the inverse square root as a function for others to use?

%%cpp
double rsqrt_fast(const double x) {
    auto i = *(uint64_t *) &x;
    i = 0x5fe6eb50c7b537a9 - (i >> 1);
    auto y = *(double *) &i;

    static constexpr auto rel_tol=1e-9;
    const auto x2 = x*0.5;
    double x_;
    do {
        static constexpr auto threehalfs = 1.5;
        y = y * (threehalfs - (x2 * y * y));
    } while ( // threehalfs is not in scope but rel_tol is
        y<0 || (x_=1/y/y)!=x && fabs(x-x_) > rel_tol*max(fabs(x),fabs(x_))); // <cmath>, <algorithm>
    return y;                    
}

@interact(x="10/3")
def print_rsqrt_fast(x):
    print("rsqrt({})={}".format(x:=eval(x), ROOT.rsqrt_fast(x)))

<cmath> corresponds to a standard library header file that specifies a set of common mathematical functions or constants defined in the standard library.

%%cpp
atan(tan(M_PI/4))*4  // arctan, tan, and pi

(double) 3.1415927

%%cpp
exp(log(M_E))            // exponential, natural logarithm, and natural number

(double) 2.7182818

%%cpp
sqrt(pow(2, 2))          // square root and power

(double) 2.0000000

Does it click? We can squeeze the inverse square root function into nearly one line using the std::sqrt function from <cmath>:

%%cpp
double rsqrt(const double x) {
    return 1./sqrt(x);     // <cmath>
}

@interact(x="10/3")
def print_rsqrt(x):
    print("rsqrt({})={}".format(x:=eval(x), ROOT.rsqrt(x)))

%%hermes
Explain briefly why the macro INFINITY is in the C++ standard but M_PI is not?

🌿 Fork/new: main (will create on click)

Hermes

Because the standard has to define what’s needed and can’t otherwise be written portably — not what’s merely convenient.

INFINITY is semantically required. ISO C99 §7.25.3 (adopted into C++) standardizes INFINITY, NAN, and HUGE_VAL as constant expressions. Every conforming implementation must use IEEE-754, which has a definite, unambiguous inf — so the committee could specify it exactly. It also can’t be portably written any other way: 1.0/0.0 is undefined behavior, and HUGE_VAL is only “a large finite value” on the non-IEEE platforms the standard still had to accommodate. There’s no alternative idiom for the infinity constant itself, so the standard had no choice.
M_PI is just a convenience constant. It comes from POSIX, not ISO C. π is transcendental, so no double value of it is exact — and the committee worried that publishing one specific value in the standard would invite endless complaints about precision, plus another untyped macro (the non-type-safe kind the caution cell above flags, platform-gated behind _USE_MATH_DEFINES on MSVC). The standard’s rule of thumb: don’t put in the standard what users can get for themselves.
M_PI has a portable substitute; INFINITY doesn’t. You can always write 4.0 * atan(1.0) or acos(-1.0) (and in C++17+, use the typed std::numbers::pi_v<double>). There is no equivalent portable expression for the infinity constant — that’s precisely why INFINITY had to be standardized.

I verified with g++ (-std=c++11) on this host: INFINITY prints inf, equals 1.0/0.0, and equals HUGE_VAL — consistent with the IEEE-754 mandate (on a hypothetical non-IEEE platform HUGE_VAL could be finite while INFINITY would still be true infinity).

To provide portable and type-safe constants, C++23 introduced <numbers>, which provides different constants in different types:

%%cpp
numbers::pi

(const double) 3.1415927

%%cpp
numbers::pi_v<float>

(const float) 3.14159f

The standard library also has other headers listed here such as those we have used so far:

<algorithm> for operating on ranges of elements,
<utility> for language support and other general purposes,
<iostream>, <format>, <limits>, <cstring>, <cstdint>, and <cstdlib>.

When to write your own code?¶

As a student learning programming, shouldn’t you write your own code all the time?

%%hermes
Explain briefly the benefit of reusing code from standard libraries instead of
writing your own?

↻ Session: main (ACP: 92c90f07-348…)

Hermes

The benefit is that you get a battle-tested, portable, readable solution for free instead of reinventing and debugging it yourself:

Faster to write — no reinventing the wheel. As the tip says, “the more you know about the functions available, the faster you can code.” You call std::sqrt(x) instead of deriving your own version. The lecture literally squeezes rsqrt down to one line: return 1./sqrt(x); — the whole job the standard library gives you back.
More readable and easier to maintain. std::sqrt and std::fabs are self-documenting at the call site. Your own equivalent (the rsqrt_fast above) hides a magic constant 0x5fe6eb50c7b537a9 and a bit-manipulation trick that a reader must reverse-engineer.
Correct, thoroughly tested, and portable. Standard library functions are exercised against the hard edge cases (zero, negatives, huge values, NaN) and the standard guarantees the same behavior on every platform and compiler. A hand-rolled version carries your bugs and its own platform quirks — exactly the fragility the M_PI caution flags (non-type-safe, #define-gated on MSVC). The C++23 <numbers> cell makes the same point: reach for the standard’s numbers::pi instead of a local constant.

The one caveat the next heading (“When to write your own code?”) raises: as a learner you’re expected to write your own to practice — so you should weigh “I need the skill” against “this is already solved for me.”

Other than being short, the implementation of rsqrt using sqrt actually gives better answers, especially when the argument is very large or very close to 0.

For instance, we expect $\frac1{\sqrt{0}}=\infty$ :

%%cpp
rsqrt(0)    // perfect!

(double) inf

%%cpp
rsqrt_fast(0)          // not large enough... Why?

(double) 8.0633208e+161

On the opposite extreme, we expect $\frac1{\sqrt{\infty}}=0$ :

%%cpp
rsqrt(1./0) // perfect!

(double) 0.0000000

%%cpp
rsqrt_fast(1./0)       // totally off... Why?

(double) inf

std::sqrt is also fast because it can be compiled to use the hardware accelerated SQRTSD instruction provided by the SIMD instruction sets.

The following cells generate the source code and compile it to use the SQRTSD instruction with the -O2 -ffast-math compiler options:

%%writefile private/rsqrt.cpp
#include <cmath>

double rsqrt(const double x) {
    return 1./std::sqrt(x);
}

Writing private/rsqrt.cpp

!clang++ --stdlib=libc++ -O2 -ffast-math -S private/rsqrt.cpp -o private/rsqrt.s

Solution to Exercise 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    	.file	"rsqrt.cpp"
    	.section	.rodata.cst8,"aM",@progbits,8
    	.p2align	3, 0x0                          # -- Begin function rsqrt
    .LCPI0_0:
    	.quad	0x3ff0000000000000              # double 1
    	.text
    	.globl	rsqrt
    	.p2align	4
    	.type	rsqrt,@function
    rsqrt:                                  # @rsqrt
    	.cfi_startproc
    # %bb.0:
    	sqrtsd	%xmm0, %xmm1
    	movsd	.LCPI0_0(%rip), %xmm0           # xmm0 = [1.0E+0,0.0E+0]
    	divsd	%xmm1, %xmm0
    	retq
    .Lfunc_end0:
    	.size	rsqrt, .Lfunc_end0-rsqrt
    	.cfi_endproc
                                            # -- End function
    	.ident	"Ubuntu clang version 22.1.8 (++20260714015917+ca7933e47d3a-1~exp1~20260714135927.17)"
    	.section	".note.GNU-stack","",@progbits
    	.addrsig

Program 1:Assembly code rsqrt.s showing std::sqrt can be compiled to use the hardware accelerated SQRTSD instruction provided by the SIMD instruction sets.

Abstraction¶

Callable¶

Procedural abstraction allows code reuse by hiding implementation details and exposing input parameters. A callable is the entity that realizes it:

It is a piece of code that can be invoked with different arguments passed to the input parameters.

In C++, functions are technically only one type of callables.

The following defines the simplest callable, which does nothing other than using three different kinds of brackets:

%%cpp
[](){}            // the simplest function

((lambda at input_line_78:2:2)) @0x5e247bd0cb90

This is called a lambda expression, which can be invoked by appending an empty argument list ():

%%cpp
[](){}()          // the simplest function call that does nothing

Alternatively, the callable can be defined as a function with the name do_nothing:

%%cpp
void do_nothing() {}     // the simplest named function
do_nothing()             // the simplest function call by the function name

Why the name lambda?

The name lambda originates from $\lambda$ -calculus, which is a formal system for computation introduced by Alonzo Church in 1930s. For more details, see the following video made with Manim:

Programming with Math | The Lambda Calculus

A lambda expression is also known as an anonymous function, even though it is not regarded as a function according to <type_traits> for meta-programming, i.e., programming:

%%cpp
!is_function_v<decltype([](){})> && is_invocable_v<decltype([](){})> // from <type_traits>

(bool) true

%%cpp
is_function_v<decltype(do_nothing)>

(const bool) true

As shown below, an anonymous function can actually be named by assigning it to a variable. It may be better called a callable literal literally!

%%cpp
std::function<void()> simplest_callable = [](){};
simplest_callable()

std::function<void()> from <functional> specifies the type for the callable:

void is a type with an empty set of values.
void() is the signature of the callable [](){}:
- The callable returns nothing, or equivalently, has output type void, and
- it takes no arguments, i.e., has an empty parameter list ().

While we cannot declare any variables with type void (why?), we can declare a pointer to void:

%%cpp
int a=1;
void *addr=&a;
cout << format("a={} @ {}", a, addr);
// *addr    // fails as addr is not meant for dereferencing

a=1 @ 0x73df55c65000

To return a value, we can use a return statement in the compound statement at the end:

%%cpp
[]() {
    return 0;     // return statement
}
()                // called with no arguments

(int) 0

%%cpp
int zero() { return 0; }
zero()

(int) 0

Parameters can be specified before the body in parentheses:

%%cpp
[](const int x){     // one parameter
    return x>0 ? x : -x;
}
(-1.f)               // one argument passed by copy to x

(int) 1

%%cpp
double absolute(const double x) {
    return x>0 ? x : -x;
}
absolute(-1.f)

(double) 1.0000000

%%hermes
Explain briefly why it is a good practice to declare the argument `x` as
`const` if its value is not modified within the function body.

↻ Session: main (ACP: 92c90f07-348…)

Hermes

It documents intent and catches accidental bugs at compile time. const double x in absolute(const double x) (and the lambda [](const int x)) announces “this function only reads its input.” If the body later tries to reassign x, the compiler refuses:
```
error: assignment of read-only parameter 'x'
```
So a x = 1.0; that sneaks in during refactoring becomes a hard compile error instead of a silent logic bug.
It costs nothing. A const-by-value parameter changes no code generation, i.e., compiling with absolute(const double x) and absolute(double x) with -O2 generates the same assembly. In other words, the promise is free.

A callable can have multiple parameters/arguments separated by commas:

%%cpp
[](const auto a, const auto b){ // takes two arguments
    return a>b? a: b;
}
(2, 3)

(int) 3

Note that auto can be used to deduce the type for each parameter from the arguments provided to the function call. This is known as an abbreviated function template.

%%cpp
[](const auto a, const auto b){
    return a>b? a: b;
}
(2.f, 3)  // called with float and int

(float) 3.00000f

Note that the resulting type is float instead of int, according to how the conditional operator resolves its type.

%%cpp
[](const auto a, const auto b) -> double {
    if (a>b) return a;
    return b;
}
(2.f, 3)

(double) 3.0000000

If multiple return statements return values of different types, the callable may encounter errors unless the output type is explicitly specified, as shown in the code above with -> double, or the code below using function definition:

%%cpp
double maximum(const auto a, const auto b) {
    if (a>b) return a;
    return b;
}
maximum(2.f, 3)

(double) 3.0000000

Why can’t we skip the return type?

Since C++ is statically typed, all the variable types must be deduced at compile time.

Exercise 2

Why is it okay not to specify the output type for the following code using the conditional operator instead of the if statement?

[](const auto a, const auto b){
    return a>b? a: b;
}
(2.f, 3)

Solution to Exercise 2

There is only a single return statement, and therefore no ambiguity in resolving the type of the return value at compile time, even though the type of the return value still depends on the types of the input arguments.

A parameter cannot be specified as const if its value may be modified:

%%cpp
long a=2; unsigned long b=3;
[](long a, unsigned long b) { // not declared with const
    auto ans=1uL;
    while (b) {
        if (b%2) ans *= a;
        a *= a;
        b /= 2;
    }
    return ans;
} 
(a, b)

(unsigned long) 8

%%cpp
unsigned long ipow(long a, unsigned long b) {
    auto ans=1uL;
    while (b) {
        if (b%2) ans *= a;
        a *= a;
        b /= 2;
    }
    return ans;
}
ipow(a, b)

(unsigned long) 8

Solution to Exercise 3

It computes a to the non-negative integer power of b using exponentiation by squaring. However, overflow is not detected.

For instance, the global values of a and b remain unchanged even if the parameters a and b are modified in the function call.

%%cpp
cout << format("a={}, b={}\n", a, b);

a=2, b=3

Overloading¶

Can we implement the inverse square root directly using the CPU instruction SQRTSD instead of relying on the compiler?

We can use the CPU intrinsic _mm_sqrt_sd from <immintrin.h> (or the smaller <emmintrin.h>) that maps directly to the CPU instruction SQRTSD:

%%cpp
double rsqrt_(const double x) {
    return 1. / _mm_cvtsd_f64(_mm_sqrt_sd(_mm_set_sd(x), _mm_set_sd(x)));
}

@interact(x="10/3")
def print_rsqrt_(x):
    print("rsqrt({})={}".format(x:=eval(x), ROOT.rsqrt_(x)))

There is also a CPU intrinsic _mm_rsqrt_ss from <xmmintrin.h> that maps to the instruction RSQRTSS for inverse square root, but it only has single precision:

%%cpp
float rsqrt_(const float x) {
    return _mm_cvtss_f32(_mm_rsqrt_ss(_mm_set_ss(x)));
}

%%hermes
In the above code, explain briefly why it uses _mm_set_sd and _mm_cvtsd_f64?
Why _mm_sqrt_sd takes two arguments instead of one?
---
1. / _mm_cvtsd_f64(_mm_sqrt_sd(_mm_set_sd(x), _mm_set_sd(x)))

↻ Session: main (ACP: 92c90f07-348…)

Hermes

Both questions come down to one fact: the intrinsics are a thin, one-to-one reflection of the hardware SQRTSD instruction, which operates on 128-bit XMM registers, not C++ scalars.

_mm_set_sd(x) — packing the input. _mm_sqrt_sd takes __m128d (a 128-bit vector register holding two 64-bit doubles), but x is a plain C++ double. _mm_set_sd packs the scalar into the low 64 bits of an __m128d (high lane zero) so it can be handed to the intrinsic.
_mm_cvtsd_f64 — unpacking the result. Symmetrically, the intrinsic returns an __m128d vector, but rsqrt_ must return a scalar double. _mm_cvtsd_f64 extracts the low 64-bit double from the vector. The whole pipeline is: double → pack into low lane → SQRTSD on low lane → extract low lane → double.
Two arguments because SQRTSD is a two-operand instruction with a lane side-effect. SQRTSD xmm1, xmm2 does not touch the high lane of the destination register — it only writes the low 64 bits. The high lane of xmm1 simply survives as-is, whatever it was. The intrinsic mirrors that: the first argument supplies the high lane that is preserved, the second supplies the low lane that is square-rooted — result is {√(B[0]), A[1]}. I verified this on the host: _mm_sqrt_sd(a, b) with a = (low 7, high 100), b = (low 16, high 100) returned low = 4 (√16), high = 100 (kept from a), exactly matching the GCC header’s documented contract Return pair {sqrt(B[0]), A[1]}.

That’s also why the cell passes the same value twice — _mm_sqrt_sd(_mm_set_sd(x), _mm_set_sd(x)): only the low lane matters (the second argument), and since _mm_cvtsd_f64 discards the high lane anyway, the first argument’s high lane can be anything (here 0). You’re paying a small “two-register” price to exactly match a single, one-instruction CPU operation — which is the whole point of using the intrinsic over std::sqrt in this cell.

With so many possible implementations, here comes the design problem:

Should we define rsqrt_ with single precision or double precision? The user should have a say.
Should we define two versions of rsqrt_, one with single precision or double precision? It is already complicated to have different versions of square roots!

We should define two version, and we already did:

%%cpp
rsqrt_(10.f/3)

(float) 0.547729f

%%cpp
rsqrt_(10./3)

(double) 0.54772256

Observe from the output data type that C++ can call the correct version of rsqrt_ based on the argument type. We have overloaded the same function rsqrt_ with two different versions, one for double precision argument, and one for single precision.

Unlike C++, Python does not support traditional function overloading. Because Python is dynamically typed, function definitions do not include argument types, making it impossible to distinguish functions by their parameter types.^[1]

Caution

An overloaded function cannot be assigned to a variable. E.g., the following code fails

auto rsqrt_intrin = rsqrt_;

Similarly, we cannot overload a function by assigning multiple lambda expressions to the same variable. (Why?)

Encapsulation¶

Pass by Reference¶

To implement a callable that can be reused by future unseen programs, it is important to encapsulate the content properly to avoid undesirable effects contaminating other code and vice versa.

In functional programming, the function gcd is called a pure function because

its return value is identical for identical arguments; and
it has no side effects like modifying the global a and b.

In comparison, std::swap from <utility> is an example of an impure function which has the side effect of changing the values of its argument.

How to implement std::swap?

%%cpp
int a=2, b=3; // input
cout << format("a={}, b={}\n", a, b);
[](auto a, auto b) {  // arguments passed by copy
    auto c=a;
    a = b;
    b = c;
} (a, b);
cout << format("a={}, b={}\n", a, b);

a=2, b=3
a=2, b=3

Solution to Exercise 4

Only the values of the global a and b are passed to the parameters a and b in the function scope. Hence, swapping the values of the parameters have no effect on global a and b.

To fix the issue, one way is to use pointers:

%%cpp
int a=2, b=3; // input
cout << format("a={}, b={}\n", a, b);
[](auto * const a, auto * const b) {  // references passed by value
    auto c=*a;
    *a = *b;
    *b = c;
} (&a, &b);   // pass the references by copy
cout << format("a={}, b={}\n", a, b);

a=2, b=3
a=3, b=2

The arguments &a and &b, namely the references of the global a and b, are passed by copy to the constant pointer parameters a and b respectively, which then points to the global a and b.

Another way is to use the lvalue reference, which avoids the additional dereference operations:

%%cpp
int a=2, b=3;
cout << format("a={}, b={}\n", a, b);
[](auto &a, auto &b) {  // arguments passed by lvalue reference
    auto c=a;
    a=b;
    b=c;
}
(a, b);
cout << format("a={}, b={}\n", a, b);

a=2, b=3
a=3, b=2

Since the parameters are declared with auto &, the references (memory addresses) instead of the values of the global variables are passed as the references of the parameters. The parameters a and b become aliases of the global variables a and b respectively. This is called pass by reference, as supposed to pass by value.

In comparison, Python does not support pass by copy, as the argument values are not copied to the parameters:

def f(a):
    print("ID of local  a:", id(a))
    
a = 1
print("ID of global a:", id(a))
f(a)

ID of global a: 103509561833744
ID of local  a: 103509561833744

Python passes arguments to the parameters by object reference, i.e., it binds the address of the value of an argument to the corresponding parameter.

Is Python’s pass by object reference the same as C++'s pass by reference?

No. This is because a variable in Python is just a name with no persistent location. We cannot implement swap in python because the memory location is associated with the values (rvalue in C++'s term), not the variables (lvalue). Put it another way, swap(1, 2) in C++ fails because 1 and 2 are not in memory locations suitable for users to modify.

Static Variable¶

Recall that in the function rsqrt_fast defined before, constant expressions threehalfs and rel_tol are declared as static.

double rsqrt_fast(const double x) {
    ...
    static constexpr auto rel_tol=1e-9;          // initialized once only
    ...
    do {
        static constexpr auto threehalfs = 1.5;  // initialized once only
        ...
    } while (...);
    ...               
}

Why?

Like global variables, static variables are initialized only once and persist throughout the program’s execution. However, it is not visible outside the scope where it is defined.

For example, consider the following code that counts function calls:

%%cpp
unsigned int increment_count() {
    static int count=0;
    return ++count;
}

Repeatedly call the function below to observe the increase in the static variable count, even though it is initialized to 0 within the function:

%%cpp
cout << increment_count();
// count  // fails as count is out of scope

In contrast, the memory for non-static local variables is typically released when they go out of scope. For instance, without the static qualifier, the count is initialized in every function call, which is not desirable:

%%cpp
unsigned int increment_count_() {
    int count=0;
    return ++count;
}
increment_count_(); increment_count_(); increment_count_();
increment_count_()  // boring

(unsigned int) 1

Exercise 5

Recall the program for converting undecimal to decimal in Lecture 3:

unsigned long value=0;
constexpr auto m1=numeric_limits<unsigned long>::max(), m2=m1/11, m3=m1-10;
for (size_t i=0, length=strlen(s); i < length; ++i) {
    value *= value<=m2 ? 11 : throw runtime_error("The value is too big.");
    switch (unsigned char c=s[i]) {
    case 'X':
        [[fallthrough]];
    case 'x':
        value<=m3 ? value+=10 : throw runtime_error("The value is too big.");
        break;
    default:
        if ((c=s[i]-'0')>9) throw runtime_error("Invalid character found.");
        value<=m1-c? value+=c : throw runtime_error("The value is too big.");
    }
}

Define it as a function undecimal2decimal that takes s as an argument and return the value. Declare variables to be static if doing so is considered good programming practice.

%%cpp
/*
### BEGIN SOLUTION
*/
unsigned long undecimal2decimal(const char* s) {
    unsigned long value=0;
    static constexpr auto m1=numeric_limits<unsigned long>::max(), m2=m1/11, m3=m1-10;
    for (size_t i=0, length=strlen(s); i < length; ++i) {
        value *= value<=m2 ? 11 : throw runtime_error("The value is too big.");
        switch (unsigned char c=s[i]) {
        case 'X':
            [[fallthrough]];
        case 'x':
            value<=m3 ? value+=10 : throw runtime_error("The value is too big.");
            break;
        default:
            if ((c=s[i]-'0')>9) throw runtime_error("Invalid character found.");
            value<=m1-c? value+=c : throw runtime_error("The value is too big.");
        }
    }
    return value;
}
/*
### END SOLUTION
*/

Check that your function works:

@interact(s="1X2X3x")
def print_undecimal2decimal(s):
    print("Decimal value of the undecimal {} is {}.".format(s, ROOT.undecimal2decimal(s)))

Solution to Exercise 6

The use of global variables can cause conflicts if multiple functions uses global variables of the same name. E.g., a global variable specifying relative tolerances may be used by multiple functions. On the other hand, encapsulating the variables within the code that uses them makes it easier to maintain the code.

Closure¶

While it is good to declare constants as static, the use of static variables that are not constants is discouraged as it can complicate the logic of the program and cause nasty bugs. For example, declaring x2 as static in rsqrt_fast not only leads to incorrect results but can also result in infinite loops. (How?)

In more complicated scenarios, when the operating system needs to execute the program in multiple threads and pause or resume execution, static variables will not work properly:

Why non-constant static variables are discouraged even when they make a program easy to write?

Programs such as increment_count that use non-constant static variables are non-reentrant and not thread-safe.

%%hermes
Write code to illustrate the above issue.

How to avoid using static/global variables, for instance, in increment_count?

unsigned int increment_count() {
    static int count=0;
    return ++count;
}

To avoid using static/global variables, we can create a closure using the lambda expression:

%%cpp
std::function<int()> counter(int count=0) {
    return [count]() mutable {  // count captured by copy
        return ++count;
    };
}

[count] is a lambda capture that captures the value of the existing variable count by copying its value (not reference); and
mutable is a lambda specifier that allows the body of the lambda expression to modify the objects captured.

Run the following cell to create multiple counters:

%%cpp
auto counter1=counter(), counter2=counter();

Try running the following two cells repeatedly in arbitrary order to see that the counters are incremented independently.

%%cpp
counter1()  // increment counter1

(int) 2

%%cpp
counter2()   // increment counter2

(int) 1

As another example, consider the problem of computing the Fibonacci number $F_n$ of order $n\geq 0$ , which is defined as

\begin{align} F_n = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 2. \end{cases} \end{align}

(1)

Like the gcd function, we can implement it easily as a recursion:

%%cpp
unsigned long fibonacci(const unsigned long n) {
    return n>1? fibonacci(n-1) + fibonacci(n-2): n==1? 1: 0;
}
fibonacci(4)

(unsigned long) 3

The following prints the first 10 Fibonacci numbers:

%%cpp
for (auto n=0uL; n<10; n++) {
    cout << fibonacci(n) << '\n';
}

Can we define a recursion using a lambda expression?

%%cpp
std::function<unsigned long(const unsigned long)> fib=[&fib](const unsigned long n) {
    return n>1? fib(n-1) + fib(n-2): n==1? 1: 0;
};
fib(4)

(unsigned long) 3

[&fib] captures fib by reference. This is possible because fib is immediately available as we are defining it after the point of declaration!
auto would not work because the declaration is incomplete without evaluating the initializer, which relies on fib to be declared.

Solution to Exercise 7

This is because fib, while available, is uninitialized, i.e., it does not yet point to a valid function that can be captured by value.

%%cpp
/*
### BEGIN SOLUTION
*/
/*
std::function<unsigned long(unsigned long)> factorial=[&](unsigned long n) {
     return n>1? n*factorial(n-1): 1;
};
*/
auto factorial = [](unsigned long n) -> unsigned long {
    return [](auto self, unsigned long n) -> unsigned long {
        return n > 1 ? n * self(self, n - 1) : 1UL;
    }(
        [](auto self, unsigned long n) -> unsigned long {
            return n > 1 ? n * self(self, n - 1) : 1UL;
        },
        n
    );
};
/*
### END SOLUTION
*/
factorial(10) == 10*9*8*7*6*5*4*3*2*1 // for testing

(bool) true

Let’s run fibonacci for bigger orders:

%%cpp
fibonacci(20)

(unsigned long) 6765

%%cpp
fibonacci(30)

(unsigned long) 832040

%%cpp
fibonacci(40)

(unsigned long) 102334155

if input("You really want to wait? [y/N]").lower() == 'y':
    print(ROOT.fibonacci(50))       # restart the kernel to stop

You really want to wait? [y/N] y

12586269025

The following is an implementation using iteration:

%%cpp
unsigned long fibonacci_iteration(const unsigned long n) {
    if (n==0) return 0;
    if (n==1) return 1;
    auto _=0uL,   // F_{n-2}
         F=1uL,   // F_{n-1}
         tmp=F;
    for (auto i=n; i>1; i--) {
        tmp += _; // F_{n-1} + F_{n-2} mod uL_max
        _ = F;    // F_{n-1}
        F = tmp;  
        if (_>F) throw runtime_error("The value overflows.");
    }
    return F;     // F_n
}

@interact(n=(0,100))
def print_fibonacci_iteration(n):
    print("Fibonacci number of order {}: {}.".format(n, ROOT.fibonacci_iteration(n)))

Solution to Exercise 9

tmp += _ and F = tmp corresponds to assigning $F_{n-1} + F_{n-2} \mod M$ to F. When checking the condition _>F:

If there is no overflow, F takes the value of $F_{n-2} + F_{n-1}$ , which is bigger than the value $F_{n-1}$ of _, since the fibonacci sequence is strictly increasing for order larger than 1. Hence, F>_ as desired.
If there is overflow, F takes the value $F_{n-2} + F_{n-1} - M$ . Since $F_{n-2}<M$ , we have $F_{n-2} + F_{n-1} - M < F_{n-1}$ , which implies _>F as desired.

Overflow occurs when n increases from 93 to 94.

\begin{align} F_{92}&=7540113804746346429\\ F_{93}&=12200160415121876738\\ F_{94}&=19740274219868223167\\ &>18446744073709551615, \end{align}

(2)

which is the maximum value of an unsiged long.

Note that fibonacci_iteration(50) returns $F_{50}$ with no sweat!

%%cpp
fibonacci_iteration(50)

(unsigned long) 12586269025

%%cpp
cout << format("fibonacci(90)={}\n", fibonacci_iteration(90)); // no wait/way?

fibonacci(90)=2880067194370816120

fibonacci(90) is expected to be 10 billion times slower than fibonacci(40), so you have to wait for centuries to see it returns the above value!

%%cpp
/**
 * @brief Counts the number of words in a string using tail recursion.
 *
 * A word is defined as a sequence of non-whitespace characters separated by whitespace.
 * This function uses tail recursion to traverse the string and count words efficiently.
 *
 * @param s The input C-style string to be processed.
 * @param i The current index in the string (default is 0).
 * @param c The current count of words found (default is 0).
 * @param w A flag indicating whether the previous character was whitespace (default is true).
 * @return The total number of words in the string.
 */
size_t count_words(const char *s,
                   const size_t i=0, const size_t c=0, const bool w=true) {
    bool t = isspace(s[i]); // Check if the current character is a whitespace
    return s[i] ? count_words(s, i + 1, c + (w && !t), t) : c;
}

count_words("😎: Hello, World!")

(unsigned long) 3

Solution to Exercise 10

The function is a tail recursion because the function immediately returns after the recursive call count_words(s, i + 1, c + (w && !t), t).

%%cpp
auto count_words_iteration(const char* s) {
    /*
    ### BEGIN SOLUTION
    */
    auto c=0uLL;
    bool w=true;
    size_t i=0;
    while (s[i++]) {
        if (isspace(s[i])) w=true; else {
            if (w) c++;
            w=false;
        }
    }
    return c;
    /*
    ### END SOLUTION
    */
}

%%cpp
// test
if (count_words_iteration("😎: Hello, World!") != 3)
throw runtime_error("failed")

%%hermes
Explain briefly whether we can always convert a recursion to an interation.

Hermes

Yes, in principle every recursion can be converted to an iteration — but the conversion is only clean for tail recursion, and even when it always works, it is not always nice.

Why it always works: a recursive call is just “push a frame on the call stack, return later.” A stack is just data, so any recursion can be simulated iteratively by keeping the call stack explicitly (e.g., a std::stack of frames) in a for(;;) loop. I verified this mechanically: I translated the notebook’s non-tail fibonacci(n-1) + fibonacci(n-2) into such an explicit-stack loop and it returned identical values to the recursion for n = 0…15 (g++-checked: fib_stack matches fib_recursive). So computational power is not the issue — the iterative version always exists and runs in the same time, with O(depth) explicit memory.
Why it’s not always practical:
- Tail recursion (the gcd above) converts to a simple loop: the recursive call is the last action, so you just replace “call” with “update variables and repeat.” This is exactly what the lecture does with gcd and with count_words → count_words_iteration.
- Non-tail recursion (the fibonacci above) has work to do after the recursive calls return (+ fibonacci(n-2)), so the loop must save the pending state in an explicit stack. The code still works (that’s what my g++ check proved), but it is bulky and hard to read — you’ve essentially reimplemented the call stack by hand.
- Note that the lecture’s fibonacci_iteration is not this mechanical translation — it’s a rewritten algorithm that carries only the two previous values F_{n-1}, F_{n-2} as state, turning O(φⁿ) work into O(n) with O(1) memory. That kind of win requires insight, not mere conversion.

So: always possible (simulate the call stack), but only tail recursion converts to a natural loop; for other recurrences the mechanical version is ugly, and the useful iterative version is usually a different, better algorithm.

To demonstrate the issue, the following program overloads fibonacci to print the recursive calls and count them:

%%cpp
unsigned long fibonacci(const unsigned long n, const int verbosity) {
    static auto count=0uL, depth=-1uL;
    depth+=1;
    if (!depth) count=0;
    count+=1;
    if (verbosity>1) {
        for (auto i=depth; i>0; i--) cout << '|';
        cout << format("fibonacci({})\n", n);
    }
    auto value = n>1? fibonacci(n-1,verbosity)+fibonacci(n-2,verbosity): n==1?1:0;
    if (!depth && verbosity>0) cout << format("Total number of calls: {}\n", count);
    depth-=1;
    return value;
}

With verbosity level 2, the function calls and the total number of calls are printed:

%%cpp
fibonacci(0, 2)

fibonacci(0)
Total number of calls: 1
(unsigned long) 0

%%cpp
fibonacci(1, 2)

fibonacci(1)
Total number of calls: 1
(unsigned long) 1

%%cpp
fibonacci(2, 2)

fibonacci(2)
|fibonacci(1)
|fibonacci(0)
Total number of calls: 3
(unsigned long) 1

%%cpp
fibonacci(3, 2)

fibonacci(3)
|fibonacci(2)
||fibonacci(1)
||fibonacci(0)
|fibonacci(1)
Total number of calls: 5
(unsigned long) 2

%%cpp
fibonacci(4, 2)

fibonacci(4)
|fibonacci(3)
||fibonacci(2)
|||fibonacci(1)
|||fibonacci(0)
||fibonacci(1)
|fibonacci(2)
||fibonacci(1)
||fibonacci(0)
Total number of calls: 9
(unsigned long) 3

The depth of a recursive call is denoted by the number of bars |. Observe the redundant computations of the lower order Fibonacci numbers.

To see the total number of calls for larger orders, use the verbosity level 1 to print only the count, not the calls:

%%cpp
fibonacci(30, 1)

Total number of calls: 2692537
(unsigned long) 832040

The number of calls in computing $F_n$ can be shown to be $2F_{n+1}-1$ :

%%cpp
2*fibonacci(31)-1

(unsigned long) 2692537

It can be shown that the Fibonacci number grows exponentially as $F_n\approx \frac{\phi^n}{\sqrt{5}}$ , so does the count. This explains the exponentially long wait mentioned before.

Solution to Exercise 12

Cache the values of previously computed Fibonacci numbers, e.g., using std::unordered_map.

But the more important question for now is:

%%cpp
unsigned long fibonacci(const unsigned long n, const int verbosity) {
    auto count=0uL, depth=-1uL;
    /*
    ### BEGIN SOLUTION
    */
    std::function<unsigned long(const unsigned long)> fib = [&](const unsigned long n) {
        depth+=1;
        count+=1;
        if (verbosity>1) {
            for (auto i=depth; i>0; i--) cout << '|';
            cout << format("fibonacci({})\n", n);
        }
        auto value = n>1? fib(n-1)+fib(n-2): n==1?1:0;
        if (!depth && verbosity>0) cout << format("Total number of calls: {}\n", count);
        depth-=1;
        return value;
    };
    return fib(n);
    /*
    ### END SOLUTION
    */
}
fibonacci(4, 2)  // for testing

fibonacci(4)
|fibonacci(3)
||fibonacci(2)
|||fibonacci(1)
|||fibonacci(0)
||fibonacci(1)
|fibonacci(2)
||fibonacci(1)
||fibonacci(0)
Total number of calls: 9
(unsigned long) 3

Decorator¶

Can we enhance a function to print function calls without modifying the source code of the function?

We can define a print_call that takes a function as an argument and return the function but decorated with the enhancement to print calls:

We can make use of the following decorator:

/**
 * @brief Decorates a unary function and logs each invocation with indentation based on call depth.
 *        Also counts the total number of possibly recursive calls.
 *
 * @tparam f A callable object (e.g., lambda or function) that takes a single argument.
 * @param name A string literal representing the name of the function being wrapped.
 * @return A lambda that logs the function call, tracks depth and count, and returns the result of f(n).
 */
auto print_call(auto f, const char *name) {
    // Initialize call count and depth tracking
    auto count = 0uL;     // Total number of calls
    auto depth = -1uL;    // Current depth of recursion

    // Return a lambda that wraps the original function
    return auto n mutable {
        depth += 1;       // Entering a new call level

        // Reset count at the top level
        if (!depth) count = 0;
        count += 1;

        // Print indentation based on depth
        for (auto i = depth; i > 0; i--) std::cout << '|';

        // Log the function call with its argument
        cout << name << "(" << n << ")\n";

        // Call the original function and store the result
        auto output = f(n);

        // If returning from top-level call, print total call count
        if (!depth) cout << "Total number of calls: " << count << "\n";

        depth -= 1;       // Exiting the current call level
        return output;
    };
}

Program 2:A decorator that prints and counts recursive calls to a function.

%%cpp
auto print_call(auto f, const char *name) {
    auto count=0uL, depth=-1uL;
    return [count, depth, f, name](auto n) mutable {
        depth+=1;
        if (!depth) count=0;
        count+=1;
        for (auto i=depth; i>0; i--) cout << '|';
        cout << name << "(" << n << ")\n";
        auto output = f(n);
        if (!depth) cout << "Total number of calls: " << count << "\n";
        depth-=1;
        return output;
    };
}

Recall the recursion for computing Fibonacci sequence:

%%cpp
std::function<unsigned long(const unsigned long)> fib=[&fib](const unsigned long n) {
    return n>1? fib(n-1) + fib(n-2): n==1? 1: 0;
};
auto fib0=fib;   // backup for later use
fib(5)

(unsigned long) 5

To apply the decorator to fib:

%%cpp
fib=print_call(fib0, "fib");
fib(5)

fib(5)
|fib(4)
||fib(3)
|||fib(2)
||||fib(1)
||||fib(0)
|||fib(1)
||fib(2)
|||fib(1)
|||fib(0)
|fib(3)
||fib(2)
|||fib(1)
|||fib(0)
||fib(1)
Total number of calls: 15
(unsigned long) 5

To recover the original function:

%%cpp
fib=fib0;
fib(5)

(unsigned long) 5

Decorator is a design pattern, i.e., a reusable solution to a common software development problem. It amplifies code reuse by adding or removing enhancements easily to an object without modifying the source code of the original object. To understand how print_call works in greater details, you can step through the execution of the following Python counterpart:

%%pytutor
import functools
def print_call(f):
    count, depth = 0, -1
    @functools.wraps(f)
    def wrapper(n):
        nonlocal count, depth
        depth+=1
        if not depth: count=0
        count+=1
        for i in range(depth): print('|', end='');
        print(f"{f.__name__}({n})")
        output = f(n)
        if not depth: print(f"Total number of calls: {count}")
        depth-=1
        return output
    return wrapper
@print_call
def fib(n):
    return fib(n-1)+fib(n-2) if n>1 else 1 if n==1 else 0
fib(3)

The history saving thread hit an unexpected error (OperationalError('attempt to write a readonly database')).History will not be written to the database.

Exercise 14

Why does the following code fail to decorate the function fibonacci:

unsigned long fibonacci(const unsigned long n) {
    return n>1? fibonacci(n-1) + fibonacci(n-2): n==1? 1: 0;
}

fibonacci=print_call(fibonacci, "fib");
fibonacci(5)

Solution to Exercise 14

This is because fibonacci declared using the function declaration is not an assignable variable/object.

A limitation of print_call is that it does not decorate functions with more than one argument. To fix this, we will need to know how to define a function that takes a variable number of arguments:

%%hermes
How to define a function that takes a variable number of arguments in C++?

Hermes

In C++ there are four standard ways, each with a different tradeoff:

Variadic templates (the C++11+ idiom — type-safe, and what you actually want): a parameter pack typename... Ts followed by a fold expression to consume it:
```
template <typename... Ts>
auto sum(const Ts&... xs) { return (xs + ...); }  // sum(1, 2.5, 3) → 6.5
```
Generic lambda with a pack (C++14) — same idea without a named template, and it’s what fits this notebook’s style:
```
auto add = [](auto... xs) { return (xs + ...); };  // add(1, 2, 3) → 6
```
C-style ... (what printf uses): void log(const char* fmt, ...) + va_list/va_start/va_end (<cstdarg>). It works with any count but is not type-checked — I verified log("%s", 42) compiles fine and then segfaults, which is exactly why it’s legacy.
std::initializer_list<T> — variable count but one fixed element type: void print(const std::initializer_list<double> xs) called as print({1, 2, 3}).

And the direct fix for the limitation noted in the cell just above: the notebook’s print_call hard-codes a single auto n parameter, so to decorate functions with any number of arguments, replace it with a pack:

auto print_call(auto f, const char* name) {
    auto count = 0uL;
    return [count, f, name](auto... args) mutable {  // pack, not (auto n)
        count += 1;
        cout << format("{} called (#{})\n", name, count);
        auto output = f(args...);                     // pack EXPANDED at the call
        return output;
    };
};

Two gotchas worth knowing:

The pack must be expanded with ... exactly once per use. Forgetting it is a hard compile error — return f(args); fails with error: parameter packs not expanded with '...' (g++ 15.2, verified above).
A function template can’t be passed to print_call — the same deduction failure as in ex:decorator (candidate template<auto:12> auto print_call(auto:12, const char*), couldn't deduce template parameter). Wrap the call target in a lambda (or std::function), as the cells above do — that’s why the multi-arg version I verified passes [](auto... xs){ return (xs+...); } rather than sum itself.

So the one-liner: prefer parameter packs (auto... / typename... Ts + a fold expression) over C-style ..., and expand the pack (f(args...)) wherever you use it.

Modularization¶

How to use a function you define in a file? The simplest way is to write the code that uses the function in the same file that defines it:

%%writefile private/rsqrt.cpp
#include <cmath>
#include <iostream>
#include <format>

inline double rsqrt(const double x) {
    return 1./std::sqrt(x);
}

using std::cout, std::format;

int main() {
    double x = 10./3;
    cout << format("rsqrt({})={}.\n", x, rsqrt(x));
    return 0;
}

Overwriting private/rsqrt.cpp

!clang++ -fuse-ld=lld --std=c++23 --stdlib=libc++ -O2 -ffast-math private/rsqrt.cpp -o private/rsqrt && private/rsqrt

rsqrt(3.3333333333333335)=0.5477225575051661.

inline is a function specifier that suggests to the compiler that it can perform optimizations such as inlining. Inlining involves replacing function calls with the function’s code directly at the call site, which can reduce function call overhead and improve performance, especially for small functions.

We can also separate the function declaration from its definition:

%%writefile private/rsqrt.cpp
#include <cmath>
#include <iostream>
#include <format>

using std::cout, std::format;

int main() {
    double rsqrt(const double x);   // rsqrt available in block scope, but inline not allowed
    double x = 10./3;
    cout << format("rsqrt({})={}.\n", x, rsqrt(x));
    return 0;
}

inline double rsqrt(const double x) {
    return 1./std::sqrt(x);
}

Overwriting private/rsqrt.cpp

!clang++ -fuse-ld=lld --std=c++23 --stdlib=libc++ -O2 -ffast-math private/rsqrt.cpp -o private/rsqrt && private/rsqrt

rsqrt(3.3333333333333335)=0.5477225575051661.

The above attempts to encapsulate rsqrt within the block scope of main, making it easier to maintain. However, the inline declaration is only allowed in namespace scope, not block scope. If multiple programs need to access rsqrt, we can use a custom header file rsqrt.hpp as shown below, to be included in other files that use it:

%%writefile private/rsqrt.hpp
#pragma once  // Non-standard pragma to ensure the header is only parsed once.
#include <cmath>

inline double rsqrt(const double x) {
    return 1./std::sqrt(x);
}

Writing private/rsqrt.hpp

%%writefile private/main.cpp
#include <iostream>
#include <format>
#include "rsqrt.hpp"

using std::cout, std::format;

int main() {
    double x = 10./3;
    cout << format("rsqrt({})={}.\n", x, rsqrt(x));
    return 0;
}

Writing private/main.cpp

!clang++ -fuse-ld=lld --std=c++23 --stdlib=libc++ -O2 -ffast-math private/main.cpp -o private/main && private/main

rsqrt(3.3333333333333335)=0.5477225575051661.

rsqrt.hpp is a header file included in main.cpp using the quote form as opposed to the angular form:

Headers included in the quote form such as #include "rsqrt.hpp" tells the compiler to search in the current directory before the system directories.
Headers included using the angular bracket form such as #include <format> tells the compiler to search only in the system include directories as they are not defined in the current project.

%%hermes
What happens if a header file is included more than once? Is it possible to have
a cyclic inclusion of header files? E.g., what if `rsqrt.hpp` includes itself?

Hermes

The core idea: #include is “paste this file’s text here”. The preprocessor doesn’t do anything clever — including a file twice just pastes its contents twice. So whether a repeated include is a problem depends entirely on what’s in the file and whether it’s guarded. Assuming there are no guards.

Included more than once

Without a guard → redefinition compile errors, for everything the file defines.

Cyclic / self-inclusion

Without guards → infinite expansion → compile error. The preprocessor keeps re-entering the same file until it hits its include-depth limit and/or emits the definitions repeatedly. A guardless self-include produced, among a long In file included from … chain of the same file:

...: error: redefinition of ...

A self-include that contained only an #include and no definition would instead die on the preprocessor’s “too many levels of recursion” depth limit — same failure, different message.

#pragma once in the first line of rsqrt.hpp ensures that the header is parsed only once even if the header is included multiple times in a single compilation. However, since #pragma once is not part of the C++ standard, it may not be supported by older compilers. Whether it works also relies on the compiler’s ability to detect file identity. A more conservative alternative is to use an include guard such as

#ifndef RSQRT_HPP
#define RSQRT_HPP
...
#endif // RSQRT_HPP

where the macro RSQRT_HPP should be chosen as specific as possible to indicate that the content of rsqrt.hpp has been included.

%%writefile private/rsqrt.hpp
#ifndef RSQRT_HPP
#define RSQRT_HPP
#include <cmath>

inline double rsqrt(const double x) {
    return 1./std::sqrt(x);
}
#endif // macro RSQRT_HPP to indicate whether the header has been included

Overwriting private/rsqrt.hpp

!clang++ --std=c++23 --stdlib=libc++ -O2 -ffast-math private/main.cpp -o private/main && private/main

rsqrt(3.3333333333333335)=0.5477225575051661.

rsqrt.hpp is also known as a header-only library because all implementations are included in the header file. For more complex implementations that can benefit from pre-compilation, the implementations can be placed in a separate source file. Consider the following modified header file:

%%writefile private/rsqrt.hpp
#include <cmath>

inline double rsqrt(const double x) {
    return 1./std::sqrt(x);
}

namespace intrin {
double rsqrt(const double x);
float rsqrt(const float x);
} // namespace intrin to avoid name conflicts

Overwriting private/rsqrt.hpp

The header file

defines inline double rsqrt(const double x) as before, and
declares but not defines double rsqrt(const double x) and float rsqrt(const float x).

The declaration without inline specifiers are grouped under a custom namespace called intrin to avoid name conflict with the inline version of rsqrt.

To implement the overloaded intrin::rsqrt function in a separate source file:

%%writefile private/rsqrt.cpp
#include "rsqrt.hpp"     // optional but strongly prefered
#include <immintrin.h>    

namespace intrin {
// inline is unnecssary for definitions not in a header file
double rsqrt(const double x) {
    return 1. / _mm_cvtsd_f64(_mm_sqrt_sd(_mm_set_sd(x), _mm_set_sd(x)));
}

float rsqrt(const float x) {
    return _mm_cvtss_f32(_mm_rsqrt_ss(_mm_set_ss(x)));
}
} // namespace mymath

Overwriting private/rsqrt.cpp

%%hermes
Why including the header file (e.g., rsqrt.hpp) in the implementation source file 
(e.g., rsqrt.cpp) that defines the function is strongly preferred in C++?

Hermes

The notebook’s rsqrt.cpp opens with:

#include "rsqrt.hpp"     // optional but strongly prefered

It’s “optional” because rsqrt.cpp’s intrin::rsqrt definitions are self-contained — they name their own parameters and return types, so the .cpp compiles fine even without seeing the header. It’s “strongly preferred” because including your own header is the only way to make the compiler check that your definition actually matches your declaration. That’s the whole point.

Why it matters?

The definition must match the declaration, and only the compiler can prove that

rsqrt.hpp is the interface (it declares intrin::rsqrt(const double) and intrin::rsqrt(const float)); rsqrt.cpp is the implementation. For the program to be correct, every definition in the .cpp must agree, exactly, with the matching declaration in the header. If the .cpp includes the header, the declaration is in scope at the moment the definition is written, so the compiler cross-checks them at compile time. If it doesn’t, the definition is just a brand-new declaration as far as that translation unit is concerned — nothing compares it to the header, and a mismatch slips through.

To demonstrate the dangerous case directly, consider having the header saying float rsqrt(const float x):

.cpp does NOT include the header, but defines int rsqrt(const float x) (return type drifted float → int):
```
.cpp compiled OK (no error!)
LINKED OK
```
It builds and runs with zero diagnostics — but main (which trusts the header) gets an int where it expects a float. Return type is not part of C++ name mangling, so the symbol still matches and the linker has nothing to complain about. This is a silent, corrupting bug that the header include would have prevented.
.cpp DOES include the header, same int rsqrt(const float x) drift → compile error:
```
bad5.cpp:4:8: error: ambiguating new declaration of ‘int intrin::rsqrt(float)’
rsqrt.hpp:4:8: note: old declaration ‘float intrin::rsqrt(float)’
```
The compiler now sees both the old declaration and the new definition in scope and rejects the conflict immediately, at the right place, before anything links.

Other kinds of drift behave the same way — caught at compile time when the header is included, and at best as an undefined reference at link time when it isn’t. (A namespace typo, e.g. defining intrint::rsqrt instead of intrin::rsqrt, is exactly this: without the header the .cpp compiles and you only fail at link with undefined reference to 'intrin::rsqrt(...)'; including the header keeps the real names in view so that class of mistake is far harder to make.)

Are there other benefits?

Single source of truth. The header is the contract; the .cpp including it says “I am implementing this contract.” If someone edits a signature in rsqrt.hpp, the next build of rsqrt.cpp immediately errors if the implementation wasn’t updated. Without the include, the two can silently diverge.
Self-sufficiency / self-documentation. A reader of rsqrt.cpp sees, in the first line, which interface it belongs to, and the .cpp picks up the header’s own prerequisites transitively.
Costs essentially nothing. It’s one #include; the header is #pragma once-guarded (as established in the cell above), so re-including it inside the .cpp is a no-op, not a redefinition.

So the inclusion is “optional” only in the narrow sense that these particular definitions don’t reference the inline rsqrt — but it’s “strongly preferred” because it’s the difference between the compiler verifying your implementation against your interface and the linker (or, worse, the CPU) finding out for you later.

To use the rsqrt’s in a program:

%%writefile private/main.cpp
#include <iostream>
#include <format>
#include "rsqrt.hpp"

using std::cout, std::format;

int main() {
    double x = 10./3;
    float x_ = static_cast<float>(x);
    cout << format("rsqrt({})={}.\n", x, rsqrt(x));
    cout << format("intrin::rsqrt({})={}.\n", x, intrin::rsqrt(x));
    cout << format("intrin::rsqrt({}f)={}f.\n", x_, intrin::rsqrt(x_));
    return 0;
}

Overwriting private/main.cpp

!clang++ -fuse-ld=lld --std=c++23 --stdlib=libc++ -O2 -ffast-math private/main.cpp private/rsqrt.cpp -o private/main && private/main

rsqrt(3.3333333333333335)=0.5477225575051661.
intrin::rsqrt(3.3333333333333335)=0.5477225575051661.
intrin::rsqrt(3.3333333f)=0.5477295f.

To share the library between multiple programs, we can first compile rsqrt to a dynamic library:

!clang++ -v -fuse-ld=lld -fPIC -shared --std=c++23 --stdlib=libc++ -O2 -ffast-math private/rsqrt.cpp -o private/librsqrt.so

Ubuntu clang version 22.1.8 (++20260714015917+ca7933e47d3a-1~exp1~20260714135927.17)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-22/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/14
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/15
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/15
Candidate multilib: .;@m64
Selected multilib: .;@m64
 "/usr/lib/llvm-22/bin/clang" -cc1 -triple x86_64-pc-linux-gnu -O2 -emit-obj -dumpdir private/librsqrt.so- -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name rsqrt.cpp -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -menable-no-infs -menable-no-nans -fapprox-func -funsafe-math-optimizations -fno-signed-zeros -mreassociate -freciprocal-math -ffp-contract=fast -fno-rounding-math -ffast-math -ffinite-math-only -complex-range=basic -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/jovyan/cs2310i26a/source/Lecture4-5 -v -fcoverage-compilation-dir=/home/jovyan/cs2310i26a/source/Lecture4-5 -resource-dir /usr/lib/llvm-22/lib/clang/22 -internal-isystem /usr/lib/llvm-22/bin/../include/c++/v1 -internal-isystem /usr/lib/llvm-22/lib/clang/22/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include --std=c++23 -fdeprecated-macro -ferror-limit 19 -fmessage-length=80 -fgnuc-version=4.2.1 -fno-implicit-modules -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -fdwarf2-cfi-asm -o /tmp/rsqrt-32b749.o -x c++ private/rsqrt.cpp
clang -cc1 version 22.1.8 based upon LLVM 22.1.8 default target x86_64-pc-linux-gnu
ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/15/../../../../x86_64-linux-gnu/include"
ignoring nonexistent directory "/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/lib/llvm-22/bin/../include/c++/v1
 /usr/lib/llvm-22/lib/clang/22/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
 "/usr/lib/llvm-22/bin/ld.lld" -z relro --hash-style=gnu --build-id --eh-frame-hdr -m elf_x86_64 -shared -o private/librsqrt.so /lib/x86_64-linux-gnu/crti.o /usr/lib/gcc/x86_64-linux-gnu/15/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/15 -L/usr/lib/gcc/x86_64-linux-gnu/15/../../../../lib64 -L/lib/x86_64-linux-gnu -L/lib/../lib64 -L/usr/lib/x86_64-linux-gnu -L/usr/lib64 -L/usr/lib/llvm-22/bin/../lib -L/lib -L/usr/lib /tmp/rsqrt-32b749.o -lc++ -lm -lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-linux-gnu/15/crtendS.o /lib/x86_64-linux-gnu/crtn.o

To compile and link main.cpp with librsqrt.so:

!clang++ -v -fuse-ld=lld --std=c++23 --stdlib=libc++ -O2 private/main.cpp -L private -l rsqrt -o private/main_

Ubuntu clang version 22.1.8 (++20260714015917+ca7933e47d3a-1~exp1~20260714135927.17)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-22/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/14
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/15
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/15
Candidate multilib: .;@m64
Selected multilib: .;@m64
 "/usr/lib/llvm-22/bin/clang" -cc1 -triple x86_64-pc-linux-gnu -O2 -emit-obj -dumpdir private/main_- -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name main.cpp -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/jovyan/cs2310i26a/source/Lecture4-5 -v -fcoverage-compilation-dir=/home/jovyan/cs2310i26a/source/Lecture4-5 -resource-dir /usr/lib/llvm-22/lib/clang/22 -internal-isystem /usr/lib/llvm-22/bin/../include/c++/v1 -internal-isystem /usr/lib/llvm-22/lib/clang/22/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include --std=c++23 -fdeprecated-macro -ferror-limit 19 -fmessage-length=80 -fgnuc-version=4.2.1 -fno-implicit-modules -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -fdwarf2-cfi-asm -o /tmp/main-b9ebf9.o -x c++ private/main.cpp
clang -cc1 version 22.1.8 based upon LLVM 22.1.8 default target x86_64-pc-linux-gnu
ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/15/../../../../x86_64-linux-gnu/include"
ignoring nonexistent directory "/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/lib/llvm-22/bin/../include/c++/v1
 /usr/lib/llvm-22/lib/clang/22/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
 "/usr/lib/llvm-22/bin/ld.lld" -z relro --hash-style=gnu --build-id --eh-frame-hdr -m elf_x86_64 -pie -dynamic-linker /lib64/ld-linux-x86-64.so.2 -o private/main_ /lib/x86_64-linux-gnu/Scrt1.o /lib/x86_64-linux-gnu/crti.o /usr/lib/gcc/x86_64-linux-gnu/15/crtbeginS.o -Lprivate -L/usr/lib/gcc/x86_64-linux-gnu/15 -L/usr/lib/gcc/x86_64-linux-gnu/15/../../../../lib64 -L/lib/x86_64-linux-gnu -L/lib/../lib64 -L/usr/lib/x86_64-linux-gnu -L/usr/lib64 -L/usr/lib/llvm-22/bin/../lib -L/lib -L/usr/lib /tmp/main-b9ebf9.o -lrsqrt -lc++ -lm -lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-linux-gnu/15/crtendS.o /lib/x86_64-linux-gnu/crtn.o

To run the program, we need to include the folder private in the linker search path for dynamic libraries. This can be done using the compiler flag -L or by prepending the folder to the environment variable LD_LIBRARY_PATH:

!LD_LIBRARY_PATH=private:$LD_LIBRARY_PATH private/main_

rsqrt(3.3333333333333335)=0.5477225575051661.
intrin::rsqrt(3.3333333333333335)=0.5477225575051661.
intrin::rsqrt(3.3333333f)=0.5477295f.

Observe that the executable private/main_ relying on private/librsqrt.so is smaller in size than the standalone executable private/main.

!ls -l private/main private/main_ private/librsqrt.so

-rwxr-xr-x 1 jovyan users   5568 Sep 19 15:00 private/librsqrt.so
-rwxr-xr-x 1 jovyan users 106096 Sep 19 15:00 private/main
-rwxr-xr-x 1 jovyan users 105192 Sep 19 15:01 private/main_

Solution to Exercise 15

There are two headers in the include folder. include/mymath.hpp declares:

the add functions implemented in mymath/add.cpp, and
the mul functions implemented in mymath/mul.cpp.

These functions are compiled into a dynamic library located at lib/libmymath.so, which is linked to the executable bin/addmul.

include/util.hpp declares the input_int function implemented in util/io.cpp. This function is compiled into a static library located at bin/libutil.a and included as part of the executable bin/addmul.

Footnotes¶

Python allows operator overloading using type-based dispatch instead.
↩