O que torna as linguagens de programação funcional declarativas e não imperativas?

Em muitos artigos, descrevendo os benefícios da programação funcional, vi linguagens de programação funcional, como Haskell, ML, Scala ou Clojure, conhecidas como "linguagens declarativas" distintas de linguagens imperativas como C / C ++ / C # / Java. Minha pergunta é o que torna as linguagens de programação funcional declarativas e não imperativas.

Uma explicação frequentemente encontrada que descreve as diferenças entre a programação declarativa e a imperativa é que, na programação imperativa, você diz ao computador "Como fazer algo" em oposição a "O que fazer" em linguagens declarativas. O problema que tenho com essa explicação é que você está constantemente fazendo as duas coisas em todas as linguagens de programação. Mesmo que você desça para a montagem de nível mais baixo e ainda esteja dizendo ao computador "O que fazer", instrua a CPU a adicionar dois números, não o instruirá sobre como executar a adição. Se formos para o outro extremo do espectro, uma linguagem funcional pura de alto nível como Haskell, você estará dizendo ao computador como realizar uma tarefa específica, é isso que o seu programa é uma sequência de instruções para realizar uma tarefa específica que o computador não sabe realizar sozinho. Entendo que linguagens como Haskell, Clojure etc. são obviamente mais altos que C / C ++ / C # / Java e oferecem recursos como avaliação lenta, estruturas de dados imutáveis, funções anônimas, currying, estruturas de dados persistentes, etc. programação funcional possível e eficiente, mas eu não os classificaria como linguagens declarativas.

Uma linguagem declarativa pura para mim seria uma que é composta inteiramente apenas por declarações; um exemplo dessas linguagens seria CSS (Sim, eu sei que CSS tecnicamente não seria uma linguagem de programação). O CSS contém apenas declarações de estilo usadas pelo HTML e Javascript da página. O CSS não pode fazer mais nada além de fazer declarações, não pode criar funções de classe, ou seja, funções que determinam o estilo a ser exibido com base em algum parâmetro, você não pode executar scripts CSS, etc. Isso para mim descreve uma linguagem declarativa (observe que eu não disse declarativa linguagem de programação ).

Atualizar:

Estive brincando com o Prolog recentemente e, para mim, o Prolog é a linguagem de programação mais próxima de uma linguagem totalmente declarativa (pelo menos na minha opinião), se não for a única linguagem de programação totalmente declarativa. Para elaborar a programação no Prolog é feita fazendo declarações que afirmam um fato (uma função predicada que retorna true para uma entrada específica) ou uma regra (uma função predicada que retorna true para uma determinada condição / padrão com base nas entradas), regras são definidos usando uma técnica de correspondência de padrões. Para fazer qualquer coisa no prólogo, você consulta a base de conhecimento substituindo uma ou mais das entradas de um predicado por uma variável e o prólogo tenta encontrar valores para as variáveis ​​para as quais o predicado é bem-sucedido.

Meu ponto de vista é que, no prólogo, não há instruções imperativas, você basicamente diz (declara) ao computador o que sabe e depois pergunta (faz perguntas) sobre o conhecimento. Nas linguagens de programação funcional, você ainda está fornecendo instruções, como pegar um valor, chamar a função X e adicionar 1, etc., mesmo que você não esteja manipulando diretamente os locais da memória ou escrevendo a computação passo a passo. Eu não diria que a programação em Haskell, ML, Scala ou Clojure é declarativa nesse sentido, embora eu possa estar errado. É adequada, verdadeira, pura programação funcional declarativa no sentido que descrevi acima.

Você parece estar traçando uma linha entre declarar coisas e instruir uma máquina. Não existe essa separação difícil e rápida. Como a máquina que está sendo instruída na programação imperativa não precisa ser um hardware físico, há muita liberdade de interpretação. Quase tudo pode ser visto como um programa explícito para a máquina abstrata correta. Por exemplo, você pode ver o CSS como uma linguagem de alto nível para programar uma máquina que principalmente resolve seletores e define atributos dos objetos DOM selecionados.

A questão é se essa perspectiva é sensata e, inversamente, quão perto a sequência de instruções se assemelha a uma declaração do resultado que está sendo calculado. Para CSS, a perspectiva declarativa é claramente mais útil. Para C, a perspectiva imperativa é claramente predominante. Quanto a idiomas como Haskell, bem…

