Funções puras: “Sem efeitos colaterais” implica “sempre a mesma saída, dada a mesma entrada”?

84

As duas condições que definem uma função puresão as seguintes:

  1. Sem efeitos colaterais (ou seja, apenas alterações no escopo local são permitidas)
  2. Sempre retorna a mesma saída, dada a mesma entrada

Se a primeira condição for sempre verdadeira, há algum momento em que a segunda condição não seja verdadeira?

Ou seja, é realmente necessário apenas com a primeira condição?

Magnus
fonte
3
Suas instalações estão mal especificadas. "Entrada" é muito ampla. As funções podem ser consideradas como dois tipos de entrada. Seus argumentos, e "ambientais" / "contextuais". Uma função que retorna a hora do sistema pode ser considerada pura (embora seja óbvio) se você não distinguir entre esses dois tipos de entrada.
Alexander - Reintegrar Monica
4
@Alexander: No contexto de "função pura", "entrada" é comumente entendida como significando os parâmetros / argumentos que são passados ​​explicitamente (por qualquer mecanismo que a linguagem de programação use). Isso faz parte da definição de "função pura". Mas você está certo, é importante considerar a definição.
sleske
3
Contra-exemplo trivial: retorna o valor de uma variável global. Sem efeitos colaterais (o global só é lido!), Mas ainda resultados potencialmente diferentes a cada vez. (Se você não gosta de globais, retorne o endereço de uma variável local que depende da pilha de chamadas em tempo de execução).
Peter - Reintegrar Monica
2
Você precisa expandir sua definição de "efeitos colaterais"; você diz que um método puro não produz efeitos colaterais, mas também precisa observar que um método puro não consome efeitos colaterais produzidos em outro lugar.
Eric Lippert
2
@sleske Talvez seja comumente compreendido, mas a falta dessa distinção é a causa exata da confusão do OP.
Alexander - Reintegração de Monica

Respostas:

114

Aqui estão alguns contra-exemplos que não mudam o escopo externo, mas ainda são considerados impuros:

  • function a() { return Date.now(); }
  • function b() { return window.globalMutableVar; }
  • function c() { return document.getElementById("myInput").value; }
  • function d() { return Math.random(); } (o que certamente muda o PRNG, mas não é considerado observável)

Acessar variáveis ​​não locais não constantes é suficiente para violar a segunda condição.

Sempre penso nas duas condições de pureza como complementares:

  • a avaliação do resultado não deve ter efeitos no estado lateral
  • o resultado da avaliação não deve ser afetado pelo estado lateral

O termo efeito colateral refere-se apenas ao primeiro, a função que modifica o estado não local. No entanto, às vezes as operações de leitura também são consideradas como efeitos colaterais: quando são operações e também envolvem a escrita, mesmo que seu objetivo principal seja acessar um valor. Exemplos disso são a geração de um número pseudoaleatório que modifica o estado interno do gerador, a leitura de um fluxo de entrada que avança a posição de leitura ou a leitura de um sensor externo que envolve um comando de "fazer medição".

Bergi
fonte
1
Obrigado Bergi. Por algum motivo, pensei que os efeitos colaterais incluíam a leitura de variáveis ​​fora do escopo local, mas acho que é apenas um efeito colateral se gravar essas variáveis ​​externas.
Magnus
17
Se prompt("you choose")não tiver efeitos colaterais, devemos dar um passo atrás e esclarecer o significado dos efeitos colaterais.
Holger
1
@Magnus Sim, é exatamente isso que significa efeito . Vou tentar esclarecer na minha resposta também, não esperava tanta atenção e quero fazer uma resposta digna de dezenas de votos :-)
Bergi
2
Bem, pelo que você sabe, Math.random () retorna um diodo térmico. Na verdade, não é especificado para usar um RNG ruim.
Joshua
1
Das duas condições, já ouvi a primeira chamada de "efeitos", enquanto a última é chamada de "coeficientes". Ambos são "efeitos colaterais" e impuros. f (coeficientes, entrada) -> efeitos, saída Coefeitos são entradas que vêm das mudanças no ambiente mais amplo, efeitos são saídas que mudam o ambiente mais amplo. Elm e Clojurescrips reformulam o trabalho com este modelo, por exemplo.
30

A maneira "normal" de expressar o que é uma função pura é em termos de transparência referencial . Uma função é pura se for referencialmente transparente .

Transparência referencial , grosso modo, significa que você pode substituir a chamada à função por seu valor de retorno ou vice-versa em qualquer ponto do programa, sem alterar o significado do programa.

Então, por exemplo, se C's printffossem referencialmente transparentes, esses dois programas deveriam ter o mesmo significado:

printf("Hello");

e

5;

e todos os programas a seguir devem ter o mesmo significado:

