#### How can two subroutines call one another without knowing each other's names?

The procedure for creating a function which is recursive (self-calling) despite also being anonymous (i.e. having no name by which to call itself) is well-understood and straightforward. In a nutshell, the solution is to use a fixed point combinator.

Unfortunately, this procedure is only effective for constructing anonymous functions which directly call themselves, such as:

```fibonacci = lambda n: \
0 if n == 0 else \
1 if n == 1 else \
fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(17)) # "1597"
```

Now imagine you want to construct a pair of anonymous functions, such that each one potentially calls itself and/or the other, such as:

```even = lambda n: \
True if n == 0 else odd(n - 1)
odd = lambda n: \
False if n == 0 else even(n - 1)

print(even(6)) # "True"
```

In this situation, a mere Y combinator isn't sufficient. We need a variadic fixed point combinator which can resolve the fixed points of multiple mutually referential functions simultaneously.

### Summary of previous results

Our original procedure is to start with an anonymous function which looks like this:

```fib_incomplete = lambda func: \
lambda n: \
0 if n == 0 else \
1 if n == 1 else \
func(n - 1) + func(n - 2)
```

Our desired function `fibonacci` is the fixed point `func` such that `fib_incomplete(func) = func`.

Then, use the Y fixed point combinator:

```def Y(func):
'''Take a function as input, return its fixed point as output'''
def Y2(x):
def Y3(*args, **kwargs):
return x(x)(*args, **kwargs)
return func(Y3)
return Y2(Y2)
```

to find our original function's fixed point:

```fibonacci = Y(fib_incomplete)
print(fibonacci(17)) # "1597"
```

This result works not just for functions of a single integer (as with `fibonacci` here), but for functions of arbitrary combinations of positional and named arguments. However, it cannot resolve multiple mutually-referential functions at once.

```even_incomplete = lambda func1, func2: \
lambda n: \
True if n == 0 else func2(n - 1)
odd_incomplete = lambda func1, func2: \
lambda n: \
False if n == 0 else func1(n - 1)
```

Notice how our desired functions, `even` and `odd`, are respectively the points `func1` and `func2` such that

```even_incomplete(func1, func2) = func1
odd_incomplete(func1, func2) = func2
```

Consider `even_incomplete` and `odd_incomplete` as components in a higher-order vector-valued function,

```incomplete = (even_incomplete, odd_incomplete)
```

Then we seek `(func1, func2)` such that

```incomplete(func1, func2) = (func1, func2)
```

In other words, we seek the fixed point of `incomplete`.

To do this when there are just two components, you can use the dyadic fixed point combinator:

```def Y(func1, func2):
'''Return the fixed point of the vector function (func1, func2).'''
def Y2_a(x_a, x_b):
def Y3_a(*args, **kwargs):
return x_a(x_a, x_b)(*args, **kwargs)
def Y3_b(*args, **kwargs):
return x_b(x_a, x_b)(*args, **kwargs)
return func1(Y3_a, Y3_b)

def Y2_b(x_a, x_b):
def Y3_a(*args, **kwargs):
return x_a(x_a, x_b)(*args, **kwargs)
def Y3_b(*args, **kwargs):
return x_b(x_a, x_b)(*args, **kwargs)
return func2(Y3_a, Y3_b)

return (Y2_a(Y2_a, Y2_b), Y2_b(Y2_a, Y2_b))
```

to find the original functions' collective fixed point:

```(even, odd) = Y(even_incomplete, odd_incomplete)
print(even(6)) # "True"
```

This is already a little ugly, and the solution for three components is even more grotesque. However, I hope you can see the pattern forming. We can generalise from two functions to an arbitrary number of them quite easily.

### Variadic fixed point combinator - first attempt

First, for the sake of appearance, rewrite our incomplete functions a little:

```even_incomplete = lambda *funcs: \
lambda n: \
True if n == 0 else funcs[1](n - 1)
odd_incomplete = lambda *funcs: \
lambda n: \
False if n == 0 else funcs[0](n - 1)
```

They now refer to one another by number.

