Whoever said that pleasure wasn’t functional?—Charles Eames

Imagine that our alien is sitting at a cafe, surfing the Internet, sipping a triple mochaccino, and is now about to purchase the Harry Potter Complete DVD Collection (movies 1 through 17) from the massive online store, Nile.com. As it types in its credit card number to make its purchase, it suddenly pauses to wonder how its financial details will be kept secure as they are transmitted over the cafe’s Wi-Fi and then over the vast reaches of the Internet. That’s a valid concern. The good news is that many online stores use cryptography to keep such transactions secure.

One of the most famous and widely-used cryptography schemes is called RSA, after the three computer scientists who invented it: Ron Rivest, Adi Shamir, and Leonard Adleman. Here’s how it works: The online store has its own mathematical function that all customers use to encrypt their data before transmitting it over the network. This mathematical function is made publicly available. The hope is that while anyone can easily use this function to encrypt data, only the online store can “undo” (or, more technically, “invert”) the function to decrypt the data and recover the original number.

For example, imagine that Nile.com tells customers to use the function \(f(x)=2x\). It’s certainly easy to encrypt any number we wish to send—we simply double it. Unfortunately, any first grader with a calculator can decrypt the message by simply dividing it by 2, so that encryption function is not secure.

The RSA scheme uses a slightly more complicated function. If \(x\) is our credit-card number, we encrypt it using the function \(f(x) = x^e \text{ mod } n\), where \(e\) and \(n\) are carefully chosen numbers. (Remember from the previous chapter that \(x^e \text{ mod } n\) means the remainder when \(x^e\) is divided by \(n\); it can be easily computed in Python using the expression `(x**e) % n`.)

It turns out that if \(e\) and \(n\) are chosen appropriately, the online store will be able to decrypt the number to retrieve the credit card number \(x\) but it will be nearly impossible for anyone else to do so—even though everyone knows \(e\) and \(n\).

That’s pretty interesting, but how do we choose \(e\) and \(n\) and how will the store later decrypt the number that it receives? Well, we first choose two different large prime numbers \(p\) and \(q\) at random. Next, \(n\) is just \(pq\). Now, to get the number \(e\), we have to perform two steps: first we let \(m = (p−1)(q−1)\), and then we choose our exponent \(e\) to be a random prime number less than \(m\) that is also not a divisor of \(m\). That’s it!

Now, any number \(x\) less than \(n\) can be encrypted by computing \(x^e \text{ mod } n\). Once we have selected \(e\) and \(n\), we can share those values with anyone wishing to send us encrypted information. In a typical Internet shopping transaction, your web browser would get the publicly available values of \(e\) and \(n\) from the online store and use them to encrypt your credit card number, \(x\). Together, the values \(e\) and \(n\) are called the *public key* for this store. (In cryptology, a public key is simply a key that can be safely published without giving away the corresponding *secret key*.)

For example, let \(p=3\) and \(q=5\). They’re certainly prime (although they are way too small to be secure in practice). Now, \(n=3 \times 5=15\) and \(m = (3−1) \times (5−1) = 8\). For our encryption exponent \(e\), we could choose the prime number 3 because it’s less than 8 and also doesn’t divide 8. Now, we can encrypt any number less than n. Let’s encrypt the number 13, for example. We can compute \(13^3 \text{ mod } 15\) in Python as `(13**3) % 15`; the result is 7. So 7 is our encrypted number, which we send over the Internet to the online store.

How does the store decrypt that 7 and discover that the original number was actually 13? At the same time that the encryption exponent e was computed, we should have also computed a decryption exponent \(d\), which has two properties: it is between 1 and \(m − 1\), and \(ed \text{ mod } m = 1\). It’s not hard to show that, because of the way \(e\) and \(m\) were chosen, there is exactly one value that has these properties; we call d the *multiplicative inverse of e modulo m*. In our example, \(e = 3\) and \(m = 8\), and \(d\) is also 3 (it’s a coincidence that \(e\) and \(d\) are equal; that’s not normally the case—if it were, the decryption key wouldn’t exactly be a secret!). Notice that \(ed \text{ mod } 8 = 9 \text{ mod } 8 = 1\). Now, the online store can decrypt any number \(y\) that it receives by simply computing \(y^d \text{ mod } n\). In our case, we received the encrypted number \(y = 7\). We compute \(7^3 \text{ mod } 15\) using Python `((7**3) % 15)` and get the answer 13. Indeed, that’s the value that we encrypted a moment ago! Keep in mind that while the encryption key \(e\) and \(n\) are public, the online store must keep the *decryption key* \(d\) private. Anyone with access to \(d\) can decrypt any message sent with the encryption key.

Exactly *why* this works is not too hard to show and is often taught in an introductory discrete math or algorithms course. But you may be wondering why we are so confident that the scheme is secure. This, too, requires a bit more time to explain than we have here. We will point out, however, that since the the values \(e\) and \(n\) are public, if a malicious person could find the two primes \(p\) and \(q\) that we originally selected, then they could figure out \(m\) and then \(d\) and they could crack the code. The good news is that “factoring” a number \(n\) into its prime divisors is known to be a “computationally hard” problem—*very* hard. (*Computationally hard* means a problem that takes a long time to compute the answer for.) For example, the U.S. National Institutes of Standards and Technology estimates that if we encrypt a message today using public keys that are about 600 digits long, it would take until about the year 2030 to crack the code—even if a very large number of very fast computers
were used for the attack.

Recall that in the previous chapter we learned about Python functions and explored the power of recursion. The style of programming that we examined—programs constructed from functions that call one another (and possibly themselves)—is called *functional programming*. Interestingly, in functional programming languages like Python, functions are actually data just like numbers, lists, and strings. We say that functions are “first-class citizens” of the language. In particular, we can write functions that take *other functions* as arguments and return *other functions* as results! In this chapter we’ll explore these ideas, first using them to write a short program that efficiently generates long lists of primes, and ultimately writing a function that generates both the encryption and decryption functions for RSA cryptography. By the end of this chapter, we’ll have written Python programs that will allow you to securely send data to your friends.

Motivated by RSA cryptography, our first mission is to find a way to generate a list of primes. One reasonable way to do this is to first write a function that determines whether or not its argument is prime. Once we have such a function, we could use it to test a sequence of consecutive numbers for primality, keeping those that are prime in a list.

