In lambda calculus, all functions are anonymous, so we can not define a recursive function in usual way, e.g. call function itself by name inside function’s body.

1
2
# we can not do this invoke self thing
lambda x: 1 if x < 2 else x * invoke_self(x - 1)

To tackle this issue, we can assume we already have one function f which can calculate factorial of x. Then we use this helper function f to implement our factorial function.

1
2
# we use currying here rather than write lambda f, x:
lambda f: lambda x: 1 if x < 2 else x * f(x - 1)

To use this function, we need to pass two arguments, one is the helper function f, the other is the number we need to calculate its factorial.

1
2
F = lambda f: lambda x: 1 if x < 2 else x * f(x - 1)
F(f)(5) == 120

By now, we get a function F1 = F(f), and with this F1, we can calculate factorial of any number. Then we get to know one thing: actually, F1 is our helper function f!
Let’s look closer, F1 = F(f) and F1 is f so F1 = F(F1). If we know fixed point concept in mathematics, then we’ll find out that F1 is a fixed point of F.
If we have one function T, for any given F: T(F) == F(T(F)), e.g. T(F) is a fixed point of F. Then we can easily write recursive functions, for our factorial example:

1
factorial = T(lambda f: lambda x: 1 if x < 2 else x * f(x - 1))

OK, let’s figure out the definition of T. Wait, we already have the definition of T: T(F) == F(T(F)). Except that this definition is a recursive definition. But we are good at eliminating recursion.

1
2
3
4
5
6
7
# T = lambda y: y(T(y))
# we define T1 which accept two arguments, first one is T1 itself
T1 = lambda x: lambda y: y(x(x)(y))
# to get T, we just apply T1 to T1
T = T1(T1)
# in conclusion
T = (lambda x: lambda y: y(x(x)(y)))(lambda x: lambda y: y(x(x)(y)))

This T is the Turing fixed-point combinator. But if we test it in Python, we will get RuntimeError: maximum recursion depth exceeded. This is because Python use strict evaluation strategy, so when we call T(F), it try to evaluate arguments immediately, then endless evaluation occur. To work around this, we don’t return value directly in T1, we return the function:

1
2
3
T1 = lambda x: lambda y: lambda z : y(x(x)(y))(z)
T = T1(T1)
print T(lambda f: lambda x: 1 if x < 2 else x * f(x - 1))(5)