Get best of the week

Programação funcional é o que você (provavelmente) foi informado. Se você ouviu

Eu gosto de conversas sobre o tópico "Eu costumava ser informado na escola / instituto / pais, mas agora descobri." Se, por um acaso, eu me achar pelo menos um pouco competente no assunto em discussão, essas conversas geralmente se resumem a uma das três opções: "onde você já ouviu essa bobagem antes?" (se o interlocutor estiver certo), "e de onde você tirou isso?" (se ele estiver errado) e "você estiver certo, apenas isso não contradiz o que lhe disseram antes" (na grande maioria dos casos). Gosto dessas conversas pelo seguinte motivo: geralmente o iniciador não está sobrecarregado com o conhecimento preliminar excessivo da questão, o que, em alguns casos, permite apontar alguns pontos que foram aceitos como óbvios, mas não realmente. E um dos tópicos para essas conversas era a programação funcional.

Em geral, tanto se escreveu e se disse sobre o FP que parece haver todas as perguntas sobre sua aplicabilidade, frescor, desempenho etc. roeu a medula óssea. No entanto, essas questões são levantadas repetidamente, e sempre haverá alguém que queira falar sobre o que todos vocês entenderam mal, mas, na verdade, é assim. Talvez hoje eu tente me assumir esse papel ingrato, uma vez que vários posts sobre esse assunto de muito sofrimento recentemente me chamaram a atenção. O primeiro e o segundo mais uma vez dizem que a FA é lixo e estudá-la apenas estraga o carma do seu futuro especialista. Outros ( um e dois) são muito mais adequados, neles o autor pretende explicar que todas essas suas lambdas, combinadores e categorias nada mais são do que poeira em seus olhos, e o próprio FP é uma coisa simples, compreensível e agradável da vida.

Quão verdadeiro é isso?

Antes de abordar a essência da questão, farei uma pequena digressão e enfatizarei. Acho que o conteúdo das duas primeiras postagens é um absurdo total de um analfabeto ... especialista que, com os dedos afastados, discute coisas que ele nem gastou um pouco do seu precioso tempo estudando. Boas pessoas dentre os comentaristas já indicaram que isso não passa de brincadeira. O problema é que, como se viu, não consigo perceber as teses apresentadas nessas traduções como uma brincadeira, pois tive que ouvir a maioria delas ao vivo. Aparentemente, você pode diagnosticar a presença de trauma psicológico causado por um excesso de absurdo que passou pelo cérebro.

Os segundos dois eram mais propensos a evocar emoções positivas, porque neles o autor aplica a prática de FP às tarefas que o desenvolvedor de POO entende. Apesar do desacordo com a mensagem básica da primeira publicação refletida no título e das dúvidas sobre a razoabilidade da implementação do conceito de mônada de forma tão explícita na linguagem orientada para OOP, o autor não pode ser criticado pela falta de elaboração do material. Mas há um aspecto básico, que eu não poderia ignorar. Esse é um tipo de vulgarização da programação funcional, uma tentativa de considerá-lo um conjunto simples de ferramentas e abordagens para o design de programas. O que, na minha opinião, não é inteiramente verdade.

Portanto, neste artigo, é feita uma tentativa de mostrar que as propriedades dos programas funcionais que o autor está tentando reproduzir em seu código não são a base da programação funcional, não são estabelecidas pelos sábios criadores de Haskell e suas soluções de design ilk, mas uma consequência direta desses conceitos e modelos que realmente estabelecido em sua fundação, ou, curiosamente, uma tentativa de compensar as deficiências que essas fundações geram.

Então, ao ponto


Na ciência, muitas vezes você pode observar a seguinte metamorfose. Primeiro, como parte da consideração de um certo processo / fenômeno / teoria, aparece um certo objeto que possui algumas propriedades importantes e úteis. Mas geralmente também acaba sendo bastante complicado em sua estrutura, o que limita sua utilidade prática. Portanto, eles geralmente agem dessa maneira: tomam as propriedades desse objeto como base e, com base nisso, constroem uma nova teoria / modelo / descrição, dentro da qual o objeto desejado se torna simples ou até trivial, ou as propriedades inerentes necessárias aparecem em objetos muito mais simples. Algo assim está relacionado à programação funcional "real" e aos "elementos da programação funcional", disponíveis em linguagens modernas de alto nível.