But how do we test if a single positive integer \(n\) is prime? One idea is to simply test whether any number between 2 and \(n − 1\) divides it. If so, the number is not prime. Otherwise the number is prime. (In fact, it suffices to test just the numbers between 2 and \(\sqrt{n}\), since if \(n\) is not prime, at least one of its divisors must be less than or equal to \(\sqrt{n}\). But for now, let’s simply test all the possible divisors between 2 and \(n−1\).)

To that end, it would be useful to have a function `divisors(n)` that accepts our number `n` (which we wish to test for primality) and returns `True` if `n` has any divisors (other than 1 and itself), and `False` otherwise. Actually, it will turn out to be handy if `divisors` accepts two additional numbers, `low` and `high`, that give a range of divisors to test. That will let us reduce the amount of work that has to be done.

For example, `divisors(15, 2, 14)` should return `True` because 15 has a divisor between 2 and 14 (and therefore is not prime), but `divisors(11, 2, 10)` should return `False` because 11 has no divisors between 2 and 10 (and therefore is prime). Also, note that `divisors(35, 2, 4)` should return `False` even though 35 is *not* prime.

We can write the `divisors(n, low, high)` function using recursion! To simplify matters, we’ll assume that the arguments are all positive integers. If `low` is higher than `high`, then the answer is `False` because `n` cannot have any divisors in the specified range (since there are no numbers in increasing order between `low` and `high`). So, if `low > high` we must return `False`—which is a base case.

But what if `low` is less than or equal to `high`? In this case, we can test whether `n` has a divisor between `low` and `high` like this: If `n` is divisible by `low`, then we’ve found a divisor in that range and we must return `True`. Otherwise, the answer to the question: “Does `n` have a divisor between `low` and `high`?” now becomes the same as the answer to the question “Does `n` have a divisor between `low+1` and `high`?” But that’s a version of the original question, and thus one that we can solve recursively! Here’s our solution:

```
def divisors (n, low, high):
'''Returns True if n has a divisor in the range from low to high.
Otherwise returns False.'''
if low > high:
return False
elif n % low == 0: # Is n divisible by low?
return True
else:
return divisors (n , low + 1, high)
```

Now we can test if n is prime by checking whether it has any divisors between `2` and
`n-1`:

```
def isPrime (n):
'''For any n greater than or equal to 2,
Returns True if n is prime. False if not.'''
if divisors (n, 2, n-1):
return False
else :
return True
```

We can do this even more elegantly this way:

```
def isPrime (n):
'''For any n greater than or equal to 2,
Returns True if n is prime. False if not.'''
return not divisors (n, 2, n-1)
```

Recall from Chapter 2, that `not` “negates” a Boolean, so if `divisors(n, 2, n-1)` is `True` then `not divisors(n, 2, n-1)` is `False`, and if `divisors(n, 2, n-1)` is `False` then `not divisors(n, 2, n-1)` is `True`.

Now we can use `isPrime` to generate lists of primes, again using recursion. Imagine that we want to know all of the primes from 2 to some limit, for example 100. For each number in that range, we could test if it’s prime and, if so, add it to our growing list of primes. Before you look at the code below, see if you can determine the base case and the
recursive step for such a function.

Now, here is the Python implementation:

```
def listPrimes (n, limit):
'''Returns a list of prime numbers between n and limit.'''
if n == limit:
return []
elif isPrime (n):
return [n] + listPrimes (n+1, limit)
else:
return listPrimes (n+1, limit)
```

Notice that in the second return statement, we returned `[n] + listPrimes(n+1, limit)` rather than `n + listPrimes(n+1, limit)`. Why? Well, in this case the plus sign means that two lists should be concatenated, so the expressions on its left and right have to be lists. Indeed, the result of calling `listPrimes` will be a list, since by definition a list is what this function returns (and notice that in the base case it returns the empty list). However, `n` is a number, not a list! To make it a list, we place it inside square brackets. That way, we are concatenating two lists and life is good.

The above strategy for generating primes works, but it’s quite slow—particularly when attempting to generate large primes. The problem is that it repeats a lot of work. For example, if you call `listPrimes(51, 2, 50)` it will test 2 as a divisor and fail—but it will still insist on testing 4,6,8,...,50 even though we’ve already proven that 51 isn’t even!

A much faster algorithm for generating primes is the so-called *sieve of Eratosthenes*. This method is named after Eratosthenes, an ancient Greek mathematician who lived around 2200 years ago. Here’s the idea: To find all of the primes from 2 to 1000, for example, we first write down all of the integers in that range. Then we start with 2; it’s the first prime. Now, we remove (or “sift”) all multiples of 2 from this list since they are definitely not prime. When we’re done, we come *back* to the beginning of our remaining list. The number 3 survived the sifting of numbers that was performed by 2, so 3 is prime. We now cancel out all remaining numbers that are multiples of 3, since they too cannot be prime. When we’re done, we look at the first number in the remaining list. It’s not 4 (it got sifted out earlier when we looked at 2), but 5 is there. So 5 is prime and we let it sift all of its multiples that remain in the list. We continue this process until every remaining number has had a chance to sift the numbers above it.

We’ll implement a recursive algorithm motivated by Eratosthenes’ algorithm as a Python function called... `primeSieve`. (In the spirit of full disclosure, our implementation will take a few liberties with Eratosthenes’ algorithm.) It will take a list of numbers 2,3,... up to the largest number that we’re interested in, and will return a list of all the primes in the original list. Fortunately, Python has a built-in function that allows us to obtain the list of all integers from a starting point to an ending point. It’s called `range`, and in Python 2 it works like this:

```
>>> range(0,5)
[0, 1, 2, 3, 4]
>>> range(3,7)
[3, 4, 5, 6]
```

In Python 3 `range` works almost the same, but it needs a little nudge to turn the result into a list:

```
>>> list(range(0,5))
[0, 1, 2, 3, 4]
>>> list(range(3,7))
[3, 4, 5, 6]
```

Notice that the list that we get back from `range` seems to stop one number too soon. That may seem weird, but as we’ll see later, it turns out to be useful. So getting *all* the integers from 2 to 1000, for example, is easy: `range(2, 1001)`. We can then pass that list into the `primeSieve` function.

Before writing primeSieve let’s just do a small thought experiment to better understand how it will work. Imagine that we start it with the list `range(2, 11)`, which is:

`[2, 3, 4, 5, 6, 7, 8, 9, 10]`

