How can I serialize a recursive function?

Question

Suppose I have a function recursive through its closure:

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

Now I want to serialize the function and restore 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 regular closures, but with fact it leads to infinite recursion, as pickle tries to serialize fact within its closure. The usual way to handle recursive data structures in pickle is to memoise the object between construction and initialization, but function objects are immutable, like the t28> tags (tuple) and cells:

 >>> 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 should do something similar when building recursive functions within regular code, since again the function object is not available for placement in its closure before its creation. Is there any magic for creating recursive functions that I miss?

Answer 1

Closing is associated with a free variable, not with it. For self-referencing closure, all Python needs to create a closure for the free fact name (not tied to anything), create a function object with a closure, and then bind fact to this object.

Thus, you need to combine the creation of the closure and the function into the same external function that you create the closure of the name to which the function will be bound:

 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 do this with unpickling, you have to iterate over the closure argument ( args[-1] ) and determine where there is recursion, and replace this one element with create_function_closure.__closure__[0] , I suppose.

Answer 2

Here's how I did 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 you to separate the creation of the closing cell from setting the value of its free variable; the rest of the solution just requires some intervention with pickle memoisation.