You've probably been told that you can convert any recursive function into an iterative loop just by using an explicit stack.

Tail-recursive functions

Whenever you get an example, it's usually something that's trivial, because the function was tail-recursive, so you don't even need a stack:

    def fact(n, value=1):
        if n<2:
            return 1
        return fact(n-1, value*n)
That maps directly to:
    def fact(n):
        value = 1
        while True:
            if n<2:
                return value
            n, value = n-1, value*n
You can merge the while and if, at which point you realize you have a for in disguise. and then you can realize that, multiplication being commutative and associative and all that, you might as well turn the loop around, so you get:
    def fact(n):
        value = 1
        for i in range(2, n+1):
            value *= i
        return value
(You might also notice that this is just functools.reduce(operator.mul, range(2, n+1), 1), but if you're the kind of person who notices that and finds it more readable, you probably also rewrote the tail-recursive version into a recursive fold/reduce function, and all you had to do was find an iterative reduce function to replace it with.)

Continuation stacks

Your real program isn't tail-recursive. Either you didn't bother making that transformation because your language doesn't do tail call elimination (Python doesn't), or the whole reason you're switching from recursive to iterative in the first place is that you couldn't figure out a clean way to write your code tail-recursively.

So, now you need a stack. But what goes on the stack?

The most general answer to that is that you want continuations on the stack: what the result of the function does with the result of each recursive call. That may sound scary, and in general it is… but in most practical cases, it's not.

Let's say you have this:
    def fact(n):
        if n < 2:
            return 1
        return n * fact(n-1)
What's the continuation? It's "return n * _", where that _ is the return value of the recursive call. You can write a function with one argument that does that. (What about the base case? Well, a function of 1 argument can always ignore its argument). So, instead of storing continuations, you can just store functions:
    def fact(n):
        stack = []
        while True:
            if n < 2:
                stack.append(lambda _: 1)
                break
            stack.append(lambda _, n=n: _ * n)
        value = None
        for frame in reversed(stack):
            value = frame(value)
        return value
(Notice the n=n in the second lambda. See the Python FAQ for an explanation, but basically it's to make sure we're building a function that uses the current value of n, instead of one that closes over the variable n.)

This is undeniably kind of ugly, but we can start simplifying it. If only the base case and the recursive call had the same form, we could factor out the whole function, right? Well, if we start with 1 instead of None, the base case can return _ * 1. And then, yes, we can factor out the whole function, and just store each n value on the stack:
    def fact(n):
        stack = []
        while True:
            if n < 2:
                stack.append(1)
                break
            stack.append(n)
        value = 1
        for frame in reversed(stack):
            value = value * frame
        return value
But once we're doing this, why even store the 1? And, once you take that out, the while loop is obviously a for loop over a range in disguise:
    def fact(n):
        stack = []
        for i in range(n, 1, -1):
            stack.append(i)
        value = 1
        for frame in reversed(stack):
            value *= frame
        return value
Now stack is obviously just list(range(n, 1, -1)), so we can skip the loop entirely:
    def fact(n):
        stack = list(range(n, 1, -1))
        value = 1
        for frame in reversed(stack):
            value *= frame
        return value
Now, we don't really care that it's a list, as long as it's something we can pass to reversed. In fact, why even call reversed on a backward range when we can just write a forward range directly?
    def fact(n):
        value = 1
        for frame in range(2, n+1):
            value *= frame
        return value
Not surprisingly, we ended up with the same function we got from the tail recursive starting point.

Interpreter stacks

Is there a way to do this in general without stacking up continuations? Of course there is. After all, an interpreter doesn't have to call itself recursively just to execute your recursive call (even if CPython does, Stackless doesn't…), and your CPU certainly isn't calling itself recursively to execute compiled recursive code.

Here's what a function call does: The caller pushes the "program counter" and the arguments onto the stack, then it jumps to the callee. The callee pops, computes the result, pushes the result, jumps to the popped counter. The only issue is that the callee can have locals that shadow the caller's; you can handle that by just pushing all of your locals (not the post-transformation locals, which include the stack itself, just the set used by the recursive function) as well.