Passing this list to `primeSieve` is basically saying “Could you please find me all of the primes in this list?” To accommodate your polite request, the `primeSieve` function should grab the 2 and hold on to it because it’s a prime. It should then sift all of the multiples of 2 from this list, resulting in a new list:

`[3, 5, 7, 9]`

Now what? Well, `primeSieve` would like to do as little work as possible and instead send that list to some function and ask it, “Could you please find me all of the primes in *this* list?” Aha! We can send that list *back* to `primeSieve` because its job is to find the primes in a given list. That’s just recursion!

So, continuing with our example, the first time we called `primeSieve` it found the 2, sifted out the multiples of 2 to get the list `[3, 5, 7, 9]`, and called `primeSieve` on that list. Whatever comes back from the recursive call will be tacked on to the 2 that we’re currently holding—and then we’ll have the whole list of primes from 2 to 10.

The recursive call to primeSieve with the argument list `[3, 5, 7, 9]` will similarly grab the 3 from the front of that list, sift out all of the multiples of 3 to get list `[5, 7]`, and will ask for help finding the primes in that list. Whatever primes are returned will be tacked on to the 3 that we’re holding, and that will be all of the primes in the list `[3, 5, 7, 9]`.

In the next recursive call, we’ll grab 5 and recur on the list `[7]`. *That* recursive call will grab the 7 and recur on the empty list. We see here that since the list is getting shorter each time, the base case arises when we have an empty list. In that case, `primeSieve` must report that “the list of all the primes in my argument is empty”—that is, it should return the empty list.

We still need a function that will do the actual sifting. We can imagine a function called `sift` that takes two arguments—a number `toRemove` and a list of numbers `numList`—and returns all of the numbers in `numList` that are *not* multiples of `toRemove`. Let’s come back to that in a moment, and write our `primeSieve` under the assumption that we have `sift`. This approach for writing programs is called *top-down design* because we start at the “top” (what we want) and then work our way down to the details that we need.

```
def primeSieve(numberList):
'''Returns the list of all primes in numberList, using a prime sieve algorithm.'''
if numberList == []: # if the list is empty,
return [] # ...we're done
else:
prime = numberList[0] # The first element is prime!
return [prime] + primeSieve(sift(prime, numberList[1:]))
```

Now, we need to sift. The next section will introduce a tool that will help us do exactly that, so read on...

Fortunately for us, Python (like most functional programming languages) has a built-in function named `filter` that does (almost) exactly the sifting that we would like to do.

We’ll eventually get back to the problem of general list sifting that we started above, but for the moment let’s just focus on the problem of sifting a list by removing numbers divisible by two. To demonstrate `filter` in action, let’s first define a function called `isNotDivisibleBy2` that takes a number `n` as an argument and returns a Boolean value: `True` if the number is not divisible by 2 (i.e., it is odd) and `False` otherwise (i.e. it is even).

```
def isNotDivisibleBy2(n):
'''Returns True if n is not divisible by 2,
else returns False.'''
return n % 2 != 0
```

Now back to filtering. Having `isNotDivisibleBy2`, here’s how we can use it with Python’s `filter` function. In Python 2 it looks like this:

```
>>> filter(isNotDivisibleBy2, range(3, 10))
[3, 5, 7, 9]
```

In Python 3, `filter` doesn’t eagerly produce a list, so we need to send its result to the
`list` function, as follows:

```
>>> list(filter(isNotDivisibleBy2, range(3, 10)))
[3, 5, 7, 9]
```

You may have inferred what `filter` is doing: its first argument is a *function* and its second argument is a list. The function is a special one that takes a single argument and returns a Boolean result. A function that returns a Boolean is called a *predicate*; you can think of the predicate as telling us whether or not it “likes” its argument. Then, `filter` gives us back all of the elements in the list that the predicate likes. In our example, `isNotDivisibleBy2` is a predicate that likes odd numbers. So we got back the list of all the odd numbers in the original list.

A function that takes other functions as arguments?! Strange, but definitely allowed, and even encouraged! This idea is central to functional programming: functions can be passed into and returned from other functions just like any other kind of data. In fact, Chapter 4 will explain why this idea is not so strange after all.

Lists of numbers are not all we can filter. Here’s another example of `filter`, this time using lists of strings. In preparation for its next visit to Earth, our alien is attempting to master English and a number of other languages. The alien has a list of words to learn, but it’s particularly keen on learning the four-letter words first. For example, if it’s given the list of words `['aardvark', 'darn', 'heck', 'spam', 'zyzzyva']` it would like to have a way of filtering that list to just be the “bad” words `['darn', 'heck', 'spam']`.

Again, we define a predicate function first: a function called `isBad` that takes a string named `word` as an argument and returns a Boolean value: `True` if the word is of length four and `False` otherwise.

```
def isBad(word):
'''Returns True if the length of "word" is 4, else returns False.'''
return len(word) == 4
```

Now that we have `isBad`, here’s how we can use it with Python’s `filter` function:

```
>>> list(filter(isBad, ['ugh', 'darn', 'heck', 'spam', 'zyzzyva']))
['darn', 'heck', 'spam']
```

`Filter` helps us sift lists of numbers, but so far all we’ve seen how to do is to sift them to remove even numbers. If we wanted to remove multiples of 3 we would need another helper function:

```
def isNotDivisibleBy3(n):
'''Returns True if n is not divisible by 3, else returns False.'''
return n % 3 != 0
```

And then we’d need another to remove multiples of 5, and one for 7, and 11, and so on. Obviously this is not going to work.

The idea behind our `primeSieve` function is that we want to change what we are filtering for “on the fly,” depending on which number is currently first in the list. You might imagine that we could add a second argument to our predicate function, as follows:

```
def isNotDivisibleBy(n, d):
'''Returns True if n is not divisible by d, else returns False.'''
return n % d != 0
```

Generally, this would solve the problem, but in this case we have a problem: `filter` *requires* that the predicate function we pass it takes only one argument. So this new definition will not work either.

What we really need is a sort of “disposable” function that we can define just when we need it—using the number we currently care about sifting—and then immediately throw it away after we are done using it.

In fact, this function will be so temporary that we won’t even bother to give it a name! Such a function is called an anonymous function.

Here’s what an anonymous function definition looks like for our `isNotDivisibleBy2` example:

```
>>> filter(lambda n: n % 2 != 0, range(0, 1001))
```