Como geralmente é útil familiarizar-se com a história de sua origem para entender um fenômeno, vamos relembrar os momentos da história da teoria da computação e da programação importantes para nossa pergunta. No final do século XIX e início do século XX, houve uma reestruturação significativa dos alicerces da ciência matemática. Isso não apenas resolveu uma série de problemas e contradições identificados que surgiram no âmago das idéias na época de que havia matemática e provas matemáticas, mas também colocou uma série de novas questões. Um deles foi o seguinte: qual é o algoritmo? Ou, o que é o mesmo, que classe de problemas pode ser resolvida puramente mecanicamente. Não vou explicar por que essa pergunta acabou sendo importante; é melhor ir direto à resposta que Alan Turing, amplamente conhecido em círculos não muito estreitos, deu a ele. Ele formulou a tese:"Somente funções para as quais uma máquina de Turing pode ser construída são computáveis." Esta afirmação não está comprovada. Isso é, de fato, Turing simplesmente deu uma definição formal estrita do que é considerado uma função computável, consistente com as representações intuitivas que geralmente estão embutidas nesse conceito. Essa definição provou ser capaz de satisfazer os solicitantes, porque eles sabem muito bem o que é uma máquina, mesmo com uma fita infinita, e como ela deve funcionar. Mas para muitos matemáticos, essa definição não é muito satisfeita.que geralmente são investidos nesse conceito. Essa definição provou ser capaz de satisfazer os solicitantes, porque eles sabem muito bem o que é uma máquina, mesmo com uma fita infinita, e como ela deve funcionar. Mas para muitos matemáticos, essa definição não é muito satisfeita.que geralmente são investidos nesse conceito. Essa definição provou ser capaz de satisfazer os solicitantes, porque eles sabem muito bem o que é uma máquina, mesmo com uma fita infinita, e como ela deve funcionar. Mas para muitos matemáticos, essa definição não é muito satisfeita.

Aparentemente, os conceitos que Turing operava lhes pareciam insuficientemente ... abstratos. Nesse sentido, eles não abandonaram as tentativas de dar uma definição diferente, que abrangeria uma classe maior de funções matemáticas e, ao mesmo tempo, ainda corresponderia às nossas idéias intuitivas. Essas tentativas foram infrutíferas. Cada definição alternativa que foi proposta e resistiu à crítica acabou sendo equivalente à definição de Turing, no sentido de que descrevia exatamente a mesma classe de funções matemáticas. No entanto, esses estudos não foram de forma alguma inúteis. Tentativas de olhar para o objeto de estudo de um ponto de vista diferente geralmente são raramente inúteis. No nosso caso, isso levou ao surgimento de várias teorias, uma das quais foi o cálculo lambda proposto pela Igreja de Alonzo.

A preguiça é o motor do progresso


O que é tão útil no cálculo lambda e por que todos estão tão preocupados com isso? Tudo é simples. No modelo proposto por Turing, o algoritmo é uma sequência de instruções familiares para nós, que novamente deve ser executada pelo executor usual. É intuitivo. Mas a definição da Igreja é diferente. O principal (e essencialmente o único) mecanismo de construção no quadro desta teoria são os chamados termos lambda, que em nossos termos atuais podem (condicionalmente) ser chamados de funções anônimas. O programa (algoritmo), neste caso, é uma combinação desses termos construídos de acordo com certas regras, os dados iniciais são os valores das variáveis ​​livres do termo lambda e o processo de cálculo nada mais é do que uma redução (simplificação) do termo lambda (função), que pode ser realizadoassim que alguma variável livre obtém valor. O seguinte fato acabou sendo inesperado aqui: assim que uma variável recebe um valor - ou seja, assim que apresentamos uma parte dos dados iniciais ao programa - podemos realizar a redução, mas não de uma, mas de duas maneiras. No primeiro caso, o processo de cálculo é equivalente ao reproduzido por calculadoras mecânicas típicas, como uma máquina de Turing. A regra corresponde a ela: os argumentos da função devem ser calculados antes que a própria função seja calculada. Mas há outra opção - o chamado cálculo parcial. Nesse caso, se apenas uma parte dos argumentos for calculada, ainda podemos calcular (reduzir) a parte da função que usa apenas esses argumentos. Essa abordagem geralmente é chamada de modelo "preguiçoso" de computação.Em contraste com isso, o modelo de computação de Turing às vezes é chamado de "energético" ou "ganancioso"; as linguagens de programação construídas com base nisso serão chamadas de imperativas abaixo. Uma característica importante dos cálculos "preguiçosos" é que, se uma sub-rotina é escrita como uma função de, digamos, três argumentos, mas, na realidade, usa apenas dois, não é necessário calcular esse terceiro argumento para calcular o valor da função.

