strange returning value in a python function

cons is a function, that takes two arguments, and returns a function that takes another function, which will consume these two arguments.

For example, consider the following function:

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

This is just a function that adds the two inputs, so, for instance, add(2, 5) == 7

As this function takes two arguments, we can use cons to call this function:

func_caller = cons(2, 5)  # cons receives two arguments and returns a function, which we call func_caller

result = func_caller(add) # func_caller receives a function, that will process these two arguments

print(result)             # result is the actual result of doing add(2, 5), i.e. 7 

This technique is useful for wrapping functions and executing stuff, before and after calling the appropriate functions.

For example, we can modify our cons function to actually print the values before and after calling add:

def add(a, b):
    print('Adding {} and {}'.format(a, b))
    return a + b


def cons(a, b):
    print('Received arguments {} and {}'.format(a, b))
    def pair(f):
        print('Calling {} with {} and {}'.format(f, a, b))
        result = f(a, b)
        print('Got {}'.format(result))
        return result
    return pair

With this update, we get the following outputs:

 func_caller = cons(2, 5)
 # prints "Received arguments 2 and 5" from inside cons

 result = func_caller(add)
 # prints "Calling add with 2 and 5" from inside pair
 # prints "Adding 2 and 5" from inside add
 # prints "Got 7" from inside pair

This isn't going to make any sense to you until you know what cons, car, and cdr mean.

In Lisp, lists are stored as a very simple form of linked list. A list is either nil (like None) for an empty list, or it's a pair of a value and another list. The cons function takes a value and a list and returns you another list just by making a pair:

def cons(head, rest):
    return (head, rest)

And the car and cdr functions (they stand for "Contents of Address|Data Register", because those are the assembly language instructions used to implement them on a particular 1950s computer, but that isn't very helpful) return the first or second value from a pair:

def car(lst):
    return lst[0]
def cdr(lst):
    return lst[1]

So, you can make a list:

lst = cons(1, cons(2, cons(3, None)))

… and you can get the second value from it:

print(car(cdr(lst))

… and you can even write functions to get the nth value:

def nth(lst, n):
    if n == 0:
        return car(lst)
    return nth(cdr(lst), n-1)

… or print out the whole list:

def printlist(lst):
    if lst:
        print(car(lst), end=' ')
        printlist(cdr(lst))

If you understand how these work, the next step is to try them on those weird definitions you found.

They still do the same thing. So, the question is: How? And the bigger question is: What's the point?

Well, there's no practical point to using these weird functions; the real point is to show you that everything in computer science can be written with just functions, no built-in data structures like tuples (or even integers; that just takes a different trick).

The key is higher-order functions: functions that take functions as values and/or return other functions. You actually use these all the time: map, sort with a key, decorators, partial… they’re only confusing when they’re really simple:

def car(f):
    def left(a, b):
        return a
    return f(left)

This takes a function, and calls it on a function that returns the first of its two arguments.

And cdr is similar.

It's hard to see how you'd use either of these, until you see cons:

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

This takes two things and returns a function that takes another function and applies it to those two things.

So, what do we get from cons(3, None)? We get a function that takes a function, and applies it to the arguments 3 and None:

def pair3(f):
    return f(3, None)

And if we call cons(2, cons(3, None))?

def pair23(f):
    return f(2, pair3)

And what happens if you call car on that function? Trace through it:

def left(a, b):
    return a
return pair23(left)

That pair23(left) does this:

return left(2, pair3)

And left is dead simple:

return 2

So, we got the first element of (2, cons(3, None)).

What if you call cdr?

def right(a, b):
    return a
return pair23(right)

That pair23(right) does this:

return right(2, pair3)

… and right is dead simple, so it just returns pair3.

You can work out that if we call car(cdr(pair23)), we're going to get the 3 out of it.

And now you can write lst = cons(1, cons(2, cons(3, None))), write the recursive nth and printlist functions above, and trace through how they work on lst.

I mentioned above that you can even get rid of integers. How do you do that? Read about Church numerals. You define zero and successor functions. Then you can define one as successor(zero) and two as successor(one). You can even recursively define add so that add(x, zero) is x but add(x, successor(y)) is successor(add(x, y)), and go on to define mul, etc.

You also need a special function you can use as a value for nil.

Anyway, once you've done that, using all of the other definitions above, you can do lst = cons(zero(cons(one, cons(two, cons(three, nil)))), and nth(lst, two) will give you back one. (Of course writing printlist will be a bit trickier…)

Obviously, this is all going to be a lot slower than just using tuples and integers and so on. But theoretically, it’s interesting.

Consider this: we could write a tiny dialect of Python that has only three kinds of statements—def, return, and expression statements—and only three kinds of expressions—literals, identifiers, and function calls—and it could do everything normal Python does. (In fact, you could get rid of statements altogether just by having a function-defining expression, which Python already has.) That tiny language would be a pain to use, but it would a lot easier to write a program to reason about programs in that tiny language. And we even know how to translate code using tuples, loops, etc. into code in this tiny subset language, which means we can write a program that reasons about that real Python code.

In fact, with a couple more tricks (curried functions and/or static function types, and lazy evaluation), the compiler/interpreter could do that kind of reasoning on the fly and optimize our code for us. It’s easy to tell programmatically that car(cdr(cons(2, cons(3, None)) is going to return 3 without having to actually evaluate most of those function calls, so we can just skip evaluating them and substitute 3 for the whole expression.

Of course this breaks down if any function can have side effects. You obviously can’t just substitute None for print(3) and get the same results. So instead, you need some clever trick where IO is handled by some magic object that evaluates functions to figure out what it should read and write, and then the whole rest of the program, the part that users write, becomes pure and can be optimized however you want. With a couple more abstractions, we can even make IO something that doesn’t have to be magical to do that.

And then you can build a standard library that gives you back all those things we gave up, written in terms of defining and calling functions, so it’s actually usable—but under the covers it’s all just reducing pure function calls, which is simple enough for a computer to optimize. And then you’ve basically written Haskell.