O sonho da programação declarativa [fechado]

Por que o sonho da programação declarativa não foi realizado? Quais são alguns obstáculos concretos no caminho? Para um exemplo simples, por que não posso dizer

sort(A) is defined by sort(A) in perm(A) && asc(sort(A))

e automaticamente obtém um algoritmo de classificação. permsignifica permutações e ascsignifica ascender.

Existem algumas respostas muito boas. Vou tentar contribuir para a discussão.

Sobre o tema da programação lógica declarativa em Prolog, há o grande livro "The Craft of Prolog", de Richard O'Keefe . Trata-se de escrever programas eficientes usando uma linguagem de programação que permite escrever programas muito ineficientes. Neste livro, ao discutir as implementações eficientes de vários algoritmos (no capítulo "Métodos de programação"), o autor adota a seguinte abordagem:

• defina o problema em inglês
• escreva uma solução funcional que seja o mais declarativa possível; normalmente, isso significa exatamente o que você tem na sua pergunta, corrija o Prolog
• a partir daí, tome medidas para refinar a implementação para torná-la mais rápida

A observação mais esclarecedora (para mim) que pude fazer enquanto trabalhava no caminho:

Sim, a versão final da implementação é muito mais eficiente que a especificação "declarativa" com a qual o autor começou. Ainda é muito declarativo, sucinto e fácil de entender. O que aconteceu no meio é que a solução final captura propriedades do problema ao qual a solução inicial estava alheia.

Em outras palavras, ao implementar uma solução, usamos o máximo de nosso conhecimento sobre o problema possível. Comparar:

Encontre uma permutação de uma lista de forma que todos os elementos estejam em ordem crescente

para:

Mesclar duas listas classificadas resultará em uma lista classificada. Como pode haver sublistas que já estão classificadas, use-as como ponto de partida, em vez de sublistas de comprimento 1.

Um pequeno aparte: uma definição como a que você forneceu é atraente porque é muito geral. No entanto, não posso escapar da sensação de que ela propositalmente ignora o fato de que permutações são, bem, um problema combinatório. Isso é algo que já sabemos ! Isso não é uma crítica, apenas uma observação.

Quanto à verdadeira questão: como avançar? Bem, uma maneira é fornecer o máximo de conhecimento sobre o problema que estamos declarando ao computador.

A melhor tentativa que conheço para realmente resolver o problema é apresentada nos livros de co-autoria de Alexander Stepanov, "Elements of Programming" e "From Mathematics to Generic Programming" . Infelizmente, não estou preparado para resumir (ou mesmo entender completamente) tudo nesses livros. No entanto, a abordagem adotada para definir algoritmos de biblioteca e estruturas de dados eficientes (ou mesmo ótimos), sob a condição de que todas as propriedades relevantes da entrada sejam conhecidas antecipadamente. O resultado final é:

• Cada transformação bem definida é um refinamento das restrições que já existem (as propriedades conhecidas);
• Deixamos o computador decidir qual transformação é ideal com base nas restrições existentes.

Quanto ao porquê ainda não aconteceu, bem, a ciência da computação é um campo muito jovem, e ainda estamos lidando com a verdadeira apreciação da novidade da maior parte dele.

PS

Para dar uma idéia do que quero dizer com "refinar a implementação": considere, por exemplo, o problema fácil de obter o último elemento de uma lista, no Prolog. A solução declarativa canônica é dizer:

last(List, Last) :-
    append(_, [Last], List).

Aqui, o significado declarativo de append/3é:

List1AndList2é a concatenação List1eList2

Como no segundo argumento append/3, temos uma lista com apenas um elemento e o primeiro argumento é ignorado (o sublinhado), obtemos uma divisão da lista original, que descarta a frente da lista ( List1no contexto de append/3) e exige que o verso ( List2no contexto de append/3) é de fato uma lista com apenas um elemento: portanto, é o último elemento.

A implementação real fornecida pelo SWI-Prolog , no entanto, diz:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

Isso ainda é muito declarativo. Leia de cima para baixo, diz:

O último elemento de uma lista só faz sentido para uma lista de pelo menos um elemento. O último elemento para um par de cauda e a cabeça de uma lista é: a cabeça, quando a cauda está vazia, ou o último da cauda não vazia.

O motivo pelo qual essa implementação é fornecida é solucionar as questões práticas que envolvem o modelo de execução do Prolog. Idealmente, não deve fazer diferença qual implementação é usada. Da mesma forma, poderíamos ter dito:

last(List, Last) :-
    reverse(List, [Last|_]).

O último elemento de uma lista é o primeiro elemento da lista invertida.

Se você deseja obter o preenchimento de discussões inconclusivas sobre o que é bom, o Prolog declarativo, basta passar por algumas das perguntas e respostas na tag Prolog no Stack Overflow .

Idiomas lógicos já fazem isso. Você pode definir a classificação da mesma forma que está fazendo.

