Functional Programming

Abstract¶

In this notebook, we explore key techniques in functional programming, with a particular emphasis on recursion. Recursion exemplifies code reuse by defining a function in terms of itself, allowing for elegant, declarative solutions to complex problems using a divide-and-conquer approach. However, readers will also learn about the potential inefficiencies of recursion due to redundant computations of subproblem solutions. To address these inefficiencies, we introduce the concept of using function states to simplify calculations, while discussing the pitfalls of global variables and their impact on program predictability. Finally, we delve into the idea of encapsulation through closures, paving the way for an understanding of object-oriented programming principles.

from __init__ import install_dependencies

await install_dependencies()

Recursion¶

To motivate the idea of programming using functions, consider the problem of computing the greatest common divisor:

%%optlite -r -h 600
def gcd(a, b):
    ### BEGIN SOLUTION
    return gcd(b, a % b) if b else abs(a)
    ### END SOLUTION


print(gcd(3 * 5, 5 * 7))

# tests
assert gcd(3 * 5, 5 * 7) == 5
assert gcd(1302, 0) == gcd(0, 1302) == 1302
assert gcd(0, 0) == 0
assert gcd(10**10, 10**10 + 1) == 1

One may implement Definition 1 directly using a for loop as follows:

def gcd(a, b):
    if a and b:
        for d in range(min(abs(a), abs(b)), 0, -1):
            if a % d == b % d == 0:
                return d
    return abs(a) or abs(b)


print(gcd(3 * 5, 5 * 7))

Unfortunately, the implementation is inefficient: It will take a long time to run the following test case:

if input('Run test? [Y/n]').lower() != 'n':
    assert gcd(10**10, 10**10 + 1) == 1

A more efficient way to compute gcd is as follows:

Proof

The base case holds trivially and $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a)$ , so it suffices to show that any common factor of $a$ and $b$ must divide $r:=a\operatorname{mod}b$ , if $b\neq 0$ . To this end, suppose $c$ is the common factor. Then, for some integers $q_0, q_1, q_2$ :

\begin{align} r &\stackrel{\text{(a)}}= \underbrace{a}_{\stackrel{\text{(b)}}=q_1 c} - \underbrace{b}_{\stackrel{\text{(c)}}=q_2 c} q_0\\ &= (q_1-q_2 q_0) c \end{align}

(2)

