Review of Tkinter GUI Application Development Hotshot

Here's my Amazon review of a new book on Tkinter.

Good big picture view of Tkinter, some problems in details, overly Windows specific

Packt provided me a complimentary ebook copy of the book for review purposes. This was in response to some concerns I had about whether the book was overly focused on Windows; I’ll address that below as a part of my review.

Tkinter GUI Application Development Hotshot is an introduction to Tkinter, requiring no previous experience with Tkinter but some experience with Python. The book is structured as a series of projects, nominally with each chapter being a distinct project. The first chapter is actually a collection of small examples showing how key elements of Tkinter work, chapters 2 through 6 each describe a separate application in detail, and chapter 7 describes several smaller applications more briefly. There are two appendices as well, the first of which (“Miscellaneous Tips”) pretty clearly should have been the final chapter of the book; the conclusion of the book is actually in this appendix. The second appendix constitutes a short Tkinter reference. Support code for the projects can be downloaded from Packt, and really must be downloaded, as the programs are wisely not presented in full in the book for each change to the application.

The approach of the book is to give a big picture view of Tkinter in the first chapter, describing its structure of widgets, geometry management, events and callbacks, and using Tkinter variables to provide communication between the widgets and your program. The later chapters then introduce different types of widgets and techniques for structuring GUI applications made in Tkinter. It is at this big picture level that the book seems to be strongest. The author doesn’t attempt to be encyclopedic, so there was a suitable focus on the relevant ideas, rather than details that can be checked in reference material. 

Turning to more specifics, flaws become apparent in the book. Despite a generally clear text, there are several points where formatting problems or lack of clarity cause confusion. A particularly unfortunate example of this is found in the discussion of callbacks in the first chapter: due apparently to incorrect indentation, the example of how to define a callback is nonsensical. It’s followed by mention of using lambda functions to deal with callbacks that take arguments, but the syntax given for lambda functions is wrong. There are several other instances in the text where general examples have misleading or flatly incorrect presentations, sometimes in quite important sections, such as the description of the general form of widget instantiation (chapter 1) and the specification of tags to be used with indexing in the Text widget (chapter 2). I don’t think experienced Python programmers would have much trouble with any of these, but beginners might. 

One of the strengths of Tkinter is that it is cross-platform, portable across operating systems. The author note this strength, but develops everything on Windows 7, claiming that “since Tkinter is truly cross-platform, you can follow along on Mac or Linux distributions without any modifications to our code.” As Tkinter’s cross-platform nature is an important part of why I’m considering using it, I decided to test the claim by working along exclusively on my Mac while using the same Python and Tcl/Tk versions as the author.  

The claim is flatly untrue. 

Most of the projects have visual issues, and several don’t work correctly. Buttons resize differently, so example of the pack geometry manager is rather confusing, and there isn’t a clear discussion of how it works outside this example. The text editor in the second chapter just has display issues, but these include such things as wrapped lines leading to hidden characters and the line numbering being incorrectly sized so that the lines are, effectively, numbered wrong. A short sample program in the second chapter tries to illustrate how different types of top-level windows should behave, but their described behavior isn’t observed. Mouse buttons numbering and appropriate modifier keys for keyboard shortcuts are platform specific, but without any discussion of this in the book. 

The third chapter (which is available as a sample on the Packt site), presenting a drum machine application, is a complete disaster. It depends on a third-party module called pymedia. This appears to be dead, not having been updated since 2006. It is claimed to work with Windows and Linux, but not Mac OS X or other Unix systems. It’s not in Homebrew. Searching for build information is not promising. Trying to build it doesn’t work. Just considering the interface isn’t much better. The author uses an array of buttons to set the drum patterns, registering button presses to manually set the states of the beats in the pattern. With the Mac versions of the widgets, the author’s code doesn’t correctly color the buttons to show the pattern, so you can neither see nor hear the pattern. And this because the author fakes a widget with two states using buttons, rather than using a checkbox which actually has two states. 

