foundations of computational agents
Datalog requires a name, using a constant, for every individual about which the system reasons. Often it is simpler to identify an individual in terms of its components, rather than requiring a separate constant for each individual.
In many domains, you want to be able to refer to a time as an individual. You may want to say that some course is held at 11:30 a.m. You do not want a separate constant for each possible time, although this is possible. It is better to define times in terms of, say, the number of hours past midnight and the number of minutes past the hour. Similarly, you may want to reason with facts about particular dates. You cannot give a constant for each date, as there are infinitely many possible dates. It is easier to define a date in terms of the year, the month, and the day.
Using a constant to name each individual means that the knowledge base can only represent a finite number of individuals, and the number of individuals is fixed when the knowledge base is built. However, you may want to reason about a potentially infinite set of individuals.
Suppose you want to build a system that takes questions in English and answers them by consulting an online database. In this case, each sentence is an individual. You do not want to have to give each sentence its own name, because there are too many English sentences to name them all. It may be better to name the words and then to specify a sentence in terms of the sequence of words in the sentence. This approach may be more practical because there are far fewer words to name than sentences, and each word has its own natural name. You may also want to specify the words in terms of the letters in the word or in terms of their constituent parts.
You may want to reason about lists of students. For example, you may be required to derive the average mark of a class of students. A list of students is an individual that has properties, such as its length and its seventh element. Although it may be possible to name each list, it is very inconvenient to do so. It is much better to have a way to describe lists in terms of their elements.
Function symbols allow you to describe individuals indirectly. Rather than using a constant to describe an individual, an individual is described in terms of other individuals.
Syntactically a function symbol is a word starting with a lower-case letter. We extend the definition of a term so that a term is either a variable, a constant, or of the form , where is a function symbol and each is a term. Apart from extending the definition of terms, the language stays the same.
Terms only appear within predicate symbols. You do not write clauses that imply terms. You may, however, write clauses that include atoms that use function symbols.
The semantics of Datalog must be expanded to reflect the new syntax. The definition of is extended so that also assigns to each n-ary function symbol a function from into . A constant can be seen as a 0-ary function symbol (i.e., one with no arguments). Thus, specifies which individual is denoted by each ground term.
Suppose you want to define dates, such as 20 July 1969, which is the date the first time a human was on the moon. You can use the function symbol (common era) so that denotes a date with year , month and day . For example, may denote 20 July 1969. Similarly, you can define the symbol to denote the date before the common era.
The only way to use the function symbol is to write clauses that define relations using the function symbol. There is no notion of defining the function; dates are not in a computer any more than people are.
To use function symbols, you can write clauses that are quantified over the arguments of the function symbol. For example, Figure 13.6 defines the relation that is true if date is before date in a day.
% is true if date is before date
% is true if month is the th month of the year.
This assumes the predicate “” represents the relation “less than” between integers. This could be represented in terms of clauses, but is often predefined, as it is in Prolog. The months are represented by constants that consist of the first three letters of the month.
A knowledge base consisting of clauses with function symbols can compute any computable function. Thus, a knowledge base can be interpreted as a program, called a logic program. Logic programs are Turing complete; they can compute any function computable on a digital computer.
This expansion of the language has a major impact. With just one function symbol and one constant, the language contains infinitely many ground terms and infinitely many ground atoms. The infinite number of terms can be used to describe an infinite number of individuals.
Function symbols are used to build data structures, as in the following example.
A tree is a useful data structure. You could use a tree to build a syntactic representation of a sentence for a natural language processing system. You could decide that a labeled tree is either of the form or of the form . Thus, is a function from a name, a left tree, and a right tree into a tree. The function symbol denotes a function from the label of a leaf node into a tree.
The relation is true if label is the label of a leaf in tree . It can be defined by
This is an example of a structural recursive program. The rules cover all of the cases for each of the structures representing trees.
The relation , which is true if label is the label of an interior node of tree , can be defined by
A list is an ordered sequence of elements. You can reason about lists using just function symbols and constants, without the notion of a list being predefined in the language. A list is either the empty list or an element followed by a list. You can invent a constant to denote the empty list. Suppose you use the constant to denote the empty list. You can choose a function symbol, say , with the intended interpretation that it denotes a list with first element and rest of the list . The list containing the elements , , would then be represented as
To use lists, one must write predicates that do something with them. For example, the relation that is true when , , and are lists, such that contains the elements of followed by the elements of , can be defined recursively by
There is nothing special about or ; we could have just as well used and .