A linguagem especificou, semântica concreta. Ou seja, é claro que se pode interpretar o programa como uma cadeia de operações. Nem é preciso muito esforço para escolher as operações primitivas para que elas sejam mapeadas de maneira adequada no hardware comum (é o que a máquina STG e outros modelos fazem).

No entanto, da maneira como os programas Haskell são escritos, eles freqüentemente podem ser lidos com sensatez como uma descrição do resultado a ser calculado. Pegue, por exemplo, o programa para calcular a soma dos primeiros N fatoriais:

sum_of_fac n = sum [product [1..i] | i <- ..n]

Você pode alterar isso e lê-lo como uma sequência de operações STG, mas muito mais natural é lê-lo como uma descrição do resultado (que é, eu acho, uma definição mais útil de programação declarativa do que "o que calcular"): O resultado é a soma dos produtos de [1..i]todos i= 0,…, n. E isso é muito mais declarativo do que quase qualquer programa ou função C.

A unidade básica de um programa imperativo é a afirmação . As instruções são executadas por seus efeitos colaterais. Eles modificam o estado que recebem. Uma sequência de instruções é uma sequência de comandos, denotando fazer isso e depois fazer isso. O programador especifica a ordem exata para executar o cálculo. É isso que as pessoas querem dizer ao computador como fazê-lo.

A unidade básica de um programa declarativo é a expressão . Expressões não têm efeitos colaterais. Eles especificam um relacionamento entre uma entrada e uma saída, criando uma saída nova e separada de sua entrada, em vez de modificar seu estado de entrada. Uma sequência de expressões não tem sentido sem que algumas contenham expressão especificando o relacionamento entre elas. O programador especifica os relacionamentos entre os dados e o programa infere a ordem para executar a computação a partir desses relacionamentos. É isso que as pessoas querem dizer ao computador o que fazer.

Linguagens imperativas têm expressões, mas seu principal meio de fazer as coisas são declarações. Da mesma forma, as linguagens declarativas têm algumas expressões com semânticas semelhantes às declarações, como sequências de mônadas na donotação de Haskell , mas, em sua essência, são uma grande expressão. Isso permite que os iniciantes escrevam um código que é muito imperativo, mas o verdadeiro poder da linguagem surge quando você foge desse paradigma.

A característica real de definição que separa a programação declarativa da imperativa é no estilo declarativo que você não está dando instruções seqüenciais; no nível mais baixo, sim, a CPU opera dessa maneira, mas isso é uma preocupação do compilador.

Você sugere que o CSS é uma "linguagem declarativa", que eu não chamaria de linguagem. É um formato de estrutura de dados, como JSON, XML, CSV ou INI, apenas um formato para definir dados conhecidos por um intérprete de alguma natureza.

Alguns efeitos colaterais interessantes acontecem quando você tira o operador de atribuição de um idioma, e essa é a verdadeira causa da perda de todas essas instruções imperativas das etapas 1-etapa2-etapa3 em idiomas declarativos.

O que você faz com o operador de atribuição em uma função? Você cria etapas intermediárias. Esse é o ponto crucial, o operador de atribuição é usado para alterar os dados passo a passo. Assim que não é mais possível alterar os dados, você perde todas essas etapas e acaba com:

Toda função possui apenas uma declaração, sendo essa declaração a única declaração

Agora, existem muitas maneiras de fazer com que uma única declaração se pareça com muitas, mas isso é apenas truque, por exemplo: 1 + 3 + (2*4) + 8 - (7 / (8*3))essa é claramente uma declaração única, mas se você a escrever como ...

1 +
3 +
(
  2*4
) +
8 - 
(
  7 / (8*3)
)

Pode assumir a aparência de uma sequência de operações que podem ser mais fáceis para o cérebro reconhecer a decomposição desejada que o autor pretendia. Costumo fazer isso em c # com código como ..

people
  .Where(person => person.MiddleName != null)
  .Select(person => person.MiddleName)
  .Distinct();

Esta é uma afirmação única, mas mostra a aparência de ser decomposta em muitas - observe que não há atribuições.

Observe também, nos dois métodos acima - a maneira como o código é realmente executado não está na ordem em que você o lê imediatamente; porque esse código diz o que fazer, mas não determina como . Observe que a aritmética simples acima obviamente não será executada na sequência escrita da esquerda para a direita e, no exemplo C # acima, esses 3 métodos são todos reentrantes e não executados até a conclusão em sequência; o compilador de fato gera código isso fará o que essa afirmação deseja , mas não necessariamente como você assume.

