Quais são as principais diferenças técnicas entre o Prolog e o miniKanren, com relação à programação lógica? [fechadas]

Quando eu quero ler sobre programação lógica, eu sempre tropeço em duas maneiras "principais" de fazer isso hoje em dia:

• miniKanren , uma minilíngua introduzida no The Reasoned Schemer e popular no momento devido ao core.logic .
• Prolog , a primeira "grande" linguagem de programação lógica.

O que me interessa agora: quais são as principais diferenças técnicas entre os dois? Eles são muito parecidos em abordagem e implementação, ou eles adotam abordagens completamente diferentes para a programação lógica? De quais ramos da matemática eles vêm e quais são os fundamentos teóricos?

Primeiro, permita-me elogiá-lo pelo seu excelente ícone pw0n1e.

Esta é uma pergunta difícil de responder, principalmente porque existem muitas variantes do miniKanren e do Prolog. O miniKanren e o Prolog são realmente famílias de idiomas, o que dificulta a comparação de seus recursos ou mesmo como eles são usados ​​na prática. Por causa disso, tome tudo o que vou dizer com cautela: se eu disser que o Prolog usa a pesquisa aprofundada, saiba que muitas implementações do Prolog suportam outras estratégias de pesquisa e que estratégias de pesquisa alternativas também podem ser codificadas na meta nível de intérprete. Ainda assim, o miniKanren e o Prolog têm diferentes filosofias de design e fazem trocas diferentes.

Prolog é uma das duas linguagens clássicas para programação simbólica de inteligência artificial (a outra linguagem clássica é Lisp). O Prolog é excelente na implementação de sistemas simbólicos baseados em regras nos quais o conhecimento declarativo é codificado na lógica de primeira ordem. A linguagem é otimizada para expressividade e eficiência para esses tipos de aplicativos, às vezes à custa da pureza lógica. Por exemplo, por padrão, o Prolog não usa a "verificação de ocorrência" na unificação. Do ponto de vista matemático / lógico, esta versão da unificação está incorreta. No entanto, a verificação da ocorrência é cara e, na maioria dos casos, a falta da verificação da ocorrência não é um problema. Essa é uma decisão de design muito pragmática, assim como o uso da pesquisa profunda da Prolog e o corte (!) para controlar o retorno. Tenho certeza de que essas decisões foram absolutamente necessárias quando executadas no hardware da década de 1970, e hoje são muito úteis ao trabalhar com grandes problemas e ao lidar com grandes espaços de pesquisa (geralmente infinitos!).

O Prolog suporta muitos recursos "extra-lógicos" ou "não-lógicos", incluindo corte asserte retractprojeção de variáveis ​​para aritmética usandois, e assim por diante. Muitos desses recursos facilitam a expressão do fluxo de controle complexo e a manipulação do banco de dados global de fatos da Prolog. Uma característica muito interessante do Prolog é que o próprio código Prolog é armazenado no banco de dados global de fatos e pode ser consultado em tempo de execução. Isso torna trivial escrever meta-intérpretes que modifiquem o comportamento do código Prolog sob interpretação. Por exemplo, é possível codificar a pesquisa pela primeira vez no Prolog usando um meta-interpretador que altera a ordem da pesquisa. Essa é uma técnica extremamente poderosa que não é bem conhecida fora do mundo Prolog. 'The Art of Prolog' descreve essa técnica em detalhes.

Foi feito um tremendo esforço para melhorar as implementações do Prolog, a maioria baseada na Warren Abstract Machine (WAM). O WAM usa um modelo de efeito colateral no qual os valores são atribuídos destrutivamente a variáveis ​​lógicas, com esses efeitos colaterais sendo desfeitos após o retorno. Muitos recursos podem ser adicionados ao Prolog estendendo as instruções do WAM. Uma desvantagem dessa abordagem é que os documentos de implementação do Prolog podem ser difíceis de ler sem uma sólida compreensão do WAM. Por outro lado, o implementador do Prolog possui um modelo comum para discutir questões de implementação. Houve muita pesquisa paralela ao Prolog, culminando no Andorra Prolog nos anos 90. Pelo menos algumas dessas idéias permanecem no Ciao Prolog. (O Ciao Prolog está cheio de idéias interessantes, muitas das quais vão muito além do padrão do Prolog.)

