In the last articleI started my story about the hybrid language modeling component. It is a set of concepts-objects connected by logical relationships. I managed to talk about the main ways of defining concepts, inheritance and defining the relationship between them. The reasons that prompted me to start designing a hybrid language, and its features, can be found in my previous publications on this topic. Links to them can be found at the end of this article.
And now I propose to plunge into some of the nuances of logic programming. Since the language of the modeling component has a declarative logical form, it will be necessary to solve such problems as defining the semantics of the negation operator, introducing elements of higher-order logic and adding the ability to work with logical variables. To do this, you will have to deal with such theoretical issues as the assumption of the openness / closedness of the world, denial as a refusal, stable model semantics and well-founded semantics. And also with how the possibilities of higher-order logic are implemented in other logical programming languages.
Let's start with boolean variables
In most logic programming languages, variables are used as a symbolic designation (placeholder) of arbitrary statements. They occur at the positions of the arguments of predicates and connect the predicates with each other. For example, in the following rule of the Prolog language, variables play the role of objects X and Y , connected by relations: brother , parent , male and inequality:
brothers(X,Y) :- parent(Z,X), parent(Z,Y), male(X), male(Y), X\=Y.
In the modeling component, the role of term arguments is primarily played by concept attributes:
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
They can be accessed by name directly, as in SQL. Although the proposed syntax looks more cumbersome compared to Prolog, in the case of a large number of attributes, this option will be more convenient, since it emphasizes the structure of the object.
But in some cases it would still be convenient to declare a boolean variable that would not be included in the attributes of any of the concepts, but at the same time be used in the expression of relations. For example, if a subexpression has a complex form, then you can break it down into its component parts by linking them to boolean variables. Also, if a subexpression is used several times, then you can declare it only once by associating it with a variable. And in the future, use a variable instead of an expression. In order to distinguish boolean variables from concept attributes and computation component variables, let us decide that Boolean variable names must begin with the $ symbol .
As an example, we can analyze the concept that specifies the belonging of a point to a ring, which is described by the external and internal radii. The distance from a point to the center of a ring can be calculated once, linked to a variable, and compared to the radii:
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))
At the same time, this distance itself has an auxiliary role and will not be part of the concept.
Negation.
Now let's look at a more complex issue - the implementation of the negation operator within the modeling component. Logic programming systems usually include, in addition to the boolean negation operator, the negation rule as a refusal. It allows you to print not p if the derivation of p fails . In different systems of knowledge representation, both the meaning and the algorithm of the rule of inference of negation may differ.
First, it is necessary to answer the question about the nature of the knowledge system in terms of its completeness. In systems that adhere to the "open world assumption" , the knowledge base is considered incomplete, so statements that are missing from it are considered unknown. Not p assertion can be output only if the knowledge base explicitly stores the statement that pfalse. Such denial is called strong. Missing statements are considered unknown, not false. An example of a knowledge system using such an assumption is the Semantic WEB. It is a publicly accessible global semantic network formed on the basis of the World Wide Web. The information in it is, by definition, incomplete - it is not fully digitized and translated into a machine-readable form, it is distributed among different nodes and is constantly being supplemented. For example, if in Wikipedia, in an article about Tim Berners-Lee, the creator of the World Wide Web and the author of the concept of the Semantic Web, nothing is said about his culinary preferences, then this does not mean that he does not have them, the article is simply incomplete.
The opposite assumption is "the assumption that the world is closed."... It is believed that in such systems the knowledge base is complete, and the missing statements in it are taken as non-existent or false. Most databases follow this assumption. If the database does not have a record about a transaction or about a user, then we are sure that such a transaction did not exist, and the user is not registered in the system (at least the whole logic of the system is based on the fact that they do not exist).
Complete knowledge bases have their advantages. First, there is no need to encode unknown information - two-valued logic (true, false) is sufficient instead of three-valued (true, false, unknown). Second, you can combine the Boolean negation operator and the check of the derivability of a statement from the knowledge base into one negation operator as a refusal(negation as failure). It will return true not only if the statement that the statement is false is stored, but also if there is no information about it in the knowledge base at all. For example, the
rule
p <— not q
will infer that q is false (since there is no statement that it is true) and p is true.
Unfortunately, the semantics of denial as rejection are not as obvious and more complex than they seem. In different logical programming systems, its meaning has its own characteristics. For example, in the case of cyclic definitions:
p ← not q q ← not p
the classic SLDNF resolution (SLD + Negation as Failure) used in Prolog language will fail. The output of the statement p needs the output of q , and q - in p , the output procedure will fall into an infinite loop. In Prolog, such definitions are considered invalid and the knowledge base is considered inconsistent.
At the same time, these statements are not a problem for us. Intuitively, we understand these two rules as saying that p and qhave opposite meanings, if one of them is true, then the other is false. Therefore, it is desirable that the operator of negation as a refusal be able to work with such rules, so that the constructions of logical programs are more natural and understandable for a person.
Also, consistency in the knowledge base is not always achievable. For example, sometimes rule definitions are deliberately separated from facts so that the same set of rules can be applied to different sets of facts. In this case, there is no guarantee that the rules will agree with all possible sets of facts. It is also sometimes acceptable that the rules themselves are inconsistent, for example, if they are drawn up by different experts.
The best-known campaigns, allows to formalize the logical conclusion under cyclic definitions and program inconsistencies are "Semantics sustainable» (Stable model semantics) and "reasonable semantics» (the Well-founded the semantics).
The inference rule with persistent model semantics is based on the assumption that some negation operators in a program can be ignored if they are not consistent with the rest of the program. Since there can be several such consistent subsets of the initial set of rules, there can be several solutions, respectively. For example, in the definition above, inference can start with the first rule ( p ← not q ), discard the second ( q ← not p ) and obtain the solution {p, not q} . And then do the same for the second and get {q, not p} . The overall solution will be a combined set of alternative solutions. For example, from the rules:
person(alex) alive(X) ←person(X) male(X) ←person(X) AND NOT female(X) female(X) ←person(X) AND NOT male(X)
we can display two answers: {person (alex), alive (alex), male (alex)} and {person (alex), alive (alex), female (alex)} .
Reasonable semantics starts with the same assumptions, but seeks to find one general partial solution that satisfies all alternative consensual subsets of rules. Partial solution means that the values "true" or "false" will be displayed only for a part of the facts, and the values of the rest will remain unknown. Thus, in the description of facts in the program, two-valued logic is used, and in the process of inference, three-valued. For the rules considered above, the meanings of both p and qwill be unknown. But, for example, for
p ← not q q ←not p r ← s s
we can confidently infer that r and s are true, although p and q remain unknown.
For example, from the alex example, we might infer {person (alex), alive (alex)} , while the statements male (alex) and female {alex} remain unknown.
In SQL, the Boolean Negation ( NOT ) and Derivability Check ( NOT EXISTS) are separated. These operators apply to different types of arguments: NOT inverts a boolean value, and EXISTS / NOT EXISTS checks the result of a nested query for emptiness, so it makes no sense to combine them. The semantics of the negation operators in SQL are very simple and are not designed to work with recursive or complex inconsistent queries; with a special SQL skill, the query can be sent to infinite recursion. But complex logical constructs are clearly outside the scope of traditional SQL applications, so it does not need sophisticated negation operator semantics.
Now let's try to understand the semantics of the negation operators of the modeling component of the designed hybrid language.
First, the modeling component is designed to integrate disparate data sources. They can be very varied and can be either complete or incomplete. Therefore, derivability check operators are definitely needed.
Second, the form of modeling component concepts is much closer to SQL queries than to logic programming rules. The concept also has a complex structure, so mixing in one operator of Boolean negation and checking the derivability of the concept does not make sense. Boolean negation only makes sense to apply to attributes, variables, and expression results - they can be either false or true. It is more difficult to apply it to a concept, it may consist of different attributes and it is not clear which of them should be responsible for the falsity or truth of the concept as a whole. The concept can be deduced from the initial data as a whole, and not its individual attributes. Unlike SQL, where the structure of tables is fixed, the structure of concepts can be flexible, a concept may not have the required attribute in its composition at all,therefore, you will also need to check the existence of the attribute.
Therefore, it makes sense to introduce separate operators for each type of negation listed above. The falsity of attributes can be checked using the traditional Boolean NOT operator , whether a concept contains an attribute using the built-in DEFINED function , and the result of inferring the concept from the original data using the EXISTS function . The three separate operators are more predictable, understandable, and easier to use than the complex negation-as-failure operator. If necessary, they can be combined into one operator in one way or another that makes sense for each specific case.
Third, at the moment, the modeling component is seen as a tool for creating small application-level ontologies. Its language is unlikely to need special logical expressiveness and sophisticated inference rules that can cope with recursive definitions and logical inconsistencies of the program. Therefore, the implementation of complex inference rules based on the semantics of persistent models or grounded semantics does not seem advisable, at least at this stage. Classic SLDNF resolution should be enough.
Now let's look at a few examples.
A concept can be given a negative meaning if certain of its attributes have a meaning that indicates it. Negation of attributes allows you to explicitly find such entities:
concept unfinishedTask is task t where not t.completed
The function of checking the ambiguity of an attribute will be convenient if the entities of a concept can have different structures:
concept unassignedTask is task t where not defined(t.assignedTo) or empty(t.assignedTo)
The function of checking the deducibility of a concept is irreplaceable when working with recursive definitions and hierarchical structures:
concept minimalElement is element greater where not exists(element lesser where greater.value > lesser.value)
In this example, the check for the existence of a smaller item is performed as a subquery. I plan to consider in detail the creation of nested queries in the next publication.
Elements of higher order logic
In first-order logic, variables can only match sets of objects and appear only at the positions of the arguments of predicates. In higher-order logic, they can also correspond to sets of relations and appear in the position of predicate names. In other words, first-order logic allows us to make the assertion that some relation is true for all or some of the objects. And higher order logic is to describe the relationship between relationships.
For example, we can make statements that some people are brothers, sisters, children or parents, uncles or aunts, etc .:
Brother(John, Joe). Son(John, Fred). Uncle(John, Alex).
But in order to make a relationship assertion, in first-order logic, we need to list all the statements above, combining them using the OR operation:
Ɐ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)).
Second-order logic allows you to make a statement about other statements. For example, one could directly state that the relationship between brothers, sisters, parents and children, uncles and nephews is a kinship relationship:
RelativeRel(Brother). RelativeRel(Son). RelativeRel(Uncle). ⱯX,ⱯY(ⱻR(RelativeRel(R) AND (R(X, Y) OR R(Y, X))) → Relative(X, Y)).
We argue that if for each X and Y there is a relationship R that is a relationship between RelativeRel siblings , and X and Y satisfy this relationship, then X and Y are siblings. Relationship arguments can be other relationships, and variables can be substituted for relationship names.
Third-order logic allows you to construct statements about statements about statements, and so on, higher-order logic- about statements of any nesting level. Higher-order logic is much more expressive, but also much more complex. In practice, logical programming systems support only some of its elements, which are mainly limited to the use of variables and arbitrary expressions at the positions of predicates.
In Prolog, the elements of such logic are implemented using several built-in meta-predicates, the arguments of which are other predicates. The main one is the predicate callwhich allows you to dynamically add predicates to the target list of the current rule. His first argument is treated as the goal, and the rest as its arguments. Prolog will search the knowledge base for predicates matching the first argument and add them to the current target list. An example with relatives would look like this:
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 also supports predicates findall (Template, Goal, Bag) , bagof (Template, Goal, Bag) , setof (Template, Goal, Set) , etc., which allow you to find all Goal goal solutions that match the Template template and unify (link) their list with the result Bag (or Set ). Prolog has built-in predicates current_predicate , clause, and others for finding predicates in the knowledge base. You can also manipulate predicates and their attributes in knowledge bases - add, delete and copy them.
HiLog language supports higher order logic at the syntax level. Instead of special meta-predicates, it allows arbitrary terms (such as variables) to be used directly in the position of predicate names. The rule for determining relatives will take the form:
relative(X, Y) :- relative_rel(R), (R(X, Y); R(Y, X)).
This syntax is more declarative, concise, understandable and natural compared to Prolog. At the same time, HiLog remains a syntactic variant of Prolog, since all HiLog syntactic constructs can be converted to first-order logic expressions using the call meta-predicates .
HiLog is considered to have higher order syntax but first order semantics . This means that when comparing variables that represent rules or functions, only their names are taken into account, not their implementation. There are also languages that support higher order semantics, such as λ-Prolog, which also allow the implementation of rules and functions to be involved in the inference process. But such logic and its inference algorithms are much more complicated.
Now let's move on to the higher order logic functionality of the modeling component . For most practical meta-programming tasks, Prolog and HiLog should suffice. HiLog has a more natural syntax, so it makes sense to take it as a basis. To be able to use arbitrary expressions on the positions of the names of concepts and their attributes and to distinguish them from variables, function calls and other constructions, we introduce a special operator for dynamically specifying names :
< >
It allows you to evaluate the value of an expression and use it as a concept name, alias, or attribute name, depending on the context. If this operator stands in the place of the concept name in the FROM section and the value of its expression is defined, then all concepts with the specified name will be found and a logical search is performed for them:
concept someConcept ( … ) from conceptA a, <a.conceptName> b where …
If the value of the expression is not defined, for example, the expression is a boolean variable not associated with the value , then the procedure will find all suitable concepts and associate the value of the variable with their names:
concept someConcept is <$conceptName> where …
We can say that in the context of the FROM section, the operator for specifying the name has logical semantics .
Also, the <> operator can be used and the WHERE clauses at the position of a concept alias or attribute name:
concept someConcept ( … ) from conceptA a, conceptB b where conceptB.<a.foreignKey> = a.value ...
Expressions in the WHERE clause are deterministic, that is, they do not use logical search to find unknown values for their arguments. This means that the expression conceptB. <A.foreignKey> = a.value will be evaluated only after the entities of the concept a are found , and its foreignKey and value attributes are associated with values. Therefore, we can say that in the context of the FROM clause , the name statement has functional semantics .
Let's consider some possible applications of higher order logic.
The most obvious example where higher-order logic will be convenient is the union under one name of all concepts that satisfy certain conditions. For example, having certain attributes. So the concept of point can be considered all concepts that include coordinates x and y :
concept point is <$anyConcept> a where defined(a.x) and defined(a.y)
Boolean search will bind the $ anyConcept variable with all declared concept names (except of course itself) that have coordinate attributes.
A more complex example would be to declare a general relationship that applies to many concepts. For example, a transitive parent-child relationship between concepts:
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) ))
The variable $ conceptName is used in all three concepts of parent, child, and intermediate, which means that their names must be the same.
Higher-order logic opens up possibilities for generic programming in the sense that you can create generic concepts and relationships that can be applied to many concepts that satisfy specified conditions without being tied to their specific names.
Also, dynamic name substitution will be convenient in cases where the attributes of one concept are references to the names of other concepts or their attributes, or when the source data contains not only facts, but also their structure. For example, the source data can include a description of the schemas of XML documents or tables in a database. The original data can also include additional information about the facts, for example, data types, formats or default values, validation conditions or some rules. Also, the initial data can describe a model of something, and the modeling component will be responsible for building a metamodel. Working with natural language texts also assumes that the source data will include not only statements, but also statements about statements.In all these cases, first-order logic will not be enough and a more expressive language is needed.
As a simple example, consider the case when the data includes some objects, as well as the rules for validating the attributes of these objects as a separate entity:
fact validationRule {objectName: “someObject”, attributeName: “someAttribute”, rule: function(value) {...}}
Validation results can be described by the following concept:
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>)
Higher-order logic opens up some pretty interesting possibilities for generalized and meta-programming. We were able to consider only its general idea. This area is quite complex and requires some thorough research in the future. Both from the point of view of choosing a convenient design of the language, and issues of its performance.
conclusions
In the process of working on the modeling component, I had to deal with rather specific issues of logical programming, such as working with boolean variables, the semantics of the negation operator and elements of higher order logic. If everything turned out to be quite simple with variables, then there is no single well-established approach to the implementation of the negation operator and higher-order logic, and there are several solutions that have their own characteristics, advantages and disadvantages.
I tried to choose a solution that would be easy to understand and convenient in practice. I preferred to split the monolithic negation operator as a refusal into three separate operators of Boolean negation, checking the deducibility of a concept and the existence of an attribute on an object. If necessary, these three operators can be combined to obtain the negation semantics required for each specific case. For the rule of inference negation, I decided to take the standard SLDNF resolution as a basis. While not capable of dealing with inconsistent recursive statements, it is much easier to understand and implement than more sophisticated alternatives such as persistent model semantics or reasoned semantics.
Higher order logic is needed for generalized and meta-programming. By generic programming, I mean the ability to build new concepts from a wide variety of child concepts without being tied to specific names of the latter. By meta-programming, I mean the ability to describe the structure of some concepts with the help of other concepts. I decided to take the HiLog language as a model for the higher-order logic elements of the modeling component. It has a flexible and convenient syntax that allows you to use variables in the positions of predicate names, as well as simple and clear semantics.
I plan to devote the next article to borrowing from the world of SQL: nested queries and aggregations. I will also talk about another type of concept, which does not use inference, but instead, entities are directly generated using a given function. And how you can use it to convert tables, arrays and associative arrays into object format and include them in the logical inference process (by analogy with the SQL UNNEST operation, which converts arrays to table format).
The full text in scientific style in English is available here .
Links to previous publications:
Designing a multi-paradigm programming language. Part 1 - What is it for?
We design a multi-paradigm programming language. Part 2 - Comparison of building models in PL / SQL, LINQ and GraphQL We
design a multi-paradigm programming language. Part 3 - Overview of knowledge representation languages We
design a multi-paradigm programming language. Part 4 - Basic Constructions of the Modeling Language