O principal problema é o desempenho. Os computadores podem ser ótimos em calcular muitas coisas, mas são inerentemente burros. Toda decisão "inteligente" que um computador pode tomar foi programada por um programador. E essa decisão geralmente é descrita não pela aparência do resultado final, mas por como atingir, passo a passo, esse resultado final.

Imagine a história de um golem . Se você tentar dar a ele um comando abstrato, na melhor das hipóteses, ele fará isso de maneira ineficiente e, na pior das hipóteses, se machucará, você ou outra pessoa. Mas se você descrever o que deseja com o máximo de detalhes possível, terá a garantia de que a tarefa será concluída com eficácia e eficiência.

O trabalho do programador é decidir qual nível de abstração usar. Para o aplicativo que você está criando, você vai subir de nível e descrevê-lo de maneira abstrata e diminuir o desempenho ou ficar baixo e sujo, gastar 10x mais tempo com ele, mas obter um algoritmo 1000x mais eficiente?

Além do excelente argumento de Euphoric , eu gostaria de acrescentar que já estamos usando linguagens declarativas em muitos lugares onde elas funcionam bem, ou seja, descrevendo o estado que provavelmente não muda ou solicitando algo para o qual o computador realmente pode gerar código eficiente sozinho:

• O HTML declara qual é o conteúdo de uma página da web.

• O CSS declara como devem ser os vários tipos de elementos em uma página da web.

• Todo banco de dados relacional possui uma linguagem de definição de dados que declara qual é a estrutura do banco de dados.

• O SQL está muito mais próximo de declarativo do que imperativo, já que você diz o que deseja ver e o planejador de consultas do banco de dados descobre como realmente fazer isso acontecer.

• Alguém poderia argumentar que a maioria dos arquivos de configuração (.vimrc, .profile, .bashrc, .gitconfig) está usando uma linguagem específica de domínio que é amplamente declarativa

Abstrações estão vazando

Você pode implementar um sistema declarativo em que declara o que deseja, e o compilador ou interpretador descobre uma ordem de execução. O benefício teórico é que ele libera você de pensar no 'como' e não precisa detalhar essa implementação. No entanto, na prática para computação de uso geral, você ainda precisa pensar sobre o 'como' e escrever todos os tipos de truques, mantendo em mente como isso será implementado, pois, caso contrário, o compilador pode (e geralmente escolherá) uma implementação que será muito, muito, muito lento (por exemplo, n! operações onde n seria suficiente).

No seu exemplo em particular, você obterá um algoritmo de classificação A - isso não significa que você obterá um bom ou até um pouco utilizável. Sua definição, se implementada literalmente (como provavelmente seria um compilador), resulta em http://en.wikipedia.org/wiki/Bogosort, que não pode ser usado em conjuntos de dados maiores - é tecnicamente correto, mas precisa de uma eternidade para classificar mil números .

Para alguns domínios limitados, você pode escrever sistemas que quase sempre se saem bem em descobrir uma boa implementação, por exemplo, SQL. Para computação de uso geral que não funciona particularmente bem - você pode escrever sistemas, digamos, em Prolog, mas precisa visualizar como exatamente suas declarações serão convertidas em uma ordem de execução imperativa no final e que perde muito do declarativo esperado benefícios de programação.

A decidibilidade computacional é a razão mais importante pela qual a programação declarativa não se mostrou tão fácil quanto parece.

Muitos problemas que são relativamente fáceis de declarar provaram ser indecidíveis ou têm complexidade de NP completa para resolver. Isso geralmente ocorre quando levamos em consideração classes e classificações negativas, contabilidade e recursão.

Eu gostaria de explicar isso com alguns domínios bem conhecidos.

A decisão sobre qual classe CSS usar precisa de conhecimento e consideração de todas as regras CSS. Adicionar novas regras pode invalidar todas as outras decisões. Classes negativas de CSS não são intencionalmente adicionadas à linguagem, devido a problemas de NP-completos, mas a falta de classes negativas complica as decisões de design de CSS.

Dentro de um otimizador de consultas (SQL), existe o problema incômodo de decidir em qual ordem ingressar, quais índices usar e qual memória alocar para quais resultados temporários. Esse é um problema NP-completo conhecido e complica o design do banco de dados e a formulação de consultas. Para formulá-lo de maneira diferente: ao projetar um banco de dados ou uma consulta, o designer precisa conhecer as ações e a ordem das ações que o otimizador de consultas provavelmente executará. Um engenheiro experiente precisa ter conhecimento das heurísticas usadas pelos principais fornecedores de banco de dados.

Os arquivos de configuração são declarativos, mas é difícil declarar certas configurações. Por exemplo, para configurar corretamente os recursos, é necessário levar em consideração a versão, implantação (e histórico de implantação), possíveis substituições manuais e possíveis conflitos com outras configurações. Validar corretamente uma configuração pode se tornar um problema NP-completo.