The word “lambda” indicates that we are defining an anonymous function—a short-lived function that we need right here and nowhere else. Then comes the names of the arguments to the function (in this case, one argument named `n`), then a colon, and then the value that this function should return. So, this anonymous function `lambda n: n % 2 != 0` is exactly equivalent to our `isNotDivisibleBy2` function above.

The anonymous function syntax in Python is odd; in particular, we don’t put parentheses around the function’s arguments, and there is no `return` statement. Instead, anonymous functions in Python implicitly return whatever value comes after the colon.

Just to make the point that anonymous functions really are full-fledged functions, take a look at this:

Whoa—that’s really weird! In the first line, we’re defining a variable named `double` and giving it the value `lambda x: 2 * x`. But in a functional programming language functions are truly *first-class citizens*; they are data just like numbers,
strings, and lists. So `double` is a function with one argument, and if we want to use it we need to pass it a value. In the second line, that’s exactly what we’re doing. In fact, when we define a function in the “normal” way, that is by starting with the line `def double(n)`, we are *really* just saying `double` is a variable whose value is the function that I’m going to define in the lines following the `def` statement.”

Finally, we can use anonymous functions to finish writing `sift`, as follows:

```
def sift(toRemove, numList):
'''Takes a number, toRemove, and a list of numbers, numList.
Returns the list of those numbers in numList that are not multiples of toRemove.'''
return list(filter(lambda x: x % toRemove != 0, numList))
```

The anonymous function we pass into `filter` uses `toRemove` in its body without having to pass it in as an argument. It can do this because this function is defined in an environment where `toRemove` *already exists* and has a value.

Of course we could also write `sift` using the list-comprehension syntax (see the sidebar in section 3.6.2); then it would look like this:

```
def sift(toRemove, numList):
return [x for x in numList if x % toRemove != 0]
```

Finally, as a reminder, here is our `primeSieve` function again, using `sift`:

```
def primeSieve(numberList):
'''Returns the list of all primes in numberList using a prime sieve algorithm.'''
if numberList == []: # if the list is empty,
return [] # ...we're done
else:
prime = numberList[0] # The first element is prime!
return [prime] + primeSieve(sift(prime, numberList[1:]))
```

It’s surprising how much entertainment value there is in running `primeSieve` to generate long lists of primes. However, Python got angry with us when we tried something like this:

```
>>> primeSieve(list(range(2, 10000)))
```

We got a long and unfriendly error message. The reason is that this created a lot of recursion, and Python is trained to believe that if there is a lot of recursion going on, there must be an error in your program (usually because you forgot to put in a base case). Exactly how much recursion Python thinks is too much depends on the Python version and your computer’s operating system. However, you can ask Python to allow you more recursion by including the following two lines at the top of your file:

```
import sys
sys.setrecursionlimit(20000) # Allow 20000 levels of recursion
```

We asked for \(20,000\) levels of recursion here. Some operating systems may allow you more or less than this. (Most modern machines will allow much, much more.)

This brings us to one last point: while the prime sieve is quite efficient, most good implementations of the RSA scheme use even more efficient methods to generate large prime numbers. In practice, the primes used by RSA when encoding Internet transactions are generally a few hundred digits long! A CS course on algorithms or cryptography may well show you some of the more sophisticated and efficient algorithms for generating primes.

In the rest of this chapter we will continue to build on the idea of functions as first-class citizens that can be passed into or returned from other functions. We’ll look at two more examples: Google’s MapReduce approach to processing data, and taking derivatives of functions.

Imagine that you work for Nile.com. Your company maintains a list of product prices, and periodically the prices are systematically increased. Your boss comes into your office one morning and asks you to write a function called `increment` that takes a list of numbers as an argument and returns a new list in which each number is replaced by a value one greater. So, with the argument `[10, 20, 30]`, the result should be `[11, 21, 31]`.

No problem! We can write `increment` recursively. For the base case, if the argument is an empty list, we’ll also return an empty list. (Remember, the result is always a list of the same length as the argument, so returning anything other than the empty list in this case would be violating our contract!). For the recursive case, we observe that we can easily increment the first number in the list: We simply find that element and add one to it. We can then slice that first element off the list and increment the remainder. The phrase “increment the remainder” is essentially saying “use recursion on the remaining list.” In other words, `increment([10, 20, 30])` will first find the 10, add one to make it 11, and then recursively call `increment([20, 30])` to get the result `[21, 31]`. Once we have that, we just concatenate the 11 to the front of that list, resulting in `[11, 21, 31]`. Here’s the Python program:

```
def incrementList(numberList):
'''Takes a list of numbers as an argument and returns
a new list with each number incremented by one.'''
if numberList == []:
return []
else:
newFirst = numberList[0] + 1 # increment 1st element
# Next, increment the remaining list
incrementedList = incrementList(numberList[1:])
# Now return the new first element and the
# incremented remaining list
return [newFirst] + incrementedList
```

Your boss is pleased, but now tells you “I need a very similar function that takes a list as an argument and adds 2 to each element in that list.” Obviously, we could modify `increment` very slightly to do this. Then your boss tells you, “I need yet another function that takes a list as an argument and triples each element.” We can do that too, but this is getting old.

We see that your boss frequently needs us to write functions that take a list of numbers as an argument and return a new list in which *some function* is applied to every element in that list.

An important principle in computer science is “if you are building lots of very similar things, try instead to build one thing that can do it all.”

We’ve seen this principle before when we started writing functions, but here we’ll take it one step further. The “do it all” thing in this case is a function called `map`, which is built in to Python and many other functional programming languages. We’ll show it to you and then explain. But first, it will be handy to have two simple functions to help with our example. One function, called `increment`, takes a number as an argument and returns that number plus 1. The second, called `triple`, takes a number as an argument and returns three times that number:

```
def increment(x):
'''Takes a number x as an argument and returns x + 1.'''
return x+1
```

```
def triple(x):
'''Takes a number x as an argument and returns 3 * x.'''
return 3 * x
```

If you’re using Python 2, you can now do the following:

```
>>> map(increment, [10, 20, 30])
[11, 21, 31]
>>> map(triple, [1, 2, 3, 4])
[3, 6, 9, 12]
```

If you’re using Python 3, `map` is a bit lazy and requires some cajoling to produce the list, just like `filter` did. The magic incantation required in Python 3 looks like this:

```
>>> list(map(increment, [10, 20, 30]))
[11, 21, 31]
>>> list(map(triple, [1, 2, 3, 4]))
[3, 6, 9, 12]
```

