Programação funcional, declarativa e imperativa [fechada]

O que significam os termos programação funcional, declarativa e imperativa?

No momento em que escrevemos isso, as respostas mais votadas nesta página são imprecisas e confusas na definição declarativa versus imperativa, incluindo a resposta que cita a Wikipedia. Algumas respostas estão confundindo os termos de maneiras diferentes.

Consulte também minha explicação de por que a programação da planilha é declarativa, independentemente de as fórmulas sofrerem mutações nas células.

Além disso, várias respostas afirmam que a programação funcional deve ser um subconjunto de declarativo. Nesse ponto, depende se diferenciarmos "função" de "procedimento". Vamos lidar com o imperativo e o declarativo primeiro.

Definição de expressão declarativa

O único atributo que pode diferenciar uma expressão declarativa de uma expressão imperativa é a transparência referencial (RT) de suas subexpressões. Todos os outros atributos são compartilhados entre os dois tipos de expressões ou derivados do RT.

Uma linguagem 100% declarativa (isto é, na qual toda expressão possível é RT) (entre outros requisitos de RT) não permite a mutação de valores armazenados, por exemplo, HTML e a maioria de Haskell.

Definição de expressão de RT

RT é frequentemente referido como "sem efeitos colaterais". O termo efeitos não tem uma definição precisa; portanto, algumas pessoas não concordam que "nenhum efeito colateral" é o mesmo que RT. RT tem uma definição precisa .

Como toda subexpressão é conceitualmente uma chamada de função, a RT exige que a implementação de uma função (ou seja, as expressões dentro da função chamada) não possa acessar o estado mutável que é externo à função (acessar o estado local mutável é permitido). Simplificando, a função (implementação) deve ser pura .

Definição de função pura

Diz-se que uma função pura "não tem efeitos colaterais". O termo efeitos não possui uma definição precisa; portanto, algumas pessoas não concordam.

Funções puras têm os seguintes atributos.

• a única saída observável é o valor de retorno.
• a única dependência de saída são os argumentos.
• argumentos são totalmente determinados antes que qualquer saída seja gerada.

Lembre-se de que o RT se aplica a expressões (que inclui chamadas de função) e a pureza se aplica a (implementações de) funções.

Um exemplo obscuro de funções impuras que produzem expressões RT é simultaneidade, mas isso ocorre porque a pureza é quebrada na camada de abstração de interrupção. Você realmente não precisa saber disso. Para criar expressões RT, você chama funções puras.

Atributos derivados de TR

Qualquer outro atributo citado para programação declarativa, por exemplo, a citação de 1999 usada pela Wikipedia, deriva do RT ou é compartilhada com a programação imperativa. Provando assim que minha definição precisa está correta.

Observe que a imutabilidade de valores externos é um subconjunto dos requisitos para RT.

• Linguagens declarativas não possuem estruturas de controle em loop, por exemplo, fore while, devido à imutabilidade , a condição do loop nunca mudaria.

• Linguagens declarativas não expressam fluxo de controle além da ordem das funções aninhadas (também conhecidas como dependências lógicas), porque devido à imutabilidade , outras opções de ordem de avaliação não alteram o resultado (veja abaixo).

• Linguagens declarativas expressam "etapas" lógicas (ou seja, a ordem de chamada de função RT aninhada), mas se cada chamada de função é uma semântica de nível superior (ou seja, "o que fazer") não é um requisito da programação declarativa. A distinção de imperativo é que, devido à imutabilidade (ou seja, mais geralmente RT), esses "passos" não podem depender de um estado mutável, mas apenas da ordem relacional da lógica expressa (ou seja, a ordem de aninhamento das chamadas de função, também conhecidas como sub-expressões )

  Por exemplo, o parágrafo HTML <p>não pode ser exibido até que as subexpressões (ou seja, tags) no parágrafo tenham sido avaliadas. Não há estado mutável, apenas uma dependência de ordem devido ao relacionamento lógico da hierarquia de tags (aninhamento de subexpressões, que são chamadas de função aninhadas analogicamente ).

• Portanto, existe o atributo derivado da imutabilidade (geralmente RT), que expressões declarativas expressam apenas o relações lógicas das partes constituintes (isto é, dos argumentos da função de subexpressão) e não relações de estado mutáveis .

Ordem de avaliação

A escolha da ordem de avaliação das subexpressões somente pode dar um resultado variável quando qualquer uma das chamadas de função não é RT (ou seja, a função não é pura), por exemplo, algum estado mutável externo a uma função é acessado dentro da função.

Por exemplo, dadas algumas expressões aninhadas, por exemplo f( g(a, b), h(c, d) ), uma avaliação rápida e preguiçosa dos argumentos da função fornecerá os mesmos resultados se as funçõesf , ge hsão puros.

Considerando que, se as funções f , ge hnão forem puras, a escolha da ordem de avaliação pode dar um resultado diferente.

