什么是参考透明度?

问题描述 投票:254回答:12

参考透明度这个术语是什么意思?我听说它被描述为“它意味着你可以用平等替换等于”,但这似乎是一个不充分的解释。

functional-programming computer-science theory referential-transparency
12个回答
327
投票

“参照透明度”一词来自analytical philosophy,它是分析自然语言结构,基于逻辑和数学方法的陈述和论证的哲学分支。换句话说,它是计算机科学以外最接近的主题,我们称之为programming language semantics。哲学家Willard Quine负责启动参照透明度的概念,但它也隐含在Bertrand Russell和Alfred Whitehead的方法中。

“参考透明度”的核心是一个非常简单明了的想法。术语“指示物”用于分析哲学中,用于谈论表达所指的事物。它与编程语言语义中的“含义”或“外延”大致相同。使用Andrew Birkett的例子(blog post),“苏格兰的首都”一词指的是爱丁堡市。这是一个直接的“指称对象”的例子。

如果在该上下文中用引用同一实体的另一个术语替换术语而不改变含义,则句子中的上下文是“引用透明的”。例如

苏格兰议会在苏格兰首都举行会议。

意思是一样的

苏格兰议会在爱丁堡举行会议。

因此,“苏格兰议会在...中会面”的背景是一种参考透明的背景。我们可以用“爱丁堡”取代“苏格兰的首都”而不改变其含义。换句话说,上下文只关心术语所指的内容,而不关心其他内容。这就是上下文“引用透明”的意义。

另一方面,在句子中,

自1999年以来,爱丁堡一直是苏格兰的首府。

我们不能做这样的替代。如果我们这样做,我们会得到“自1999年以来爱丁堡一直是爱丁堡”,这是一个可怕的说法,并没有表达与原句相同的含义。因此,似乎“爱丁堡自1999年以来一直”的背景是参考不透明的(与参考透明相反)。它显然关心的东西比术语所指的更多。它是什么?

像“苏格兰的首都”这样的东西被称为明确的术语,他们长期以来没有给逻辑学家和哲学家带来过少的头痛。 Russell和Quine将它们排除在外,说它们实际上并不是“参照”,即认为上述例子用于指代实体是错误的。正确的理解“爱丁堡自1999年以来一直是苏格兰的首都”的正确方法

苏格兰自1999年以来一直有资本,首都是爱丁堡。

这句话不能变成坚果。问题解决了!奎因的观点是说自然语言是混乱的,或者至少是复杂的,因为它被用来方便实际使用,但哲学家和逻辑学家应该以正确的方式理解它们。参考透明度是一种用于带来这种清晰含义的工具。

这与编程有什么关系?实际上并不是很多。正如我们所说,参考透明度是用于理解语言的工具,即用于分配意义。 Christopher Strachey创立了编程语言语义学领域,在他的意义研究中使用它。他的基础论文“Fundamental concepts in programming languages”可在网上找到。这是一篇精美的论文,每个人都可以阅读和理解它。所以,请这样做。你会得到很多启发。他在本段中引入了“参照透明度”一词:

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

使用“本质上”表明Strachey正在解释它,以便用简单的术语来解释它。功能程序员似乎以自己的方式理解这一段。本文还有其他9种“引用透明度”,但它们似乎并没有打扰其他任何一种。实际上,Strachey的全文都致力于解释命令式编程语言的含义。但是,今天,功能程序员声称命令式编程语言不是透明的。 Strachey会在他的坟墓中转身。

我们可以挽救局势。我们说自然语言是“杂乱的,或者至少是复杂的”,因为它是为了方便实际使用。编程语言是一样的。它们“杂乱,或至少复杂”,因为它们被制作成便于实际使用。这并不意味着他们需要混淆我们。他们只需要以正确的方式理解它们,使用一种引用透明的元语言,这样我们就可以清晰地理解它们。在我引用的论文中,Strachey正是如此。他通过将命令式编程语言分解为基本概念来解释命令式语言的含义,从不在任何地方失去清晰度。他的分析的一个重要部分是指出编程语言中的表达式有两种“值”,称为l值和r值。在Strachey的论文之前,这一点并未得到理解,并且混乱占据了至高无上的地位。今天,C的定义经常提及它,每个C程序员都理解这种区别。 (其他语言的程序员是否同样理解它很难说。)

