An Analysis of Lazy and Eager Evaluation in Python

-or-

Python: Not so Lazy as we Thought

Summary: Lazy? Not even in the slightest.

In a recent thread (http://reddit.com/r/programming/info/65mm7/comments) we discussed the abuses of embedding functions in data structures. A couple people went "oooh" and rejoiced on the possibility of lists of lazy lambdas.

I presented a simple hack. It was a one line factorial function:

fac = lambda n: [1, n*fac(n-1)] [n>1]

It is a stupid function, not tail recursive and guaranteed to overflow eventually. But the function definition passes, and it is syntactically valid Python. I also commented that it should not be run, because running it for any value causes infinite recursion. Finding the factorial of 1 should not make an infinite loop. Something is amiss.

Maybe lists are not lazy? A simple test confirms this:

>>> a = []
>>> b = []
>>> [a.append(1), b.append(2)][0]
>>> a
[1]
>>> b
[2]

So lists are not lazy. How about tuples and dictionaries?

>>> a = []
>>> b = []
>>> (a.append(1), b.append(2))[0]
>>> a
[1]
>>> b
[2]

>>> a = []
>>> b = []
>>> {0: a.append(1), 1: b.append(2)}[0]
>>> a
[1]
>>> b
[2]

Not lazy at all! Python has quite possibly just nominated itself as the most eagerly evaluated programming language, as every value in a data structure is evaluated when retrieving one value.

Looking at the previous factorial example, it is now obvious why the recursion never stopped looping. It would also seem quite plain that Python is incapable of any neat functional tricks.

For the most part, that is correct assessment. I've seen Mark Dominus wield functional perl-fu and run circles around Python's limited abilities. But my previous examples were flawed. The list/tuple/dictionary examples did not return anything and were heavy on the side effects. Not functional at all, and thus not really a fair test.

Dictionaries of functions sound pretty useful, though. Let's build something. First, we'll justify them with a contrived example: temperature conversion, done in a beginner's OOP fashion:

class Temperature:
    def __init__(self, k=0):
        self.k = float(k)
    def to_k(self):
        return self.k
    def to_c(self):
        return self.k - 273.15
    def to_f(self):
        return self.k * 1.8 - 459.67

Now, what if you want a sort of interactive REPL? Extend the class with an input handler, ignoring all errors:

class Temperature:
    def __init__(self, k=0):
        self.k = float(k)
    def to_k(self):
        return self.k
    def to_c(self):
        return self.k - 273.15
    def to_f(self):
        return self.k * 1.8 - 459.67
    def convert_to(self, unit):
        if unit == 'k':
            return self.to_k()
        if unit == 'c':
            return self.to_c()
        if unit == 'f':
            return self.to_f()

def user_readeval(t):
    return t.convert_to(raw_input('convert to: '))

This is just the read-eval section, you'd need more boilerplate for the print-loop. Altogether, it is really messy. Let's rebuild it using dictionaries:

class Temperature:
    def __init__(self, k=0):
        self.k = float(k)
    def convert_to(self, unit):
        convert = {
            'k': self.k,
            'c': self.k - 273.15,
            'f': self.k * 1.8 - 459.67 }
        return convert[unit]

def user_readeval(t):
    return t.convert_to(raw_input('convert to: '))

Good news is that this example works. There is no infinite recursion, no horrible side effects. It looks neater and is much easier to expand upon. You can keep on scaling this up to a full interpreter. But please don't do this. Since each element is of the data structure is evaluated, there will be a linear slowdown for each instruction added to the interpreter. To bring this into stark clarity, try this:

>>> import time
>>> ['no pause', time.sleep(1), time.sleep(2)][0]
'no pause'

There is a three second delay before printing 'no pause'. Not acceptable for complex systems.

Taking all these tricks into account, is it possible to fix the simple factorial example above? Sure. You can use an inline if/else expression, or you can abuse nested lists. (That is really ugly and uses python's ability to append a list inside itself in order to simulate a very large stack while not getting confused by the infinite recursion. I'm not going to post it here, since writing it nearly made my eyes bleed.) In nutshell, don't use recursion for anything were the recursion depth is linear.

(Ugly hack presented for completeness; proceed at own risk.)

Instead I give you the simplest useful factorial, one without an upper bound limit:

from operator import mul

def xlrange(start, end):
    i = int(start)
    while i < end:
        yield i
        i = i + 1

def fac(n):
    return reduce(mul, xlrange(1, n+1))

Where xlrange is used to get around xrange's utter bafflement of long integers.

(All code presented in Python 2.5.1)

Linkback:
  http://www.pages.drexel.edu/~kmk592/rants/lazy-python/

Printer friendly links:
  http://reddit.com/r/programming/info/65mm7/comments
  http://hop.perl.plover.com/
  http://www.pages.drexel.edu/~kmk592/rants/lazy-python/uglyhack.txt

History:
  2008/02/03 uploaded


<center> <br> Instead of a table, which I find lame<br> This page uses a single i-frame<br> But you don't have support<br> To which you'll surely retort:<br> "No reverse compatibility? Shame!" </center>