* Qualquer tarefa do programa pode ser expressa sem estado?

13

Essa é uma questão teórica, mas depois de muitos anos de programação no que agora percebo ser uma técnica imperativa "normal", usando C ++ principalmente, descobri esse outro mundo de programação funcional, que me deparei acidentalmente enquanto aprendia JavaScript casualmente.

Isso me levou a pensar se você poderia substituir tecnicamente qualquer programa completo orientado a estado por uma implementação diferente que seja puramente funcional e sem estado?

É uma ideia intrigante e devo admitir que há uma clareza e elegância na programação funcional que realmente me surpreendeu.

javascript functional-programming haskell state turing-completeness johnbakers
fonte
1
Uma resposta relevante do StackOverflow: stackoverflow.com/questions/3722084/…
jfriend00 14/13
Se existe ou não um estado que persiste de um momento para o outro não depende de qual paradigma de programação você usa, mas de qual problema ou tarefa você está codificando. Se você estiver contando o número de vezes que um botão é clicado, é evidente que há um estado para registrar esse contador e não importa qual técnica de codificação você usa, terá que haver um estado para acompanhar a contagem durante o processo. Portanto, essa tarefa específica não pode ser concluída sem o estado ao longo do caminho, não importa como você a codifique.
jfriend00
6
Se você deseja discutir estado; é necessário indicar claramente, mesmo que seja apenas para o próprio programa. Parece que você está pensando em um estado mutável versus imutável - você pode indicar o que quer dizer na pergunta.
Billy ONeal
1
É como perguntar se todos os programas podem ser convertidos em verdadeiras máquinas de Turing. Tecnicamente sim, mesmo programas que salvam e carregam de um banco de dados, no entanto, torna-se mais difícil a magnitude de simulações desse comportamento em uma máquina de Turing. Da mesma forma, você pode ter um programa cujo lado do controlador na arquitetura MVC é removido e você faz todas as chamadas, embora novamente se torne mais difícil lidar com magnitudes (você se torna o controlador para tornar o programa sem estado).
Neil

Respostas:

17

Resposta curta: sim. Segundo a Wikipedia, a equivalência do cálculo lambda às máquinas de Turing como modelo universal de computação foi mostrada em 1937 por Alan Turing. O modelo computacional de uma máquina de Turing é o que você normalmente tem em mente quando se fala de programação imperativa ou com estado, e o cálculo lambda é uma formalização matemática da "programação funcional pura".

Conjuga-se que todo modelo eficaz de computação é capaz de realizar os mesmos cálculos que uma máquina de Turing e vice-versa. Isso é chamado de tese de Church-Turing . Essa conjunção, no entanto, não pode ser comprovada, por causa do termo mais ou menos intuitivo "modelo eficaz de computação" (talvez alguém invente um novo modelo no futuro?)

Doc Brown
fonte
2
Seu mesmo argumento pode ser revertido, dizendo que, sendo o cálculo de lamba equivalente a máquinas de turismo, todo cálculo deve ter um estado (mais ou menos oculto). Se é representado como externo ao código (por meio de variáveis) ou interno ao fluxo (por meio de chamada de função baseada em pilha), sempre "estado" é.
Emilio Garavaglia
3
O cálculo lambda tem estado; sua restrição é que o estado é imutável. Estado imutável ainda é estado. Parâmetros para funções, incluindo lambdas, ainda são estado; presumivelmente, você deseja que uma função tenha um comportamento diferente, com parâmetros diferentes.
Billy ONeal
@emilio Declarar que existe uma solução equivalente baseada em estado para um problema (como você descreve) não prova que não existe uma versão sem estado dessa solução.
Billy ONeal
2
@EmilioGaravaglia, você está se referindo ao estado de um intérprete lambda-calculus. Ao raciocinar no cálculo lambda, não há necessidade de raciocinar sobre o estado. Além disso, o aspecto de "Mutabilidade" é diferente.
Wirrbel # 14/13
1
@EmilioGaravglia: O estado na programação imperativa é a configuração da memória de cada vez, aqui o espaço do parâmetro é fornecido por todos os valores possíveis da memória e o estado é uma configuração de cada vez (banda da máquina de turing). Ao escrever um programa no cálculo lambda, não existe uma entidade direta, como um campo de memória. A execução do programa é a aplicação de transformações lambda. Etapas intermediárias podem se parecer com "estado", mas são apenas expressões equivalentes do mesmo valor. Nada muda durante a avaliação, as expressões são apenas reescritas e processadas em um formato "mais simples".
Wirrbel #
14

Em qualquer sistema dinâmico, o "estado" é o que faz com que seu presente seja influenciado por seu passado ou futuro (a flecha do tempo não é uma questão matemática, apenas uma restrição física).

Se você tem algo para "lembrar" ou depende do que você fez, você tem um estado.

Um sistema sem estado não é "dinâmico": é apenas uma função combinatória. Isso pode não ter um estado, mas, para produzir resultados diferentes, é necessário que um estado seja fornecido de alguma forma.

Agora, dependendo do modelo computacional a que você se refere, um estado pode ser representado explicitamente (na forma de variável) ou implicitamente (na forma de "endereços de retorno").

quando você fna(fnb(x))está dando um estado ao fnb que, por sua vez, produzirá um estado para o fna. Isso se deve ao fato de xexistir antes que o fnb seja chamado (então, vem do próprio "passado").

Não é uma questão de "existência de estado" ou "estado não existe". É uma questão de "eu me importo" ou "eu não".

Emilio Garavaglia
fonte
0

Estado significa a capacidade de responder a um estímulo presente de uma maneira que depende de estímulos passados, não apenas com base no estímulo presente.

Programas puramente funcionais são apenas funções. Assim, para aplicações práticas, o programa puramente funcional insere um par (old_state * present_stimulus) e gera um par (new_state * present_response). Um "looper" externo e com estado é necessário para aguardar o próximo estímulo e propagar o estado.

Um programa puramente funcional não possui estado intrinsecamente e não pode ser usado diretamente para aplicações práticas.

Portanto, nenhum programa orientado a estado pode ser substituído por uma implementação diferente que seja puramente funcional e sem estado.

Atsby
fonte
0

Você pode evitar um estado mutável explícito, desde que não precise interagir com o mundo exterior.

No JavaScript, para que seu programa realmente tenha um efeito além da execução dos ciclos do processador, é necessário modificar o objeto Dom ou Window, e essas APIs são stateful. Mas suponho que você possa criar um wrapper que passasse os objetos Dom e Window como parâmetros para o código JavaScript e, em seguida, recebesse um novo Dom / Window como saída. Isso isolaria o código JavaScript do estado mutável.

É claro que você ainda depende do estado, pois a janela do navegador e o DOM são de estado por natureza. Qualquer aplicativo interativo é inerentemente com estado, mas você ainda pode estruturar seu código de maneira a minimizar o estado explícito.

Uma pergunta diferente é se é uma boa ideia. Até o Haskell, que é uma linguagem funcional pura por design, inclui a mônada 'state', que permite simular estados mutáveis. Isso mostra que o estado mutável explícito às vezes é realmente um padrão desejável.

JacquesB
fonte
0

Pense em como você implementaria uma "máquina de estado" em uma linguagem de programação sem estado.

Você provavelmente poderia realmente fazer isso, mas acabaria usando nomes de funções como armazenamento. Terminando com gobblyday gook como:

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()
James Anderson
fonte