14.7 Going Further in Prolog

14.7.1 Program Control in Prolog: A Binary Tree Example

The following set of facts describes a binary tree (lines 2–3). A path predicate is also included that defines a path between two vertices, with two rules, to be either an edge from X to Y (line 6) or a path from X to Y (line 7) through some intermediate vertex Z such that there is an edge from X to Z and a path from Z to Y:

Notice that the comma in the body (i.e., right-hand side) of the rule on line 7 represents conjunction. Likewise, the :- in that rule represents implication. Thus, the rule path(X,Y) :- edge(X,Z), path(Z,Y) is the Prolog equivalent of the Horn clause path(X, Y) ⊂ edge(X, Z)∧ path(Z, Y). The user can then query the program by expressing goals to determine whether the goal is true or to find all instantiations of variables that make the goal true. For instance, the goal path(b,c) asks if there exists a path between vertices b and c:

To prove this goal, Prolog uses resolution, which involves unification. When the goal path(b,c) is given, Prolog runs its resolution algorithm with the following steps:

During resolution, the term(s) in the body of the unified rule become subgoal(s). Consider the goal path(X,c), which returns all the values of X that satisfy this goal:

Prolog searches its database top-down and searches subgoals from left-to-right during resolution; thus, it constructs a search tree in a depth-first fashion. A top-down search of the database during resolution results in a unification between this goal and the head of the rule on line 6 and leads to the new goal: edge(X, c). A proof of this new goal leads to additional unifications and subgoals. The entire search tree illustrating the resolution process is depicted in Figure 14.2. Source nodes in Figure 14.2 denote subgoals, and target nodes represent the body of a rule whose head unifies with the subgoal in the source. Edge labels in Figure 14.2 denote the line number of the rule involved in the unification from subgoal source to body target.

Modified from Louden, K. C., and K. A. Lambert. 2011. Logic Programming. In Programming Languages: Principles and Practices. Boston, MA: Cengage Learning.

Notice that satisfaction of the goal edge(X,c) involves backtracking to find alternative solutions. In particular, the solution X=b is found first in the left subtree and the solution X=a is found second in the right subtree. A source node with more than one outgoing edge indicates backtracking (1) to find solutions because searching for a solution in a prior subtree failed (e.g., see two source nodes in the right subtree each with two outgoing edges) or (2) to find additional solutions (e.g., second outgoing edge from the root node leads to the additional solution X=a).

Consider transposing the rules on lines 6 and 7 constituting the path predicate in the example database:

A top-down search of this modified database during resolution results in a unification of the goal path(X, c) with the head of the rule on line 6 and leads to two subgoals: edge(X, Z), path(Z, c). A left-to-right pursuit of these two subgoals leads to additional unifications and subgoals, where the solution X=a is found before the solution X=b:

The entire search tree illustrating the resolution process with this modified database is illustrated in Figure 14.3. Notice the order of the terms in the body of the rule path(X,Y) :- edge(X,Z), path(Z,Y). Left recursion is avoided in this rule since Prolog uses a depth-first search strategy. Consider a transposition of the terms in the body of the rule path(X,Y) :- edge(X,Z), path(Z,Y):

The left-to-right pursuit of the subgoals leads to an infinite use of the rule path(X,Y) :- path(Z,Y), edge(X,Z) due to its left-recursive nature:

Since the database is also searched in a top-down fashion, if we reverse the two rules constituting the path predicate, the stack overflow occurs immediately and no solutions are returned:

The search tree for the goal path(X,c) illustrating the resolution process with this modified database is presented in Figure 14.4. Since Prolog terms are evaluated from left to right, Z will never be bound to a value. Thus, it is important to ensure that variables can be bound to values during resolution before they are used recursively.

Mutual recursion should also be avoided—to avert an infinite loop in the search, not a stack overflow:

