Lazy Programming - Not Just for Lazy Programmers

Everybody is lazy sometimes.  Klaus Sutner, one of my two professors for my Fundamental Data Structures and Algorithms class (the other being Danny Sleator, co-inventor of splay trees under whom I am now a teaching assistant), loved stating that in Computer Science, we as programmers should strive to be lazy in the sense that we should never do work unless we absolutely must.  This principle is the motivation for lazy programming.

All languages were not created equally.  The ability to use the power of lazy programming illustrates this concept nicely.  You would be hard-pressed to find a programming language nowadays that didn't support short-circuit evaluation for conditional statements.  This feature is, at its very core, lazy.  Why should we take time to do that extra computation to evaluate the remaining statements in the conditional when we know that, regardless of their value, the statement will evaluate to true (or false)?

But what happens when we extend this concept further than most languages take it?  Let's begin with Python.  Python has an interesting language feature called generators.  These generators are essentially methods that return iterators.  Iterators are nice in that they only compute up to the next value they need to return.  Thus we can custom define methods to return iterators that can potentially iterate over an infinite sequence.  Let's look at them in action:

def nats():
    i = 1
    while True:
        yield i
        i += 1

n = nats()

for i in range(0, 10):
    print n.next()

The use of the keyword "yield" is...well, key.  This keyword lets Python know that the method returns a generator.  This implementation is right out of the pages of Knuth's section on coroutines in The Art of Computer Programming.  At each invocation of the next() method, the function picks up exactly where it left off, allowing us to generate as many naturals as we feel like, as long as it isn't all of them.

Which brings me to my next point--the itertools module for Python, specifically the ifilter() function.  Since we have essentially just created a representation all the natural numbers, we could, using ifilter(), derive, say, all of the odd natural numbers in the following manner:

import itertools

n = nats()
n = itertools.ifilter(lambda x: x % 2 != 0, n)

for i in range(0,10):
    print n.next()

It's a short step from filtering all of the numbers divisible by two out to filtering all of the numbers divisible by all of the previous primes out.  Thus, we have reached the Sieve of Eratosthenes:

def primes():
    n = nats()
    # get rid of the leading 1
    n.next()
    while True:
        newPrime = n.next()
        yield newPrime
        n = itertools.ifilter(lambda x, p=newPrime: x % p != 0, n)

p = primes()

for i in range(0, 10):
    print p.next()

And there you have it.  Lazy programming allows us to retrieve, one by one, as many primes as we want--if we're willing to wait long enough, that is.