5 + 5;

printf("Hello") + 5;

printf("Hello") + printf("Hello");

Porque printfretorna o número de caracteres escritos, neste caso 5.

Fica ainda mais óbvio com voidfunções. Se eu tenho uma função void foo, então

foo(bar, baz, quux);

deve ser o mesmo que

;

Ou seja, uma vez que foonão retorna nada, devo ser capaz de substituí-lo por nada sem alterar o significado do programa.

É claro, então, que nem printfnem foosão referencialmente transparentes e, portanto, nenhum deles é puro. Na verdade, uma voidfunção nunca pode ser referencialmente transparente, a menos que seja um ambiente autônomo.

Acho essa definição muito mais fácil de lidar do que a que você deu. Também permite aplicá-lo em qualquer granularidade desejada: você pode aplicá-lo a expressões individuais, a funções, a programas inteiros. Ele permite que você, por exemplo, fale sobre uma função como esta:

func fib(n):
    return memo[n] if memo.has_key?(n)
    return 1 if n <= 1
    return memo[n] = fib(n-1) + fib(n-2)

Podemos analisar as expressões que compõem a função e facilmente concluir que não são referencialmente transparentes e, portanto, não puras, uma vez que utilizam uma estrutura de dados mutável, ou seja, o memoarray. No entanto, também podemos olhar para a função e ver que ela é referencialmente transparente e, portanto, pura. Isso às vezes é chamado de pureza externa , ou seja, uma função que parece pura para o mundo exterior, mas é implementada internamente impura.

Essas funções ainda são úteis, porque enquanto a impureza infecta tudo ao seu redor, a interface externa pura constrói uma espécie de "barreira de pureza", onde a impureza infecta apenas as três linhas da função, mas não vaza para o resto do programa . Essas três linhas são muito mais fáceis de analisar quanto à correção do que o programa inteiro.

Jörg W Mittag
fonte
2
Essa impureza afeta todo o programa, uma vez que você tenha simultaneidade.
R .. GitHub PARAR DE AJUDAR O ICE
@R .. Você consegue pensar em uma maneira pela qual a simultaneidade poderia tornar o Fibonacci descrito funcionar externamente impuro? Eu não posso. Gravar em memo[n]é idempotente e deixar de ler a partir dele apenas desperdiça ciclos de CPU.
Brilliand
Eu concordo com vocês dois. A impureza pode levar a problemas de simultaneidade, mas não neste caso específico.
Jörg W Mittag
@R .. Não é difícil imaginar uma versão com reconhecimento de simultaneidade.
user253751
1
@Brilliand Por exemplo, memo[n] = ...pode primeiro criar uma entrada de dicionário e, em seguida, armazenar o valor nela. Isso deixa uma janela durante a qual outro encadeamento pode ver uma entrada não inicializada.
user253751
12

Parece-me que a segunda condição que você descreveu é uma restrição mais fraca do que a primeira.

Deixe-me dar um exemplo, suponha que você tenha uma função para adicionar outra que também registra no console:

function addOneAndLog(x) {
  console.log(x);
  return x + 1;
}

A segunda condição fornecida é satisfeita: esta função sempre retorna a mesma saída quando dada a mesma entrada. No entanto, não é uma função pura porque inclui o efeito colateral de fazer login no console.

Uma função pura é, estritamente falando, uma função que satisfaz a propriedade de transparência referencial . Essa é a propriedade de que podemos substituir um aplicativo de função pelo valor que ele produz, sem alterar o comportamento do programa.

Suponha que temos uma função que simplesmente adiciona:

function addOne(x) {
  return x + 1;
}

Podemos substituir addOne(5)por 6qualquer lugar em nosso programa e nada mudará.

Por outro lado, não podemos substituir addOneAndLog(x)pelo valor 6em qualquer lugar em nosso programa sem alterar o comportamento, porque a primeira expressão resulta em algo sendo gravado no console, enquanto a segunda não.

Consideramos qualquer um desse comportamento extra que addOneAndLog(x)executa além de retornar a saída como um efeito colateral .