which is divisible by $c$ as desired. (Can you explain the equalities $\text{(a)--(c)}$ ?

How to implement (1)? Can we define gcd using gcd?

%%optlite -h 600
def gcd(a, b):
    return gcd(a % b, b)


print(gcd(3 * 5, 5 * 7))

Solution to Exercise 2

It is crucial to swap the arguments to ensure a strict reduction in the size of the problem. Additionally, the base case gcd(a, 0) must be handled properly to terminate the recursive call correctly. For example, the following implementation can result in an infinite loop:

def gcd(a, b):
    return gcd(b, a % b if b else a)

This occurs because gcd(a, 0) returns gcd(0, a), which in turn calls gcd(a, 0) again, i.e., there is no reduction in the size of the problem.

%%ai chatgpt -f text
Using Eclidean algorithm for gcd, explain in one paragraph or two how to come up with a recursion that solves a problem by divide-and-conquer.

%%ai chatgpt -f text
Describe in one paragraph how recursion got adopted in programming.

Recursion vs Iteration¶

Is recursion always better than iteration?

Consider computing the Fibonacci number of order $n$ , which is even defined in a recursive manner:^[2]

F_n := \begin{cases} F_{n-1}+F_{n-2} & n>1 \kern1em \text{(recurrence)}\\ 1 & n=1 \kern1em \text{(base case)}\\ 0 & n=0 \kern1em \text{(base case)}. \end{cases}

(3)

%%ai chatgpt -f text
Describe what the fibonacci number is in one sentence and list three most important applications of the Fibonacci number in bullet points.

The following function fibonacci(n) implements $F_n$ naturally as a recursion:

%%optlite -r -h 450
def fibonacci(n):
    if n > 1:
        return fibonacci(n - 1) + fibonacci(n - 2)  # recursion
    elif n == 1:
        return 1
    else:
        return 0


print(fibonacci(2))

# Assign n the appropriate value
### BEGIN SOLUTION
n = 35
### END SOLUTION
n

%%timeit -n 1 -r 1
fibonacci(n)

# hidden tests
### BEGIN HIDDEN TESTS
n < 40
### END HIDDEN TESTS

Is the recursion efficient?

As a comparison, the following computes the Fibonacci number using a while loop instead of a recursion.

%%optlite -r -h 550
def fibonacci_iteration(n):
    if n > 1:
        _, F = 0, 1  # next two Fibonacci numbers
        while n > 1:
            _, F, n = F, F + _, n - 1
        return F
    elif n == 1:
        return 1
    else:
        return 0


fibonacci_iteration(3)

# Assign n the appropriate value
### BEGIN SOLUTION
n = 340000
### END SOLUTION
n

%%timeit -n 1 -r 1
fibonacci_iteration(n)

# hidden tests
### BEGIN HIDDEN TESTS
n > 3e5
### END HIDDEN TESTS

To understand the difference in performance, modify fibonacci to print each function call as follows.

def fibonacci_verbose(n):
    """Returns the Fibonacci number of order n."""
    print(f"fibonacci({n})")
    return fibonacci_verbose(n - 1) + fibonacci_verbose(n - 2) if n > 1 else 1 if n == 1 else 0


fibonacci_verbose(5)

Solution to Exercise 5

There are many redundant computations. E.g., fibonacci(3) is called twice because

fibonacci(5) calls fibonacci(4) and fibonacci(3).
fibonacci(4) then calls fibonacci(3) and fibonacci(2).

Setting performance considerations aside, do we really need recursion?

Indeed, we can always convert a recursion to an iteration that is at least as efficient. (Why?)^[3]

%%optlite -r -h 550
def gcd_iteration(a, b):
    ### BEGIN SOLUTION
    while b:
        a, b = b, a % b
    return a
    ### END SOLUTION


gcd_iteration(3 * 5, 5 * 7)

%%ai chatgpt -f text
Explain in one paragraph what a tail recursion is and how to convert a tail recursion to an iteration.

%%ai chatgpt -f text
Explain in one paragraph how non-tail recursive functions can be significantly slower than their iterative counterparts.

Global Variables¶

Suppose our task is to print the entire sequence of Fibonacci numbers up to certain order such as:

for n in range(10):
    print(fibonacci_iteration(n))

Solution to Exercise 7

Each call to fibonacci_iteration(n) recomputes the last two Fibonacci numbers $F_{n-1}$ and $F_{n-2}$ for $n\geq 2$ .

How to avoid redundant computations?

One way is to store the last two computed Fibonacci numbers as global variables.

%%optlite -r -h 700
Fn, Fnn, n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    Fn  : Next Fibonacci number      = {Fn}
    Fnn : Next next Fibonacci number = {Fnn}
    n   : Next order                 = {n}"""
    )


def next_fibonacci():
    global Fn, Fnn, n  # global declaration
    value, Fn, Fnn, n = Fn, Fnn, Fn + Fnn, n + 1
    return value


for i in range(5):
    print(next_fibonacci())
print_fibonacci_state()

Why global is needed in next_fibonacci?

What would happen if the global statement is removed?

%%optlite -h 400
def next_fibonacci():
    """Returns the next Fibonacci number."""
    # global Fn, Fnn, n
    value = n
    n, Fnn, n = Fnn, n + Fnn, n + 1
    return value


next_fibonacci()

UnboundLocalError is raised (as supposed to NameError) because

the assignment in Line 5 defines n as a local variable by Rule 2, but
the assignment in Line 4 references n, which is not yet defined at that point.

Consider rewriting the for loop as a while loop:

%%optlite -h 650
Fn, Fnn, n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    Fn  : Next Fibonacci number      = {Fn}
    Fnn : Next next Fibonacci number = {Fnn}
    n   : Next order                 = {n}"""
    )


def next_fibonacci():
    """Returns the next Fibonacci number."""
    global Fn, Fnn, n  # global declaration
    value, Fn, Fnn, n = Fn, Fnn, Fn + Fnn, n + 1
    return value


n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

Solution to Exercise 8

There is a name collision. n is also incremented by next_fibonacci(), and so the while loop is only executed 3 times in total.

To avoid such error, a convention in python is to use a leading underscore for variable names that are private (for internal use):

_single_leading_underscore: weak “internal use” indicator. E.g., from M import * does not import objects whose names start with an underscore.

