函数式编程 - 什么是参考透明度?

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

12个解决方案
317 votes

“参照透明度”一词来自分析哲学,即分析自然语言结构,基于逻辑和数学方法的陈述和论证的哲学分支。 换句话说,它是计算机科学之外最接近我们称之为编程语言语义的主题。 哲学家Willard Quine负责启动参照透明度的概念,但Bertrand Russell和Alfred Whitehead的方法也暗示了这一点。

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

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

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

意思是一样的

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

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

另一方面,在句子中,

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

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

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

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

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

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

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

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

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

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

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

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

Uday Reddy answered 2019-02-19T00:36:47Z
122 votes

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

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

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;
}

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

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

Brian R. Bondy answered 2019-02-19T00:38:09Z
83 votes

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

Draemon answered 2019-02-19T00:38:33Z
69 votes

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

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

  • 虽然哲学家/逻辑学家使用诸如“参考”,“外延”,“designatum”和“bedeutung”(弗雷格的德语术语)之类的术语,但功能程序员使用术语“价值”。 (这不完全是他们的行为。我注意到Landin,Strachey和他们的后代也使用术语“价值”来谈论参考/外延。这可能只是Landin和Strachey介绍的术语简化,但似乎是 以天真的方式使用时的巨大差异。)

  • 功能程序员似乎相信这些“价值”存在于编程语言中,而不是在外部。 在这样做时,它们与哲学家和编程语言语义学家都不同。

  • 他们似乎相信这些“价值”应该通过评估获得。

例如,维基百科关于参考透明度的文章说,今天早上:

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

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

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

着陆:

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

斯托伊:

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

Bird and Wadler:

表达式的值仅取决于其成分的值   表达式(如果有的话)和这些子表达式可以被其他人自由替换   拥有相同的价值[增加重点]。

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

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

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

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

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

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

1965年,Strachey在牛津大学担任读者,并且似乎基本上全职工作于制定命令和跳跃理论。 到1967年,他准备好了一个理论,他在哥本哈根暑期学校的“编程语言基础概念”课程中讲授这个理论。 讲座本应该已经发表,但“不幸的是,因为拖延编辑,诉讼从未实现; 喜欢然而,Strachey在牛津大学的工作很多纸张有一个有影响力的私人发行量。“(Martin Campbell-Kelly)

获得Strachey的着作的困难可能导致混淆被传播,人们依赖二手资料和传闻。 但是,现在网上已经可以获得“基本概念”,因此无需进行猜测工作。 我们应该阅读它并自己决定Strachey的意思。 特别是:

  • 在3.2节中,他谈到了“表达”,他谈到了“R值参照透明度”。
  • 他的第3.3节涉及“命令”,他谈到“L值参照透明度”。
  • 在3.4.5节中,他谈到了“功能和惯例”,并声明“在R值上下文中R值引用透明度的任何偏离都应该要么通过将表达式分解为几个命令来消除,要么更简单表达,或者,如果这很难,则是评论的主题。“

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

Uday Reddy answered 2019-02-19T00:42:32Z
21 votes

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

CMS answered 2019-02-19T00:42:56Z
13 votes

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

Barry Kelly answered 2019-02-19T00:43:20Z
8 votes

如果您对词源感兴趣(即为什么这个概念有这个特定名称),请查看我关于该主题的博客文章。 术语来自哲学家/逻辑学家奎因。

Andrew Birkett answered 2019-02-19T00:43:44Z
6 votes

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

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

f x = x + x,

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

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

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

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

chrisdornan answered 2019-02-19T00:44:56Z
4 votes
  1. 指称语义基于通过构建构成可表示值的域来建模语言。
  2. 函数式程序员使用术语值来描述基于语言重写规则的计算收敛,即。 它的操作语义。

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

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

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

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

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

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

Anuradha answered 2019-02-19T00:46:13Z
2 votes

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

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

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

rdm answered 2019-02-19T00:46:57Z
2 votes

我希望以下答案增加并证明有争议的第一和第三答案。

让我们授予表达式表示或引用一些指称。 然而,一个问题是这些指示物是否可以作为表达式本身的一部分同构编码,称这些表达式为“值”。 例如,文字数值是算术表达式集的子集,真值是布尔表达式集的子集,等等。想法是将表达式计算为其值(如果有的话)。 因此,“值”一词可以指代表达式或表达式集合的区分元素。 但是如果指示对象和值之间存在同构(双射)可以说他们是一回事。 (这就是说,必须谨慎定义指称领域所证明的指称和同构语义。 举一个回答第三个回答的例子来说,代数数据类型定义data Nat = Zero | Suc Nat没有对应于自然数字集合。)

让我们写一个带孔的表达式[[·]],在某些方面也是已知的作为'背景'。 类似C的表达式的两个上下文示例是ExpressionState

让我们为表达式(无孔)的函数编写[[·]]并在某些方面传达其含义(指称,指示等)提供意义的宇宙。 (我正在借用现场的记号指称语义学。)

让我们在一定程度上正式地调整奎因的定义如下:上下文[[·]]给出任何两个表达式ExpressionState(无孔)是引用透明的那样)[[x]](即表达式表示/指代相同的指示物)然后是[[x++]](即填写[·]++E2的孔导致表达式也表示相同所指)。

