O que é transparência referencial?

https://stackoverflow.com/questions/210835

03-07-2019
|

Pergunta

O que significa o termo referencial transparência média? Eu já ouvi isso descrito como "isso significa que você pode substituir iguais com iguais", mas esta parece ser uma explicação inadequada.

Solução

O termo "transparência referencial" vem da filosofia analítica , o ramo da filosofia que analisa naturais construções de linguagem, declarações e argumentos baseados nos métodos da lógica e da matemática. Em outras palavras, é a ciência mais próxima computador fora sujeita a que chamamos programação semântica da linguagem . O filósofo Willard Quine foi responsável por iniciar o conceito de transparência referencial, mas também estava implícito no se aproxima de Bertrand Russell e Alfred Whitehead.

Na sua essência, "transparência referencial" é uma ideia muito simples e clara. O termo "referente" é usado em filosofia analítica para falar sobre a coisa que uma expressão refere-se a . É mais ou menos o mesmo que o que entendemos por "sentido" ou "denotação" na programação semântica da linguagem. Usando o exemplo de Andrew Birkett ( post ), o termo "a capital da Escócia" refere-se à cidade de Edimburgo. Esse é um exemplo simples de um "referente".

Um contexto em uma frase é "referencialmente transparente" se a substituição de um termo, nesse contexto, por outro termo que refere-se à mesma entidade não altera o significado. Por exemplo

O Parlamento escocês encontra-se na capital da Escócia.

significa o mesmo que

O Parlamento escocês reúne-se em Edimburgo.

Assim, o contexto "O Parlamento escocês reúne-se em ..." é um contexto referencialmente transparente. Podemos substituir "a capital da Escócia", com "Edinburgh" sem alterar o significado. Para colocar de outra forma, o contexto só se preocupa com o que o termo refere-se a e nada mais. Esse é o sentido em que o contexto é "referencialmente transparente."

Por outro lado, na sentença,

Edimburgo foi a capital da Escócia desde 1999.

não podemos fazer tal substituição. Se o fizéssemos, teríamos "Edinburgh tem sido Edimburgo desde 1999", que é uma coisa nutty a dizer, e não transmite o mesmo significado que a sentença original. Assim, parece que o contexto "Edinburgh tem sido ... desde 1999" é referencialmente opaco (o oposto do referencialmente transparente). Aparentemente preocupações sobre algo mais do que o que o termo se refere. O que é isso?

As coisas tais como "a capital da Escócia" são chamados de termos definitivos e deram nenhuma quantidade magra de dor de cabeça para os lógicos e filósofos por um longo tempo. Russell e Quine classificados los dizendo que eles não são realmente "referencial", ou seja, é um erro pensar que os exemplos acima são usados ??para se referir a entidades. O caminho certo para entender "Edinburgh tem sido a capital da Escócia desde 1999" é dizer

Scotland teve um capital desde 1999 e que o capital é Edimburgo.

Esta frase não pode ser transformado em uma noz. Problema resolvido! O ponto de Quine foi dizer que a linguagem natural é confuso, ou pelo menos complicada, porque ela é feita para ser conveniente para o uso prático, mas filósofos e lógicos deve trazer clareza por compreendê-los no caminho certo. transparência referencial é uma ferramenta a ser usada para trazer um clareza do que significa .

O que tudo isso tem a ver com programação? Não muito, na verdade. Como dissemos, a transparência referencial é uma ferramenta para ser usada em compreensão da linguagem, ou seja, na atribuição de significa . Christopher Strachey , que fundou o campo da programação semântica da linguagem, usou em seu estudo do significado. Seu papel fundamental '

A "post-scriptum" separada abaixo relaciona esta discussão às preocupações de programação funcional e imperativa .

Outras dicas

Transparência referencial, um termo comumente usado em programação funcional, significa que dada uma função e um valor de entrada, você receberá sempre a mesma saída. Isso quer dizer que não há nenhum estado externo usado na função.

Aqui está um exemplo de uma função transparente referencial:

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

Com uma função transparente referencial, dada uma entrada e uma função, você pode substituí-lo por um valor em vez de chamar a função. Então, em vez de chamar plusone com um parâmetro de 5, nós poderíamos apenas substituir aquele com 6.

Outro bom exemplo é a matemática em geral. Em matemática dada uma função e um valor de entrada, ele sempre fará o mapeamento para o mesmo valor de saída. f (x) = x + 1. Portanto funções em matemática são referencialmente transparente.

