No último artigoComecei minha história sobre o componente de modelagem de linguagem híbrida. É um conjunto de conceitos-objetos conectados por relações lógicas. Consegui falar sobre as principais formas de definir conceitos, herança e definir a relação entre eles. Os motivos que me levaram a começar a projetar uma linguagem híbrida e seus recursos podem ser encontrados em minhas publicações anteriores sobre este tópico. Os links para eles podem ser encontrados no final deste artigo.
E agora eu proponho mergulhar em algumas das nuances da programação lógica. Como a linguagem do componente de modelagem tem uma forma lógica declarativa, será necessário resolver problemas como definir a semântica do operador de negação, introduzir elementos lógicos de ordem superior e adicionar a capacidade de trabalhar com variáveis booleanas. E para fazer isso, você terá que lidar com questões teóricas como o pressuposto da abertura / fechamento do mundo, a negação como recusa, semântica de modelo estável e semântica bem fundamentada. E também como as possibilidades da lógica de ordem superior são implementadas em outras linguagens de programação lógica.
Vamos começar com variáveis booleanas
Na maioria das linguagens de programação lógica, as variáveis são usadas como uma designação simbólica (espaço reservado) de instruções arbitrárias. Eles ocorrem nas posições dos argumentos dos predicados e conectam os predicados entre si. Por exemplo, na seguinte regra da linguagem Prolog, as variáveis desempenham o papel dos objetos X e Y , conectados por relações: irmão , pai , homem e desigualdade:
brothers(X,Y) :- parent(Z,X), parent(Z,Y), male(X), male(Y), X\=Y.
No componente de modelagem, o papel dos argumentos do termo é desempenhado principalmente por atributos de conceito:
concept brothers (person1, person2) FROM parent p1 (child = person1), parent p2 (child = person2), male(person: person1), male(person: person2) WHERE p1.parent = p2.parent AND person1 != person2
Eles podem ser acessados por nome diretamente, como no SQL. Embora a sintaxe proposta pareça mais complicada comparada ao Prolog, no caso de um grande número de atributos, esta opção será mais conveniente, pois enfatiza a estrutura do objeto.
Mas em alguns casos ainda seria conveniente declarar uma variável booleana que não seria incluída nos atributos de nenhum dos conceitos, mas ao mesmo tempo usada na expressão de relações. Por exemplo, se uma subexpressão tem uma forma complexa, você pode dividi-la em suas partes componentes, vinculando-as a variáveis booleanas. Além disso, se uma subexpressão for usada várias vezes, você poderá declará-la apenas uma vez, associando-a a uma variável. E, no futuro, use uma variável em vez de uma expressão. Para distinguir variáveis booleanas de atributos de conceito e variáveis de componentes de computação, vamos decidir que os nomes de variáveis booleanas devem começar com o símbolo $ .
A título de exemplo, podemos analisar o conceito que especifica o pertencimento de um ponto a um anel, que é descrito pelos raios externo e interno. A distância de um ponto ao centro do anel pode ser calculada uma vez, vinculada a uma variável e comparada aos raios:
relation pointInRing between point p, ring r where $dist <= r.rOuter and $dist >= r.rInner and $dist = Math.sqrt((p.x – r.x) * (p.x – r.x) + (p.y – r.y) * (p.y – r.y))
Ao mesmo tempo, essa distância em si tem um papel auxiliar e não fará parte do conceito.
Negação.
Agora, vamos examinar uma questão mais complexa - a implementação do operador de negação no componente de modelagem. Os sistemas de programação lógica geralmente incluem, além do operador de negação booleana, a regra de negação como recusa. Ele permite que você imprima not p se a derivação de p falhar . Em diferentes sistemas de representação do conhecimento, tanto o significado quanto o algoritmo da regra para a inferência de negação podem ser diferentes.
Em primeiro lugar, é necessário responder à pergunta sobre a natureza do sistema de conhecimento em termos de sua integridade. Em sistemas que aderem à "suposição de mundo aberto" , a base de conhecimento é considerada incompleta, de modo que as afirmações ausentes são consideradas desconhecidas. Não p asserção só pode ser gerado se a base de conhecimento armazenar explicitamente a declaração de que pfalso. Essa negação é chamada de forte. Declarações ausentes são consideradas desconhecidas, não falsas. Um exemplo de sistema de conhecimento que usa tal suposição é a WEB Semântica. É uma rede semântica global acessível ao público, formada com base na World Wide Web. As informações nele são, por definição, incompletas - não são totalmente digitalizadas e traduzidas em um formato legível por máquina, são distribuídas entre diferentes nós e são constantemente complementadas. Por exemplo, se na Wikipedia, em um artigo sobre Tim Berners-Lee, o criador da World Wide Web e autor do conceito de Web Semântica, nada é dito sobre suas preferências culinárias, isso não significa que ele não as tenha, o artigo está simplesmente incompleto.
A suposição oposta é "a suposição de que o mundo está fechado".... Acredita-se que, em tais sistemas, a base de conhecimento está completa e as afirmações ausentes são consideradas inexistentes ou falsas. A maioria dos bancos de dados segue essa suposição. Se o banco de dados não possui um registro sobre uma transação ou sobre um usuário, então temos certeza de que tal transação não existiu, e o usuário não está registrado no sistema (pelo menos toda a lógica do sistema é baseada no fato de que eles não existem).
Bases de conhecimento completas têm suas vantagens. Primeiro, não há necessidade de codificar informações desconhecidas - a lógica de dois valores (verdadeiro, falso) é suficiente em vez de três valores (verdadeiro, falso, desconhecido). Em segundo lugar, você pode combinar o operador booleano de negação e a verificação da derivabilidade de uma instrução da base de conhecimento em um operador de negação como uma recusa(negação como falha). Ele retornará verdadeiro não apenas se a declaração de que a declaração é falsa for armazenada, mas também se não houver nenhuma informação sobre ela na base de conhecimento. Por exemplo, a
regra
p <— not q
inferirá que q é falso (uma vez que não há afirmação de que seja verdadeiro) e p é verdadeiro.
Infelizmente, a semântica da negação como rejeição não é tão óbvia e complexa do que parece. Em diferentes sistemas de programação lógica, seu significado possui características próprias. Por exemplo, no caso de definições cíclicas:
p ← not q q ← not p
a resolução SLDNF clássica (SLD + Negação como Falha) usada na linguagem Prolog falhará. A derivação da declaração p precisa da saída de q , eq - em p , o procedimento de inferência cairá em um loop infinito. No Prolog, tais definições são consideradas inválidas e a base de conhecimento é considerada inconsistente.
Ao mesmo tempo, essas declarações não são um problema para nós. Intuitivamente, entendemos essas duas regras dizendo que p e qtêm significados opostos, se um deles for verdadeiro, então o outro é falso. Portanto, é desejável que o operador de negação como recusa seja capaz de trabalhar com tais regras para que as construções de programas lógicos sejam mais naturais e compreensíveis para uma pessoa.
Além disso, a consistência da base de conhecimento nem sempre é alcançável. Por exemplo, às vezes as definições de regra são deliberadamente separadas dos fatos para que o mesmo conjunto de regras possa ser aplicado a diferentes conjuntos de fatos. Nesse caso, não há garantia de que as regras concordarão com todos os conjuntos de fatos possíveis. Às vezes, também é aceitável que as próprias regras sejam inconsistentes, por exemplo, se forem elaboradas por especialistas diferentes.
As campanhas mais conhecidas, permitem formalizar a conclusão lógica sob as definições cíclicas e as inconsistências do programa são "Semântica sustentável» (semântica do modelo estável) e "semântica razoável» (a semântica bem fundamentada).
A regra de inferência com semântica de modelo persistente é baseada na suposição de que alguns operadores de negação em um programa podem ser ignorados se não forem consistentes com o resto do programa. Como pode haver vários subconjuntos consistentes do conjunto inicial de regras, pode haver várias soluções, respectivamente. Por exemplo, na definição acima, a inferência pode começar com a primeira regra ( p ← não q ), descarte o segundo ( q ← não p ) e obtenha a solução {p, não q} . E então faça o mesmo para o segundo e obtenha {q, não p} . A solução geral seria um conjunto combinado de soluções alternativas. Por exemplo, a partir das regras:
person(alex) alive(X) ←person(X) male(X) ←person(X) AND NOT female(X) female(X) ←person(X) AND NOT male(X)
podemos exibir duas opções de resposta: {pessoa (alex), vivo (alex), masculino (alex)} e {pessoa (alex), vivo (alex), feminino (alex)} .
A semântica razoável começa com as mesmas suposições, mas procura encontrar uma solução parcial geral que satisfaça todos os subconjuntos consensuais alternativos de regras. Solução parcial significa que os valores "verdadeiro" ou "falso" serão exibidos apenas para uma parte dos fatos e os valores do resto permanecerão desconhecidos. Assim, na descrição dos fatos no programa, a lógica de dois valores é usada e, no processo de inferência, de três valores. Para as regras consideradas acima, os significados de p e qserá desconhecido. Mas, por exemplo, para
p ← not q q ←not p r ← s s
podemos inferir com segurança que r e s são verdadeiros, embora p e q permaneçam desconhecidos.
Por exemplo, a partir do exemplo do alex, podemos inferir {pessoa (alex), vivo (alex)} , enquanto as declarações masculino (alex) e feminino {alex} permanecem desconhecidas.
No SQL, a negação booleana ( NOT ) e verificações de derivabilidade ( NOT EXISTS) são separados. Esses operadores se aplicam a diferentes tipos de argumentos: NOT inverte um valor booleano e EXISTS / NOT EXISTS verifica o resultado de uma consulta aninhada quanto ao vazio, portanto, não faz sentido combiná-los. A semântica dos operadores de negação em SQL é muito simples e não foi projetada para funcionar com consultas inconsistentes recursivas ou complexas; com uma habilidade especial de SQL, a consulta pode ser enviada para recursão infinita. Mas construções lógicas complexas estão claramente fora do escopo dos aplicativos SQL tradicionais, portanto, não precisam de semânticas sofisticadas de operador de negação.
Agora, vamos tentar entender a semântica dos operadores de negação do componente de modelagem da linguagem híbrida projetada.
Primeiro, o componente de modelagem é projetado para integrar fontes de dados díspares. Eles podem ser muito variados e podem ser completos ou incompletos. Portanto, os operadores de verificação de derivabilidade são definitivamente necessários.
Em segundo lugar, a forma de modelar conceitos de componentes está muito mais próxima das consultas SQL do que das regras de programação lógica. O conceito também tem uma estrutura complexa, portanto, misturar em um operador de negação booleana e verificar a derivabilidade do conceito não faz sentido. A negação booleana só faz sentido se aplicar a atributos, variáveis e resultados de expressão - eles podem ser falsos ou verdadeiros. É mais difícil aplicá-lo a um conceito, pode consistir em diferentes atributos e não está claro qual deles deve ser responsável pela falsidade ou verdade do conceito como um todo. O conceito pode ser derivado dos dados iniciais como um todo, e não de seus atributos individuais. Ao contrário do SQL, onde a estrutura das tabelas é fixa, a estrutura dos conceitos pode ser flexível, um conceito pode não ter o atributo necessário em sua composição,portanto, você também precisará verificar a existência do atributo.
Portanto, faz sentido introduzir operadores separados para cada tipo de negação listado acima. A falsidade dos atributos pode ser verificada usando o operador booleano NOT tradicional , se um conceito contém um atributo usando a função DEFINED embutida e o resultado de inferir o conceito dos dados originais usando a função EXISTS . Os três operadores separados são mais previsíveis, compreensíveis e fáceis de usar do que o complexo operador de negação como falha. Se necessário, eles podem ser combinados em um operador de uma forma ou de outra que faça sentido para cada caso específico.
Terceiro, no momento, o componente de modelagem é visto como uma ferramenta para criar pequenas ontologias no nível do aplicativo. É improvável que sua linguagem precise de expressividade lógica especial e regras de inferência sofisticadas que possam lidar com definições recursivas e inconsistências lógicas do programa. Portanto, a implementação de regras de inferência complexas baseadas na semântica de modelos persistentes ou na semântica fundamentada não parece apropriada, pelo menos neste estágio. A resolução SLDNF clássica deve ser suficiente.
Agora, vamos ver alguns exemplos.
Um conceito pode receber um significado negativo se alguns de seus atributos tiverem um significado que o indique. A negação de atributos permite que você encontre explicitamente essas entidades:
concept unfinishedTask is task t where not t.completed
A função de verificar a ambigüidade de um atributo será conveniente se as entidades de um conceito puderem ter estruturas diferentes:
concept unassignedTask is task t where not defined(t.assignedTo) or empty(t.assignedTo)
A função de verificar a dedutibilidade de um conceito é insubstituível quando se trabalha com definições recursivas e estruturas hierárquicas:
concept minimalElement is element greater where not exists(element lesser where greater.value > lesser.value)
Neste exemplo, a verificação da existência de um item menor é realizada como uma subconsulta. Pretendo considerar em detalhes a criação de consultas aninhadas na próxima publicação.
Elementos de lógica de ordem superior
Na lógica de primeira ordem, as variáveis só podem corresponder a conjuntos de objetos e aparecem apenas nas posições dos argumentos dos predicados. Na lógica de ordem superior, eles também podem corresponder a conjuntos de relações e aparecer na posição de nomes de predicados. Em outras palavras, a lógica de primeira ordem nos permite fazer a asserção de que alguma relação é verdadeira para todos ou alguns dos objetos. E a lógica de ordem superior é descrever a relação entre os relacionamentos.
Por exemplo, podemos fazer declarações de que algumas pessoas são irmãos, irmãs, filhos ou pais, tios ou tias, etc.:
Brother(John, Joe). Son(John, Fred). Uncle(John, Alex).
Mas para fazer uma afirmação de relacionamento, na lógica de primeira ordem, precisamos listar todas as instruções acima, combinando-as usando a operação OR:
ⱯX,ⱯY(Brother(X, Y) OR Brother(Y, X) OR Son(X, Y) OR Son(Y, X) OR Uncle(X, Y) OR Uncle(Y, X) → Relative(X, Y)).
A lógica de segunda ordem permite que você faça uma declaração sobre outras declarações. Por exemplo, pode-se afirmar diretamente que a relação entre irmãos, irmãs, pais e filhos, tios e sobrinhos é uma relação de parentesco:
RelativeRel(Brother). RelativeRel(Son). RelativeRel(Uncle). ⱯX,ⱯY(ⱻR(RelativeRel(R) AND (R(X, Y) OR R(Y, X))) → Relative(X, Y)).
Argumentamos que se para cada X e Y houver um relacionamento R que é um relacionamento entre irmãos RelativeRel , e X e Y satisfazem esse relacionamento, então X e Y são irmãos. Os argumentos de relacionamento podem ser outros relacionamentos e as variáveis podem ser substituídas por nomes de relacionamento.
A lógica de terceira ordem permite que você construa declarações sobre declarações sobre declarações e assim por diante, lógica de ordem superior- sobre declarações de qualquer nível de aninhamento. A lógica de ordem superior é muito mais expressiva, mas também muito mais complexa. Na prática, os sistemas de programação lógica suportam apenas alguns de seus elementos, que são principalmente limitados ao uso de variáveis e expressões arbitrárias nas posições de predicados.
No Prolog, os elementos de tal lógica são implementados usando vários meta-predicados embutidos, os argumentos dos quais são outros predicados. O principal é a chamada de predicado que permite adicionar predicados dinamicamente à lista de destino da regra atual. Seu primeiro argumento é tratado como a meta e o resto como seus argumentos. O Prolog irá pesquisar a base de conhecimento por predicados que combinem com o primeiro argumento e os adicionará à lista de destino atual. Um exemplo com parentes ficaria assim:
brother(john, jack). sister(mary, john). relative_rel(brother). relative_rel(sister). relative(X, Y) :- relative_rel(R), (call(R, X, Y); call(R, Y, X)).
Prolog também suporta predicados findall (Template, Goal, Bag) , bagof (Template, Goal, Bag) , setof (Template, Goal, Set) , etc., que permitem que você encontre todas as soluções de meta de objetivo que correspondam ao template Template e unifique (link) sua lista com o resultado Bolsa (ou Conjunto ). Prolog tem predicados internos current_predicate , clause e outros para localizar predicados na base de conhecimento. Você também pode manipular predicados e seus atributos em bases de conhecimento - adicione, exclua e copie-os.
A linguagem HiLog oferece suporte à lógica de ordem superior no nível de sintaxe. Em vez de meta-predicados especiais, permite que termos arbitrários (como variáveis) sejam usados diretamente na posição de nomes de predicados. A regra para determinar parentes terá a forma:
relative(X, Y) :- relative_rel(R), (R(X, Y); R(Y, X)).
Esta sintaxe é mais declarativa, concisa, compreensível e natural em comparação com Prolog. Ao mesmo tempo, HiLog permanece uma variante sintática do Prolog, uma vez que todas as construções sintáticas HiLog podem ser transformadas em expressões lógicas de primeira ordem usando os metapredicados de chamada .
HiLog é considerado ter uma sintaxe de ordem superior , mas semântica de primeira ordem . Isso significa que, ao comparar variáveis que representam regras ou funções, apenas seus nomes são levados em consideração, não sua implementação. Existem também linguagens que suportam semântica de ordem superior, como λ-Prolog, que também permitem a implementação de regras e funções a serem envolvidas no processo de inferência. Mas essa lógica e seus algoritmos de inferência são muito mais complicados.
Agora, vamos prosseguir para a funcionalidade de lógica de ordem superior do componente de modelagem . Para a maioria das tarefas práticas de metaprogramação, Prolog e HiLog devem ser suficientes. HiLog tem uma sintaxe mais natural, por isso faz sentido tomá-la como base. Para poder usar expressões arbitrárias nas posições dos nomes dos conceitos e seus atributos e para distingui-los de variáveis, chamadas de função e outras construções, introduzimos um operador especial para nomes dinâmicos :
< >
Ele permite que você avalie o valor de uma expressão e use-o como um nome de conceito, alias ou nome de atributo, dependendo do contexto. Se este operador estiver no lugar do nome do conceito na seção FROM e o valor de sua expressão for definido, todos os conceitos com o nome especificado serão encontrados e uma pesquisa lógica será realizada para eles:
concept someConcept ( … ) from conceptA a, <a.conceptName> b where …
Se o valor da expressão não for definido, por exemplo, a expressão é uma variável booleana não associada ao valor , então o procedimento encontrará todos os conceitos adequados e associará o valor da variável com seus nomes:
concept someConcept is <$conceptName> where …
Podemos dizer que no contexto da seção FROM , o operador para especificar um nome tem semântica lógica .
Além disso, o operador <> pode ser usado e as cláusulas WHERE na posição de um alias de conceito ou nome de atributo:
concept someConcept ( … ) from conceptA a, conceptB b where conceptB.<a.foreignKey> = a.value ...
As expressões da cláusula WHERE são determinísticas, ou seja, não usam a pesquisa lógica para encontrar valores desconhecidos para seus argumentos. Isso significa que a expressão conceptB. <A.foreignKey> = a.value será avaliada apenas depois que as entidades do conceito a forem encontradas e seus atributos ForeignKey e value forem associados a valores. Portanto, podemos dizer que, no contexto da cláusula FROM , a instrução name possui semântica funcional .
Vamos considerar algumas aplicações possíveis da lógica de ordem superior.
O exemplo mais óbvio em que a lógica de ordem superior será conveniente é a união sob um nome de todos os conceitos que satisfazem certas condições. Por exemplo, ter certos atributos. Portanto, o conceito de ponto pode ser considerado todos os conceitos que incluem as coordenadas x e y :
concept point is <$anyConcept> a where defined(a.x) and defined(a.y)
A pesquisa booleana vinculará a variável $ anyConcept com todos os nomes de conceitos declarados (exceto, é claro, ela própria) que possuem atributos de coordenadas.
Um exemplo mais complexo seria declarar uma relação geral que se aplica a muitos conceitos. Por exemplo, uma relação transitiva pai-filho entre conceitos:
relation ParentRel between <$conceptName> parent, <$conceptName> child where defined(parent.id) and defined(child.parent) and ( parent.id = child.parent or exists( <$conceptName> intermediate where intermediate.parent = parent.id and ParentRel(intermediate, child) ))
A variável $ conceptName é usada em todos os três conceitos de pai, filho e intermediário, o que significa que seus nomes devem ser iguais.
A lógica de ordem superior abre possibilidades para a programação genérica, no sentido de que você pode criar conceitos e relacionamentos genéricos que podem ser aplicados a muitos conceitos que satisfazem condições especificadas sem estar vinculado a seus nomes específicos.
Além disso, a substituição dinâmica de nomes será conveniente nos casos em que os atributos de um conceito são referências aos nomes de outros conceitos ou seus atributos, ou quando os dados de origem contêm não apenas fatos, mas também sua estrutura. Por exemplo, os dados de origem podem incluir uma descrição dos esquemas de documentos ou tabelas XML em um banco de dados. Os dados originais também podem incluir informações adicionais sobre os fatos, por exemplo, tipos de dados, formatos ou valores padrão, condições de validação ou algumas regras. Além disso, os dados iniciais podem descrever o modelo de algo, e o componente de modelagem será responsável por construir o metamodelo. Trabalhar com textos em linguagem natural também pressupõe que os dados de origem incluirão não apenas declarações, mas também declarações sobre declarações.Em todos esses casos, a lógica de primeira ordem não será suficiente e uma linguagem mais expressiva é necessária.
Como um exemplo simples, considere o caso em que os dados incluem alguns objetos, bem como as regras para validar os atributos desses objetos como uma entidade separada:
fact validationRule {objectName: “someObject”, attributeName: “someAttribute”, rule: function(value) {...}}
Os resultados da validação podem ser descritos pelo seguinte conceito:
concept validationRuleCheck ( objectName = r.objectName, attributeName = r.attrName, result = r.rule(o.<r.attrName>) ) from validationRule r, <r.objectName> o where defined(o.<r.attrName>)
A lógica de ordem superior abre algumas possibilidades bastante interessantes para generalização e metaprogramação. Pudemos considerar apenas sua ideia geral. Esta área é bastante complexa e requer algumas pesquisas aprofundadas no futuro. Tanto do ponto de vista da escolha de um design conveniente da linguagem, quanto das questões de seu desempenho.
conclusões
No processo de trabalho no componente de modelagem, tive que lidar com questões bastante específicas de programação lógica, como trabalhar com variáveis booleanas, a semântica do operador de negação e elementos de lógica de ordem superior. Se tudo acabou sendo bastante simples com variáveis, então não existe uma abordagem única bem estabelecida para a implementação do operador de negação e da lógica de ordem superior, e existem várias soluções que têm suas próprias características, vantagens e desvantagens.
Tentei escolher uma solução que fosse fácil de entender e conveniente na prática. Preferi dividir o operador monolítico de negação como uma recusa em três operadores separados de negação booleana, verificando a dedutibilidade de um conceito e a existência de um atributo em um objeto. Se necessário, esses três operadores podem ser combinados para obter a semântica de negação necessária para cada caso específico. Para a regra de negação de inferência, decidi tomar a resolução SLDNF padrão como base. Embora não seja capaz de lidar com instruções recursivas inconsistentes, é muito mais fácil de entender e implementar do que alternativas mais sofisticadas, como semântica de modelo persistente ou semântica racional.
A lógica de ordem superior é necessária para generalizada e meta-programação. Por programação genérica, quero dizer a capacidade de construir novos conceitos a partir de uma ampla variedade de conceitos filhos sem estar vinculado a nomes específicos dos últimos. Por metaprogramação, entendo a capacidade de descrever a estrutura de alguns conceitos com a ajuda de outros conceitos. Decidi tomar a linguagem HiLog como modelo para os elementos lógicos de ordem superior do componente de modelagem. Possui uma sintaxe flexível e conveniente que permite o uso de variáveis nas posições de nomes de predicados, bem como uma semântica simples e clara.
O próximo artigo que pretendo dedicar a tomar emprestado do mundo do SQL: consultas aninhadas e agregações. Também vou falar sobre outro tipo de conceito que não usa inferência, mas, em vez disso, entidades são geradas diretamente usando uma determinada função. E como pode ser usado para converter tabelas, arrays e arrays associativos em formato de objeto e incluí-los no processo de inferência lógica (por analogia com a operação SQL UNNEST, que converte arrays em formato de tabela).
O texto completo em estilo científico em inglês está disponível aqui .
Links para publicações anteriores:
Projetando uma linguagem de programação multiparadigma. Parte 1 - Para que serve?
Nós projetamos uma linguagem de programação multiparadigma. Parte 2 - Comparação de modelos de construção em PL / SQL, LINQ e GraphQL Nós
projetamos uma linguagem de programação multiparadigma. Parte 3 - Visão geral das linguagens de representação do conhecimento Nós
projetamos uma linguagem de programação multiparadigma. Parte 4 - Construções básicas da linguagem de modelagem