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. :)

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.

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()

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.)

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

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.