Observe que expressões aninhadas são funções conceitualmente aninhadas, pois os operadores de expressão são apenas chamadas de função que se disfarçam como prefixo unário, postfix unário ou notação de infixo binário.

Tangencialmente, se todos os identificadores, por exemplo a, b, c, d, são imutáveis em todos os lugares, estado externo para o programa não pode ser acedido (ou seja, I / O), e não há nenhuma quebra camada de abstracção, em seguida, as funções são sempre puro.

A propósito, Haskell tem uma sintaxe diferente f (g a b) (h c d),.

Detalhes da ordem de avaliação

Uma função é uma transição de estado (não um valor armazenável mutável) da entrada para a saída. Para composições RT de chamadas para funções puras , a ordem de execução dessas transições de estado é independente. A transição de estado de cada chamada de função é independente das outras, devido à falta de efeitos colaterais e ao princípio de que uma função RT pode ser substituída por seu valor em cache . Para corrigir um equívoco popular , a composição monádica pura é sempre declarativa e RT , apesar de a IOmônada de Haskell ser indiscutivelmente impura e, portanto, imperativa.World estado externo ao programa (mas no sentido da advertência abaixo, os efeitos colaterais estão isolados).

Avaliação ágil significa que os argumentos das funções são avaliados antes que a função seja chamada e avaliação lenta significa que os argumentos não são avaliados até que (e se) sejam acessados ​​dentro da função.

Definição : os parâmetros da função são declarados no site de definição da função e os argumentos da função são fornecidos no site da chamada da função . Conheça a diferença entre parâmetro e argumento .

Conceptualmente, todas as expressões são (a composição de) chamadas de função, por exemplo, constantes são funções sem entradas, operadores unárias são funções com uma entrada, operadores infixas binários são funções com duas entradas, construtores são funções e instruções mesmo de controlo (por exemplo if, for, while) pode ser modelado com funções. A fim de que estes argumentos funções (não confundir com a ordem de chamada de função aninhada) são avaliados não é declarado pela sintaxe, por exemplo, f( g() )poderia ansiosamente avaliar g, em seguida, fem g's resultado ou pode avaliar fe apenas preguiçosamente avaliar gquando seu resultado é necessário dentro f.

Advertência, nenhuma linguagem completa de Turing (isto é, que permita recursão ilimitada) é perfeitamente declarativa, por exemplo, uma avaliação lenta introduz indeterminismo de memória e tempo. Mas esses efeitos colaterais, devido à escolha da ordem de avaliação, são limitados ao consumo de memória, tempo de execução, latência, não terminação e histerese externa e, portanto, sincronização externa.

Programação funcional

Como a programação declarativa não pode ter loops, a única maneira de iterar é a recursão funcional. É nesse sentido que a programação funcional está relacionada à programação declarativa.

Mas a programação funcional não se limita à programação declarativa . A composição funcional pode ser contrastada com a subtipagem , especialmente com relação ao Problema da Expressão , em que a extensão pode ser alcançada adicionando subtipos ou decomposição funcional . A extensão pode ser uma mistura de ambas as metodologias.

A programação funcional geralmente torna a função um objeto de primeira classe, o que significa que o tipo de função pode aparecer na gramática em qualquer lugar que qualquer outro tipo. O resultado é que as funções podem inserir e operar funções, fornecendo assim uma separação de preocupações enfatizando a composição da função, isto é, separando as dependências entre as subcomputações de uma computação determinística.

Por exemplo, em vez de escrever uma função separada (e empregar recursão em vez de loops, se a função também precisar ser declarativa) para cada um de um número infinito de ações especializadas possíveis que poderiam ser aplicadas a cada elemento de uma coleção, a programação funcional emprega iteração reutilizável funções, por exemplo map, fold, filter. Essas funções de iteração inserem uma função de ação especializada de primeira classe. Essas funções de iteração iteram a coleção e chamam a função de ação especializada de entrada para cada elemento. Essas funções de ação são mais concisas porque não precisam mais conter as instruções de loop para iterar a coleção.

No entanto, observe que, se uma função não é pura, é realmente um procedimento. Talvez possamos argumentar que a programação funcional que utiliza funções impuras é realmente programação procedural. Assim, se concordarmos que expressões declarativas são RT, podemos dizer que a programação procedural não é programação declarativa e, portanto, poderíamos argumentar que a programação funcional é sempre RT e deve ser um subconjunto da programação declarativa.

Paralelismo

Essa composição funcional com funções de primeira classe pode expressar a profundidade do paralelismo separando a função independente.

Princípio de Brent: computação com trabalho we profundidade d pode ser implementada em um PRAM com processador p no tempo O (máximo (m / p, d)).

Simultaneidade e paralelismo também requerem programação declarativa , ou seja, imutabilidade e RT.

