It's Fun(ctional)

Of course, we can simply run it:

1
2
3
4
5

>>> x = lambda x: x(x)
>>> y = lambda y: (lambda z: y(y(z)))
>>> z = lambda z: z+1
>>> print (x)(y)(z)(0)
# prints 4

but that kind of defeats the point. So instead, we will analyze what this code does. The following solution is aimed for people that have never known lambda s and functional programming before, but can understand functions in Python.

lambda is just a fancy way to say "I want a 'simple' function, and am too lazy to give it a name", where "simple" means "computes a single statement and immediately returns its value". In other words, if we have print (lambda x: x*x)(2) , it's more or less the same as:

1
2
3
4

def some_function_whose_name_we_do_not_care(x):
    return x*x

print some_function_whose_name_we_do_not_care(2)

And since lambda is mostly used just to avoid giving names to simple computations, assigning a lambda to a name more or less defeats the point; the three assignments are equivalent to:

1
2
3
4
5
6
7
8
9

def x(x0):
    return x0(x0)

def y(y0):
    def z(z0):
        return y0(y0(z0))

def z(z0):
    return z0+1

(Note the renaming of the arguments; we don't have to, but it makes us to understand the code much easier.)

Now, we can see that x is a function that takes another function x0 (with one argument), and applies x0 to with itself being the argument. z is just a function that increments its input. What is y ?

We first need to know what a function inside a function means. Normally, we write a function with two variables as:

1
2

def our_function(arg1, arg2):
    # do stuff

We invoke it with our_function(1, 2) , for example. We need to give both arguments at the same time; doing our_function(1) won't work. What if we want to put just some of the arguments, not all, and complete it at a later time?

Currying is a way to do this. Instead of having a function that takes two arguments (and thus must be supplied at the same time), we just take one argument instead, which returns another function that takes the second argument. That is, we do:

1
2
3

def our_function(arg1):
    def temporary_function(arg2):
        # do stuff

This way, we can call our_function(1) ; now we have a function that can be supplied with the second argument later. As the expense, this is the only way we can call the function; if we want to call it with two arguments like before, we need to go in a roundabout way (our_function(1))(2) ; we first give the first argument 1 , and immediately give the second argument 2 to the result.

As an example, we might have this:

1
2
3
4
5
6

def addition_no_currying(a, b):
    return a+b

def addition_with_currying(a):
    def temporary_function(b):
        return a+b

And now, addition_no_currying(1, 2) will return 3 , but we cannot do addition_no_currying(1) . Instead, we can put addition_with_currying(1) , which will give a function that increments its input (because giving it the argument b will return the result 1+b ). And if we want to just compute a single addition, not making a function to increment, we can do that with (addition_with_currying(1))(2) which will also return 3 .

Now, we can understand y . It is a curried function that takes two arguments y0 and z0 , and applies y0 on z0 twice (it compute y0(z0) , takes its result, and uses it as the argument for y0 ).

To understand these, it might be better to illustrate them with examples:

1
2
3
4
5

>>> x(lambda a: str(a))
'<function <lambda> at 0x02B85780>'

>>> (y(lambda a: a+1))(1)
3

In the first example, we apply x , thus we get (lambda a: str(a))(lambda a: str(a)) . The first lambda a: str(a) indicates that we want the argument to be converted to a string. The second lambda a: str(a) is just a function object that we never get to use anywhere; it's simply treated as an object, and it's given to the first lambda a: str(a) , which prints it as a string. When Python converts a function to a string, it just gives <function [name] at [address]> , where name is the name of the function, if any, and address is the address of the function object in memory; in this case, it's a lambda that we never give a name into, so it appears as <lambda> , and its address is 0x02B85780 when I run it. (Running it on different computers/times can produce different addresses.)

In the second example, we apply the increment function lambda a: a+1 twice to 1 . The first time, we get 2 ; the second time, we apply it on 2 to get 3 .

Now that we know what they do, let's rename them so we can understand the logic better: x is apply_to_itself , y is apply_twice , and z is increment . So the modified code is:

1
2
3
4

apply_to_itself = lambda x: x(x)
apply_twice = lambda y: (lambda z: y(y(z)))
increment = lambda z: z+1
print (apply_to_itself)(apply_twice)(increment)(0)

Now with the knowledge of lambda in hand, we can try to parse what the statement (apply_to_itself)(apply_twice)(increment)(0) means.

First, apply_to_itself doesn't need any parentheses; you can try that (str)(123) and str(123) give the same result '123' . So now we have apply_to_itself(apply_twice)(increment)(0) .

Function application is left-associative; that is, f1(f2)(f3) means (f1(f2))(f3) . So we can add parentheses to the above to get ((apply_to_itself(apply_twice))(increment))(0) .

The first application is easy; apply_to_itself(apply_twice) can be evaluated to apply_twice(apply_twice) . Our statement now reads ((apply_twice(apply_twice))(increment))(0)

Now, apply_twice needs to take two consecutive arguments. We have the first one, apply_twice . The next one is given afterwards; increment . Applying apply_twice twice on increment , we change (apply_twice(apply_twice))(increment) to apply_twice(apply_twice(increment)) . Note the subtle change of parentheses; that's all the work that is done, but that's because the first argument (the middle text) is apply_twice . To compare, (apply_twice(str))(increment) would give str(str(increment)) . Our statement now reads (apply_twice(apply_twice(increment)))(0) .

Now, consider apply_twice(increment) , the part that's inside. We know apply_twice needs two arguments. It has one argument, increment , so we now have a function that takes an argument -- the second argument -- and applies increment twice to it. That is, apply_twice(increment) is the same as lambda arg2: increment(increment(arg2)) . Our statement now reads (apply_twice( lambda arg2: increment(increment(arg2)) ))(0) .

We're close! The first apply_twice needs two arguments. Conveniently, they are supplied right after: the first is the function lambda arg2: increment(increment(arg2)) , and the second is 0 . The result is (lambda arg2: increment(increment(arg2)))((lambda arg2: increment(increment(arg2)))(0)) .

The inner portion, (lambda arg2: increment(increment(arg2)))(0) , can now be evaluated. Computing the application (lambda x: <stuff>)(arg) is simply substituting x by arg everywhere in <stuff> . Thus, (lambda arg2: increment(increment(arg2)))(0) computes as increment(increment(0)) , which is 2 . Our statement reads (lambda arg2: increment(increment(arg2)))(2) . We can apply this once more, giving increment(increment(2)) which returns 4 . This is our answer.

TL;DR : This problem is a complicated way of saying "add 4".