1.2 Comparing and contrasting procedural and functional styles

1.2.1 Using the functional paradigm

In a functional sense, the sum of the multiples of 3 and 5 can be decomposed into two parts:

• The sum of a sequence of numbers

• A sequence of values that pass a simple test condition, for example, being multiples of 3 and 5

To be super formal, we can define the sum as a function using simpler language components. The sum of a sequence has a recursive definition:

from collections.abc import Sequence 
def sumr(seq : Sequence[int]) -> int: 
    if len(seq) == 0: 
        return 0 
    return seq[0] + sumr(seq[1:])

We’ve defined the sum in two cases. The base case states that the sum of a zero-length sequence is 0. The recursive case states that the sum of a sequence is the first value plus the sum of the rest of the sequence. Since the recursive definition depends on a shorter sequence, we can be sure that it will (eventually) devolve to the base case.

Here are some examples of how this function works:

>>> sumr([7, 11]) 
18 
>>> sumr([11]) 
11 
>>> sumr([]) 
0

The first example computes the sum of a list with multiple items. The second example shows how the recursion rule works by adding the first item, seq[0], to the sum of the remaining items, sumr(seq[1:]). Eventually, the computation of the result involves the sum of an empty list, which is defined as 0.

The + operator on the last line of the sumr function and the initial value of 0 in the base case characterize the equation as a sum. Consider what would happen if we changed the operator to * and the initial value to 1: this new expression would compute a product. We’ll return to this simple idea of generalization in the following chapters.

Similarly, generating a sequence of values with a given property can have a recursive definition, as follows:

from collections.abc import Sequence, Callable 
def until( 
        limit: int, 
        filter_func: Callable[[int], bool], 
        v: int 
) -> list[int]: 
    if v == limit: 
        return [] 
    elif filter_func(v): 
        return [v] + until(limit, filter_func, v + 1) 
    else: 
        return until(limit, filter_func, v + 1)

In this function, we’ve compared a given value, v, against the upper bound, limit. If v has reached the upper bound, the resulting list must be empty. This is the base case for the given recursion.

There are two more cases defined by an externally defined filter_func() function. The value of v is passed by the filter_func() function; if this returns a very small list, containing one element, this can be concatenated with any remaining values computed by the until() function.

If the value of v is rejected by the filter_func() function, this value is ignored and the result is simply defined by any remaining values computed by the until() function.

We can see that the value of v will increase from an initial value until it reaches limit, assuring us that we’ll reach the base case.

Before we can see how to use the until() function, we’ll define a small function to filter values that are multiples of 3 or 5:

def mult_3_5(x: int) -> bool: 
    return x % 3 == 0 or x % 5 == 0

We could also have defined this as a lambda object to emphasize succinct definitions of simple functions. Anything more complex than a one-line expression requires the def statement.

This function can be combined with the until() function to generate a sequence of values, which are multiples of 3 and 5. Here’s an example:

>>> until(10, mult_3_5, 0) 
[0, 3, 5, 6, 9]

Looking back at the decomposition at the top of this section, we now have a way to compute sums and a way to compute the sequence of values.

We can combine the sumr() and until() functions to compute a sum of values. Here’s the resulting code:

def sum_functional(limit: int = 10) -> int: 
    return sumr(until(limit, mult_3_5, 0))

This small application to compute a sum doesn’t make use of the assignment statement to set the values of variables. It is a purely functional, recursive definition that matches the mathematical abstractions, making it easier to reason about. We can be confident each piece works separately, giving confidence in the whole.

As a practical matter, we’ll use a number of Python features to simplify creating functional programs. We’ll take a look at a number of these optimizations in the next version of this example.

1.2.2 Using a functional hybrid

We’ll continue this example with a mostly functional version of the previous example to compute the sum of multiples of 3 and 5. Our hybrid functional version might look like the following:

def sum_hybrid(limit: int = 10) -> int: 
    return sum( 
        n for n in range(1, limit) 
        if n % 3 == 0 or n % 5 == 0 
    )

We’ve used a generator expression to iterate through a collection of values and compute the sum of these values. The range(1, 10) object is an iterable; it generates a sequence of values {n∣1 ≤ n < 10}, often summarized as “values of n such that 1 is less than or equal to n and n is less than 10.” The more complex expression n for n in range(1, 10) if n % 3 == 0 or n % 5 == 0 is also a generator. It produces a set of values, {n∣1 ≤ n < 10 ∧ (n ≡ 0 mod 3 ∨n ≡ 0 mod 5)}; something we can describe as “values of n such that 1 is less than or equal to n and n is less than 10 and n is equivalent to 0 modulo 3 or n is equivalent to 0 modulo 5.” These are multiples of 3 and 5 taken from the set of values between 1 and 10. The variable n is bound, in turn, to each of the values provided by the range object. The sum() function consumes the iterable values, creating a final object, 23.

The variable n in this example isn’t directly comparable to the variable n in the first two imperative examples. A for statement (outside a generator expression) creates a proper variable in the local namespace. The generator expression does not create a variable in the same way that a for statement does:

>>> sum( 
...     n for n in range(1, 10) 
...     if n % 3 == 0 or n % 5 == 0 
... ) 
23 
>>> n 
Traceback (most recent call last): 
   File "<stdin>", line 1, in <module> 
NameError: name ’n’ is not defined

The generator expression doesn’t pollute the namespace with variables, like n, which aren’t relevant outside the very narrow context of the expression. This is a pleasant feature that ensures we won’t be confused by the values of variables that don’t have a meaning outside a single expression.

1.2.3 The stack of turtles

When we use Python for functional programming, we embark down a path that will involve a hybrid that’s not strictly functional. Python is not Haskell, OCaml, or Erlang. For that matter, our underlying processor hardware is not functional; it’s not even strictly object-oriented, as CPUs are generally procedural.

All programming languages rest on abstractions, libraries, frameworks and virtual machines. These abstractions, in turn, may rely on other abstractions, libraries, frameworks and virtual machines. The most apt metaphor is this: the world is carried on the back of a giant turtle. The turtle stands on the back of another giant turtle. And that turtle, in turn, is standing on the back of yet another turtle.

It’s turtles all the way down.

— Anonymous

There’s no practical end to the layers of abstractions. Even something as concrete as circuits and electronics may be an abstraction to help designers summarize the details of quantum electrodynamics.

More importantly, the presence of abstractions and virtual machines doesn’t materially change our approach to designing software to exploit the functional programming features of Python.

Even within the functional programming community, there are both purer and less pure functional programming languages. Some languages make extensive use of monads to handle stateful things such as file system input and output. Other languages rely on a hybridized environment that’s similar to the way we use Python. In Python, software can be generally functional, with carefully chosen procedural exceptions.

Our functional Python programs will rely on the following three stacks of abstractions:

• Our applications will be functions—all the way down—until we hit the objects;

• The underlying Python runtime environment that supports our functional programming is objects—all the way down—until we hit the libraries;

• The libraries that support Python are a turtle on which Python stands.

The operating system and hardware form their own stack of turtles. These details aren’t relevant to the problems we’re going to solve.