1. Earlier today, I saw two different StackOverflow questions that basically looked like this:
    Why does this not work? 
        try:
            [broken code]
        except:
            print('[-] exception occurred')
    
    Unless someone can read minds or gets lucky or puts a whole lot more work into your question than you have any right to expect, the only answer anyone can give is "because an exception occurred", because your code goes out of its way to make it impossible for you to tell us what exception occurred and why.

    This is exactly why you almost never want to handle exceptions with a bare except clause.

    So, how do you want to handle exceptions?

    If there's a specific exception you want to deal with, handle that

    On both posts, someone suggested replacing the except: with except Exception:. But this doesn't really help anything.

    OK, yes, it means that you'll no longer catch things like KeyboardInterrupt, which is nice, but it's still not going to help you tell what actually went wrong.

    For example, one of the users' broken code was trying to create a socket, but he had a simple typo. Presumably he wanted to handle socket errors in some way, but because he used a bare except, the NameError raised by the typo looked exactly like a socket error. Handling Exception instead of everything wouldn't help that at all; socket.error and NameError are both subclasses of Exception. What you want to do here is handle socket.error.

        try:
            sock = socket(AF_INET, SOCK_STEAM)
        except socket.error:
            print('[-] exception occurred')

    This way,  you'll get a traceback telling you there's a NameError on SOCK_STEAM, which is pretty easy to debug.

    Sometimes, Exception is the right thing to handle (especially if you want to catch all unexpected exceptions at the very top of your program to log or display them in some way), but usually not.

    Almost always use an as clause

    Even just handling any Exception would still have allowed the user to debug his problem, if he hadn't thrown away all the information:
        try:
            sock = socket(AF_INET, SOCK_STEAM)
        except Exception as e:
            print('[-] exception occurred: {!r}'.format(e))
    This doesn't give you a full traceback, or exit the program, but at least it lets you see NameError("name 'SOCK_STEAM' is not defined"), which is enough to debug the problem.

    (If you really need to handle absolutely everything, even things like KeyboardInterrupt that aren't subclasses of Exception, how do you do that? You can't use an as clause with a bare except. But in recent Python—which includes 2.6 and 2.7, not just 3.x—"except BaseException:" does the same thing as "except:", so you write "except BaseException as e:". In earlier versions, you have to call sys.exc_info() to recover the exception.)

    The one exception to this is in cases where there's only one thing that could go wrong, and the details of how it went wrong are irrelevant. That isn't actually true in this case—you'd like the log to tell you whether the socket failed because you're out of resources, or don't have permissions, or whatever, not just that it failed. But here are some examples where it's perfectly fine:

        try:
            import xml.etree.cElementTree as ET
        except ImportError:
            import xml.etree.ElemnetTree as ET
    
        try:
            return main[key]
        except KeyError:
            return backup[key]
    
    (The second one could be handled better by a ChainMap, but let's ignore that; if you do want to do it with try/except, there's no reason to care about the information in the KeyError.)

    If you can't handle the exception in some useful way, don't handle it

    In the socket example, there's no point handling the error and just continuing on. The very next line of code is almost certainly going to be calling sock.bind or sock.connect, which will just raise a NameError anyway. If the socket creation fails, the whole function has presumably failed, so let the exception propagate back to the caller.

    In general, it's your high-level functions that can do something useful with errors, not your mid-level functions (except maybe to reraise them with more context).

    A start_server function had better either start the server, or report that it failed to do so in some way; it shouldn't return successfully with the server not running. And the obvious way to report that failure is to raise an exception. So, just let that socket call raise right through start_server.

    At a higher level, you're going to have a daemon script or a GUI app or something else. That something else may want to wait 10 seconds and try again, or sys.exit(17), or popup up an error message and re-enable the "Start" button, or whatever. That higher-level function is where you want to handle the exception.

    That may mean don't handle it at all

    In fact, in many cases—especially early in development—the right place to handle an exception is nowhere at all. Just let the program exit and print a complete traceback that tells you (or, if not you, the people trying to help you on StackOverflow) exactly what you did wrong and where.

    You might object that this is a bad end-user experience, but surely printing "[-] exception occurred" and then exiting (or printing out an endless stream of such messages and doing nothing useful) is just as bad of an end-user experience.

    Once you have something working, it's often worth wrapping a top-level except Exception as e: at the top level to handle anything that escaped your design, because you want your server to log useful information somewhere and return an appropriate exit code, or you want to display the error in a window with instructions to submit a bug report instead of dumping it to the (possibly-non-existent) console. But until you've got things working at least far enough to do that, it's way too early to be catching everything anywhere.

    Sidebar on other languages

    Pretty much everything above applies to other languages that use exceptions, not just Python. But there's one more issue that comes up in a few languages, like C++, where you're often using a whole bunch of functions written for C that use status codes instead of exceptions.

    In those cases, never call those C functions directly from your mid-level code. Instead, write code that wraps those calls up to raise exceptions when they fail, then use those functions from your mid-level code. (This is especially important if you're using RAII to manage resources, as you really should be in C++.)

    This gives you a very simple rule of thumb: Your bottom-level code throws exceptions, your mid-level code just lets exceptions pass through, and your top-level code catches exceptions. That's not universally true, but it's true often enough to be a handy guide.
    2

    View comments

  2. There are three commonly useful ways to read files: Read the whole thing into memory, iterate them element by element (usually meaning lines), or iterate them in chunks.

    Python makes the first one dead simple, the third one maybe unnecessarily hard, and the second one dead simple if you mean lines, but hard otherwise.

    How to do each one

    Read the whole thing

    You can't get much simpler than this:
    with open(path) as f:
        contents = f.read()
    dostuff(contents)
    
    Or, if you're dealing with a binary file:
    with open(path, 'rb') as f:
        contents = f.read()
    dostuff(contents)
    
    From here on out, I won't distinguish between binary and text files, because the difference is always the same: open in 'rb' mode instead of the default 'r', and you get bytes instead of str.

    At any rate, either way, you get the entire contents of the file as a single str or bytes in just two lines.

    Iterate lines

    This is almost as simple:
    with open(path) as f:
        for line in f:
            dostuff(line)
    
    Lines don't make as much sense for most binary files—but when they do, it's just as simple; pass the 'rb' mode, and each line is a bytes instead of a str.

    Iterate chunks

    This one is simple for Python experts, but not exactly easy to explain to novices:
    with open(path, 'rb') as f:
        for chunk in iter(lambda: f.read(4096), b''):
            dostuff(chunk)
    
    In order to understand this, you have to know the two-argument form of the iter function, how to wrap an expression in a lambda, and that file objects' read method returns an empty bytes (or str, for non-binary files) at EOF. If you didn't know all that, you'd have to write something like this:
    with open(path, 'rb') as f:
        while True:
            chunk = f.read(4096)
            if not chunk:
                break
            dostuff(chunk)
    
    Fortunately, you can wrap things up in a function, so at least its uses are easy to understand, even if its implementation isn't:
    def chunk_file(f, chunksize=4096):
        return iter(lambda: f.read(chunksize), b'')
    

    Iterate non-line elements

    This one is even trickier. To do the same thing file objects magically do to split on lines, you have to write most of the magic manually: accumulate a buffer between read calls, and split that buffer yourself. Like this:
    def resplit(buffers, separator):
        buf = type(separator)()
        for buffer in buffers:
            buf += buffer
            chunks = buf.split(separator)
            yield from chunks[:-1]
            buf = chunks[-1]
        if buf:
            yield buf
    
    with open(path, 'rb') as f:
        buffers = chunk_file(f)
        for element in resplit(buffers, b'\0'):
            dostuff(element)
    
    At least resplit is reusable. But no novice is going to be able to write that. Instead, they'd copy and paste code like this:
    with open(path, 'rb') as f:
        buf = b''
        while True:
            chunk = f.read(4096)
            if not chunk:
                break
            buf += chunk
            elements = buf.split(b'\0')
            for element in elements[:-1]:
                dostuff(element)
            buf = elements[-1]
        if buf:
            dostuff(buf)
    
    Except, of course, that they'll get all kinds of things wrong, and then have to go back and edit all the copy-pasted copies when they find the bug.

    Also, notice that most file-like objects (including actual files) already have their own buffer. Throwing another buffer in front of them obviously hurts performance. Less obviously, it also means the file position is ahead of what you've iterated so far (because you've got extra stuff sitting around in your local buf, or the one hidden inside the generator state), so if you wanted to, say, use f.tell() for a progress bar, it wouldn't be accurate.

    But what alternative do you have? Obviously you can read one byte at a time; then, you can be sure that each time you've read a line, the file pointer is right at the end of that line. But that's likely to be slow (and especially so with unbuffered raw files).

    Binary file objects have a peek method that can help here—instead of read(4096), you just do peek(). If you get anything back, you search for the last separator in the peeked buffer, and, if found, you read that much and split; if not found, you read the length of the peeked buffer and stash it. That's how readline works under the covers on binary files, at least as of CPython 3.4. But that doesn't work for text files, or file-like objects that aren't actual binary files, etc.

    Could this be improved?

    Novices have to write code like this all the time, and they aren't going to know how to do it. Is there a way Python could make it easier?

    New file methods

    One possibility is to add new methods to file objects. The most important one is a readuntil method (or, alternatively, a new sep parameter for readline, or maybe even a sep parameter for the __init__ method or open function), because you'll need that to get around all of the insurmountable problems with iterating non-line-based elements. But methods like iterchunks and iterlines would also be helpful (and, with some implementations, could be more efficient than what you'd write yourself).

    For a brand-new language, that would almost certainly be the answer. But for Python? There are thousands of existing file-like classes, many of which do not use the io module to do their job.

    If it were easier to wrap file-like objects in io objects, that would be a different story. But it's not. If you've got an object with a read method that returns bytes (what "file-like object" usually means for binary files), that's not something you can wrap in a BufferedReader; you'll need to first create a RawIOBase subclass that delegates to your file-like object and implements readinto, so you can wrap that wrapper a BufferedReader. If you've got an object with a readline method (or __iter__) that returns str (what "file-like object" often means for text files), there's no way at all to wrap a text file with as a TextFileWrapper, except by wrapping it in a BufferedReader that fakes an encoding that you can "decode" cheaply just so you can wrap that up.

    Meanwhile, people don't usually want to modify key parts of the standard library until there's significant experience with a third-party module on PyPI. But, at least as of 3.4, there's really no way to write such a module. A readuntil function for binary files is easy (it can call peek if present, go byte by byte if not, just like readline already does), but there's nothing equivalent for text files. (If you're using the _pyio implementation, you can call _get_decoded_chars and _set_decoded_chars to access the internal buffer, but needless to say the builtin C implementation in CPython that you're actually using doesn't expose those internal private methods.) Also, it's not easy to wrap or monkeypatch classes built in C that are returned directly by builtin functions all over the stdlib.

    New generic functions

    Another option would be to include the chunk_file and split_buffers functions (possibly with better names that I can't think of without more coffee…) in the stdlib, possibly even as builtins. This might not be a bad idea.

    Files as an iterable of bytes

    If you could treat files as iterables of individual characters (or bytes), these functions would become a lot easier to write… but then they'd also become a lot less efficient if it means going back to the file object (or, worse, the actual file) for each character. It might be worth writing an iterbytes()/iterchars() method or helper (but remember that you can already do it with chunk_file(f, 1) or, if you prefer better, chain.from_iterable(chunk_file(f, 4096)), which seems too trivial for the stdlib, and that it'll have all the same problems as the two ideas above…), but it's not a solution.

    One way to improve on that would be to provide some way for files to act like a sliceable sequence of characters or bytes—or, even better, as a buffer—rather than just an iterable. The mmap module in the stdlib already provides a (not-quite-novice-friendly, but not too bad) way to do this for binary files, but it's not much help for text files, or file-like objects that aren't OS files, or OS files that aren't regular files (like sockets), or files that are too big for your VM space (a problem for anyone on 32-bit systems), etc.
    2

    View comments

  3. Code for this post can be found at https://github.com/abarnert/lazylist.

    The same discussion that brought up lazy tuple unpacking also raised the idea of implementing a full lazy list class in Python.

    This is easy to do, but isn't as useful as it sounds at first glance.

    Background

    If you don't know about cons lists, triggers, lazy evaluation, etc., first go read about lazy cons lists.

    The short version is that a lazy cons list automatically provides all of the advantages of an iterator, while still being a (linked) list. If you iterate over it (or walk it recursively) without keeping a reference to the original list, each node becomes garbage as soon as the next node is created, so there's no space cost or up-front time cost to build the list. But, on the other hand, you can use the list as a list if you want to, keeping a reference to the original value, so you can iterate over it multiple times. So, in a language like Haskell, where all lists are lazy, there's no need for separate list comprehension and generator expression syntax; there's just a comprehension that gives you a lazy list, and you can use it either way.

    Lazy Python lists

    In Python, having the best of an iterator and a cons list in one isn't too useful, because you rarely want a cons list, you want a Python list—that is, a dynamic array that you can, e.g., randomly access in constant time.

    Can we wrap things up the same way to get lazy Python lists? Well, not quite the same way, but it's about as easy.

    Let's take a little shortcut here. When discussing lazy cons lists, the goal was to make it easy to wrap a function up in something that looked like a linked list. But in Python, the obvious use for lazy lists is going to be wrapping up iterators, not functions. (And you can always turn any function into an iterator trivially if you come up with some other use.) So, I'll change the API to just take an iterable in the initializer. But see below for alternate constructors.

    The trick is to keep a list of already-evaluated values, together with the iterator that provides additional values on demand. At first, you'll have an empty list; each time you need to evaluate another value, you just pull it off the iterator and append it to the list:
    class LazyList(collections.abc.MutableSequence):
        def __init__(self, iterable):
            self._nonlazy, self._lazy = [], iter(iterable)
        def __len__(self):
            self._delazify()
            return len(self._nonlazy)
        def _delazify(self, index=None):
            if index is None:
                return self._nonlazy.extend(self._lazy)
            if isinstance(index, slice):
                index = range(index.start, index.stop, index.step)[-1]
            if index < 0:
                raise IndexError('LazyList cannot take negative indexes')
            self._nonlazy.extend(islice(self._lazy, index - len(self._nonlazy) + 1))
        def __getitem__(self, index):
            self._delazify(index)
            return self._nonlazy[index]
        def __delitem__(self, index):
            self._delazify(index)
            del self._nonlazy[index]
        def __setitem__(self, index, value):
            self._delazify(index)
            self._nonlazy[index] = value
        def insert(self, index, value):
            if index:
                self._delazify(index-1)
            self._nonlazy.insert(index, value)
        def __iter__(self):
            yield from self._nonlazy
            for value in self._lazy:
                self._nonlazy.append(value)
                yield value
        def append(self, value):
            self._lazy = chain(self._lazy, (value,))
        def extend(self, values):
            self._lazy = chain(self._lazy, values)
        def clear(self):
            self._nonlazy, self._lazy = [], iter(())
        def __str__(self):
            return '[{}]'.format(', '.join(map(repr, self._nonlazy + ['...'])))
        def __repr__(self):
            return 'LazyList({})'.format(self)
    

    Bikeshedding

    We have a few choices to make in a real implementation.

    How long is a lazy list?

    A lazy list obviously doesn't have to be infinite, but it may be, and given that we're initializing with an iterator, there's no way to know whether we're infinite or not. So, what should __len__ do?

    The implementation above will eagerly evaluate the entire list—which could loop forever if the iterable is infinite. This means that it's pretty easy to write innocent code that isn't expecting an infinite sequence, pass it one, and hang. On the other hand, any other alternative, like raising an exception (in which case you have to choose carefully between TypeError, ValueError, and maybe NotImplementedError), means we're cheating as a MutableSequence, and not fully usable as a drop-in replacement for a list. On top of that, methods like __contains__ or count are going to iterate the whole list anyway, and there's no real way around that, short of making them raise as well. Or, of course, you could decide not to make it a MutableSequence at all, but just an Iterable that happens to support many but not all MutableSequence methods. That may be a useful tradeoff in some use cases, but I think a list that eagerly evaluates on __len__ is the most general design.

    If you were redesigning the entire stdlib (and maybe the language) around lazy lists, you could keep track of which iterables are definitely finite, definitely infinite, or unknown, so you could eagerly evaluate finite lists but raise on infinite lists—although you'd still have to make a choice for unknown lists. (A statically-typed language could even do that at compile time, and refuse to compile code that tried to take the length of an infinite sequence.) But that's obviously too big a change to drop into Python. (You can't even assume that a normal list is finite, since it can contain itself…)

    Notice that many of the methods that Sequence and MutableSequence automatically define for us call __len__: __iter__, __reversed__, append, and reverse all call it directly; __contains__, count, and index call __iter__; extend calls append; __iadd__ calls extend. Also, while clear only depends on __delitem__, it will still eagerly evaluate the list just to destroy it. It's easy to implement __iter__ manually; append and friends can be done by chaining the new values to the iterator. For count, __reversed__, and reverse, there's no good way around evaluating everything; for __contains__ and index, you'll automatically get the best behavior (only evaluate until the element is found) just by implementing __iter__. So, that's what I've done above. But be aware that the library reference doesn't actually define which methods depend on which other methods, so at least in theory, that's an implementation artifact of CPython, and it might be safer to define _all_ of these methods manually.

    Negative indices

    Having implemented __len__, there's no reason we couldn't also implement negative indexing and slicing. In fact, we don't even need to handle it manually (including the whole mess with slice.indices); we know we have to eagerly evaluate the whole list to use any negative index, so just do that, then delegate the index or slice to the list:
        def _delazify(self, index=None):
            if index is None:
                return self._nonlazy.extend(self._lazy)
            if isinstance(index, slice):
                if index.start < 0 or index.stop < 0:
                    return self._delazify()
                index = range(index.start, index.stop, index.step)[-1]
            if index < 0:
                return self._delazify()
            self._nonlazy.extend(islice(self._lazy, index - len(self._nonlazy) + 1)) 

    What is and isn't public?

    There are some use cases where the user is could take advantage of knowing much of the list has been evaluated so far. We could do that by having a nonlazy_length method (or even making len return that, instead of evaluating the whole list) and letting the caller index accordingly, but it seems even simpler for the caller (and obviously for the class) to just turn the private _nonlazy attribute into a public one. Then, if you want to iterate over all so-far-computed values, it's just for i in lst.nonlazy, not for i in lst[:lst.nonlazy_length()]. But "nonlazy" isn't a very good name for the value from an outside consumer point of view; maybe "computed" is better. Anyway, I can't see any good argument for keeping this hidden, and at least in some use cases there's a reason to not do so, so it would probably be a better design.

    We could also expose the _delazify method, but that doesn't seem as necessary. Wanting to explicitly force evaluation (either up to a certain point, or of the whole thing) without actually wanting to see those values doesn't seem like it would be very common—and if you really want to, lst[30] or lst[-1] works just fine.

    Representation

    The str and repr give us another place to make a choice. In most cases, the repr is either a string that can be evaluated to produce the same value, or something that's obviously not evaluatable, like the generic <LastLazy at 0x123456789>. But for list, repr includes [...] if the list recursively includes itself, and of course eval('[1, 2, 3, [...]]') evaluates to [1, 2, 3, [Ellipsis]], which is not the same thing you started with. I think that's enough precedent to use ... for lazy lists as well, as I've done above.

    We could keep track of the fact that we've exhausted our iterator (with a flag, or just replacing self._lazy with None), which would allow us to drop the ... when the list is no longer lazy, but that seems more work than it's worth for the small benefit.

    Optimizing Sequences

    If the input iterable is a Sequence, we could just copy the sequence to _nonlazy, instead of putting it in _lazy. For some use cases, that might have a significant performance benefit, but in others it won't make any difference, and it makes it a little harder to play with lazy lists, so I haven't done it. If you want to, it's trivial:
        def __init__(self, iterable):
            if isinstance(iterable, collections.abc.Sequence):
                self._nonlazy, self._lazy = list(iterable), iter(())
            else:
                self._nonlazy, self._lazy = [], iter(iterable)
    

    Slicing

    We could make slicing return a new LazyList instead of a list. But that's not as easy as it sounds.

    The simplest solution is to just return LazyList(islice(self, slice.start, slice.stop, slice.step)), which works great—except that it won't handle negative slice indices. That may be an acceptable tradeoff, but it may not. Of course we could fully evaluate, then return LazyList(self), to handle negative slice indices. (In fact, together with the sequence optimization above, this would be effectively equivalent to what we do now for negative slices, but lazy for positive slices.)

    Alternatively, we could implement a view class (as dict does for its keys, values, and items, and NumPy does for its arrays, and as I touched on in my posts on map and filter views and lazy tuple unpacking. But that's making a pretty major change to the sequence API, especially once we start dealing with mutating operations. (And it brings up new questions, e.g., should mutating a view mutate the parent, or should it be copy-on-write?)

    Finally, as an alternative to a generic copy-on-write view, we could explicitly slice _nonlazy, share _lazy, keep track of the slicing information, and keep track of everyone who needs to be updated whenever _lazy is iterated (similar to what itertools.tee does). This sounds like a lot of extra work for no benefit, but it's a foundation on which we could add further benefits. For example, if we kept weak references to all owners of the shared _lazy, we could stop updating them when they go away.

    All of these are potentially good ideas for specific use cases, but probably not appropriate for a general-purpose sequence class.

    Benefits of LazyList

    So, now we have a complete MutableSequence, which can be used as a drop-in replacement for list, but which doesn't evaluate values until you need it. So, does that give us all the advantages of Haskell's lazy lists?

    Unfortunately, it doesn't. While we get the time advantages of an iterator (values aren't generated until you need them), we don't get the space advantages (only one value live at a time).

    So, what's the difference? Well, as mentioned above, when you iterate over a cons list (or use it recursively) without keeping a reference to the list, each time you evaluate the next node, the previous one automatically becomes garbage and can be cleaned up. But a lazy Python list can't do that. Even if you drop your reference to the original LazyList object, the iterator still has a reference to it. And you can't magic that away; it needs a reference to at least self._nonlazy, or the list can't be reused after iteration. And of course it needs to keep appending to that self._nonlazy, too. So, by the time you're done iterating, you have the whole list alive in memory.

    The last alternative discussed above—a manual copy-on-write slice view with weak references—would allow you to use the LazyList cheaply, but only in recursive slicing algorithms (whether using a[0] and recursing on a[1:], or something else like recursing on a[::2] and a[1::2]). I think in most such use cases, you'd be better off just using an iterator instead of trying to write your code around sequences that may or may not be lazy.

    In short, if you need an iterable to be a sequence, you generally don't need it to be lazy; if you need it to be lazy, you generally don't need it to be a sequence; if you need it to be both, there's no convenient way to write your code.

    So, lazy lists aren't useless in Python, but they're not as exciting as they first appear.

    Let's look at the specific use case that brought up this suggestion: lazy tuple unpacking. The idea was that a, b, *c, d, e = foo could be implemented something like this:
    lfoo = LazyList(foo)
    a, b, c, d, e = lfoo[0], lfoo[1], lfoo[2:-2], lfoo[-2], lfoo[-1]
    
    But clearly, that's going to evaluate the entire list anyway. If foo is some object that already knows how to slice itself lazily (like range, or np.ndarray), the LazyList is getting in the way here; we would have been better off just using foo[2:-2]. If it's not, the LazyList can't help us, no matter how we implement it, because there's no way it can pop off the last two values without iterating to the end. An iterator, on the other hand, could help us, at least in the case that foo is a Sequence:
    a, b, c, d, e = foo[0], foo[1], islice(foo, 2, len(foo)-2), foo[-2], foo[-1]
    
    That will make c a lazy iterator over the slice, rather than a copy of the whole thing. Of course it still doesn't help if foo is an iterator, but there's nothing that can possibly help there anyway.

    And I think most of the cases where lazy lists at first seem attractive will turn out the same way: at best the same as iterators (possibly with itertools.tee), and often even less useful.

    But of course I'd love to see examples that prove me wrong.

    Construction

    We want to make it easy to write LazyList-generating functions. That's easy; just write a decorator that you can put on any generator function, and now it returns a LazyList instead of an iterator:
    def lazylist(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            return LazyList(func(*args, **kwargs))
        return wrapper
    
    But you can go farther with this. What about a decorator that passes the LazyList itself to the function? Then you can write this:
    @recursive_lazylist
    def primes(lst):
        yield 2
        for candidate in itertools.count(3): #start at next number after 2
            if all(candidate % p for p in lst.computed()):
                yield candidate
    
    That's not quite as easy to write; we can't pass the iterator returned by calling the generator function into the LazyList constructor and also pass the constructed LazyList into the generator function as an argument. But there are a couple different ways around this. We could just construct a LazyList without an iterator, call the function, then assign the iterator after the fact:
    def recursive_lazylist(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            lst = LazyList(())
            lst._lazy = func(lst, *args, **kwargs)
            return lst
        return wrapper
    
    A really clever idea (not mine) is to realize that that first argument is exactly equivalent to the self argument for a method call. So, we can create a new subclass on the fly, like this:
    class RecursiveLazyList(LazyList):
        @abc.abstractmethod
        def _producer(self):
            while False:
                yield
        def __init__(self, *args, **kwds):
            super().__init__(self._producer(*args, **kwds))
    
    def recursive_lazylist(func):
        return type(RecursiveLazyList)(func.__name__,
                                       (RecursiveLazyList,),
                                       {_producer: func})
    
    This has the advantage that a reader can use their existing knowledge and intuitions about classes to realize that at the time the function is getting called, the new subclass's __init__ has been called but the subclass __init__ hasn't. Although the need to understand the basics of metaclasses (and dynamic class construction) may reduce the number of people who have useful intuitions here…

    By the way, notice that I didn't use an explicit metaclass for RecursiveLazyList. As far as I can tell from the documentation, anything inheriting collections.abc.Sequence is guaranteed to already have some subclass of ABCMeta as its metaclass, so explicitly specifying ABCMeta here would just cause problems if some future version of collections.abc used a proper subclass rather than ABCMeta itself (as CPython 3.4 does), and can't be necessary in any possible implementation. But I may be wrong here; it certainly looks less clear to use abstractmethod when there are no visible metaclasses.

    Sidebar: going crazy with LazyList

    It may be that to really see the benefits of LazyList, you'd need to cram more support into the language. I don't think that's worth doing—I think if there are benefits to LazyList, you can find them without doing any more than building the class. But in case I'm wrong, you can go a lot farther without too much hacking.

    There are many functions in the stdlib that return iterators. Just as many of these functions could instead return a view (as discussed in Swift-style map and filter views), they could also return a lazy list. We can easily create wrappers for them:
    def _wrap(module, name):
        globals()[name] = lazylist(getattr(module, name))
    for name in 'map', 'filter', 'zip', 'enumerate':
        _wrap(builtins, name)
    for name in ('count', 'cycle', 'repeat', 'accumulate', 'chain',
                 'compress', 'dropwhile', 'filterfalse', 'groupby',
                 'islice', 'starmap', 'takewhile', 'zip_longest',
                 'product', 'permutations', 'combinations',
                 'combinations_with_replacement'):
        _wrap(itertools, name)
    del _wrap
    
    Or, if you really want to, you can monkeypatch the stdlib itself (just replace that globals()[name] = func with setattr(module, name, func)). This is starting to get more dangerous—there could easily be code in the stdlib or a third-party library that expects map to return an iterator, not a LazyList—but if you want to try it, go for it.

    While we're going crazy, what if you wanted to automatically wrap every generator function so it became a lazylist function? That should be doable with an import hook. See inline (bytecode) assembly for the basics—or, better, you could probably do this with MacroPy. You could try to determine which FunctionDef nodes are generator functions by looking for any Yield or YieldFrom descendants, and, if found, just add a node to the decorator_list. Or, maybe even hackier, write a safe decorator and just decorate every function. For example:
    def lazylist(func):
        if not inspect.isgeneratorfunction(func):
            return func
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            return LazyList(func(*args, **kwargs))
        return wrapper
    
    builtins.lazylist = lazylist
    
    class LazifyGenerators(ast.NodeTransformer):
        def visit_FunctionDef(self, node):
            node.decorator_last.insert(0,
                ast.copy_location(ast.Name(id='lazylist'), node))
            return node
    
    I've left out the code to install a SourceFileLoader import hook and cram the LazifyGenerators transformer in at the right point, but emptyify has some working (but probably not very good) code for Python 3.4+.

    And, while you're hacking up the AST, you could even change list displays and comprehensions (or, if you prefer, generator expressions) to instead build LazyLists):
    class LazifyLists(ast.NodeTransformer):
        def visit_List(self, node):
            node = self.generic_visit(node)
            func = ast.copy_location(
                ast.Name(id='lazylist', ctx=ast.Load()),
                node)
            call = ast.copy_location(
                ast.Call(func=func, ctx=func.ctx,
                         args=[node], keywords=[],
                         starargs=None, kwargs=None),
                func)
            return call
        visit_ListComp = visit_List
    
    All this without needing to hack up the compiler or interpreter. Of course you can do that too. For CPython, first you need to port LazyList itself to C, and make it available as a builtin, and export C-API-style methods like PyLazyList_New. Then, if you want to, e.g., change list comprehensions to always return LazyLists instead, just change the interpreter code for BUILD_LIST to call PyLazyList_New and PyLazyList_SetItem. If you'd rather add new syntax, that's less radical, but more work—starting with picking the syntax (would angle brackets work? if not, what symbols are left?), then editing the grammar, then changing the compiler to be able to generate a new BUILD_LAZYLIST opcode, and then finally modifying the interpreter the same way as above, except adding a BUILD_LAZYLIST handler instead of modifying the BUILD_LIST handler.
    After all that, if you still can't find any benefits for LazyList, then it's probably time to admit that Python doesn't need it. :)
    2

    View comments

  4. This post is meant as background to the following post on lazy Python lists. If you already know all about cons lists, triggers, lazy evaluation, tail sharing, etc., you don't need to read it.

    Linked lists

    What Python calls "list" is actually a dynamic array. In most other languages, especially functional languages, "list" refers to some sort of linked list. Here's a basic linked list in Python:
    class Hlist(collections.abc.Iterable):
        class Node:
            def __init__(self, value, next):
                self.value, self.next = value, next
            def __repr__(self):
                return '{}({}, {})'.format(type(self).__name__,
                                           self.value, self.next)
        def __init__(self, iterable):
            self.head = last = None
            for value in iterable:
                node = Hlist.Node(value, None)
                if last is None:
                    self.head = node
                else:
                    last.next = node
                last = node
        def __iter__(self):
            node = self.head
            while node is not None:
                yield node.value
                node = node.next
        def __repr__(self):
            return '{}({})'.format(type(self).__name__, list(self))
    
    Of course you can implement all of the methods of the MutableSequence ABC on top of this—although many of them will take linear time, instead of the constant time of arrays (like Python's list). For example:
        def __len__(self, value):
            length = sum(1 for _ in self)
    
    There are all kinds of variations on linked lists that I won't get into here—double-linked lists, lists that hold a tail pointer as well as a head, lists with sentinel nodes, etc. If you want to know more, the Wikipedia article linked above should cover everything.

    Removing the list handle

    If you look at the Hlist class, really all it's holding is that head attribute, which is the first node. What if you just passed around the nodes themselves?

    That means, among other things, that if you already have the node at which you want to perform an operation, it takes constant time to do so, because you no longer have to iterate from the start of the list.

    This also means that an empty list is no longer the same type as a non-empty list—it's None, rather than a Node. But that's not a problem in a duck-typed language like Python:
    class Slist(collections.abc.Iterable):
        def __init__(self, head, tail):
            self.head, self.tail = head, tail
        @classmethod
        def fromiter(cls, iterable):
            first, last = None, None
            for value in iterable:
                node = Slist(value, None)
                if last is not None:
                    last.tail = node
                if first is None:
                    first = node
            return first
        def __iter__(self):
            node = self
            while node is not None:
                yield node.head
                node = node.tail
        def __repr__(self):
            return '{}({})'.format(type(self).__name__, list(self))
    
    (This also wouldn't be a problem in a statically-typed language with a sufficiently powerful type system either; you'd use a union type or some other higher-level type equivalent to Node|NoneType, or Maybe Node, etc.)

    However, this design does run into problems with some of the methods of the MutableSequence ABC. Most notably, insert and __delitem__ can't operate on position 0, because you can't change the head of the list when the only reference you have is to the head of the list.

    You can instead write immutable methods that return a new Slist:
        def inserted(self, index, value):
            i = iter(self)
            return Slist(chain(islice(i, 0, index)), [value], i))
    
    … but that obviously has performance implications that may not always be acceptable. A language designed around immutable linked lists (like ML or Haskell) will have ways to optimize away most of the copying costs whenever possible, but that's not going to happen automatically in Python.

    Side note: C++ std::list

    I won't follow up on this in depth, but C++ (along with a few other languages, like Swift) has a clever way of getting the best of both worlds. The std::list type is itself a list handle, with head and tail pointers, which means you can destructively insert or delete at the head. But it also provides a special kind of opaque pointer (called an iterator, but of course C++ iterators aren't the same kind of thing as Python iterators) to positions within the list, which means that after you (linearly) find some position, you can then perform a bunch of (constant-time, destructive) operations at that position. On top of that, the C++ stdlib is mostly made up of generic functions that work on any such pair of head and tail pointers—whether they come from a linked list, an array, an input stream iterator, or some abstract function that generates values on the fly, as long as they know how to dereference (get the value pointed at), increment (point at the next value), and compare for equality. (In this sense, C++ iterators are related to Python iterators, of course—just as map takes any iterable, no matter what its type or where it came from, std::transform takes any pair of iterators, no matter what their type or where they came from.)

    Recursion

    Before we go any further, notice that Slist is defined recursively—it's a value and another Slist. And that means in many cases, a recursive definition will be simpler than an iterative one. For example, if we didn't use the iterator protocol (and itertools.islice) above, inserted would look like this:
        def inserted(self, index, value):
            snode, dnode = self, None
            result = None
            while True:
                if not index:
                    node = Slist(value, None)
                else:
                    if not snode:
                        raise IndexError('Slist index out of range')
                    node = Slist(snode.value, None)
                    snode = snode.tail
                if dnode:
                    dnode.tail = node
                else:
                    result = node
                index -= 1
    
    Ouch. But a recursive definition looks like this:
        def copy(self):
            if self.tail is None:
                return Slist(self.value, None)
            return Slist(self.head, self.next.copy())
        def inserted(self, index, value):
            if not index:
                return Slist(value, self.copy())
            if self.tail is None:
                raise IndexError('Slist index out of range')
            return Slist(self.head, self.tail.insert(index-1, value))
    

    Tail sharing

    What if, instead of copying the list to insert a new element, we just shared the tail after the insertion point? Not only does everything get a lot simpler, this also can potentially save a lot of memory.
        def inserted(self, index, value):
            if not index:
                return Slist(value, self)
            if self.next is None:
                raise IndexError('Slist index out of range')
            return Slist(self.value, self.next.insert(index-1, value))
        def extended(self, slist):
            if self.tail is None:
                return SList(self.head, slist)
            else:
                return SList(self.head, self.tail.extended(slist))
        # etc.
    

    Mutation

    This tail sharing means that if we use any mutating methods on lists, like calling __setitem__ or assigning to head or tail, things can quickly get confusing. In fact, even without explicit tail-sharing methods, we can see this easily:
    >>> l1 = Slist([0, 1, 2, 3])
    >>> l2 = l1.tail
    >>> l1
    Slist([0, 1, 2, 3])
    >>> l2.head = 100
    >>> l1
    Slist([0, 100, 2, 3])
    
    This is effectively the same problem that Python has with binding the same list (or other mutable data type) to two different variables and then mutating one, but it can be harder to see when you're actually only sharing part or the list instead of the whole thing, and when you're using higher-level abstractions like splicing rather than just copying the tail around manually.

    Persistence

    In the ML/Haskell world, this doesn't come up because all data structures are immutable—if you can't mutate the shared tail, you can't tell whether tails are shared, so it's always safe to do so. But in the Scheme/Racket/Clojure world, where everything is mutable, they solve the problem by making a distinction beyond mutable vs. immutable, to persistent vs. ephemeral. I won't get into the details here (follow the link if you're interested), but basically, any code that uses only persistent operations on its persistent values is effectively referentially transparent, even if it's not purely immutable. Of course this means the stdlib needs naming conventions and/or some other way to make it clear to the reader which functions are non-mutating, which are mutating but safe for ephemeral objects, and which are always destructive, much like Python's reversed vs. list.reverse.

    Cons lists

    In traditional Lisp, the only compound data structure is the cons (named for the assembly instruction originally used to implement it, which is short for "construct"), which is just a pair of values (traditionally called car and cdr, for the assembly instructions used to implement them, short for "contents of address register" and "contents of data register"). Obviously, modern Lisps and derivatives have plenty of other data structures—array-based vectors, hash-based dictionaries, etc.—but the cons is still fundamental to programming in the whole family of languages.

    So if Lisp stands for LISt Processing language, where are the lists?

    Simple: Just define an empty list as nil (Lisp's name for None), and a non-empty list as a cons of the first element and the rest of the list, and implement functions like insert in the obvious way, and you have a tail-sharing, handle-less, singly-linked list. Of course you can still have conses that aren't lists—a cons is a list iff its tail is a list—but otherwise, this is the exact same thing we've just defined as Slist.

    Lisp adds a bit of syntactic sugar to make this nicer: nil can be written as (); cons(1, cons(2, cons(3, nil))) as (1 2 3); cons(1, 2) as (1 . 2); cons(1, cons(2, 3)) as (1 2 . 3). But under the covers (and not very deep under the covers), a list is always a cons, or nil.

    Triggers

    Iterators

    One of the great things about Python is the iterator protocol, a way to create iterables that only generate new items on demand, and don't store them anywhere. As usual, I'll defer to David Beazley's Generator Tricks for Systems Programmers for a detailed illustration of why this is so cool, but the basic appeal is simple: You can represent a very large iterable without actually storing (or computing up-front) anything but the current value, and whatever state is needed to calculate the next one. For a trivial example:
    def count(start=0):
        i = start
        while True:
            yield i
            i += 1
    
    def take(n, it):
        return [next(it) for _ in range(n)]
    
    numbers = count()
    odds = filter(lambda x: x%2, numbers)
    first_10_odds = take(10, odds)
    
    Here we've created an infinite iterable (all the nonnegative integers), filtered it to remove the even numbers, and taken the first 10. Obviously, if we tried to do this by creating a list of all of the nonnegative integers, it would take infinite time. We could create a finite list of just the nonnegative integers that we're going to need—in this case, range(20) would do, because 19 is the 10th non-negative integer—but in most non-toy examples, it's not as easy (often not even possible) to work that out. For example, a program to compute the first million primes can't know how many integers to filter, unless you already know the first million primes (in which case you don't need the program); a program to pull out the first 20 HTTP packets from a pcap stream can't possibly know how many total packets it will need to look at to find 20 HTTP packets; etc.

    Of course I've been both using and implementing the iterator protocol above, just because it makes everything so much simpler and more compact that it's hard not to… But many languages don't have any support for such a thing.

    Doing it manually

    In such languages, we can get the same benefit, without the syntactic sugar of the iterator protocol (and, sadly, without the semantic abstraction of generators) by using triggers.

    In fact, if you look under the covers of the iterator protocol, an iterator is just an object with a __next__ method that returns the next value (and updates its state to be ready to return the one after that).

    Triggered lists

    You can do something similar with a linked list: instead of storing a value and another linked list, we can store a value and a function that returns another linked list:
    class count:
        def __init__(self, start=0):
            self.head = start
        @property
        def tail(self):
            return count(self.head+1)
    
    Or, more generally:
    def Tlist:
        def __init__(self, head, trigger):
            self.head, self._trigger = head, trigger
        @property
        def tail(self):
            return Tlist(self._trigger(self.head), self._trigger)
    
    def count(start=0):
        return Tlist(start, lambda value: value+1)
    
    Of course many languages don't have the equivalent of @property either, so you need an explicit function or method call to get the next value—everywhere your code used to say t.next, it has to say t.next()—but that's just minor syntactic sugar.

    In many cases, you need more state than the current value (or no state at all), so it makes more sense to take a trigger as a function of no variables—which can be a closure over the needed state. Also, to allow finite lazy lists, you need some way for the trigger to signal that it's done—by raising StopIteration, by returning a new Tlist or None rather than just a value, etc. I'll do all of the options differently in the next section, for illustration.

    Lazy lists

    A lazy list is just a triggered list that hides the triggers under the covers—providing the same API as an Slist on top of a Tlist. Thanks to @property, we've almost got that. However, you don't want to have to recalculate the list over and over again; once a node is calculated, the trigger should be replaced by the actual node. Not all languages make it possible to build such a thing, and some have it built in, but for those in the middle, like Python, it's pretty simple:
    def Llist:
        def __init__(self, head, trigger):
            self.head, self._trigger, self._tail = head, trigger, None
        @classmethod
        def fromiter(cls, iterable):
            i = iter(iterable)
            return Llist(None, iter(iterable).__next__).tail
        @property
        def tail(self):
            if self._trigger is not None:
                try:
                    self._tail = Llist(self._trigger(), self._trigger)
                except StopIteration:
                    self._tail = None
                self._trigger = None
            return self._tail
    
    Just as with Slist above, we can expand this into a full Python Sequence by adding the appropriate methods:
        def __iter__(self):
            yield self.head
            if self.tail is not None:
                yield from self.tail
        def __getitem__(self, index):
            if isinstance(index, slice):
                return [self[i] for i in range(slice.start, slice.stop, slice.step)]
            elif not index:
                return self.head
            elif index < 0:
                raise IndexError('Llist cannot take negative indexes')
            elif self.tail is None:
                raise IndexError('Llist index out of range')
            else:
                return self.tail[index-1]
        # etc.
    
    Of course I cheated by implementing __iter__ as a generator, but in a language without generators, you generally don't have to implement anything like __iter__ (Swift being the notable exception). It's not hard to turn that into an explicit class or closure if you need to, just annoyingly verbose:
        def __iter__(self):
            class Iterator:
                def __init__(self, node):
                    self.node = node
                def __iter__(self):
                    return self
                def __next__(self):
                    if self.node is None:
                        raise StopIteration
                    result = self.node.head
                    self.node = self.node.tail
                    return result
            return Iterator(self)
    

    You may want to implement methods like __repr__ specially, to not iterate the entire list, because that would defeat the purpose of being lazy. For example:
        def _lazyiter(self):
            yield self.head
            if self._trigger is not None:
                yield ...
            else:
                yield from self._tail
        def __repr__(self):
            return 'Llist({})'.format(list(self._lazyiter()))
    
    This is basically what languages like Haskell have built in: an automatically lazy, single-linked, tail-sharing cons list.

    Laziness

    There are two important things to observe here.

    First, calling __getitem__ (or any other function that takes an index) automatically instantiates all nodes up to the index, while leaving the rest unevaluated. So, it's evaluating nodes exactly as fast as necessary, and no faster.

    Second, if you just iterate over the Llist, without keeping a reference to the Llist itself around, every time you generate the next node, the previous one becomes garbage and can be cleaned up. So, just like an iterator, only a single value is alive at a time, automatically. (But, just like a list, if you _want_ to keep all the values alive, and iterate over them multiple times, you can do that, too, just by keeping the Llist around.) And if you use it in a typical recursive linked-list algorithm instead of a Python iterator loop, it's again going to free up each node as soon as you get the next one. So, a lazy linked list gives you all the advantages of an iterator, while still being a (linked) list.

    Linked lists in Python

    There's nothing stopping you from using lazy cons lists, other linked list types, or related types in Python. But they don't fit into the language and stdlib (and third-party libraries) nearly as well as sequences and iterators. The entire Python ecosystem is designed around the iterator, iterable, and sequence protocol, and in particular around looping over iterables, rather than around recursing over recursive data structures.

    As Guido explains in his post on tail recursion elimination, this is intentional.

    So, is this a limitation in Python? Not really. The iterator protocol and other Pythonic idioms bring most of the benefits of recursive programming to iterative programming. An iterator is the same kind of quasi-mutable data structure as a tail-sharing linked list: using it mutates an ephemeral object you don't care about, but if you write everything else immutably, you still get referential transparency. Stack up a bunch of iterator-transforming expressions, and at the end you get an iterator over some new virtual sequence, without affecting the original sequence, without wasting memory, without computing everything up-front, and with the ability to handle infinite sequences (as long as you truncate the iterator in some way at some point, of course). It's a different way of getting the same benefits, but the fact that Python is a bad language for writing idiomatic Haskell is no more of a problem than the fact that it's a bad language for writing idiomatic Java; it's a great language for writing idiomatic Python.

    So, if you want to use lazy cons lists, go ahead… but don't expect to get much support from the stdlib, third-party libraries, etc.
    1

    View comments

  5. Lazy tuple unpacking

    In a recent discussion on python-ideas, Paul Tagliamonte suggested that tuple unpacking could be lazy, using iterators. But it was immediately pointed out that this would break lots of code:

        a, b, *c, d, e = range(10000000000)

    If c were an iterator, you'd have to exhaust c to get to d and e.

    One way to solve this would be to try to slice the iterable:

        try:
            a, b, c, d, e = i[0], i[1], i[2:-2], i[-2], i[-1]
        except TypeError:
            # current behavior

    Then c ends up as a range object, which is better than either an iterator or a list.

    With most types, of course, you'd get a list, because most types don't have lazy slices, but that's no worse than today. And range is by no means the only type that does; lazy slices are critical to NumPy.

    So, why doesn't Python do this?

    That's actually a good question. I'm sure the answer would be more obvious if it weren't 4am, and I'll be sure and edit this section to make myself look less stupid when I think of it. :)

    Smarter lazy tuple unpacking through sequence views

    In Swift-style map and filter views, I looked at Swift's sequence types (Swift calls them collections, but let's stick to Python terms to avoid confusion), and pointed out that they can do things that Python's can't.

    And if you take things a bit farther, what you get is exactly what Swift has. In Swift, some functions (although not at all consistently, unfortunately) that return iterators in Python return lazy sequences in Swift that are views on the original sequence(s) if possible, falling back to iterators if not.

    For example, map acts as if written like this:

        class MapView(collections.abc.Sequence):
            def __init__(self, func, sequence):
                self.func, self.sequence = func, sequence
            def __getitem__(self, index):
                if isinstance(index, slice):
                    # do slice stuff
                else:
                    return self.func(self.iterable[index])

        def map(func, sequence):
            if isinstance(sequence, collections.abc.Sequence):
                return MapView(func, sequence)
            else:
                return (func(item) for item in sequence)

    And now, you can do this:

        a, b, *c, d, e = map(lambda i: i*2, range(10000000000))

    … and c is a MapView object over a range object.

    And Swift takes this even further by adding bidirectional sequences—sequences that can't be indexed by integers, but can be indexed by a special kind of index that knows how to get the next or previous value.

    BidirectionalSequence

    Imagine these two types added to collections.abc:

        class BidirectionalIndex:
            @abc.abstractmethod
            def __succ__(self): pass
            @abc.abstractmethod
            def __pred__(self): pass

        class BidirectionalSequence(Iterable):
            @abc.abstractmethod
            def __begin__(self): pass
            @abc.abstractmethod
            def __end__(self): pass
            @abc.abstractmethod
            def __getitem__(self, index): pass

        class Sequence(Sized, BidirectionalSequence, Container):
            # existing stuff

    A BidirectionalSequence is expected to return a BidirectionalIndex from __begin__ and __end__, and to accept one, or a slice of them, in __getitem__, and return a TypeError if you try to pass an int. A Sequence has the same methods but with something like an integer, as usual. (This means that int, and maybe the ABCs in numbers as well, has to implement __succ__ and __pred__.)

    Now we could implement a, b, *c, d, e = i like this:

        try:
            a, b, c, d, e = i[0], i[1], i[2:-2], i[-2], i[-1]
        except TypeError:
            try:
                begin, end = i.__begin__(), i.__end__()
            except AttributeError:
                # current behavior
            else:
                a = i[begin]
                begin = begin.succ()
                b = i[begin]
                begin = begin.succ()
                end = end.pred()
                e = i[end]
                end = end.pred()
                d = i[end]
                c = i[begin:end]

    So, why would you want this? Well, just as map can return a lazy Sequence if given a Sequence, filter can return a lazy BidirectionalSequence if given a BidirectionalSequence. (Also, map can return a lazy BidirectionalSequence if given a BidirectionalSequence.) So you can do this:

        a, b, *c, d, e = filter(lambda i: i*2, range(10000000000))

    And this means generator expressions (or some new type of comprehension?) could similarly return the best possible type: a Sequence if given a Sequence and there's no if clauses, otherwise a BidirectionalSequence if given a BidirectionalSequence, otherwise an Iterator.

    While we're at it, we could also provide a ForwardSequence, which is effectively usable in exactly the same cases as an Iterable that's not an Iterator, but provides an API consistent with BidirectionalSequence.

    Reversible iterables

    But that last point brings up a different possible way to get the same thing: reversible iterators.

    At first glance, it seems like all you need is a new Iterable subclass (that Sequence inherits) that adds a __reviter__ method. But then you also need some way to compare iterators, to see if they're pointing at the same thing. (It's worth noting that C++ iterators and Swift indexes can do that… but they're not quite the same thing as Python iterators; Swift generators, which are exactly the same thing as Python iterators, cannot.) And the code to actually use these things would be pretty complicated. For example, the unpacking would work like this:

        try:
            a, b, c, d, e = i[0], i[1], i[2:-2], i[-2], i[-1]
        except TypeError:
            try:
                rit = reviter(i)
            except TypeError:
                # current behavior
            else:
                it = iter(i)
                if it == rit: raise ValueError('Not enough values')
                a = next(it)
                if it == rit: raise ValueError('Not enough values')
                e = next(rit)
                if it == rit: raise ValueError('Not enough values')
                b = next(it)
                if it == rit: raise ValueError('Not enough values')
                d = next(rit)
                c = make_iterator_between(it, rit)

    It should be pretty obvious how that make_iterator_between is implemented.

    Double-ended iterators

    But once you think about how that make_iterator_between works, you could just make it a double-ended iterator, with __next__ and __last__ methods. Since you've always got just a single object, you don't need that iterator equality comparison. And it's a lot easier to use. The unpacking would look like this:

        try:
            a, b, c, d, e = i[0], i[1], i[2:-2], i[-2], i[-1]
        except TypeError:
            it = iter(i)
            a = next(it)
            b = next(it)
            try:
                e = last(it)
            except TypeError:
                # existing behavior
            else:
                d = last(it)
                c = it

    Summary

    So, is any version of this a reasonable suggestion for Python?

    Maybe the first one, but the later ones, not at all.

    Python hopped on the iterator train years ago, and 3.0's conversion of map and friends to iterators completed the transition. Making another transition to different kinds of lazy sequences at this point would be insane, unless the benefit was absolutely gigantic.

    Reversible iterators are a much less radical change, but they're also a big pain to use, and a bit of a pain to implement.

    Double-ended iterators are an even less radical change, and simpler both to use and to implement… but they're not a very coherent concept to explain. An iterator today is pretty simple to understand: It keeps track of a current location within some (possibly virtual) iterable. An iterator that can also go backward, fine. But an iterator that keeps track of a pair of locations and can only move inward? That's an odd thing.

    In a new language, it might be another story. In fact, if you got lazy sequences right, iterators would be something that users rarely have to, or want to, look at. (Which makes the interface simpler, too—map doesn't have to worry about fallback behavior when called on an iterator, just don't let it be called on anything but a sequence.) Which raises the question of why Swift added iterables in the first place. (It's not because they couldn't think of how else generators and comprehensions could work, because Swift has neither… nor does it have extended unpacking, for that matter.)
    3

    View comments

  6. Something that comes up all the time—and not just in Python—is how to write a file atomically. And the solutions given are usually wrong.

    tl;dr

    You just want some code that makes it easy to do atomic writes? Try fatomic. The example below becomes:

        datafile = 'spam.data'
        fatomic.transform(datafile, process_data)

    Or, if you prefer:

        datafile = 'spam.data'
        with fatomic.open(datafile) as fout, open(datafile) as fin:
            fout.writelines(process_data(line) for line in fin)

    The problem

    Let's say you have some code like this:

        datafile = 'spam.data'
        with open(datafile) as f:
            data = list(f)
        newdata = [process_data(line) for line in data]
        with open(datafile, 'w') as f:
            f.writelines(newdata)

    What happens if the program halts in the middle of that writelines call? Half your data are gone. (Plus, one of your lines probably ends in the middle, which may make process_data fail next time—but in that case, really, you've gotten lucky; an exception is probably better than quietly succeeding without letting you know you've lost important information…)

    Another problem

    On top of that, the code above has to read the whole file into memory, process it all, and write it back out. That's necessary for some problems, but in many cases, you can just process each line at a time, which would be a lot more efficient. (Mostly because you don't need to allocate a bunch of memory, but also because you can often pipeline the reads, processing, and writes, and get better VM locality.)

    But you can't open the file for writing and start writing to it while you're still reading it, or you'll screw everything up. (If you do it the naive way, you'll just truncate the file immediately and have no data at all, but even if you try to be clever, think about what happens if you read a 60-character line, process it, write it back out as a 70-character line, then try to read the next 63-character line.)

    The solution

    There's an easy way to solve both problems: Write to a temporary file, then atomically move that temporary file over the original. That way, only two things can happen: either you get the new version of the data, or you still have the old version.

    So:

        datafile = 'spam.data'
        with open(datafile) as fin, tempfile.NamedTemporaryFile(
            dir=os.path.dirname(datafile), delete=False) as fout:
            for line in fin:
                fout.write(process_data(line))
        os.replace(fout.name, datafile)

    As a side note, many posted solutions to this problem use datafile + '.tmp' instead of the tempfile module. Don't do this. It means if someone runs two copies of your script, they'll end up writing over the same file at the same time (at least on POSIX), leaving you garbage. It also means that if your program fails multiple times, you'll only have the latest temporary file around to recover from. (If you actually want that, e.g., to save space, just add code that cleans up old temp files on startup; don't reuse existing ones.) It also means that a failure may be impossible to automatically recover from if, e.g., an old temporary file becomes unwritable. There are a lot of issues you have to think through carefully in creating temporary files, and tempfile has already thought them through for you.

    Also, many non-Windows developers will put the os.replace inside the with statement. Don't do that. On Windows, both files will be exclusively locked, so the replace will fail. Plus, even on POSIX, on a non-journaled or non-local filesystem, you're opening the possibility that the file will be successfully renamed before it's flushed, re-creating the very problem you were trying to solve.

    Many Windows developers don't realize how replace could possibly work. On POSIX, under the covers, a rename call changes nothing but metadata (directory entries and marking blocks free), and it does this all under appropriate locks on the source and destination directories (or a journaled transaction), and in a carefully-chosen order that makes sure nothing can end up inconsistent. (Filesystems with persistent journaling may do the work optimistically and roll back the transaction instead of locking, but the idea is the same.) That's something you can't do at the user level, because you can't access those locks.

    The big problem with the solution

    Unfortunately, that os.replace method only exists on Python 3.3 and later. If you need to work in Python 3.2 or 2.7, what do you do?

    If you're coding on a Mac or Linux box, you'd probably just use os.rename and everything would seem to work fine—and then you'd publish your code and someone on Windows would run it and get an OSError because the destination file already exists. On Windows, the rename function can't overwrite an existing file.

    This is the point where people always exclaim, "Why the hell doesn't Python give me an easy solution?" The answer, as usual, is that they did add a solution a few years ago, but if you insist on using an old version of Python, you don't get any of the new features. But yes, sometimes people still need to use Python 2.7 (there's less of an excuse for 3.2…); what should those people do?

    The solution to the problem with the solution

    If you google for a solution, you'll find many people suggesting a shuffling operation: rename the original file to filename.bak, then rename filename.tmp to filename, then delete filename.bak. The most common version is:

        if os.path.isfile(filename):
            os.rename(filename, filename + '.bak')
        os.rename(fout.name, filename)
        if os.path.isfile(filename + '.bak'):
            os.remove(filename + '.bak')

    The first few problems with the solution to the problem with the solution (and its solution)

    While os.rename is atomic, os.path.isfile followed by os.rename obviously isn't. That second check is completely worthless, and the first one is insufficient.

    On top of that, if filename.bak is already present (left over from a previous attempt), you will overwrite it on POSIX, but fail with an EEXIST on Windows. You'd have to think about which behavior is the one you actually want, but it can't possibly be both.

    Fortunately, you can EAFP instead of LBYL to fix this: os.rename will fail with ENOENT if filename isn't present, EEXIST if you're on Windows and filename.bak is present, and something different for a real error (like insufficient permissions).

    So, the right way to write that code:

        try:
            os.rename(filename, filename + '.bak')
        except OSError as e:
            if e.errno == errno.EEXIST:
                # whatever you want to do here
            elif e.errno == errno.ENOENT:
                pass
            else:
                raise
        os.rename(fout.name, filename)
        try:
            os.remove(filename + '.bak')
        except OSError as e:
            if e.errno == errno.ENOENT:
                pass
            else:
                raise

    Having to switch on the error's errno inside the exception handler is horribly clunky, and you'd think Python would have a better answer to that. And again, it already does; in 3.3+, you get subclasses like FileNotFoundError and FileExistsError that you can handle separately. But if we were using 3.3+, we'd just use os.replace and not have to worry about any of that code.

    The bigger problem with the solution to the problem with the solution (and its solution)

    More seriously, this shuffle isn't actually an atomic overwrite, even in principle; it's perfectly possible to end up with the old file at filename.bak, the new file at filename.tmp, and nothing at all at filename. On POSIX, you've created a problem that didn't exist in the simple version; on Windows, you've slightly narrowed the problem but not solved it.

    At the very least, you want to avoid adding the problem on POSIX by trying os.rename first, and only falling back to the shuffle if it raises EEXIST:

        try:
            os.rename(fout.name, filename)
        except OSError as e:
            if e.errno == EEXIST:
                # the shuffling code above
            else:
                raise

    Meanwhile, if you have to do the shuffle, then your code will have to deal with the fact that, at read time, filename may not exist, and fall back to filename.bak if so:

        def open_with_bak(filename):
            try:
                return open(filename)
            except OSError as e:
                if e.errno == errno.ENOENT:
                    return open(filename + '.bak')
                else:
                    raise
        with open_with_bak(filename) as fin, tempfile.NamedTemporaryFile(
            # etc.

    (Fortunately, you don't have to remember that you opened filename.bak instead of filename for later; the writing code will successfully rename filename.tmp to filename without caring that there was an old filename.bak lying around.)

    Yet another problem with the solution to the problem with the solution (and its solution)

    But wait, there's more. On POSIX, writing a file, closing it, and renaming it is guaranteed to be atomic unless someone else has written the same file in between. But on Windows, there is no guarantee that the write has been flushed to disk before the rename happened, and it's possible that if your program halts (or, more likely, if someone pulls the power cord) at the wrong time, you end up with a partial file in place of the original file, which is exactly what we were trying to avoid. (When ext4 had similar behavior, that was considered a bug that had to be fixed, but for NTFS, it's considered working as intended.)

    You can solve this by relying on the way locking works on Windows and the (not documented) way that Python uses that, but that's a huge mess.

    A better solution is to drop to the Win32 API… but if we're going to do that, there's a much easier answer.

    The real solution to the whole problem (besides just using Python 3.3+)

    On Windows XP and later, there actually is a perfectly good way to rename a file over another one, as explained on MSDN at Creating and Using a Temporary File. It's just not exposed to the POSIX-ish rename function; you have to use the Win32 API MoveFileEx function. This is exactly what Python 3.3's os.replace uses. If you can require PyWin32, it's as simple as this:

        if sys.platform == 'win32':
            import win32api, win32con
            def replace(src, dst):
                win32api.MoveFileEx(src, dst, win32con.MOVEFILE_REPLACE_EXISTING)
        else:
            replace = os.rename

    Or, better, if you're writing code that runs on 2.6+/3.2+, try the 3.3 os.replace first:

        try:
            replace = os.replace
        except AttributeError:
            # the code above

    If you can't require PyWin32, you can still get at the function via ctypes, which is built into the stdlib:

        import ctypes
        _MoveFileEx = ctypes.windll.kernel32.MoveFileExW
        _MoveFileEx.argtypes = [ctypes.c_wchar_p, ctypes.c_wchar_p, ctypes.c_uint32]
        _MoveFileEx.restype = ctypes.c_bool
        def replace(src, dst):
            if not _MoveFileEx(src, dst, 1): # MOVEFILE_REPLACE_EXISTING
                raise OSError(…)

    … but you'll need to write the code to generate a proper OSError by calling GetLastError, and to deal with non-unicode filenames (either by using MoveFileA, or by decoding appropriately). There's already lots of sample code out there showing how to do both, so I'll leave that as an exercise for the reader. And hopefully, most readers won't want it—use Python 3.3+ if you can, use PyWin32 if you need Windows support and you can, only use this mess if you have to run on older Pythons and can't require any non-stdlib modules.

    This relies on the fact that we're guaranteed to be moving on the same filesystem, in which case MoveFileEx is just a metadata update (as on POSIX), and therefore it's guaranteed to be atomic on any filesystem that can handle it, like NTFS.

    One last problem with all of the solutions (with a partial solution)

    What if you're using Windows, and your filesystem is something horrible like FAT32 that can't do anything atomically?

    In that case, there really is no complete solution, and the shuffle may narrow the problem down better than MoveFileEx can, so you may want to do it after all. But in that case, rather than trying to get the shuffle right, you should use the Win32 API function ReplaceFile that does it for you. You can call this via PyWin32, or via ctypes, basically as shown above for MoveFileEx. If you look at the documentation, you can see that, despite wrapping the three steps up into one call, it gives you different three error codes to let you know which step went wrong, which is all you need to handle each case properly.

    What about Transactional NTFS?

    In NTFS 6 and later, you can create filesystem transactions at user level, and do the whole shuffle within a single transaction (with MoveFileTransacted), which effectively lets you do the same thing POSIX does under the covers for rename, but at user level. However, as the documentation explains, this is a deprecated technology that may be removed in the future. 

    So, if you want your code to only work on Vista-8, and only on drives that were created for those OS versions (rather than, say, upgraded from XP), and only on local NTFS drives, and you don't mind writing more complicated code, then sure, you can use TxF. But even then, as Alternatives to using Transactional NTFS implies, this ends up having the exact same effect as ReplaceFile, so you might as well just use that.

    Hey, what was with that "unless" bit back in the "Yet another…" part?

    It's good that you're thinking carefully here.

    What happens if some other process overwrites your temporary file after you've written it, but before the rename? Then of course you'll be renaming the wrong file. But how could that happen?

    Because you're using tempfile (you are using it, right?), two instances of the same script aren't going to end up with the same temporary file. And, because you're using tempfile, the temporary file is guaranteed to be owner-writable only, so no malicious program (that couldn't just move something over your original file) can move something over your temporary file before the rename. And, because you're using tempfile, there is no race condition that could cause you to pick a name that's not in use, then open it and write to it after someone else has already grabbed that name and put his own data there.

    So, there's nothing to worry about here.

    Summary

    • Use Python 3.3+ and its os.replace if possible.
    • Use os.rename if you don't care about Windows but do care about Python 2.7.
    • Use MoveFileEx if you care about both Windows and Python 2.7.
    • Use ReplaceFile if you care about Windows and care more about getting the narrowest range of bad behavior on bad filesystems than about getting no bad behavior on good filesystems.
    • Never write your own shuffling code.
    0

    Add a comment

  7. To my post Why Python doesn't need blocks, julien tayon replied with a comment about a completely different meaning of blocks, which I think leads to some interesting points, even if it's irrelevant to that post.

    Terminology

    Like many words in computing, "block" is overloaded with multiple, contradictory meanings.

    Ruby has a syntactic feature that it calls "blocks," a way to define special-purpose anonymous callables, which it calls "procs". Objective-C (and Apple-extended C) borrowed that feature, and used the word "block" to refer both to the syntax for defining these things, and for the things so defined.

    But meanwhile, there's a completely separate concept in most imperative languages: a sequence of statements set off by braces, indentation, begin/end, etc., that can be used syntactically like a single statement. And "block" is a pretty common word to refer to this idea, but I'll use the term "suite", as used by Python's reference documentation, to avoid confusion.

    Julien's reply

    Scope, what is it good for? 

    well scopes (not blocks) are for limiting the existence of a variable so that it does not clubber the namespace later and make side effects.
    This is only half of what scopes do, and not the most interesting half.

    Scopes are closures—the variables defined in a scope are only available inside that scope. But in a language with lexical scoping and first-class functions, this means you can capture those variables in a lexical closure and pass it around. That isn't possible in C, but in Python (and many other languages), you can write this:

        def make_adder(addend):
            def adder(augend):
                return augend+addend
            return adder

        adder_of_5 = make_adder(5)
        adder_of_10 = make_adder(10)

    (And, at the risk of increasing the confusion again, it's this use of scopes that Ruby's blocks were invented for—unlike Python, Ruby functions are not lexically scoped, so they needed something else that was.)

    I don't want to give a full tutorial on closures, how cool they are, and the effects of alternative scoping rules, etc.; if you don't already know all that, you'll find better versions on Google (or probably even Wikipedia).
    It is also useful for enforcing the locality of variable (which is very usefull for triggering CPU cache optmization but since python variables are boxed it is not very useful in python).
    I'll ignore the micro-optimization stuff here, because it really isn't relevant.

    Suites and scopes

    Python is lacking of blocks, I miss strictures from Perl. 
    Python is not lacking either suites (blocks) or scopes.

    The difference between Python and the C family of languages is that not every suite defines a scope; basically, it's just function and class definitions.

    So, why not have every suite define a scope?

    First, there's not much benefit (except in the case of a few unusual languages like C++, which I'll get to in the next section). Functions can bind scopes, but for statements can't. So, all you get out of a scoped for statement is the ability to (usually accidentally) shadow outer variables. If you look inside the code generated by a C compiler, a function's stack frame has room for all of the variables defined in the deepest scope in the function, just like in Python.

    And there is a cost. Besides making the language harder to understand, compile, and interpret, it makes it harder to debug your code. For example, in this function:

        int foo() {
            int bar = 1;
            // ...
            if (1) {
                int bar = 2;
                // ...
            }
            // ...
            return bar;
        }

    … there are two different variables, both named bar, where the inner one shadows the outer. Of course in real life, this would probably be a 120-line function, where the two definitions were 58 lines apart and couldn't even fit on the screen together. This makes it harder for a reader to understand the code. And it means a debugger needs some way to distinguish "not that bar, the other bar in the same function". And it means the debugger's interface needs some way to let you distinguish them in your commands.

    In C, there are (at least historical) reasons why long, complex functions are worth having, and occasionally maybe it's even worth reusing the same variable name 58 lines later because it's the locally most-readable name. (That being said, in some cases, compilers will warn you about doing so…)

    But in most newer languages—including Python—there's no reason not to break your code up into smaller pieces. If your inner code needs to use the name bar for readability, factor it out into a separate function. You can even keep that function inline if you want (gaining the added advantage over C that you can explicitly control which variables you do and don't want to share with the parent scope):

        def foo():
            bar = 1
            # ...
            def inner():
                bar = 2
                # ...
            inner()
            # ...
            return bar

    So, you can have a new scope whenever you want it, but you don't get one when you don't need it. You don't accidentally shadow variables, but you can do so when you need to. And so on.

    RAII

    C++, like Python, is designed to encourage small functions, but it still makes extensive use of suite scopes. In fact, you'll even often see "bare suites" created just for scoping purposes:

        void foo(shared_ptr<thing_t> thing) {
            immutable_stuff(thing);
            {
                lock_t lock(thing->mutex);
                mutating_stuff(thing);
            }
            more_immutable_stuff(thing);
        }

    This is a feature that C++ calls Resource Acquisition Is Initialization.

    In C++, everything, even class types, gets allocated on the stack, and destroyed when it goes out of scope. If you want something to live longer, you have to use the new operator to allocate it on the heap, use a pointer to it, and delete it when you're done. If you need to allocate it on the heap, but still want it to go away at the end of the scope, you can allocate a smart pointer (the stdlib comes with various different variations) that itself lives on the stack, goes away at the end of the scope, and deletes the object.

    Building on that, each class can have a destructor that gets called right before the object gets destroyed. So, if you acquire a resource in your constructor, and release it in your destructor, you can tie the resource's lifetime to your object's lifetime, which you can tie to the scope.

    The problem with this feature is that it relies on manual memory management. In most other current languages, objects are allocated on the heap, and automatically garbage collected after you no longer refer to them. Since the garbage collector isn't tied to any scope, you can't rely on destructors to tie resource lifetimes to scopes. Instead, you have to do it using something like Java's try/finally statement:

        void foo(Thing thing) {
            immutable_stuff(thing);
            try {
                lock(thing->mutex);
                mutating_stuff(thing);
            } finally {
                unlock(thing->mutex);
            }
            more_immutable_stuff(thing);
        }

    In that code, the extra scope created by the try suite is obviously not helping anything. Without RAII, suite scopes aren't useful.

    Special-purpose suites

    Many C++-family languages have a special kind of statement that wraps this up lock-a-mutex-for-the-duration-of-a-suite use case:

        void foo(Thing thing) {
            immutable_stuff(thing);
            synchronized(thing->mutex) {
                mutating_stuff(thing);
            }
            more_immutable_stuff(thing);
        }

    But that only works for locks; it doesn't work for files or large chunks of memory or anything else, unless the language has a special statement for each kind of resource. RAII effectively exposes a try/finally contexts in a way that's accessible at the language level, so you (or the stdlib, or a third-party library) can write any number of "synchronized"-like wrappers for every kind of object you want.

    Python has a very similar, but different, solution to the same problem, as Julien acknowledges:

    Context managers

    And python with context manager has finally began to understand the wisdom in scopes:  
    with open("/tmp/whatever") as f: do some_thing_of(f) 
    # f does not exists here, and file is closed \o/ 
    I'm not sure what's meant by "finally" here, since context managers have been part of Python since 2.5 (see PEP 343), and were under discussion for 3 years before being implemented.

    Also, it's not true that f does not exist after the with statement. It still exists; you can print it out and see that it's a perfectly valid TextIOWrapper around a closed file.

    And this is the key. With statements are not about scopes; they're a way of managing resource lifetimes independently of the scopes of any variables that may reference them. You get all of the advantages of RAII without needing the otherwise-useless scoped suites.

    (The fact that a with statement has a suite, and so does a function definition or other scoped statement, is really only marginally relevant here; all compound statements have suites, most of them don't have scopes, and most of them have nothing to do with resource lifetime.)

    On the other hand, there is an advantage of RAII over context managers, and most other languages' solutions. RAII effectively lets you turn any scope into a context manager. If you already have a suite whose scope is "close enough" to the desired lifetime of the resource, you can just drop an RAII object into that suite, without needing to create an enclosed suite. Whether that benefit is worth the cost of explicit memory management is a question for debate.
    1

    View comments

  8. Along the way to an attempt to port itertools from Python to Apple's new language Swift (see my Stupid Swift Ideas blog), I discovered something interesting: Swift's map and filter functions are in some ways better than Python's. Would the same ideas be worth having in Python? What about for other functions, like the ones in itertools?

    Terminology

    Swift has the same key types and methods as Python, but uses different names for all of them: Generator for Iterator, Sequence for Iterable, Collection for Sequence, generate() for __iter__(), next() for __next__(), generatorOf() for iter(), etc.

    For the most part, everything you know about Python translates over directly. A Python iterator is an iterable that returns itself on __iter__ and is one-pass (looping over it consumes it); a Python sequence is an iterable that can be indexed, does not return itself, and is multi-pass; the exact same things are true for the Swift equivalents.

    From here on out, I'll use Python terminology for everything.

    map

    In Python, map(function, iterable) returns a map object, which is a kind of iterator.

    Because it's an iterator, it doesn't generate new values until you ask for them, which means you can map over an large sequence without needing to waste memory storing all the mapped values, or wait until all of the values have been mapped before using them. You can even map over infinite iterators:

        squares = map(lambda x: x*x, itertools.count())

    If you don't get why iterators are cool, David Beazley explains it better than I ever could.

    On the other hand, a map object is single-pass, it's not so nice for debugging, and it can't be indexed. These are all things people who migrate from Python 2.x (where map returns a list) complain about.

    Of course you can get the Python 2.x behavior trivially:

        def map2(*args, **kwargs):
            return list(map(*args, **kwargs))

    But Swift actually has something better.

    When you call map on an iterator, you get back an iterator. But when you call it on a sequence, you get back a sequence. And not a list, but a special map view sequence. If m = map(func, seq), m[3] gives you func(seq[3]). There may or may not be a permanent or LRU cache on it, I'm not sure.

    Anyway, this is pretty easy to get as well:

        class MapSequenceView(collections.abc.Sequence):
            def __init__(self, func, seq): self.func, self.seq = func, seq
            def __getitem__(self, idx): return self.func(self.seq[idx])
            def __len__(self): return len(self.seq)

        def swiftmap(func, seq):
            if isinstance(func, collections.ast.Sequence):
                return MapView(func, seq)
            else:
                return map(func, seq)

    This isn't complete code. For example, when __getitem__ is called with a slice, you'll want to call func on each element, not on the whole sliced list. (And if you want it cached, you'll want to use lru_cache or memoize on the individual values only, not on slices, meaning you'll want __getitem__ to delegate to a _getsingle that can be decorated. But I'm assuming we don't want it cached.) But it's not hard to flesh out. (See the documentation on collections.abc.Sequence for exactly what you need to implement to be a proper sequence.)

    If you just use the MapSequenceView as an iterable, it works exactly the same as a map, with no extra cost. But if you then want to iterate it again, you can. Or if you want to iterate it in reverse, or jump to index #17, you can, again with no extra cost.

    Of course the fact that it's not an iterator means it's not a drop-in replacement. You can't dropwhile a MapSequenceView to get a map starting at the first positive element, or islice it or even next it to skip a value—or, rather, you can, but you'll get a new iterator, leaving the original MapSequenceView unchanged. But that's OK; you wouldn't use this as a drop-in replacement, you'd use this when you want the new behavior. And ideally, dropwhile, islice, etc. should all be built the same way, with their own DropWhileSequenceView, etc. types.

    Interestingly, some Swift collections, when sliced, return special FooSlice types that provide a view onto the sliced part of the original collection. But I don't think that's at all necessary, given that an ISliceSequenceView over a MapSequenceView would provide the exact same benefits as a special MapSequenceViewSlice type.

    Also, the repr of a Swift map sequence view isn't the mapped sequence, it's essentially the constructor call that shows how to rebuild the same view. I'm not sure whether that's a good thing or a bad thing. (What might be cool is to show something like [f(0), f(1), f(2), f(3)] for map(f, [0, 1, 2, 3])…)

    filter

    The filter function is even more interesting. When given an iterator, it returns an iterator, but when given a sequence, it returns a sequence. How does that work? How can you know in advance that index #3 in the filtered sequence is index #8 in the original?

    You can't. This is where another interesting feature of Swift comes in.

    In Swift, sequences aren't necessarily indexed by integers; they're indexed by any kind of object you want, and there's a standard hierarchy of index types: ForwardIndex can't do anything but increment, BidirectionalIndex can also decrement; RandomAccessIndex can also do arithmetic; and Integer is what it sounds like. This idea is borrowed from C++, where the standard library has a bunch of collections that have begin and end methods (which Swift uses a different name for, but I'll ignore that for consistency) that return indexes (which C++ calls iterators, but I'll ignore that again) of the appropriate type, and all of its functions work on those indexes while knowing nothing of the collection itself.

    And Swift makes things even more interesting by having the equivalent of range(start, end) for all kinds of indexes rather than just integers, and slice(start, end) as well (in fact, range and slice are the same thing in Swift, because sadly it doesn't support negative indexing). And enumerate returns indexes of the appropriate type too.

    So, what good is all that? Well, a FilterSequenceView can return a BidirectionalIndex from its begin and end methods, rather than 0 and len(self), and therefore enumerate returns BidirectionalIndex values. Which means you can look ahead or back from the current position while looping:

        for i, value in enumerate(f):
            if value == "spam":
                if f[i.pred()] == "eggs":
                    return "complete breakfast"

    It also means the reversed function works on any bidirectional sequence, like a FilterSequenceView, because it's implemented as a ReversedSequenceView that wraps the other sequence and returns indexes that work backward.

    Of course this requires ints to have succ and pred methods, so the same code will work whether f is random-access or just bidirectional, but that's a pretty minor thing to add.

    (I'm cheating a bit here; while Swift has this capability, at least as of beta 2, its standard library doesn't actually use it. The filter function returns a forward-only sequence, which can't be reversed. Also, both bidirectional and forward sequences are basically useless for anything but iteration because the protocol provides no begin and end methods. Each sequence in the stdlib happens to provide startIndex and endIndex properties, but because Swift has statically-typed generics instead of duck typing, that doesn't help if all you know is that you have a sequence…)

    Other methods

    Sadly, Swift has almost no other functions that create or transform iterables—beyond map and filter, there's enumerate and partial implementations of zip and repeat. But the same idea can be carried forward to all of the functions that Python has in itertools and elsewhere. For the functions in itertools and builtin:
    • map, zip, count, cycle, repeat, islice, starmap, zip_longest, and product can create return randomly-accessible sequences, bidirectional sequences, forward sequences, or iterators, depending on the weakest of their arguments.
    • filter, chain, compress, filterfalse, dropwhile, takewhile, and permutation and friends can return bidirectional sequences, forward sequences, or iterators, depending on the weakest argument.
    • accumulate and groupby can return a forward sequence or iterator, depending on the weakest argument. (If the function had an inverse, accumulate could return a bidirectional sequence, but you can't even guarantee that for the default + operator for all types…)
    The recipes are mostly pretty obvious, since they're just wrappers around other functions. However, some of them have their own complex implementations—e.g., grouper, roundrobin, and partition could return a random-access sequence, bidirectional sequence, forward sequence, or iterator depending on the arguments.

    Implementation

    It's worth noting that any itertools-like function that wants to return a sequence has to be implemented as a custom class, not a generator. In some cases, a single class can provide the best-index-possible behavior, but in other cases, you'd need as many as four separate classes (or three classes and one generator).

    If we added a tower of index types that a single sequence class could use without having to care what kind of index is has, then those three classes could, I think, always be reduced to one.

    However, in some cases, knowing that you have a random-access sequence allows for a more efficient implementation. (This is actually why the C++ standard originally came up with its iterator tower.)

    It should be pretty easy to factor out the details for a delegating sequence, so the only ones that will be difficult to write are the ones that rely on complex implicit state. (It's worth noting that Swift apparently does not have any such factored-out helpers, and implements the same thing repeatedly, with a whole lot of boilerplate. But I think that's down to limitations in the language, and to the fact that fleshing out and polishing the stdlib hasn't been the highest priority, and the fact that they only have a handful of functions so refactoring would only provide so much benefit…)

    See seqview on GitHub for a proof of concept.

    An even crazier idea

    It might be nice to have syntactic support for a "sequence comprehension" that returns the best kind of sequence it can for a given input (the same as the input type if there are no if clauses, no better than bidirectional if there are), 

    Conclusion

    I have no idea which parts of this, if any, are good ideas, or at least good enough to be worth implementing, but I can break them down into separate ideas worth considering:
    • map and similar functions returning sequence views if given a sequence
      • all such functions in itertools being updated
      • helper to make it easier to define such sequence-or-iterator functions in Python
        • similar helper for C?
    • bidirectional, and maybe forward, sequences
      • single sequence type with standard index types, instead of new sequence types
      • making reversed work on bidirectional sequences
      • filter and similar functions returning sequence views if given a sequence
        • all such functions in itertools being updated
      • helper function to make it easier to define random-or-bidirectional-or-iterator functions in Python
        • similar helper for C?
    • sequence comprehensions
    However, it's worth remembering that the main use for all of these functions is in iterator-pipeline-style programming, where you're going to be mixing generator expressions and custom generator functions in with your itertools calls. As soon as you have one generator anywhere in the pipeline, the whole thing is an iterator. Plus, except for debugging purposes, such code usually has no reason to restart, index, or reverse an iterator anyway. So, this may all just be idle speculation.
    1

    View comments

  9. In a recent discussion on adding an empty set literal to Python, the conversion went as far off-base as usual, and I offhandedly suggested:
    Alternatively, it might be nice if there were a way to do "inline bytecode assembly" in CPython, similar to the way you do inline assembly in many C compilers, so the answer to random's question is just "asm [('BUILD_SET', 0)]" or something similar.
    You can follow the rest of the thread from there if you want. I don't really think it's worth pursuing (certainly not for this use case), but it's an interesting idea.

    Here's what it would take.

    Bytecode assembler

    First, you need something that can assemble that inline assembly into actual bytecode. This is the easy part, but I couldn't find any existing projects that worked with Python 3.x, so I wrote one, called cpyasm. There are things that could be improved (see the TODO section in the README), but the basics are there.

    If you only want to write entire functions in assembly, cpyasm already gives you everything you need. But that's not what we want, we want to be able to write most of a function in Python, dropping to assembly for a line or two in the middle.

    Compiler support

    The compiler works in three stages: It tokenizes the data, parses the tokens into an AST, and compiles the AST into bytecode.

    The parsing is done according to a GRAMMAR file. Changing CPython's Grammar explains how to edit this file, and then all the other things you have to edit or rebuild after that. The end result is going to be a new kind of AST node, Asm, with appropriate properties.

    Fortunately, we're not adding any new bytecodes to the interpreter; the whole point of inline assembly is to provide a different way to generate the existing bytecodes. But compile.c needs to be edited to transform the AST node into a sequence of bytecodes. This is where the actual "assembler" part of the inline assembler goes.

    The simplest way to add an asm statement would be to make it a simple statement with one argument, which can be parsed by the existing machinery because it's just a string:

        simple_stmt ::=  expression_stmt
                         | ...
                         | asm_stmt

        asm_stmt ::= "asm" stringliteral

    However, that would mean the parser can't detect any errors in the inline assembly, or even recognize names. On the opposite end, you could make it a compound statement whose suite consists of lines of assembly code, which have their own grammar:

        compound_stmt ::=  if_stmt
                           | ...
                           | inline_asm_stmt
        inline_asm_stmt ::= 'asm' ':' asm_suite
        asm_suite ::=  asm_statement NEWLINE | NEWLINE INDENT asm_statement+ DEDENT
        asm_statement ::= asm_jrel_stmt | asm_jabs_stmt | asm_local_stmt | ...
        asm_jrel_stmt ::= ( 'FOR_ITER' | 'JUMP_FORWARD' | ... ) asm_jrel_target
        asm_jrel_target ::= asm_label | '+' integer | '-' integer | integer

    … and so on

    That's a whole lot more work, but it also means the parser does a lot of your work for you (all the cruft I did with regexps in cpyasm).

    In between the two, you could use something like a simple statement that takes a list display instead of a string, which would make the parser parse out the list values, which would allow it to recognize identifiers and notice them as names in use, etc.       

    Import hook

    Adding support to the compiler might be fun to do when I have a bit of free time, but it'll be a lot of work.

    Also, it's unlikely to get accepted upstream. The best way to get a radically new feature accepted upstream is to package it as a module, put it on PyPI, and see how people are using it, and then go back to the core team and show them how useful it is. But you can't package a compiler modification up as a module. So, what can you do?

    Instead of modifying the compiler, you can use an import hook. The core of the normal import process for source files is read the data as bytes, decode the bytes, parse the str into an AST, compile the AST into bytecode. We can write our own version of the function that does those steps and insert our own code to, regexp the source code, or transform the tree. And we can get that installed to handle all source files, or to handle source files with some new extension like .pya, or whatever we want.

    The importlib docs show all the details on how to do this, although there's really no good overview there, or anywhere else. You can see an example in a module called emptyset, which I think does a good job with the source and AST modification code, but probably a terrible job with the actually hooking part.

    But notice that, while we can do whatever we want to the source before parsing it, and do whatever we want to the tree before compiling it, we can't do much to influence how the parsing itself happens. So, our new syntax has to be valid Python syntax, or at least something we can transform into valid Python syntax. And neither "asm:" followed by a suite full of statements like "CALL_FUNCTION 1,2" nor just "asm" followed by a string are valid syntax.

    Fortunately, there's a simple trick that will work here easily: "asm(foo, bar, baz)" is a function call; "CALL_FUNCTION(1,2)" is a function call; etc. So, we either make that our syntax (which kind of sucks; if you wanted your blocks to end with ")" and each like to end in ",", you wouldn't be using Python, you'd be using one of those languages that ends blocks with "}" and lines with ";"…), or we transform our source to convert our chosen syntax into the parseable syntax—which I think is doable with regexps (since there are no recursive asm statements, etc.) even for the complex-statement version, and almost certainly for the simple-statement versions.

    So now, we've got a parse tree that has a Call node where the func is a Name node whose id is 'asm', and whose args list is either a list of Call nodes, or a single Str node.

    The way to handle this is to write an ast.NodeTransformer that has visit_Call and, if appropriate, visit_Str methods. The example in emptyset is pretty self-explanatory, and the docs in the ast module do a great job on this.

    But… what do we transform these nodes into? We could try to work out the appropriate AST node for each bytecode, but this could get pretty tricky. So I think what we'd want to do instead is to assemble the bytecode here, then put some kind of marker into the node that will compile to some known, easily-findable bytecode of the right length—maybe just a sequence of NOPs?—and stash the assembled bytecode. Then, after we've gotten the bytecode back, we'll need to munge it. First, we may need to fixup some references in our code—e.g., the thing we thought was going to be local #1 is actually local #2, we need to change our LOAD_FAST 1 to a LOAD_FAST 2. The easy way to do this is to just re-assemble the source, now that we have all the info we need (the starting offset, the co_varnames, etc.). Then we just replace the sequence of NOPs with the assembled code, update the co_names etc. with any new names we've added, fix up the co_lnotab, and build a new code object out of the result. This isn't completely trivial, but the cpyasm module shows how all of it works.

    MacroPy

    There's one last option to consider here: Haoyi Lin's amazing MacroPy library helps you build macros that intercept and transform ASTs without having to do all the boilerplate stuff yourself. And it has support for all kinds of cool things that are a pain to build, like making it possible to generate .pyc files that are pre-transformed so you can distribute your project without requiring users to have MacroPy (or the inline asm module).

    I don't think MacroPy has hooks for source and bytecode transformations, and, it has only provisional Python 3.x support, but contributing to MacroPy might be better than duplicating all of the work already done. (And of course this would also mean you get support for the earlier versions of import hooks that are needed for each of 2.7, 3.2, and 3.3, instead of just 3.4…)

    Conclusion

    This post is a lot more pie-in-the-sky than most of my others, mainly because I haven't actually put the work into building the thing I'm discussing. If there's enough interest, and I have enough free time, to make it worth going farther, I'll write a new post.
    0

    Add a comment

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