Quine和Strachey都关注语言结构的含义,这些结构涉及某种形式的背景依赖。例如,我们的例子“爱丁堡自1999年以来一直是苏格兰的首都”,这标志着“苏格兰的首都”取决于它被考虑的时间。无论是在自然语言还是编程语言中,这种上下文依赖都是现实。即使在函数式编程中,自由和绑定变量也要根据它们出现的上下文进行解释。任何类型的上下文依赖性都会以某种方式阻止引用透明性。如果您试图理解术语的含义而不考虑它们所依赖的上下文,那么您最终会感到困惑。奎因关注模态逻辑的含义。他认为modal logic是参考不透明的,应该通过将其翻译成一个参考透明的框架(例如,将必要性视为可证明性)来清理它。他基本上失去了这场辩论。逻辑学家和哲学家都认为克里普克可能的世界语义是完全足够的。类似的情况也与命令式编程有关。由Strachey解释的状态依赖性和Reynolds解释的存储依赖性(以类似于Kripke可能的世界语义的方式)是完全足够的。功能程序员对这项研究知之甚少。他们关于参考透明度的想法应该用大量的盐。

[补充说明:上面的例子表明,诸如“苏格兰之都”这样的简单短语具有多层含义。在某种程度上,我们可能在谈论当前的资本。在另一个层面上,我们可能会讨论苏格兰可能在一段时间内可能拥有的所有资本。在正常练习中,我们可以“放大”特定的上下文并“缩小”以跨越所有上下文。自然语言的效率利用了我们这样做的能力。命令式编程语言以非常相同的方式有效。我们可以在赋值的右侧使用变量x(r值)来讨论它在特定状态下的值。或者,我们可以谈论它跨越所有州的l值。人们很少被这些事情搞糊涂。然而,它们可能或可能不能精确地解释语言结构中固有的所有意义层。所有这些意义层面都不一定是“显而易见的”,正确研究它们是一个科学问题。然而,普通人解释这种分层意义的意义并不意味着他们对它们感到困惑。

下面单独的“后记”将此讨论与功能和命令式编程的关注联系起来。


3
投票

我希望以下答案增加并限定有争议的第一和第三个答案。

让我们承认表达式表示或引用某些指示物。然而,一个问题是这些指示物是否可以作为表达式本身的一部分同构编码,称这些表达式为“值”。例如,文字数值是算术表达式集的子集,真值是布尔表达式集的子集,等等。想法是将表达式计算为其值(如果有的话)。因此,“值”一词可以指代表达式或表达式集合中的区分元素。但是如果指示物与价值之间存在同构(双射),我们可以说它们是同一个东西。 (这就是说,必须小心定义所指对象和同构,正如指称语义学领域所证明的那样。举一个回答第三个答案提到的例子,代数数据类型定义data Nat = Zero | Suc Nat不符合预期的一组自然数。)

让我们写一个带有洞的表达式的E[·],在某些方面也称为“上下文”。类似C的表达式的两个上下文示例是[·]+1[·]++

让我们为带有表达式(没有空洞)的函数编写[[·]],并在一些提供意义的宇宙中传递它的含义(指示,表示等)。 (我借用了指称语义学领域的符号。)

让我们在一定程度上正式地修改奎因的定义如下:如果给出任何两个表达式E[·]E1(没有那里的孔)使得E2(即表达式表示/引用相同的指示物),则上下文[[E1]] = [[E2]]是引用透明的话就是这种情况[[E[E1]]] = [[E[E2]]](即用E1E2填充洞,导致表达也表示相同的指示物)。

莱布尼茨用等于等于等于的平均值表示为“如果E1 = E2然后E[E1] = E[E2]”,它表示E[·]是一个函数。函数(或者就此而言,计算函数的程序)是从源到目标的映射,使得每个源元素最多有一个目标元素。非确定性函数是用词不当,它们是关系,函数传递集合等。如果在莱布尼茨的规则中,等式=是指示性的,那么双括号只是被认为是理所当然和被忽略的。因此,引用透明的上下文是一种功能。而莱布尼茨的规则是等式推理的主要成分,因此等式推理肯定与参照透明度有关。

虽然[[·]]是从表达到表示的函数,但它可以是从表达式到“值”的函数,被理解为表达式的有限子集,并且[[·]]可以被理解为评估。

现在,如果E1是一个表达式并且E2是一个值,我们认为大多数人在表达,值和评估方面定义参照透明度时的含义。但正如本页第1和第3个答案所示,这是一个简单的定义。

[·]++这样的上下文的问题不是副作用,而是它的值在C中没有与其含义同构。函数不是值(嗯,指向函数的指针),而在函数式编程语言中它们是。 Landin,Strachey和指称语义学的先驱们在使用功能世界提供意义方面非常聪明。

对于命令式C语言,我们可以(粗略地)使用函数[[·]] : Expression -> (State -> State x Value)为表达式提供语义。

ValueExpression的一个子集。 State包含对(标识符,值)。语义函数采用表达式并将当前状态下的函数作为其含义传递给具有更新状态和值的对。例如,[[x]]是从当前状态到对的函数,其第一个分量是当前状态,第二个分量是x的值。相反,[[x++]]是从当前状态到该对的函数,其第一个分量是x的值递增的状态,并且其第二个分量就是那个值。在这个意义上,如果上下文[·]++满足上面给出的定义,那么它就是引用透明的。

我认为函数式程序员有权使用引用透明性,因为它们自然地将[[·]]恢复为从表达式到值的函数。函数是一等值,状态也可以是值,而不是外延。州monad(部分)是一种传递(或穿越)国家的清洁机制。


2
投票

请注意,这种“意义”概念是在观察者心中发生的事情。因此,相同的“参考”可能对不同的人意味着不同的东西。因此,例如,我们在维基百科中有一个爱丁堡消歧页面。

可以在编程的上下文中出现的相关问题可能是多态性。

也许我们应该为多态(或者甚至是转换)的特殊情况命名,其中为了我们的目的,不同的多态情况在语义上是等价的(而不是仅仅是相似的。例如,数字1 - 可能表示使用整数类型,或复杂类型或任何其他各种类型 - 可以多态处理。


0
投票

我在“计算机程序的结构和实现”(向导书)一书中发现了引用透明度的定义很有用,因为它通过引入赋值操作来解释如何违反引用透明性。查看我对该主题制作的以下幻灯片:https://www.slideshare.net/pjschwarz/introducing-assignment-invalidates-the-substitution-model-of-evaluation-and-violates-referential-transparency-as-explained-in-sicp-the-wizard-book


125
投票

参考透明度是函数式编程中常用的术语,意味着给定函数和输入值,您将始终获得相同的输出。也就是说,函数中没有使用外部状态。

以下是参照透明函数的示例:

int plusOne(int x)
{
  return x+1;
}

使用参照透明函数,给定输入和函数,您可以用值替换它而不是调用函数。因此,我们不能用参数5调用plusOne,而只需用6替换它。

另一个很好的例子是数学。在给定函数和输入值的数学中,它将始终映射到相同的输出值。 f(x)= x + 1.因此,数学中的函数是参考透明的。

这个概念对于研究人员很重要,因为它意味着当你具有参考透明功能时,它有助于简化自动并行化和缓存。

参考透明度总是在像Haskell这样的函数式语言中使用。

--

相反,存在参考不透明的概念。这意味着相反的情况。调用该函数可能并不总是产生相同的输出。

//global G
int G = 10;

int plusG(int x)
{//G can be modified externally returning different values.
  return x + G;
}

另一个例子是面向对象编程语言中的成员函数。成员函数通常对其成员变量进行操作,因此是引用不透明的。成员函数当然可以是引用透明的。

另一个例子是从文本文件中读取并打印输出的函数。此外部文本文件可能随时更改,因此该函数将是引用不透明的。


84
投票

引用透明函数是仅依赖于其输入的函数。


70
投票

[这是我3月25日回答的一个附言,旨在使讨论更接近功能/命令式编程的关注。

功能程序员的引用透明度的想法似乎与标准概念有三种不同:

  • 虽然哲学家/逻辑学家使用诸如“参考”,“外延”,“designatum”和“bedeutung”(弗雷格的德语术语)之类的术语,但功能程序员使用术语“价值”。 (这不完全是他们的行为。我注意到Landin,Strachey和他们的后代也使用术语“价值”来谈论参考/外延。这可能只是Landin和Strachey介绍的术语简化,但似乎是以天真的方式使用时的巨大差异。)
  • 功能程序员似乎相信这些“价值”存在于编程语言中,而不是在外部。在这样做时,它们与哲学家和编程语言语义学家都不同。
  • 他们似乎相信这些“价值”应该通过评估获得。

例如,关于referential transparency的维基百科文章今天上午说:

如果表达式可以替换为其值而不改变程序的行为(换句话说,产生在相同输入上具有相同效果和输出的程序),则表示该表达式是引用透明的。

这完全与哲学家/逻辑学家所说的不一致。他们说如果上下文中的表达式可以被另一个引用同一事物的表达式(一个共同表达式)替换,那么上下文就是引用或引用透明的。谁是这些哲学家/逻辑学家?它们包括FregeRussellWhiteheadCarnapQuineChurch和无数其他人。他们每个人都是一个高耸的人物。至少可以说,这些逻辑学家的综合智力是惊天动地的。所有这些都是一致的,在指称/表示存在于形式语言之外,语言中的表达只能谈论它们。因此,在语言中可以做的所有事情都是用另一个引用同一实体的表达式替换一个表达式。语言中不存在所指对象/表示本身。为什么功能性程序员会偏离这种成熟的传统?

人们可能会认为编程语言语义学家可能误导了他们。但是,他们没有。

Landin

(a)每个表达式都有一个嵌套子表达式结构,(b)每个子表达式表示一些东西(通常是数字,真值或数值函数),(c)表达式表示的东西,即它的“值”,仅取决于其子表达式的值,而不是它们的其他属性。 [增加重点]

Stoy

关于表达式唯一重要的是它的值,任何子表达式都可以被任何其他相等的值替换[添加重点]。此外,表达式的值在某些限制内,无论何时发生都是相同的“。

Bird and Wadler

表达式的值仅取决于其组成表达式的值(如果有的话),并且这些子表达式可以由具有相同值的其他人自由替换[增加强调]。

因此,回想起来,Landin和Strachey通过用“价值”取代“参考”/“外延”来简化术语的努力可能是不明智的。一旦人们听到“价值”,就会有一种诱惑,想到一个导致它的评估过程。将评价所产生的任何东西视为“价值”同样具有诱惑力,尽管可能很清楚这不是表示。这就是我在功能程序员眼中发生的“参照透明度”概念。但是早期语义学家所说的“价值”并不是评价或函数或任何此类事物的输出的结果。这是该术语的表示。

一旦我们理解了表达的所谓“价值”(古典哲学家话语中的“参考”或“外延”)作为复杂的数学/概念对象,就会开辟各种可能性。

  • Strachey将命令式编程语言中的变量解释为L值,正如我在3月25日的回答中所提到的,这是一个复杂的概念对象,在编程语言的语法中没有直接表示。
  • 他还使用诸如状态到状态函数之类的语言来解释命令,这是复杂数学对象的另一个实例,它不是语法中的“值”。
  • 即使是C中的副作用函数调用也有一个明确定义的“值”作为状态转换器,它将状态映射到状态和值对(函数式程序员术语中所谓的“monad”)。

功能程序员不愿意将这些语言称为“引用透明”仅仅意味着他们不愿意接受这样复杂的数学/概念对象作为“价值”。另一方面,他们似乎完全愿意将状态变换器称为“价值”,当它被放入他们自己喜欢的语法中并且用一个像“monad”这样的热门词汇打扮时。我不得不说它们完全不一致,即使我们向他们表示他们的“参考透明度”的想法有一些连贯性。

一些历史可能会说明这些混淆是如何形成的。对于克里斯托弗·斯特拉奇来说,1962年至1967年间是一个非常密集的时期。 1962年至1965年间,他在莫里斯威尔克斯担任研究助理的兼职工作,设计并实施了后来被称为CPL的编程语言。这是一种命令式编程语言,但也意味着具有强大的函数式编程语言功能。 Landin是Strachey在其咨询公司的一名员工,对Strachey的编程语言观产生了巨大的影响。在具有里程碑意义的1965年论文“Next 700 programming languages”中,Landin毫不掩饰地推广了函数式编程语言(称之为外延语言),并将命令式编程语言描述为“对立”。在随后的讨论中,我们发现Strachey对Landin的强势地位提出质疑。

...... DL构成了所有语言的子集。它们是一个有趣的子集,但除非你已经习惯了,否则它不方便使用。我们需要它们,因为目前我们不知道如何使用包含命令和跳转的语言来构建证明。 [增加重点]

1965年,Strachey在牛津大学担任读者,并且似乎基本上全职工作于制定命令和跳跃理论。到1967年,他准备好了一个理论,他在哥本哈根暑期学校的“Fundamental concepts in programming languages”课程中讲授这个理论。这些讲义应该已经发表,但“不幸的是,由于拖延编辑,诉讼从未实现;像Strachey在牛津大学的工作一样,该论文有一个有影响力的私人发行。” (Martin Campbell-Kelly

获得Strachey的着作的困难可能导致混淆被传播,人们依赖二手资料和传闻。但是,既然“Fundamental concepts”可以在网上找到,就没有必要求助于猜测工作。我们应该阅读它并自己决定Strachey的意思。特别是:

  • 在3.2节中,他谈到了“表达”,他谈到了“R值参照透明度”。
  • 他的第3.3节涉及“命令”,他谈到“L值参照透明度”。
  • 在3.4.5节中,他讨论了“函数和例程”,并声明“通过将表达式分解为多个命令和更简单的表达式,或者,如果要将R值中的R值参照透明度的任何偏离消除,或者,如果这很难成为评论的主题。“

任何关于“引用透明度”的讨论都没有理解L值,R值和填充命令式程序员概念宇宙的其他复杂对象之间的区别,这从根本上是错误的。


21
投票

如果表达式可以替换为其值而不更改算法,则表达式是引用透明的,从而产生在相同输入上具有相同效果和输出的算法。


13
投票

引用透明的函数是一个充当数学函数的函数;给定相同的输入,它将始终产生相同的输出。它意味着传入的状态不会被修改,并且该函数没有自己的状态。


8
投票

如果你对词源感兴趣(即为什么这个概念有这个特定的名字),请看看我的blog post这个主题。术语来自哲学家/逻辑学家奎因。


7
投票

对于需要简明解释的人,我会冒一个(但请阅读下面的披露)。

编程语言中的参照透明度促进了等式推理 - 您拥有的参考透明度越高,就越容易进行等式推理。例如。使用(伪)函数定义,

f x = x + x,

在这个定义的范围内,你可以很容易地(安全地)用foo + foo替换f(foo),而不必对你可以执行这种缩减的地方有太多限制,这很好地表明了你的编程语言的参考透明度有多大具有。

例如,如果foo是C编程意义上的x ++,那么你就无法安全地执行这种减少(也就是说,如果你要执行这种减少,你将不会得到你开始使用的相同程序)。

在实际的编程语言中,你不会看到完美的参考透明度,但功能程序员比大多数人更关心它(参见Haskell,它是一个核心目标)。

(完全披露:我是一名功能性程序员,所以在最佳答案中你应该用一点点解释。)


4
投票
  1. 指称语义基于通过构建构成可表示值的域来建模语言。
  2. 函数式程序员使用术语值来描述基于语言重写规则的计算收敛,即。它的操作语义。

在1中,有两种语言的清晰度:

  • 被建模的对象语言
  • 建模语言,元语言

2,由于对象和元语言的接近,它们可能会混淆。

作为一名语言实施者,我发现我需要不断记住这种区别。

因此Reddy教授可以这样解释你:-)

在函数式编程和语义的上下文中,术语“引用透明度”并不是指称透明的。

© www.soinside.com 2019 - 2024. All rights reserved.