Como funcionam as linguagens de programação funcional?

Se as linguagens de programação funcional não podem salvar nenhum estado, como eles fazem coisas simples como ler a entrada de um usuário? Como eles "armazenam" a entrada (ou armazenam quaisquer dados para esse assunto?)

Por exemplo: como essa coisa simples em C se traduziria em uma linguagem de programação funcional como Haskell?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(Minha pergunta foi inspirada por este excelente post: "Execução no Reino dos Substantivos" . A leitura me deu um melhor entendimento do que exatamente é a programação orientada a objetos, como Java a implementa de uma maneira extrema e como as linguagens de programação funcionais são uma contraste.)

Se as linguagens de programação funcional não podem salvar nenhum estado, como eles fazem algumas coisas simples, como ler a entrada de um usuário (quero dizer, como eles "armazenam"), ou armazenar quaisquer dados para esse assunto?

Como você percebeu, a programação funcional não tem estado - mas isso não significa que não pode armazenar dados. A diferença é que se eu escrever uma declaração (Haskell) ao longo das linhas de

let x = func value 3.14 20 "random"
in ...

Tenho a garantia de que o valor de xé sempre o mesmo em ...: nada pode alterá-lo. Da mesma forma, se eu tiver uma função f :: String -> Integer(uma função que recebe uma string e retorna um inteiro), posso ter certeza de que fnão modificarei seu argumento, nem alterarei nenhuma variável global, nem gravarei dados em um arquivo e assim por diante. Como sepp2k disse em um comentário acima, esta não mutabilidade é realmente útil para raciocinar sobre programas: você escreve funções que dobram, giram e mutilam seus dados, retornando novas cópias para que você possa encadea-los, e você pode ter certeza de que nenhum dessas chamadas de função pode fazer qualquer coisa "prejudicial". Você sabe que xé sempre x, e não precisa se preocupar se alguém escreveu x := foo barem algum lugar entre a declaração dex e seu uso, porque isso é impossível.

Agora, e se eu quiser ler a entrada de um usuário? Como KennyTM disse, a ideia é que uma função impura é uma função pura que é passada para o mundo inteiro como um argumento e retorna seu resultado e o mundo. Claro, você não quer realmente fazer isso: por um lado, é terrivelmente desajeitado e, por outro, o que acontece se eu reutilizar o mesmo objeto de mundo? Portanto, isso é abstraído de alguma forma. Haskell lida com isso com o tipo IO:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

Isso nos diz que mainé uma ação IO que não retorna nada; executar esta ação é o que significa executar um programa Haskell. A regra é que os tipos IO nunca podem escapar de uma ação IO; neste contexto, apresentamos essa ação usando do. Assim, getLineretorna um IO String, que pode ser pensado de duas maneiras: primeiro, como uma ação que, quando executada, produz uma string; em segundo lugar, como uma string "manchada" por IO, pois foi obtida de maneira impura. O primeiro é mais correto, mas o segundo pode ser mais útil. O <-tira o Stringdo IO Stringe o armazena - strmas como estamos em uma ação de IO, teremos que embrulhá-lo novamente, para que não possa "escapar". A próxima linha tenta ler um inteiro ( reads) e pega a primeira correspondência bem-sucedida (fst . head); tudo isso é puro (sem IO), então damos um nome a ele com let no = .... Podemos então usar noe strno .... Assim, armazenamos dados impuros (de getLineem str) e dados puros ( let no = ...).

Este mecanismo para trabalhar com IO é muito poderoso: ele permite separar a parte pura e algorítmica de seu programa da parte impura de interação com o usuário, e reforça isso no nível de tipo. Sua minimumSpanningTreefunção não pode mudar algo em algum outro lugar em seu código ou escrever uma mensagem para seu usuário e assim por diante. É seguro.

Isso é tudo que você precisa saber para usar IO em Haskell; se isso é tudo que você quer, pode parar por aqui. Mas se você quiser entender por que isso funciona, continue lendo. (E observe que essas coisas serão específicas para Haskell - outras linguagens podem escolher uma implementação diferente.)