The chess program in chapter 4 seems to work fine. The audio player in chapter 5 does not, raising a type error in a division. This uses pyglet to actually play the audio files, but a function that needs to return a number instead returns None. Whether this is due to a platform dependency or due to a difference in the pyglet version I installed (with pip) compared to the unspecified version the author used, I do not know (and by this point in the book, was not inclined to try to figure it out). The drawing program in chapter 6 seems to work, more or less. I didn’t try the applications in chapter 7.

The author seems to have taken the approach that if it works on his system, it must be right. But it isn’t right if you take cross-platform function as part of working right, and platform dependence is only addressed in the most cursory of fashions.

Overall, the value of the book seems likely to depend strongly on the systems you want to work on. I’d probably give the book 4 out of 5 stars if you just care about Windows, and maybe 2 stars if you want to produce something cross platform. So I’ll give it three stars overall: a useful overview of Tkinter that fails to adequately treat an important use case. I have not tried the programs on Linux; I’d advised Linux users to try out the sample code and compare the results to what previews are available. 

W3R-7: Summary and Assessment

In the What's Wrong With Reduce series, I've attempted to resolve contrasting views of the usefulness of higher order function called reduce or fold. By examining the origins of reduce, we saw that it is an abstraction over a particular recursive pattern of control flow. Further, reduce can be readily defined in Python.

However, it is easy to find cases where reduce works well for a functional programming language but poorly in Python. In essence, reduce is an abstraction over a common pattern for functional programming languages that is uncommon in imperative programming languages like Python. Instead, a much narrower selection of Python procedures map well onto the reduce control abstraction.

By examining control flow patterns actually used in Python, a more appropriate higher order procedure¹, app, was identified as an alternative to reduce. Several common control flow patterns cannot be captured by app, so a dual gen procedure was also defined.

Between app and gen, we can define many functions to process or create iterators. However, an important question remains: should we use app or gen? I'd have to say that it isn't worthwhile. Both app and gen are abstractions over imperative patterns, depending crucially on side effects. As a consequence, it is of equal importance to understand the order in which, say, app processes the elements of an iterator. Thus, app fails to provide any conceptual benefit over just using a for loop—in contrast, functional programming with reduce, map, and other higher order functions lets you ignore the order in which things are done.

That said, I use and define higher order procedures all the time in Python. I just define them as (generator) functions using imperative constructs like for or while loops. Also, like the itertools module, my higher order procedures typically take iterators as arguments or return them as results. So long as iterators only need to be used once, this looks a lot like functional programming. Really, it is closer to dataflow programming.

Having an effective alternative to reduce is relatively unimportant for this iterator-intensive programming style. Far more useful would be higher order procedures that simplify composing multiple procedures taking and returning iterators. The overall result should be more like constructing a shell pipeline instead of the extensive nesting of procedure calls currently seen.

---

¹ For clarity, I distinguish here between higher order functions and higher order procedures. Functions should really be mathematical functions, i.e., no side effects, while procedures are more general.

W3R-6: Dualing Reduce

By examining actual programs, we saw that reduce is the wrong control abstraction in many cases. By starting from programs instead of starting with the abstractions, we saw that app is a more natural control abstraction for Python. The comparatively few cases where reduce is right were handled by introducing an adaptor Accumulator, with app and Accumulator being sufficient to define reduce.

Unfortunately, the approach of defining an adaptor to get app to do what we want leaves out an extremely common way that for loops get used. Consider defining map in terms of the lazy imap¹. It looks something like:

def map_lazy(function, iterable):
    return list(imap(function, iterable))

def imap(function, iterable):
    for x in iterable:
        yield function(x)

All the real work is now done in imap. However, imap cannot be written using app, since there is no way to pass in a function that will yield values we can use².

In imap, both for and yield express control flow, distinct from that given by app. Similarly, consider defining filter using an ifilter:

def ifilter(predicate, iterable):
    for x in iterable:
        if predicate(x):
            yield x

In ifilter, we have another pattern of control flow, regulated with an if statement. Thus, we need an additional higher order procedures if we want to abstract over these patterns. It should be, informally, a dual to app, creating an iterator instead of consuming one.

I don't know of a standard name for the dual procedure—it's a generator (probably confusing to call it that) and has a great deal of similarity to unfolds. At the risk of some confusion, I'll go with the short name of gen. A possibility for writing it is:

def gen(init, update, shouldEmit, emit):
    state = init
    while True:
        if shouldEmit(state):
            yield emit(state)
        update(state)

Note that I've included no explicit treatment of the internal state, so gen can in principle handle any sort of internal state, be it an iterator or otherwise.

I don't think I've seen anything like gen in Python code. Instead, generator functions are written out explicitly on a case-by-case basis. Looking at how we'd implement imap with gen suggests why:

def imap_gen(function, iterable):
    def update(state):
        it = state[2]
        state[0] = it.next()
        state[1] = True
    def emit(state): return function(state[0])
    def shouldEmit(state): return state[1]
    init = [None, False, iter(iterable)]
    return gen(init, update, shouldEmit, emit)

There is quite a lot of effort needed to convert iterable into something that we can manage with gen. A relatively simple class could be given to initialize and update the iterator state, paralleling the approach of app plus an adaptor.

Perhaps there is an alternative to gen that would be more natural for iterators as the internal state, while also cleanly handling non-iterable states. However, I'm not going to pursue the matter further, as gen demonstrates how to encode another pattern of control complementary to that encoded by app (or reduce). Taken together, app and gen can accomplish a great deal, creating an iterator with gen and processing its outputs using app.

---

¹ Arguably, we don't need map at all when we have imap. This is the case in Python 3, where map returns an iterator.

² This is a limitation of Python's coroutines. More general (and more complicated) routines, such as those in Lua, do allow such an implementation.

W3R-5: Cart Follows Horse

Higher order functions can be used to implement control abstractions, but that doesn't mean all higher order functions provide useful control abstractions. As we've seen, a useful control abstraction in one language may not work so well in another. In SML, folds are frequently used, while the analogous reduce is uncommon in Python. In retrospect, this doesn't seem so surprising: SML is principally a functional programming language depending on declarative (i.e., recursive) control flow, while Python is a hybrid procedural and object-oriented programming depending on imperative control flow. Where the two languages overlap is where reduce becomes useful, but that overlap is relatively small.

If reduce abstracts over the wrong pattern of control flow, then what are the correct patterns for Python? Let's return to map and see what we can conclude. An imperative definition of map is natural, along the lines of:

def map_imper(function, iterable):
    acc = []
    for x in iterable:
        acc.append(function(x))
    return acc

This version of map utilizes a typical imperative pattern of control, consisting of mutating an object based on values encountered as we iterate though a collection using a for loop. Python has no higher order procedure capturing this imperative pattern; there is such a higher order procedure for Standard ML, where it is called app.

Let's define app for Python. It's easy:

def app(mutate, iterable):
    for x in iterable:
        mutate(x)

Note that app has no useful return value, always returning None, emphasizing that it is always called for its side effects. Using app to define map, we obtain

def map_app(function, iterable):
    acc = []
    def mutate(x): acc.append(function(x))
    app(mutate, iterable)
    return acc

The definition of map_app is no simpler than that of map_imper, but does illustrate an appropriate control abstraction.

Although not needed for map, several generalizations of app could be made. One possibility would be to include optional arguments in order to allow slicing of the iterable:

import itertools
def app(mutate, iterable, start=None, stop=None, step=None):
    if start is not None or stop is not None or step is not None:
        iterable = itertools.islice(iterable, start, stop, step)
    for x in iterable:
        mutate(x)

Many other variations are possible. I'll not suggest which is correct, as that is a question best addressed by empirical analysis of existing code bases.

Now let's reconsider our other motivating example, sum. An imperative implementation is quite similar to that for map:

def sum_imper(numbers):
    acc = 0
    for x in numbers:
        acc += x
    return x

