O que é transparência referencial?

36

Eu vi isso em paradigmas imperativos

f (x) + f (x)

pode não ser o mesmo que:

2 * f (x)

Mas em um paradigma funcional, deve ser o mesmo. Eu tentei implementar os dois casos em Python e Scheme , mas para mim eles parecem bem diretos.

Qual seria um exemplo que poderia apontar a diferença com a função dada?

    
por asgard 24.08.2014 / 17:44
fonte

3 respostas

60

Transparência referencial, referenciada a uma função, indica que você pode determinar o resultado da aplicação dessa função apenas observando os valores de seus argumentos. Você pode escrever funções referencialmente transparentes em qualquer linguagem de programação, por exemplo, Python, Scheme, Pascal, C.

Por outro lado, na maioria das linguagens você também pode escrever funções não referencialmente transparentes. Por exemplo, essa função do Python:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

não é referencialmente transparente, na verdade chamando

foo(x) + foo(x)

e

2 * foo(x)

produzirá valores diferentes para qualquer argumento x . A razão para isso é que a função usa e modifica uma variável global, portanto, o resultado de cada invocação depende desse estado de mudança, e não apenas do argumento da função.

Haskell, uma linguagem puramente funcional, separa estritamente avaliação de expressão na qual funções puras são aplicadas e que é sempre referencialmente transparente, a partir de execução de ação (processamento de valores especiais), que não é referencialmente transparente, ou seja, executar a mesma ação pode ter cada vez um resultado diferente.

Então, para qualquer função do Haskell

f :: Int -> Int

e qualquer inteiro x , é sempre verdade que

2 * (f x) == (f x) + (f x)

Um exemplo de uma ação é o resultado da função de biblioteca getLine :

getLine :: IO String

Como resultado da avaliação de expressão, essa função (na verdade, uma constante) produz primeiro um valor puro do tipo IO String . Valores desse tipo são valores como qualquer outro: você pode passá-los, colocá-los em estruturas de dados, compor-os usando funções especiais e assim por diante. Por exemplo, você pode fazer uma lista de ações assim:

[getLine, getLine] :: [IO String]

As ações são especiais porque você pode dizer ao tempo de execução do Haskell para executá-las escrevendo:

main = <some action>

Nesse caso, quando seu programa Haskell é iniciado, o tempo de execução percorre a ação associada a main e executa , possivelmente produzindo efeitos colaterais. Portanto, a execução da ação não é referencialmente transparente, pois a execução da mesma ação duas vezes pode produzir resultados diferentes, dependendo do que o tempo de execução recebe como entrada.

Graças ao sistema de tipos de Haskell, uma ação nunca pode ser usada em um contexto onde outro tipo é esperado e vice-versa. Então, se você quiser encontrar o tamanho de uma string, você pode usar a função length :

length "Hello"

retornará 5. Mas se você quiser encontrar o comprimento de uma string lida do terminal, não poderá escrever

length (getLine)

porque você recebe um erro de tipo: length espera uma entrada da lista de tipos (e uma String é, na verdade, uma lista), mas getLine é um valor do tipo IO String (uma ação). Dessa forma, o sistema de tipos garante que um valor de ação como getLine (cuja execução é executada fora do idioma principal e que pode ser não-referencialmente transparente) não possa ser oculto dentro de um valor de não ação do tipo Int .

EDITAR

Para responder à pergunta do exizt, aqui está um pequeno programa do Haskell que lê uma linha do console e imprime sua extensão.

main :: IO () -- The main program is an action of type IO ()
main = do
          line <- getLine
          putStrLn (show (length line))

A ação principal consiste em duas subações que são executadas sequencialmente:

  1. getline do tipo IO String ,
  2. o segundo é construído avaliando a função putStrLn do tipo String -> IO () em seu argumento.

Mais precisamente, a segunda ação é construída por

  1. ligando line ao valor lido pela primeira ação,
  2. avaliando as funções puras length (compute length como um inteiro) e, em seguida, show (transforme o inteiro em uma string),
  3. criando a ação aplicando a função putStrLn ao resultado de show .

Neste ponto, a segunda ação pode ser executada. Se você digitou "Olá", ele imprimirá "5".

Se você receber um valor de uma ação usando a notação <- , só poderá usar esse valor em outra ação, por exemplo, você não pode escrever:

main = do
          line <- getLine
          show (length line) -- Error:
                             -- Expected type: IO ()
                             --   Actual type: String