Portanto, isso provavelmente parecia uma trapaça, de alguma forma adicionando impureza ao puro Haskell. Mas não é - acontece que podemos implementar o tipo IO inteiramente dentro de Haskell puro (contanto que tenhamos RealWorld). A ideia é esta: uma ação IO IO typeé o mesmo que uma função RealWorld -> (type, RealWorld), que pega o mundo real e retorna um objeto do tipo typee o modificado RealWorld. Em seguida, definimos algumas funções para que possamos usar este tipo sem enlouquecer:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

O primeiro nos permite falar sobre ações IO que não fazem nada: return 3é uma ação IO que não consulta o mundo real e apenas retorna 3. O >>=operador, pronunciado "vincular", nos permite executar ações IO. Ele extrai o valor da ação IO, passa-o e ao mundo real por meio da função e retorna a ação IO resultante. Observe que isso >>=impõe nossa regra de que os resultados das ações de IO nunca podem escapar.

Podemos então transformar o anterior mainno seguinte conjunto comum de aplicativos de função:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

O tempo de execução de Haskell começa maincom o inicial RealWorlde está pronto! Tudo é puro, tem apenas uma sintaxe sofisticada.

[ Editar: como @Conal aponta , isso não é realmente o que Haskell usa para fazer IO. Este modelo quebra se você adicionar simultaneidade, ou mesmo qualquer forma de o mundo mudar no meio de uma ação de IO, portanto, seria impossível para Haskell usar este modelo. É preciso apenas para computação sequencial. Portanto, pode ser que o IO de Haskell seja um pouco um esquivo; mesmo se não for, certamente não é tão elegante. De acordo com a observação de @ Conal, veja o que Simon Peyton-Jones diz em Tackling the Awkward Squad [pdf] , seção 3.1; ele apresenta o que pode equivaler a um modelo alternativo ao longo dessas linhas, mas depois o descarta por sua complexidade e adota uma abordagem diferente.]

Novamente, isso explica (praticamente) como o IO e a mutabilidade em geral funcionam em Haskell; se isso é tudo que você quer saber, pode parar de ler aqui. Se você quiser uma última dose de teoria, continue lendo - mas lembre-se, neste ponto, já fomos muito longe de sua pergunta!

Então, uma última coisa: acontece que essa estrutura - um tipo paramétrico com returne >>=- é muito geral; é chamado de mônada, e a donotação return, e >>=funciona com qualquer um deles. Como você viu aqui, as mônadas não são mágicas; tudo o que é mágico é que os doblocos se transformam em chamadas de função. O RealWorldtipo é o único lugar onde vemos alguma magia. Tipos como [], o construtor de lista, também são mônadas e não têm nada a ver com código impuro.

Você agora sabe (quase) tudo sobre o conceito de mônada (exceto algumas leis que devem ser satisfeitas e a definição matemática formal), mas falta-lhe intuição. Há um número ridículo de tutoriais de mônadas online; Eu gosto deste , mas você tem opções. No entanto, isso provavelmente não o ajudará ; a única maneira real de obter a intuição é combinando usá-los com a leitura de alguns tutoriais no momento certo.

No entanto, você não precisa dessa intuição para entender IO . Compreender as mônadas em geral é a cereja do bolo, mas você pode usar IO agora. Você poderia usá-lo depois que eu mostrasse a primeira mainfunção. Você pode até tratar o código IO como se estivesse em uma linguagem impura! Mas lembre-se de que há uma representação funcional subjacente: ninguém está trapaceando.

(PS: Desculpe pela extensão. Fui um pouco mais longe.)

Muitas respostas boas aqui, mas são longas. Vou tentar dar uma resposta curta útil:

• Linguagens funcionais colocam estado nos mesmos lugares que C: em variáveis ​​nomeadas e em objetos alocados no heap. As diferenças são que:

  • Em uma linguagem funcional, uma "variável" obtém seu valor inicial quando entra no escopo (por meio de uma chamada de função ou ligação let), e esse valor não muda depois . Da mesma forma, um objeto alocado no heap é inicializado imediatamente com os valores de todos os seus campos, que não mudam depois disso.

  • "Mudanças de estado" tratadas não pela mutação de variáveis ​​ou objetos existentes, mas pela vinculação de novas variáveis ​​ou alocação de novos objetos.