O Prolog possui uma bela sintaxe no estilo "correspondência de padrão", que resulta em programas muito sucintos. Prologadores amam sua sintaxe, assim como Lispers amam suas expressões s. O Prolog também possui uma grande biblioteca de predicados padrão. Devido a toda a engenharia necessária para acelerar o WAM, existem implementações Prolog muito capazes e maduras. Como resultado, muitos sistemas grandes baseados em conhecimento foram escritos inteiramente no Prolog.

O miniKanren foi projetado como uma linguagem de programação lógica mínima, com uma implementação pequena, facilmente compreensível e facilmente hackável. O miniKanren foi originalmente incorporado ao Scheme e foi portado para dezenas de outros idiomas de host na última década. A implementação mais popular do miniKanren é 'core.logic' no Clojure, que agora possui muitas extensões do tipo Prolog e várias otimizações. Recentemente, o núcleo da implementação do miniKanren foi simplificado ainda mais, resultando em um minúsculo "micro kernel" chamado "microKanren". O miniKanren pode então ser implementado sobre esse núcleo microKanren. Transportar microKanren ou miniKanren para um novo idioma host tornou-se um exercício padrão para programadores que aprendem miniKanren. Como um resultado,

As implementações padrão do miniKanren e microKanren não contêm mutações ou outros efeitos colaterais, com uma única exceção: algumas versões do miniKanren usam igualdade de ponteiros para comparação de variáveis ​​lógicas. Considero isso um "efeito benigno", embora muitas implementações evitem mesmo esse efeito passando um contador pela implementação. Também não há banco de dados de fatos global. A filosofia de implementação do miniKanren é inspirada na programação funcional: mutações e efeitos devem ser evitados e todas as construções de linguagem devem respeitar o escopo lexical. Se você observar atentamente a implementação, poderá até encontrar algumas mônadas. A implementação da pesquisa é baseada na combinação e manipulação de fluxos preguiçosos, mais uma vez sem o uso de mutações. Essas opções de implementação levam a compromissos muito diferentes dos do Prolog. No Prolog, a pesquisa variável é tempo constante, mas o retorno requer efeitos colaterais desfavoráveis. No miniKanren, a pesquisa de variáveis ​​é mais cara, mas o retorno é "gratuito". De fato, não há retorno no miniKanren, devido à maneira como os fluxos são tratados.

Um aspecto interessante da implementação do miniKanren é que o código é inerentemente seguro para threads e --- pelo menos em teoria --- trivialmente paralelamente agradável. Obviamente, paralelizar o código sem torná-lo mais lento não é trivial, pois cada segmento ou processo deve receber trabalho suficiente para compensar a sobrecarga da paralelização. Ainda assim, essa é uma área de implementação do miniKanren que, espero, receba mais atenção e experimentação.

O miniKanren usa a verificação de ocorrência para unificação e usa uma pesquisa intercalada completa em vez da pesquisa aprofundada. A pesquisa intercalada usa mais memória do que a pesquisa em profundidade, mas pode encontrar respostas em alguns casos em que a pesquisa em profundidade divergirá / fará um loop para sempre. miniKanren faz suportar alguns operadores extra-lógicas --- conda, condue project, por exemplo. condae condupode ser usado para simular o corte do Prolog e projectpode ser usado para obter o valor associado a uma variável lógica.

A presença de conda, condueproject--- e a capacidade de modificar facilmente a estratégia de pesquisa --- permitem que os programadores usem o miniKanren como uma linguagem semelhante ao Prolog incorporada. Isso é especialmente verdadeiro para usuários do 'core.logic' do Clojure, que inclui muitas extensões semelhantes ao Prolog. Esse uso "pragmático" do miniKanren parece ser responsável pela maior parte do uso do miniKanren na indústria. Os programadores que desejam adicionar um sistema de raciocínio baseado em conhecimento a um aplicativo existente escrito em Clojure ou Python ou JavaScript geralmente não estão interessados ​​em reescrever todo o aplicativo no Prolog. A incorporação de uma pequena linguagem de programação lógica no Clojure ou Python é muito mais atraente. Uma implementação de Prolog incorporada funcionaria tão bem para esse propósito, presumivelmente.

