CSc 372 - Comparative Programming Languages
22 : Prolog -- The Database

Christian Collberg

Department of Computer Science

University of Arizona

1 Manipulating the Database

So far we have assumed that the Prolog database is static, i.e. that it is loaded once with the program and never changes thereafter.
This is not necessarily true; we can add or remove facts and rules from the database at will.
This is not necessarily good programming practice, but sometimes it is necessary and sometimes it makes for elegant programs.
In a nutshell:
1. Allows us to program with side effects.
2. Justified under some circumstances.
3. Often inefficient.

2 Assert

assert(X) adds a clause to the database. Not defined in gprolog!
asserta(X) adds a clause to the beginning of the database.
assertz(X) adds a clause to the end of the database.
assert always succeeds, and backtracking does not undo the assertion.

3 Assert...

assert can be used in machine learning programs, program which learn new facts as they progress.
In some Prolog implementations you have to specify whether a certain clause is dynamic (new clauses can be added to the database during execution) or static:
$\begin{gprogram} % \redtxt{:- dynamic(hanoi/5).} \end{gprogram}$
This means that we can add and remove clauses with five arguments whose functor is hanoi.

4 Assert ...- Example

Write a program that learns the addresses of places in a city.
This program assumes a Manhattan-style city layout: locations are given as the intersection of streets and avenues.

$\begin{gprogram} \redtxt{?- loc(whitehorse, Ave, St).} \\ \x Ave = 8, St = 11 \... ...2 \\ \redtxt{?- loc(airport, Ave, St).} \\ \x Ave = 5, St = 32 \end{gprogram}$

5 Assert ...- Example

$\begin{gprogram} location(whitehorse, 8, 11). \\ location(microsoft, 8, 42).\ ... ...at street? '), read(Street),\\ \x assert(location(X, Ave, Str)). \end{gprogram}$

6 Retract

retract(X) removes the first clause that matches X.
assert and retract behave differently on backtracking. When we backtrack through assert nothing happens. When we backtrack to retract Prolog continues searching the database trying to find another matching clause. If one is found it is removed.
If the argument to retract(clause(X)) contains some uninstantiated variables they will be instantiated.
retract(X) fails when no matching clause can be found.

7 Retract...

Backtracking does not undo the removal.

$\begin{gprogram} retractall(X) :- \\ \x retract(X), fail.\\ retractall(X) :- \\ \x retract((X :- Y))),\\ \x fail.\\ retractall(\_). \end{gprogram}$

8 Clause

clause(X, Y) finds all clauses in the database with head X and body Y.

$\begin{gprogram} append([], X, X). \\ append([A\vert B],C,[A\vert D]) :- \\ \x... ...\_6, Z=[\_4\vert\_7], \\ \xx Y=append(\_5, \_6, \_7) ; \\ \x no \end{gprogram}$

9 Clause...

The goal clause(X, Y) instantiates X to the head of a goal (the left side of :-) and Y to the body.
X can be just a variable (in which case it will match all the clauses in the database), a fully instantiated (ground) term, or a term which contains some uninstantiated variables.
Note that a fact has a body true.

10 Clause...

List all the clauses whose head matches X.

$\begin{gprogram} list(X) :- clause(X, Y),\\ \x print(X, Y), \\ \x write('.'), ... ...5\vert\_6],\_7,[\_5\vert\_8]) :- \\ \xxx append(\_6, \_8, \_8). \end{gprogram}$

11 Clausal Representation of Data Structures

Normally we represent a data structure using a combination of Prolog lists and structures.
A graph can for example be represented as a list of edges, where each edge is represented by a binary structure:
$\begin{gprogram}[edge(a,b), edge(c,b), edge(a,d), edge(c,d)] \end{gprogram}$
However, it is also possible to use clauses to represent data structures such as lists, trees, and graphs.
It is usually not a good idea to do this, but sometimes it is useful, particularly when we are faced with a static data structure (one which does not change, or changes very little).

12 Clauses as Data Structures - Lists

$\begin{gprogram} list(c). \\ list(h). \\ list(r). \\ list(i). \\ list(s). \\... ...cess\_list :- list(X), process\_item(X), fail. \\ process\_list. \end{gprogram}$

13 Clauses as Data Structures - Trees

$\begin{gprogram} t(node1, node2, phone(thompson, 2432), node3). \\ t(node2, nil... ...white, 2432), nil). \\ t(node4, nil, phone(mcbride, 1781), nil). \end{gprogram}$

14 Clauses as Data Structures - Trees...

Tree

15 Clauses as Data Structures - Trees...

$\begin{gprogram} inorder(nil).\\ inorder(Node) :-\\ \x t(Node, Left, P, Right)... ...(mcbride,1781)\\ \x phone(thompson,2432)\\ \x phone(white,2432) \end{gprogram}$

