The official tutorial does a great job explaining list comprehensions, iterators, generators, and generator expressions at a high level. Since some people don't want to read even that much, I wrote a post on comprehensions for dummies to summarize it.

And if you want to know the lowest level nitty gritty of how they work, there's documentation to point you to the right place, and then the code is relatively readable, at least if you understand C well and know the basics of how CPython works.

But what if you're somewhere between the two extremes? People occasionally ask this on StackOverflow, and the questions invariably get closed because "explain to me how this works" is not a good question for the SO format, but it's a perfectly good question for, say, a blog.

List comprehensions


Under the covers, Python compiles the guts of your list comprehension into a function, and then compiles the comprehension itself into a call to that function. I'll oversimplify it a bit, but the basic idea is this:
    [random.choice(string.ascii_lowercase + " ") for i in range(n)]
… turns into:
    def _comprehension(source):
        result = []
        for i in source:
            result.append(random.choice(string.ascii_lowercase + " "))
        return result
    _comprehension(iter(range(n)))

Of course the function isn't defined in the middle of the expression, it's sort of but not quite as if it were defined in the previous statement (it is definitely defined in the local scope, of course, so it can access your variables as closure cells). And it doesn't have a visible name like _comprehension. Also, because comprehensions are limited in form, it can optimize things a bit. But that's the basic idea.

Set and dict comprehensions

A set comprehension looks exactly like a list comprehension, except it starts with result = set() and does add instead of append.

A dict comprehension is basically the same, but the function it calls on each colon-separated key-value tuple doesn't really exist, so just think of it as result[key] = value.

Generator expressions

A generator expression looks a lot like a list comprehension, except that it's a generator function instead of a regular function. In other words:
    def _comprehension(source):
        for i in source:
            yield random.choice(string.ascii_lowercase + " ")
    _comprehension(iter(range(n)))
In fact, generator expressions (even though they came later than list comprehensions in Python history) are really the core concept; you can almost build everything else on top of them:
    a = [i*2 for i in range(10)]
    b = list(i*2 for i in range(10))
    assert a == b
    a = {i*2 for i in range(10)}
    b = set(i*2 for i in range(10))
    assert a == b
    a = {i: i*2 for i in range(10)}
    b = dict((i, i*2) for i in range(10))
    assert a == b
But the other comprehensions aren't quite pure syntactic sugar.

First, they're up to 40% faster (in the worst case, where you're basically doing nothing).

Second, raising StopIteration just ends a generator expression early, but in a list/set/dict comprehension it ends the whole containing expression; you don't get a list up to the point where you raised StopIteration, you get nothing. (This difference is apparently actually a bug, but not one worth fixing; see my post Can you optimize list(genexp) for further details on what it would take to fix it.) So, in the rare cases where you need to handle StopIteration properly (which I personally have only come across once, and it was write writing code to experiment with an idea for changing the language, not real code…), you have to use list(…), not […].

Finally, if you're writing code that's backward compatible with Python 2.x, generator expressions worked the same way they do in 3.x, but the other comprehensions didn't; they were inlined into the current function, meaning they leaked the iteration variable into the outer scope (overwriting any existing variable with the same name). And if you're still using Python 2.6 or earlier, you don't have set or dict comprehensions, so you have no choice but to use set(…) or dict(…).

Disassembling comprehensions

If you want to dive in further yourself, you might think about disassembling the comprehension. But if you try that, you're just going to be disassembling the code that builds and calls a function, not the actual internal comprehension function's code.

