What is the explanation of the python code which uses anonymous lambda to implement factorial function

Question

This function really makes me flummoxed. Could anyone explain the key ideas ? It will be better if there are some examples to demonstrate how the function works.

from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    """
    return (lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))

Answer 1

So rewriting in a longer form:

def make_anonymous_factorial():
  def func1(f):
    def func2(k):
      return f(f, k))
    return func2
  def func3(f, k):
    if k == 1:
      return k
    else:
      return mul(k, f(f, sub(k, 1)))
  return func1(func3)

And simplifying again:

def make_anonymous_factorial():
  def func1(factorial_function):
    def func2(k):
      factorial_function(factorial_function, k))
    return func2
  def factorial(recursive_func, k):
    if k == 1:
      return k
    else:
      return k * recursive_func(recursive_func, k-1)
  return func1(factorial)

Normally you could write factorial like:

def factorial(k):
    if k == 1:
      return k
    else:
      return k * factorial(k-1)

...but then this relies on factorial being able to reference itself by name. As an anonymous function, it can't do that, so it needs to be passed "itself" as an argument, so it knows whom to call.

The func1 and func2 are just setting up the system to call itself:

def func1(factorial_function):
  def func2(k):
    factorial(factorial_function, k))
func1(factorial)

This returns a function (func2 as a closure, with access to the enclosing scope containing factorial_function). That func2, when called, will call factorial(factorial, k) and thus compute the factorial function.

Answer 2

I write it here because I can't post indented code in comments. @MikeLambert: the first part of your code is wrong. It should be:

def func1(f):
    def func2(k):
        return f(f, k)

    return func2

A word of explanation for Dimen61: this is because lambda functions are a "shortcut" for defining functions. So:

lambda x, y, z...: some_expression

is equivalent to

def someFunction(x, y, z):
    return some_expression

Returning to our "nested" lambdas

lambda f: lambda k: f(f, k)

the expression can be translated to

def func1(f):
    return lambda k: f(f, k)

and transforming also the other lambda you obtain the expression above.

I would also add that I completely agree with TigerhawkT3: this code is ugly, and even if Lambert unencrypted it, I consider it completely useless.