3.9 Working with Definitions

Throughout this course, we will study various mathematical objects that play key roles in computer science. As these objects become more complex, so too will our statements about them, to the point where if we try to write out everything using just basic set and arithmetic operations, our formulas won’t fit on a single line! To avoid this problem, we create definitions, which we can use to express a long idea using a single term.This is analogous to using local variables or helper functions in programming to express part of an overall value or computation.

In this section, we’ll look at one extended example of defining our own predicates mathematically and in Python, and using them in our statements. Let us take some familiar terminology and make it precise using the languages of predicate logic and Python.

As you can see, using this new predicate makes our formula quite a bit more concise! But the usefulness of our definitions doesn’t stop here: we can, of course, use our terms and predicates in further definitions.

Expressing definitions in programs

As we just saw, in mathematics we can often express definitions as predicates, where an element of the domain (e.g., an integer) satisfies the predicate if it fits the definition. Because predicates are just functions, we can express these in programs as well. For example, let’s consider the divisibility predicate \(\mid\), where \(d \mid n\) means \(\exists k \in \Z,~ n = kd\) (for \(d, n \in \Z\)). Here is the start of a function design in Python:

def divides(d: int, n: int) -> bool:
    """Return whether d divides n."""

While we can use the modulo operator % to implement this function (more on this later), we’ll stick to remaining faithful to the mathematical definition as much as possible. Unfortunately, there is one challenge with translating the mathematical definition of divisibility precisely into a Python function. In mathematics we have no trouble at all representing an infinite set of numbers with the symbol \(\Z\); but in a computer program, we cannot represent infinite sets in the same way. Instead, we’ll use a property of divisibility to restrict the set of numbers to quantify over: when \(n \neq 0\), every number that divides \(n\) must lie in the range \(\{-|n|, -|n| + 1, \dots, |n| - 1, |n|\}\). We’ll actually prove this property later on!

But the next question is, how do we represent the set \(\{-|n|, -|n| + 1, \dots, |n| - 1, |n|\}\) in Python, when the \(n\) is given as a parameter? We can use the range data type: Remember the asymmetry here: the start argument is inclusive, but the end argument is exclusive.

possible_divisors = range(-abs(n), abs(n) + 1)

And then we can replace \(\Z\) by this variable in the definition of divisibility to obtain \(\exists k \in possible\_divisors,~ n = kd\). We can now translate this directly into Python code using what we learned earlier this chapter:

def divides(d: int, n: int) -> bool:
    """Return whether d divides n."""
    possible_divisors = range(- abs(n), abs(n) + 1)
    return any({n == k * d for k in possible_divisors})

Now let’s turn our attention to the definition of \(\mathit{IsPrime}\):

\[\mathit{IsPrime}(p): p > 1 \AND \big( \forall d \in \N,~ d \DIV p \IMP d = 1 \OR d = p \big), \qquad \text{where $p \in \Z$}.\]

Here’s a start for translating this definition into a Python function:

def is_prime(p: int) -> bool:
    """Return whether p is prime."""

Once again, we have a problem of an infinite set: \(\forall d \in \N\). We can use the same property of divisibility as above and note that the possible natural numbers that are divisors of p are in the set \(\{1, 2, \dots, p\}\). This is simpler than the version above because \(p \geq 1\). The quantified statement is a bit harder to translate because it contains an implication, so here we recall what we discussed in 3.3 Filtering Collections to use the if keyword in a comprehension to model implications. Here is our complete implementation of is_prime:

def is_prime(p: int) -> bool:
    """Return whether p is prime."""
    possible_divisors = range(1, p + 1)
    return (
        p > 1 and
        all({d == 1 or d == p for d in possible_divisors if divides(d, p)})
    )

Notice that just like the mathematical definition, in Python our implementation of is_prime uses the divides function. This is a great example of how useful it can be to divide our work into functions that build on each other, rather than writing all of our code in a single function. As we learn about more complex domains in this course, we’ll see this pattern repeat itself: definitions will build on top of one another, and you should expect that your functions will build on one another as well.

Divisibility and the remainder operation

You might have noticed that our definition of divides, though faithful to the mathematical definition, is not the same as how we’ve previously determined whether a number is divisible by 2 (i.e., is even).

def is_even(n: int) -> bool:
    """Return whether n is even."""
    return n % 2 == 0

In this case, we check whether n is divisible by 2 by checking whether the remainder when n is divided by 2 is 0 or not. It turns out that for non-zero \(d \in Z\), checking remainders is equivalent to the original definition of divisibility:

\[\forall n, d \in \Z,~ d \neq 0 \Rightarrow (d \mid n \Leftrightarrow n~\%~d = 0).\]

Note that when \(d = 0\), the remainder \(n~\%~d\) is undefined, and so we really do need the \(d \neq 0\) condition in the above statement.

We can use this observation to write an alternate implementation of the divides function:

def divides2(d: int, n: int) -> bool:
    """Return whether d divides n."""
    if d == 0:
        # This is the original definition.
        possible_divisors = range(-abs(n), abs(n) + 1)
        return any({n == k * d for k in possible_divisors})
    else:
        # This is a new but equivalent check.
        return n % d == 0

You might also notice that the d == 0 case is quite special: according to our definition of divisibility, when d == 0 we know that d divides n if and only if n == 0:

\[\forall n, d \in \Z,~ d = 0 \Rightarrow (d \mid n \Leftrightarrow n = 0)\]

We can use this to greatly simplify the if branch in our divides2 function:

def divides3(d: int, n: int) -> bool:
    """Return whether d divides n."""
    if d == 0:
        # This is another new, equivalent check.
        return n == 0
    else:
        # This is a new but equivalent check.
        return n % d == 0

Our implementation in divides3 meets the same function specification as the original divides, but has a much simpler implementation! It is also much more efficient than the original divides, meaning it performs fewer calculations (or computational “steps”) and takes less time to compute its result. Intuitively, this is because the original divides function used the value range(-abs(n), abs(n) + 1) in a comprehension, and so the number of expressions evaluated gets larger as n grows. This is not the case for divides3, which does not use a single range or comprehension in its body!

What this also means is that we can speed up our implementation of is_prime simply by calling divides3 instead of divides:

def is_prime(p: int) -> bool:
    """Return whether p is prime."""
    possible_divisors = range(1, p + 1)
    return (
        p > 1 and
        all({d == 1 or d == p for d in possible_divisors if divides3(d, p)})  # <-- Note the "divides3"
    )

This is a very powerful idea: we started out with one implementation of the divisibility predicate (divides), and then through some mathematical reasoning wrote a second implementation (divides3) that was logically equivalent to the first, but simpler and faster. But because divides and divides3 were logically equivalent, we could safe replace divides with divides3 in the implementation of is_prime to make it run faster, without worrying about introducing new errors!

The idea of swapping out implementations will come up again and again in this course. As the functions and programs you write grows larger, efficiency will be an important consideration for your code, and so it will be common to start with one function implementation and eventually replace it with another. We’re only touching on these idea here with a relatively simple example, but we will talk formally about program efficiency in a later chapter.