O resultado é que essas complicações pegam os iniciantes de surpresa, quebram a 'beleza' da programação declarativa e fazem com que alguns engenheiros procurem outras soluções. A migração de engenheiros inexperientes do SQL para o NoSQL pode ter sido desencadeada pelas complexidades subjacentes dos bancos de dados relacionais.

Temos uma diferença na declaratividade das linguagens de programação que é bem utilizada na verificação da lógica digital.

Normalmente, a lógica digital é descrita no nível de transferência de registro (RTL), onde é definido o nível lógico dos sinais entre os registros. Para verificar se estamos adicionando cada vez mais propriedades definidas de maneira mais abstrata e declarativa.

Um dos subconjuntos de idiomas / idiomas mais declarativos é chamado PSL para Property Specification Language. Ao testar um modelo RTL de um multiplicador no qual, por exemplo, todas as operações lógicas de troca e adição de múltiplos ciclos de clock precisam ser especificadas; você pode escrever uma propriedade da maneira de assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles. A descrição da PSL pode então ser verificada junto com a RTL em uma simulação, ou a PSL pode ser formalmente comprovada como válida para a descrição da RTL.

O modelo PSL mais declarativo obriga a descrever o mesmo comportamento que a descrição da RTL, mas de uma maneira suficientemente diferente que pode ser verificada automaticamente na RTL para verificar se eles concordam.

Principalmente o problema é como você modela os dados; e programação declarativa não está ajudando aqui. Em linguagens imperativas, você já possui muitas bibliotecas que fazem muitas coisas para você, portanto, você só precisa saber como chamar. De uma maneira particular, pode-se considerar essa programação declarativa (provavelmente o melhor exemplo disso é a API Stream no Java 8 ). Com isso, a abstração já está resolvida e a programação declarativa não é necessária.

Além disso, como foi dito, as linguagens de programação lógica já fazem exatamente o que você deseja. Pode-se dizer que o problema é desempenho, mas com o hardware e as pesquisas atuais nessa área, é possível melhorar as coisas para estar pronto para o uso em produção; na verdade, o Prolog é usado para coisas de IA, mas acredito apenas na academia.

Note-se que se aplica a linguagens de programação de uso geral. Para idiomas específicos do domínio, os idiomas declarativos são muito melhores; SQL provavelmente é o melhor exemplo.

Seria algo parecido com isto .. {(qualquer que seja => leia um arquivo e chame um url) | chamar uma url e ler um arquivo} No entanto, essas são ações a serem executadas e o estado do sistema muda como resultado, mas isso não é óbvio a partir da fonte.

Declarativos podem descrever uma máquina de estados finitos e suas transições. O FSM é como o oposto de declarativos sem ações, mesmo que a única ação seja alterar o estado para o próximo estado.

A vantagem de usar esse método é que transições e ações podem ser especificadas por predicados que se aplicam a várias transições, em vez de apenas uma.

Eu sei que isso parece um pouco estranho, mas em 2008 eu escrevi um gerador de programa que usa esse método, e o C ++ gerado é de 2 a 15 vezes mais que a fonte. Agora tenho mais de 75.000 linhas de C ++ a partir de 20.000 linhas de entrada. Duas coisas vão com isso: consistência e integridade.

Consistência: Não há dois predicados que possam ser verdadeiros ao mesmo tempo, que podem implicar ações inconsistentes, como x = 8 ex = 9, nem diferentes estados seguintes.

Completude: a lógica para cada transição de estado é especificada. Pode ser difícil verificar se há sistemas com N subestados, com> 2 ** N estados, mas existem métodos combinatórios interessantes que podem verificar tudo. Em 1962, escrevi a fase 1 de um tipo de sistema para as máquinas 7070, usando esse tipo de geração de código condicional e depuração combinatória. Das 8.000 linhas do tipo, o número de bugs desde o dia do primeiro lançamento para sempre foi zero!

A segunda fase do tipo, 12.000 linhas, teve mais de 60 erros nos primeiros dois meses. Há muito mais a dizer sobre isso, mas funciona. Se os fabricantes de automóveis usassem esse método para verificar o firmware, não veríamos as falhas que vemos agora.

Nem tudo pode ser representado de maneira declarativa.

Freqüentemente, você deseja controlar explicitamente o fluxo de execução

Por exemplo, após o pseudocódigo: if whatever read a file call an URL else call an URL write a file como você o representaria declarativamente?

Claro, provavelmente existem algumas maneiras exóticas de fazer isso. Como mônadas . Mas estes geralmente são mais pesados, complicados e muito menos intuitivos do que a parte processual.

Tudo se resume ao fato de que "interagir" com seu ambiente / sistema não é declarativo. Tudo relacionado a E / S é processual por essência. Você precisa dizer exatamente quando e o que deve acontecer e em que ordem.

Declarativo é ótimo para tudo que está puramente relacionado à computação. Como uma função gigante, você coloca X e obtém Y. Isso é ótimo. Um exemplo disso é HTML, a entrada é texto, a saída é o que você vê no seu navegador.