Leibniz将equals代入等于的平均值通常表示为“if”[[·]]然后Expression',其中说State是一个功能。 一个功能(或者就此而言,计算函数的程序)是来自a的映射源到目标,以便每个源最多有一个目标元素元件。 非确定性函数是用词不当,它们要么是关系,如果在莱布尼茨的规则中,平等[[x]]是然后双括号被认为是理所当然的省略。 因此,引用透明的上下文是一种功能。 而莱布尼茨的规则是等式推理的主要成分,因此等式推理肯定与参照透明度有关。

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

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

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

对于命令式C语言,我们可以(粗略地)提供语义表达式使用函数[[·]]

[[·]]Expression的子集.State包含对(标识符,值)。 语义函数采用表达式并传递为它的含义是从当前状态到具有更新的对的函数状态和价值。 例如,[[x]]是当前状态下的函数到第一个组件是当前状态和第二个组件的对component是x的值。 相比之下,[[x++]]的功能来自于当前状态到第一个组件是其中值的状态x的增量,其第二个分量就是那个值。 在这感觉,如果它满足,则上下文[·]++是引用透明的上面给出的定义。

我认为功能程序员有权使用参考透明度他们自然地将[[·]]恢复为从表达式到值的函数。函数是一等值,状态也可以是值,而不是a表示。 国家monad(部分)是一个干净的传球机制(或穿线)国家。

answered 2019-02-19T00:48:45Z
0 votes

在函数式编程中,引用透明度通常被定义为程序中的表达式可以被其值(或具有相同值的任何值)替换而不改变程序结果的事实。 这意味着方法应始终为给定参数返回相同的值,而不会产生任何其他影响。 这种函数式编程概念也适用于命令式编程,可以帮助您使代码更清晰。

参考透明度

表达参考透明度用于各种领域,例如数学,逻辑,语言学,哲学和编程。 它在每个领域都有不同的含义。 在这里,我们将只处理计算机程序,虽然我们将与数学类比(简单的数学,不要担心)。 但请注意,计算机科学家不同意编程中参考透明度的含义。 我们将看到的是参考透明度,因为它被功能程序员使用。

数学中的参考透明度在数学中,引用透明性是表达式的属性,可以由具有相同值的其他表达式替换,而不以任何方式更改结果。 请考虑以下示例:

x = 2 + (3 * 4)

我们可以用任何其他具有相同值的表达式替换子表达式(3 * 4)而不改变结果(x的值)。 最明显的表达方式当然是12:

x = 2 + 12

可以使用具有值12(可能是(5 + 7))的任何其他表达而不改变结果。 因此,子表达式(3 * 4)是参考透明的。

我们也可以用另一个具有相同值的表达式替换表达式2 + 12而不改变x的值,因此它也是引用透明的:

x = 14

您可以轻松地看到引用透明度的好处:它允许推理。 没有它,我们无法在不考虑其他元素的情况下解决任何表达。

编程中的参考透明度在编程中,参考透明度适用于程序。 由于程序由子程序组成,子程序本身就是程序,它也适用于那些子程序。 子程序尤其可以通过方法表示。 这意味着方法可以是引用透明的,如果对此方法的调用可能被其返回值替换,则会出现这种情况:

int add(int a, int b) {
        return a + b
    }

int mult(int a, int b) {
        return a * b;
    }

int x = add(2, mult(3, 4));

在此示例中,mult方法是引用透明的,因为对它的任何调用都可以用相应的返回值替换。 这可以通过用12代替mult(3,4)来观察:

int x = add(2, 12)

以同样的方式,add(2,12)可以用相应的返回值替换,14:

int x = 14;

这些替换都不会改变程序的结果,无论它做什么。 请注意,我们可以使用具有相同值的任何其他表达式,这在重构时很有用。

另一方面,请考虑以下程序:

int add(int a, int b) {
    int result = a + b;
    System.out.println("Returning " + result);
    return result;
}

用相应的返回值替换对add方法的调用将更改程序的结果,因为将不再打印该消息。 在这种情况下,它只会消除副作用,但在其他情况下,它可能会更改方法返回的值:

public static void main(String... args) {
    printFibs(10);
}

public static void printFibs(int limit) {
    Fibs fibs = new Fibs();
    for (int i = 0; i < limit; i++) {
        System.out.println(fibs.next());
    }
}

static class Fibs {
    private int previous = -1;
    private int last = 1;

    public Integer next() {
        last = previous + (previous = last);
        return previous + last;
    }
}

这里,下一个方法不能被具有相同值的任何东西替换,因为该方法被设计为在每次调用时返回不同的值。

使用这种非引用透明的方法需要强有力的规则,以便不共享计算中涉及的可变状态。 功能样式避免了这种方法支持引用透明版本。

命令式编程中的参考透明度命令式和函数式编程都使用函数。 虽然函数式编程仅使用函数,但命令式编程使用:

  • 纯函数:返回值且没有其他影响的方法
  • 纯粹的效果:方法只返回一些东西在他们之外)
  • 带副作用的函数:返回值和方法的方法改变一些事

众所周知,避免具有副作用的功能是一种好习惯。 这使命令式程序员具有纯粹的功能和纯粹的效果。 然后,参照透明度是命令式程序员使其程序更易于推理和更容易测试的强大工具。

bumblebee answered 2019-02-19T00:51:47Z
translate from https://stackoverflow.com:/questions/210835/what-is-referential-transparency