In summary, the order in which both the knowledge base in a Prolog program and the subgoals are searched and proved, respectively, during resolution is significant. While the order of the terms in the antecedent of a proposition in predicate calculus is insignificant (since conjunction is a commutative operator), Prolog pursues satisfaction of the subgoals in the body of a rule in a deterministic order. Prolog searches its database top-down and searches subgoals left-to-right during resolution and, therefore, constructs a search tree in a depth-first fashion (Figures 14.2–14.4). A Prolog programmer must be aware of the order in which the system searches both the database and the subgoals, which violates a defining principle of declarative programming—that is, the programmer need only be concerned with the logic and leave the control (i.e., inference methods used to satisfy a goal) up to the system. Resolution comes free with Prolog— the programmer need neither implement it nor be concerned with the details of its implementation. The goal of logic/declarative programming is to make programming entirely an activity of specification—programmers should not have to impart control upon the program. On this basis, Prolog falls short of the ideal. The language Datalog is a subset of Prolog. Unlike Prolog, the order of the clauses in a Datalog program is insignificant and has no effect on program control.

While a depth-first search strategy for resolution is efficient, it is incomplete; that is, DFS will not always result in solutions even if solutions exist. Thus, Prolog, which uses DFS, is incomplete. In contrast, a breadth-first search strategy, while complete (i.e., BFS will always find solutions if any exist), is inefficient. However, Prolog and Datalog are both sound—neither will find incorrect solutions. Table 14.13 compares Prolog and Datalog.

Table 14.13 A Comparison of Prolog and Datalog

14.7.2 Lists and Pattern Matching in Prolog

The built-in list data structures in Prolog and the associated pattern matching are nearly identical syntactically to those in ML/Haskell (Table 14.14). However, ML/Haskell, unlike Prolog, support currying and curried functions and a powerful and clean type and module system for creating abstract data types. As a result, ML and Haskell are used in AI for applications where Prolog (or Lisp) may have once been the only programming languages considered.

Table 14.14 Example List Patterns in Prolog Vis-à-Vis the Equivalent List Patterns in Haskell

Notice the declarative nature of these predicates. Also, be aware that if we desire to include data in a Prolog program beginning with an uppercase letter, we must quote the entire string (lines 3, 5–10, and 22); otherwise, it will be treated as a variable. Similarly, if we desire to use a variable name beginning with a lowercase letter, we must preface the name with an underscore (_) (line 13). Consider the following the transcript of an interactive session with this database:

Notice the use of pattern matching and pattern-directed invocation with lists in the queries on lines 67, 81, 96, and 103 (akin to their use in ML and Haskell in Sections B.8.3 and C.9.3, respectively, in the online ML and Haskell appendices). Moreover, notice the nature of some of the queries. For instance, the query on line 10 called a cross-product or Cartesian product. A relation is a subset of the Cartesian product of two or more sets. For instance, if A = {1, 2, 3} and B = {a, b}, then arelation R ⊆ A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}. The query on line 27 is also a Cartesian product, but one in which the pairs with duplicate components are pruned from the resulting relation.

14.7.3 List Predicates in Prolog

Consider the following list predicates using some of these list patterns:

Notice the declarative nature of these predicates as well as the use of pattern-directed invocation (akin to its use in ML and Haskell in Sections B.8.3 and C.9.3, respectively, in the online ML and Haskell appendices). The second fact (line 4) of the islist predicate indicates that a non-empty list consists of a head and a tail, but uses an underscore (_), with the same semantics as in ML/Haskell, to indicate that the contents of the head and tail are not relevant. The cons predicate accepts a head and a tail and puts them together in the third list argument. The cons predicate is an example of using an additional argument to simulate another return value. However, the fact cons(H,T,[H,T]) is just a declaration—we need not think of it as a function. For instance, we can pursue the following goal to determine the components necessary to construct the list [1,2,3]:

Notice also that the islist and cons facts can be replaced with the rules islist([_|T]) :- islist(T). and cons(H,T,L) :- L = [H|T]., respectively, without altering the semantics of the program. The member1 predicate declares that an element of a list is either in the head position (line 9) or a member of the tail (line 10):

14.7.4 Primitive Nature of append

The Prolog append/3 predicate succeeds when its third list argument is the result of appending its first two list arguments. While append is built into Prolog, for purposes of instruction we define it as append1:

Notice that the fact on line 2 in the definition of the append1/2 predicate is superfluous since the rule on line 3 recurses through the first list only. The append predicate is a primitive construct that can be utilized in the definition of additional list manipulation predicates:

We redefine the member1 predicate using append1 (line 2). The revised predicate requires only one rule and declares that E is a element of L if any list can be appended to any list with E as the head resulting in list L:

The sublist predicate (line 5) is defined similarly using append1. The reverse predicate declares that the reverse of an empty list is the empty list (line 8). The rule (line 9) declares that the reverse of a list [H|T] is the reverse of list T— the tail—appended to the list [H] containing only the head H. Again, notice the declarative style in which these predicates are defined. We use lists to define graphs and a series of graph predicates in Section 14.7.8. However, before doing so, we discuss arithmetic predicates and the nature of negation in Prolog since those graph predicates involve those two concepts.

14.7.5 Tracing the Resolution Process

Consider the following Prolog program:

To illustrate the assistance that the trace/0 predicate provides, consider determining the vertices along the path from vertex a to b:

This trace is produced incrementally as the user presses the ăenterą key after each line of the trace to proceed one step deeper into the proof process.

14.7.6 Arithmetic in Prolog

Since comparison operators (e.g., < and >) in other programming languages are predicates (i.e., they return true or false), such predicates are generally used in Prolog in the same manner as they are used in other languages (i.e., using infix notation). The assignment operator in Prolog—in the capacity that an assignment operator can exist in a declarative style of programming—is the is predicate in Prolog:

The binding is held only during the satisfaction of the goal that produced the instantiation/binding (lines 1–2). It is lost after the goal is satisfied (lines 4–5). The following are the mathematical Horn clauses in Section 14.5.3 represented in Prolog syntax for Horn clauses:

The factorial predicate binds its second parameter F to the factorial of the integer represented by its first parameter N:

14.7.7 Negation as Failure in Prolog

The built-in +/1 (not) predicate in Prolog is not a logical not operator (i.e., ), so we must exercise care when using it. The goal +(G) succeeds if goal G cannot be proved, not if goal G is false. Thus, + is referred to as the not provable operator. Thus, the use of +/1 can produce counter-intuitive results:

Assume only the fact mother (mary) exists in the database. The predicate +(mother (M)) is asserting that “there are no mothers.” The response to the query on line 8 (i.e., false) is indicating that “there is a mother,” and not indicating that “there are no mothers.” In attempting to satisfy the goal on line 10, Prolog starts with the innermost term and succeeds with M = mary. It then proceeds outward to the next term. Once a term becomes false, the instantiation is released. Thus, on line 11, we do not see a substitution for X, which proves the goal on line 10, but we are only given true. Consider the following goals:

Again, false is returned on line 2 without presenting a binding for M, which was released. Notice that the goals on lines 4 and 7 are the same—only the order of the subgoals is transposed. While the validity of the goal in logic is not dependent on the order of the subgoals, the order in which those subgoals are pursued is significant in Prolog. On line 5, we see that Prolog instantiated M to mary to prove the goal on line 4. However, the proof of the goal on line 7 fails at the first subgoal without binding M to mary.

14.7.8 Graphs

We can model graphs in Prolog using a list whose first element is a list of vertices and whose second element is a list of directed edges, where each edge is a list of two elements—the source and target of the edge. Using this list representation of a graph, a sample graph is [[a,b,c,d], [[a,b], [b,c], [c,d], [d,b]]]. Using the append/2 and member/2 predicates (and others not defined here, such as noduplicateedges/1 and makeset/2—see Programming Exercises 14.7.15 and 14.7.16, respectively), we can define the following graph predicates:

The graph predicate (lines 1–3) tests whether a given list represents a valid graph by checking if there are no duplicate edges (line 2) and confirming that the defined edges do not use vertices that are not included in the vertex set (line 3). The flatten/2 and subset/2 predicates (line 3) are built into SWI-Prolog. The vertex predicate (line 5) accepts a graph and a vertex; it returns true if the graph is valid and the vertex is a member of that graph’s vertex set, and false otherwise. Similarly, the edge predicate (line 7) takes a graph and an edge; it returns true if the graph is valid and the edge is a member of that graph’s edge set, and false otherwise. The following are example goals:

These predicates serve as building blocks from which we can construct more graph predicates. For instance, we can check if one graph is a subgraph of another one:

The following are subgraph goals :

We can also check whether a graph has a cycle, or a cycle containing a given vertex. A cycle is a chain where the start vertex and the end vertex are the same vertex. A chain is a path of directed edges through a graph from a source vertex to a target vertex. Using a Prolog list representation, a chain is a list of vertices such that there is an edge between each pair of adjacent vertices in the list. Thus, in that representation of a chain, a cycle is a chain such that there is an edge from the final vertex in the list to the first vertex in the list. Consider the following predicate to test a graph for the presence of cycles:

Note that the cycle/2 predicate uses a chain/4 predicate (not defined here; see Programming Exercise 14.7.19) that checks for the presence of a path from a start vertex to an end vertex in a graph.

An independent set is a graph with no edges, or a set of vertices with no edges between them. A complete graph is a graph in which each vertex is adjacent to every other vertex. These two classes of graphs are complements of each other. To identify an independent set, we must check if the edge set is empty. In contrast, a complete graph has no self-edges (i.e., an edge from and to the same vertex), but all other possible edges. A complete directed graph with n vertices has exactly n × (n – 1) edges. Thus, we can check if a graph is complete by verifying that it is a valid graph, that it has no self-edges, and that the number of edges is described by the prior arithmetic expression. The following are independent and complete predicates for these types of graphs—proper is a helper predicate:

The list length/2 predicate (line 32) is built into SWI-Prolog. The following are goals involving independent and complete:

14.7.9 Analogs Between Prolog and an RDBMS

Interaction with the Prolog interpreter is strikingly similar to interacting with a relational database management system (RDBMS) using SQL. Pursuing goals in Prolog is the analog of running queries against a database. Consider the following database of Prolog facts:

Each of the five predicates in this Prolog program (each containing multiple facts) is the analog of a table (or relation) in a database system. The following is a mapping from some common types of queries in SQL to their equivalent goals in Prolog.

Union

While a comma (,) is the conjunction or the and operator in Prolog, a semicolon (;) is the disjunction or the or operator in Prolog.

Intersection

Difference

Projection

Selection

Projection Following Selection

Natural Join

Theta-Join

Adding the preceding queries in the form of rules creates what are called views in database terminology, where the head of the headed Horn clause is the name of the view:

Table 14.15 presents analogs between Relational Database Management Systems and Prolog. Datalog is a non-Turing-complete subset of Prolog for use with deductive databases or rule-based databases.

Table 14.15 Analogs Between a Relational Database Management System (RDBMS) and Prolog

Conceptual Exercises for Sections 14.6–14.7

Exercise 14.7.1 Prolog is a declarative programming language. What does this mean?

Exercise 14.7.2 Give an example of a language supporting declarative/logic programming other than Prolog.

Exercise 14.7.3 Explain why the +/1 Prolog predicate is not a true logical NOT operator. Provide an example to support your explanation.

Exercise 14.7.4 Does Prolog use short-circuit evaluation? Provide a Prolog goal (and the response the interpreter provides in evaluating it) to unambiguously support your answer. Note that the result of the goal ?– 3 = 4, 3 = 3. does not prove or disprove the use of short-circuit evaluation in Prolog.

Exercise 14.7.5 Since the depth-first search strategy is problematic for reasons demonstrated in Section 14.7.1, why does Prolog use depth-first search? Why is breadth-first search not used instead?

Exercise 14.7.6 In Section 14.7.1, we saw that left-recursion on the left-hand side of a rule causes a stack overflow. Why is this not the case in the reverse predicate in Section 14.7.4?

Exercise 14.7.7 Consider the following Prolog predicate a :- b, c,d., where b, c, and d can represent any subgoals. Prolog will try to satisfy subgoals b, c, and d, in that order. However, might Prolog satisfy subgoal c before it satisfies subgoal b? Explain.