This is the same pattern of control as used in map, mutation within a for loop, but it cannot be expressed using app. In sum, the mutation is that of the variable acc. We can't pass in a variable to app and expect it to be modified, as only the local variable would be changed. That is, app mutates values, while sum mutates a variable.

I can think of two solutions. First, we could introduce another higher order procedure to abstract over what happens in sum. That procedure—function, in this case—is just reduce. Second, we could adapt the value from an immutable number to some mutable object. Which to choose is pretty much a matter of taste. Having two substantially similar control flow mechanisms may be undesirable, but reduce is also a known quantity. The adaptor approach is not as well explored, but may turn out to be more natural. Let's take a look.

When combined with app, the adaptor needs to produce the same effect as reduce. Since app is handling the control flow, the adaptor just needs to handle the accumulation. One possible definition is to use an Accumulator class, defined as:

class Accumulator(object):
    def __init__(self, function, init):
        self.function = function
        self.value = init

    def update(self, x):
        self.value = self.function(self.value, x)

As an example of usage, here is an accumulator for summation:

>>> acc_sum = Accumulator(operator.add, 0)
>>> acc_sum.update(4)
>>> acc_sum.value
4
>>> acc_sum.update(37)
>>> acc_sum.value
41

Putting together an Accumulator instance and app, we can give another definition of sum:

def sum_adapt(numbers):
    acc = Accumulator(operator.add, 0)
    app(acc.update, numbers)
    return acc.value

As a second example, here is yet another definition of a fold:

def fold_app(function, init, iterable):
    acc = Accumulator(function, init)
    app(acc.update, iterable)
    return acc.value

Personally, I find these definitions to be quite natural and appealing; app and Accumulator would fit in well with my programming style.

W3R-4: What's Wrong With Reduce.

We've used fold—our model of reduce—to define sum, product, and a function min3 that finds the three smallest elements in a list. We have not yet used fold to define map, which was one of the functions we used to motivate fold in the first place. Let's do that now¹.

With linked lists, it is easy:

def reverse(lnkLst):
    def app(acc, x): return Cons(x, acc)
    return fold(app, Nil(), lnkLst)

def map_ll(function, lnkLst):
    def app(acc, x):
        return Cons(function(x), acc)
    return reverse(fold(app, Nil(), lnkLst))

I've introduced a reverse function to preserve the order, as we didn't bother to define a right-to-left foldr, just the left-to-right fold that parallels Pythons reduce. Otherwise, the definition is straightforward. The accumulating function needs to create a new linked list by transforming values from the source list. This is a perfect match for fold.

The same idea can be applied to Python's lists (actually arrays):

def map(function, lst):
    def app(acc, x):
        return acc + [function(x)]
    return fold(app, [], lst)

However, this is quite poor. This implementation of map creates a new list at each step, and thus performs very badly—O(N2) time, where N is the length of the list, instead of the O(N) that should be taken. Even though fold—i.e., reduce—is applicable to any iterable, that does not mean it has captured a useful pattern for every iterable!

So what went wrong? Folds are a good way to break down data structures, which led us to iterators, the standard way to take apart data structures in Python. That worked fine, and we really have no reason to expect it to suddenly fail. However, we have introduced something new: we're also using reduce to build up a new data structure—specifically, a new list. This works fine with the functional link list but fails badly with the imperative arrays.

To see this, let's expand the fold out again, using fold_iter (introduced earlier) to do it:

def map_iter(function, lst):
    acc = []
    for x in iterable:
        acc = acc + [function(x)]
    return acc

The final form is just not how it should be done. In other words, fold is an abstraction over the wrong pattern!

What has happened is that we've gone about things entirely backwards. In a functional programming language like SML, folds are useful. That usefulness was (apparently) the basis for thinking reduce should be useful in Python. However, folds are useful in functional programming languages because they capture a particular pattern of recursion that is common in functional programming. That pattern of recursion is not common in Python, so we have no reason to conclude that reduce will be useful².

---

¹ For simplicity, I'll only allow a single list to be given as an argument to map, unlike the Python built-in function.