• O IO funciona por meio de um truque. Um cálculo de efeito colateral que produz uma string é descrito por uma função que recebe um World como argumento e retorna um par contendo a string e um novo World. O mundo inclui o conteúdo de todas as unidades de disco, o histórico de cada pacote de rede já enviado ou recebido, a cor de cada pixel na tela e coisas assim. A chave para o truque é que o acesso ao mundo é cuidadosamente restrito para que

  • Nenhum programa pode fazer uma cópia do World (onde você colocaria?)

  • Nenhum programa pode jogar fora o mundo

  O uso desse truque possibilita que haja um único mundo cujo estado evolui com o tempo. O sistema de tempo de execução da linguagem, que não é escrito em uma linguagem funcional, implementa uma computação de efeito colateral atualizando o mundo único no local em vez de retornar um novo.

  Este truque é lindamente explicado por Simon Peyton Jones e Phil Wadler em seu artigo de referência "Programação Funcional Imperativa" .

Estou interrompendo uma resposta de comentário para uma nova resposta, para dar mais espaço:

Eu escrevi:

Pelo que posso dizer, essa IOhistória ( World -> (a,World)) é um mito quando aplicada a Haskell, já que esse modelo explica apenas a computação puramente sequencial, enquanto o IOtipo de Haskell inclui simultaneidade. Por "puramente sequencial", quero dizer que nem mesmo o mundo (universo) pode mudar entre o início e o fim de um cálculo imperativo, exceto devido a esse cálculo. Por exemplo, enquanto seu computador está funcionando, seu cérebro, etc., não consegue. A simultaneidade pode ser tratada por algo mais parecido World -> PowerSet [(a,World)], o que permite não-determinismo e intercalação.

Norman escreveu:

@Conal: Eu acho que a história de IO generaliza muito bem para o não-determinismo e intercalação; se bem me lembro, há uma explicação muito boa no jornal "Awkward Squad". Mas não conheço um bom artigo que explique claramente o verdadeiro paralelismo.

@Norman: Generaliza em que sentido? Estou sugerindo que o modelo / explicação denotacional normalmente dado, World -> (a,World)não corresponde a Haskell IOporque não leva em conta o não determinismo e a simultaneidade. Pode haver um modelo mais complexo que se ajusta, como World -> PowerSet [(a,World)], mas não sei se esse modelo foi elaborado e se mostrou adequado e consistente. Eu pessoalmente duvido que tal besta possa ser encontrada, visto que IOé preenchida por milhares de chamadas de API imperativas importadas por FFI. E, como tal, IOestá cumprindo seu propósito:

Problema aberto: a IOmônada se tornou o pecado de Haskell. (Sempre que não entendemos algo, jogamos na mônada IO.)

(Do discurso POPL de Simon PJ Vestindo a camisa de cabelo Vestindo a camisa de cabelo: uma retrospectiva de Haskell .)

Na Seção 3.1 de Tackling the Awkward Squad , Simon aponta o que não funciona type IO a = World -> (a, World), incluindo "A abordagem não escala bem quando adicionamos concorrência". Ele então sugere um possível modelo alternativo e, em seguida, abandona a tentativa de explicações denotacionais, dizendo

No entanto, em vez disso, vamos adotar uma semântica operacional, baseada em abordagens padrão para a semântica de cálculos de processo.

Essa falha em encontrar um modelo denotacional preciso e útil está na raiz do motivo pelo qual vejo Haskell IO como um afastamento do espírito e os benefícios profundos do que chamamos de "programação funcional", ou o que Peter Landin mais especificamente chamou de "programação denotativa" . Veja os comentários aqui.

A programação funcional deriva do cálculo lambda. Se você realmente deseja entender a programação funcional, confira http://worrydream.com/AlligatorEggs/

É uma maneira "divertida" de aprender cálculo lambda e levá-lo para o emocionante mundo da programação funcional!

Como saber Lambda Calculus é útil na programação funcional.

Então Lambda Calculus é a base para muitas linguagens de programação do mundo real, como Lisp, Scheme, ML, Haskell, ....

Suponha que desejamos descrever uma função que adiciona três a qualquer entrada para fazermos isso, escreveríamos:

plus3 x = succ(succ(succ x)) 

Leia “plus3 é uma função que, quando aplicada a qualquer número x, produz o sucessor do sucessor do sucessor de x”

