通常，我头疼是因为我的推理有问题：
对于一组参数，引用透明函数将始终返回1组输出值。
这意味着这样的函数可以表示为真值表（一个表格，其中为一组参数指定了1组输出参数）。
这使得这些函数背后的逻辑是组合的（而不是时序的）。
这意味着使用纯函数式语言（只有rt函数的语言）只能描述组合逻辑。
最后一个陈述是从这个推理中推导出来的，但显然是错误的；这意味着推理有误。[问题：这个推理哪里错了？]
UPD2. 你们说了很多有趣的事情，但没有回答我的问题。我现在更明确地定义了它。抱歉搞乱了问题定义！
理解引用透明性。
7
- Vladimir Keleshev
5
1这意味着使用纯函数式语言...只能描述顺序逻辑，您是不是更想说“组合逻辑”？ - Dave O.
非常感谢！那非常重要！ - Vladimir Keleshev
你能解释一下为什么说“一个纯函数式语言只能描述组合逻辑”这个陈述是错误的吗？谢谢。 - Dave O.
@Dave：因为你可以使用纯函数式语言实现状态机。（我其实就是这么假设的 - 但除此之外，函数式语言对于任何目的都没有用处） - Vladimir Keleshev
同样，图灵完备的机器具有无限递归能力，因此函数可以调用自身。 - Shelby Moore III
5个回答
6
问题：这个推理的错误在哪里？
一个引用透明的函数可能需要一个无限真值表来表示其行为。你很难设计一个组合逻辑中的无限电路。
另一个错误是：顺序逻辑的行为可以被纯函数地表示为从状态到状态的函数。实现中这些状态按时间顺序发生的事实并不妨碍定义一个纯粹的引用透明函数，描述状态如何随时间演变。
一个引用透明的函数可能需要一个无限真值表来表示其行为。你很难设计一个组合逻辑中的无限电路。
另一个错误是：顺序逻辑的行为可以被纯函数地表示为从状态到状态的函数。实现中这些状态按时间顺序发生的事实并不妨碍定义一个纯粹的引用透明函数，描述状态如何随时间演变。
- Norman Ramsey
3
编辑：虽然我显然错过了实际问题的核心，但我认为我的答案非常好，所以我会保留它 :-)（见下文）。
我想更简洁地表达这个问题：一个纯函数式语言能否计算出任何命令式语言可以计算出的东西？
首先，假设你拿一种命令式语言比如C语言，并使它不能在定义后更改变量。例如：
int i;
for (i = 0; // okay, that's one assignment
i < 10; // just looking, that's all
i++) // BUZZZ! Sorry, can't do that!
好的，你的for循环就这样结束了。我们还能保留while循环吗？
while (i < 10)
当然，但这并不是非常有用。因为i无法更改，所以它要么会一直运行，要么根本不会运行。
那么递归呢？是的，你可以继续使用递归，而且它仍然非常有用：
int sum(int *items, unsigned int count)
{
if (count) {
// count the first item and sum the rest
return *items + sum(items + 1, count - 1);
} else {
// no items
return 0;
}
}
现在，有了函数，我们不再改变状态，但是变量可以变化。一旦一个变量传递到我们的函数中，它就被锁定了。然而，我们可以调用函数（递归），这就像获得了一组全新的变量（旧的变量保持不变）。虽然有多个
items和count实例，但sum((int[]){1,2,3}, 3)总是评估为6，所以如果你愿意，你可以将该表达式替换为6。我们还能做任何我们想做的事情吗？我不是100%确定，但我认为答案是“是”。当然，如果你有闭包，那么你肯定可以。
你说得对。这个想法是，一旦定义了一个变量，它就不能被重新定义。给定相同的变量，具有引用透明性的表达式总是产生相同的结果值。
我建议研究一下Haskell，这是一种纯函数语言。 Haskell严格来说没有“赋值”运算符。例如：
my_sum numbers = ??? where
i = 0
total = 0
在这里，你不能编写一个“for循环”来逐步增加i和total的值。但是并不是一无所有，只需使用递归来不断获取新的i和total：
my_sum numbers = f 0 0 where
f i total =
if i < length numbers
then f i' total'
else total
where
i' = i+1
total' = total + (numbers !! i)
main = do
a <- readLn
b <- readLn
print (a + b)
实际上这只是语法糖，其实际含义为：
main =
readLn >>= (\a ->
readLn >>= (\b ->
print (a + b)))
这个想法是，main不再是一个由语句列表组成的函数，而是一个Haskell执行的IO操作，操作由bind操作定义并链接在一起。同时，可以使用return函数定义一个什么也不做但返回任意值的操作。
需要注意的是，bind和return不只适用于操作。它们可以与任何自称为Monad类型的类型一起使用，做出各种奇妙的事情。
为了澄清这一点，我们来看看readLn。readLn是一个操作，如果被执行，将从标准输入中读取一行并返回它的解析值。为了对该值进行操作，我们不能将其存储在变量中，因为这会违反引用透明性：
a = readLn
如果允许这样做，a的值将取决于外部环境，并且每次调用readLn时都会有所不同，这意味着readLn不是引用透明的。
相反，我们将readLn操作绑定到处理该操作的函数上，产生一个新的操作，像这样：
readLn >>= (\x -> print (x + 1))
这个表达式的结果是一个操作值。如果Haskell起身执行这个操作，它会读取一个整数，将其加1并打印出来。通过将行动的结果绑定到执行某些操作的函数，我们可以在状态世界中玩耍，同时保持参照透明度。
- Joey Adams
4
2我真的在“如果 Haskell 起身了…”这句话上大笑了。现在的编程语言都太懒了。 - Chuck
我已经读了你的答案10遍，但仍然不明白-状态的改变在哪里？哪个函数应该有状态？我仍然只看到组合逻辑。 - Vladimir Keleshev
也许你可以给一个命令式语法的例子吗？如果避免变量赋值（除了函数返回值）并保持函数引用透明 - 它不应该做同样的事情吗？ - Vladimir Keleshev
我是否理解正确 - 没有递归，纯函数式程序中就无法存在状态？ - Vladimir Keleshev
2
据我所了解，引用透明度只意味着：给定函数在使用相同参数调用时总是产生相同的结果。因此，你在学校学习的数学函数是具有引用透明性的。
如果你想了解纯函数语言中如何处理事物，可以尝试学习Haskell这种语言。例如，可以使用“可更新存储机制”（如Reader Monad和State Monad）等方式。如果你对纯函数数据结构感兴趣，可以阅读Okasaki。
是的，你是正确的：在像Haskell这样的纯函数语言中，求值顺序并不像非函数语言那样重要，因为如果没有副作用，就没有理由在某些操作之前/之后执行其他操作--除非一个操作的输入取决于另一个操作的输出，或者涉及到类似单子的概念。
我不太清楚真值表问题。
如果你想了解纯函数语言中如何处理事物，可以尝试学习Haskell这种语言。例如，可以使用“可更新存储机制”（如Reader Monad和State Monad）等方式。如果你对纯函数数据结构感兴趣，可以阅读Okasaki。
是的，你是正确的：在像Haskell这样的纯函数语言中，求值顺序并不像非函数语言那样重要，因为如果没有副作用，就没有理由在某些操作之前/之后执行其他操作--除非一个操作的输入取决于另一个操作的输出，或者涉及到类似单子的概念。
我不太清楚真值表问题。
- danlei
5
3读者注意： "Monad" 并没有什么神秘的地方。Haskell 不允许像 C++ 那样重载，它使用类型类。 "Monad" 只是一个类型类，很多类型都订阅了它，所以它们可以使用漂亮的
>>= 和 return 函数。当你看到 IO Int 时，就想象一个动作，如果执行它，则会产生一个 Int。您可以使用 >>=（绑定）运算符构建复合动作，而不是编写逐步执行的指令。>>= 运算符以奇妙有趣的方式用于其他类型。别害怕 "M" 字。 - Joey Adams是的，基本上，您可以通过链接函数调用来强制评估顺序，甚至无需触及单子。 - danlei
@danlei：在惰性语言中，函数调用的链式调用本身不应该强制执行顺序，至少一般情况下不会。函数本身必须以这种方式编写。IO的绑定运算符就是这样一个函数，这就是为什么它可以用于顺序执行操作。 - Chuck
@Chuck：你说得对，感谢澄清。我想说的是，如果我们（或者顶层）评估某些东西，那么依赖它的一切都必须被评估。如果我们想象一个依赖链，在传递某种“世界状态”的同时，我们基本上拥有了类似于IO单子的东西（好吧，这个版本不太容易允许时间旅行），可以想象为隐式地传递世界。我的最后一条评论确实太笼统了，表达也不好。希望这次我说对了。 :) - danlei
s/depending on it/它取决于/ - danlei
1
以下是我对这个问题的看法：
任何系统都可以被描述为组合函数，无论大小。
纯函数只能处理组合逻辑并没有错，这种推理是正确的，只不过函数式语言在某种程度上隐藏了这一点。
你甚至可以将游戏引擎的工作描述为真值表或组合函数。
你可能有一个确定性函数，它以游戏引擎占用的 RAM 和键盘输入作为“整个游戏的当前状态”，并返回“游戏下一帧的状态”。返回值由输入中位的组合决定。
当然，在任何有意义和理智的函数中，输入都会被解析成整数、小数和布尔值的块，但这些值中位的组合仍然决定了函数的输出。
还要记住，基本的数字逻辑可以用真值表来描述。之所以不对超过4位整数的算术运算使用真值表，是因为真值表的大小呈指数级增长。
- Rei Miyasaka
1
在核心部分，你的回答说的和我试图解释的一样。 - Dave O.
0
你推理的错误在于以下内容：
“这意味着这样的函数可以表示为真值表”。你从引用透明的函数语言属性中得出了这个结论。到目前为止，这个结论听起来似乎是有道理的，但你忽略了一个函数能够接受集合作为输入并对它们进行处理，与逻辑门的固定输入形成对比。
因此，一个函数并不等同于逻辑门，而是一个依赖于实际（在运行时确定）输入的逻辑门的构造计划！
针对你的评论：虽然是无状态的，但函数式语言可以通过每次从头开始构建状态来实现状态机。
“这意味着这样的函数可以表示为真值表”。你从引用透明的函数语言属性中得出了这个结论。到目前为止，这个结论听起来似乎是有道理的，但你忽略了一个函数能够接受集合作为输入并对它们进行处理，与逻辑门的固定输入形成对比。
因此，一个函数并不等同于逻辑门，而是一个依赖于实际（在运行时确定）输入的逻辑门的构造计划！
针对你的评论：虽然是无状态的，但函数式语言可以通过每次从头开始构建状态来实现状态机。
- Dave O.
1
一台图灵完备的机器具有无限递归能力，因此函数可以调用自身。 - Shelby Moore III
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接