无状态意味着引用透明？

Question

我有这个代码

data Slist a = Empty | Scons (Sexp a) (Slist a) 
data Sexp a = AnAtom a | AnSlist (Slist a)
data Fruit = Peach | Apple | Pear | Lemon | Fig deriving (Show,Eq)

sxOccurs oatm sxp =
  let slOC Empty = 0
      slOC (Scons se sls) = (seOC se) + (slOC sls)
      seOC (AnAtom atm) = if (atm == oatm) then 1 else 0
      seOC (AnSlist sla) = slOC sla
  in seOC sxp

正如您在 sxOccurs 中所看到的，我在 let 中有两个辅助函数，它们是“相互自指”的，就像我的 The Little MLer 调用它们：slOC 和 seOC。所以在SML中你必须使用关键字and来让它们相互了解并相互“交叉引用”。顺便说一句，sxOccurs 计算 s-list 中特定 AnAtom 对象的数量，在我的示例中原子是 Fruit 变量。

我的问题是，这是引用透明的例子吗？同样，在 Davie 中，他给出了这个例子

let s0 = emptyStack
    s1 = push 12.2 s0
    s2 = push 7.1 s1
    s3 = push 6.7 s2
    s4 = divStack s3
    s5 = push 4.3 s4
    s6 = subtStack s5
    s7 = multStack s6
    s8 = push 2.2 s7
    s9 = addStack s8
in popStack s9

注意到 Imperative-land 中的堆栈不断地改变堆栈，而 Haskell 正在为每个堆栈操作创建一个新的 si 变量。然后他说，这些行中的每一行都可以改组为不同的顺序，结果将保持不变。 AFAICT 这与我的 sxOccurs 的基本思想相同，当它不关心我呈现子功能的顺序时。那么，这又是引用透明性的更深层含义吗？如果不是，我在这里展示的是什么？

Answer 1

引用透明意味着这一点，而且仅意味着这一点：您可以根据变量的定义替换变量，而不会改变程序的含义。这称为“引用透明性”，因为您可以“查看”对其定义的引用。

比如你写：

slOC Empty = 0
slOC (Scons se sls) = (seOC se) + (slOC sls)
seOC (AnAtom atm) = if (atm == oatm) then 1 else 0
seOC (AnSlist sla) = slOC sla

由于引用透明，您可以进行以下几个转换：

-- replace slOC by its definition
seOC (AnSlist sla) = (\v -> case v of Empty -> 0; SCons se sls -> seOC se + slOC sls) sla
-- replace slOC by its definition *again*, starting from the previous line
seOC (AnSlist sla) = (\v -> case v of
    Empty -> 0
    SCons se sls -> seOC se + (\v -> case v of
        Empty -> 0
        SCons se sls -> seOC se + slOC sls
        ) sls
    ) sla
-- replace slOC by its definition in another equation
slOC (Scons se sls) = seOC se + (\v -> case v of Empty -> 0; SCons se sls -> seOC se + slOC sls) sls
-- or, you could replace seOC by its definition instead
slOC (SCons se sls) = (\v -> case v of
    AnAtom atm -> if atm == oatm then 1 else 0
    AnSlist sla -> sLOC sla
    ) se + slOC sls
-- or you could do both, of course

当然可以，对吧？现在你可能在想，“但是丹尼尔，这个属性怎么会失败呢？”。我将简单地转向另一种语言来说明：C.

int *x = malloc(sizeof(*x));
x[0] = 42;
printf("%d\n", x[0]);

以防你没读好 C，这会创建一个名为 x 的新变量，为其分配一些 space，将 42 写入 space，然后打印出来存储在 space 中的值。（我们应该期望它打印 42！）但是我在第一行定义了 x = malloc(sizeof(*x))；我可以用这个定义在别处替换 x 吗？

没有！这是一个非常不同的程序：

int *x = malloc(sizeof(*x));
malloc(sizeof(*x))[0] = 42;
printf("%d\n", x[0]);

它仍然是一个语法上有效的程序，但是现在 x[0] 在我们到达打印它的那一行时还没有被初始化——因为我们分配了第二个独立的 space 块，并初始化了另一个space。

事实证明这是其他语言违反引用透明性的主要方式：当你有值可以改变的变量时，用定义的值替换对它们的引用是不安全的，因为它可能已经改变了然后或者因为这将导致它不会按照程序其余部分预期的方式进行更改。 Haskell 避开这个能力；变量一旦赋值，就永远不会被修改。

Answer 2

如评论中所述，当两个函数在求值过程中相互调用时，更准确地称为“相互递归”。参照透明性实际上是说，给定完全相同的输入，一个函数将产生相同的输出。这在 Python 中是不正确的，我们可以在其中编写此函数

global_var = 0

def my_function():
    return global_var

my_function() # 0
global_var = 100
my_function() # 100

我们用相同的输入调用 my_function，但它神秘地产生了不同的输出。现在，当然，在这个例子中，为什么会这样很明显，但是引用透明性背后的想法是，在现实世界的代码中，它不会那么明显。如果您使用的语言不具有引用透明性，并且确实如果该语言鼓励远距离操作样式突变，那么您将不可避免地得到这样的函数访问您不知道的可变状态。一个编写良好的函数将包含有关这些极端情况的大量文档，但如果您曾经处理过任何中型或大型代码库，您就会知道“记录良好的函数”是一种罕见的景象。

在Haskell中，没有办法*像上面的Python函数那样写一个函数。在最坏的情况下，我们可以将其包装在 IO

中

myFunction :: IORef Int -> IO Int
myFunction = readIORef

但是现在类型签名一目了然地告诉我们，“这里发生了一些可疑的事情；买家当心”，即使这样我们也只能访问 IORef 允许我们访问的一个全局变量到.

*没法写Haskell的函数，只能利用unsafePerformIO，后面有很多龙。使用 unsafePerformIO，我们可以很明显地打破引用透明性，这就是为什么每个 Haskell 教程都告诉你忘记并且永远不要使用它是一个名为“不安全”的模块中的一个名为“不安全”的函数。

无状态意味着引用透明？

Statelessness implies referential transparency?

haskell

stateless

referential-transparency