²Nor may we conclude on logical grounds that reduce will not be useful. Experience suggests it is not particularly so, but we don't know if that is something fundamental about reduce or something incidental, such as the documentation.

W3R-3: Object-Oriented Reduce

We now have worked through deriving reduce in Python. In doing so, we have defined two closely related functions, fold¹ and scan. Since they're so similar, it makes sense to briefly digress and consider bundling them together into a class. I won't make much use of the class in future installments of this series, but it is an interesting exercise to consider alternative definitions that might be a better fit to Python.

Define:

class Fold(object):

    def __init__(self, function, init):
        self.function = function
        self.init = init

    def __call__(self, acc, x):
        return self.function(acc, x)

    def scan(self, iterable):
        function = self.function
        acc = self.init
        yield acc
        for x in iterable:
            acc = function(acc, x)
            yield acc

    def fold(self, iterable):
        for x in self.scan(iterable): pass
        return x

The Fold class is defined to take the function and initial value for the accumulator when the class is instantiated. This gives us some of the benefits we saw for the curried SML functions.

Putting the Fold class to use, we can define the sum and cumsum functions that we saw last time:

sum = Fold(operator.add, 0).fold
cumsum = Fold(operator.add, 0).scan

Perhaps more useful is to define something like<

add = Fold(operator.add, 0)

and then using add.scan and add.fold as needed.

Indeed, any function of two arguments could be given this treatment, so long as a sensible default (or identity) value can be given. Note that the min3 function from last time is not well suited to this sort of treatment, because it has no clear default value. However, the Fold class presents no additional difficulties over separate fold and scan functions.

---

¹ As a reminder, fold is another name for reduce. We'll continue to reserve reduce as the name of the Python built-in function.

W3R-2: Importing Reduce Into Python

Last time, we took a look at reduce in Standard ML, where it is known as a fold. Now, we'll translate those folds into Python. Let's keep calling them folds, reserving reduce for describing the existing Python function.

The main challenge in the translation process is that Python doesn't have the right data types—Python's lists are actually arrays, not (linked) lists. As a first step, introduce two classes Cons and Nil to define linked lists:

class Cons(object):

    def __init__(self, head, tail):
        self.head = head
        self.tail = tail

    def __iter__(self):
        lnkLst = self
        while True:
            if lnkLst.isNull():
                break
            yield lnkLst.head
            lnkLst = lnkLst.tail

    def __repr__(self):
        return "Cons(%s, %s)" % (repr(self.head), repr(self.tail))

    def isNull(self):
        return False

class Nil(object):

    def __repr__(self):
        return "Nil()"

    def __iter__(self):
        if False:
            yield

    def isNull(self):
        return True

With these classes, we can construct lists in a Lisp-like fashion:

Cons(0, Cons(1, Cons(2, Cons(3, Cons(4, Nil())))))

For convenience, we'll also introduce a function to convert a Python list into a linked list:

def fromList(lst):
    lnkLst = Nil()
    for x in lst[::-1]:
        lnkLst = Cons(x, lnkLst)
    return lnkLst

Using fromList(range(5)) is a lot easier than nesting Cons repeatedly, as shown above.

With linked lists available, it is easy to define a (left) fold:

def fold_recur(function, init, linkedList):
    if linkedList.isNull():
        result = init
    else:
        acc = function(init, linkedList.head)
        result = fold_recur(function, acc, linkedList.tail)
    return result

I'll note two important differences between the SML folds and fold_recur. First, the arguments to the function taken by fold_recur are reversed from those taken by its SML counterpart, in order to match Python's reduce. Second, and far more importantly, fold_recur is terribly broken because it is a tail recursive function, but only has Python's broken support for recursion to draw on. Trying to use fold_recur will cause stack overflows when the list is too long—that is, containing 1000 elements with the default recursion limit¹.

To rectify this problem, we need to transform fold_recur by hand into an imperative version. Fortunately, fold_recur is constructed in an iterative form, so the transformation is easy:

def fold_imper(function, init, linkedList):
    acc = init
    while not linkedList.isNull():
        acc = function(acc, linkedList.head)
        linkedList = linkedList.tail
    return acc

With the imperative definition, our fold will not cause a stack overflow.

Since we've defined linked lists to be iterable, we can still make our fold a bit more elegant:

def fold_ll_iter(function, init, linkedList):
    acc = init
    for x in linkedList:
        acc = function(acc, x)
    return acc

Although fold_ll_iter was obtained by iterating over a linked list, it will work with any iterable. Rewrite it to make that clearer:

def fold_iter(function, init, iterable):
    acc = init
    for x in iterable:
        acc = function(acc, x)
    return acc

Through this process, the deconstruction of a data structure has been shifted from SML fold functions to Python iterators. This is unsurprising: in Python, it is quite standard to use iterators to deconstruct data structures. It is not completely equivalent, but covers many cases.

The iterator approach suggests another modification of fold, which is normally called scan:

def scan(function, init, iterable):
    acc = init
    yield acc
    for x in iterable:
        acc = function(acc, x)
        yield acc

Our scan function processes the list in the same sequence, yielding values accumulated at each step along the way. Using scan, we define one last version of fold:

def fold(function, init, iterable):
    for x in scan(function, init, iterable): pass
    return x

We can use scan and fold to define many useful functions in a simple manner. For example:

import operator
def sum(numbers): return fold(operator.add, 0, numbers)
def cumsum(numbers): return scan(operator.add, 0, numbers)
def product(numbers): return fold(operator.mul, 1, numbers)
def cumproduct(numbers): return scan(operator.mul, 1, numbers)

I think these functions illustrate rather well the difference between fold and scan. In sum, we use fold to total up the numbers in a list, while in cumsum we use scan to generate the partial sums as we proceed through the list. The product and cumproduct functions are similar.

More complex functions are possible as well. Consider finding the three smallest items in a list. This can be done in linear time by iterating through the list and keeping track of the three smallest as we proceed. But that's exactly what fold is for! The accumulator is a collection of the three smallest items, and we just need a function to update that. Putting that together:

def min3(lst):
    def comp(acc, x):
        a,b,c = acc
        if x < a:
            result = x,a,b
        elif x < b:
            result = a,x,b
        elif x < c:
            result = a,b,x
        else:
            result = acc
        return result
    init = sorted(lst[:3])
    return fold(comp, init, lst[3:])

For simplicity, I've assumed that min3 takes a list, but it could easily be modified to work with any iterable.

I've presented a lot of program code in this post, transforming a direct translation of the SML folds into function that are defined in a more natural way for Python. Next time, I'll digress briefly to present an alternative structure that has some practical advantages over what's been shown here, then return to examining why reduce doesn't see much use in Python.

---

¹ In practice, this might as well read that the limit is 1000 elements, end of story. The limit can be increased with sys.setrecursionlimit, but "a too-high limit can lead to a crash."

W3R-1: Origins of Reduce

To begin our investigation of reduce in Python, we need to come to grips with what reduce actually is. I find that the documentation for reduce is rather poor, requiring a fair amount of thinking to determine just what you need to pass in as arguments. Instead, let's examine the origins of reduce to better understand it.

Reduce originates outside of Python. It comes to Python through a contributed patch:

About 12 years ago, Python aquired lambda, reduce(), filter() and map(), courtesy of (I believe) a Lisp hacker who missed them and submitted working patches.

The fate of reduce() in Python 3000
Guido van Rossum, 2005

That's not very helpful, so let's derive reduce by abstracting from some examples. Instead of Lisp, I'll use Standard ML. SML has two key advantages over Lisp: the syntax is more approachable for the uninitiated, and its robust (Hindley-Milner) type system and pattern matching will make things a little clearer. I'll follow the definitions in SML rather than Python, so we'll refer to reduce-like functions as folds, with argument order matching those in the Standard ML Basis Library.

Consider adding up a list of integers. In SML, that list is a linked list, so we'll have a typical recursive solution:

fun sum [] = 0
  | sum (h::t) = h + sum t