This is passing the result of `map` to a built-in function called `list`, which forces Python 3 to actually produce the list.

Notice that `map` takes two arguments. The first is a function; the second is a list. The function that is given to `map` (e.g., `increment` and `triple` in our examples) **must** be a function that takes one argument and produces a single result. Then, `map` applies that function one-by-one to each element in the list to build a new list of elements.

Sometimes, we don’t need to create our own functions to give to `map`. For example, take a look at this example:

```
>>> map(len, ['I', 'like', 'spam'])
[1, 4, 4]
```

In Python 3, this would be

```
>>> list(map(len, ['I', 'like', 'spam']))
[1, 4, 4]
```

In this case, the built-in function `len` is applied to each of the strings in the given list. First, `len` is applied to the string `'I'`. The length of the string is 1 and that’s the first thing to go in the result list. Then the `len` function is applied to the string `'like'`; the result is 4, which is the next thing to go in the result. Finally, the length of `'spam'` is 4, which is the last value placed in the result list.

Notice how our abstraction theme comes into play with `map`. The details of how the function we pass to `map` is applied to the list are hidden away. We no longer have to worry specifically about how to step through the list to modify each element: `map` does this for us.

Note

**List Comprehensions**The

`map`,`reduce`, and`filter`functions, and the`lambda`notation for anonymous functions, are not unique to Python; they are found in most functional programming languages. However, Python offers an alternative syntax to`map`and`filter`called*list comprehensions*, which allow us to avoid using`lambda`. Sometimes that’s both conceptually easier and faster to type!Let’s start with the example from Section 3.6.1, where we wanted to increment every element in the list

`[10, 20, 30]`. Whereas earlier we used`map`and an`increment`function to do this, the list comprehension syntax looks like this:>>> [x + 1 for x in [10, 20, 30]] [11, 21, 31]

Similarly, we can triple every element in the list

`[1, 2, 3, 4]`using the syntax:>>> [3 * x for x in [1, 2, 3, 4]] [3, 6, 9, 12]

In general, the syntax is:

`[f(x) for x in L]`...where

`f`is some function and`L`is some list. Notice that this is really just like`map`in that we are mapping the function`f`to every element`x`in the list`L`. By the way, there’s nothing special about the name`x`for the variable; we could use a different variable name as in:>>> [len(myString) for myString in ['I', 'like', 'spam']] [1, 4, 4]

A very similar syntax can be used to do the job of

`filter`. Rather than using`filter`to obtain the four-letter words in a list as we saw earlier, we can use list comprehensions this way:>>> words = ['aardvark', 'darn', 'heck', 'spam', 'zyzzyva'] >>> [x for x in words if len(x) == 4] ['darn', 'heck', 'spam']

In this case, we defined the list

`words`before using the list comprehension, just to make the point that we can do that. Of course, we could have also done this as:>>> [x for x in ['aardvark', 'darn', 'heck', 'spam', 'zyzzyva'] ... if len(x) == 4]

Similarly, we could get the multiples of 42 between 0 and 1 million (another example where we used

`filter`) this way:>>> [x for x in range(0, 1000000) if x % 42 == 0]

In general, the format for using list comprehensions to filter looks like this:

`[x for x in L if ...]`...where

`L`is a list and the ... represents some Boolean expression; that is, an expression that evaluates to either`True`or`False`. We get back the list of all values of`x`in the list`L`for which that Boolean expression (recall that it’s called a predicate) is`True`. That is, we get all of the values of`x`that the predicate “likes.” Finally, we can write list comprehensions that combine both`map`and`filter`into one. Here’s an example where we produce the square of every even number between 0 and 10:>>> [x**2 for x in range(0, 11) if x % 2 == 0] [0, 4, 16, 36, 64, 100]

This list comprehension is mapping the function \(f(x) = x^2\) to every value of

`x`in the list of integers from 0 to 10 subject to filtering that list through a predicate that only likes even numbers. Thus, we get the squares of even numbers. In general, the syntax is:`[f(x) for x in L if ...]`where

`f`is a function,`L`is a list, and what comes after the \(\dots\) is a predicate. We get back the list of \(f(x)\) values for those values of`x`for which the predicate is`True`.By the way, this syntax works just the same in Python 2 and 3. Python 3 doesn’t require any special prodding to produce a list when list comprehensions are used.

Our alien has just learned about `map` and is quite excited. During its visit to Earth, the alien purchased a number of items and it plans to request reimbursement from its employer.

For example, here is a list of the costs, in U.S. dollars, of several items purchased by the alien: `[14, 10, 12, 5]`. The alien would like to convert these costs to its own currency and then add up the total. The exchange rate is 1 U.S. dollar equals 3 alien dollars. So, the values of the four items in alien dollars are `[42, 30, 36, 15]` and the total request for reimbursement in alien dollars will be \(42 + 30 + 36 + 15 =123\).

Converting a list from U.S. dollars to alien dollars is no problem—we did that above using `map` and our `triple` function. Now, though, we want to add up the elements in the resulting list. We could write a recursive function for that task. However, it turns out that there are many very similar tasks that the alien needs to perform as well.

Here’s one: Imagine that the alien converted between a variety of currencies while shopping on Earth. For example, the alien first got some dollars, then changed dollars into Euros, then changed Euros into rubles, and then rubles into yen. If the alien started with 1 U.S. dollar, how many yen is that? This is a matter of computing the products of exchange rates. If one dollar is 0.7 Euros, one Euro is 42 rubles, and one ruble is 3 yen, then one dollar is \(0.7 \times 42 \times 3 = 88.2\) yen. So now the alien needs to compute the *product* of a list of numbers.

Again, rather than writing a separate function to add up the numbers in a list and another to multiply the numbers in a list (and possibly others to do other things to elements in a list), Python provides a general-purpose function called `reduce` that reduces all of the elements in a list to a single element (e.g., their sum or product or something else).

Let’s first define a function called `add` that takes *two* arguments and returns their sum, and another called `multiply` that takes *two* arguments and returns their product.

```
def add(x, y):
'''Returns the sum of the two arguments.'''
return x + y
def multiply(x, y):
'''Takes two numbers and returns their product.'''
return x * y
```

Now, here’s `reduce` in action:

```
>>> from functools import *
>>> reduce(add, [1, 2, 3, 4])
10
>>> reduce(multiply, [1, 2, 3, 4])
24
```

In the first case `reduce` reduced our list to the sum of its elements, and in the second case to the product of its elements. Notice that the first argument to `reduce` is a function and the second is a list. A subtle point here is that the function that we give as an argument to `reduce` must take *two* arguments and return a single result. Then, `reduce` takes the first two elements from the list and applies the given function to reduce them to one element, takes that result and the next element from the list and applies the function to them, and repeats that process until all of the elements are reduced to a single value.

Finally, imagine that we plan to frequently take a list, map some function (e.g., `triple`) to each element in that list to produce a new list (e.g., the list of 3 times each element), and then apply some other function to reduce that new list to a single value (e.g., using `add` to get the sum of these values). This is a combination of `map` and `reduce`, or more accurately the *composition* of `map` and `reduce`. Let’s write such a function and call it `mapReduce`. It will take two functions and a list as arguments—the first function for `map` and the second for `reduce`:

Alternatively, this can be done more succinctly in one line as follows:

```
def mapReduce(mapFunction, reduceFunction, myList):
'''Applies mapFunction to myList to construct a new list
and then applies reduceFunction to the new list
and returns that value.'''
return reduce(reduceFunction, map(mapFunction, myList))
```

Now, for example, we can use `mapReduce` to convert prices from U.S. dollars to alien dollars and add up the total, like this:

```
>>> mapReduce(triple, add, [14, 10, 12, 5])
123
```

The second version of `mapReduce` above is particularly elegant in the way that `map` and `reduce` are composed or “glued” in one line. Notice that in order for Python to evaluate the expression `reduce(reduceFunction, map(mapFunction, myList))` it must first evaluate `map(mapFunction, myList)`, since that is one of the arguments to `reduce`. So, the `map` function is applied to `mapFunction` and list `myList` to get the resulting list. Now, `reduce` has both the function and the list that it needs to do its thing.

The `mapReduce` function is so broadly useful that it inspired a major part of Google’s internal software design! To read more about it, you can (of course) just Google “mapReduce.”

Note

**Functional Programming Meets Psychotherapy**

The ideas behind functional programming actually predate the computer. A mathematical framework called the *lambda calculus* was developed by the logician Alonzo Church in the 1930’s to examine the limits of what is theoretically computable. (We address some of these issues in Chapter 7.) The lambda calculus served as the basis of actual programming languages, such as the early language LISP developed at MIT in the 1950’s. The “lambda” in lambda calculus is the reason for its appearance in Python’s anonymous functions.

LISP and related functional programming languages have been of particular interest to researchers in Artificial Intelligence (AI) because they are well suited for analyzing text. We can take a human’s typed input and write functions that process the words as strings and sentences as lists of strings. This is called *natural language processing*. (The “natural” here refers to human languages in contrast to programming languages.)

One of the early and controversial examples of natural language processing and artificial intelligence was the ELIZA program, first written by Professor Joseph Weizenbaum at MIT in the mid-1960’s. Eliza impersonated a psychologist and allowed the human user to enter text that ELIZA would process and return a simple response that—while not actually aware of the user’s emotions—seemed generally appropriate. Eliza was first written by Weizenbaum in a language called SLIP, but was later reprogrammed in LISP.

Here’s the beginning of an actual transcript of an interaction with ELIZA from an online version of the program (available here).

`Eliza: Hello. I am ELIZA. How can I help you?`

`You: I am learning about functional programming.`

`Eliza: How long have you been learning about functional programming?`

`You: I guess it has been a few weeks now.`

`Eliza: Can you elaborate on that?`

Responses such as “Can you elaborate on that?” or even “Tell me about your mother” are commonly used and quickly reveal that ELIZA is actually rather clueless. While Weizenbaum evidently only intended ELIZA to serve as a demonstration of the power of natural language processing, some people actually took an interest in using ELIZA as their therapist! A book and a documentary have been made about Weizenbaum and ELIZA, and a number of free and commercial versions of the program are available, including some that have a very bad attitude and deliberately berate their “patient.”

If functions can be the arguments to other functions, it must also be possible for them to be the results of functions, right? Take a look at this `scale` function and try to figure out what it does:

The `scale` function takes the number 42 as an argument and returns a function (the `lambda` indicates that we’re giving back a function) that we are then assigning to the variable `f`. So `f` is a function, but what does that function do? Well, for any argument `x` it returns `42 * x`—as we see here:

```
>>> f(2)
84
>>> f(10)
420
```

There’s something odd here! In the definition of the `scale` function, the line:

`return lambda x: n * x`

makes it look like the function that we’re returning has *two variables*, `n` and `x`, whereas the `lambda x` indicates that this a function of just *one*
variable, `x`. Indeed, in the examples above, we defined `f = scale(42)` and then we gave `f` just *one* argument as in `f(2)` and `f(10)`.

When we said `f = scale(42)`, the 42 was passed into `scale`‘s argument `n`, and `n` was replaced with 42. Therefore, `scale(42)` actually returned

`lambda x: 42 * x`

That’s clearly a function of just *one* variable and that is the function that we then assigned to our variable `f`.

Although the `scale` function is admittedly not super-useful, the amazing thing here is that we wrote a program that can write other programs—a powerful concept that is widely used by computer scientists. Indeed, many complex programs are, at least in part, written by other programs.

By the way, rather than using an anonymous function inside our `scale` function, we could have given the function a name and returned that function. We do this as follows:

```
def scale(n):
def multiply(x): # Here we are defining a new function,
return n * x # but it's INSIDE scale!
return multiply # Here we are returning that function
```

Notice that the indented `def multiply(x)` indicates that `multiply` is being defined inside `scale`, so this is defining `multiply` to be one of `scale`‘s own variables, just like defining any variable within a function. The only difference is that `multiply` is a *function* rather than a number, list, or string. Then, once we’ve defined that variable, we return it. Now, calling `scale(42)`, for example, gives us back a function and we can do exactly what we did a moment ago with the first version of `scale`:

```
>>> f = scale(42)
>>> f(2)
84
>>> f(10)
420
```

Functions that take other functions as arguments or return a function as a result are called *higher-order functions*.

In addition to learning English and other languages, our alien has been advised to study calculus before returning to Earth, so that it can better impersonate a college student.

