如何测试两个函数是否相同？ [英] How to test if two functions are the same?

问题描述

我在网上找到了某处的代码片段：

 （letrec 
（[id（lambda（v）v）] 
 [ctx0（lambda（v）`（k，v）） ] 
 ..... 
 ..... 
（if（memq ctx（list ctx0 id））< ---- condition always return false 
 .. ... 
  

其中ctx也是一个函数：

然而，我永远不会让测试语句返回true。

然后我有以下测试：

 （define ctx0（lambda（v）`（k，v）））
（define ctx1（lambda（v）`（k，v）））
（eq？ctx0 ctx1）
 => #f 
（eqv？ctx0 ctx1）
 => #f 
（等于？ctx0 ctx1）
 => #f 
  

这让我怀疑两个函数总是不同，因为它们具有不同的内存位置。

但是如果函数可以与其他函数进行比较，我该如何测试两个fun ction是一样的吗？以及如果他们有不同的变量名称呢？例如：

（lambda（x）（+ x 1））和（ lambda（y）（+ y 1））

PS我使用DrRacket来测试代码。

解决方案

不能。函数被视为不透明价值观：他们只是通过身份来比较，没有更多。 这是设计。

---

但是为什么？ Couldn' t语言实现有意义的方式来比较有时可能有用的函数？那么，不是真的，但有时很难理解为什么没有详细说明。让我们从你的问题中考虑你的例子 - 这两个函数似乎是相同的：

 （define ctx0（lambda （v）`（k，v）））
（define ctx1（lambda（v）`（k，v）））
  

事实上，他们是。但是，比较这些功能的平等完成？毕竟，我们可以轻松地实现另一个函数：

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $（定义ctx2（lambda（w）`（k，w） ））

对于所有意图和目的，此函数相同前两个，但它会失败一个天真的平等检查！

为了决定两个值是否相等，我们必须定义一些定义相等性的算法。鉴于迄今为止我提供的例子，这样的算法看起来很明显：如果（并且只有）它们是α-等效。有了这个，我们现在可以有意义地检查两个函数是否相等！

...对吗？

 （define ctx3（lambda（v）（list'kv）））
  

呃，哦。这个函数的功能完全一样，但它没有以完全相同的方式实现，所以它没有通过相等检查。当然，我们可以解决这个问题。 Quasiquotation和使用 list 构造函数几乎相同，所以我们可以在大多数情况下将它们定义为等价。

< pre $ （define ctx4（lambda（v）（reverse（list v'k））））


嘎！这在操作上也是等价的，但它仍然失败了我们的等价算法。我们如何才能做到这一点？

---

原来我们不能，真的。函数是抽象的单位 - 就其性质而言，我们并不需要知道它们是如何实现的，而只是它们的作用。这意味着函数相等性只能根据运算等价性正确定义;也就是说，实现并不重要，只有行为才行。

当然，这在任何非平凡语言中都是不可判定的问题。无法确定任何两个函数在操作上是否相同，因为如果可以的话，我们可以解决停止问题。编程语言在理论上可以提供一个尽力而为的算法来确定函数等价性，也许使用α-等价或其他类型的度量。不幸的是，这实际上并不会有用 - 取决于函数的实现而不是它的行为来确定程序的语义打破了功能抽象的基本规律，并且因此依赖于这样的系统的任何程序将是反模式。
$ b 功能相等是一个非常诱人的问题，当简单案例看起来很简单时就想解决问题，但大多数语言都采用正确的方法甚至不尝试。这并不是说这不是一个有用的想法：如果可能的话，这将是非常有用的！但由于事实并非如此，您必须为这项工作使用不同的工具。

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.

解决方案

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 equivalent 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 equivalency; that is, the implementation doesn’t matter, only the behavior does.

This, of course, 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.

这篇关于如何测试两个函数是否相同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！