Então, de onde veio essa perigosa suposição de que o paralelismo == simultaneidade vem? É uma conseqüência natural de idiomas com efeitos colaterais: quando seu idioma tem efeitos colaterais em todos os lugares, sempre que você tenta fazer mais de uma coisa de cada vez, você tem essencialmente um determinismo causado pela intercalação dos efeitos de cada operação. . Portanto, em linguagens com efeitos colaterais, a única maneira de obter paralelismo é simultaneidade; Portanto, não é de surpreender que muitas vezes vejamos os dois conflitantes.

Ordem de avaliação FP

Observe que a ordem de avaliação também afeta os efeitos colaterais de término e desempenho da composição funcional.

Ansioso (CBV) e preguiçoso (CBN) são duelos categóricos [ 10 ], porque inverteram a ordem de avaliação, ou seja, se as funções externa ou interna, respectivamente, são avaliadas primeiro. Imagine uma árvore de cabeça para baixo e, em seguida, avalie ansiosamente desde as pontas das ramificações da árvore de funções até a hierarquia da ramificação até o tronco da função de nível superior; enquanto preguiçoso avalia do tronco até as pontas dos galhos. Ansioso não possui produtos conjuntivos ("e", a / k / a "produtos" categóricos) e preguiçoso não possui coprodutos disjuntivos ("ou", a / k / a "somas" categóricas) [ 11 ].

atuação

• Ansioso

  Como na não terminação, ansioso é muito ansioso com a composição funcional conjuntiva, ou seja, a estrutura de controle composicional faz um trabalho desnecessário que não é feito com o preguiçoso. Por exemplo , ansiosamente e desnecessariamente mapeia a lista inteira para booleanos, quando é composta por uma dobra que termina no primeiro elemento verdadeiro.

  Esse trabalho desnecessário é a causa do reivindicado "até" um fator log n extra na complexidade de tempo seqüencial de ansioso versus preguiçoso, ambos com funções puras. Uma solução é usar functores (por exemplo, listas) com construtores preguiçosos (ou seja, ansiosos com produtos preguiçosos opcionais), porque com o desejo a incorreta ansiedade se origina da função interna. Isso ocorre porque os produtos são tipos construtivos, ou seja, tipos indutivos com uma álgebra inicial em um ponto de fixação inicial [ 11 ]

• Preguiçoso

  Como na não terminação, o preguiçoso é muito preguiçoso com a composição funcional disjuntiva, ou seja, a finalização coindutiva pode ocorrer mais tarde do que o necessário, resultando em trabalho desnecessário e não determinismo do atraso que não é o caso dos ansiosos [ 10 ] [ 11 ] . Exemplos de finalidade são exceções de estado, tempo, sem término e tempo de execução. Esses são efeitos colaterais imperativos, mas mesmo em uma linguagem declarativa pura (por exemplo, Haskell), há estado na mônada IO imperativa (nota: nem todas as mônadas são imperativas!) Implícitas na alocação de espaço, e o tempo é o estado relativo ao imperativo mundo real. Usar preguiçoso, mesmo com coprodutos ansiosos opcionais, vaza "preguiça" para os coprodutos internos, porque, com preguiça, o erro de preguiça se origina da função externa(veja o exemplo na seção Sem terminação, onde == é uma função externa do operador binário). Isso ocorre porque os coprodutos são limitados pela finalidade, ou seja, tipos coindutivos com uma álgebra final em um objeto final [ 11 ].

  Preguiçoso causa indeterminismo no design e depuração de funções para latência e espaço, cuja depuração provavelmente está além dos recursos da maioria dos programadores, devido à dissonância entre a hierarquia de funções declarada e a ordem de avaliação do tempo de execução. As funções puras e preguiçosas avaliadas com entusiasmo podem potencialmente introduzir a não interrupção anteriormente invisível no tempo de execução. Por outro lado, funções puras ansiosas avaliadas com preguiça poderiam potencialmente introduzir indeterminismo de espaço e latência anteriormente não visto em tempo de execução.

Não rescisão

Em tempo de compilação, devido ao problema de parada e recursão mútua em um idioma completo de Turing, geralmente não é possível garantir que as funções sejam encerradas.

• Ansioso

  Com ansiedade, mas não preguiça, pela conjunção de Head"e" Tail, se um Headou Tailnão termina, respectivamente, List( Head(), Tail() ).tail == Tail()ou List( Head(), Tail() ).head == Head()não é verdade, porque o lado esquerdo não termina e o lado direito termina.

  Visto que, com preguiça, ambos os lados terminam; Portanto, ansioso é muito ansioso com produtos conjuntivos e não termina (incluindo exceções de tempo de execução) nos casos em que não é necessário.

