How can I serialise a recursive function?

Question

Suppose I have a function that is recursive through its closure:

def outer():
    def fact(n):
        return 1 if n == 0 else n * fact(n - 1)
    return fact

I now want to serialize the function and reconstruct it using types.FunctionType:

import pickle, marshal, copyreg, types

def make_cell(value):
    return (lambda: value).__closure__[0]

def make_function(*args):
    return types.FunctionType(*args)

copyreg.pickle(types.CodeType,
    lambda code: (marshal.loads, (marshal.dumps(code),)))
copyreg.pickle(type((lambda i=0: lambda: i)().__closure__[0]),
    lambda cell: (make_cell, (cell.cell_contents,)))
copyreg.pickle(types.FunctionType,
    lambda fn: (make_function, (fn.__code__, {}, fn.__name__, fn.__defaults__, fn.__closure__)))

buf = pickle.dumps(outer())
fn = pickle.loads(buf)

This works fine for ordinary closures, but with fact it results in infinite recursion as pickle attempts to serialise fact within its closure. The usual way to handle recursive data structures in pickle is to memoise the object between construction and initialisation, but function objects are immutable, as are fn.__closure__ (a tuple), and cell objects:

>>> cell = (lambda i=0: lambda: i)().__closure__[0]
>>> cell.cell_contents = 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: attribute 'cell_contents' of 'cell' objects is not writable

Presumably the language has to do something similar when constructing recursive functions within normal code, as again the function object isn't available to place in its closure until it's been constructed. Is there some magic to building recursive functions that I'm missing?

Answer 1

A closure binds to a free variable, not it's value. For a self-referencing closure, all Python needs to do is create a closure for the free fact name first (not yet bound to anything), create the function object with the closure, and then bind fact to that object.

As such, you need to combine creating a closure and a function into the same outer function, such that you create a closure to the name the function is going to be bound to:

def create_closure_and_function(*args):
    func = None
    def create_function_closure():
         return func

    closure = create_function_closure.__closure__
    func = types.FunctionType(*args[:-1] + [closure])
    return func

To make this work with unpickling you'd have to loop over the closure argument (args[-1]) and detect where there is a recursion, and replace that one item with create_function_closure.__closure__[0], I suppose.

Answer 2

This is how I ended up doing it, in Python 3 using nonlocal:

def settable_cell():
    if False:
        x = None
    def set_cell(y):
        nonlocal x
        x = y
    return (lambda: x).__closure__[0], set_cell

And in Python 2 using a generator:

def settable_cell():
    def g():
        while True:
            x = (yield (lambda: x).__closure__[0])
    set_cell = iter(g()).send
    return set_cell(None), set_cell

This allows separating creating a closure cell from setting the value of its free variable; the rest of the solution just requires some fiddling with the pickle memoisation facility.