Variadic fixed point combinators

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

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

Back to Code
Back to Things Of Interest

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 22: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 17: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-10-08 20:07:07 by oddsock:

Hi, thanks for your post. I'm afraid I couldn't make head or tails of your Python code (because I don't know Python), but the phrase "dyadic fixed point combinator" gave me the kick I needed to solve my problem.

I'm doing stuff in O'Caml, so I wouldn't ordinarily need any fixed point combinators because <code>let rec</code> does the job admirably, including mutual recursion. However, I'm doing memoisation. To memoise a recursive function, you need a high-order function, say <code>memo</code>,
which takes an ordinary function and returns a memoised version of it, but snag is that the ordinary function needs to refer to the memoised function which <code>memo</code> is going to return. On the face of it, you might try something like <code>let rec memfun = memo (fun x -> ..... memfun ....)</code>. In Haskell, this would be no problem, but O'Caml, being strict, has certain restrictions on the use of <code>let rec</code> which scupper this plan. So, I needed to use incomplete functions as you described in your post and was able to define monadic and dyadic fixed point combinators very easily:
<pre>
  (* fixed point combinator *)
  (* fp : (('a -> 'b) -> ('a -> 'b)) -> 'a -> 'b *)
  let fix f = let rec p x = f p x in p
 
  (* dyadic fixed point combinator *)
  (* fp : (('a -> 'b) * ('c -> 'd) -> 'a -> 'b)
   * * (('a -> 'b) * ('c -> 'd) -> 'c -> 'd)
   * -> ('a -> 'b) * ('c -> 'd) i
   *)
  let fix2 (f,g) =
    let rec fp x = f (fp,gp) x
    and gp x = g (fp,gp) x
    in (fp,gp)
</pre>
Then, using a nice trick by Bruce McAdam <a href="http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/">here</a>, I was able to write monadic and dyadic memoisers very simply as follows:
<pre>
  (* memoinc takes an incomplete recursive function whose complement (the part that tells
   * it what to do if recursive calls are required) is an arbitrary type 'c, and returns
   * a new incomplete recursive function with the same type that does memoisation.
   *
   * memoinc : ('c -> 'a -> 'b) -s-> ('c -> 'a -s-> 'b)
   *
   * The -s-> arrows denote function evaluations which affect global state.
   *)
  let memoinc f =
    let loc = ref BatMap.empty in
    fun comp x -> try BatMap.find x !loc
                  with Not_found -> let v = f comp x in
                                    loc := BatMap.add x v !loc; v

  let memorec f = fix (memoinc f)
  let memorec2 f g = fix2 (memoinc f, memoinc g)
</pre>
There was a lot more code than this at one point, but then after I pinned down the definition of <code>memoinc</code>, it all just boiled away in a very pleasing manner. Thanks again for the tip.

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

Oh dear, that hasn't rendered at all. I'm glad you found this article useful though.

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:

Should have just done this to start with:

https://gist.github.com/quantheory/7941245