Abstracting over Computation

In object-oriented programming, methods (functions associated with classes or objects) are often considered "second-class citizens" because they are not as flexible as first-class functions. They cannot be passed around as arguments or stored independently in data structures. Instead, they are tied to the objects or classes they belong to, much like how verbs are tied to the nouns they describe.

Python, however, supports the concept of first-class functions. This means that functions in Python are treated as objects. You can assign them to variables, store them in data structures, pass them as arguments to other functions, and even return them as values from other functions. This provides a lot of flexibility and power.

Here's an example of how you might use a first-class function in Python:

def greet(name):
    return f"Hello, {name}!"

def process(func, argument):
    return func(argument)

print(process(greet, "Alice"))  # prints "Hello, Alice!"

In this example, the greet function is passed as an argument to the process function, demonstrating the concept of first-class functions.

This flexibility allows for powerful programming paradigms such as functional programming, where functions can be used to create abstract computations that can be combined in flexible ways. This is different from the object-oriented paradigm, where the focus is more on the objects and their interactions. Both paradigms have their strengths and can often be used together effectively in Python.

First-Class Functions

def repeat(action:callable, n:int):
    for _ in range(n):
        action()
repeat(do_something,10)

The authors suggest that instead of writing a loop each time, the logic can be factored into a function that takes two arguments: a function to be executed and the number of times the function should be executed. The function is defined as repeat() and takes two arguments: action (a function) and n (an integer). The function then uses a for loop to execute the action function n times.

The authors provide an example of how to use the repeat() function by passing a function called do_something and the integer value 10 as arguments. This will execute the do_something function 10 times.

The authors use the concept of higher-order functions, where a function can take another function as an argument, to simplify the code and make it more modular. The use of higher-order functions is a common technique in functional programming.

The notation used in the code snippet includes the use of the range() function, which generates a sequence of numbers from 0 up to (but not including) the specified number. The notation for the repeat() function includes the use of the Callable type hint, which specifies that the action argument should be a function.

Lambdas

A lambda expression is a function literal that allows us to write a function without giving it a name.Lambdas are great for functions whose bodies are short expressions, but if multiple statements are needed in a function, a named function using "def" must be used instead.

The syntax of the lambda expression is as follows:

lambda argument: expression

expected_value(coin_flip, lambda coin: 1.0 if coin == ”heads” else 0.0)

the argument is "coin" and the expression is "1.0 if coin == 'heads' else 0.0".

Iterative Algorithms

Iterative algorithms converge to the correct result by repeatedly running the algorithm and making smaller and smaller improvements with each iteration. The example given is the approximation of the square root of a number, where the initial guess is repeatedly refined using the 🎉

def sqrt(a: float) -> float:
     x = a / 2 # initial guess
     x_n = a
     while abs(x_n - x) > 0.01:
        x = x_n
        x_n = (x + (a / x)) / 2
     return x_n

A common issue with iterative algorithms is deciding when to stop iterating. In the given square root example, the algorithm stops when the change between the current guess and the next guess is less than 0.01. But this hard-coded value might not always be appropriate.

A proposed solution is to allow the caller to specify the precision as an argument to the function.

def sqrt(a: float, threshold: float) -> float:
    x = a / 2 # initial guess
    x_n = a
    while abs(x_n - x) > threshold:
        x = x_n
        x_n = (x + (a / x)) / 2
    return x_n

This provides more control to the caller but still isn't perfect. If the function takes too long to reach the desired precision, the caller might want to stop early, which isn't possible with this approach.

Iterators and Generators

Iterators and Generators: Iterators and generators in Python allow us to handle sequences of data in a memory-efficient way. They can be used to abstract the process of iteration, separating the production of values from their consumption.

Python's for Loop and Iterators: Python's for loop uses an iterator under the hood. This is why the for loop works with different types of sequences like lists, dictionaries, sets, and ranges. The section also explains how different types of sequences have different default iterators (e.g., iterating over a dictionary gives you the keys by default).

Generators and yield keyword: Generators are a type of iterator that generate values on the fly. The yield keyword is used in a function like a return statement, but instead of returning a value and terminating the function, it produces a value and suspends the function’s execution. The function can then be resumed later on from where it left off, allowing it to produce a sequence of results over time, instead of computing them all at once and sending them back in a list, for example.

from typing import Iterator

def sqrt(a: float) -> Iterator[float]:
    x = a / 2  # initial guess
    while True:
        x = (x + (a / x)) / 2
        yield x

With this version, we update x at each iteration and then yield the updated value. Instead of getting a single value, the caller of the function gets an iterator that contains an infinite number of iterations; it is up to the caller to decide how many iterations to evalu- ate and when to stop. The sqrt function itself has an infinite loop, but this isn’t a problem because execution of the function pauses at each yield which lets the caller of the function stop it whenever they want. To do 10 iterations of the sqrt algorithm, we could use itertools.islice:

Using Generators with itertools: The Python itertools module provides powerful tools for working with iterators and generators. The itertools.islice function can be used to consume a specific number of values from a generator.

import itertools

iterations = list(itertools.islice(sqrt(25), 10))
iterations[-1]

Implementing a converge Function: The section ends with the implementation of a converge function that takes an iterator and a threshold, and yields values from the iterator until two consecutive values are within the threshold of each other. This function uses the itertools.pairwise function, which is available in Python 3.10 and later, to get pairs of consecutive values from the iterator.

def converge(values: Iterator[float], threshold: float) -> Iterator[float]:
    for a, b in itertools.pairwise(values):
        yield a
        
        if abs(a - b) < threshold:
            break

Each function takes an iterator as an input and returns an iterator as an output. This doesn’t always have to be the case, but we get a major advantage when it is: iterator → iterator operations compose. We can get relatively complex behavior by starting with an iterator (like our sqrt example) then applying multiple operations to it. For example, somebody calling sqrt might want to converge at some threshold but, just in case the algorithm gets stuck for some reason, also have a hard stop at 10,000 iterations. We don’t need to write a new version of sqrt or even converge to do this; instead, we can use converge with itertools.islice:

results = converge(sqrt(n), 0.001)
capped_results = list(itertools.islice(results, 10000))

We can write and test each operation— sqrt, converge, islice—in isolation and get complex behavior by combining them in the right way.