Além do uso do miniKanren como uma linguagem de programação lógica pragmática incorporada, similar ao espírito do Prolog, o miniKanren está sendo usado para pesquisas em programação "relacional". Ou seja, ao escrever programas que se comportam como relações matemáticas em vez de funções matemáticas. Por exemplo, em Esquema, a appendfunção pode anexar duas listas, retornando uma nova lista: a chamada da função (append '(a b c) '(d e))retorna a lista (a b c d e). Podemos, no entanto, também tratar appendcomo uma relação de três lugares e não como uma função de dois argumentos. A chamada (appendo '(a b c) '(d e) Z)associaria a variável lógica Zà lista (a b c d e). É claro que as coisas ficam mais interessantes quando colocamos variáveis ​​lógicas em outras posições. A chamada se (appendo X '(d e) '(a b c d e))associa Xa (a b c), enquanto a chamada(appendo X Y '(a b c d e))associados Xe Ycom pares de listas que, quando anexados, são iguais a (a b c d e). Por exemplo X= (a b)e Y= (c d e)são um desses pares de valores. Nós também pode escrever (appendo X Y Z), o que irá produzir um número infinito de triplos de listas X, Ye Ztal que acrescentar Xa Yproduz Z.

Esta versão relacional do appendpode ser facilmente expressa no Prolog e, de fato, é mostrada em muitos tutoriais do Prolog. Na prática, os programas Prolog mais complexos tendem a usar pelo menos alguns recursos extra-lógicos, como corte, que inibem a capacidade de tratar o programa resultante como uma relação. Por outro lado, o miniKanren foi projetado explicitamente para suportar esse estilo de programação relacional. Versões mais recentes do miniKanren tem suporte para resolução de restrição simbólica ( symbolo, numbero,absento, restrições de desigualdade, programação lógica nominal) para facilitar a criação de programas não triviais como relações. Na prática, nunca uso nenhum dos recursos extra-lógicos do miniKanren e escrevo todos os meus programas miniKanren como relações. Os programas relacionais mais interessantes são os intérpretes relacionais de um subconjunto do esquema. Esses intérpretes têm muitas habilidades interessantes, como gerar um milhão de programas do Scheme que são avaliados na lista (I love you)ou gerar trivialmente quines (programas que se avaliam).

O miniKanren faz várias compensações para ativar esse estilo relacional de programação, que são muito diferentes das compensações que a Prolog faz. Com o tempo, o miniKanren adicionou mais restrições simbólicas, tornando-se realmente uma linguagem de programação de lógica de restrição orientada simbolicamente. Em muitos casos, essas restrições simbólicas tornam prático evitar o uso de operadores extra-lógicos como condue project. Em outros casos, essas restrições simbólicas não são suficientes. Um melhor suporte para restrições simbólicas é uma área ativa da pesquisa miniKanren, juntamente com a questão mais ampla de como escrever programas maiores e mais complexos como relações.

Em resumo, o miniKanren e o Prolog têm recursos, implementações e usos interessantes, e acho que vale a pena aprender as idéias dos dois idiomas. Também existem outras linguagens de programação lógica muito interessantes, como Mercury, Curry e Gödel, cada uma com sua própria opinião sobre a programação lógica.

Terminarei com alguns recursos miniKanren:

O site principal do miniKanren: http://minikanren.org/

Uma entrevista que dei sobre programação relacional e miniKanren, incluindo uma comparação com o Prolog: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

Felicidades,

--Vai

Resposta provisória:

AFAIK, "The Reasoned Schemer" introduziu a programação lógica básica na sintaxe do esquema y e no estilo de programação funcional, adicionando, em particular, os objetivos constantes "#u" (falha) e "#s" (suceeed) aos valores booleanos "#t "e" #f ". Ele usou a mesma abordagem para a programação lógica que o Prolog: Unificação e pesquisa de retorno. Vou ver se tenho algum tempo para recuperar esse livro da minha estante no fim de semana. O ramo da matemática é uma lógica de primeira ordem de forma restrita, neste caso as cláusulas de Horn e a resolução Unfication. Veja: Lógica Computacional: Memórias do Passado e Desafios para o Futuro, de John Alan Robinson; e Os primeiros anos de programação lógica de Robert Kowalski, para um começo frio.