Chapter 8:
The logical paradigm: From a boolean core to Prolog

8.1 A logical core language: logical variables and backtracking
8.2 Predicate abstracts are Horn clauses
    8.2.1 Parameter patterns
8.3 Data structures: functors
    8.3.1 Matching versus unification
    8.3.2 Data bases
8.4 Control structures
    8.4.1 Cut
8.5 No control structures
8.6 Parser and interpreter construction with Prolog
8.7 A few additional useful Prolog predicates
8.8 An implementation you can use
8.9 Addendum: Adding storable values

When you solve a crossword puzzle or a Sudoku puzzle, you are confronted with a gameboard of squares and a set of clues. (In Sudoku, the clues are values already inserted in some of the squares.) You solve the puzzle by placing values in the squares so that they fit the clues. Maybe you make some guesses for some of the squares, and you guess incorrectly, so you must ``backtrack'' and erase the values you placed in the squares and try again. Ultimately, there is a ``correct'' value for each square, and once you find the value, it stays in the square permanently. The puzzle is solved when all the squares are filled correctly to match the clues.

There is a style of programming that matches puzzle solving --- it is called constraint programming or logical programming. In the logical-programming paradigm, a program is a set of constraints, written as logical assertions, and a computation finds values for the variables mentioned in the logical assertions so that all the assections are made true. The variables are called logical variables, and they are like the squares of a puzzle. The logical assertions are like the clues to the puzzle. The computation tries various combinations of values to bind to the logical variables, trying to make true the logical assertions. If a combination of values does not succeed in making the assertions true, the computation backtracks (erases some of the values from the logical variables) and tries other combinations.

For example, here is a logical assertion: 2 + 1 = X. The X is a logical variable, a ``square'' to be filled to make the assertion true. If we bind 3 to X, we ``solve'' the ``puzzle.'' A puzzle can have more that one solution, for example, the logical assertion, Y > 3, can be solved by binding Y to 4 or to 5, etc.

The logical-programming paradigm is useful for solving problems in data bases, knowledge discovery, and learning: a data- or knowledge-base is coded as a set of logical assertions, and a query to the database is a logical assertion with variables that must receive values to answer the query.

In this chapter, we will study the structure of Prolog, the most popular language in the logical-programming paradigm.

8.1 A logical core language: logical variables and backtracking

A core language for a logical language should define how to write logical assertions. Here is the syntax we use:

===================================================

A: Atom (a single-quoted string)
X: LogicalVariable (a string that begins with an upper-case letter)
E: Element  (expressions)
P: Predicate (logical assertions)
Q: Query

Q ::=  ?- P .
E ::=  A  |  X
P ::=  E1 = E2  |  P1 , P2  |  P1 or P2  |  true  |  false
A ::=  an int or a single-quoted string

===================================================

The ``expressions'' of this language are elements, which, for the moment, are primitive atoms (ints and strings) or variables. Logical assertions are expressed as predicates which are either equality assertions, conjunctions (P1, P2 stands for ``P1 ∧ P2''), disjunctions, or just the primitives, true and false. (IMPORTANT: in the Prolog language, or is coded by ;.)

A program is a query, that is, a predicate that must be made true by binding values to the logical variables. The ``answer'' to the query (program) is the set of bindings that make the query true.

For this core language, the expressible values are ints and strings; the denotable values are the expressibles; and there are no storables, because there is no storage structure and no assignments.

Think of a query in this language as a puzzle that must be solved; it is a goal to be achieved. For example, the query,

?-  X = 'abc'.

is solved by binding (assigning once and for all) 'abc' to X. The answer to the query, the result of the computation, is the binding set (environment), {X == 'abc'}
Each binding is like a single-assignment, a final-variable, as it is called in Java/C#. Here, X is set to 'abc' and cannot be changed hereon.

Here are more example queries:

?- X = 'kim' or X = 'icecream' .
This goal can be achieved in two ways. The first solution sets X to 'kim', that is, the answer is the environment, {X == 'kim'}. A second solution sets X to 'icecream'.
?- X = 'kim', X = 'john'
This goal cannot be achieved, because variable X must be simultaneously bound to both kim as well as john, and this is impossible. The result is false.
The query
?- Y = Y
returns true, because no binding was needed to make the query true; the answer environment is { }.
?- (X = 'john', (Y = 'icecream' or Y = 'mary')) or (X = 'mary') .
This query can be solved in three ways, and it is worthwhile to examine the order in which the solutions are discovered. Let's say that the interpreter reads the query from left to right:
1. Since the goal has the form, P or Q, one solution is to make P true, that is, try to make true
  X = 'john', (Y = 'icecream' or Y = 'mary')
  This subgoal has the form, R, S (``R and S), so an environment must be found that makes both R and S true. We first make true X = 'john'. This builds the environment, {X == 'john'}, which is carried forward to solve the second goal, Y = 'icecream' or Y = 'mary'. This second goal can be solved by binding Y to 'icecream'. Here is the first solution to the query:
  {X == 'john', Y == 'icecream'}
2. The second solution is found by ``pretending'' that the first solution failed. That is, we erase Y == 'icecream' by reverting (backtracking) to the environment, {X == 'john'}, and we try to solve instead the second disjunct, Y = 'mary'. This gives the second solution:
  {X == 'john', Y == 'mary'}
3. To discover the third solution, we pretend that the second solution did not work and proceed from there. If the second solution did not work, it means the subgoal, X = 'john', (Y = 'icecream' or Y = 'mary') is exhausted. We backtrack and forget both the bindings for X and Y. We try to solve X = 'mary' with the empty environment, { }. This gives us the third solution:
  {X == 'mary'}
The example shows that the interpreter for the core language examines a query from left to right, solving subgoals. When a solution is found, the environment (bindings) generated are printed. To find more solutions, if any, the interpreter pretends that the solution failed, and it backtracks and searches for the next possibility. Each occurrence of or offers another possibility for solving the query.
Here is an example that shows why the environment is critical to solving a query:
?- (X = 'icecream' or X = 'kim'), X = Y, Y = 'kim' .
The interpreter must solve three subgoals: X = 'icecream' or X = 'kim' and then X = Y and then Y = 'kim'. The interpreter binds X to 'icecream and moves forward to solve the second subgoal, X = Y. The second subgoal makes the environment, {X == 'icecream', Y == 'icecream'}. This environment is used to solve the third subgoal, Y = 'kim'. It is impossible to set Y to both 'icecream' and also 'kim', and the attempt fails.
The interpreter backtracks to attempt another solution, returning us to the disjunct, X = 'icecream'. The bindings to X and Y are forgotten, and instead, the subgoal X = 'kim' must be solved. The second goal forces Y equals to X, and the environment for third goal is {X == 'kim', Y == 'kim'}. This enviroment makes true the third goal, Y = 'kim', giving us the only solution to the query.

8.2 Predicate abstracts are Horn clauses

If the same query is asked over and over, we might want to name it. Here is the syntax of predicate abstracts, equipped with element (expression) parameters:

===================================================

S: Session
D: Definition

S ::=  D ?- P
D ::=  D1 . D2  |  I1(I2*) :- P
P ::=  ...  |  I(E*)