Este conceito é importante para os pesquisadores, porque isso significa que quando você tem uma função referencialmente transparente, que se presta a fácil paralelização automática e cache.

Transparência referencial é usado sempre em linguagens funcionais, como Haskell.

Em contraste, há o conceito de opacidade referencial. Isto significa que o oposto. Chamar a função nem sempre pode produzir a mesma saída.

//global G
int G = 10;

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

Outro exemplo, é uma função membro de uma linguagem de programação orientada a objeto. membro funções comumente operar em suas variáveis ??de membro e, portanto, seria opaca referencial. funções de membro que pode naturalmente ser referencialmente transparente.

Ainda outro exemplo é uma função que lê a partir de um arquivo de texto e imprime a saída. Este arquivo de texto externo pode mudar a qualquer momento, assim que a função seria referencialmente opaco.

A função referencialmente transparente é uma que só depende da sua entrada.

[Este é um pós-escrito para a minha resposta de 25 de março, em um esforço para trazer a discussão para mais perto as preocupações de programação funcional / imperativo.]

idéia de transparência referencial dos programadores funcionais parece diferir da noção padrão de três maneiras:

Considerando que os filósofos / lógicos usar termos como "referência", "denotação", "designatum" e " bedeutung " (termo alemão de Frege), os programadores funcionais usar o termo "valor" . (Isso não é inteiramente seu fazer eu aviso. Que Landin, Strachey e seus descendentes também usou o termo "valor" para falar sobre referência / denotação. Pode ser apenas um terminológica simplificação que Landin e Strachey introduzido, mas parece fazer um grande diferença quando utilizado de forma ingênua.)
programadores funcionais parecem acreditar que esses "valores" existem dentro da linguagem de programação, não fora. Ao fazer isso, eles diferem de ambos os filósofos e os semânticos da linguagem de programação.
Eles parecem acreditar que esses "valores" devem ser obtidas por avaliação.

Por exemplo, o artigo da Wikipedia sobre referencial transparência diz, esta manhã:

Uma expressão é dito ser referencialmente transparente se ele pode ser substituído com o seu valor sem alterar o comportamento de um programa (por outras palavras, obtendo-se um programa que tem os mesmos efeitos e de saída na mesma entrada).

Esta é completamente em desacordo com o que os filósofos / lógicos dizer. Eles dizem que um contexto é referencial ou referencialmente transparente, se uma expressão nesse contexto pode ser substituído por outro expressão que se refere à mesma coisa (a correferencial expressão). Quem são estes filósofos / lógicos? Eles incluem href="http://en.wikipedia.org/wiki/Frege"> Frege, Russell , Whitehead , Carnap , Quine , Church e inúmeros outros. Cada um deles é uma figura imponente. O poder intelectual combinada desses lógicos é a terra tremer para dizer o mínimo. Todos eles são unânimes na posição que referentes / denotações existe fora da linguagem formal e expressões dentro da linguagem só pode falar sobre -los. Então, tudo o que se pode fazer dentro da linguagem é substituir uma expressão por outra expressão que se refere à mesma entidade. Os referentes / denotações-se não existem dentro da linguagem. Por que os programadores funcionais desviar-se esta tradição bem estabelecida?

Pode-se presumir que os semânticos da linguagem de programação pode ter enganado-los. Mas, eles não fizeram.

Landin :

(a) cada expressão tem um estrutura subexpressão de assentamento, (b) cada subexpressão denota algo (geralmente um número, valor de verdade ou função numérica) , (c) a coisa que um denota expressão, isto é, o seu "valor", depende apenas os valores da sua sub- expressões, e não sobre outras propriedades deles. [Grifo nosso]

Stoy :

A única coisa que importa cerca de uma expressão é o seu valor, e qualquer subexpressão pode ser substituídos por qualquer outro igual em valor [grifo nosso]. Além disso, o valor de uma expressão é, dentro de certos limites, o mesmo sempre que ocorre".

Bird e Wadler :

o valor de uma expressão depende somente dos valores de seu constituinte expressões (se houver) e estes subexpressions pode ser substituído livremente pelo outros possuindo o mesmo valor [grifo nosso].