E isso nos dá possibilidades práticas interessantes. Por exemplo, a capacidade de trabalhar com sequências infinitas. Seria fácil para quem começou a conhecer a programação funcional em geral e com a linguagem Haskell em particular, entender essa maneira de obter os primeiros n números de Fibonacci:

fibonacci2 a b = a : (fibonacci2 b (a+b))
fibonacci = fibonacci2 1 1

nfibonacci n = take n fibonacci

Explicação para estranhos com Haskell
fibonacci2 , , fibonacci2 b (a+b). ( !) :
def fibonacci2(a, b) :
    return [a] + fibonacci2(b, a+b)

def fibonacci() :
    return fibonacci2(1, 1)

def nfibonacci(n) :
    res = []
    data = fibonacci()
    for i in range(n) :
      res.append( data[i] )
    return res

nfibonacci.

A função fibonacci (e essa é precisamente a função) gera uma lista interminável de números. Se usássemos o modelo computacional familiar, nfibonacci nunca poderia ter terminado (o que, lembro-me, é perfeitamente aceitável e não contradiz as noções de sua “computabilidade”). Mas se usarmos o modelo "preguiçoso" de cálculos, é fácil perceber que, assim que n assume um valor específico, para obter o valor da função nfibonacci, precisamos apenas dos primeiros n elementos da lista que são o resultado da função fibonacci . Nesse caso, podemos agir assim: obter o item da lista - executar a redução, o próximo elemento é outra etapa de redução, n-ésimo argumento - a redução levou à obtenção do valor da função. Ou seja, nesse caso, obtemos um resultado por um tempo finito, apesar do "loop" do procedimento para construir uma lista de números de Fibonacci.

Aqui, um leitor particularmente zeloso e imperativo exclama: " Mas espere, apenas um idiota franco implementará a construção de uma lista de números de Fibonacci dessa maneira! Existem soluções óbvias que não levam a um loop"". E ele, é claro, estará certo. A transferência estúpida de uma solução envolvendo a implementação do modelo de cálculos" preguiçosos "em um programa para cálculos" gananciosos "não é realmente um indicador de grande inteligência. Se você oferecer essa tarefa a um programador que manteve toda a sua vida profissional Lealdade, digamos, à linguagem C, ele provavelmente oferecerá uma variante com um ciclo com um contador e duas variáveis ​​de estado.

Mas o ponto não são os números de Fibonacci. O fato é que a regra para construir uma sequência neste exemplo é separada do método de processamento de seus elementos. E essa é uma propriedade útil que é desejável poder reproduzir em casos mais complexos, quando os elementos da sequência processada são gerados de uma maneira bastante complicada e uma simples transferência da solução "de frente" para a sequência de Fibonacci, nesse caso, é ineficaz no tempo, na memória ou simplesmente leva a código cujo entendimento não é acessível a meros mortais. Essa aspiração é natural e pode ser realizada, por exemplo, através do uso de iteradores ou geradores. Em python, por exemplo, podemos fazer o seguinte:

def fibonacci() :
    a = 1
    b = 1
    yield a
    yield b
    while True :
      c = a + b
      yield c
      a = b
      b = c
     
def nfibonacci(n) :
    return [e for e in itertools.islice(fibonacci(), n)]

Aqui fibonacci () é um gerador que cria um elemento de sequência por elemento. E, neste caso, em vez de fibonacci, pode haver uma função geradora de qualquer complexidade. Se introduzirmos o código completamente, incluindo o código do capô do motor, obtemos um design de software muito complexo e completamente imperativo. Mas a versão final é bastante "funcional". No C ++, pode-se fazer um truque semelhante tendo uma classe Fibonachi especial e iteradores para ele. A decisão variará de acordo com os recursos da linguagem de programação e as preferências do programador, mas o objetivo permanecerá o mesmo - dividir no nível da organização do programa uma maneira de criar uma sequência de comprimentos desconhecidos anteriormente e uma maneira de processar seus elementos.