Of course you run into that problem with any local function, and you can get around that easily by having the outer function return the local function (or its disassembly, or whatever), but that doesn't work here, because you don't have a name for the local to return (and it's not in locals() or anywhere else introspectable).

Well, you can always put a comprehension in a module and disassemble everything in the module.

Or you can use this quick&dirty hack:
    >>> frame = [sys._getframe() for _ in range(1)][0]
    >>> dis.dis(frame.f_code)
      1           0 BUILD_LIST               0
                  3 LOAD_FAST                0 (.0)
            >>    6 FOR_ITER                18 (to 27)
                  9 STORE_FAST               1 (_)
                 12 LOAD_GLOBAL              0 (sys)
                 15 LOAD_ATTR                1 (_getframe)
                 18 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
                 21 LIST_APPEND              2
                 24 JUMP_ABSOLUTE            6
            >>   27 RETURN_VALUE
If you know Python bytecode, you can see some of the optimizations I mentioned—there's no GET_ITER before the FOR_ITER, because the source is always passed in as an iterator; it uses special BUILD_LIST and LIST_APPEND bytecodes instead of calling the list constructor and looking up and calling its append method and then having to push the list again; it jumps straight from the loop to the RETURN_VALUE rather than doing the extra POP_BLOCK work and pushing some value, because the list set up in BUILD_LIST is already guaranteed to be on top of the stack.

You can probably guess how set and dict comprehensions work: they do BUILD_SET and BUILD_MAP, and SET_ADD and MAP_ADD instead of the list equivalents. And MAP_ADD requires two things on the stack instead of one.

Generator expressions are similar. No BUILD_LIST, a YIELD_VALUE followed by POP_TOP instead of LIST_APPEND, and they have to LOAD_CONST None at the end because they have nothing to return, but that's the only differences.
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. Languages in the Abject-Oriented space have been borrowing ideas from another paradigm entirely—and then everyone realized that languages like Python, Ruby, and JavaScript had been doing it for years and just hadn't noticed (because these languages do not require you to declare what you're doing, or even to know what you're doing). Meanwhile, new hybrid languages borrow freely from both paradigms.

This other paradigm—which is actually older, but was largely constrained to university basements until recent years—is called Functional Addiction.

A Functional Addict is someone who regularly gets higher-order—sometimes they may even exhibit dependent types—but still manages to retain a job.

Retaining a job is of course the goal of all programming. This is why some of these new hybrid languages, like Rust, check all borrowing, from both paradigms, so extensively that you can make regular progress for months without ever successfully compiling your code, and your managers will appreciate that progress. After all, once it does compile, it will definitely work.

Closures

It's long been known that Closures are dual to Encapsulation.

As Abject-Oriented Programming explained, Encapsulation involves making all of your variables public, and ideally global, to let the rest of the code decide what should and shouldn't be private.

Closures, by contrast, are a way of referring to variables from outer scopes. And there is no scope more outer than global.

Immutability

One of the reasons Functional Addiction has become popular in recent years is that to truly take advantage of multi-core systems, you need immutable data, sometimes also called persistent data.

Instead of mutating a function to fix a bug, you should always make a new copy of that function. For example:

function getCustName(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

When you discover that you actually wanted fields 2 and 3 rather than 1 and 2, it might be tempting to mutate the state of this function. But doing so is dangerous. The right answer is to make a copy, and then try to remember to use the copy instead of the original:

function getCustName(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

function getCustName2(custID)
{
    custRec = readFromDB("customer", custID);
    fullname = custRec[2] + ' ' + custRec[3];
    return fullname;
}

This means anyone still using the original function can continue to reference the old code, but as soon as it's no longer needed, it will be automatically garbage collected. (Automatic garbage collection isn't free, but it can be outsourced cheaply.)

Higher-Order Functions

In traditional Abject-Oriented Programming, you are required to give each function a name. But over time, the name of the function may drift away from what it actually does, making it as misleading as comments. Experience has shown that people will only keep once copy of their information up to date, and the CHANGES.TXT file is the right place for that.

Higher-Order Functions can solve this problem:

function []Functions = [
    lambda(custID) {
        custRec = readFromDB("customer", custID);
        fullname = custRec[1] + ' ' + custRec[2];
        return fullname;
    },
    lambda(custID) {
        custRec = readFromDB("customer", custID);
        fullname = custRec[2] + ' ' + custRec[3];
        return fullname;
    },
]

Now you can refer to this functions by order, so there's no need for names.

Parametric Polymorphism

Traditional languages offer Abject-Oriented Polymorphism and Ad-Hoc Polymorphism (also known as Overloading), but better languages also offer Parametric Polymorphism.

The key to Parametric Polymorphism is that the type of the output can be determined from the type of the inputs via Algebra. For example:

function getCustData(custId, x)
{
    if (x == int(x)) {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return int(fullname);
    } else if (x.real == 0) {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return double(fullname);
    } else {
        custRec = readFromDB("customer", custId);
        fullname = custRec[1] + ' ' + custRec[2];
        return complex(fullname);
    }
}

Notice that we've called the variable x. This is how you know you're using Algebraic Data Types. The names y, z, and sometimes w are also Algebraic.

Type Inference

Languages that enable Functional Addiction often feature Type Inference. This means that the compiler can infer your typing without you having to be explicit:


function getCustName(custID)
{
    // WARNING: Make sure the DB is locked here or
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

We didn't specify what will happen if the DB is not locked. And that's fine, because the compiler will figure it out and insert code that corrupts the data, without us needing to tell it to!

By contrast, most Abject-Oriented languages are either nominally typed—meaning that you give names to all of your types instead of meanings—or dynamically typed—meaning that your variables are all unique individuals that can accomplish anything if they try.

Memoization

Memoization means caching the results of a function call:

function getCustName(custID)
{
    if (custID == 3) { return "John Smith"; }
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

Non-Strictness

Non-Strictness is often confused with Laziness, but in fact Laziness is just one kind of Non-Strictness. Here's an example that compares two different forms of Non-Strictness:

/****************************************
*
* TO DO:
*
* get tax rate for the customer state
* eventually from some table
*
****************************************/
// function lazyTaxRate(custId) {}

function callByNameTextRate(custId)
{
    /****************************************
    *
    * TO DO:
    *
    * get tax rate for the customer state
    * eventually from some table
    *
    ****************************************/
}

Both are Non-Strict, but the second one forces the compiler to actually compile the function just so we can Call it By Name. This causes code bloat. The Lazy version will be smaller and faster. Plus, Lazy programming allows us to create infinite recursion without making the program hang:

/****************************************
*
* TO DO:
*
* get tax rate for the customer state
* eventually from some table
*
****************************************/
// function lazyTaxRateRecursive(custId) { lazyTaxRateRecursive(custId); }

Laziness is often combined with Memoization:

function getCustName(custID)
{
    // if (custID == 3) { return "John Smith"; }
    custRec = readFromDB("customer", custID);
    fullname = custRec[1] + ' ' + custRec[2];
    return fullname;
}

Outside the world of Functional Addicts, this same technique is often called Test-Driven Development. If enough tests can be embedded in the code to achieve 100% coverage, or at least a decent amount, your code is guaranteed to be safe. But because the tests are not compiled and executed in the normal run, or indeed ever, they don't affect performance or correctness.

Conclusion

Many people claim that the days of Abject-Oriented Programming are over. But this is pure hype. Functional Addiction and Abject Orientation are not actually at odds with each other, but instead complement each other.
5

View comments

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