You probably recall the idea of taking the derivative of a function. For example, the derivative of \(f(x) = x^2\) is a new function \(f'(x) = 2x\). For our purposes, the key observation is that the derivative of a function is another function. You may also recall that there are many rules for computing derivatives, and yet some functions are very hard to differentiate and others are downright impossible. So in some cases we may want to approximate the derivative—and we can do this computationally! In fact, let’s write a Python function that differentiates *any* function (approximately).

We looked back at our own calculus notes and found that the derivative of a function \(f(x)\) is a function \(f'(x)\) defined as follows:

**\(\displaystyle{f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}}\)**

The derivative is defined as “the limit as \(h\) goes to zero.” However, for small positive values of \(h\), like \(h = 0.0001\), we get a good approximation of the limit. We can make the approximation as good as we want by making \(h\) as small as we want. Our objective, then, is to write a function called `derivative` that takes a function and a value of \(h\) as an argument, and returns another function that is the approximation of the derivative for that value of \(h\). Here we go:

```
def derivative(f, h):
'''Returns a new function that is the approximation of
the derivative of f with respect to h.'''
return lambda x: (f(x+h) - f(x)) / h
```

Notice that we’re returning a function, as we’re supposed to. That function takes an argument `x` and returns the approximate value of the derivative at that value `x` for the given `h`.

Wait a second! It seems that the function that we’re returning is using a function `f` and two numeric variables, `x` and `h`—so why do we see just the variable `x` after the `lambda`? This is the same issue that we saw earlier with the `scale` function. Remember that when we call the `derivative` function, we pass it both a function `f` and a number `h`. Then, that function and that number are “plugged in” wherever we see a `f` and a `h` in the program. In the expression `lambda x: (f(x+h) - f(x)) / h`, both the `f` and the `h` are no longer variables—they are actual values (albeit the `f` is a value that happens to be a function). So, the `lambda` anonymous function truly only has one argument, and that’s `x`.

Let’s try it out. First, let’s define a function \(x^2\) and name it `square`.

```
def square(x):
return x**2
```

Now, let’s use our `derivative` function:

```
>>> g = derivative(square, 0.0001)
>>> g(10)
20.000099999890608
```

The actual derivative of \(x^2\) is \(2x\), so the derivative at \(x=10\) is actually \(20\). We’re getting a pretty good approximation. That’s good, but here’s something better: if we now want to find the second derivative of \(x^2\), we can differentiate our first derivative. The actual second second derivative of \(x^2\) is simply \(2\) (for all values of \(x\)). Let’s see what our `derivative` function says.

```
>>> h = derivative(g, 0.0001)
>>> h(10)
2.0000015865662135
```

Speaking of second derivatives, it sure would be handy to have a more general function that could find us the first, second, third, or generally, the \(k^{th}\) derivative of a function. Let’s write a function called `kthDerivative(f, h, k)` to do this. It will take arguments that include a function `f`, a small number `h`, and a positive integer `k` and will return an approximation of the \(k^{th}\) derivative of \(f\). We could do this “from scratch”, not relying on the existing `derivative` function that we just wrote, but since we have it already let’s use `derivative`.

What’s the base case? The simplest case appears to be when \(k=1\), in which case we just return the derivative of the given function. (Although it would be equally defensible to have a base case at \(k=0\), in which case we would just return \(f\) itself.) Otherwise, \(k > 1\) and we need to find the recursive substructure. Well, the \(k^{th}\) derivative of \(f\) is, by definition, just the derivative of the \((k-1)^{st}\) derivative of \(f\). So we can ask the `kthDerivative` function to find the \((k-1)^{st}\) derivative of `f` and then apply our `derivative` function to it. This should be fun and easy.

```
def kthDerivative(f, h, k):
'''Returns a new function that is the approximation of
the kth derivative of f with respect to h.'''
if k == 1:
return derivative(f, h)
else:
return derivative(kthDerivative(f, h, k-1), h)
```

Let’s take this out for a spin by defining the “quartic” function \(x^4\) and then taking the third derivative, which we know to be \(24x\).

```
def quartic(x):
'''Returns x**4.'''
return x**4
```

```
>>> g = kthDerivative(quartic, 0.0001, 3)
>>> g(10)
241.9255906715989
```

The actual answer should have been 240; we got an approximation due to the value we used for \(h\).

That was a high-velocity discussion of derivatives, but it demonstrated some of the integral features of functional programming.

We began this chapter with a discussion of RSA cryptography. Recall that if Alice wants to be able to receive secure messages, then she can use the RSA algorithm to generate a public and a private key. The public key is entirely public—anyone can use it to encrypt a message to Alice. The private key, however, belongs exclusively to her; she uses it to decrypt messages encrypted using her public key. Of course, if Alice’s friend, Bob, wants to receive encrypted messages too, he can use RSA to generate his own public and private keys. He then shares his public key and keeps his private key secure. When you want to send an encrypted message to Alice, you use her public key to encrypt the message. When you want to send a message to Bob, you use his public key.

Our objective is to write a function called `makeEncoderDecoder()`, which takes no arguments, constructs the RSA encryption and decryption keys, and returns *two* functions: The first encrypts data using the encryption key (which is built into the function, so we don’t need to keep track of it—convenient when a key is hundreds of digits long!) The second function decrypts encrypted data using the decryption key (again built-in). Alice, Bob, you, and your friends will all be able to use the `makeEncoderDecoder()` function to construct encryption and decryption functions; each encryption function will be made public and each decryption function will be kept by its owner. Here’s an example of Alice using `makeEncoderDecoder`.

```
>>> AliceEncrypt, AliceDecrypt = makeEncoderDecoder()
Maximum number that can be encrypted is 34
>>> AliceEncrypt(5)
10
>>> AliceDecrypt(10)
5
>>> AliceEncrypt(31)
26
>>> AliceDecrypt(26)
31
```

Notice here that `makeEncoderDecoder` returned two functions (we’ll see in a moment how we can return two things), which we’ve named `AliceEncrypt` and `AliceDecrypt`. Then, we tested those two functions by encrypting them using Alice’s encryption function (which contains the encryption key inside of it) and then decrypting them with Alice’s decryption function (which incorporates the decryption key).

Let’s first remind ourselves how the RSA scheme works. We begin by choosing two different random prime numbers \(p\) and \(q\) (preferably large, but we’ll be able to decide how large later). We compute \(n = pq\) and \(m = (p-1)(q-1)\). We then choose the public encryption key \(e\) to be a random prime number between 2 and \(m-1\) such that \(e\) does not divide \(m\). Next, we construct the decryption key \(d\) to be the multiplicative inverse of \(e\) modulo \(m\)—that is, the unique number \(d\) such that \(d \leq m-1\) and \(ed \mod m == 1\). Now, we can encrypt a number \(x\) between 1 and \(n-1\) by computing \(y = x^e \mod n\). The value \(y\) is the encrypted message. We can decrypt \(y\) by computing \(y^d\mod n\).

We’ve already written functions that produce lists of prime numbers. We’ll use our efficient `primeSieve` function for that purpose. Recall that this function takes a list of consecutive integers from 2 to some largest value and returns the list of all primes in that range. Our first task will be to call the `primeSieve` function and choose two different prime numbers from that list. For now, let’s restrict the range of the prime numbers to be between 2 and 10. This will be useful for testing purposes, and later you can change the maximum value from 10 to something much larger.

To choose items at random, we can use Python’s `random` package. We tell Python that we want to use that package by including the line `import random` at the top of the file. Now, we have access to a variety of functions in that package. You can find out what’s in the package by looking at the Python documentation Web site or by typing `import random` at the Python prompt and then typing `help(random)`, which will describe all of the functions in that package.

One of the most useful functions in the `random` package is `random.choice`. It takes a list as an argument and returns a randomly selected element of that list. Here’s an example of that function in action:

```
>>> import random
>>> random.choice([1, 2, 3, 4])
3
>>> random.choice([1, 2, 3, 4])
2
```

We need to choose two different prime numbers in the range from 2 to 10. We could use `random.choice` twice, one to choose each of the two prime numbers, but there is a chance that we’ll get the same prime number twice, which doesn’t work for RSA. So, we can use another function in the `random` package, `random.sample`. It takes two arguments: a list and the number of items that we want to choose randomly—but uniquely—from that list. The function returns a list of the randomly selected items. Here’s an example of `random.sample` in action:

```
>>> import random
>>> random.sample([1, 2, 3, 4], 2) # Pick 2 items at random
[4, 3]
>>> random.sample(range(2, 100), 3) # Pick 3 different items
[17, 42, 23]
```

When a function returns a list of several items and we know how many items will be in that list, we can give names to those items like this:

```
>>> import random
>>> a, b = random.sample([1, 2, 3, 4], 2)
>>> a
4
>>> b
3
```

In this case, we knew that the `random.sample` function was going to return a list of two items (since we asked it to!) and we assigned the first of those items to the variable \(a\) and the second to \(b\). This technique is called *multiple assignment*.

Now let’s assume that we’ve already written a function called `inverse(e, m)` that returns the multiplicative inverse of \(e\) modulo \(m\)—that is, the unique number \(d < m\) such that \(ed \mod m = 1\). We’ll write that function in a moment, but assuming it exists, we have the ingredients for the `makeEncoderDecoder` function:

```
def makeEncoderDecoder():
'''Returns two functions: An RSA encryption function
and an RSA decryption function.'''
#
# Choose 2 primes:
#
p, q = random.sample(primeSieve(list(range(2, 10))), 2)
n = p*q # compute n
m = (p-1)*(q-1) # compute m
print ("Maximum number that can be encrypted is ", n-1)
#
# Choose a random prime for e:
#
e = random.choice(primeSieve(list(range(2, m))))
if m % e == 0: # If e divides m, it won't work!
print ("Please try again")
return
else:
d = inverse(e, m) # compute d
encoder = lambda x: (x**e) % n # encryption function
decoder = lambda y: (y**d) % n # decryption function
return [encoder, decoder]
```

Notice that this function is returning a list of two functions: the encryption and decryption functions! The encryption and decryption keys \(e\) and \(d\) are actual numbers that are embedded in those two functions, but \(x\) and \(y\) are the names of variables—the arguments that the user will ask to have encrypted or decrypted.

Finally, we need the `inverse(e, m)` function. We can implement it very simply by using `filter`, which we saw in Section 3.4. We’re looking for the single number \(d\) such that \(d < m\) and \(ed \mod m = 1\). So we can generate all of the integers between 1 and \(m-1\) (which is done with `range(1, m)`) and then filter all of the values \(d\) such that \(ed \mod m == 1\). Mathematicians tell us that there will be exactly one value of those. The `filter` function returns a list, so we use a sneaky Python trick and treat the call as if it were itself a list: we put `[0]` after it to pull out the first element and return it.

```
from functools import *
def inverse(e, m):
'''Returns the inverse of e mod m'''
return filter(lambda d: e*d % m == 1, range(1, m))[0]
```

You have to admit that this is amazing! However, *we* must admit that there are a few places where this function could be improved and extended. First, the prime numbers that we’re choosing from for \(p\) and \(q\) are in the range from 2 to 10. We could easily change the 10 to something much larger, but we almost certainly don’t want primes as small as 2. On the other hand, the `primeSieve` function expects to get a list of numbers that begins with 2 (do you see why?). To limit it to large prime numbers, we’d first need to generate primes beginning from 2 and then slice off the small ones. In addition, currently the `makeEncoderDecoder` might choose an encryption key \(e\) that is a divisor of \(m\). In this case, we’re told to try running the function again. That’s not a very nice solution. You might try to think of ways to fix this so that `makeEncoderDecoder` would keep choosing values of \(e\) until it finds one that is not a divisor of \(m\). You can do this with recursion, or you can do it with something called a `while` loop which we’ll see in Chapter 5.

You might also rightfully object that encrypting numbers is not as interesting as encrypting strings (i.e., text). We’d agree. The good news is that strings can be converted into numbers and vice versa, as we’ll see in the next chapter. Thus, it would not be difficult to encrypt strings by first converting them to numbers and then encrypting those numbers as we’ve done here. Decryption would first decrypt the number and then convert that back into the original string. In fact, that’s *exactly* how real encryption programs work!

In this chapter we’ve seen a beautiful idea: Functions are “first-class citizens” of the language, allowing us to treat them just like any other kind of data. In particular, functions can be the arguments and results of other functions. As a result, it’s possible to have general-purpose higher-order functions like `map`, `reduce`, and `filter` that can be used in many different ways by simply providing them with appropriate functions of their own. Moreover, we can write other higher-order functions that produce functions as results, allowing us to easily write programs that write other programs.

Now that we have explored the foundations of programming, we will turn our attention to a new question: “How exactly does a computer actually manage to do all of this amazing stuff?” To answer that question, in the next chapter we’re going to open the hood of a computer and see just how it works.