Beyond type errors

October 2014 — 4 minute read

Ways of calling a piece of code incorrectly.

Consider this Python function:

def factorial(n):
    """Returns n! (n factorial)"""
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Provided that this code is correct, what are kinds of errors (bugs) that can happen when this function is used?

First that come to mind are type errors. The factorial function could be called with something that’s not a number — for example, a string. Since Python is dynamically-typed, that would result in a runtime exception:

>>> factorial("hello")
TypeError: cannot concatenate 'str' and 'int' objects

Some languages are statically typed so the same type error would be caught earlier, at compile time. For example, in Haskell:

factorial :: (Num a) => a -> a
factorial n = if n == 0 then 1 else n * factorial (n - 1)

Compiling a program that attempts to use factorial with a string would result in a compile-time error such as:

No instance for (GHC.Num.Num [GHC.Types.Char])
arising from a use of `factorial'

Statically-typed languages have the advantage that, when properly used, they can help detect most of the type errors as early as possible.

The second class of errors are value or domain errors. These errors occur when the code is called with arguments of proper types, but unacceptable values — in other words, when the function is called with arguments outside its domain. The factorial function, in math, is defined only for positive integers. In code, if the caller supplies -1 as the value of n, it will raise a value error.

The Python function defined earlier will return an incorrect result 1. The Haskell counterpart will run for a long time, consume all available stack, and crash.

The usual way to deal with this problem is by practicing defensive programming, that is, by adding manual guards. The functions might be rewritten as:

def factorial(n):
    """Returns n! (n factorial)"""
    if n < 0:
        raise ValueError('factorial is not defined for negative '
            'integers')
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

factorial :: (Num a, Ord a) => a -> a
factorial 0 = 1
factorial n
    | n < 1 = error "factorial is not defined for negative integers"
    | otherwise = n * factorial (n - 1)

in Python and Haskell, respectively. Note that in both cases, this is a runtime error — it’s not possible to detect it at compile time[0].

A formalization of the concept of guards gives us design by contract, in which classes and functions can specify preconditions, postconditions and invariants that must hold in the correct program. The checks are specified in ordinary code and are also run in runtime. Design by contract was introduced in Eiffel but, sadly, never gained mainstream adoption.

The third class of errors are more insidious, to a point where it’s not clear whether they should be called errors at all: using a piece of code outside the context it’s intended for. Often, the code works, but has performance problems, and it is hard to determine where the error boundary is.

To continue with the factorial example, using either the Python or the Haskell function to calculate 1000000! won’t work, or it’ll run for a long, long time and use huge amount of memory, depending on the computer it is executed on.

For a more realistic example, consider a piece of code using Django ORM to fetch data from the database:

class Book(models.Model):
    author = models.ForeignKey(Author, related_name='books')
    published = models.BooleanField(default=False)
    ...

class Author(models.Model):
    ...
    @property
    def published_books(self):
       return self.books.filter(published=True)

By itself, it looks rather solid. The results are filtered by the database and only the interesting ones are returned. Also, the Author object hides the complexity of using the correct query[1]. But then there comes the caller[2]:

def list_authors():
    authors = Author.objects.all().prefetch_related('books')
    for author in authors:
        print author.name
        for book in author.published_books:
            print book.title

Now, the caller function did try to do the right thing. It told Django it would need to use the related table (books). But what it didn’t know is how exactly the published_books property was implemented. It just so happens that the implementation ignores already prefetched books in memory and loads them again from the database - at one SQL query per author.

In both examples[3], the error is not in the function itself, but in the calling code — it has failed to meet some basic assumption that the called code makes. However, these assumptions are impossible to encode in the code itself. The best one can do is to list them thoroughly in the documentation and hope the programmer calling the functions will read it and keep it in mind.

In all three classes of errors, the caller invoked the function in a way that violated some of its assumptions — either about argument types or values, or about the wider context it was running in.

Type errors are easy to catch, especially in statically-typed languages. Value errors require more work (defensive programming or contracts), and are thus often ignored until they happen in production, but they can be dealt with. (Mis)using the code in a different context is something that’s not even widely recognized as an error, and the best approach in handling them, usually boils down to “don’t do this” notes in documentation.

Can we do better? Can we redefine component interfaces to go beyond types or even values? To describe, guarantee and enforce all behaviour, including time and space complexity, and interactions with the outside world? Would it make sense at all?

I don’t know, but it’s an interesting line of thought.

Notes:

[0] At least not without making it very impractical to use, or until languages with value-dependent types, such as Idris, become mainstream.

[1] We could have done the same thing in a ModelManager for Book that would wrap the query. The example would have been a bit longer but the point would still stand.

[2] Example is a normal function instead of Django view to ease the pain for non-Django users reading the article.

[3] For another extended example, read my article about Security of complex systems.