porque show (length line) tem tipo String , enquanto a notação exige que uma ação ( getLine do tipo IO String ) seja seguida por outra ação (por exemplo, putStrLn (show (length line)) do tipo IO () ).

EDIT 2

A definição de transparência referencial de Jörg W Mittag é mais geral do que a minha (eu votei sua resposta). Eu usei uma definição restrita porque o exemplo na pergunta se concentra no valor de retorno das funções e eu queria ilustrar esse aspecto. No entanto, RT geralmente se refere ao significado de todo o programa, incluindo mudanças no estado global e interações com o ambiente (IO) causadas pela avaliação de uma expressão. Então, para uma definição geral correta, você deve se referir a essa resposta.

    
por 24.08.2014 / 18:11
fonte
25
def f(x): return x()

from random import random
f(random) + f(random) == 2*f(random)
# => False

No entanto, isso não é o que significa Transparência Referencial. RT significa que você pode substituir qualquer expressão no programa com o resultado de avaliar essa expressão (ou vice-versa) sem alterar o significado do programa.

Veja, por exemplo, o seguinte programa:

def f(): return 2

print(f() + f())
print(2)

Este programa é referencialmente transparente. Eu posso substituir uma ou ambas as ocorrências de f() com 2 e ele ainda funcionará da mesma forma:

def f(): return 2

print(2 + f())
print(2)

ou

def f(): return 2

print(f() + 2)
print(2)

ou

def f(): return 2

print(2 + 2)
print(f())

todos se comportarão da mesma forma.

Bem, na verdade, eu trapaceei. Eu deveria ser capaz de substituir a chamada para print com seu valor de retorno (que não é nenhum valor) sem alterar o significado do programa. No entanto, claramente, se eu apenas remover as duas instruções print , o significado do programa mudará: antes, ele imprimiu algo na tela, depois disso, não. AE / S não é referencialmente transparente.

A regra simples é: se você pode substituir qualquer expressão, sub-expressão ou sub-rotina chamada com o valor de retorno dessa expressão, sub-expressão ou sub-rotina em qualquer lugar do programa, sem que o programa mude seu significado, então você tem transparência referencial. E o que isso significa, na prática, é que você não pode ter nenhuma E / S, não pode ter nenhum estado mutável, não pode ter nenhum efeito colateral. Em toda expressão, o valor da expressão deve depender somente dos valores das partes constituintes da expressão. E em todas as chamadas de sub-rotina, o valor de retorno deve depender somente dos argumentos.

    
por 24.08.2014 / 18:23
fonte
1

Partes desta resposta são obtidas diretamente de um tutorial inacabado sobre programação funcional , hospedado na minha conta do GitHub:

A function is said to be referentially transparent if it, given the same input parameters, always produces the same output (return value). If one is looking for a raison d'être for pure functional programming, referential transparency is a good candidate. When reasoning with formulae in algebra, arithmetic, and logic, this property — also called substitutivity of equals for equals — is so fundamentally important that it is usually taken for granted...

Considere um exemplo simples:

x = 42

Em uma linguagem funcional pura, o lado esquerdo e o lado direito do sinal de igual são substituíveis um pelo outro nos dois sentidos. Isto é, diferentemente de uma linguagem como C, a notação acima realmente afirma uma igualdade. Uma conseqüência disso é que podemos raciocinar sobre o código do programa como equações matemáticas.

De wiki do Haskell :

Pure computations yield the same value each time they are invoked. This property is called referential transparency and makes possible to conduct equational reasoning on the code...

Para contrastar isso, o tipo de operação executada por linguagens semelhantes a C é, às vezes, chamado de atribuição destrutiva .

O termo pure é frequentemente usado para descrever uma propriedade de expressões, relevantes para esta discussão. Para uma função ser considerada pura,

  • não é permitido exibir efeitos colaterais e
  • deve ser referencialmente transparente.

De acordo com a metáfora da caixa preta, encontrada em numerosos manuais de matemática, os componentes internos de uma função são completamente isolados do mundo exterior. Um efeito colateral é quando uma função ou expressão viola esse princípio - isto é, o procedimento pode se comunicar de alguma forma com outras unidades de programa (por exemplo, para compartilhar e trocar informações).

Em resumo, a transparência referencial é uma obrigação para funções se comportarem como true , funções matemáticas também na semântica de linguagens de programação.

    
por 24.08.2014 / 21:09
fonte