7

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

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

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

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

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

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

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

4

5 回答 5

6

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

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

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

于 2010-07-17T00:25:41.527 回答
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尽管and有多个实例，但count总是sum((int[]){1,2,3}, 3)会计算为6，因此您可以根据需要将该表达式替换为6。

我们还能做任何我们想做的事吗？我不是 100% 确定，但我认为答案是“是”。不过，如果你有闭包，你当然可以。

你说得对。这个想法是，一旦定义了变量，就不能重新定义它。给定相同变量的引用透明表达式总是产生相同的结果值。

我建议研究 Haskell，一种纯粹的函数式语言。严格来说，Haskell 没有“赋值”运算符。例如：

my_sum numbers = ??? where
    i     = 0
    total = 0

在这里，您不能编写一个“for 循环”来递增 i 和 total 。不过，一切都没有丢失。只需使用递归来不断获取新i的 s 和totals：

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 不是由语句列表组成的函数，main 是 Haskell 执行的 IO 操作，并且操作被定义并与绑定操作链接在一起。此外，可以使用该return函数定义不执行任何操作、产生任意值的操作。

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

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

a = readLn

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

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

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

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

于 2010-07-16T21:28:13.330 回答
2

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

您可以查看以了解如何用纯函数式语言完成事情的语言是Haskell。有一些方法可以使用“可更新的存储可能性”，例如 Reader Monad 和State Monad。如果您对纯函数式数据结构感兴趣，Okasaki可能是一本不错的读物。

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

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

于 2010-07-16T20:40:16.000 回答
1

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

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

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

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

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

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

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

于 2010-07-16T23:24:25.690 回答
0

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

您从函数式语言的引用透明度属性得出结论。到目前为止，这个结论听起来似乎是合理的，但是你注意到一个函数能够接受集合作为输入并处理它们，这与逻辑门的固定输入不同。

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

评论您的评论：函数式语言可以——尽管是无状态的——通过在每次访问它们时从头开始构建状态来实现状态机。

于 2010-07-16T23:09:59.617 回答