71

这些术语的定义似乎确实 不同,但我一直认为一个暗示另一个;我想不出任何情况下表达式是引用透明但不纯的,反之亦然。

维基百科为这些概念维护了单独的文章,并说:

参考透明度

如果表达式中涉及的所有函数都是纯函数,则表达式是引用透明的。此外,如果某些不纯函数的值被丢弃并且它们的副作用微不足道,则可以将它们包含在表达式中。

纯表达式

纯函数是构造纯表达式所必需的。[...] 纯表达式通常被称为引用透明的。

我发现这些陈述令人困惑。如果所谓的“不纯函数”的副作用微不足道,以至于不允许在不实质性更改程序的情况下不执行它们(即用它的替换对此类函数的调用),那么它就好像它是纯的一样第一,不是吗?

有没有一种更简单的方法来理解纯表达式和引用透明表达式之间的区别(如果有的话)?如果存在差异,将不胜感激提供一个清楚地证明它的示例表达式。

4

7 回答 7

52

如果我将我认识的任何三位理论家聚集在一个地方,他们中至少有两位对“参照透明”一词的含义持不同意见。当我还是个年轻学生的时候,我的一位导师给了我一篇论文,解释说即使你只考虑专业文献,“参照透明”这个短语也至少意味着三个不同的东西。(不幸的是,该论文位于一箱尚未扫描的重印本中。我在 Google Scholar 中搜索过,但没有成功。)

我不能通知你,但我可以建议你放弃:因为即使是尖头语言理论家的小干部也无法就其含义达成一致,“引用透明”一词没有用处。所以不要使用它。


PS 在任何与编程语言语义有关的话题上,维基百科都是不可靠的。我已经放弃尝试修复它;维基百科流程似乎将变化和大众投票视为稳定性和准确性。

于 2011-02-11T04:23:22.297 回答
10

所有纯函数都必须是引用透明的。因为,根据定义,除了传递的内容之外,它们不能访问任何东西,因此它们的结果必须完全由它们的参数决定。

但是,可能具有不纯的引用透明函数。我可以编写一个函数,给定一个 int i,然后生成一个随机数r,从自身减去r并将其放入s,然后返回i - s。显然这个函数是不纯的,因为它生成的是随机数。但是,它是引用透明的。在这种情况下,这个例子是愚蠢和做作的。然而,例如在 Haskell 中,id函数是类型的a - > a,而我的stupidId函数是类型a -> IO a,表明它利用了副作用。当程序员可以通过外部证明来保证他们的函数实际上是引用透明的,那么他们可以使用unsafePerformIO剥离IO远离类型。

于 2011-02-02T15:03:56.337 回答
4

我有点不确定我在这里给出的答案,但肯定有人会为我们指明某个方向。:-)

“纯度”通常被认为意味着“没有副作用”。如果表达式的求值没有副作用,则称其为纯表达式。那有什么副作用呢?在纯函数式语言中,副作用是任何不符合简单 beta 规则的东西(评估函数应用的规则与用实际参数替换所有自由出现的形式参数相同)。

例如,在具有线性(或唯一性,此时此区别不应打扰)类型的函数式语言中,允许某些(受控)突变。

所以我想我们已经理清了“纯度”和“副作用”可能是什么。

引用透明度(根据您引用的维基百科文章)意味着变量可以被它表示的表达式(缩写,代表)替换,而不会改变手头程序的含义(顺便说一句,这也是一个难以解决的问题,并且我不会在这里尝试这样做)。因此,“纯度”和“参考透明度”确实是不同的东西:“纯度”是某些表达式的属性,大致意思是“执行时不会产生副作用”,而“参考透明度”是与变量和表达式相关的属性它代表并意味着“变量可以替换为它所表示的内容”。

希望这会有所帮助。

于 2011-02-02T03:51:52.837 回答
1

这些来自 ACCU2015 演讲的幻灯片对引用透明度的主题进行了很好的总结。

从其中一张幻灯片:

如果(a)每个子表达式都可以被任何其他与其相等的值替换,并且(b)在给定上下文中所有出现的表达式产生相同的值,则该语言是引用透明的。

例如,您可以拥有一个将其计算记录到程序标准输出的函数(因此,它不是纯函数),但您可以用不记录其计算的类似函数替换对该函数的调用. 因此,该函数具有引用透明性。但是......正如幻灯片强调的那样,上述定义是关于语言的,而不是表达方式。

[...] 就好像它最初是纯的一样,不是吗?

从我们的定义来看,不,不是。

有没有一种更简单的方法来理解纯表达式和引用透明表达式之间的区别(如果有的话)?

试试我上面提到的幻灯片

于 2015-04-24T13:59:10.300 回答
0

我将引用编程语言中的 John Mitchell 概念。他定义纯函数式语言必须通过没有副作用没有副作用的声明性语言测试。