I've made use of pattern matching to define sum in terms of two cases, that of an empty list and of a non-empty list. The double colon is a cons operator, joining the head h and tail t of the list.

To define map, a similar recursion scheme is used:

fun map f [] = []
  | map f (h::t) = (f h) :: (map f t)

Map is written as a curried function, so different list processors can be defined by specifying just the function map f, only giving the list later.¹

Just about any function over a list uses the same recursion scheme. Let's extract that recursions scheme into a higher order function called foldr:

fun foldr f acc [] = acc
  | foldr f acc (h::t) = f(h, (foldr f acc t))

Foldr deconstructs a list from right to left, starting with the tail and accumulating the values. As with map, foldr is a curried function.

The type of foldr can make it easier to understand:

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

The first term, in the parentheses, describes the function f; it takes a list element and an accumulator, returning an updated accumulator. The second argument to foldr is an initial value for the accumulator. Third is the list to process. Importantly, the types of the accumulator and the list elements can differ.

We can use foldr to define sum and map. Here's sum:

val sum = foldr Int.+ 0

For map, we'll introduce a helper function and use foldr on that:

fun map f lst = let
  fun maphead(x, acc) = (f x) :: acc
in
  foldr maphead [] lst
end

To get the helper function maphead right, I just looked at the types needed for foldr and wrote the obvious function to satisfy those types.

While foldr allows elegant definition of our two example functions, there is a problem. As written, foldr walks through the entire list before starting to do any work. If the list is long, this can cause a stack overflow. We need a tail-recursive version, leading us naturally to foldl:

fun foldl f acc [] = acc
  | foldl f acc (h::t) = foldl f (f(h, acc)) t

In contrast to foldr, foldl processes the list from left to right, starting with the head. This definition of foldl is tail recursive, so operates in constant space. It can also be used to define a tail recursive foldr by reversing the list before passing it to foldl.

Foldl is substantially similar to reduce in Python. Next time, I'll translate the above definitions to Python, to make the connection transparent.

---

¹ Having a curried map in SML makes for a big conceptual difference from the map in Python. It's quite reasonable to view map as transforming a function from acting on values to a function acting on lists of values, without map itself actually having anything to do with the list.

What's Wrong With Reduce?

Functional programming seems to be on the rise—there's even an O'Reilly book on Haskell, now. I'm not quite sure how that increase in popularity happened, but would guess that Paul Graham's advocacy of Lisp had something to do with it, as did Douglas Crockford's work with JavaScript. I also suspect that the higher-order constructs in Python played an important role, allowing imperative programmers to gradually start using a functional style.

However, there is something curious about the functional constructs in Python. One of the higher-order functions in Python—reduce—seems not to find much acceptance. Probably the best example of this is from the BDFL himself, who wrote:

…almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.



The fate of reduce() in Python 3000

Guido van Rossum, 2005

I don't think the above is out of line with most Python users think, but it clashes severely with conventional thinking of users of functional programming languages.

For example, in an influential paper, John Hughes wrote

…a little modularisation can go a long way. By modularising a simple function (sum) as a combination of a “higher order function” and some simple arguments, we have arrived at a part (reduce) that can be used to write down many other functions on lists with no more programming effort.

and

…functional languages allow functions which are indivisible in conventional programming languages to be expressed as a combination of parts—a general higher order function and some particular specialising functions. Once defined, such higher order functions allow many operations to be programmed very easily. Whenever a new datatype is defined higher order functions should be written for processing it. This makes manipulating the datatype easy, and also localises knowledge about the details of its representation. The best analogy with conventional programming is with extensible languages—it is as though the programming language can be extended with new control structures whenever desired.


Why Functional Programming Matters

John Hughes, 1984

My own experience with ML is quite in line with what Hughes wrote: reduce, or foldl as it is also known, is used all the time, and seems very natural.

Why the difference? I'm not aware of any case where GvR has demonstrated much knowledge of functional programming—maybe he was just speaking outside his area of expertise, and got it wrong? The PLT Scheme people may have thought so, satirizing him shortly after in a (quite funny!) April Fool's Day announcement.