Observe que a função que adiciona 3 a qualquer número não precisa ser chamada de plus3; o nome “plus3” é apenas uma abreviatura conveniente para nomear esta função

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Observe que usamos o símbolo lambda para uma função (acho que se parece com um jacaré, estou supondo que foi daí que veio a ideia dos ovos de jacaré)

O símbolo lambda é o Jacaré (uma função) e x é sua cor. Você também pode pensar em x como um argumento (na verdade, as funções Lambda Calculus têm apenas um argumento), o resto você pode pensar nele como o corpo da função.

Agora considere a abstração:

g ≡ λ f. (f (f (succ 0)))

O argumento f é usado em uma posição de função (em uma chamada). Chamamos uma função de ordem superior porque ela recebe outra função como entrada. Você pode pensar nas outras chamadas de função f como " ovos ". Agora, pegando as duas funções ou " crocodilos " que criamos, podemos fazer algo assim:

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

Se você notar, pode ver que nosso λ f Jacaré come nosso λ x Jacaré e então o λ x Jacaré e morre. Então, nosso λ x Jacaré renasce nos ovos de Jacaré de λ f. Em seguida, o processo se repete e o λ x Alligator à esquerda agora come o outro λ x Alligator à direita.

Então você pode usar este conjunto simples de regras de " Jacarés " comendo " Jacarés " para projetar uma gramática e, assim, nasceram as linguagens de programação funcional!

Assim, você pode ver se conhece o Lambda Calculus e entenderá como funcionam as linguagens funcionais.

A técnica para lidar com o estado em Haskell é muito direta. E você não precisa entender as mônadas para entender isso.

Em uma linguagem de programação com estado, você normalmente tem algum valor armazenado em algum lugar, algum código é executado e, em seguida, você tem um novo valor armazenado. Em linguagens imperativas, esse estado está apenas em algum lugar "no fundo". Em uma linguagem funcional (pura), você torna isso explícito, então escreve explicitamente a função que transforma o estado.

Então, em vez de ter algum estado do tipo X, você escreve funções que mapeiam X para X. É isso! Você muda de pensar sobre o estado para pensar sobre quais operações deseja realizar no estado. Você pode então encadear essas funções e combiná-las de várias maneiras para fazer programas inteiros. É claro que você não está limitado a apenas mapear X a X. Você pode escrever funções para obter várias combinações de dados como entrada e retornar várias combinações no final.

As mônadas são uma ferramenta, entre muitas, para ajudar a organizar isso. Mas as mônadas não são realmente a solução para o problema. A solução é pensar em transformações de estado em vez de estado.

Isso também funciona com E / S. Na verdade, o que acontece é o seguinte: em vez de obter a entrada do usuário com algum equivalente direto de scanf, e armazená-la em algum lugar, você escreve uma função para dizer o que faria com o resultado de scanfse o tivesse, e então passa isso função para a API de E / S. Isso é exatamente o que >>=acontece quando você usa a IOmônada em Haskell. Portanto, você nunca precisa armazenar o resultado de qualquer I / O em qualquer lugar - você só precisa escrever um código que diga como gostaria de transformá-lo.

(Algumas linguagens funcionais permitem funções impuras.)

Para linguagens puramente funcionais , a interação do mundo real geralmente é incluída como um dos argumentos da função, como este:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Linguagens diferentes têm estratégias diferentes para abstrair o mundo do programador. Haskell, por exemplo, usa mônadas para esconder o worldargumento.

Mas a parte pura da linguagem funcional em si já é Turing completa, o que significa que qualquer coisa factível em C também é factível em Haskell. A principal diferença para a linguagem imperativa é, em vez de modificar os estados existentes:

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

Você incorpora a parte da modificação em uma chamada de função, geralmente transformando loops em recursões:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

A linguagem funcional pode salvar o estado! Eles geralmente apenas encorajam ou forçam você a ser explícito sobre isso.

Por exemplo, verifique a Mônada Estadual de Haskell .

pode ser útil, a programação de funções para o resto de nós

haskell:

main = do no <- readLn
          print (no + 1)

Você pode, é claro, atribuir coisas a variáveis ​​em linguagens funcionais. Você simplesmente não pode alterá-los (então basicamente todas as variáveis ​​são constantes em linguagens funcionais).