entendendo a transparência referencial

https://stackoverflow.com/questions/3268587

16-09-2020
|

Pergunta

Geralmente, tenho dor de cabeça porque algo está errado com meu raciocínio:

Para 1 conjunto de argumentos, a função transparente referencial sempre retornará 1 conjunto de valores de saída.
isso significa que tal função pode ser representada como uma tabela verdade (uma tabela onde 1 conjunto de parâmetros de saída é especificado para 1 conjunto de argumentos).
isso faz com que a lógica por trás de tais funções é combinacional (em oposição a sequencial)
isso significa que com linguagem funcional pura (que possui apenas funções rt) é possível descrever apenas lógica combinacional.

A última afirmação é derivada desse raciocínio, mas é obviamente falso;isso significa que há um erro de raciocínio. [pergunta:onde está o erro neste raciocínio?]

UPD2.Vocês estão dizendo muitas coisas interessantes, mas não respondem à minha pergunta.Eu defini isso mais explicitamente agora.Desculpe por bagunçar a definição da pergunta!

Solução

O erro no seu raciocínio é o seguinte:
"Isso significa que essa função pode ser representada como uma tabela de verdade".

Você conclui que, da propriedade de uma linguagem funcional da transparência referencial.Até agora, a conclusão soaria plausível, mas você supervisiona que uma função é capaz de aceitar coleções como entrada e processar em contraste com as entradas fixas de um portão lógico.

Portanto, uma função não é igual a um portão lógico, mas sim um plano de construção de tal portão lógico, dependendo da entrada real (em tempo de execução),

Para comentar sobre o seu comentário: Idiomas funcionais podem - Embora sem estado - implementar uma máquina de estado construindo os estados a partir do zero cada vez que estão sendo acessados.

Outras dicas

.
Pergunta: Onde está o erro neste raciocínio?

Uma função referencialmente transparente pode exigir uma tabela de verdade infinita para representar seu comportamento.Você será duramente pressionado para projetar um circuito infinito em lógica combinatória.

Outro erro: O comportamento da lógica sequencial pode ser representado puramente funcionalmente como uma função de estados para estados.O fato de que, na implementação, esses estados ocorram sequencialmente no tempo não impedem que sejam definindo uma função puramente referencialmente transparente que descreva como o estado evolui ao longo do tempo.

Editar: Embora aparentemente eu tenha perdido o alvo na pergunta real, acho que minha resposta é muito boa, então vou mantê-la :-) (veja abaixo).

Acho que uma maneira mais concisa de formular a pergunta seria:uma linguagem puramente funcional pode calcular qualquer coisa que seja imperativa?

Primeiro de tudo, suponha que você pegou uma linguagem imperativa como C e fez com que não fosse possível alterar variáveis depois de defini-las.Por exemplo.:

int i;

for (i = 0;  // okay, that's one assignment
     i < 10; // just looking, that's all
     i++)    // BUZZZ!  Sorry, can't do that!

Bem, lá se vai o seu for laço.Conseguiremos manter nosso while laço?

while (i < 10)

Claro, mas não é muito útil. i não pode mudar, então ele funcionará para sempre ou não funcionará.

Que tal recursão?Sim, você consegue manter a recursão e ainda é muito útil:

int sum(int *items, unsigned int count)
{
    if (count) {
        // count the first item and sum the rest
        return *items + sum(items + 1, count - 1);
    } else {
        // no items
        return 0;
    }
}

Agora, com funções, não alteramos o estado, mas as variáveis podem, bem, variar.Depois que uma variável passa para nossa função, ela fica bloqueada.Entretanto, podemos chamar a função novamente (recursão), e é como obter um novo conjunto de variáveis (as antigas permanecem as mesmas).Embora existam vários casos de items e count, sum((int[]){1,2,3}, 3) sempre avaliará para 6, então você pode substituir essa expressão por 6 se você gostar.

Ainda podemos fazer o que quisermos?Não tenho 100% de certeza, mas acho que a resposta é “sim”.Você certamente pode, se tiver fechamentos.

Você está certo.A ideia é que, uma vez definida uma variável, ela não pode ser redefinida.Uma expressão referencialmente transparente, dadas as mesmas variáveis, sempre produz o mesmo valor de resultado.

Eu recomendo dar uma olhada em Haskell, uma linguagem puramente funcional.Haskell não possui um operador de "atribuição", estritamente falando.Por exemplo:

