理解引用透明度

你的推理错误如下:
“这意味着这种函数可以表示为真值表”。

你可以从函数式语言的指称透明性得出结论。到目前为止,这个结论听起来似乎是有道理的,但是您可以监督函数是否能够接受集合作为输入并处理它们,这与逻辑门的固定输入不同。

对您的注释进行注释:函数式语言可以——尽管是无状态的——通过在每次被访问时从头构造状态来实现状态机。

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

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

虽然我显然没有回答实际问题,但我认为我的答案很好,所以我保留它:-)(见下文)。

首先,假设您采用了命令式语言(如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

我们还能做任何我们想做的事吗?我不是百分之百肯定,但我想答案是“是的”。如果你有闭包,当然可以。

我建议研究Haskell,一种纯函数式语言。严格来说,Haskell没有“赋值”操作符。例如:

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

我 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不是一个由语句列表组成的函数,而是Haskell执行的IO动作,动作通过bind操作定义并链接在一起。此外,可以使用 return 功能。

要澄清,请考虑 readLn . 阅读 如果执行该操作,将从标准输入中读取一行并产生其解析值。要使用该值执行某些操作,我们不能将其存储在变量中,因为这样会违反 参照透明度 :

a = readLn

,含义 阅读 不会是透明的。

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

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

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

据我所知,引用透明只是意味着:给定的函数在使用相同的参数调用时总是会产生相同的结果。所以,你在学校学到的数学函数是透明的。

为了学习如何使用纯函数式语言进行操作,您可以检查一种语言 Haskell . 有一些方法可以使用“可更新的存储可能性”,比如读卡器Monad和 State Monad 例如。如果你对纯函数数据结构感兴趣, Okasaki 可能是一本好书。

是的,你说得对:像haskell这样的纯函数式语言的求值顺序与非函数式语言的求值顺序并不重要,因为如果没有副作用,就没有理由在其他语言之前/之后做一些事情——除非一个语言的输入取决于另一个语言的输出,或者像单子这样的方法起作用。

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

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

纯函数只能处理组合逻辑的推理是正确的,只是函数语言在某种程度上隐藏了这一点。

还要记住,基本的数字逻辑可以用真值表来描述。唯一的原因是,除了对4位整数进行算术运算之外,没有其他方法可以做到这一点,因为真值表的大小是指数增长的。