Exercise 14.7.8 Reconsider the factorial predicate presented in Section 14.7.6. Explain why the goal factorial(N,120) results in an error.

Exercise 14.7.9 Consider the following Prolog goal and its result:

Explain why the result of the following Prolog goal does not bind X to 1:

Exercise 14.7.10 Which approach to resolution is more complex: backward chaining or forward chaining? Explain with reasons.

Programming Exercises for Sections 14.6–14.7

Exercise 14.7.11 Reconsider the append1/3 predicate in Section 14.7.4:

This predicate has a bug—it produces duplicate solutions (lines 4–5, 8–9, 12–13, 14–15, and 16–17):

This bug propagates when append1 is used as a primitive construct to define other (list) predicates. Modify the definition of append1 to eliminate this bug:

Exercise 14.7.12 Define a Prolog predicate reverse(L, R) that succeeds when the list R represents the list L with its elements reversed, and fails otherwise. Your predicate must not produce duplicate results. Use no auxiliary predicates, except for append/3.

Exercise 14.7.13 Define a Prolog predicate sum that binds its second argument S to the sum of the integers from 1 up to and including the integer represented by its first parameter N.

Examples:

Exercise 14.7.14 Consider the following logical description for the Euclidean algorithm to compute the greatest common divisor (gcd) of two positive integers u and v:

The gcd of u and 0 is u.

The gcd of u and v, if v is not 0, is the same as the gcd of v and the remainder of dividing v into u.

Define a Prolog predicate gcd (U, V, W) that succeeds if W is the greatest common divisor of U and V, and fails otherwise.

Exercise 14.7.15 Reconsider the list representation of an edge in a graph described in Section 14.7.8. Define a Prolog predicate noduplicateedges/1 that accepts a list of edges and that returns true if the list of edges is a set (i.e., has no duplicates) and false otherwise. Use no auxiliary predicates, except for not/1 and member/2.

Examples:

Exercise 14.7.16 Define a Prolog predicate makeset/2 that accepts a list and removes any repeating elements—producing a set. The result is returned in the second list parameter. Use no auxiliary predicates, except for not/1 and member/2.

Examples:

Exercise 14.7.17 Using only append, define a Prolog predicate adjacent that accepts only three arguments and that succeeds if its first two arguments are adjacent in its third list argument and fails otherwise.

Examples:

Exercise 14.7.18 Modify your solution to Programming Exercise 14.7.17 so that the list is circular.

Examples:

Exercise 14.7.19 Reconsider the description of a chain in a graph described in Section 14.7.8. Define a Prolog predicate chain/4 that returns true if the graph represented by its first parameter contains a chain (represented by its fourth parameter) from the source vertex and target vertex represented by its second and third parameters, respectively, and false otherwise.

Examples:

Exercise 14.7.20 Define a Prolog predicate sort that accepts two arguments, sorts its first integer list argument, and returns the result in its second integer list argument.

Examples:

The Prolog less than predicate is <:

Exercise 14.7.21 Define a Prolog predicate last that accepts only two arguments and that succeeds if its first argument is the last element of its second list argument and fails otherwise.

Examples:

Exercise 14.7.22 Define a Prolog nand/3 predicate. The following table models a nand gate:

Exercise 14.7.23 A multiplexer is a device that connects one of many inputs to a single output through one or more selector lines, which collectively model the numeric position of the selected input as a binary number. Define a Prolog predicate that acts as a 4-input 2-bit multiplexer.

Examples:

Exercise 14.7.24 Define a Prolog predicate validdate(Month,Day,Year) that accepts only three arguments, which represent a month, day, and year, in that order. The predicate succeeds if these arguments represent a valid date in the Gregorian calendar, and fails otherwise. For example, date (oct, 15, 1996) is valid, but date (jun, 31, 1921) is not. You must account for both different numbers of days in different months and February in leap years. A leap year is a year that is divisible by 400, or divisible by 4 but not also by 100. Therefore, 2000, 2012, 2016, and 2020 were leap years, while 1800 and 1900 were not. Your solution must not use more than three user-defined predicates or exceed 20 lines of code.

Examples: