functional programming - How to test if two functions are the same?

Question

I found a code snippet somewhere online:

(letrec
  ([id (lambda (v) v)]
   [ctx0 (lambda (v) `(k ,v))]
         .....
         .....
         (if (memq ctx (list ctx0 id)) <---- condition always return false
         .....

where ctx is also a function:

However I could never make the test-statement return true.

Then I have the following test:

(define ctx0 (lambda (v) `(k ,v)))
(define ctx1 (lambda (v) `(k ,v)))
(eq? ctx0 ctx1)
=> #f
(eqv? ctx0 ctx1)
=> #f
(equal? ctx0 ctx1)
=> #f

Which make me suspect that two function are always different since they have different memory location.

But if functions can be compared against other functions, how can I test if two function are the same? and what if they have different variable name? for example:

(lambda (x) (+ x 1)) and (lambda (y) (+ y 1))

P.S. I use DrRacket to test the code.

Answer 1

You can’t. Functions are treated as opaque values: they are only compared by identity, nothing more. This is by design.

---

But why? Couldn’t languages implement meaningful ways to compare functions that might sometimes be useful? Well, not really, but sometimes it’s hard to see why without elaboration. Let’s consider your example from your question—these two functions seem equivalent:

(define ctx0 (lambda (v) `(k ,v)))
(define ctx1 (lambda (v) `(k ,v)))

And indeed, they are. But what would comparing these functions for equality accomplish? After all, we could just as easily implement another function:

(define ctx2 (lambda (w) `(k ,w)))

This function is, for all intents and purposes, identical to the previous two, but it would fail a na?ve equality check!

In order to decide whether or not two values are equivalent, we must define some algorithm that defines equality. Given the examples I’ve provided thus far, such an algorithm seems obvious: two functions should be considered equal if (and only if) they are α-equivalent. With this in hand, we can now meaningfully check if two functions are equal!

...right?

(define ctx3 (lambda (v) (list 'k v)))

Uh, oh. This function does exactly the same thing, but it’s not implemented exactly the same way, so it fails our equality check. Surely, though, we can fix this. Quasiquotation and using the list constructor are pretty much the same, so we can define them to be equivalent in most circumstances.

(define ctx4 (lambda (v) (reverse (list v 'k))))

Gah! That’s also operationally equivalent, but it still fails our equivalence algorithm. How can we possibly make this work?

---

Turns out we can’t, really. Functions are units of abstraction—by their nature, we are not supposed to need to know how they are implemented, only what they do. This means that function equality can really only be correctly defined in terms of operational equivalence; that is, the implementation doesn’t matter, only the behavior does.

This is an undecidable problem in any nontrivial language. It’s impossible to determine if any two functions are operationally equivalent because, if we could, we could solve the halting problem.

Programming languages could theoretically provide a best-effort algorithm to determine function equivalency, perhaps using α-equivalency or some other sort of metric. Unfortunately, this really wouldn’t be useful—depending on the implementation of a function rather than its behavior to determine the semantics of a program breaks a fundamental law of functional abstraction, and as such any program that depended on such a system would be an antipattern.

Function equality is a very tempting problem to want to solve when the simple cases seem so easy, but most languages take the right approach and don’t even try. That’s not to say it isn’t a useful idea: if it were possible, it would be incredibly useful! But since it isn’t, you’ll have to use a different tool for the job.