===================================================

As usual, I* means zero or more identifiers, separated by commas, and E* means zero or more expressions, separated by commas. Multiple abstracts are listed in a sequence, separated by periods. The meaning of a call, I(E*), is the binding of the arguments to I's parameters, augmenting the environment with the bindings.

With the addition of predicate abstracts, the language's denotable values now include constant predicates.

Here is a simple example that defines two abstracts followed by a query:

===================================================

expensive(X) :- (X = 'house') or (X = 'car').
likes(Y, Z) :- Y = 'john',  expensive(Z)
?- likes(A, B)

===================================================

The first abstract states that when X is bound to 'house' or 'car', then the result is true (``a house is expensive; a car is expensive''). The second abstract returns true if its first argument is 'john' and its second argument makes expensive compute to true (``john likes Z if Z is expensive'').

It's worth studying how the interpreter searchs for a solution to the query, likes(A, B):

===================================================

GOAL                               ENVIRONMENT
=========================================================================
                                   { }
likes(A, B)        
                                   {A == Y0, B == Z0}
Y0 = 'john', expensive(Z0) 
                                   {A == 'john', B == Z0, Y0 == 'john'}
expensive(Z0) 
                                  {A == 'john', B == X0, Y0 == 'john', Z0 == X0}
(X0 = 'house') or (X0 = 'car') 

# (*) attempt to solve first disjunct: 
X0 = 'house'                         
                                   {A = 'john', B = 'house', Y0 = 'john',
                                                    Z0 = 'house', X0 == 'house'}
true

===================================================

The solution dsplayed is A == 'john' B == 'house'
(The internal variables are not displayed.) The second solution is found by pretending the first disjunct was a failure. This forces a backtrack to the execution point marked with (*), where the second disjunct can be tried:

===================================================

GOAL                               ENVIRONMENT
=========================================================================
                                 {A == 'john', B == X0, Y0 == 'john', Z0 == X0}
(X0 = 'house') or (X0 = 'car')       
# attempt to solve second disjunct:
X0 = 'car'
                                {A = 'john', B = 'car', Y0 = 'john',
                                                       Z0 = 'car', X0 == 'car'}
true

===================================================

The second solution displayed is A == 'john' B == 'car'
There are no more disjuncts to try, so the search is exhausted.

In the example, parameter variables are just logical variables. Each time an abstract is called, new variable names are created for the formal parameters; this avoids confusion when two abstracts use the same formal-parameter name, e.g, as in

expensive(X) :- (X = 'house') or (X = 'car').
likes(X, Z) :- X = 'john',  expensive(Z)

Since we invent new variable names, we don't need an environment stack (in which the same name can appear at different depths in the stack), like we did for the functional programs in the previous chapter.

The predicate abstracts give the language a new expressibility. The previous example suggests this reading:

To prove something is expensive, prove it is a house or car: expensive(X) :- (X = 'house') or (X = 'car').
To prove that someone likes something, prove that the someone is john and the something is expensive: likes(Y, Z) :- Y = 'john', expensive(Z).

Actually, this is the historical origin of the programming language, Prolog: The abstracts are called Horn clauses, and in logic, they are written as logical laws, looking like this: ∀X((X = 'house' ∨ X = 'car') —> expensive(X)) ∀X∀Z((X = 'john' ∧ expensive(Z)) —> likes(X, Z))
With this viewpoint, the query, likes(A, B), is written in logic like this: ?- ∃A∃B(likes(A,B))
To answer the query, the interpreter searches for values (witnesses, as they are called in logic) that prove there do indeed exist values, A and B, such that likes(A,B).

Here is a second example. The one abstract that follows codes all these facts:

--- john likes icecream and mary

--- everyone likes kim

--- ed likes everything

These facts are summarized in a relationship named, likes. Read the the following as, ``X likes Y if....''

===================================================

likes(X, Y) :- (X = 'john', (Y == 'icecream' or  Y == 'mary'))
               or (Y = 'kim')
               or (X = 'ed')

===================================================

We might make this query: ``who likes icecream?'' as ?- likes(Z, 'icecream')
The two solutions are {Z == 'john'} and {Z == 'ed'}. Here, icecream is the ``input'' argument to ``function'' likes and Z is the ``output'' variable.

Another query is, ``what does john like?'' --- likes('john', X). Here, john is the input and X gets the output. (The three outputs for X are icecream, mary, and kim.)

The query, likes('john', 'mary') returns true (no assignments to the empty environment are necessary). Both arguments are inputs. The query, likes('john', 'john') returns false. Finally, likes(A,B) returns all the combinations embedded within the rule for likes; both variables are output variables.

Here is another example, which lists which individuals (atoms) are female, which individuals have which parents, and what it means for one individual to have a second as a sister:

===================================================

female(X) :- X = 'marge' or X = 'lisa' or X = 'maggie' .

parents(A, B, C) :- B = 'homer', C = 'marge',
                    (A = 'bart' or A = 'maggie' or A = 'lisa') .

sisterOf(X,Y) :- female(Y), parents(Y,M,W), parents(X,M,W)

===================================================

(Read the second abstract as defining when A has B and C as parents; read the third as saying that X has Y as a sister.) The abstracts define a database that can be queried: ?- sisterOf('bart', B)
Let's follow the steps the computation takes to discover the first solution, B == 'lisa':

===================================================

GOAL                               ENVIRONMENT
=========================================================================
                                   { }
sisterOf('bart', B)
                                   {X0 == 'bart', B == Y0}
female(Y0), parents(Y0,M0,W0), parents(X0,M0,W0)
# solve the first of three subgoals:
female(Y0)
                                   {X0 == 'bart', B == Y0, X1 == Y0}
X1 = 'marge' or X1 = 'lisa' or X1 = 'maggie'
# (*) try the first option:
X1 = 'marge'
                                   {X0 == 'bart', B == 'marge',
                                            X1 == 'marge', Y0 == 'marge'}
# now, attempt the second of the three subgoals:
parents(Y0,M0,W0)
                                   {X0 == 'bart', B == 'marge', Y0 == 'marge',
                                        X1 == 'marge', A2 = 'marge',
 . . .                                  B2 == M0, C2 == W0}
false     # for A2 == 'marge', cannot make an assignment to B2 and C2

# backtrack to (*), where there is another option (disjunct) to try:

# try the second option:           {X0 == 'bart', B == Y0, X1 == Y0}
X1 == 'lisa'
                                   {X0 == 'bart', B == 'lisa',
                                        X1 == 'lisa', Y0 == 'lisa'}

# now, attempt the second of the three subgoals:
parents(Y0,M0,W0)
                                   {X0 == 'bart', B == 'lisa', Y0 == 'lisa',
                                        X1 == 'lisa', A2 = 'lisa',
 . . .                                  B2 == M0, C2 == W0}