A diferença é que, dentro da estrutura da abordagem funcional, essa organização do programa é natural e é imposta pelo próprio método de sua implementação, enquanto na estrutura do imperativo exige trabalho criativo adicional, incluindo a criação de conceitos e padrões de design adicionais.

Limpeza é a chave para a saúde


Outra propriedade, na presença da qual eles falam de uma abordagem funcional da programação, é a "pureza" das funções. É a ausência de efeitos colaterais. Ou seja, uma chamada de função com o mesmo conjunto de argumentos deve levar ao mesmo resultado. O autor do post citado descreveu em detalhes suficientes o motivo pelo qual, em programas executados em um estilo imperativo, essa propriedade também é desejável. No entanto, nada mais é do que uma consequência do modelo de cálculos utilizado.

A razão pela qual todas as funções em um programa funcional devem estar limpas é simples. Supondo a presença desses mesmos efeitos colaterais, verifica-se que a ordem na qual os argumentos da função obtêm seu valor afeta diretamente o resultado da função. Podemos dizer que isso também é verdade no quadro da abordagem imperativa, mas no caso de “preguiça” dos cálculos, tudo é muito pior. Mesmo se assumirmos que os argumentos da função podem ser calculados independentemente um do outro em ordem arbitrária, a “preguiça” ainda implica que (condicionalmente) nem todo o código da função será executado de uma só vez. Ele será executado em partes, dependendo de duas coisas - na verdade, a estrutura da função que o compilador condicional nos fornecerá gentilmente, e a ordem na qual apresentaremos seus argumentos para a função.

É natural que esperemos que, se definimos pela primeira vez uma função

def f(x,y) :
  ...

e depois dela
def g(x, y) :
  return f(y, x)

então o resultado da chamada de g (a, b) será igual ao resultado da chamada de f (b, a) para quaisquer valores computáveis ​​independentemente de a e b . Mas se f tem efeitos colaterais que afetam o cálculo dos valores dos argumentos, então nossas expectativas podem ser brutalmente enganadas . Por exemplo, ao calcular b , ocorre a leitura do arquivo - e ao calcular f , também ocorre a leitura do mesmo arquivo. Nos cálculos "preguiçosos", não sabemos antecipadamente qual parte do código (para b ou para f) será executado primeiro. Isso significa que não sabemos qual resultado o programa dará, mesmo que conheçamos o conteúdo do arquivo que ele deve ler. Esse comportamento é, em princípio, inaceitável e, portanto, deve ser categoricamente excluído. Portanto, dentro da estrutura do modelo de cálculos “preguiçosos”, efeitos colaterais descontrolados da função devem ser proibidos .

Se a ordem gananciosa dos cálculos for aplicada, os efeitos colaterais são muito mais previsíveis. Por isso e somente por esse motivo, eles são permitidos na programação imperativa. Mas se você abusar deles, o recurso se tornará um bug. Portanto, você não deve abusar deles. Então, novamente, o conceito de “pureza” que é natural na programação funcional está em demanda no mundo imperativo.

Consequentemente, a tese
Programa funcional - um programa que consiste em funções puras
incorreto se visto como uma definição. Sim, um programa funcional consiste em funções "puras", mas um programa que consiste em funções puras não precisa ser "funcional". Esta é sua propriedade, mas não uma propriedade definidora.

No entanto, há um problema. A capacidade de salvar estado e até de entrada e saída banais são coisas diretamente relacionadas aos efeitos colaterais. E a vida sem eles é cheia de dor e sofrimento. Surge a pergunta: como casar efeitos colaterais e cálculos "preguiçosos"? A resposta em geral não é possível. A resposta está correta - em cada caso específico, uma solução particular satisfatória deve ser buscada. Descobriu-se que muitas maneiras de reproduzir cálculos com efeitos colaterais sem violar o conceito de "pureza" dos cálculos se encaixam no conceito geral da mônada, emprestado da teoria das categorias. Eu não gostaria de tentar novamente explicar o que é e o que é consumido, apenas porque, em qualquer caso, ele não substituirá (e, na minha experiência, nem sequer simplificará) uma explicação de como as variáveis ​​de estado podem ser implementadas especificamente,exceções e coisas semelhantes em linguagens funcionais "puras". A moral principal é que a programação imperativa é uma fonte de inspiração para o funcional, assim como funcional para o imperativo. Além disso, às vezes uma idéia passa por um conceito concorrente como por um filtro, retorna de forma alterada e leva ao aparecimento de uma nova ferramenta.

Mônadas são necessárias em um mundo imperativo? Não tenho opinião estabelecida sobre esse assunto. O autor destejejum certo que necessário. Estou inclinado a duvidar dessa afirmação, já que o uso do conceito de mônada em programas funcionais geralmente está relacionado ao fato de que um determinado algoritmo pode ser formulado, independentemente dos efeitos colaterais específicos que essa mônada oculta. Em outras palavras, se um tipo de dados definido pelo usuário (hipotético, ainda não criado pela humanidade) atende aos requisitos de uma mônada, o algoritmo escrito para ela funcionará corretamente. Isso é conveniente principalmente em estudos teóricos. Mas há algumas nuances. Em primeiro lugar, não está muito claro por que ocultar os efeitos colaterais do invólucro são eficazes em idiomas para os quais são um fenômeno natural. Em segundo lugar,ao escrever programas específicos com tipos de dados específicos e uma arquitetura de destino específica, um algoritmo generalizado é geralmente forçado a passar por uma reestruturação para aumentar a produtividade. É possível escrever algoritmos generalizados usando mônadas em um estilo imperativo, mas a adequação dessa abordagem levanta minhas dúvidas. O fato de que talvez um analógico do tipo std :: optional do C ++ seja declarado como mônada provavelmente não afetará de alguma forma a prática de seu uso.

?


Funções de ordem superior são uma ferramenta tão amplamente usada em programas funcionais que o fato de oferecer suporte a algo semelhante em alguma linguagem de programação é suficiente para alguns indivíduos estranhos reconhecerem essa linguagem como funcional. O que são "funções de ordem superior"? Essa é uma função que opera em outras funções como argumentos ou retorna uma função como resultado. Parece que aqui pode causar debate? Acontece muito. Para começar, o que geralmente é entendido pelo termo "função". Os programadores costumam raciocinar com simplicidade: se algo pode ser chamado como uma função, pode ser considerado como uma função. Na estrutura da abordagem imperativa, isso faz sentido, pois intuitivamente uma função é que, para um determinado conjunto de argumentos, ela produz um certo resultado.Se admitimos a presença de efeitos colaterais, então, no sentido prático, realmente não há diferença entre a função "normal" da linguagem e, digamos, o objeto da classe que possui o operador sobrecarregado ().

Mas na programação funcional, essa definição de função não é construtiva o suficiente, pois não permite interpretar o conceito de cálculo parcial dessa função. Na programação funcional, uma função não é "um dos" elementos estruturais de um programa, mas, em certo sentido, o oposto: todos os elementos do programa são funções. Portanto, de fato, isso é "programação funcional". E, novamente, se tudo é uma função, ou seja, qualquer argumento de qualquer função é uma função, qualquer função com argumentos é uma função de ordem superior. Portanto, funções de ordem superior são um elemento natural de um programa funcional. Tanto é assim que mesmo sua alocação em uma classe separada não faz muito sentido.

Como uma função de ordem superior, o mapa ou a dobra geralmente são fornecidos.. Mas vamos considerar uma forma mais trivial - qualquer - a função dos dois argumentos de f (x, y) . Dentro da estrutura do modelo de cálculos “preguiçosos”, os argumentos dessa função serão calculados apenas quando forem realmente necessários. Suponha que o primeiro argumento seja x .

Calculamos esse argumento, fornecemos seu valor f e, além disso, calculamos tudo o que podemos calcular sem usar o valor do argumento y . O restante dos cálculos pode ser representado como uma nova função, já independente de x , por exemplo, g (y) . Mas, neste caso, nada nos impede de apresentar formalmente f não como função de dois argumentos, mas como função de um argumentof (x) , cujo resultado é outra função g (y) . Em outras palavras, dentro da estrutura da abordagem funcional, qualquer função dos argumentos N> 1 é uma função de ordem superior, pois pode ser interpretada como uma função de um argumento, cujo resultado é a função dos argumentos N-1 .