However, I think that explanation is overly facile. Personally, while I use folds in functional languages, I rarely do in Python. I think there are real reasons for that, and will examine them in future blog posts.

Another Skeptical Take on Python 3

Jens Alfke wonders "What’s The Point?" of Python 3.

Via Daring Fireball.

Thoughts on Python 3.0

Python 3.0 has been released. I first used Python at either the end of 1999 or the beginning of 2000. It's with some surprise that I find myself rather ambivalent about what is a major landmark for a tool that I've used on a near-daily basis for almost nine years.

There are a variety of reasons for my ambivalence. Largely, my own programming interests have diverged from the main features of Python. Thus, the significant changes that are present in Python 3 just aren't addressing the shortcomings of Python that affect me. In particular,

• My interest in functional programming has continually increased since I first learned about it in 2002. Python is pretty limited in its support for functional programming, especially in its inability to do tail call optimization and its lack of suitable data structures.
• Learning about functional programming led me to Standard ML and its kin. Reading Harper's Standard ML book profoundly affected how I think about programming, perhaps even more than did reading SICP. Much to my surprise, I found that static typing didn't have to be the nightmare I remembered from C programming. Indeed, typeful programming turns out to be a natural match for how I like to work, with types encoding—and enforcing—a great deal of the assumptions that go into function definition. Python, with its untyped variables, doesn't lend much support to this style.
• Concurrency appears increasingly relevant. I'd like to learn more about concurrent programming, and apply it in practice. Specifically, message passing concurrency shows great promise, interacting well with a functional programming style and providing ready control over when nondeterminism appears (see, e.g., a recent post on Lambda the Ultimate). Python isn't structured for the approach I want to explore.

Basically, there are things that I want to do that Python just gets in the way of, and the future of Python seems quite unlikely to include the changes I need.

In light of the above, the landmark Python 3 release comes across as a good time to re-assess how I use Python. As a whole, I'm left thinking that I'd be better off directing more of my time to Scala, OCaml, or Haskell. The changes in Python 3 hardly seem worth even the relatively minor effort needed to upgrade at this point, so I think I'll just stick with the installation I have for now.

Passive-Aggressive Python

Consider sum. It's great for adding up a list of numbers:

Python 2.5.1 (r251:54863, Feb  4 2008, 21:48:13) 
[GCC 4.0.1 (Apple Inc. build 5465)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> x = range(10); print x
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> sum(x)
45

Strings, on the other hand, it doesn't care for:

>>> y = list("abcdefghi"); print y
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
>>> sum(y, "")
Traceback (most recent call last):
  File "", line 1, in 
TypeError: sum() can't sum strings [use ''.join(seq) instead]

This is about performance. Repeatedly adding up strings behaves quite a bit differently than adding up numbers. Each addition causes a new string to be created, turning the whole thing into O(n²), where n is the number of strings being concatenated, instead of the O(n) you would get by using join or when summing up numbers.

Think that seems like a fair tradeoff? Think again:

>>> u = map(lambda a: [a], x); print u
[[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]]
>>> sum(u, [])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 

and again:

>>> v = map(lambda a: (a,), x); print v
[(0,), (1,), (2,), (3,), (4,), (5,), (6,), (7,), (8,), (9,)]
>>> sum(v, ())
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> 

Both of those have the same performance issues with sum that strings have.

So much for polymorphism. The interface is muddled, being neither specialized to numbers, nor polymorphic to objects that support addition. It's all quite silly, really, because there's no reason for sum to behave like this. The worst-case time complexity is intended to be O(n), but easily becomes O(n²) as shown above—and actually is entirely unpredictable because objects can make arbitrary calculations. On the other hand, the TypeError raised for a string is an arbitrary restriction, since it could instead just internally make use of ''.join.

Apparently, sum is the way it is because that's just not how one should concatenate a string. Anything else that supports addition, go ahead, but for strings there is one—and only one—right way to do it. By fiat.