Chapter 16 : Datalog - a precursor to Prolog

In previous chapters we have generally started by giving a ready made grammar and possibly a complete manual. Then it became possible to base the implementation on the grammar. In this chapter we shall develop the grammar in several stages.

input  ::=
        [   '+'
          | '-'
          | atom { ':-' formula } '.'
          | formula '.' ]
formula  ::=  atom { ',' formula }
atom  ::=  predicate { '(' parameterlist ')' }
parameterlist  ::=  parameter { ',' parameterlist }
parameter  ::=  variable | name
predicate  ::=  l-identifier
name  ::=  l-identifier
variable  ::=  u-identifier
l-identifier  ::=  lowercase letter,
                   followed by further letters, digits and underscores
u-identifier  ::=  uppercase letter,
                   followed by further letters, digits and underscores

Note that formulas and parameterlists are very similar in structure, and that both are recursively defined in terms of themselves. There is no other recursion at all. If these two recursive definitions could be replaced by non-recursive ones, then the entire grammar would be free of recursion. Then any occurrences of non-terminals could be replaced by their definition, and the entire language would be defined by just the first production as expanded.

To remove the recursion in the definitions of formulas and parameterlists we can replace the option braces by repetition brackets:

formula  ::=  atom [ ',' atom ]
parameterlist  ::=  parameter  [ ',' parameter ]

If in the production for formula we now replace the two occurrences of atom by its definition we end up with:

formula  ::=  predicate { '(' parameterlist ') }
              [ ',' predicate { '(' parameterlist ')' } ]

If we replace the two occurrences of parameterlist by its definition, then we end up with something even longer. Clearly what is needed is a way of defining formulas as consisting of one or more atomic formulas separated by commas. A construct that does this is what is used by Digital Equipment Corporation in their help files.

The dieresis … is to mean: the previous item. Inside repetition brackets it means: while there is a comma, repeat the previous item. Note that the dieresis can always be eliminated by replacing it textually with the previous item. Hence no new expressive power is introduced by the device.

The two productions can now be written like this:

formula  ::=  atom [',' ...]
parameterlist  ::=  parameter  [',' ...]

The device has the welcome effect that diereses are not non-terminals and hence are not to be expanded.

We can now expand:

parameterlist  ::=  (name | variable) [',' ...]
atom  ::=  predicate { '(' (name | variable) [',' ...] ')' }
formula  ::=  ( predicate { '(' (name | variable) [',' ...] ')' } )
              [',' ...]

The entire grammar can now be written as:

input  ::=
  [   '+'
    | '-'
    | { l-identifier { '(' (l-identifier | u-identifier) [',' ...] ')' } }
      { ':-' }
      { ( l-identifier { '(' (l-identifier | u-identifier) [',' ...] ')' } )
        [',' ...] }
      '.' ]

The first long line handles the formal parameters, the second long line handles the actual parameters. Having the lists of parameters defined twice seems wasteful, but it is a small price to pay for the elimination of other non-terminals. More importantly, having them defined twice is in fact helpful for the compiler, because code generation is very different for the formal and actual parameters.

The entire grammar is non-recursive — in the right hand side of the production the only symbols are the terminals +, -, (, ), =,=, :-, . and the two non-terminals l-identifier and u-identifier. Even these two non-terminals could be eliminated in favour of terminals.

However, the terminals and these two non-terminals will of course be handled by the scanner, so there is no point in doing this elimination. There are no other non-terminals, apart from the start symbol, so the entire language is defined by the regular expression which is the right hand side of one production. Hence it will be possible to write a parser which does not use any parsing procedures apart from the main program.

This is the first time that we have had a non-trivial language which could be defined by a regular expression. We shall use the opportunity to write the entire parser in the main program. You should judge yourself whether you like this monolithic style or whether you prefer to have the parser broken up into several procedures.

The scanner has to recognise several single character symbols, the two character symbol turnstyle :-, and user introduced identifiers. The latter may be predicates or names, both starting with a lowercase letter, or they may be variables, starting with an uppercase letter. It is best if the scanner distinguishes identifiers beginning with a lowercase letter and those beginning with an uppercase letter. It does not look up or enter into a symbol table.

The scanner also has to recognise Prolog- or C-style comments enclosed in /* and */. These are similar to the Pascal-style comments enclosed in (* and *) that were first used in Mondef. The difference is that (, the first character of a Pascal-style comment, when not followed by a *, was also a legal character in Mondef, and, incidentally, in Pascal. By contrast, the slash /, the first character of a Prolog- or C-style comment, when not followed by a *, is not a legal symbol in Datalog, though it is in Prolog and in C.

Since no parsing procedures are needed, the entire parser is contained in the body of the main program. It consists of a big REPEAT loop which examines the current input symbol. If it is one of the mode switches + or -, then the mode is set accordingly, for entering or for questioning. Otherwise, depending on the mode, either a fact or rule is to be entered, or a question is to be put.

In entering mode, a clause is expected. The first symbol has to be a lowercase identifier, a predicate, and this may be followed by a parenthesised list of parameters separated by commas. If a left parenthesis is seen, then the list of parameters is handled by a REPEAT loop which exits when the next symbol is not a comma. Each parameter has to be a lowercase identifier, a constant, or an uppercase identifier, a variable. The next symbol should then be a right parenthesis. After the predicate and perhaps the parameters, a turnstyle may occur; if not, a period is expected.

Whatever the mode, if the next symbol is not a period, a formula is expected, consisting of one or more atomic formulas separated by the and-commas. This is again handled by a REPEAT loop which on each pass handles one atomic formula, the loop exits when the next symbol is not an identifier. Each atomic formula is handled like the head of a clause described in the previous paragraph: it has to consist of a lowercase identifier possibly followed by a list of parameters handled by a further REPEAT loop.

Whatever the mode, the next symbol must be the terminating period.

This completes the parser. Note that the comma-separated lists of formal and actual parameters are treated slightly differently from the comma-separated lists of atomic formulas. Following the method of stepwise refinement used in previous chapters, we now expand on this basic skeleton. If you are writing the program yourself, you are strongly urged to write the parser up to this point.

During parsing two kinds of identifiers will be encountered by the scanner: those beginning with a lowercase letter and those beginning with an uppercase letter.

The parser accepts lowercase identifiers in predicate position to the left of the turnstyle and to the right of the turnstyle. Such predicates have to be recognised later, so they are entered into a table of predicates. That table will also contain pointers to the code of each defined predicate.

The parser accepts lowercase identifiers and uppercase identifiers in parameter positions, either as formal parameters to the left of the turnstyle, or as actual parameters to the right of the turnstyle.

Variables play a vital role for identification of values inside a clause or a query, but their meaning is local to that clause or query. Therefore they can be entered into a shortlived and quite small table as they are encountered; the same space can be used for all clauses and queries. On the other hand, lowercase identifiers in parameter positions are names, they retain their meaning outside any clause in which they occur, so they have to be entered into a permanent table.

It follows that there are three separate tables: for predicates, for variables and for names. They are not managed by the scanner but each by an independent function which handles lookup and, if necessary, new entries. All three tables will be consulted for code generation to determine various addresses.

There is one more major ARRAY, the code that is generated by the now familiar procedure generate.

If an error occurs, then all three tables should be restored to what they were at the start of the clause or query in which the error happened. In particular, any recent entries to any of the tables should be removed, by resetting the indices to what they were at the start of the clause or query containing the error. The resetting is done by the error procedure, but it has to know what to reset the indices to. So, the main program must set several save-variables to the values of the variables to be saved. Setting these save-variables has to occur just before a clause or query is being read. Actually only the indices of the table of predicates and the table of names have to be reset by the error procedure, since the table of variables will be reset automatically for the reading of the next clause or query. And while on the topic of resetting, in order not to waste space in the code that has been generated, the index to the last code should be reset after any error or after reading and processing a query.

The utility routines then are:

• a procedure getch,
• a procedure getsym,
• three functions for looking up the three tables,
• a procedure for generating code,
• and procedures for reporting normal syntactic errors and fatal errors when tables overflow.

The only other procedure is the interpreter, the theorem prover itself.

Several of our previous programs have used backtracking; they had a global variable to which changes were made and later undone. For Datalog the global variable will have to be a stack containing values of parameters of predicates being called. These parameters are either constants or variables. The latter may at any one moment be undefined or defined. When they become defined, they do not become constants, but they become pointers to constants or pointers to pointers to constants, or pointers to pointers to pointers to constants, and so on.

If two variables directly or indirectly point to a third which directly or indirectly points to a fourth, then if one of the first two becomes defined then so does the other and the third and the fourth. This is the way logical variables have to behave. In the stack any value that is a pointer value always points down into the lower part of the stack.

Now consider a query with several variables:

p(X,Y), q(Y,Z).

The three variables X, Y and Z have to become variables at the bottom of the stack, so that their values may be printed out later.

For the call to p, X and Y have to be pushed as parameters — the stack now contains five elements. Then p can be called, possibly repeatedly. Any one of these calls may give values to the parameters X and Y by giving values to the X and Y at the bottom of the stack.

Each of the calls that succeeds is followed by pushing Y and Z as parameters for q — the stack now contains seven elements — and possibly repeated calls to q. Each successful call to q is followed by the three bottom values X, Y and Z being printed. With this much by way of preview of the interpreter, we now take a first look at code generation.

It will be best if we begin with the code generation for the formal and the actual parameters.

We now look at the remaining details of the code generation, in particular the computation of those addresses that were left out in the discussion of the generation of opcodes for parameters. In the parser there are seven places where code for parameters is generated, two for formals and five for actuals.

For formal parameters the instructions generated are either match-name or match-var instructions. When they are being executed by the interpreter, the corresponding actual parameters will already be on the stack, and hence the addresses used by the two match instructions will be relative to the top of the stack. During code generation for formal parameters, though, it will not be known how many formal parameters there are until the closing parenthesis is reached. By that time the code for the formals has been generated, except that for the match-name instruction the b-field has to be fixed and for the match-var instruction both the a-field and the b-field have to be fixed.

A simple method of doing this is to keep a count of the actual parameters, by a variable which is initialised to zero when the predicate is seen and which is incremented for each formal parameter encountered. Then, when the code is generated for the formals, this count is used in the b-field of both instructions. For variables on their first occurrence the count is saved in the the table of variables, and for later occurrences the saved count is used for the a-field when code is generated for the repeated variable. When the closing right parenthesis is reached, the addresses in the b-fields and for the match-var instructions also the addresses in the a-field are exactly the inverses of what they should be: for example for b-fields of the last of n parameters it will have the value n when it should be zero. So, when the closing parenthesis is reached and hence the total number of formals is known, these addresses must be fixed up. The instructions to be fixed are all those following the or-node that had been generated for the predicate. The fix up consists of replacing the value in the field by the difference between the count of formals and the value in the field. Of course for the match-name instruction the a-field is not changed because this contains the absolute address of the name in the table of names.

For actual parameters all instructions generated will be push instructions. Again it will be necessary to keep a count of the actuals, initialised to zero and incremented for each actual parameter encountered in a formula which is the body of a rule. Syntactically formulas that are queries are treated just like formulas that are bodies, but it so happens that for queries the count of actuals is not needed.

There are five different places where push instructions are generated for actual parameters. The first occurs when an actual parameter is a name. In that case the a-field is the address of the name in the table of names; that address is delivered by the function that looks up and possibly updates the table of names. In all other cases the actual parameter is a variable, the function for looking up and possibly updating the table of variables is called and the address returned is saved in a variable. What to do with that address depends on several factors.

In questioning mode what has to be pushed is the absolute address of the variable, but being an address into the stack it has to be a negative value. So the a-field is the negative of the address, and since it is absolute and not relative to the top of stack, the b-field is set to zero.

In entering mode, the address of the variable may be less than or equal to the number of formal parameters, or it may be greater. If the address is equal to or less than the number of formals, then the variable has already occurred as a formal parameter. The required address has to be relative to what at run time is the top of stack, and this is indicated by setting the b-field to one. The required absolute value of this relative address is increased by each of the actual parameters there are so far, because each of them increases the distance from the top of stack. The required value is also increased by each intervening formal parameter, and the number of these is given by the difference between the number of formals and the address of the variable. Adding the number of actuals and this difference gives the required value for the a-field.

If the address of the variable is greater than the number of formal parameters, then the variable is local and understood to be existentially quantified. The table of variables already records whether this is the first or a later occurrence. If it is the first occurrence, then the interpreter has to push a new undefined item, so the push instruction has a zero in the a-field. Since this value has to be pushed absolutely, the b-field is also set to zero. It is also necessary to record in the table of variables the ordinal number of this first occurrence.

If there are further occurrences of this local variable, then the interpreter will have to be able to access this initially undefined item. What has to be pushed is a relative address, so the b-field is one. The required value of the relative address is the difference between the ordinal number of the first occurrence as recorded in the table and the current occurrence of this actual parameter.

Write a manual for Datalog. You may assume that your reader is familiar with some version of Prolog or with some other form of logic programming language. But you should not make any too specific assumptions. You may also assume that your reader is familiar with the syntax of some form of predicate logic. However, you should be aware that understanding the semantics of predicate logic is of no help in understanding the semantics of Datalog (or of Prolog).

Write a tutorial for Datalog. You should assume that your reader does not know about Prolog and does not know about predicate logic. Readers who have studied your tutorial should then be able to understand your manual.

Why wasn't sequential execution used in the program for expanding regular expressions in Chapter~9, or in the program for semantic tableaux in Chapter~10, or the program for context free grammars in Chapter~11 or the program for monadic logic in Chapter~15?

In Datalog all disjunctions are implicit, by way of multiple definitions of predicates. For any disjunctive query it is necessary to first give a multiple definition of some suitable and possibly contrived predicate, and this can be annoying. Implement explicit disjunctions for queries, and with no extra effort, for bodies of clauses. As usual, conjunctions should have greater precedence than disjunctions; so you should also allow parentheses for overriding precedences. Most of the parser will have to be rewritten completely, because the grammar will now be recursive.

As implemented, Datalog will spew forth all solutions it can find. Implementations of Prolog stop after each group of solutions and then let the user indicate whether more are wanted. Implement such a feature in Datalog.

In Datalog and in Prolog there is no need for an identity relation. Different names always denote different individuals anyhow, so an identity statement using different names will always be false. Identity statements using a name and a variable are not needed because one can use the name instead of the variable throughout the clause or query. Identity statements using two different variables are not needed because one can use the same variable throughout the clause or query.

On the other hand, it is sometimes useful to have negated identity statements, or non-identity statements, but only if one of the two terms used is a variable. For example, one might want to define X and Y to be full siblings if they have two parents P1 and P2 in common. It is essential that P1 and P2 are not identical. Using, say # as the symbol for non-identity, the new atomic formula P1 # P2 would be part of the definition for full siblinghood:

full_siblings(X,Y)  :-
    parent(P1,X), parent(P1,Y), parent(P2,X), parent(P2,Y), P1 # P2.

(One might argue that another condition is needed: X # Y.) Implement non-identity in Datalog. Beware of some difficulties: how would you handle the case where the non-identity statement is not the last conjunct in the definition, but the third, or the second, or even the first?

Prolog and Datalog will produce the same solution of variable bindings several times if there are several ways of proving them. For some applications this is exactly what is wanted, for some it is at least acceptable, but for others it is positively annoying. Modify the program so that each solution is printed only once. A similar exercise was already suggested for semantic tableaux in Chapter~10. When a solution is found, it will be necessary to check whether the same solution has been found before — if not it has to be added. The solutions can be printed as soon as they have been found and been seen to be new, or they can be printed at the end when the entire set of solutions has been completed. Duplicate solutions are eliminated in the Logical Data Language LDL described in Naqvi and Tsur (1989).

Implement either a Prolog-like form of negation or a full classical negation. For the latter, a negated atom not p(X) with a variable as the actual parameter should return all those bindings of X for which the un-negated atom fails. The bindings are obtained by searching the table of names of individuals, hence it is assumed that there are no individuals other than those mentioned in one way or another. Note that such a classical form of negation only makes sense in Datalog, though not in full Prolog.

Study the cut primitive of Prolog and implement it in Datalog.

Design a different syntax for Datalog, closer to natural language, somewhat along the lines of Mondef in Chapter~15. A new syntax for facts and rules and questions should be designed. Then rewrite Datalog for this new syntax.

• Maier and Warren (1988) describe a sequence of implementations of Proplog, Datalog and Prolog.
• Kluzniak and Szpakiwics (1985) is said to contain a diskette with the Pascal source of a simple Prolog system.
• Campbell (1984) contains many articles on the implementation of full Prolog.
• Spivey (1996) contains an introduction to Prolog and the design and final source code for a Prolog implementation in Pascal.