Podemos implementar esse comportamento como parte de uma abordagem imperativa? Claro que podemos. Em python, escreveríamos algo como o seguinte:

def partial(f, x) :
	def g(*args) :
		return f(x, *args)
	return g

Ao chamar a função parcial , cujo primeiro argumento é a função dos argumentos N e o segundo é o valor do primeiro argumento, obtemos a função N-1 do argumento. Agora podemos usar a nova função sempre que pudermos usar a função de argumento N-1 . Ou seja, eles têm a mesma coisa que no programa funcional. Assim? Não, não assim. Se estivéssemos lidando com um programa verdadeiramente funcional, quando chamamos parcial , calcularíamos parte do valor do primeiro argumento. Em alguns casos, pode até acontecer que g seja um valor constante. O que temos em um análogo imperativo? O valor passado do argumento xapenas lembrado (adicionado ao contexto da função g ). Quando chamamos g , o valor de x será retirado dos compartimentos e simplesmente substituído em f . Ou seja, não há diferença na forma, mas no conteúdo - significativo.

O uso de funções a partir de funções é conveniente, pois permite descrever naturalmente muitos algoritmos importantes. Então, eles foram obrigados a aparecer em linguagens de programação imperativas. E eles apareceram. Mas, como eles usam um modelo de cálculo diferente, isso exigiria o desenvolvimento de novos conceitos. E eles foram desenvolvidos. Por exemplo, o fechamento descrito acima. Ou seja, as funções de ordens superiores nas linguagens imperativas correspondem ao que pode ser observado nas linguagens funcionais, apenas externamente. Mas o conteúdo é completamente diferente. Isso é importante para o programador? Provavelmente não, mas apenas se ele entender bem como funcionam esses mecanismos que implementam recursos semelhantes em sua linguagem de programação favorita. Caso contrário, você pode, por exemplo, implementar "aplicativo parcial", fechar ao criar uma nova função (bem ouo que, no seu caso, se parecerá com uma função) vincula em vez de valor e obtém um comportamento interessante do programa. E depois disso, grite sobre a abordagem funcional falha.

Então, quem estava traindo quem?


Nesta fase da apresentação, é bem possível colocar um ponto e vírgula e retornar à questão principal. Desde agora, podemos formular as seguintes declarações:

  • A principal diferença entre programação funcional e programação imperativa não é propriedade de pureza de funções, presença de funções anônimas, funções de ordem superior, mônadas, polimorfismo paramétrico ou qualquer outra coisa. A principal diferença é o uso de um modelo de cálculo diferente. Tudo o resto não passa de consequências.
  • , , . . , «» «» . , . .
  • , , , . . — .
  • , . , «» ; , . , - , - . .
  • , . , . , , , . .

Programação funcional é sobre o que você (provavelmente) foi informado. São redução beta, combinadores de ponto fixo, mônadas, digitação Hindley-Milner e muito mais. Não confunda o invólucro com o conteúdo. O FP não se baseia na matemática mais simples; não pode ser dominado por algumas noites com um copo de chá; é improvável que seja diretamente projetado nos seus problemas e projetos prementes; você não obterá um lucro garantido e rápido com esse conhecimento. Mas muitos elementos do que está na abordagem funcional são emprestados, processados ​​e, finalmente, implementados em linguagens de programação orientadas para o desenvolvimento de grandes projetos. Sim, eles são organizados de maneira diferente dos seus ancestrais funcionais, mas isso não os torna menos úteis. Somente um idiota clínico transmitirá uma mensagem séria de que Haskell é uma linguagem ruim,porque é difícil escrever um programa para qualquer tipo de contabilidade. Uma pessoa sobrecarregada com a presença de inteligência, mesmo do ponto de vista de sua atividade profissional, sem uma imersão profunda nos meandros da teoria, é capaz de entender exatamente quais práticas da programação funcional devem ser adotadas para melhorar seu código. Por uma demonstração convincente da qual expresso gratidãoPsyhast.

Aprenda programação funcional. Em nome de si mesmo.

More articles:


All Articles