14.6 The Prolog Programming Language

Prolog, which stands for PROgramming in LOGic, is a language supporting a declarative/logic style of programming that was developed in the early 1970s for artificial intelligence applications. Traditionally, Prolog has been recognized as a language for artificial intelligence (AI) because of its support for logic programming, which was initially targeted at natural language processing. Since then, its use has expanded to other areas of AI, including expert systems and theorem proving. The resolution algorithm built into Prolog, along with the unification and backtracking techniques making resolution practical in a computer system, make its semantics more complex than those found in languages such as Python, Java, or Scheme.

14.6.1 Essential Prolog: Asserting Facts and Rules

In a Prolog program, knowledge is represented as facts and rules and a Prolog program consists of a set of facts and rules. A Prolog programmer asserts facts and rules in a program, and those facts and rules constitute the database or the knowledge base. Facts and rules are propositions that are represented as Horn clauses in Prolog (Table 14.11).

Table 14.11 Mapping of Types of Horn Clauses to Prolog Clauses

Facts. A headed Horn clause with an empty antecedence is called a fact in Prolog— an axiom or a proposition that is asserted as true. The fact “it is raining” can be declared in Prolog as: weather (raining).

Rules. A headed Horn clause with a non-empty antecedent is called a rule. A rule is a declaration that is expressed in the form of an if–then statement, and consists of a head (the consequent) and a body (the antecedent). We can declare the rule “if it is raining, then I carry an umbrella” in Prolog as follows: carry (umbrella) :- weather (raining). A rule can be thought of as a function. In Prolog, all functions are predicates—a function that returns true or false. (We can pass additional arguments to simulate returning values of other types.) Consider the following set of facts and rules in Prolog:

The facts on lines 1–3 assert that a circle, square, and rectangle are shapes. The two rules on lines 5–6 declare that shapes that are squares and rectangles are also rectangles. Syntactically, Prolog programs are built from terms. A term is either a constant, a variable, or a structure. Constants and predicates must start with a lowercase letter, and neither have any intrinsic semantics—each means whatever the programmer wants it to mean. Variables must start with an uppercase letter or an underscore (i.e., _). The X on lines 5–6 is a variable. Recall that propositions (i.e., facts and rules) have no intrinsic semantics—each means whatever the programmer wants it to mean. Also, note that a period (.), not a semicolon (;)— which has an another important function—terminates a fact and a rule.

14.6.2 Casting Horn Clauses in Prolog Syntax

The following are some of the Horn clauses given previously represented in Prolog syntax:

Notice that the implication ⊂ and conjunction ∧ symbols are represented in Prolog as :- and ,, respectively.

14.6.3 Running and Interacting with a Prolog Program

We use the SWI-Prolog⁷ implementation of Prolog in this chapter. There are two ways of consulting a database (i.e., compiling a Prolog program) in SWI-Prolog:

• Enter swipl <filename> at the (Linux) command line:

  

• Use the built-in consult/1⁸ predicate (i.e., consult (′<filename>′). or [<f ilename>].):

  

In either case, enter make. in the SWI-Prolog REPL to reconsult the loaded prolog program file (without exiting the interpreter), if (uncompiled) changes have been made to the program. Enter halt. or the EOF character (e.g., <ctrl-D> on Linux) to end your session with SWI-Prolog. Table 14.12 offers more information on this process.

Table 14.12 Predicates for Interacting with the SWI-Prolog Shell (i.e., REPL)

Comments. A percent sign (i.e., %) introduces a single-line comment until the end of a line. C-style comments (i.e., /* … */) are used for multi-line comments. Unlike in C, in Prolog multi-line comments can be nested.

Backtracking. The user can enter an n or ; character to cause Prolog to backtrack up the search tree to find the next solution (i.e., substitution or unification of values to variables that leads to satisfaction of the stated goal). The built-in predicate trace/0 allows the user to trace the resolution process (described next), including instantiations, as Prolog seeks to satisfy a goal.

Program output. The built-in predicates write, writeln, and nl (for newline), with the implied semantics, write output. The programmer can include the following goal in a program to prevent Prolog from abbreviating results with ellipses:

The argument passed to max_depth indicates the maximum depth of the list to be printed. The maximum depth is 10 by default. If this value is set to 0, then the printing depth limit is turned off.

14.6.4 Resolution, Unification, and Instantiation

Once a database—a program—has been established, running the program involves asking questions or, in other words, pursuing goals. A headless Horn clause is called a goal (or query) in Prolog (Table 14.11). There is a distinction between a fact and a goal even though they appear in Prolog to be the same. The proposition commuter(lucia) ⊂ true is a fact because its antecedence is always true. Conversely, the proposition false ⊂ commuter(lucia) is a goal. Since both an empty antecedent and an empty consequent are omitted in Prolog, these two clauses can appear to be both facts or both goals. The goal false ⊂ commuter(χ) ∧ doesnothave(χ, bicycle) has two subgoals in its antecedent.

A Prolog interpreter acts as an inference engine. In Prolog, the user gives the inference engine a goal that the engine then sets out to satisfy (i.e., prove) based on the knowledge base of facts and rules (i.e., the program). In particular, when a goal is given, the inference engine attempts to match the goal with the head of a headed Horn clause, which can be either a fact or a rule. Prolog works backward from the goal using resolution to find a series of facts and rules that can be used to prove the goal (Section 14.5.5). This approach is called backward chaining because the inference engine works backward from a goal to find a path through the database sufficient to satisfy the goal. A more detailed examination of the process of resolution in Prolog is given in Section 14.7.1.

To run a program, the user supplies one or more goals, each in the form of a headless Horn clause. The activity of supplying a goal can be viewed as asking questions of the program or querying the system as one does through SQL with a database system (Section 14.7.9). Given the shape database from our previous example, we can submit the following queries:

This small example involves multiple notable observations:

• Lines 1, 3, and 7 contain goals.

• Aperiod(.), not a semicolon (;) terminates a fact, rule, or goal.

• After Prolog returns its first solution (line 4), the user can enter an ; or n character to cause Prolog to backtrack up the search tree to find the next solution (i.e., substitution of values for variables that leads to satisfaction of the stated goal), as shown on lines 5–6.

• Since an empty antecedent or consequent is omitted in the codification of a clause in Prolog, a fact and goal are syntactically indistinguishable from each other in Prolog. For instance, the clause shape(circle). can be a fact [i.e., asserted proposition; shape(circle) ⊂ {}] or a goal [i.e., query; tu ⊂ shape(circle)]. Thus, context is necessary to distinguish between the two. When a clause [e.g., shape(circle).] is entered into a Prolog interpreter or appears on the left-hand side of a rule (i.e., the body or antecedent), then it is a goal or a subgoal, respectively. Otherwise, it is a fact.

• The case of the first letter of a term indicates whether it is interpreted as data (lowercase) or as a variable (uppercase). Variables must begin with a capital letter or an underscore. The term circle on line 1 is interpreted as data, while the term X on line 3 is interpreted as a variable.

• Thegoal shape(X) on line 3 involves a variable and returns as many values for X as we request for which the goal is true. Additional solutions are requested with a “;” or “n” keystroke.

  Recall that the process of temporarily binding values to identifiers during resolution is called instantiation. The process of finding a substitution (i.e., a mapping) that, when applied, renders two terms equivalent is called unification and the substitution is said to unify the two terms. Two literals or constants only unify if they are the same literal:

  

  The substitution that unifies a variable with a literal or term binds the literal or term to the variable:

  

  On lines 14–15, notice that a variable unifies with a term that contains an occurrence of the variable (see the discussion of occurs-check in Conceptual Exercise 14.8.3). A nested term can be unified with another term if the two terms have the same (1) predicate name; (2) shape or nested structure; and (3) number of arguments, which can be recursively unified:

  

  Lines 27–28 and 40–41 are substitutions that unify the clauses on lines 25–26 and 38–39, respectively. Lastly, to unify two uninstantiated variables, Prolog makes the variables aliases of each other, meaning that they point to the same memory location:

  

• If Prolog cannot prove a goal, it assumes the goal to be false. For instance, the goal shape (triangle) on line 7 in the first Prolog transcript given in this subsection fails (even though a triangle is a shape) because the process of resolution cannot prove it from the database—that is, there is neither a shape (triangle). fact in the database nor a way to prove it from the set of facts and rules. This aspect of the inference engine in Prolog is called the closed-world assumption (Section 14.9.1).

The task of satisfying a goal is left to the inference engine, and not to the programmer.

7. https://www.swi-prolog.org

8. The number following the / indicates the arity of the predicate. The /<#> is not part of the syntax of the predicate name.