“在 x1,...,xn 的特定减速范围内,仅包含变量 x1,...,xn 的表达式 e 的所有出现都具有相同的值。”

在语言学中,如果可以将名称或名词短语替换为具有相同所指对象的另一个名词短语而不改变其包含的句子的含义,则该名称或名词短语被认为是指称透明的。

在第一种情况下成立,但在第二种情况下它变得太奇怪了。

案例 1:“我看到沃尔特上了他的新车。”

如果 Walter 拥有 Centro,那么我们可以将给定句子中的 Centro 替换为:

“我看到沃尔特进入他的中心

与第一相反:

案例#2:因为留着胡子,他被称为威廉·鲁弗斯。

Rufus 的意思是有点红色,指的是英格兰的威廉四世。

“因为留着胡子,他被称为威廉四世。” 看起来太尴尬了。

传统的说法是,如果我们可以在程序中的任何地方将一个表达式替换为另一个具有相同值的表达式,而不改变程序的含义,那么这种语言就是引用透明的。

因此,引用透明性是纯函数式语言的一个属性。如果你的程序没有副作用,那么这个属性将成立。

因此,放弃它是很棒的建议,但在这种情况下,坚持下去也可能看起来不错。

于 2014-12-05T17:39:54.520 回答
0

纯函数是那些在每次调用时返回相同值并且没有副作用的函数。

引用透明性意味着您可以将绑定变量替换为其值,并且仍会收到相同的输出。

纯粹的和引用透明的:

def f1(x):
    t1 = 3 * x
    t2 = 6
    return t1 + t2

为什么这是纯净的?

因为它只是输入的函数,x没有副作用。

为什么这是引用透明的?

您可以在语句中用它们各自的右侧替换t1and t2in ,如下所示f1return

def f2(x):
    return 3 * x + 6

并且f2仍将始终返回与f1每种情况相同的结果。

纯粹的,但不是引用透明的:

我们修改f1如下:

def f3(x):
    t1 = 3 * x
    t2 = 6
    x = 10
    return t1 + t2

让我们再次尝试同样的技巧,将t1和替换t2为它们的右手边,看看它是否是 的等价定义f3

def f4(x):
    x = 10
    return 3 * x + 6

我们可以很容易地观察到这一点,f3并且f4在用右手边/值替换变量时并不等同。f3(1)将返回9并将f4(1)返回36

引用透明,但不纯

只需修改f1以接收 的非本地值x,如下所示:

def f5:
    global x
    t1 = 3 * x
    t2 = 6
    return t1 + t2

执行与之前相同的替换练习表明f5仍然具有引用透明性。但是,它不是纯粹的,因为它不仅仅是传递给它的参数的函数。

仔细观察,我们失去从f3到的引用透明度的原因f4是它x被修改了。在一般情况下,创建一个变量final(或者那些熟悉 Scala 的人,使用vals 而不是vars)并使用不可变对象可以帮助保持函数的引用透明。这使它们更像是代数数学意义上的变量,从而更好地进行形式验证。

于 2022-02-06T21:11:04.737 回答
0

标准的好处是有很多可供选择的。

安德鲁·S·塔南鲍姆。

...连同引用透明度的定义:

  • 来自Ian Holyer的 Miranda 函数式编程第 176 页:

    8.1 价值观和行为

    纯函数式语言的语义最重要的特性是该语言的声明性和操作性视图完全一致,如下所示:

    每个表达式都表示一个值,并且存在
    对应于所有可能的程序行为的值。
    表达式在任何上下文中产生的行为
    完全由它的值决定,反之亦然。

    这个原则,通常相当不透明地称为参照透明性,也可以用以下方式描绘:

    参考透明度图片

  • 以及来自F. Warren Burton 的具有引用透明度的函数式编程语言中的非确定性:

    [...] 表达式在相同环境中始终具有相同值的属性 [...]

...对于各种其他定义,请参阅Harald Søndergaard 和 Peter Sestoft 的参照透明度、确定性和可折叠性。

相反,我们将从“纯度”的概念开始。对于你们三个还不知道的人来说,你们正在阅读这篇文章的计算机或设备是一台固态图灵机,一种与效果有内在联系的计算模型。因此,每个程序,无论是功能性的还是其他的,都需要使用这些效果来完成任务TM

这对纯洁意味着什么?在汇编语言级别,即 CPU 的领域,所有程序都是不纯的。如果您正在用汇编语言编写程序,那么您就是对所有这些效果之间的相互作用进行微观管理的人——这真的很乏味!

大多数时候,您只是在指示 CPU 在计算机内存中移动数据,这只会更改各个内存位置的内容——那里什么也看不到!只有当您的指令指示 CPU 写入视频内存时,您才会观察到可见的变化(文本出现在屏幕上)。