my_sum numbers = ??? where
    i     = 0
    total = 0

Aqui, você não pode escrever um "loop for" que aumente i e total à medida que avança.Nem tudo está perdido entretanto.Basta usar a recursão para continuar recebendo novidades iareia totalé:

my_sum numbers = f 0 0 where
    f i total =
        if i < length numbers
            then f i' total'
            else total
        where
            i' = i+1
            total' = total + (numbers !! i)

(Observe que esta é uma maneira estúpida de somar uma lista em Haskell, mas demonstra um método de lidar com uma atribuição única.)

Agora, considere este código de aparência altamente imperativa:

main = do
    a <- readLn
    b <- readLn
    print (a + b)

Na verdade, é um açúcar sintático para:

main =
    readLn >>= (\a ->
    readLn >>= (\b ->
    print (a + b)))

A ideia é que, em vez de main ser uma função que consiste em uma lista de instruções, main é uma ação IO que Haskell executa, e as ações são definidas e encadeadas junto com operações de ligação.Além disso, uma ação que não faz nada, produzindo um valor arbitrário, pode ser definida com o return função.

Observe que bind e return não são específicos de ações.Eles podem ser usados com qualquer tipo que se autodenomina Mônada para fazer todo tipo de coisas divertidas.

Para esclarecer, considere readLn. readLn é uma ação que, se executada, leria uma linha da entrada padrão e produziria seu valor analisado.Para fazer algo com esse valor, não podemos armazená-lo em uma variável porque isso violaria transparência referencial:

a = readLn

Se isso fosse permitido, o valor de a dependeria do mundo e seria diferente toda vez que chamássemos readLn, significado readLn não seria referencialmente transparente.

Em vez disso, vinculamos a ação readLn a uma função que lida com a ação, gerando uma nova ação, assim:

readLn >>= (\x -> print (x + 1))

O resultado desta expressão é um valor de ação.Se Haskell saísse do sofá e executasse esta ação, ele leria um número inteiro, incrementaria-o e imprimiria.Ao vincular o resultado de uma ação a uma função que faz algo com o resultado, conseguimos manter a transparência referencial enquanto brincamos no mundo do estado.

Tanto quanto eu entendo, a transparência referencial só significa: uma determinada função sempre produzirá o mesmo resultado quando invocado com os mesmos argumentos. Então, as funções matemáticas que você aprendeu na escola são referencialmente transparentes.

uma língua que você poderia verificar para aprender como as coisas são feitas em uma linguagem puramente funcional seria Haskell . Existem maneiras de usar "possibilidades de armazenamento atualizáveis" como o leitor Monad, e o Estado Monad para exemplo. Se você estiver interessado em estruturas de dados puramente funcionais, okasaki pode ser um bom leia.

e sim, você está certo: ordem de avaliação em uma linguagem puramente funcional como o Haskell não importa como em linguagens não funcionais, porque se não houver efeitos colaterais, não há razão para fazer algo antes / depois de algo mais - a menos que a entrada de um dependa da saída do outro, ou meios como monads entram em jogo.

Eu realmente não sei sobre a pergunta da tabela de verdade.

Aqui está minha faca para responder a pergunta:

Qualquer sistema pode ser descrito como uma função combinatória, grande ou pequeno.

Não há nada de errado com o raciocínio que as funções puras só podem lidar com a lógica combinatória - é verdade, apenas que os idiomas funcionais escondem isso de você até certo ponto ou outro.

Você pode até descrever, digamos, o funcionamento de um motor de jogo como uma tabela de verdade ou uma função combinatória.

Você pode ter uma função determinista que ocupa "o estado atual de todo o jogo" como a RAM ocupada pelo mecanismo de jogo e pela entrada do teclado e retorna "o estado do jogo um quadro mais tarde". O valor de retorno seria determinado pelas combinações dos bits na entrada.

Claro, em qualquer função significativa e sensata, a entrada é analisada a blocos de inteiros, decimais e booleanos, mas as combinações dos bits desses valores ainda estão determinando a saída de sua função.

Tenha em mente também que a lógica digital básica pode ser descrita em tabelas de verdade. A única razão pela qual isso não é feito para nada mais do que, digamos, aritmética em inteiros de 4 bits, é porque o tamanho da tabela de verdade cresce exponencialmente.

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

Não afiliado a StackOverflow