• Preguiçoso

  Com preguiçoso, mas não ansioso, pela disjunção de 1"ou" 2, se fnão terminar, então List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tailnão é verdade porque o lado esquerdo termina e o lado direito não.

  Considerando que, com ansioso nenhum dos lados termina, o teste de igualdade nunca é alcançado. Portanto, preguiçoso é preguiçoso demais com coprodutos disjuntivos e, nesses casos, falha ao finalizar (incluindo exceções de tempo de execução) depois de fazer mais trabalho do que o esperado.

[ 10 ] Continuações declarativas e dualidade categórica, Filinski, seções 2.5.4. Uma comparação entre CBV e CBN e 3.6.1 CBV e CBN no SCL.

[ 11 ] Continuações declarativas e dualidade categórica, Filinski, seções 2.2.1 Produtos e coprodutos, 2.2.2 Objetos terminais e iniciais, 2.5.2 CBV com produtos preguiçosos e 2.5.3 CBN com coprodutos ansiosos.

Não há realmente nenhuma definição objetiva não ambígua para eles. Aqui está como eu os definiria:

Imperativo - O foco está em quais etapas o computador deve executar e não no que o computador fará . (ex C, C ++, Java.).

Declarativo - O foco está no que o computador deve fazer e não em como deve fazê-lo (por exemplo, SQL).

Funcional - um subconjunto de linguagens declarativas que tem grande foco na recursão

imperativo e declarativo descrevem dois estilos opostos de programação. imperativo é a abordagem tradicional de "receita passo a passo", enquanto declarativa é mais "é isso que eu quero, agora você decide como fazê-lo".

essas duas abordagens ocorrem durante a programação - mesmo com a mesma linguagem e o mesmo programa. geralmente, a abordagem declarativa é considerada preferível, porque libera o programador de especificar tantos detalhes, além de ter menos chances de erros (se você descrever o resultado desejado, e algum processo automático bem testado pode funcionar de trás para frente, defina as etapas e espere que as coisas sejam mais confiáveis ​​do que precisar especificar cada etapa manualmente).

por outro lado, uma abordagem imperativa oferece um controle de nível mais baixo - é a "abordagem de micromanager" da programação. e isso pode permitir que o programador explore o conhecimento sobre o problema para fornecer uma resposta mais eficiente. portanto, não é incomum que algumas partes de um programa sejam escritas em um estilo mais declarativo, mas que as partes críticas à velocidade sejam mais imperativas.

como você pode imaginar, o idioma que você usa para escrever um programa afeta o quão declarativo você pode ser - um idioma que possui "inteligência" interna para descobrir o que fazer, dada uma descrição do resultado, permitirá muito mais declarações abordagem diferente daquela em que o programador precisa primeiro adicionar esse tipo de inteligência com código imperativo antes de poder construir uma camada mais declarativa no topo. portanto, por exemplo, uma linguagem como o prólogo é considerada muito declarativa porque possui, internamente, um processo que procura respostas.

até agora, você notará que eu não mencionei funcional programação . isso é porque é um termo cujo significado não está imediatamente relacionado aos outros dois. na sua programação funcional mais simples, significa que você usa funções. em particular, que você use uma linguagem que suporte funções como "valores de primeira classe" - isso significa que não apenas você pode escrever funções, mas também funções que escrevem funções (que escrevem funções que ...) e passe funções para funções. em resumo - essas funções são tão flexíveis e comuns quanto coisas como strings e números.

pode parecer estranho, então, que funcional, imperativo e declarativo sejam freqüentemente mencionados juntos. a razão disso é uma conseqüência de levar a idéia de programação funcional "ao extremo". uma função, em seu sentido mais puro, é algo da matemática - um tipo de "caixa preta" que recebe alguma entrada e sempre fornece a mesma saída. e esse tipo de comportamento não requer o armazenamento de variáveis ​​variáveis. portanto, se você projetar uma linguagem de programação cujo objetivo é implementar uma idéia de programação funcional muito pura e influenciada matematicamente, você acaba rejeitando, em grande parte, a idéia de valores que podem mudar (em certo sentido técnico limitado).

e se você fizer isso - se você limitar a forma como as variáveis ​​podem mudar -, quase por acidente, acabará forçando o programador a escrever programas que são mais declarativos, porque grande parte da programação imperativa está descrevendo como as variáveis ​​mudam e você não pode mais faça isso! portanto, a programação funcional - particularmente a programação em uma linguagem funcional - tende a fornecer um código mais declarativo.

para resumir, então:

• imperativo e declarativo são dois estilos de programação opostos (os mesmos nomes são usados ​​para linguagens de programação que incentivam esses estilos)

• programação funcional é um estilo de programação em que as funções se tornam muito importantes e, como conseqüência, a alteração de valores se torna menos importante. a capacidade limitada de especificar alterações nos valores força um estilo mais declarativo.

então "programação funcional" é freqüentemente descrita como "declarativa".

Em poucas palavras:

Uma linguagem imperativa especifica uma série de instruções que o computador executa em sequência (faça isso e depois faça isso).

Uma linguagem declarativa declara um conjunto de regras sobre quais saídas devem resultar de quais entradas (por exemplo, se você tiver A, o resultado será B). Um mecanismo aplicará essas regras às entradas e fornecerá uma saída.

Uma linguagem funcional declara um conjunto de funções matemáticas / lógicas que definem como a entrada é traduzida para a saída. por exemplo. f (y) = y * y. é um tipo de linguagem declarativa.

Imperativo: como alcançar nosso objetivo

   Take the next customer from a list.
   If the customer lives in Spain, show their details.
   If there are more customers in the list, go to the beginning

Declarativo: o que queremos alcançar

   Show customer details of every customer living in Spain

Programação imperativa significa qualquer estilo de programação em que seu programa esteja estruturado com instruções que descrevem como as operações executadas por um computador ocorrerão .

Programação declarativa significa qualquer estilo de programação em que seu programa seja uma descrição do problema ou da solução - mas não especifique explicitamente como o trabalho será realizado .

Programação funcional é programar avaliando funções e funções de funções ... Como programação (estritamente definida) significa programação, definindo funções matemáticas livres de efeitos colaterais; portanto, é uma forma de programação declarativa, mas não é o único tipo de programação declarativa. .

A programação lógica (por exemplo, no Prolog) é outra forma de programação declarativa. Envolve a computação, decidindo se uma afirmação lógica é verdadeira (ou se pode ser satisfeita). O programa é tipicamente uma série de fatos e regras - ou seja, uma descrição e não uma série de instruções.

A Reescrita de Termos (por exemplo, CASL) é outra forma de programação declarativa. Envolve transformação simbólica de termos algébricos. É completamente diferente da programação lógica e da programação funcional.

imperativo - expressões descrevem a sequência de ações a serem executadas (associativas)

declarative - expressões são declarações que contribuem para o comportamento do programa (associativo, comutativo, idempotente, monotônico)

expressões funcionais têm valor como único efeito; semântica suporta raciocínio equacional

Desde que escrevi minha resposta anterior, formulei uma nova definição da propriedade declarativa que é citada abaixo. Também defini programação imperativa como propriedade dupla.

Essa definição é superior à que eu forneci na minha resposta anterior, porque é sucinta e é mais geral. Mas pode ser mais difícil grunhir, porque a implicação dos teoremas da incompletude aplicáveis ​​à programação e à vida em geral é difícil para os humanos compreenderem.

A explicação citada da definição discute o papel que a programação funcional pura desempenha na programação declarativa.

Todos os tipos exóticos de programação se encaixam na seguinte taxonomia de declarativa versus imperativa, uma vez que a definição a seguir afirma ser dupla.

Declarativo vs. Imperativo

A propriedade declarativa é estranha, obtusa e difícil de capturar em uma definição tecnicamente precisa que permanece geral e não ambígua, porque é uma noção ingênua que podemos declarar o significado (também conhecido como semântica) do programa sem incorrer em efeitos colaterais não intencionais. Existe uma tensão inerente entre a expressão do significado e a prevenção de efeitos não intencionais, e essa tensão realmente deriva dos teoremas da incompletude da programação e do nosso universo.

É simplista demais, tecnicamente impreciso e muitas vezes ambíguo definir declarativo como " o que fazer " e imperativo como " como fazer " . Um caso ambíguo é o "o quê " é o " como " em um programa que gera um programa - um compilador.

Evidentemente, a recursão ilimitada que completa uma linguagem de Turing também está analogamente na semântica - não apenas na estrutura sintática da avaliação (também conhecida como semântica operacional). Este é logicamente um exemplo análogo ao teorema de Gödel - " qualquer sistema completo de axiomas também é inconsistente ". Pondere sobre a estranheza contraditória dessa citação! Também é um exemplo que demonstra como a expressão da semântica não tem um limite comprovável; portanto, não podemos provar 2 que um programa (e analogicamente sua semântica) interrompe o teorema de Halting.

Os teoremas da incompletude derivam da natureza fundamental do nosso universo, que, como afirmado na Segunda Lei da Termodinâmica, é " a entropia (também conhecida como o número de possibilidades independentes) está tendendo ao máximo para sempre ". A codificação e o design de um programa nunca terminam - ele está vivo! - porque tenta atender a uma necessidade do mundo real, e a semântica do mundo real está sempre mudando e tendendo a mais possibilidades. Os humanos nunca param de descobrir coisas novas (incluindo erros nos programas ;-).

Para capturar com precisão e tecnicamente essa noção desejada acima mencionada dentro desse universo estranho que não tem limites (pense nisso! Não há "fora" de nosso universo)), requer uma definição concisa, mas enganosamente não simples, que parecerá incorreta até que seja explicada profundamente.

Definição:

---

A propriedade declarativa é onde pode existir apenas um conjunto possível de instruções que podem expressar cada semântica modular específica.

A propriedade imperativa 3 é a dupla, onde a semântica é inconsistente na composição e / ou pode ser expressa com variações de conjuntos de declarações.

---

Essa definição de declarativo é distintamente local no escopo semântico, o que significa que exige que uma semântica modular mantenha seu significado consistente, independentemente de onde e como é instanciada e empregada no escopo global . Assim, cada semântica modular declarativa deve ser intrinsecamente ortogonal a todos os outros possíveis - e não um algoritmo ou modelo global impossível (devido aos teoremas da incompletude) para testemunhar consistência, que também é o ponto de “ Mais nem sempre é melhor ” por Robert Harper, professor de Ciência da Computação na Universidade Carnegie Mellon, um dos designers da Standard ML.

Exemplos destes semântica declarativa modulares incluem categoria functors teoria, por exemplo, aApplicative , tipagem nominal, espaços de nomes, campos chamados, e com relação ao nível operacional dos semântica então programação funcional puro.

Assim, linguagens declarativas bem projetadas podem expressar mais claramente o significado , embora com alguma perda de generalidade no que pode ser expresso, mas um ganho no que pode ser expresso com consistência intrínseca.

Um exemplo da definição mencionada acima é o conjunto de fórmulas nas células de um programa de planilhas - que não devem ter o mesmo significado quando movidas para células de coluna e linha diferentes, ou seja, os identificadores de célula foram alterados. Os identificadores de célula fazem parte e não são supérfluos para o significado pretendido. Portanto, cada resultado da planilha é gravado exclusivamente nos identificadores de célula em um conjunto de fórmulas. A semântica modular consistente, neste caso, é o uso de identificadores de células como entrada e saída de funções puras para fórmulas de células (veja abaixo).

A Linguagem de Marcação de Hipertexto, também conhecida como HTML - a linguagem para páginas estáticas da web - é um exemplo de uma linguagem declarativa altamente (mas não perfeitamente 3 ) que (pelo menos antes do HTML 5) não tinha capacidade de expressar comportamento dinâmico. Talvez o HTML seja a linguagem mais fácil de aprender. Para comportamento dinâmico, uma linguagem de script imperativa, como JavaScript, geralmente era combinada com HTML. HTML sem JavaScript se encaixa na definição declarativa porque cada tipo nominal (ou seja, as tags) mantém seu significado consistente sob composição dentro das regras da sintaxe.

Uma definição concorrente para declarativa são as propriedades comutativas e idempotentes das declarações semânticas, ou seja, essas declarações podem ser reordenadas e duplicadas sem alterar o significado. Por exemplo, instruções que atribuem valores a campos nomeados podem ser reordenadas e duplicadas sem alterar o significado do programa, se esses nomes forem modulares, por escrito, em qualquer ordem implícita. Às vezes, os nomes implicam uma ordem, por exemplo, os identificadores de célula incluem suas posições de coluna e linha - mover um total na planilha altera seu significado. Caso contrário, essas propriedades implicitamente exigem mundialconsistência da semântica. Geralmente é impossível projetar a semântica das instruções para que elas permaneçam consistentes se ordenadas ou duplicadas aleatoriamente, porque ordem e duplicação são intrínsecas à semântica. Por exemplo, as declarações "Foo existe" (ou construção) e "Foo não existe" (e destruição). Se considerarmos a inconsistência aleatória endêmica da semântica pretendida, aceitaremos essa definição como suficientemente geral para a propriedade declarativa. Em essência, essa definição é vaga como uma definição generalizada, porque tenta tornar a consistência ortogonal à semântica, ou seja, desafiar o fato de que o universo da semântica é dinamicamente ilimitado e não pode ser capturado em um paradigma de coerência global .

Exigir as propriedades comutativas e idempotentes para a (ordem de avaliação estrutural da) semântica operacional de nível inferior converte a semântica operacional em uma semântica modular localizada declarativa , por exemplo, programação funcional pura (incluindo recursão em vez de loops imperativos). Então a ordem operacional dos detalhes da implementação não afeta (ou seja, espalha-se globalmente ) a consistência da semântica de nível superior. Por exemplo, a ordem de avaliação (e teoricamente também a duplicação) das fórmulas da planilha não importa, porque as saídas não são copiadas para as entradas até que todas as saídas tenham sido calculadas, ou seja, análogas às funções puras.

C, Java, C ++, C #, PHP e JavaScript não são particularmente declarativos. A sintaxe de Copute e a sintaxe do Python são mais declarativamente acopladas aos resultados pretendidos , ou seja, semântica sintática consistente que elimina o estranho, de modo que se possa compreender prontamente o código depois de esquecê-lo. Copute e Haskell reforçam o determinismo da semântica operacional e incentivam " não se repita " (DRY), porque eles permitem apenas o paradigma funcional puro.

---

2 Mesmo onde podemos provar a semântica de um programa, por exemplo, com a linguagem Coq, isso é limitado à semântica expressa na digitação , e a digitação nunca pode capturar toda a semântica de um programa - nem mesmo para idiomas que são Se Turing não estiver completo, por exemplo, com HTML + CSS, é possível expressar combinações inconsistentes que, portanto, têm semântica indefinida.

3 Muitas explicações afirmam incorretamente que apenas a programação imperativa tem instruções sintaticamente ordenadas. Esclarei essa confusão entre programação imperativa e programação funcional . Por exemplo, a ordem das instruções HTML não reduz a consistência de seus significados.

Edit: Postei o seguinte comentário no blog de Robert Harper:

na programação funcional ... o intervalo de variação de uma variável é do tipo

Dependendo de como distinguir a programação funcional da imperativa, o seu 'atribuível' em um programa imperativo também pode ter um tipo que limita sua variabilidade.

A única definição não confusa que atualmente aprecio para programação funcional é: a) funções como objetos e tipos de primeira classe; b) preferência pela recursão sobre loops; e / ou c) funções puras - ou seja, funções que não afetam a semântica desejada do programa quando memorizado ( _{^{portanto, a programação funcional perfeitamente pura não existe em uma semântica denotacional de uso geral devido a impactos da semântica operacional, por exemplo, alocação de memória}} ).

A propriedade idempotente de uma função pura significa que a chamada de função em suas variáveis ​​pode ser substituída por seu valor, o que geralmente não é o caso dos argumentos de um procedimento imperativo. As funções puras parecem ser declarativas para as transições de estado não compostas entre os tipos de entrada e resultado.

Mas a composição de funções puras não mantém essa consistência, porque é possível modelar um processo imperativo de efeito colateral (estado global) em uma linguagem de programação funcional pura, por exemplo, o IOMonad de Haskell e, além disso, é inteiramente impossível impedir isso. qualquer linguagem de programação funcional pura e completa de Turing.

Como escrevi em 2012, que parece o mesmo consenso de comentários em seu blog recente , essa programação declarativa é uma tentativa de capturar a noção de que a semântica pretendida nunca é opaca. Exemplos de semântica opaca são dependência da ordem, dependência da eliminação de semânticas de nível superior na camada semântica operacional (por exemplo, projeções não são conversões e genéricos reificados limitam a semântica de nível superior ) e dependência de valores variáveis ​​que não podem ser verificados (comprovado correto) pela linguagem de programação.

Assim, concluí que apenas linguagens completas não-Turing podem ser declarativas.

Assim, um atributo inequívoco e distinto de uma linguagem declarativa pode ser que sua saída pode ser comprovada como obedecendo a um conjunto enumerável de regras generativas. Por exemplo, para qualquer programa HTML específico (ignorando as diferenças nas maneiras como os intérpretes divergem) que não está com script (ou seja, não está completo com Turing), sua variabilidade de saída pode ser enumerável. Ou, mais sucintamente, um programa HTML é uma função pura de sua variabilidade. O mesmo programa de planilha é uma função pura de suas variáveis ​​de entrada.

Portanto, parece-me que as linguagens declarativas são a antítese da recursão ilimitada , ou seja, pelo segundo teorema da incompletude de Gödel, os teoremas auto-referenciais não podem ser provados.

Lesie Lamport escreveu um conto de fadas sobre como Euclides poderia ter trabalhado com os teoremas da incompletude de Gödel aplicados às provas de matemática no contexto da linguagem de programação, à congruência entre tipos e lógica (correspondência de Curry-Howard, etc.).

Programação imperativa: dizendo à “máquina” como fazer algo e, como resultado, o que você deseja que aconteça.

Programação declarativa: dizendo à “máquina” o que você gostaria que acontecesse e deixando o computador descobrir como fazê-lo.

Exemplo de imperativo

function makeWidget(options) {
    const element = document.createElement('div');
    element.style.backgroundColor = options.bgColor;
    element.style.width = options.width;
    element.style.height = options.height;
    element.textContent = options.txt;

    return element;
}

Exemplo de declarativo

function makeWidget(type, txt) {
    return new Element(type, txt);
}

Nota: A diferença não é de brevidade, complexidade ou abstração. Como afirmado, a diferença é como vs o quê .

Atualmente, novo foco: precisamos das classificações antigas?

Os aspectos Imperativo / Declarativo / Funcional eram bons no passado para classificar linguagens genéricas, mas hoje em dia todas as "linguagens grandes" (como Java, Python, Javascript etc.) têm alguma opção (normalmente estruturas ) para expressar com "outro foco" do que o principal (imperativo usual), e expressar processos paralelos, funções declarativas, lambdas, etc.

Portanto, uma boa variante dessa pergunta é "Qual aspecto é bom para classificar estruturas hoje?" ... Um aspecto importante é algo que podemos rotular como "estilo de programação" ...

Concentre-se na fusão de dados com algoritmo

Um bom exemplo para explicar. Como você pode ler sobre o jQuery na Wikipedia ,

O conjunto de recursos principais do jQuery - seleções, travessia e manipulação de elementos DOM -, ativado por seu mecanismo seletor (...), criou um novo "estilo de programação", fundindo algoritmos e estruturas de dados DOM

Portanto, o jQuery é o melhor exemplo (popular) de se concentrar em um "novo estilo de programação" , que não é apenas orientação a objetos, é " Fundir algoritmos e estruturas de dados ". O jQuery é um pouco reativo como planilhas, mas não "orientado a célula", é " orientado a nó DOM " ... Comparando os principais estilos nesse contexto:

1. Sem fusão : em todas as "grandes linguagens", em qualquer expressão Funcional / Declarativa / Imperativa, o habitual é "sem fusão" de dados e algoritmos, exceto por alguma orientação a objetos, que é uma fusão no ponto de vista estrito da estrutura algébrica .

2. Alguma fusão : todas as estratégias clássicas de fusão, hoje em dia têm alguma estrutura para usá-lo como paradigma ... fluxo de dados , programação orientada a eventos (ou linguagens específicas de domínios antigos como awk e XSLT ) ... Como a programação com planilhas modernas, elas também são exemplos de estilo de programação reativa .

3. Grande fusão : é "o estilo jQuery" ... jQuery é uma linguagem específica de domínio focada em " algoritmos de fusão e estruturas de dados DOM ".
   PS: outras "linguagens de consulta", como XQuery, SQL (com PL como opção de expressão imperativa) também são exemplos de fusão de algoritmos de dados, mas são ilhas , sem fusão com outros módulos do sistema ... Spring , ao usar find()-variants e cláusulas de especificação , é outro bom exemplo de fusão.

Programação declarativa é programação expressando alguma lógica atemporal entre a entrada e a saída, por exemplo, em pseudocódigo, o exemplo a seguir seria declarativo:

def factorial(n):
  if n < 2:
    return 1
  else:
    return factorial(n-1)

output = factorial(argvec[0])

Apenas definimos um relacionamento chamado 'fatorial' aqui e definimos o relacionamento entre a saída e a entrada como esse relacionamento. Como deve ser evidente aqui, sobre qualquer linguagem estruturada permite que a programação declarativa se estenda. Uma idéia central da programação declarativa são dados imutáveis; se você atribui a uma variável, faz isso apenas uma vez e nunca mais. Outras definições mais rigorosas implicam que talvez não haja efeitos colaterais; essas linguagens são algumas vezes chamadas de 'puramente declarativas'.

O mesmo resultado em um estilo imperativo seria:

a = 1
b = argvec[0]
while(b < 2):
  a * b--

output = a

Neste exemplo, não expressamos nenhuma relação lógica estática atemporal entre a entrada e a saída, alteramos os endereços de memória manualmente até que um deles mantivesse o resultado desejado. Deveria ser evidente que todas as linguagens permitem que a semântica declarativa se estenda, mas nem todas permitem, algumas linguagens declarativas 'puramente' permitem efeitos colaterais e mutações por completo.

Dizem que as linguagens declarativas especificam 'o que deve ser feito', em oposição a 'como fazê-lo'; acho que isso é um nome impróprio; os programas declarativos ainda especificam como é preciso obter da entrada para a saída, mas de outra maneira, o o relacionamento que você especificar deve ser efetivamente computável (termo importante, procure-o se não o souber). Outra abordagem é a programação não determinística , que realmente apenas especifica quais condições um resultado deve atender, antes que sua implementação acabe com todos os caminhos de tentativa e erro até que seja bem-sucedida.

Linguagens puramente declarativas incluem Haskell e Pure Prolog. Uma escala móvel de um para o outro seria: Pure Prolog, Haskell, OCaml, Scheme / Lisp, Python, Javascript, C--, Perl, PHP, C ++, Pascall, C, Fortran, Assembly

Algumas boas respostas aqui sobre os "tipos" mencionados.

Submeto alguns conceitos adicionais, mais "exóticos", geralmente associados à multidão de programação funcional:

• Linguagem específica de domínio ou programação DSL : criando uma nova linguagem para lidar com o problema em questão.
• Metaprogramação : quando o seu programa grava outros programas.
• Programação evolutiva : onde você constrói um sistema que se aprimora continuamente ou gera sucessivamente melhores gerações de subprogramas.

Eu acho que sua taxonomia está incorreta. Existem dois tipos opostos: imperativo e declarativo. Funcional é apenas um subtipo de declarativo. BTW, a Wikipedia afirma o mesmo fato.

Em poucas palavras, quanto mais um estilo de programação enfatiza O que (fazer) abstraindo os detalhes de Como (fazer), mais esse estilo é considerado declarativo. O oposto é verdadeiro para o imperativo. A programação funcional está associada ao estilo declarativo.