TheInnerLight
fonte
"Parece-me que a segunda condição que você descreveu é uma restrição mais fraca do que a primeira." Não, as duas condições são logicamente independentes.
sleske
@sleske você está enganado. Eu forneci definições claras para os termos puro e efeito colateral. Dentro dessas restrições, não há nada que uma função sem efeitos colaterais além de retornar a mesma saída para uma determinada entrada. No entanto, forneci exemplos em que a segunda condição pode ser satisfeita sem a primeira. O conceito fundamental para entender a noção de pureza é a transparência referencial.
TheInnerLight
Pequeno erro de digitação: não há nada que uma função sem efeitos colaterais possa fazer além de retornar a mesma saída para uma determinada entrada.
TheInnerLight
Que tal algo como retornar a hora atual? Isso não tem efeitos colaterais, mas retorna uma saída diferente para a mesma entrada. Ou, de forma mais geral, qualquer função em que o resultado dependa não apenas dos parâmetros de entrada, mas também de uma variável global (alterável).
sleske
2
Parece que você está usando uma definição de "efeito colateral" diferente da comumente usada. Um efeito colateral é comumente definido como "um efeito observável além de retornar um valor" ou uma "mudança observável no estado" - consulte, por exemplo , a Wikipedia , este artigo sobre engenharia de software.SE . Você está totalmente certo de que Date.now()não é puro / referencialmente transparente, mas não porque tem efeitos colaterais, mas porque seu resultado depende de mais do que apenas sua entrada.
sleske
7

Pode haver uma fonte de aleatoriedade de fora do sistema. Suponha que parte do seu cálculo inclua a temperatura ambiente. Em seguida, executar a função produzirá resultados diferentes a cada vez, dependendo do elemento externo aleatório da temperatura ambiente. O estado não é alterado com a execução do programa.

Tudo em que consigo pensar, de qualquer maneira.

user3340459
fonte
3
Para mim, essa "aleatoriedade de fora do sistema" é uma forma de efeito colateral. Funções com esses comportamentos não são "puras".
Joseph M. Dion
2

O problema com as definições de FP é que elas são muito artificiais. Cada avaliação / cálculo tem efeitos colaterais no avaliador. É teoricamente verdade. A negação disso mostra apenas que os apologistas do FP ignoram a filosofia e a lógica: uma "avaliação" significa mudança do estado de algum ambiente inteligente (máquina, cérebro, etc.). Essa é a natureza do processo de avaliação. Sem alterações - sem "cálculos". O efeito pode ser muito visível: aquecimento da CPU ou sua falha, desligamento da placa-mãe em caso de superaquecimento, e assim por diante.

Quando você fala sobre transparência referencial, você deve entender que a informação sobre tal transparência está disponível para o ser humano como criador de todo o sistema e detentor de informação semântica e pode não estar disponível para o compilador. Por exemplo, uma função pode ler algum recurso externo e terá IO mônada em sua assinatura, mas retornará o mesmo valor o tempo todo (por exemplo, o resultado de current_year > 0). O compilador não sabe que a função retornará sempre o mesmo resultado, então a função é impura, mas tem propriedade referencialmente transparente e pode ser substituída por Trueconstante.

Portanto, para evitar tal imprecisão, devemos distinguir funções matemáticas e "funções" em linguagens de programação. As funções em Haskell são sempre impuras e a definição de pureza relacionada a elas é sempre muito condicional: elas estão rodando em hardware real com efeitos colaterais e propriedades físicas reais, o que é errado para funções matemáticas. Isso significa que o exemplo com a função "printf" está totalmente incorreto.

Mas nem todas as funções matemáticas são puras também: cada função que tem t(tempo) como parâmetro pode ser impura: tcontém todos os efeitos e a natureza estocástica da função: no caso comum você tem um sinal de entrada e não tem ideia sobre os valores reais, pode ser até mesmo um barulho.

RandomB
fonte
2

Se a primeira condição for sempre verdadeira, haverá algum momento em que a segunda condição não for verdadeira?

sim

Considere o snippet de código simples abaixo

public int Sum(int a, int b) {
    Random rnd = new Random();
    return rnd.Next(1, 10);
}

Esse código retornará uma saída aleatória para o mesmo conjunto de entradas - no entanto, não tem nenhum efeito colateral.

O efeito geral de ambos os pontos # 1 e # 2 que você mencionou quando combinados significa: Em qualquer ponto do tempo, se a função Sumcom o mesmo i / p for substituída por seu resultado em um programa, o significado geral do programa não muda . Isso nada mais é do que transparência referencial .

rahulaga_dev
fonte
Mas, neste caso, a primeira condição não é verificada: escrever no console é considerado um efeito colateral, já que altera o estado da própria máquina.
perna direita
@Rightleg thx por apontar isso. De alguma forma, eu entendi OP totalmente de outra maneira. resposta corrigida.
rahulaga_dev
2
Isso não muda o estado do gerador aleatório?
Eric Duminil
1
A geração de um número aleatório é em si um efeito colateral, a menos que o estado do gerador de número aleatório seja fornecido explicitamente, o que faria a função satisfazer a condição 2.
TheInnerLight
1
rndnão escapa da função, portanto, o fato de que seu estado muda não importa para a pureza da função, mas o fato de que o Randomconstrutor usa a hora atual como um valor de semente significa que há "entradas" diferentes de ae b.
Sneftel