理解引用透明度

Question

一般来说，我很头痛，因为我的推理有问题：

1. 对于 1 组参数，引用透明函数将始终返回 1 组输出值。

2. 这意味着这样的函数可以表示为真值表（为 1 组参数指定 1 组输出参数的表）。

3. 这使得这些函数背后的逻辑是组合（而不是顺序）

4. 这意味着使用纯函数语言（仅具有 rt 函数）可以仅描述组合逻辑。

最后一个陈述是从这个推理得出的，但是它显然是错误的；这意味着推理存在错误。 [问题：这个推理错误在哪里？]

UPD2。你们，伙计们，说了很多有趣的话，但没有回答我的问题。我现在更明确地定义了它。抱歉搞乱了问题定义！

Answer 1

问题：这个推理错误在哪里？

引用透明函数可能需要无限真值表来表示其行为。您将很难用组合逻辑设计无限电路。

另一个错误：时序逻辑的行为可以纯粹从功能上表示为从状态到状态的函数。在实现中，这些状态按时间顺序发生的事实并不妨碍定义一个纯粹的引用透明函数，该函数描述状态如何随时间演变。

Answer 2

编辑：虽然我显然错过了实际问题的中心，但我认为我的答案非常好，所以我保留它:-)（见下文）。

我想用一种更简洁的方式来表达这个问题可能是：纯函数式语言可以计算命令式语言可以计算的任何东西吗？

首先，假设您采用了像 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 和总计。不过，一切并没有失去。只需使用递归来不断获取新的 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)

（请注意，这是在 Haskell 中对列表求和的愚蠢方法，但它演示了一种方法处理单个赋值的问题。）

现在，考虑一下这段看起来高度命令式的代码：

main = do
    a <- readLn
    b <- readLn
    print (a + b)

它实际上是语法糖：

main =
    readLn >>= (\a ->
    readLn >>= (\b ->
    print (a + b)))

其想法是，main 不是一个由语句列表组成的函数，而是一个 IO 操作， Haskell 执行，操作被定义并与绑定操作链接在一起。此外，可以使用 return 函数定义不执行任何操作但产生任意值的操作。

请注意，绑定和返回并不特定于操作。它们可以与任何自称为 Monad 的类型一起使用来完成各种时髦的事情。

为了澄清这一点，请考虑 readLn。 readLn 是一个操作，如果执行该操作，将从标准输入读取一行并生成其解析值。要使用该值执行某些操作，我们不能将其存储在变量中，因为这会违反引用透明度：

a = readLn

如果允许这样做，a 的值将取决于世界，并且每次调用时都会不同readLn，这意味着 readLn 不会是引用透明的。

相反，我们将 readLn 操作绑定到处理该操作的函数，从而生成一个新操作，如下所示：

readLn >>= (\x -> print (x + 1))

该表达式的结果是一个操作值。如果 Haskell 从沙发上起来并执行此操作，它将读取一个整数，递增它，然后打印它。通过将动作的结果绑定到对结果执行某些操作的函数，我们可以在状态世界中玩耍时保持引用透明度。

Answer 3

据我了解，引用透明度只是意味着：当使用相同的参数调用时，给定的函数将始终产生相同的结果。因此，您在学校学到的数学函数是引用透明的。

为了了解纯函数式语言是如何完成工作的，您可以查看 Haskell 语言。有多种方法可以使用“可更新存储的可能性”，例如 Reader Monad 和 State Monad例子。如果您对纯函数式数据结构感兴趣，Okasaki 可能是一个不错的选择读。

是的，你是对的：在像 Haskell 这样的纯函数式语言中，求值顺序并不像在非函数式语言中那样重要，因为如果没有副作用，就没有理由在其他事情之前/之后做一些事情——除非一个的输入依赖于另一个的输出，或者像单子这样的手段发挥作用。

我真的不知道真值表问题。

Answer 4

这是我回答这个问题的尝试：

任何系统都可以被描述为一个组合函数，无论大小。

纯函数只能处理组合逻辑的推理没有任何问题——这是真的，只是函数式语言在某种程度上向你隐藏了这一点。

例如，您甚至可以将游戏引擎的工作原理描述为真值表或组合函数。

您可能有一个确定性函数，它将“整个游戏的当前状态”作为游戏引擎和键盘输入占用的 RAM，并返回“一帧后的游戏状态”。返回值将由输入中的位组合确定。

当然，在任何有意义且健全的函数中，输入都会被解析为整数、小数和布尔值块，但这些值中的位组合仍然决定函数的输出。

还要记住，基本的数字逻辑可以用真值表来描述。除了 4 位整数算术之外，不这样做的唯一原因是真值表的大小呈指数增长。

Answer 5

您的推理错误如下：
“这意味着这样的函数可以表示为真值表”。

您可以根据函数式语言的引用透明度属性得出这一结论。到目前为止，结论听起来似乎合理，但您发现函数能够接受集合作为输入并处理它们，这与逻辑门的固定输入形成鲜明对比。

因此，函数并不等于逻辑门，而是取决于实际（在运行时确定）输入的逻辑门的构造计划！

评论您的评论：函数式语言尽管无状态，但可以通过每次访问时从头开始构造状态来实现状态机。