Acredito que me acostumar com essa abordagem sem etapas intermediárias da codificação declarativa é realmente a parte mais difícil de tudo; e por que Haskell é tão complicado, porque poucos idiomas realmente o proíbem como Haskell. Você precisa começar a fazer ginástica interessante para realizar algumas coisas que normalmente faria com o auxílio de variáveis ​​intermediárias, como a soma.

Em uma linguagem declarativa, se você deseja que uma variável intermediária faça alguma coisa - isso significa passá-la como parâmetro para uma função que faz essa coisa. É por isso que a recursão se torna tão importante.

sum xs = (head xs) + sum (tail xs)

Você não pode criar uma resultSumvariável e adicioná-la à medida que percorre xs, basta pegar o primeiro valor e adicioná-lo à soma de todas as outras coisas - e acessar tudo o que você precisa passar xspara uma função tailporque você não pode simplesmente criar uma variável para xs e sair da cabeça, o que seria uma abordagem imperativa. (Sim, eu sei que você poderia usar a desestruturação, mas este exemplo deve ser ilustrativo)

Eu sei que estou atrasado para a festa, mas eu tive uma epifania no outro dia, então aqui vai ...

Penso que comentários sobre funcionais, imutáveis ​​e sem efeitos colaterais perdem o alvo ao explicar a diferença entre declarativo e imperativo ou ao explicar o que significa programação declarativa. Além disso, como você mencionou na sua pergunta, todo o "o que fazer" vs "como fazê-lo" é muito vago e também não explica.

Vamos tomar o código simples a = b + ccomo base e ver a declaração em alguns idiomas diferentes para entender a idéia:

Quando escrevemos a = b + cem uma linguagem imperativa, como C, estamos atribuindo o valor atual de b + cpara a variável ae nada mais. Não estamos fazendo nenhuma declaração fundamental sobre o que aé. Em vez disso, estamos simplesmente executando uma etapa de um processo.

Quando escrevemos a = b + cem uma linguagem declarativa, como o Microsoft Excel, (sim, o Excel é uma linguagem de programação e provavelmente a mais declarativa de todas), estamos afirmando uma relação entre a, be csempre é o caso ada soma de os outros dois. Não é um passo no processo, é uma invariância, uma garantia, uma declaração da verdade.

As linguagens funcionais também são declarativas, mas quase por acidente. Em Haskel, por exemplo, a = b + ctambém afirma uma relação invariável, mas apenas porque be csão imutáveis.

Então, sim, quando os objetos são imutáveis ​​e as funções são livres de efeitos colaterais, o código se torna declarativo (mesmo que pareça idêntico ao código imperativo), mas não é o objetivo. Tampouco está evitando atribuição. O objetivo do código declarativo é fazer declarações fundamentais sobre relacionamentos.

Você está certo que não há distinção clara entre dizer ao computador o que fazer e como fazê-lo.

No entanto, de um lado do espectro, você pensa quase exclusivamente em como manipular a memória. Ou seja, para resolver um problema, você o apresenta ao computador em um formato como "defina esse local de memória como x, defina esse local de memória como y, vá para o local de memória z ..." e, de alguma forma, você acaba tendo o resultado em algum outro local de memória.

Em linguagens gerenciadas como Java, C # e assim por diante, você não tem mais acesso direto à memória do hardware. O programador imperativo agora se preocupa com variáveis ​​estáticas, referências ou campos de instâncias de classe, todos os quais são, até certo ponto, abstenções para locais de memória.

Em línguas como Haskell, OTOH, a memória desapareceu completamente. Simplesmente não é o caso que, em

f a b = let y = sum [a..b] in y*y

deve haver duas células de memória que contêm os argumentos aeb e outra que contém o resultado intermediário y. Certamente, um back-end do compilador pode emitir um código final que funciona dessa maneira (e, em certo sentido, deve fazê-lo desde que a arquitetura de destino seja uma máquina v. Neumann).

Mas o ponto é que não precisamos internalizar a arquitetura v. Neumann para entender a função acima. Também não precisamos de um computador contemporâneo para executá-lo. Seria fácil traduzir programas em uma linguagem FP pura para uma máquina hipotética que funciona com base no cálculo SKI, por exemplo. Agora tente o mesmo com um programa C!

Uma linguagem declarativa pura para mim seria uma que é composta inteiramente de declarações apenas

Isso não é forte o suficiente, IMHO. Mesmo um programa C é apenas uma sequência de declarações. Sinto que devemos qualificar ainda mais as declarações. Por exemplo, eles estão nos dizendo o que é algo (declarativo) ou o que faz (imperativo).