true
                                   {X0 == 'bart', B == 'lisa', Y0 == 'lisa',
                                        X1 == 'lisa', A2 = 'lisa',
                                        B2 == 'homer', C2 == 'marge',
                                        M0 == 'homer, W0 == 'marge'}

# now, attempt the third of the three subgoals:
parents(X0,M0,W0)
                                   {X0 == 'bart', B == 'lisa', Y0 == 'lisa',
                                       X1 == 'lisa', A2 = 'lisa',
                                       B2 == 'homer', C2 == 'marge',
                                       M0 == 'homer', W0 == 'marge',
                                     A3 == 'bart', B3 == 'homer', C3 == 'marge'}


 . . .
true  
                                  {X0 == 'bart', B == 'lisa', Y0 == 'lisa',
                                       X1 == 'lisa', A2 = 'lisa',
                                       B2 == 'homer', C2 == 'marge',
                                       M0 == 'homer', W0 == 'marge',
                                       A3 == 'bart', B3 == homer, C3 == 'marge'}

===================================================

The execution trace shows that the interpreter first tries to prove that female marge is bart's sister, but it cannot prove that marge has any parents, so the attempt fails. A backtrack discovers that female lisa has parents and these parents match bart's.

The previous definition of sisterOf is a bit imprecise, because it allows the Prolog interpreter to prove that every female with parents is a sister of herself. To remove this faulty conclusion, we can add a not-equals requirement, \=, like this:

sisterOf(X,Y) :- female(Y), parents(Y,M,W), parents(X,M,W), X \= Y.

The subgoal, X \= Y, is proved true if X and Y have distinct, nonequal values. You can also use = to check for equality.

8.2.1 Parameter patterns

In the previous chapters, we saw that abstracts become more readable if patterns can be used in place of simple formal-parameter names. Patterns are useful here, too. For example, this abstract,

===================================================

likes(X, Y) :- (X = 'john', (Y == 'icecream' or  Y == 'mary')
               or (Y = 'kim')
               or (X = 'ed')

===================================================

can be split into a three-clause definition, where X and Y are replaced by atomic patterns:

===================================================

likes('john', Y) :- Y == 'icecream' or  Y == 'mary'.
likes(X, 'kim') :- true.
likes('ed', Y) :- true.

===================================================

This is more readable that the original definition of likes.

We can split the first clause into two, and we can also employ a Prolog abbreviation that drops true. This gives us Prolog's syntax for defining an abstract:

===================================================

likes(john, icecream).
likes(john, mary).
likes(X, kim).
likes(ed, Y).

===================================================

The four clauses list all the disjuncts in the original definition, one disjunct per line.

The example of females, parents, and sisters is also simplified by coding it in Prolog style:

===================================================

female(marge).
female(lisa).
female(maggie).

parents(bart, homer, marge).
parents(lisa, homer, marge).
parents(maggie, homer, marge).

sisterOf(X,Y) :- female(Y), parents(Y,M,W), parents(X,M,W), X \= Y.

===================================================

8.3 Data structures: functors

For the language we are developing, a data structure is a container that holds a collection of individuals. In logic, ``data structures'' are functions that build new individuals out of existing ones. For example, given the atoms, 'Tale of Two Cities' and 'Charles Dickens', we build the new individual, book('Tale of Two Cities', 'Charles Dickens'). The data structure is a kind of struct or object that holds two fields; the constructor name, book, is called a functor in Prolog. (It is part function name, part constructor name.)

Since our language does not have data type names in its syntax, we can add the data-structure syntax directly to the syntax for Element:

===================================================

P: Predicate
E: Element (expressions)
f: Functor (data-structure constructors)
N: Numeral

E ::=  A  |  X  |  f(E+)  |  N  |  E1 + E2
P ::=  ...  |  E1 < E2  |  E1 =< E2

===================================================

f(E+) is the syntax for a data structure, where E+ stands for one or more elements separated by commas. We have also added numerals, N, and arithmetic addition, E1 + E2 as elements. We will compare numeric values with predicates like E1 < E2 and E1 =< E2.

These extensions mean that expressible values are atoms, ints, and data structures constructed by functors.

Recall from the previous chapter that the data type of trees can be defined with a leaf data structure and a node data structure. A tree data structure is either

a leaf, of

a node, node(E, T1, T2), where E is an element and T1 and T2 are other tree data structures.

Here are some example trees: leaf * node(2, leaf, node(4, leaf, leaf)) 2 / \ * 4 / \ * * node(leaf, node('Homer', leaf, node(4, leaf, leaf)), leaf) * / \ 'Homer' * / \ * 4 / \ * *
We can use predicate abstracts to define functions that compute on trees. Say that we build trees whose nodes always hold numerals (ints). Here is a function that adds up the integers at the nodes:

===================================================

total(leaf, 0).
total(node(M, Left, Right), Answer) :- total(Left, N), total(Right, P), 
                                       Answer is N + P + M.

===================================================

The first clause says that the total value of a leaf is 0, and the second clauses says that the total of a node is the sum of the total of the ints in the left subtree, plus the total of the ints in the right subtree, plus the int saved in the node. This example shows how to use the pattern, node(M, Left, Right), to extract the three fields in the node data structure. Note also how the clause, Answer is N + P + M, adds the three ints, N, P, and M, and makes logical variable Answer equal to this sum.

Here is a function that constructs ordered trees. (Recall that a tree is ordered if, for all its nodes, the int held at the node is greater-or-equal to all ints held in the node's left subtree and less-or-equal to all ints hold in the node's right subtree.) The form of function call is insert(V, Tree, AnswerTree), where V is the value to be inserted, Tree is the ordered tree so far, and AnswerTree is the new ordered tree that looks like Tree with V inserted:

===================================================

insert(N, leaf, node(N, leaf, leaf)).

insert(N, node(M, Left, Right), node(M, Newleft, Right))
                             :- N =< M, insert(M, Left, NewLeft).

insert(N, node(M, Left, Right), node(M, Left, Newright))
                             :- N > M, insert(M, Right, Newright)

===================================================

We use the comparison operations compare the int to insert with the int stored in a node. Notice how patterns are used in the third parameter to assemble the answer data structure from the answers computed by the recursive calls.

If we wrote this function in a functional language, it would look like this:

fun insert(n, leaf) =  node(n, leaf, leaf)
  | insert(n, node(m, left, right)) =  if n <= m
                                         then let newleft = insert(n, left)
                                              in  node(m, newleft, right)
                                         else let newright = insert(n, right)
                                              in  node(m, left, newright)

This shows that the answer assembled by the function is the same as the answer that is bound to the third parameter of the predicate abstract.

Finally, here is a function that searches for a value in an ordered tree and returns true or false as an answer.

===================================================

member(M, node(N, Left, Right) :-  M = N.
member(M, node(N, Left, Right) :-  M < N, member(M, Left).
member(M, node(N, Left, Right) :-  M > N, member(M, Right)
member(M, leaf) :- fail.      # in Prolog, you can OMIT this clause (why?)

===================================================

8.3.1 Matching versus unification

This section needs to be written. Here are three examples to think about: 1. matching: as seen in predicates of form, X = E: (one side is just a var --- the var is forced to have value E) ?- X = 3. or ?- X = f(Y). 2. unification: as seen in predicates of form, E1 = E2 (vars on both sides) ?- (X = 'a' or X = f('b')), f(Y) = X. Here, both X and Y are forced to have new values to make the predicate true. 3. occurs check: required to break a circular unification. Rare, but when it arises, Prolog can unify-forever (loop): ?- X = f(Y), Y = f(X). (What are the values for X and Y that make this predicate true?!) Try each of these examples and see what happens.

8.3.2 Data bases

Here is a second example that shows how to use predicate abstracts and data structures to define the knowledge in a library's data base. Perhaps the library will stock books and DVDs whose data-structure representations are book(Title, Author) and dvd(Title), respectively. Here are two sample items:

book('David Copperfield', 'Charles Dickens')

dvd('Tale of Two Cities')

If the library owns an item, it is asserted with the predicate, owns(IdKey, Item), where Ikdey is the identification key for the Item. Here is a sample data base:

===================================================

owns('id90', book('David Copperfield', 'Charles Dickens')).
owns('id91', book('Tale of Two Cities', 'Charles Dickens')).
owns('id92', book('Tale of Two Cities', 'Charles Dickens')).
owns('id93', dvd('Tale of Two Cities')).
owns('id94', book('Moby Dick', 'Herman Melville')).

===================================================

When a patron borrows an item, an assertion of the form, borrows(IdKey, PatronName, TodaysDate), is added to the data base: Remembering checkouts: borrowed(lookupkey, patron, dateborrowed)

===================================================

borrowed('id92', 'Homer', 44).
borrowed('id93', 'Homer', 46).
borrowed('id91', 'Lisa', 92).
borrowed('id90', 'Lisa', 92).

===================================================

(The date could itself be a data structure of form, date(Day, Month, Year), but we use single ints for simplicity here.)

Here are some sample queries of the data base:

What items have Homer borrowed? (Don't display the date borrowed.) ?- borrowed(K, 'Homer', _). {K == 'id92'} {K == 'id93'}
In Prolog, _ stands for a ``logical variable'' whose value is not displayed when the answer environment is printed:

===================================================

GOAL                                ENVIRONMENT
---------------------------------------------------------
                                    { }

borrowed(K, 'Homer', _A)   # _A is an internal logical variable

# matches  borrowed('id92', 'Homer', 44):
                                    {K == 'id92', _A == 44} 

===================================================

What are the titles of books (not DVDs) that Homer borrowed? ?- borrowed(K, 'Homer', _), owns(K, book(T, _)) {K == 'id92', T == 'Tale of Two Cities'}
Here is how the solution is found:

===================================================

GOAL                                ENVIRONMENT
---------------------------------------------------------
                                    { }

borrowed(K, 'Homer', _A), owns(K, book(T, _B))

# solve the first subgoal:
borrowed(K, 'Homer', _A)
# matches borrowed('id92', 'Homer', 44):
                                   {K == 'id92', _A == 44}
# solve the second subgoal:
owns(K, book(T, _B))
# unifies with  owns('id92', book('Tale of Two Cities', 'Charles Dickens')) :

                                   {K == 'id92', _A == 44,
                                    T == 'Tale of Two Cities',
                                    _B == 'Charles Dickens'}

===================================================

When the second subgoal is solved, there is a ``two-way matching'' (unification) of the logical variables in the goal with the logical variables in predicate abstract.

A unification can cause a logical variable to be bound to a data structure, e.g., the query, ``what items did Homer borrow?''
?- borrowed(K, 'Homer', _), owns(K, I).
is solved by these two environments:
{K == 'id92', I == book('Tale of Two Cities', 'Charles Dickens')} {K == 'id94', I == dvd('Tale of Two Cities')}
Librarians want to track overdue items. Here is a law for proving when a borrowed item is overdue. (Assume an item can be borrowed for two weeks.)
isOverdue(Person, Key, Today) :- borrowed(Key, Person, BDate), Today > BDate + 14. ?- isOverdue('Homer', K, 58). {K == 'id92'}

We finish by introducing the list data structure, which is built into Prolog. In its classic form, a list is either empty, nil, or consists of an element, h, appended to the front of t, an existing list, cons(h, t). In Prolog, nil is written [] and cons(h,t) is written [h|t].

Here are two example functions. The first checks if an element, V, is already a member of a list:

===================================================

member(V, [H|T]) :- V = H.
member(V, [H|T]) :- member(V, T).
member(V, []) :- fail.    # or omit it

===================================================

Because of the order in which the clauses are written, the search for V will proceed from the front element of the list to the next and the next, etc., failing if the end of the list is reached.

Here is a function that inserts an int into its proper position of a list of ordered ints, e.g., insert(4, [1,3,5], Ans) will bind Ans to [1,3,4,5]:

===================================================

insert(N, [], [N]).
insert(N, [H|T], [N|Subans]) :-  N =< H, Subans = [H|T].
insert(N, [H|T], [H|Subans]) :-  N > H, insert(N,T,Subans).

===================================================

8.4 Control structures

It would be helpful to write a query that returns a list that holds the keys of all items that a library patron like Homer has borrowed.

This issue appears so often in practice that Prolog has a built-in predicate, findall, that does the job for us. Here is how to define the list of items borrowed by 'Homer':

?- findall(ItemKey, borrowed(ItemKey, 'Homer', _), Ans).
{Ans == ['id92','id93']}

The predicate, findall(WHAT, PREDICATE, ANSWERLIST), repeatedly proves PREDICATE, collecting each value of variable WHAT appearing in PREDICATE, saving the values in the list, ANSWERLIST.

In the above example, borrowed(Item, 'Homer', _) is executed, and Item = id92. Then, borrowed(Item, 'Homer', _) is executed again, and Item = id93. Then, borrowed(Item, 'Homer', _) is executed again, and there is failure (false). The two answers are collected into a list, and AnswerList = ['id92', 'id93'].

Read findall(X, PREDICATE, ANSWERLIST) like this:

``Find all the items, X, that make PREDICATE hold true and save them in the list named ANSWERLIST.''

We see that

?- findall(Key, borrowed(Key, _, _), AnswerList).
AnswerList = ['id92', 'id93', 'id91', 'id90']

lists all items borrowed by all persons. Next, ?- findall(K, borrowed(K, 'Marge', _), Ans). Ans = []
shows that 'Marge' has no items borrowed, and ?- findall(Date, borrowed(K, _, Date), DateList). DateList = [44, 46, 92, 92].
lists the dates all items were borrowed. Notice that the value(s) of K are not displayed. But you can use findall to save multiple values, say the Key and Date of each book Homer borrowed: ?- findall([Key,Date], (borrowed(Key, 'Homer', Date), owns(Key, book(_,_))), Ans). Ans = [['id92', 44], ['id93', 46]].

Many functional and scripting languages, e.g., Python, have their own versions of findall --- it is called a list comprehension operator. Here is how you do it in Python:

ANSWERLIST = [ OP(X)  for X in ARGUMENTLIST  if PREDICATE ]

Here is some Python code: nums = [0,1,2,3,4,5,6,7,8,9] # collects the even-valued ints in nums and triples them: answer = [ 3*n for n in nums if n % 2 == 0 ] print answer # prints [0,6,12,16,24]

For practice, we can compute findall answers from scratch, with recursion. We first define a function, notmember, such that notmember(V,L) returns true when V is not a member of list L:

===================================================

notmember(V, []).
notmember(V, [H|T]) :- V \= H,  notmember(V, T).

===================================================

Next, getborrowed0(Who, List, Ans) searches the library's data base for all entries of form, borrowed(IdKey, Patron, _) and adds each IdKey to the front of List. When the search is finished, the value of List is copied to Ans, which is returned as the final answer:

===================================================

getborrowed0(Who, List, Ans) :-
      borrowed(K, Who, _), notmember(K, List), getborrowed0(Who, [K|List], Ans).
getborrowed0(Who, List, List).

getborrowed(Who, Ans) :- getborrowed0(Who,[], Ans)

===================================================

The clause, getborrowed0(Who, List, Ans):- borrowed(K, Who, _), notmember(K, List), getborrowed0(Who, [K|List], Ans), finds an item borrowed by Who that is not already a member of List, adds it to List, and restarts the search for additional items. The clause, getborrowed0(Who, List, List), is used to terminate the search, copying the value of the second parameter into the third, answer parameter. This is why it is listed second.

The call, getborrowed(Who, Ans), activates getborrowed0(Who, [], Ans), starting it with the patron's name and an empty list of the items collected so far.

If the items borrowed are stated by these predicates,

borrowed(k2, 'Homer', 44).
borrowed(k4, 'Homer', 46).
borrowed(k3, 'Lisa', 92).
borrowed(k0, 'Lisa', 92).

the call, ?- getborrowed('Homer', A)
is solved in five different ways: {A == ['id93', 'id92']} {A == ['id92']} {A == ['id92', 'id93']} {A == ['id93']} {A == []}
The first solution is the most exhaustive; it results from searching through the borrowed predicates from top to bottom. From where do the other answers originate? Recall that the definition of getborrowed0 is stated in ``pattern format,'' and the underlying abstract is really this: getborrowed0(Who, List, Ans):- borrowed(K, Who, _), notmember(K, List), getborrowed0(Who, [K|List], Ans) or Ans = List
The occurrence of or makes clear that the function can can terminate successfully in its search for borrowed items by merely choosing its second disjunct. So, one solution to the query, getborrowed0('Homer', [], A), is to choose immediately the second disjunct, binding A to []. Or, we can solve the query by adding to the empty list any or all of the items borrowed by Homer. This generates five possible solutions. But we want the maximal solution, and since the interpreter reads the clauses from left to right, top to bottom, the maximal solution, ['id93', 'id92'], is found first.

How can we restrict the definition of findall so that it produces the first, maximal solution? We require a control structure that ``cuts off'' the subsequent searches. In Prolog, this control structure is called cut and is written as !.

8.4.1 Cut

The cut operator is added to the syntax of predicates:

===================================================

P ::=  ... |  I(E+) |  P1 , P2  |  P1 or P2  |  !

===================================================

When a cut operator is encountered by the interpreter, the interpreter deletes all possible backtracking (or) points in the proof search. This means the environment that exists at the point where the cut is encounted must be used to solve the query. Here is a simple example. First, this query can be solved two ways, because of the the or operator in the predicate: ?- (X = 'a' or X = 'b'), Y = f(X) {X == 'a', Y == f('a')} {X == 'b', Y == f('b')}
Here are the searches:

===================================================

GOAL                              ENVIRONMENT
-------------------------------------------------
                                  { }
(X = 'a' or X = 'b'), Y = f(X)
# (*) solve the first subgoal:
X = 'a' or X = 'b'
# try this option first:
X = 'a'
                                  {X == 'a'}
# solve the second goal:
Y = f(X) 
                                  {X == 'a', Y == f('a')}

To find the second solution, backtrack to (*):
                                  { }
# try this option:
X = 'b'
                                  {X == 'b'}
# solve the second goal:
Y = f(X)
                                  {X == 'b', Y == f('b')}

===================================================

If we insert the cut operator into the example,

===================================================

?- (X = 'a' or X = 'b'), !, Y = f(X)

{X == 'a', Y == f('a')}

===================================================

this fixes the environment at the point marked by !, namely, to {X == 'a'}, and we cannot backtrack to the second disjunct and try X = 'b':

===================================================

GOAL                              ENVIRONMENT
-------------------------------------------------
                                  { }
(X = 'a' or X = 'b'), !, Y = f(X)
# (*) solve the first subgoal:
X = 'a' or X = 'b'
# try this option first:
X = 'a'
                                  {X == 'a'}
# the next subgoal is cut:
!
                                  {X == 'a'}
# NO BACKTRACK PAST HERE

# solve the second goal:
Y = f(X)
                                  {X == 'a', Y == f('a')}

# Since there are no backtrack points after the cut, the search is finished.

===================================================

We can use cut to repair the earlier example that generates the list of all items borrowed:

===================================================

notmember(V, []).
notmember(V, [H|T]) :- V \= H,  notmember(V, T).

getborrowed0(Who, List, Ans) :-
      borrowed(K, Who, _), notmember(K, List), getborrowed0(Who, [K|List], Ans).
getborrowed0(Who, List, List).

getborrowed(Who, Ans) :- getborrowed0(Who,[], Ans), !.

===================================================

The cut used in getborrowed prevents the search for any more than the first solution computed.

Here is a second solution, which also generates the largest list of items borrowed:

===================================================

getborrowed0(Who, List, Ans) :-
      borrowed(K, Who, _), notmember(K, List), !, getborrowed0(Who, [K|List], Ans).
getborrowed0(Who, List, List).

getborrowed(Who, Ans) :- getborrowed0(Who,[], Ans).

===================================================

The power of the cut operator is exhibited in this small Prolog example, which defines a form of logical negation:

===================================================

not(P) :- call(P), !, fail.
not(P).

===================================================

Here, P can be any goal formula, and call is a Prolog operator that (re)starts the Prolog interpreter to try to solve P. If the interpreter succesfully finds a substitution that proves P, the cut operator forces that result into the opposite, a fail. If the interpreter fails to prove P, then the second clause announces success. In this way, the overall result is the exact opposite of what the interpreter found. This form of "not" is called negation by failure, and it is sensible only in the case when the database of facts will never grow larger than what it currently is. (Otherwise, previously proved "not-facts" will disappear as the database grows! The database's logic becomes non-monotonic.)

8.5 No control structures

The beauty of Prolog lies in its expression of solutions to a problem without the demand of stating the order (control) needed to compute the solution steps.

Here is a first example. This Prolog program checks and generates change adding up to a dollar consisting of quarters, dimes, nickels, and pennies.

===================================================

change([Q,D,N,P]) :-
        member(Q,[0,1,2,3,4]),                  /* quarters     */
        member(D,[0,1,2,3,4,5,6,7,8,9,10]) ,    /* dimes        */
        member(N,[0,1,2,3,4,5,6,7,8,9,10,       /* nickels      */
                   11,12,13,14,15,16,17,18,19,20]),
        Sum is 25*Q +10*D + 5*N,
        Sum =< 100,
        P is 100-Sum.

===================================================

Examples: ?- change([Q,D,N,P]).
lists all possible ways of giving change for a dollar. ?- change([0,D,N,P]).
lists all the ways of generating change that excludes quarters. We can also check if a proposed quantity of change totals a dollar: ?- change([2,3,4,6]). no
since 2 quarters, 3 dimes, 4 nickels, and 6 pennies do not make a dollar, and ?- change([2,3,2,P]). P=10
calculates how many pennies are needed to make all the coins total a dollar.

The program defines what it means to add up a quantity of quarters (Q), dimes (D), and nickels (N), and then add enough pennies (P) to make 100. But the program does not state in what order to count out the coins. Further, the program's user can state incomplete quantities of some coins. The Prolog interpreter supplies the search (control) strategy for finding numerical amounts that make the coins add up to 100, This is not indicated in the program --- the interpreter controls the order in which the variables are given values.

Here is a second, famous example. We say that an input list (or an array) is sorted into a new list if the new list is a permutation (reordering) of the input list and is ordered (its elements are arranged according to a comparison operator, <=). Just stating this requirement becomes a solution to the problem in Prolog:

===================================================

/* select(X, HasAnX, HasOneLessX)  "extracts" X from  HasAnX, giving HasOneLessX */
select(X, [X|Rest], Rest).
select(X, [Y|Ys], [Y|Zs] :- select(X, Ys, Zs).

/* permutation(Xs, Zs)  holds true if Zs is a reordering of Xs */
permutation([], []).
permutation([Xs, [Z|Zs]) :- select(Z, Xs, Ys),  permutation(Ys, Zs).

/* ordered(Xs)  holds true if the elements in Xs are ordered by  < */
ordered([]).
ordered([X]).
ordered([X,Y|Rest]) :- X =< Y,  ordered([Y|Rest]).

/* sorted(Xs, Ys)  holds when  Ys  is the sorted variant of Xs */
sorted(Xs, Ys) :- permutation(Xs, Ys), ordered(Ys).

===================================================

These clauses define what it means for list Ys to be a sorted version of input list Xs. Yet, when they are read by the Prolog interpreter, e.g., ?- sorted([5,3,7,2,9,1], Ans)
the interpreter will expand the definitions of permutation and ordered, generating all possible permutations of the input list and checking to see which permutation is also ordered. The one that is ordered binds to Ans: Ans = [1,2,3,5,7,9]
The interpreter "executed" the specification, and in doing so, located the answer!

This worked because the Prolog interpreter added its own control structure to the definitional clauses. In this sense, "specification + control = algorithm" is the slogan behind Prolog --- the human provides a specification of the problem, the interpreter provides control structure, and the result is an algorithm that computes the solution.

Alas, the algorithm synthesized here is slow and naive --- it grinds through all permutations of the input list to find the very one that is also ordered. A human can provide a bit of guidance to narrow the generation of the permutations. One example of such guidance is insertion sort, where a permutation is constructed by removing elements from the input list and moving them to the output list, inserting them in the appropriate position with respect to =<. Here is how insertion sort is coded in Prolog:

===================================================

/* insert(X, L, LwithX)  inserts element X into list L, generating  LwithX */
insert(X, [], [X]).
insert(X, [Y|Ys], [X, Y | Ys]) :-  X =< Y.
insert(X, [Y|Ys], [Y|Zs]) :-  X > Y,  insert(X, Ys, Zs).

/* isort(Xs, Ys)  generates  Ys  so that it is the sorted variant of Xs */
isort([], []).
isort([X|Xs], Ys) :-  isort(Xs, Zs), insert(X, Zs, Ys).

===================================================

Only one permutation of Xs is built --- the ordered one.

Prolog works great for game playing, where multiple searches must be made to calculate the consequences of all next possible moves. (Both sorting and change-making are "games" where the "player" must choose how to order elements or add coins.) Prolog is also great for solving problems that have no best strategies and must be solved by trial and error. If we add a few heuristics to narrow the search space of such trials, then the number of errors are reduced, and efficient solutions can appear.

8.6 Parser and interpreter construction with Prolog

It is a bit surprising that we can write a programming-language's parser and interpreter in Prolog, but the exercise shows how programming-by-search can yield a surprisingly simple solution to a difficult problem.

The parser and scanner

One way of viewing parsing is that it is a search for a tree that fits a list of input words. Given a BNF definition, we can write a set of Prolog clauses that searches all possible tree structures to find one that fits a sequence of words.

We will implement a baby expression language. Say that an input program is one long string, like this:

"( 3 * ( ab + 12 ) )"

In Prolog, a string is actually a list of characters (more precisely, a list of ACSII numeric character codes). For this reason, a string can be broken apart into its characters. (In constrast, an atom, like 'abc' or '2 + 3' cannot be split apart.)

Say that we have a definition, scan, that divides a long string into a list of the words in that string. For the above example, scan would produce the list,

["(", "3", "*", "(", "ab", "+", "12", ")"]

(We will define scan a little later.) Although it looks like a list of strings, this answer is actually a list of character-code-lists: [[40], [51], [42], [40], [97, 98], [43], [49, 50], [41]]. Keep this in mind when we study the parser.

Next, say we have this grammar for expressions with variables:

===================================================

E : Expression        N : Numeral        I : Identifier

   E ::=  N  |  I  |  ( E1 + E2 )
   N  is a string of digits
   I  is a string of lower-case letters

===================================================

and we want a definition, parseExpr, that will convert a list of words (strings) into an operator tree, where the operator trees are defined from the grammar like this:

===================================================

ETREE ::=  num(n)  |  iden(i)  |  add( ETREE1, ETREE2 ) 
   where  n  is an integer
          i  is a string of lower-case letters

===================================================

Notice that num, iden, and add are Prolog functors, so an operator tree is a compound functor expression.

Our parser is defined as a predicate, parseExpr(WordList, ETree), where WordList is the input list of words to be parsed and Etree is the operator tree built from WordList. For example, if we start Prolog and ask

?- parseExpr(["(", "2", "+", "(", "ab", "+", "35", ")", ")"], Tree).

the Prolog interpreter will reply with Tree = add(num(2), add(iden("ab"), num(35)))
(Actually, you will see this: Tree = add(num(2), add(iden([97,98]), num(35)))
because Prolog prints a string as a list of Ascii-character codes.)

Here is the coding of parseExpr. There is one clause for each clause in the BNF rule for Expression. There are also clauses for Numeral and Identifier:

===================================================

/* parseExpr(WordList, ETree)
      where  WordList  is the input list of words to be parsed
             Etree  is the output parse tree built from  WordList
   Example: ?- parseExpr(["(", "2", "+", "(", "x", "+", "35", ")", ")"], Tree).
            Tree = add(num(2), add(iden("x"), num(35)))   */

/* You can parse a single word into a  num-tree  if the word is a numeral: */
parseExpr([Word], num(Num)) :- parseNum(Word), toInt(Word, F, Num). 


/* You can parse a single word into an  iden-tree  if the word is an iden: */
parseExpr([Word], iden(Word)) :- parseIden(Word).  


/* To build an  add(T1,T2) tree, the  Words  list must begin with
   "(" and then have words to build T1, then have a "+", then have words
   to build T2 and then be terminated by ")".
   By trial and error, this clause searches for a successful splitting of
   Words  into the fragments:   */
parseExpr(Words, add(Tree1, Tree2)) :-  
             /* try to split  Words  into  ["("] + E1 + ["+"] + E2 + [")"] : */
             append(["("], W1, Words),
             append(E1, W2, W1),
             append(["+"], W3, W2),
             append(E2, [")"], W3),
             /* You can write em out to see how  Words  got chopped up: */
             /* write('W1: '), write(W1), nl,
                write('W2: '), write(W2), nl,
                write('W3: '), write(W3), nl, nl,  */
             /* parse the sublists  E1 and E2  to get their operator trees: */
             parseExpr(E1, Tree1),
             parseExpr(E2, Tree2).


/* Defines when a word is a numeral, that is, all digits.  Remember that
   a word is a string, i.e., a list of character codes:   */
parseNum([H]) :- isdigit(H).
parseNum([H|T]) :- isdigit(H), parseNum(T).
isdigit(N) :- N >= 48, N =< 57.

/* Converts a string of digits,  NumeralString,  to an int,  AnswerInt:
   Call it like this:
      ?- toInt(NumeralString, F, AnswerInt)
         The  F  is a "local variable" that is not part of the answer. */
toInt([], 1, 0).
toInt([H|T], Factor, Val) :-  toInt(T, Fac, Val0),
                    HVal0 is H - 48,      /* '0' is character code 48 */
                    HVal is HVal0 * Fac,
                    Val is HVal + Val0,
                    Factor is Fac * 10.


/* Defines when a word is an identifier, that is, all lower-case letters.
   Remember that a word is a string, i.e., a list of character codes:  */
parseIden([H]) :- isLetter(H).
parseIden([H|T]) :- isLetter(H), parseIden(T).
isLetter(L) :- L >= 97,  L =< 122.   /* 'a' is 97; 'z' is 122  */

===================================================

The amazing part of this definition is the clause that parses phrases of form, ( E1 + E2 ) --- the clause exhaustively tries to divide the words it has been given into five sublists --- ["("], E1, ["+"], E2, [")"] --- such that lists, E1 and E2, also parse successfully. This is not an easy activity, especially if there are multiple occurrences of "+" in the original word list. But by trying all possible subdivisions, the parser eventually finds the correct parse.

You can see the searching for yourself --- go into the coding of parseExpr(Words, add(Tree1, Tree2)) and remove the comment symbols that surround the write commands. Use this code on examples like "( ( 1 + 2 ) + 3 )" and "( 1 + ( 2 + 3 ) )". (See below about how to start the parser and do this.)

To finish the parser, we must supply the definition for scan:

===================================================

/* Scanner:  this part divides a string into a list of words. 

  scan(InputText, CurrentWordBeingAssembled,  WordsCollectedSoFar, FinalAnswer)
        where  InputText  is the string to be broken into words
               CurrentWordBeingAssembled  is the next word to be added to
                 to the  WordsCollectedSoFar
               WordsCollectedSoFar  are the words extracted so far from the
                 input text
               FinalAnswer  will hold the final value of  WordsCollectedSoFar 
                 It will be returned as the definition's answer

  IMPORTANT: all words must be separated by 1+ blanks!

  Example:  ?- scan("( 2 + ( x + 3 ) )", "", [], AnsList).
            AnsList = ["(", "2", "+", "(", "x", "+", "3", ")", ")"]
*/

/* cases when we have processed all the input text: */
scan([], [], Words, Words).
scan([], CurrentWord, Words, Ans) :- append(Words, [CurrentWord], Ans).

/* cases when there are more input characters to read:  */
scan([Char|Rest], CurrentWord, Words, Ans) :- notBlank(Char),
                       append(CurrentWord, [Char], NewWord),
                       scan(Rest, NewWord, Words, Ans).

scan([Char|Rest], CurrentWord, Words, Ans) :- isBlank(Char),
                       flushCurrentWord(CurrentWord, Words, NewWords),
                       scan(Rest, "", NewWords, Ans).

/* helper function that moves a completely assembled current word to the
     list of words collected so far:  */
flushCurrentWord("", Words, Words).
flushCurrentWord(Word, Words, NewWords) :- append(Words, [Word], NewWords).
/* a blank space is  Ascii code  32:  */
notBlank(C) :- C \= 32.
isBlank(32).

/* How to write a list of words to the output screen: */
writeWords([]) :- nl.
writeWords([H|T]) :- writeWord(H), writeWords(T).

writeWord([]) :- put(32).
writeWord([L|Rest]) :- put(L), writeWord(Rest).

===================================================

We connect these two definitions with this ``driver code'':

===================================================

/* Scanner and parser for an arithmetic language with variables.  
   Example use:

   ?- run.
   Type program as a string followed by a period:
   |: "( 2  +  ( xy + 34 ) )".
   Scanned program: ( 2 + ( xy + 34 ) ) 
   Parse tree: add(num(2), add(iden([120, 121]), num(34)))
   true 

   (Notice that "xy" displays as the two-ASCII-char list, [120, 121].)
*/

run :- write('Type program as a string followed by a period:'),
       nl,
       read(InputText),
       scan(InputText, "", [], WordList),
       write('Scanned program: '), writeWords(WordList),
       parseExpr(WordList, ExprTree),
       write('Parse tree: '), write(ExprTree), nl.

===================================================

Before you read further, place the parser, scanner, and driver into a file and start Prolog on it. Try it by typing ?- run.
and do examples like "( ( 1 + 2 ) + 3 )" and "( 1 + ( 2 + 3 ) )".

Exercise: Fix the scanner so that the user need not insert blanks between each and every word of the input program. Try your coding on inputs "(1+2)" and "(1+(2+3))".

Interpreter

We know how to mimick functions in Prolog with predicates, and this is how we write the interpreter for the expression language:

===================================================

/* Interpreter:  This part computes the meaning of an operator tree of form,
     ETREE ::=  num(n)  |  iden(i)  |  add( ETREE1, ETREE2 ) 

  All identifiers,  i,  will be treated as having the meaning,  0.
  To call this definition:

   evalExpr(ETREE, Store, Answer)   
      where  ETREE  is as above 
             Store  is a modelling of the memory
                    (In this prototype, the memory is empty! )-:
             Answer  is the integer  Answer, the meaning of  ETREE 

  Example usage:  ?- evalExpr( add(num(2), add(iden("x"), num(3))), [], Ans)
                  Ans = 5
*/

evalExpr(num(N), Store, N).

evalExpr(iden(I), Store, Ans) :- lookup(I, Store, Ans).

evalExpr(add(E1, E2), Store, Ans) :-  evalExpr(E1, Store, Ans1),
                                      evalExpr(E2, Store, Ans2),
                                      Ans is Ans1 + Ans2.

/* Looks up the value of identifier  I  in the memory  Store,  returning  Ans.
   For now, it works only with an empty memory and always returns 0.  
   Later, you will want to improve this.   */
lookup(I, [], 0).

===================================================

Here is the driver code, trivially modified to call the interpreter:

===================================================

run :- write('Type program as a string followed by a period:'),
       nl,
       read(InputText),
       scan(InputText, "", [], WordList),
       write('Scanned program: '), writeWords(WordList),
       parseExpr(WordList, ExprTree),
       write('Parse tree: '), write(ExprTree), nl,
       evalExpr(ExprTree, [], Answer),
       write('Program evaluates to: '), write(Answer), nl.

===================================================

Assemble these parts and try your new programming language.

Exercise:: Add commands to the language:

CL : CommandList           E : Expression
C : Command                I : Identifier
                           N : Numeral

CL ::=  C  |  C ; CL
C ::=  I = E  |  while E : CL end  |  print I
E ::=  N  |  I  | ( E1 + E2 )  |  ( E1 - E2 )
N ::=  strings of digits
I ::=  strings of lower-case letters, not including the keywords used above

A program is just a CommandList. Here are some example programs. To keep it simple, there must be one or more blanks between all words and symbols. "x = 2". " x = 2 ; y = ( x + 1 ) ; print x". "x = 2 ; y = ( x + 1 ) ; while y : x = ( x + 1 ) ; y = ( y - 1 ) end ; print x".
Your interpreter should operate like the example did: ?- run. Type program as a string followed by a period: |: "x = 2 ; y = ( x + 1 ) ; x = y ; print x". Scanned program: x = 2 ; y = ( x + 1 ) ; x = y ; print x Parse tree: [assign(iden([120]), num(2)), assign(iden([121]), add(iden([120]), num(1))), assign(iden([120]), iden([121])), print(iden([120]))] 3 Final contents of memory store: x == 3 y == 3 true

You first write the parser for Commands and CommandLists. (A CommandList is just a list of commands.) Next, you must model the memory as a list of (identifier,int) pairs. (E.g., a memory that maps x to 5 and y to 3 might look like this: [cell("x",5), cell("y",3)].) Write some maintenance operations: allocateNewIden, lookup, update, prettyPrintStore, etc., for using the memory. Insert these definitions with the interpreter, which you extend to Commands and CommandLists.

8.7 A few additional useful Prolog predicates

The simplest way to use Prolog is to type the database clauses into a file, named, say, myfile.pl. Start the file by double-clicking on its icon --- you will receive a command window into which you can type queries. If you wish to update the clauses in myfile.pl, edit it, stop the command window, and restart it.

In addition to the commands shown in the previous examples, here are a few more.

Use
?- listing.
to see a list of the clauses in the database.

Use write(ARG) to print a message while computing a solution, and use nl to print a newline. For example, double([], []) :- write('empty list'), nl. double([H|T], [HH|TT]) :- write('nonempty list. H='), write(H), write(' T='), write(T), nl, HH is 2 * H, write('HH='), write(HH), nl, double(T, TT).

You can ask the Prolog interpreter to generate an execution trace of its search. For the sisterhood example seen earlier in the chapter, we would type: ?- trace(sisterOf). ?- trace(parents). ?- trace(female).
to tell Prolog to print a trace of all uses of predicates sisterOf, parents, and female. When we enter the query, sisterOf(bart, Z).
we see this printout:

===================================================

[debug] 9 ?- sisterOf(bart,Z).
 T Call: (7) sisterOf(bart, _G464)
 T Call: (8) female(_G464)
 T Exit: (8) female(marge)
 T Call: (8) parents(marge, _L174, _L175)
 T Fail: (8) parents(marge, _L174, _L175)
 T Redo: (8) female(_G464)
 T Exit: (8) female(lisa)
 T Call: (8) parents(lisa, _L174, _L175)
 T Exit: (8) parents(lisa, homer, marge)
 T Call: (8) parents(bart, homer, marge)
 T Exit: (8) parents(bart, homer, marge)
 T Exit: (7) sisterOf(bart, lisa)
Z = lisa

===================================================

The trace shows that the interpreter first tried to use marge as a value for Z, bart's sister, but this failed because the bart and marge cannot be proved to have the same parents. Notice also that the intepreter invented its own internal variables, _G464, _L174, and _L175, while it did its search.

When we continue the trace by typing a semicolon, we see

===================================================

Z = lisa ;
 T Redo: (8) female(_G464)
 T Exit: (8) female(maggie)
 T Call: (8) parents(maggie, _L174, _L175)
 T Exit: (8) parents(maggie, homer, marge)
 T Call: (8) parents(bart, homer, marge)
 T Exit: (8) parents(bart, homer, marge)
 T Exit: (7) sisterOf(bart, maggie)
Z = maggie.

===================================================

which shows how the interpreter continues as if it had failed to find a value for Z the first time.

Use spy(PREDICATENAME) in place of trace if you want a breakpoint each time PREDICATENAME is entered or exited. That is, spy is like trace except you stop and restart the execution by pressing the Enter key.
Use
?- halt.
to stop the interpreter.
You can load multiple Prolog files with a command like this:
:- ['file1.pl', 'file2.pl', 'file3.pl'].

8.8 An implementation you can use

You can download a free copy of SWI-Prolog at www.swi-prolog.org. Once you install it, the simplest way to use it is to use a text editor to type a file that holds your Prolog database. Name the file with the extension, .pl (e.g., myProgram.pl. When you double-click on the icon for your file, this starts the Prolog interpreter, which loads the contents of your file into its internal database. A command window next appears, into which you can type queries. When you must modify your program, close the command window, edit your program, and restart it.

8.9 Addendum: Adding storable values

If we are building data structures like trees and lists, it would be convenient to save them in storage cells so that they could be computed as an output answer in one query and used as an input argument to another, subsequent query.

But stored values do not mix well with computation based on logical variables, unification, and (especially) backtracking. In particular, one cannot ``backtrack'' values stored in cells, because the old values were destroyed by assignment. This is why Prolog does not use storable values. (Instead, you are supposed to use a predicate called assert to add new predicate abstracts to the definitions data base.)

Nonetheless, let's try a modest experiment at adding storable values to a logic programming language. We will allow a data structure to be assigned to a storage cell only after a query finishes, so that there is no clash between assignment and backtracking. For example,

X = 'a', Y = f(X) then assign Y to V0

assigns f('a') to the cell named by V0. If we have this sequence of two queries: X = 'a', Y = f(X) then assign Y to V0. bind V0 to A, B = f(A) then assign B to V0
This first assigns f('a') to the cell named by V0 then fetches that value from storage and binds it to logical variable A, which is used to match against B and ultimately assign f(f('a')) to V0.

Here is the syntax underlying the examples:

===================================================

S: Session
D: Definition
X: LogicalVariable
V: StorageVariable
A: Atom

S ::=  D (?- P then assign X to V)+
D ::=  D1 . D2  |  I1(I2*) :- P
P ::=  E1 = E2  |  P1 , P2  |  P1 or P2  |  I(E*)  |  !  |  bind V to X
E ::=  A  |  X  |  f(E+)

===================================================

The syntax for a session shows that a session begins with a collection of definitions followed by one or more query, assignment sequences. If the value stored in a cell holds unresolved logical variables, the variables are treated like the parameter names of a predicate abstract, uniquely renamed each time the value is fetched from storage.

This little extension give you a taste of combining the logical paradigm with the imperative one. It is an example of a multi-paradigm language. In practice, such multi-paradigm combinations must be tried with great caution, as there are almost always unexpected interactions and surprising consequences.

Chapter 8: The logical paradigm: From a boolean core to Prolog