Ensuring Equivalence in Python Functions: Understanding Implementation Impacts

Question

In defining function equivalence, several factors come into play:

• Producing equivalent results
• Sharing the same (non-)termination behavior
• Mutating (non-local) memory similarly
• Maintaining identical input/output and raising the same exceptions

Moreover, renaming arguments without altering their order should not affect equivalence, unless they refer to something else within the function body.

def g(x: bool) -> bool: 
    return True

# Functions f and f2 are equivalent

def f(x: bool) -> bool:
    return x and g(x)

def f2(x: bool) -> bool:
    if x:
        return g(x)
    else:
        return False

# Functions f3 and f4 are not equivalent

def f3(x: bool) -> bool:
    return x and g(x)

def f4(x: bool) -> bool:
    if g(x):
        return x
    else:
        return False

Consider the equivalence between f and f2: in both functions, g(x) is invoked only when x is True, adhering to the same rule. Also, f3 and f4 reveal a distinct implementation. In f3, g(x) remains uncalled if x is False, whereas in f4, g(x) is invoked regardless of the value of x.

I'm curious as to why f3 and f4 are considered non-equivalent. Despite having identical output for all potential inputs, is their lack of equivalence only due to implementation differences?

Answer 1

In an ideal world,

• All functions would be pure.
• The and operator is defined to be commutative, meaning (a and b) == (b and a).

The above conditions justifies the short-circuiting in and's implementation. This should allow us to consider f3 and f4 as equivalent.

But, Python isn't a pure functional programming language, which means the function g could have non purity / side-affects, like printing to I/O, writing to a database, making an API call etc.

Because of this side-affects, the short-circuiting can yield unexpected results, making f3 and f4 non-equivalent.