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
• JavaScript code
• 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.

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 Y3s that were generated refer to the same x, when they should refer to different ones, and all the Y2s 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"

JavaScript code

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