This sounds like it might be hard to write without a goto, but you can always simulate goto with a loop around a state machine. So:

    State = enum.Enum('State', 'start cont done')

    def fact(n):
        state = State.start
        stack = [(State.done, n)]
        while True:
            if state == State.start:
                pc, n = stack.pop()
                if n < 2:
                    # return 1
                    stack.append(1)
                    state = pc
                    continue
                # stash locals
                stack.append((pc, n))
                # call recursively
                stack.append((State.cont, n-1))
                state = State.start
                continue
            elif state == State.cont:
                # get return value
                retval = stack.pop()
                # restore locals
                pc, n = stack.pop()
                # return n * fact(n-1)
                stack.append(n * retval)
                state = pc
                continue
            elif state == State.done:
                retval = stack.pop()
                return retval
Beautiful, right? Well, we can find ways to simplify this. Let's start by using one of the tricks native-code compilers use: in addition to the stack, you've also got registers. As long as you've got enough registers, you can pass arguments in registers instead of on the stack, and you can return values in registers too. And we can just use local variables for the registers. So:
    def fact(n):
        state = State.start
        pc = State.done
        stack = []
        while True:
            if state == State.start:
                if n < 2:
                    # return 1
                    retval = 1
                    state = pc
                    continue
                stack.append((pc, n))
                pc, n, state = State.cont, n-1, State.start
            elif state == State.cont:
                state, n = stack.pop()
                retval = n * retval
            elif state == State.done:
                return retval
1

View comments

It's been more than a decade since Typical Programmer Greg Jorgensen taught the word about Abject-Oriented Programming.

Much of what he said still applies, but other things have changed.

5

I haven't posted anything new in a couple years (partly because I attempted to move to a different blogging platform where I could write everything in markdown instead of HTML but got frustrated—which I may attempt again), but I've had a few private comments and emails on some of the old posts, so I

6

Looking before you leap

Python is a duck-typed language, and one where you usually trust EAFP ("Easier to Ask Forgiveness than Permission") over LBYL ("Look Before You Leap").

1

Background

Currently, CPython’s internal bytecode format stores instructions with no args as 1 byte, instructions with small args as 3 bytes, and instructions with large args as 6 bytes (actually, a 3-byte EXTENDED_ARG followed by a 3-byte real instruction).

6

If you want to skip all the tl;dr and cut to the chase, jump to Concrete Proposal.

8

Many people, when they first discover the heapq module, have two questions:

Why does it define a bunch of functions instead of a container type? Why don't those functions take a key or reverse parameter, like all the other sorting-related stuff in Python? Why not a type?

At the abstract level, it'

1

Currently, in CPython, if you want to process bytecode, either in C or in Python, it’s pretty complicated.

The built-in peephole optimizer has to do extra work fixing up jump targets and the line-number table, and just punts on many cases because they’re too hard to deal with.

3

One common "advanced question" on places like StackOverflow and python-list is "how do I dynamically create a function/method/class/whatever"? The standard answer is: first, some caveats about why you probably don't want to do that, and then an explanation of the various ways to do it when you reall

1

A few years ago, Cesare di Mauro created a project called WPython, a fork of CPython 2.6.4 that “brings many optimizations and refactorings”. The starting point of the project was replacing the bytecode with “wordcode”. However, there were a number of other changes on top of it.

1

Many languages have a for-each loop.

4

When the first betas for Swift came out, I was impressed by their collection design. In particular, the way it allows them to write map-style functions that are lazy (like Python 3), but still as full-featured as possible.

2

In a previous post, I explained in detail how lookup works in Python.

2

The documentation does a great job explaining how things normally get looked up, and how you can hook them.

But to understand how the hooking works, you need to go under the covers to see how that normal lookup actually happens.

When I say "Python" below, I'm mostly talking about CPython 3.5.

7

In Python (I'm mostly talking about CPython here, but other implementations do similar things), when you write the following:

def spam(x): return x+1 spam(3) What happens?

Really, it's not that complicated, but there's no documentation anywhere that puts it all together.

2

I've seen a number of people ask why, if you can have arbitrary-sized integers that do everything exactly, you can't do the same thing with floats, avoiding all the rounding problems that they keep running into.

2

In a recent thread on python-ideas, Stephan Sahm suggested, in effect, changing the method resolution order (MRO) from C3-linearization to a simple depth-first search a la old-school Python or C++.

1

Note: This post doesn't talk about Python that much, except as a point of comparison for JavaScript.

Most object-oriented languages out there, including Python, are class-based. But JavaScript is instead prototype-based.

1

About a year and a half ago, I wrote a blog post on the idea of adding pattern matching to Python.

I finally got around to playing with Scala semi-seriously, and I realized that they pretty much solved the same problem, in a pretty similar way to my straw man proposal, and it works great.

About a year ago, Jules Jacobs wrote a series (part 1 and part 2, with part 3 still forthcoming) on the best collections library design.

1

In three separate discussions on the Python mailing lists this month, people have objected to some design because it leaks something into the enclosing scope. But "leaks into the enclosing scope" isn't a real problem.

2

There's a lot of confusion about what the various kinds of things you can iterate over in Python. I'll attempt to collect definitions for all of the relevant terms, and provide examples, here, so I don't have to go over the same discussions in the same circles every time.

8

Python has a whole hierarchy of collection-related abstract types, described in the collections.abc module in the standard library. But there are two key, prototypical kinds. Iterators are one-shot, used for a single forward traversal, and usually lazy, generating each value on the fly as requested.

2

There are a lot of novice questions on optimizing NumPy code on StackOverflow, that make a lot of the same mistakes. I'll try to cover them all here.

What does NumPy speed up?

Let's look at some Python code that does some computation element-wise on two lists of lists.

2

When asyncio was first proposed, many people (not so much on python-ideas, where Guido first suggested it, but on external blogs) had the same reaction: Doing the core reactor loop in Python is going to be way too slow. Something based on libev, like gevent, is inherently going to be much faster.

Let's say you have a good idea for a change to Python.

1

There are hundreds of questions on StackOverflow that all ask variations of the same thing. Paraphrasing:

lst is a list of strings and numbers. I want to convert the numbers to int but leave the strings alone.

2

In Haskell, you can section infix operators. This is a simple form of partial evaluation. Using Python syntax, the following are equivalent:

(2*) lambda x: 2*x (*2) lambda x: x*2 (*) lambda x, y: x*y So, can we do the same in Python?

Grammar

The first form, (2*), is unambiguous.

1

Many people—especially people coming from Java—think that using try/except is "inelegant", or "inefficient". Or, slightly less meaninglessly, they think that "exceptions should only be for errors, not for normal flow control".

These people are not going to be happy with Python.

2

If you look at Python tutorials and sample code, proposals for new language features, blogs like this one, talks at PyCon, etc., you'll see spam, eggs, gouda, etc. all over the place.

Most control structures in most most programming languages, including Python, are subordinating conjunctions, like "if", "while", and "except", although "with" is a preposition, and "for" is a preposition used strangely (although not as strangely as in C…).

There are two ways that some Python programmers overuse lambda. Doing this almost always mkes your code less readable, and for no corresponding benefit.

1

Some languages have a very strong idiomatic style—in Python, Haskell, or Swift, the same code by two different programmers is likely to look a lot more similar than in Perl, Lisp, or C++.

There's an advantage to this—and, in particular, an advantage to you sticking to those idioms.

1

Python doesn't have a way to clone generators.

At least for a lot of simple cases, however, it's pretty obvious what cloning them should do, and being able to do so would be handy. But for a lot of other cases, it's not at all obvious.

5

Every time someone has a good idea, they believe it should be in the stdlib. After all, it's useful to many people, and what's the harm? But of course there is a harm.

3

This confuses every Python developer the first time they see it—even if they're pretty experienced by the time they see it:

>>> t = ([], []) >>> t[0] += [1] --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <stdin> in <module>()

11
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.