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

Read on.

### Contents

- Summary of previous results
- Dyadic fixed point combinator
- Variadic fixed point combinator - first attempt
- Behaviour of closures in Python
- Variadic fixed point combinator - repaired
- Bonus: with names
- Reference

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

### Dyadic fixed point combinator

Start with two anonymous functions, looking something like this:

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.

`Y3`

refers to`x`

- but the value of`x`

is constantly changing over the course of the`for`

loop.`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?

Start with this:

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)

Here's your combinator:

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

And here's your code:

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

### 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:

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

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

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

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

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

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

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

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

## 2013-10-08 20:07:07 by oddsock:

## 2013-10-08 21:49:32 by qntm:

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

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

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