16 Clausal Representation...

In general it is a bad idea to represent data in this way.
Inserting and removing data has to be done using assert and retract, which are fairly expensive operations.
However, in Prolog implementations which support clause indexing, storing data in clauses gives us a way to access information directly, rather than through sequential search.
The reason for this is that indexing uses hash tables to access clauses.

17 Switches

From Prolog by Example, Coelho & Cotta.
In some cases it is a good idea to use global data rather than passing it around as a parameter.
Assume we want to be able to switch between short and long error messages. Instead of extending every clause by an extra parameter (clumsy and inefficient) we use a global switch.
The first clause in turnon will fire if the switch is already turned on.
The first clause in turnoff fails if Switch was already off.
The first clause in flip fails if Switch was turned off, in which case the second clause fires and the switch is turned on.

18 Switches...

$\begin{gprogram} turnon(Switch) :- \\ \x call(Switch), !. \\ turnon(Switch) :-... ...x retract(Switch), !. \\ flip(Switch) :- \\ \x assert(Switch). \end{gprogram}$

19 Switches...

$\begin{gprogram} turnon(terse\_mess). \\ \xx ..... \\ flip(terse\_mess). \\ \... ... \\ \x write(C), write('. Please accept our...'), \\ \x nl, !. \end{gprogram}$

20 Memoization

Many recursive program are extremely inefficient because they solve the same subproblem several times.
In dynamic programming the idea is simply to store the results of a computation in a table, and when we try to solve the same problem again we retrieve the value from the table rather than computing the value once more.
There is a variation of dynamic programming known as memoization.

21 Memoization - Towers of Hanoi

I'm sure you've heard of the Towers of Hanoi problem. It is one first year computer science students are tortured with to no end.
The problem is to move a number of disks from a peg A to a peg B, using a peg C as intermediate storage. Additionally, we are only allowed to put smaller disks onto larger disks.
A recursive solution of the problem to move disks from to is as follows:
1. Move disks from to .
2. Move the remaining (largest) disk from to .
3. Move the disks from to .

22 Memoization - Towers of Hanoi...

Hanoi

23 Memoization - Towers of Hanoi...

$\begin{gprogram} :- op(100, xfx, to).\\ \\ hanoi(1, A, B, C, [A to B]).\\ han... ... M2], Ms).\\ \\ go(N, Moves) :-\\ \x hanoi(N, a, b, c, Moves). \end{gprogram}$

24 Memoization - Towers of Hanoi...

$\begin{gprogram} \redtxt{?- go(2,M).} \\ \x M = [a to c, a to b, c to b] \\ \\... ..., \\ \xx c to a, b to a, c to b, \\ \xx a to c, a to b, c to b] \end{gprogram}$

25 Memoization - Towers of Hanoi...

$\begin{gprogram} hanoi(1, A, B, C, [A to B]).\\ hanoi(N, A, B, C, Ms) :-\\ \x ... ... Moves) :-\\ \x hanoi(N, A, B, C, Moves), \\ \x Pegs=[A, B, C]. \end{gprogram}$

26 Memoization - Towers of Hanoi...

$\begin{gprogram} hanoi(1, \_3, \_5, \_4, [\_3 to \_5]) :- !.\\ hanoi(2, \_3, \_... ...\xx \_3 to \_5, \_4 to \_3, \_4 to \_5,\\ \xx \_3 to \_5]) :- !. \end{gprogram}$

27 Example - Gensym

From Programming in Prolog, Clocksin & Mellish.
If we want to store data between different top-level queries, then using the database is our only option.
In the following example we want to generate new atoms.
In order to make this work, gensym has to store the number of atoms with a given prefix that it has generated so far. The clause current_num(Root, Num) is used for this purpose. There is one current_num clause for each kind of atom that we generate.

28 Example - Gensym...

$\begin{gprogram} gensym(Root, Atom) :- \\ \x get\_num(Root, Num),\\ \x name(Ro... ...).\\ get\_num(Root, 1) :- \\ \x asserta(current\_num(Root, 1)). \end{gprogram}$

29 Example - Gensym...

$\begin{gprogram} int\_name(Int, List) :- int\_name(Int, [], List).\\ int\_name(... ...x A = chris2 \\ \redtxt{?- gensym(chris, A).} \\ \x A = chris3 \end{gprogram}$

30 Readings and References

Read Clocksin-Mellish, Chapter 6.

Christian S. Collberg
2005-10-21

CSc 372 - Comparative Programming Languages 22 : Prolog -- The Database

CSc 372 - Comparative Programming Languages
22 : Prolog -- The Database