出于我们的目的,我们将效果分为两个粗略的类别:

  • 那些涉及 I/O 设备的设备,如屏幕、扬声器、打印机、VR 耳机、键盘、鼠标等;通常称为可观察到的效果。
  • 其余的,只会改变内存的内容。

在这种情况下,纯度只是意味着没有那些可观察到的影响,这些影响会导致正在运行的程序的环境发生明显的变化,甚至可能是它的主机。这绝对不是没有所有效果,否则我们将不得不更换我们的固态图灵机!


现在对于42 生命、宇宙和所有事物的问题,“参照透明”一词究竟是什么意思——与其让理论家们达成共识,不如让我们试着找出这个词的原始含义。对我们来说幸运的是,这个术语经常出现在 Haskell 中的 I/O 上下文中——我们只需要一篇相关的文章……这里有一篇:来自 Owen Stephen 的函数式 I/O 方法的第一页:

引用透明性是指在不改变外部表达式的值的情况下,用一个相等的值替换一个子表达式的能力。该术语起源于 Quine,由 Strachey 引入计算机科学。

在参考文献之后:

  • 来自 Christopher Strachey 的编程语言基本概念的第 9 页,共 39 页:

    表达式最有用的属性之一是 Quine 引用透明性所调用的属性。从本质上讲,这意味着如果我们希望找到包含子表达式的表达式的值,我们唯一需要知道的关于子表达式的就是它的值。子表达式的任何其他特征,例如其内部结构、其组成部分的数量和性质、它们的评估顺序或书写它们的墨水颜色,都与主表达式的值无关表达。

  • 从 Willard Van Ormond Quine 的Word and Object的 314 页第 163 页:

    [...] 引用因此中断了一个术语的指称力,可以说是没有指称透明度2。[...] 如果单数项t的出现在项或句子ψ ( t ) 中纯粹指称,那么它在包含项或句子 Φ( ψ ( t ))。

    脚注:

    2该术语来自 Whitehead 和 Russell,第二版,第一卷。1,第 665。

在该参考之后:

  • 从Alfred North Whitehead 和 Bertrand Russell在《数学原理》中的 719 页中的第 709 页:

    当一个断言发生时,它是通过一个特定的事实做出的,它是所断言的命题的一个实例。但是这个特殊的事实,可以说是“透明的”;关于它什么都没有说,只是通过它来谈论别的东西。当命题出现在真值函数中时,它是属于命题的“透明”性质。

让我们尝试将所有这些放在一起:

  1. Whitehead 和 Russell 引入了“透明”一词
  2. Quine 然后定义了限定术语“引用透明度”
  3. Strachey 然后在定义编程语言的基础时采用了 Quine 的定义。

因此,这是在 Quine 的原始定义或 Strachey 的改编定义之间进行选择。如果你愿意的话,你可以试着自己翻译奎因的定义——每个曾经对“纯粹功能”的定义提出质疑的人甚至可能会喜欢有机会辩论一些不同的东西,比如“遏制模式”和“纯粹参考”的真正含义……乐趣!我们其他人只会接受 Strachey 的定义有点模糊(“本质上[...]”)并继续:

表达式的一个有用属性是引用透明性。从本质上讲,这意味着如果我们希望找到包含子表达式的表达式的值,我们唯一需要知道的关于子表达式的就是它的值。子表达式的任何其他特征,例如其内部结构、其组成部分的数量和性质、它们的评估顺序或书写它们的墨水颜色,都与主表达式的值无关表达。

(我强调。)

关于该描述(“如果我们希望找到 [...] 的值”),Peter Landin 在The Next 700 Programming Languages中给出了类似但更简洁的陈述:

表达式所表示的事物,即它的“值”,仅取决于其子表达式的值,而不取决于它们的其他属性。

因此:

表达式的一个有用属性是引用透明性。本质上,这意味着表达式所表示的事物,即它的“值”,仅取决于其子表达式的值,而不取决于它们的其他属性。

Strachey 提供了一些示例:

  • (第 12 页,共 39 页)

    我们倾向于自动假设,在3_x_ 2 + 2_x_ + 17这样的表达式中,符号x在每次出现时都代表相同的事物(或具有相同的值)。这是引用透明性最重要的结果,只有凭借这个属性,我们才能使用上一节中描述的 where 子句或λ表达式。

  • (第 16 页)

    当函数被使用(或调用或应用)时,我们写f [ ε ] 其中ε可以是一个表达式。如果我们使用一种引用透明的语言,我们只需要知道表达式ε以评估f [ ε ] 就是它的值。

因此,根据 Strachey 的原始定义,参照透明度意味着纯度——在没有评估顺序的情况下,可观察的和其他效果实际上是无用的......

于 2021-09-30T00:20:48.490 回答