%%optlite -h 600
_Fn, _Fnn, _n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    _Fn  : Next Fibonacci number      = {_Fn}
    _Fnn : Next next Fibonacci number = {_Fnn}
    _n   : Next order                 = {_n}"""
    )


def next_fibonacci():
    """Returns the next Fibonacci number."""
    global _Fn, _Fnn, _n  # global declaration
    value, _Fn, _Fnn, _n = _Fn, _Fnn, _Fn + _Fnn, _n + 1
    return value


n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

Closure¶

Is it possible to store the function states without using global variables?

We can use nested functions and nonlocal variables.

def create_fibonacci(Fn, Fnn):
    def next_fibonacci():
        """Returns the next (generalized) Fibonacci number starting with
        Fn and Fnn as the first two numbers."""
        nonlocal Fn, Fnn, n  # declare nonlocal variables
        value = Fn
        Fn, Fnn, n = Fnn, Fn + Fnn, n + 1
        return value

    def print_fibonacci_state():
        print(
            """States:
        Next Fibonacci number      = {}
        Next next Fibonacci number = {}
        Next order                 = {}""".format(
                Fn, Fnn, n
            )
        )

    n = 0  # Fn and Fnn specified in the function arguments
    return next_fibonacci, print_fibonacci_state


next_fibonacci, print_fibonacci_state = create_fibonacci(0, 1)
n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

The state variables Fn, Fnn, and n are now encapsulated, meaning they are contained within the scope of the create_fibonacci function, i.e.,

they are not exposed globally, unlike the global variables, but
they are accessible by the inner functions of create_fibonacci.

The encapsulation allows us to create multiple Fibonacci sequences with different base cases independently without interfering with each others:

usual_fib = create_fibonacci(0, 1)
cs1302_fib = create_fibonacci("cs", "1302")
for n in range(3):
    print(usual_fib[0]())
    usual_fib[1]()
    print(cs1302_fib[0]())
    cs1302_fib[1]()

next_fibonacci and print_fibonacci_state are local functions of create_fibonacci:

Local functions can access (capture) the other local variables of create_fibonacci by forming the so-called closures. Each local function has an attribute named __closure__ that stores the captured local variables.
Similar to the global statement, a nonlocal statement is needed for assigning non-local variables.

def print_closure(f):
    """Print the closure of a function."""
    print("closure of ", f.__name__)
    for cell in f.__closure__:
        print("    {} content: {!r}".format(cell, cell.cell_contents))


print_closure(next_fibonacci)
print_closure(print_fibonacci_state)

Lexical scoping can sometimes be counter-intuitive:

def foo():
    return x


def bar():
    x = "dynamically scoped"
    # NOT the same as:
    # return x
    return foo()  


x = "lexically scoped"
bar()

Try re-excuting the above code after uncommenting the line # return x. Even though foo() returns x, the line return foo() is not the same as return x, i.e., one cannot simply substitute foo() by x. To understand lexical scoping, compare it with dynamic scoping illustrated by this Maxima notebook.

%%ai chatgpt -f text
Explain in one paragraph the differences between lexical scoping and dynamic scoping, and why Python implements the prior.

Lexical scoping is a powerful concept that can be leveraged to implement object-oriented programming. For example, we can rewrite create_fibonacci to return a Fibonacci object as shown below:

def create_fibonacci(Fn, Fnn):
    def next():
        """Returns the next (generalized) Fibonacci number starting with
        Fn and Fnn as the first two numbers."""
        nonlocal Fn, Fnn, n
        value = Fn
        Fn, Fnn, n = Fnn, Fn + Fnn, n + 1
        return value

    def self():  # make the return object callable to replace print_fibonacci_state
        print(
            """States:
        Next Fibonacci number      = {}
        Next next Fibonacci number = {}
        Next order                 = {}""".format(
                Fn, Fnn, n
            )
        )

    n = 0

    self.next = next  # add next as an attribute of self
    return self       # to be returned


fib = create_fibonacci(0, 1)
n = 0
while n < 5:
    print(fib.next())
    n += 1
fib()

The create_fibonacci function returns the self function, which has access to the next function and other internal states of the create_fibonacci function. To create multiple Fibonacci objects:

usual_fib = create_fibonacci(0, 1)
cs1302_fib = create_fibonacci("cs", "1302")
for n in range(3):
    print(usual_fib.next())
    usual_fib()
    print(cs1302_fib.next())
    cs1302_fib()

As the above code shows, closures enable an object-oriented programming approach by allowing the creation of objects that share methods but maintain possibly distinct attribute values.

%%ai chatgpt -f text
Explain in one paragraph the importance of closures in programming and why they are called closures.

Footnotes¶

What about the other base case $\operatorname{gcd}(0, b)$ ?
↩
Fibonacci numbers have practical applications in generating pseudorandom numbers.
↩
A recursion is ultimately executed step-by-step with an execution stack that keeps track of the recursive calls. Such an execution esssentially converts a recursion to an iteration.
↩

Lab 5

Turtle Graphics

Lecture 6

Generator and Decorator