Then, you might try this (but it won't work):

```def Y(*funcs):
Y2s = []
for func in funcs:
def Y2(*xs):
Y3s = []
for x in xs:
def Y3(*args, **kwargs):
return x(*xs)(*args, **kwargs)
Y3s.append(Y3)
return func(*Y3s)
Y2s.append(Y2)
return (Y2(*Y2s) for Y2 in Y2s)
```

The result is somewhat alarming:

```(even, odd) = Y(even_incomplete, odd_incomplete)
print(even(6)) # "False"
```

What's going wrong?

### Behaviour of closures in Python

The exact stack trace leading to this bug is a little impenetrable, but the phenomenon can be demonstrated quite easily in microcosm. This behaviour is an artifact of the way in which Python handles closures.

```i = 78
def i_printer():
print(i)
i_printer() # "78"
i = 99901
i_printer() # "99901"
```

Python has implicit capture by reference. `i_printer` implicitly captures the variable `i` by reference. Even if `i` appears to have dropped out of scope, `i_printer` can still access it. And, if some external force modifies `i` later, `i_printer` will pick up on that change.

In our faulty `Y` function, there are two of these problems.

1. `Y3` refers to `x` - but the value of `x` is constantly changing over the course of the `for` loop.
2. `Y2` refers to `func` - but the value of `func` is constantly changing over the course of another `for` loop.

At the end of the loops, all the `Y3`s that were generated refer to the same `x`, when they should refer to different ones, and all the `Y2`s that were generated refer to the same `func`, when they too should refer to different ones.

Python provides no pleasing workarounds for this behaviour. Our solution will be to wrap a "getter" around our function:

```def get_i_printer(current_i):
def func():
print(current_i)
return func
# at this point, current_i drops safely out of
# scope and can no longer be modified

i = 78
i_printer = get_i_printer(i)
i_printer() # "78"
i = 99901
i_printer() # "78"
```

### Variadic fixed point combinator - repaired

Start as before:

```even_incomplete = lambda *funcs: \
lambda n: \
True if n == 0 else funcs[1](n - 1)
odd_incomplete = lambda *funcs: \
lambda n: \
False if n == 0 else funcs[0](n - 1)
```

Next, let's wrap our `Y2` and `Y3` definitions up:

```def Y(*funcs):
'''Return the fixed point of the input vector of functions.'''
def get_Y2(func):
def Y2(*xs):
def get_Y3(x):
def Y3(*args, **kwargs):
return x(*xs)(*args, **kwargs)
return Y3
Y3s = [get_Y3(x) for x in xs]
return func(*Y3s)
return Y2
Y2s = [get_Y2(func) for func in funcs]
return (Y2(*Y2s) for Y2 in Y2s)
```

And use `Y` to resolve our references:

```(even, odd) = Y(even_incomplete, odd_incomplete)
print(even(6)) # "True"
```

Ding.

### Bonus: with names

So you want your anonymous functions to be able to refer to one another by name instead of by number?

```even_incomplete = lambda **funcs: \
lambda n: \
True if n == 0 else funcs["odd"](n - 1)
odd_incomplete = lambda **funcs: \
lambda n: \
False if n == 0 else funcs["even"](n - 1)
```

```def Y(**funcs):
'''Return the fixed point of the input dict of functions.'''
def get_Y2(func):
def Y2(**xs):
def get_Y3(x):
def Y3(*args, **kwargs):
return x(**xs)(*args, **kwargs)
return Y3
Y3s = {name : get_Y3(x) for name, x in xs.items()}
return func(**Y3s)
return Y2
Y2s = {name : get_Y2(func) for name, func in funcs.items()}
return {name : Y2(**Y2s) for name, Y2 in Y2s.items()}
```

```funcs = Y(even=even_incomplete, odd=odd_incomplete)
print(funcs["even"](6)) # "True"
```

Here.

### Reference

A Variadic Extension of Curry's Fixed-Point Combinator by Mayer Goldberg, which is probably a lot easier to follow if, unlike me, you know Scheme

### Discussion (14)

#### 2013-03-25 14:12:38 by hpc:

You don't need a variadic fixed point combinator to do this. Structural recursion will do just fine: http://hpaste.org/84636

#### 2013-03-25 14:21:44 by qntm:

I don't fully understand Haskell, what's the equivalent of that in Python? The use of the term "fix" in your snippet seems to imply that, under the covers, Haskell is doing exactly what's described above.

#### 2013-03-25 14:56:43 by hpc:

Haskell's definition of fix is relatively simple: fix :: (a -> a) -> a fix f = f (fix f) To break it down for a non-Haskell programmer, it takes any function from a type to itself, and follows the standard evaluation rules to get just a thing of that same type. It works for functions as you are using it, where you substitute some kind of function type for 'a' above. However, it also works for any other kind of data structure. An infinite list of ones in Haskell is "fix (cons 1)". In my example, I am writing a tuple that is defined in terms of itself, and using "fix" to do it. It's hard to think up an analogous example in Python, because "def Y(f): return f(Y(f))" is clearly non-terminating. All you need is a library for lazy data structures, and you can naively rewrite the Haskell to use a 2-element array in place of the tuple. More importantly, the result of Y(f) no longer needs to be a function (or more precisely, you can solve for non-function fixed points). You can find the fixed point of a list, or a tree, or any other recursive data structure. You should get more comfortable with Haskell. There's far stranger things to learn than just Y, and I think it will make you a better Python programmer. At least, that's what happened for me with Perl.

#### 2013-03-25 22:01:30 by qntm:

So basically what the Haskell code does internally is exactly what my Python code does explicitly?

#### 2013-03-25 22:32:03 by qntm:

Being able to build recursive anonymous lists and dictionaries using similar fixed-point combinators sounds like a useful further piece of work, though.

#### 2013-03-26 19:36:13 by Alda:

Ha! I knew I saw that somewhere! I studied Compilers under Mayer Goldberg, and one of the assignments he gave us was exactly that: implementing variadic fixed-point combinators in Scheme.

#### 2013-03-28 21:41:37 by ns:

I don't think the problem is with Python's closures so much as with its for loop. As far as I know, it's normal for closures to bind references to mutable variables - of the languages I'm familiar with, Scala and Javascript both do this, and I can't think of any that break the rule. On the other hand, with a for-in loop, it seems counterintuitive for the loop variable to have a scope wider than a single pass through the loop. Switching out the for statements for maps in your first attempt is a fairly minor change and shouldn't make any difference, but the map version works while its for-loop cousin doesn't.

#### 2013-03-31 23:59:23 by MHD:

@hpc GHC's base implements fix as follows: fix :: (f -> f) -> f fix f = let x = f x in x It isn't as you said: fix f = f (fix f) Because that has an unfortunate property in the spineless tagless graph machine, namely it would make: main = let l = fix (1 :) in print (last l) Exit with memory error, while the GHC version just makes a programme that runs for ever. The fix you describe creates new thunks for every application of the function, while the GHC version doesn't.

#### 2013-04-28 18:24:00 by Veky:

> Python provides no pleasing workarounds for this behaviour. I don't know if it is pleasing enough for you, but certainly is for me: using default arguments, you can capture (a new instance of) current value instead of variable itself. http://stackoverflow.com/questions/2295290/what-do-lambda-function-closures-capture-in-python/2295372#2295372

#### 2013-12-13 08:12:46 by Sean:

Here was my short python solution: def fix(funcs_incomplete): funcs = {} apply_incomplete = lambda f: lambda *args, **kwargs: \ f(**funcs)(*args, **kwargs) funcs = {name: apply_incomplete(f) for (name, f) in funcs_incomplete.items()} return funcs funcs_incomplete = { "even": even_incomplete, "odd": odd_incomplete, } funcs = fix(funcs_incomplete) It seems to me like the central problem here is that, in the final result, every function needs to have a reference to each function, including itself, which means that you need to have a way to specify references to functions before they have actually been defined. In Haskell, that's trivial, because functions can be declared in any order without consequence. In Python, I created an empty dict as a placeholder, and populated later with a lookup table for functions by name. Sam's solution looks like it's doing almost of the same thing. But instead of containing an explicit reference to the output functions, Y3 contains the expression "x(*xs)", which just so happens to be the same as "Y2(*Y2s)".

#### 2013-12-13 08:14:43 by Sean:

Ugh. Whitespace. One more try. >def fix(funcs_incomplete): > funcs = {} > apply_incomplete = lambda f: lambda *args, **kwargs: \ > f(**funcs)(*args, **kwargs) > funcs = {name: apply_incomplete(f) > for (name, f) in funcs_incomplete.items()} > return funcs > >funcs_incomplete = { > "even": even_incomplete, > "odd": odd_incomplete, >} > >funcs = fix(funcs_incomplete)

#### 2013-12-13 08:18:04 by Sean:

Plain text only. Line breaks become `<br/>`