2013-03-24 by
qntm

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.

- 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
- JavaScript code
- Reference

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.

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.

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?

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"

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.

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"

Here.

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 23:59:23 by MHD:

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

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

## 2013-10-08 22: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: