这是一个创建于 1315 天前的主题，其中的信息可能已经有所发展或是发生改变。
val foo1 = { println()}
val foo2 = { println()}
fun bar(a: Any): (b: Any) -> Unit {
return { b -> println("$a $b") }
}
val bar1 = bar(0)
val bar2 = bar(0)
foo1 、foo2， bar1 、bar2 是作用完全相同的两组方法
有什么办法能判断他们是等价的吗？
 |
1
sillydaddy 2020-09-12 12:15:54 +08:00
如果你说的『函数』是指任意的函数，那么是不可能的，跟图灵停机问题类似。
可以参考 https://www.zhihu.com/question/26881643 （如何编写一个函数判断两个函数是否相等？） |
 |
2
crayygy 2020-09-12 12:19:32 +08:00 via Android
如果是指工程上的等价的话，最简单 /有效 /可靠 的方式应该就是 UT 了吧，只要测试覆盖率足够，可以一定程度上保持行为一致性
|
 |
3
staticor 2020-09-12 12:20:44 +08:00
这个问题可以翻译翻译， 不同人可能会产生不同的理解。
如果就是只能看到 2 个黑箱子， 完全不能看到箱子内部构造细节，只能看到箱子输入和输出， 怎么判断箱子里的构造完成一样？ - 如果函数本身就是无输入的，怎么获取箱子的影响面呢？ - 如果没有输出， 怎么判断输入的影响呢？ - 如果有输出， 提供多少测试输入用例来覆盖输入空间呢？ |
 |
4
zsdroid 2020-09-12 12:33:55 +08:00
说简单也简单，只要判断方法的注释就好了
|
 |
5
GeruzoniAnsasu 2020-09-12 12:47:39 +08:00
关键词： 形式化验证
|
 |
6
hoyixi 2020-09-12 12:51:05 +08:00
那首先你得定义：什么叫你口中的等价
|
 |
7
yazinnnn OP 感谢楼上的老哥们，我的表述应该是图灵机的停机问题，先去学习一下了😊
|
 |
8
dongyx 2020-09-12 12:57:14 +08:00  1
如 @sillydaddy 所说，如果是任意函数，是不可能的。
但是，作为一个实用主义者，你可以给出更细范围的函数。虽然在图灵机范围内不可判定，但是如果限制到有限自动机，我看是可以的。把两个自动机都 minimize，然后判断是否同构。 幸运地是，现实中的很多函数用有限自动机就能表达。 |
|
9
yazinnnn OP @dongyx
请问如果两个函数的参数情况相同： 1. 无参数，或者说（ Unit/Void ） 2. 一个参数，有限个可枚举，比如所有的 32 位 int 类型 3. 有限个参数，比如两个参数都是 int 型 这种情况可以判断函数是否等价么？（感觉这有点像数学问题了。。 |
|
10
dongyx 2020-09-12 14:30:48 +08:00
@yazinnnn
假设你讨论的是实际机器上运行的纯函数，那肯定是可以判定的，大不了你枚举所有可能的参数。实际机器上的函数的参数总是可以被枚举完的，比如你说的两个 32 位 int 型参数，总共 2^64 种情况给你枚举。但是除非的你的问题涉及到的参数类型非常特殊，不然性能上肯定是不能接受的。 如果在你的问题中，函数的参数形式是比较一般的，你可以从函数体的实现限制去考虑。比如，在你的实际工程中，你要判定的函数是不是都是数学上简单的初等函数呢？加减乘除指数三角函数的有限组合与复合？是的话，你就可以用表达式树给你的函数建模。在一些语言中，你可以直接把这些基本运算覆盖了，让这些运算返回一颗表达式树，然后你的问题就变成一个更传统的算法问题：我怎么判定两棵树同构？这就好做多了。 如果不是简单的初等函数，比如可能有判断，循环。那就要再把模型的计算能力上升一下，比如你发现的这些函数虽然有循环和判断，但是他们所用的局部变量的个数不随输入而改变（不会根据传入的整数参数来决定要在函数里开多大的数组），那你就可以尝试用有限自动机去描述这些函数。每个自动机可以规约到一个最小自动机，然后你就又转化为一个传统算法问题，判断两个图是不是同构的，这个问题虽然没有高效算法，但是问题规模小，你的代码转换成自动机之后的节点数，比你的参数的可能情况要小太多，所以总体上还是可以解决的。不过在实现上，这个就比初等函数的情况要复杂了，你很难简单地把一个函数转化为自动机，要不然你写一个（或者找一个开源的）解释器，要不然你就必须提供一套基础函数 /类库，这套工具要替代语言里的基本运算和循环 /判断结构，让那些函数的作者用你这套工具重写他们的函数以便你获取函数的自动机语义。 如果自动机还是不能解决你的问题，那就需要更抽象的模型，比如下推自动机，我没有研究过，并不知道判断两个下推自动机同构的问题是否是可能的。 但是我的整个思路是这样的，因为从理论上说，判断任意函数等价不可能，工程上枚举所有输入又不现实。那就只能从需求出发，和合作者讨论清楚这个问题的边界，你要让我实现 [判断函数等价] 的功能，你必须给函数做限制，你说的函数是什么函数。然后做折衷，比如我们要不要只支持初等函数？这样成本最低，函数实现者什么额外工作都不用做。不行的话，你们的函数能不能都写成有限状态的？还是不能，那就讨论参数的形式能不能限定，限定到枚举量可以接受的程度。 非纯函数的问题本质上没有区别，让大家把外部环境改写为参数传进去。 |
Select Language