Comparing two functions without invoking them

Question
5

In the abstract

If you have no prior knowledge of each, this is not just impossible in Scala, but theoretically as well !

It’s what we call an undecidable problem. It is closely linked with the halting problem.

An intuitive way to see that this is at least the hardest possible problem, consider the following:
For most currently unsolved problems in math, there is a relatively simple program which has different behavior depending on whether the conjecture is true or not.
The simplest I know of is the 3 + 1 problem:

def collatz(x: Int): Unit =
  if x == 1 then
    return ()
  else if x % 2 == 0 then // even branch
    solve( x / 2 )
  else                    // odd branch
    solve( 3x + 1 )

val a = (x: Int) => solve(x)

val b = (x: Int) => ()

If a == b then the conjecture is true: every starting number eventually reaches 1 (in our program, returns ())
Otherwise, the conjecture is false: there exists an x such that collatz never reaches 1 (since the function must not return () on that input)

One concrete interpretation

It is possible you only wish to test the syntactic equality of functions:

val a = (x: Int) => 1
val b = (x: Int) => 0 + 1

myCustomTest(a, b) // returns false, since "1" is not the same as "0 + 1"

This is possible through reflection, but it would be hard and imperfect*, and it’s difficult to see the use for such a narrow definition of equivalence

*(x: Int) => 0+1 would be equal to (x: Int) =>/* hehe */ 0 + 1 since the whitespace and comments are not encoded into the reflection API (IIRC)

3 Likes