Assim, em retrospecto, os esforços de Landin e Strachey para simplificar a terminologia, substituindo "referência" / "denotação" com "valor" pode ter sido imprudente. Assim como se ouve de um "valor", há uma tentação de pensar de um processo de avaliação que leva a ele. É igualmente tentador pensar de tudo o que a avaliação produz como o "valor", embora possa ser bastante claro que essa não é a denotação. Isso é o que eu se reúnem para ter acontecido com o conceito de "transparência referencial" aos olhos dos programadores funcionais. Mas o "valor" que estava sendo falado pelos primeiros semânticos é não o resultado de uma avaliação ou a saída de uma função ou qualquer coisa semelhante. É a denotação do termo.

Uma vez que entendemos o chamado "valor" de uma expressão ( "referência" ou "denotação" no discurso dos filósofos clássicos) como um objeto matemático / conceitual complexa, todos os tipos de possibilidades se abrem.

Strachey interpretado variáveis ??em linguagens de programação imperativas como L-valores , como mencionado no meu 25 de março resposta, que é um objeto conceitual sofisticado, que não tem uma representação direta dentro da sintaxe de uma linguagem de programação .
Ele também interpretou comandos em tais línguas como funções de estado para estado, outra instância de um objeto matemático complexo que não é um "valor" dentro da sintaxe.
Mesmo uma chamada de função-efetuando lado em C tem um "valor" bem definida como um transformador estado que mapeia estados de pares de estados e valores (o chamado "Monad" na terminologia dos programadores funcionais).

A relutância dos programadores funcionais para chamar essas línguas "referencialmente transparente" implica apenas que eles estão relutantes em admitir tais objetos matemática / conceituais complexos como "valores". Por outro lado, eles parecem perfeitamente dispostos a chamar um estado transformador de um "valor" quando é colocado em sua própria sintaxe favorito e vestida com uma palavra da moda como "mônada". Eu tenho que dizer que eles estão sendo totalmente inconsistente, mesmo se admitirmos a eles que a sua ideia de "transparência referencial" tem alguma coerência.

Um pouco de história pode lançar alguma luz sobre como essas confusões veio a existir. O período entre 1962-1967 foi muito intensivo para Christopher Strachey. Entre 1962-1965, ele conseguiu um emprego de meio período como assistente de pesquisa com Maurice Wilkes para projetar e implementar a linguagem de programação que veio a ser conhecido como CPL. Esta foi uma linguagem de programação imperativa, mas era para ter capacidades funcionais poderosa linguagem de programação também. Landin, que era um empregado de Strachey em sua empresa de consultoria, teve uma enorme influência sobre a visão de Strachey de linguagens de programação. No papel do marco 1965 " Seguinte 700 linguagens de programação ", Landin descaradamente promove linguagens de programação funcional (chamando-os denotativo idiomas) e descreve linguagens de programação imperativas como sua "antítese". Na discussão que se seguiu, encontramos Strachey levantando dúvidas sobre a forte posição da Landin.

... forma DLs um subconjunto de todas as línguas. Eles são um subconjunto interessante, mas um que é inconveniente para uso a menos que você está acostumado a ela. Nós precisamos -los porque no momento não sabemos como construir provas com linguagens que incluem imperativos e saltos. [Grifo nosso]

Em 1965, Strachey levou a postularion de um leitor na Universidade de Oxford e parece ter funcionado essencialmente em tempo integral no desenvolvimento de uma teoria da imperativos e saltos. Em 1967, ele estava pronto com uma teoria, que ele ensinou em seu curso sobre " conceitos fundamentais na programação línguas " em uma escola de verão Copenhagen. As notas de aula deveria ter sido publicado, mas "infelizmente, por causa da dilatória edição, o processo nunca se materializou; gostar muito do trabalho de Strachey em Oxford, no entanto, o papel teve uma circulação privada influente."( Martin Campbell-Kelly )

A dificuldade de obtenção de escritos de Strachey poderia ter levado a confusões sendo propagada, com as pessoas que dependem de fontes secundárias e boatos. Mas, agora que " Conceitos fundamentais " é facilmente disponível na web, não há precisa de recorrer a adivinhar trabalho. Devemos lê-lo e fazer a nossa própria mente, como o que Strachey significava. Em particular:

Na seção 3.2, ele lida com "expressões" onde ele fala sobre "R-valor de transparência referencial".
Sua seção 3.3 lida com "comandos" onde ele fala sobre "L-valor de transparência referencial".
Na seção 3.4.5, ele fala sobre "funções e rotinas" e declara que "qualquer desvio de R-valor de transparência referencial em um contexto R-valor deve ou ser eliminado por decomposição a expressão em vários comandos e mais simples expressões, ou, se isto acaba por ser difícil, objecto de um comentário. "

