python lambda functions behavior-CodePudding

I am having a hard time understanding the behavior of these lambda functions in python 3.10.0

I am trying to define the NOT logical operator from lambda calculus (see, e.g., the definition on wikipedia The following implementation is correct:

In [1]: TRUE  = lambda a: lambda b: a
   ...: FALSE = lambda a: lambda b: b
   ...: NOT = lambda a: a(FALSE)(TRUE)
   ...: assert NOT(FALSE) == TRUE

However, when I try and do a literal substitution either for FALSE or TRUE, the code fails

In [2]: NOT1 = lambda a: a(FALSE)(lambda a: lambda b: a)
   ...: assert NOT1(FALSE) == TRUE
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[2], line 2
      1 NOT1 = lambda a: a(FALSE)(lambda a: lambda b: a)
----> 2 assert NOT1(FALSE) == TRUE

AssertionError:

Can anybody explain me why this happens?

CodePudding user response：

Python function == works by object identity. (Trying to implement it any other way ranges from "painfully inconsistent" to "plain impossible".) You have created another function with the same behavior as your NOT function, but it is not the same function object, so == says they're not equal.

CodePudding user response：

The main principle is that every invocation of lambda creates a new function.

Your first cell is exactly this:

def TRUE(a):
    def _inner(b):
        return a
    return _inner

def FALSE(a):
    def _inner(b):
        return b
    return _inner

def NOT(a):
    return a(FALSE)(TRUE)

Executing NOT(FALSE) results in FALSE(FALSE)(TRUE) results in FALSE._inner(TRUE) returning TRUE, a function.

Now your second cell, executing NOT1(FALSE) results in FALSE(FALSE)(lambda...) results in FALSE._inner(lambda...) returning lambda..., another function but not the same function defined in TRUE. Remember the principle I said earlier? That lambda statement created a new function.

The == operator when comparing two functions does not concern itself with the contents of the function. It only concerns itself whether the items being compared are pointing to the exact same function in memory. But since TRUE and lambda... are two separate functions -- at different memory locations even if the contents are the same -- then == comparison fails.