Laziness is a virtue (in programming)

Introduction

One of the things I really appreciate about Python is that it allows me to explore different programming styles. When I started with Python (coming from a C/C++/Java background) I would mostly use procedural style constructs.

These days, however, I am usually inclining towards a more functional pogramming style.

One of the key books that swayed me towards the latter was Mark Pilgrim’s “Dive Into Python”, one of the best (technical) books I have read so far. If you haven’t come across it yet, you should definitely take a look at it.

Another Python gem you may want to check out while experimenting with functional programming ideas is the itertools module.

Example

In the brief section of code that follows below I am contrasting the procedural versus the functional pogramming style through an example in which I am interested in obtaining the first in a (potentially large) range of numbers whose 8th root is an integer.

  1 from math import (pow, modf)
  2 from itertools import dropwhile
  3 
  4 def calculate(x):
  5     """calculates the 8th root of the number 'x'"""
  6     return(pow(x, 0.125))
  7 
  8 def wanted(v):
  9     """integer check: returns 'True' if fractional part of a number is 0"""
 10     return(not modf(v)[0])
 11 
 12 def unwanted(v):
 13     """returns 'False' if fractional part of a number is > 0"""
 14     return(modf(v)[0])

The lines 16-25 show a procedural style function using a loop and related control flow constructs to get the job done.

 16 def proceduralStyle(f, t):
 17     """
 18     finds the first in the range of numbers [f..t[ whose 8th root is an
 19     integer; procedural style
 20     """
 21     for x in xrange(f, t):
 22         v = calculate(x)
 23         if wanted(v): break
 24     else: v = None
 25     return(v)

The functional style solution (see lines 27-34 below) uses the dropwhile() method (from the itertools module) to get rid of any unwanted initial values (line 32).

Please note also how a generator expression (as opposed to normal list comprehension) is used (on line 32) to achieve lazy evaluation behaviour.

The syntactical differences are minute (parentheses versus square brackets) but the effects are huge.

A normal list comprehension will construct the entire list (and perform any calculations needed in the process) before completing. A generator expression on the other hand is comparable to an iterator, values are returned in piecemeal fashion and calculations are performed only as needed.

 27 def functionalStyle(f, t):
 28     """
 29     finds the first in the range of numbers [f..t[ whose 8th root is an
 30     integer; functional style
 31     """
 32     r8iter = dropwhile(unwanted, (calculate(x) for x in xrange(f, t)))
 33     try: return(r8iter.next())
 34     except StopIteration: return(None)

Finally, by experimenting with the source code we can see that lazy evaluation is in effect for the functionalStyle() function. It returns straightaway with the result anticipated (256 is the first number in the range whose 8th root is an integer (2)).

  1 bbox33:published $ python
  2 Python 2.4.4 (#1, May 22 2007, 13:30:14)
  3 [GCC 4.0.1 (Apple Computer, Inc. build 5367)] on darwin
  4 Type "help", "copyright", "credits" or "license" for more information.
  5  >>> import evaltest2
  6  >>> from time import asctime as t
  7  >>> print t(); evaltest2.functionalStyle(2, 50000000); print t()
  8 Sun May 27 10:33:18 2007
  9 2.0
 10 Sun May 27 10:33:18 2007
 11  >>> print t(); evaltest2.proceduralStyle(2, 50000000); print t()
 12 Sun May 27 10:33:30 2007
 13 2.0
 14 Sun May 27 10:33:30 2007
About these ads

14 thoughts on “Laziness is a virtue (in programming)

  1. In Ruby, there’s a “find” function which returns the first value for which the block’s result is true:

    (2..400).find{ |x| (x ** 0.125) % 1 == 0 }
    => 256
    256 ** 0.125
    => 2.0

    This example is also lazy, because the (2..400) is like xrange(2, 400) and the find stops as soon as the value is found.

    Is there no such function in Python?

  2. Hello Robin,

    thank you very much for your comment! I guess the closest thing in Python would be the ifilter() function (in the itertools module).

    The respective implementation would be as follows:

    def functionalStyle2(f, t):
        try: return(ifilter(wanted, (calculate(x) for x in xrange(f, t))).next())
        except StopIteration: return(None)

    Or to put it more simply:

    >>> ifilter(lambda v: not modf(v)[0], (pow(x, 0.125) for x in xrange(2,400))).next()

    2.0

  3. @Robin

    no, python doesn’t have it, although many other languages do (i know common lisp and c++ stl have them). i asked #python@freenode.net why the standard library doesn’t have a generalized find-if function. they flamed me from every direction–”that would be inefficient”, “you can iterate through all matches with a generator”, etc. then some dude said “i never want that function to be in MY standard library”. what a bunch of jokers. i just wanted to find the first match in a last with a lambda expression predicate without having to roll my own find-if.

  4. Err…laziness is a virtue, but I’m not sure you’ve demonstrated that, since your “proceduralStyle” function also uses a lazy approach: xrange. So the “functionalStyle” function differs mostly in its anonymity, in that it doesn’t name the result of each calculate(x) like the proc style does with the name “v”.

    Despite this, the proceduralStyle function as written is actually slightly faster in my quick tests than the functionalStyle one. And since I don’t have to guess/remember what “dropwhile” does, the proceduralStyle is more readable. And, in the procedural style, I can inline those “calculate” and “wanted” functions and get a 1400% speed boost.

    Functional programming as a style has huge benefits (provability and composability, for example), but laziness is really a separate issue.

  5. I suppose there’s more to the problem than you’ve stated, but this seems to be a painfully slow way to solve it. Why not take the 8th root of the first number in the range, round up to the next integer, and then compare successive integers n**8 with the numbers in your range?

  6. @Robert:

    Thank you very much for your comments! The points you are making are very valid.

    My focus wasn’t so much on performance. I merely meant to:

    – contrast the procedural programming style against the functional one
    – point to a common pitfall (i.e. the usage of lists for aggregating computationally “expensive” values, particularly when one only needs a small subset of these) and a better way to do it (using generator expressions)

  7. @John:

    First of all I’d like to thank you for the interesting technique you’re pointing out.

    However, in order to make the advantages of lazy evaluation more apparent, I intentionally chose an operation that’s “heavy weight” and computationally intensive: hence my choice of 8th root and the “plain vanilla” solution.

  8. Basically I agree that the functional approachi has some really nice qualities, but that example is not really doing it full justice. Regarding the ruby find method, this is how you do the same in python:
    >>> (i**0.125 for i in xrange(2,500000000) if not i**0.125 % 1).next()
    2.0

  9. @Ants Aasma:

    That’s a nice solution. However in the cases where no value is found the next call will raise a StopException whereas a return value of None would be more suitable in many situations. Although it’s easy to wrap such functionality into a function it would be handy to have something like that available.

  10. @Martin
    no no, null pointer exceptions are evil! >:-|

    rather
    default=0
    try:
    result=(i**0.125 for i in xrange(2,500000000) if not i**0.125 % 1).next()
    except StopException:
    result=default

  11. @martin and nes:

    Guys, sorry for being pedantic, but you surely meant the StopIteration exception. I don’t think there is a “StopException” in Python.

  12. Pingback: links for 2007-07-03 « PaxoBlog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s