Qualquer conversa de "transparência referencial" sem compreender a distinção entre L-valores, valores de R e outros objetos complexos que povoam universo conceitual do programador imperativo é fundamentalmente errado.

Uma expressão é referencialmente transparente, se ele pode ser substituído com o seu valor, sem alterar o algoritmo, produzindo um algoritmo que tem os mesmos efeitos e saída na mesma entrada.

A função referencialmente transparente é aquele que age como uma função matemática; dadas as mesmas entradas, ele sempre irá produzir os mesmos resultados. Isso implica que o estado passou em não for modificado, e que a função não tem estado do seu próprio.

Se você estiver interessado na etimologia (ie., Por que esse conceito tem este nome particular), dê uma olhada no meu blogue post sobre o tema. A terminologia vem do filósofo / lógico Quine.

Para aqueles que precisam de uma explicação concisa vou arriscar um (mas ler a divulgação abaixo).

Transparência referencial em uma linguagem de programação promove raciocínio equational - a transparência mais referencial você tem o que é mais fácil de fazer o raciocínio equational. Por exemplo. com um (pseudo) definição de função,

f x = x + x,

a facilidade com que você pode (com segurança) substituir f (foo) com foo + foo no âmbito desta definição, sem ter demasiadas restrições sobre onde você pode realizar esta redução, é uma boa indicação de quanto referencial transparência sua linguagem de programação tem.

Por exemplo, se foo foram x ++ no sentido de programação C, então você não poderia realizar esta redução com segurança (ou seja, se você fosse para realizar esta redução você would't acabar com o mesmo programa que você começou com) .

Em linguagens de programação práticos você não verá perfeita transparência referencial mas os programadores funcionais se preocupam com isso mais do que a maioria (cf Haskell, onde ele é um objetivo central).

(Divulgação completa: Eu sou um programador funcional por isso, a resposta de topo que você deve tomar essa explicação com um grão de sal.)

denotational-semântica é baseada na modelagem de línguas através da construção de domínios que constituem denotable valores .
Os programadores funcionais usar o termo valor para descrever a convergência de um cálculo com base nas regras de reescrita do ie idioma. sua semântica operacionais.

Em 1 há uma clareza de duas línguas em questão:

o que está sendo modelada, a linguagem objeto
a língua de modelagem, a língua meta

No 2, graças à proximidade do objeto e metalinguagens, eles podem ser confundidos.

Como um implementador da linguagem, eu acho que eu preciso lembrar constantemente essa distinção.

Assim Prof. Reddy posso parafrasear você assim: -)

Nos contextos de programação e semântica funcional, o termo Referencial Transparência não é referencialmente transparente.

A seguir esperança resposta que acrescenta e qualifica o 1º controverso e 3ª respostas.

Admitamos que um denota expressão ou refere-se a alguns referente. No entanto, a questão é se esses referentes podem ser codificados isomorficamente como parte das próprias expressões, chamando 'valores' tais expressões. Por exemplo, valores numéricos literais são um subconjunto do conjunto de expressões aritméticas, valores lógicos são um subconjunto do conjunto de expressões booleanas, etc. A ideia consiste em avaliar uma expressão para o seu valor (se ele tiver um). Assim, a palavra 'valor' pode se referir a uma denotação ou a um elemento distinto do conjunto de expressões. Mas se há um isomorfismo (a bijection) entre o referente eo valor que pode dizer que eles são a mesma coisa. (Dito isto, é preciso ter cuidado para definir os referentes eo isomorfismo, como provado pelo campo de denotacional semântica. Para colocar um exemplo mencionado por respostas para o 3º resposta, a algébrica data Nat = Zero | Suc Nat definição do tipo de dados não correspondem como esperado para o conjunto de números naturais.)

Vamos escrever E[·] para uma expressão com um buraco, também conhecido em alguns setores como um 'contexto'. Dois exemplos de contexto para C-como expressões são [·]+1 e [·]++.

Vamos escrever [[·]] para a função que recebe uma expressão (sem buracos) e proporciona o seu significado (referente, denotação, etc.) em alguns significando-fornecendo universo. (Eu estou pedindo a notação do campo de semântica denotacional.)

