9

Let's say I have two python functions f and g:

def f(x):
    y = x**2 + 1
    return y

def g(x):
    a = x**2
    b = a + 1
    return b

These two functions are clearly functionally equivalent (both return x**2 + 1).

My definition of functionally equivalent is as follows:

If two functions f and g always produce the same output given the same input, then f and g are functionally equivalent.

Further, let's say no global variables are involved in f and g.

Is it possible to automatically determine (without human inspection) if python functions f and g are functionally equivalent?

Improve this question
9
  • I guess you could check whether they compile down to the same bytecode, but that could produce false negatives. Commented Apr 25, 2016 at 23:35
  • Within a margin of error, just try a bunch of random inputs. Commented Apr 25, 2016 at 23:35
  • @TigerhawkT3 do you know if f and g from the example above would compile down to the same bytecode? Commented Apr 25, 2016 at 23:35
  • @SlaterTyranus - def r1(): return random.random() - def r2(): return random.random(). Commented Apr 25, 2016 at 23:36
  • 2
    You can check bytecode with dis.dis(myfunction). If two functions do compile to the same bytecode, they must be functionally equivalent (according to the compiler, at least). However, as I mention above and Slater notes, there could be false negatives - different bytecode for two functions that are functionally equivalent. Commented Apr 25, 2016 at 23:38

3 Answers 3

Reset to default
15

By Rice's Theorem, no. If you could do this, you could solve the halting problem. (This is true even if f and g are always guaranteed to halt.)

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Ah actually this is not quite correct, because python functions are not abstract, opaque objects. You can compare to see if they have the same bytecode.
@Marcin: First, no, comparing the bytecode doesn't work. At all. Second, even if you add in the other distinguishing features you need to compare, the comparison still doesn't even recognize the two functions from the question as equivalent. Third, Turing machines aren't opaque either. You can compare and analyze two Turing machines as easily as you can compare and analyze two Python functions, but neither analysis will be able to answer nontrivial questions like "does my new algorithm give the same results as the old one?"
It is possible to prove the equivalence of some functions using the Z3 Python API.
@AndersonGreen: Those are functions in the mathematical sense. This question is talking about functions in the sense of Python function objects. It is sometimes possible to prove that two functions in the sense of Python function objects are equivalent, but not in practically useful cases, and it'll look very different from a proof about functions in the mathematical sense.
2

If the functions are actually the same object, you can simply do f == g and see if they are the same object.

Secondly, if the functions have the same bytecode (f.func_code.co_code) then they are equivalent.

Equivalently (but probably more portably), you can use dis.dis to obtain the same information. Note that this will be subject to false negatives, as in this case.

I understand that dill will go one better, and allow you to retrieve the function text. With that information, you could use ast to parse the text, and perform similar analyses to optimising compilers, to decide whether the code can be "optimised" to the same syntax tree. Again, there will be functionally equivalent functions that can't simply be reduced to the same ast.

So, yes for certain pairs of functionally equivalent functions this detection is possible, but there will always be false negatives.

Improve this answer

1 Comment

Equal co_code does not guarantee that two functions are equivalent. def f(x): return x + 1 and def f(x): return x + 2 have equal co_code.
0

Yeah. You can do it for actual computers, because they are not Turing machines with infinite memory, you know that the set of inputs is finite and therefore two busy beavers will bound the runtime, which means that you have an oracle telling you if it will halt or not.

For example for integer functions, you just try every possible input:

class integer_function:
    __eq__(self, other):
        for i in range(-sys.maxint - 1, sys.maxint):
            s = multiprocessing.Process(self, [i])
            o = multiprocessing.Process(other, [i])
            s.start
            o.start
            dont know how to write in python but basically wait a hugely many instructions which bounds the running time of s and o until they must halt or is known to run forever

            if s.is_alive() and not o.is_alive() or not s.is_alive() and o.is_alive():
                return False
            if s.is_alive() and o.is_alive():
                break
            if not self(i) == other(i):
                return False
    return True

This will give you if they are functionally equivalent.

Im pretty sure this kind of method works for any python function.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.