Vamos adaptar a definição de Quine um pouco formalmente da seguinte forma: a E[·] contexto é sse referencialmente transparente dado qualquer E1 duas expressões e E2 (sem buracos ali) de tal modo que [[E1]] = [[E2]] (isto é, as expressões denotar / referem-à mesmo referente), então é o caso que [[E[E1]]] = [[E[E2]]] (isto é, preenchimento o furo com qualquer E1 ou E2 resultados em expressões que também denotam a mesma referente).

regra da substituição de Leibniz é igual para iguais é normalmente expressa como 'se E1 = E2 então E[E1] = E[E2]', que diz que E[·] é uma função. Uma função (Ou que não seja um programa de cálculo da função) é um mapeamento a partir de um origem a um alvo de modo a que existe no máximo um elemento de alvo para cada fonte elemento. funções não-determinísticas são impróprios, eles são ou relações, funções entregando conjuntos, etc. Se na regra de Leibniz a = igualdade é denotational então as duplas suportes são simplesmente um dado adquirido e elidida. Então um contexto referencialmente transparente é uma função. E a regra de Leibniz é o principal ingrediente de raciocínio equational, raciocínio tão equational é definitivamente relacionadas com a transparência referencial.

Embora [[·]] é uma função a partir de expressões para denotações, ele poderia ser um função das expressões para 'valores' entendido como um subconjunto restrito de expressões e [[·]] pode ser entendida como avaliação.

Agora, se E1 é uma expressão e E2 é um valor que temos o que eu acho que significa a maioria das pessoas ao definir transparência referencial em termos de expressões, valores e avaliação. Mas, como ilustrado pelas 1ª e 3ª respostas nesta página, esta é uma definição inacurate.

O problema com contextos, tais como [·]++ não é o efeito secundário, mas que o seu valor não é definido em C isomorficamente ao seu significado. As funções são não valores (bem, ponteiros para funções são), enquanto que em linguagens de programação funcionais que são. Landin, Strachey, e os pioneiros da semântica denotacional foram bastante inteligente em usando mundos funcionais para fornecer significado.

Para imperativo C-como línguas nós podemos (aproximadamente) fornecer semântica para expressões usando a função [[·]] : Expression -> (State -> State x Value).

Value é um subconjunto de Expression. State contém pares (Identificador, valor). A função semântica toma uma expressão e proporciona quanto seu significado uma função do estado atual para o par com a atualizados estado e um valor. Por exemplo, [[x]] é a função do estado actual para o par cujo primeiro componente é o estado actual e cuja segunda componente é o valor de x. Em contraste, [[x++]] é a função do estado actual para o par cujo primeiro componente é um estado em que o valor de x é incrementado, e cujo segundo componente é que muito valor. Nisso sentido, o [·]++ contexto é referencialmente transparente sse satisfaz os definição dada acima.

Eu acho que os programadores funcionais têm direito a usar transparência referencial em sentido de que eles se recuperar naturalmente [[·]] em função das expressões para valores. As funções são valores de primeira classe eo estado também pode ser um valor, não um denotação. O mônade estado é (em parte) um mecanismo de limpa para a passagem (ou rosqueamento) do estado.

Note que este conceito de "sentido" é algo que acontece na mente do observador. Assim, o mesmo de "referência" pode significar coisas diferentes para pessoas diferentes. Assim, por exemplo, temos uma página de clarificação Edimburgo na Wikipédia.

Uma questão relacionada que pode mostrar-se no contexto da programação pode ser polimorfismo.

E talvez devêssemos ter um nome para o caso especial do polimorfismo (ou talvez até mesmo lançando), onde para os nossos propósitos casos polimórficos diferentes são semanticamente equivalente (em oposição a apenas sendo semelhante Por exemplo, o número 1 -. Que pode ser representado usando um tipo de número inteiro, ou um tipo complexo ou qualquer um de uma variedade de outros tipos -. pode ser tratado polimorficamente)

Eu encontrei a definição de referencial transparência no livro " Estrutura e Implementação de programas de computador " (o Livro Wizard) útil porque é complementado por uma explicação de como referencial transparência é violada, introduzindo a operação atribuição . Confira a seguir conjunto de slides que fiz sobre o assunto: https://www.slideshare.net/pjschwarz/introducing-assignment-invalidates-the-substitution-model-of- avaliação e-viola-referencial-transparência como explicado-in-SICP-the-assistente-book

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow