COMP9814 Extended Artificial Intelligence

Prolog Extension Material

Contents:

Aims To study input and output in Prolog, including:
  • explicitly writing to the screen, & reading from the keyboard;
  • writing to and reading from files;
  • writing and reading a Prolog term at a time, vs a character at a time;

Also:

  • constructing and decomposing atoms;
  • reading programs from files from within Prolog.
References Bratko, I. Programming in Prolog for Artificial Intelligence, 3rd Edition, Addison-Wesley, 2000, chapter 6;
SWI Prolog documentation
Keywords write, nl, read, see, seen, tell, told, tab, putc, getc, atom_chars, consult.

Input & Output in Prolog

So far, our primary means of communicating with the Prolog system has been typing in queries on the keyboard, and getting responses like true., or fail., or variable binding(s) like
X = fido
Y = bone.

This isn't enough for writing serious applications in Prolog. We might want:

The built-in predicates described in this section make these things possible.

write

The built-in write(C) prints whatever is bound to C. For example,

?- write(likes(mary, pizza)).
likes(mary, pizza)


?- write(23).
23


?- write('apple').
apple


?- write("apple").
[97, 112, 112, 108, 101]

The last example is rather bizarre - SWI Prolog prints out the ASCII numeric codes for the letters a, p, p, l, and e (the ASCII code for a lower-case letter is 96 + the position of the letter in the alphabet, e.g. 96 + 5 = 101 for e).

write continued

Assume the facts: 
likes(mary, fish).
likes(john, lamb).
Then 
?- likes(mary, X), likes(john, Y), write(X), write(Y).

fishlamb

X = fish
Y = lamb

Notice that write does not move to a new line after printing, so that in the last example, fish and lamb are concatenated. In the last example, also, note that the bindings of X and Y are printed as usual, after the output of the two writes.

nl

One way to break up the output is to use the built-in predicate nl, which moves to the start of a new line:

Assume 
likes(mary, fish).
likes(john, lamb).
Then 
?- likes(mary, X), likes(john, Y),
    write(X), nl, write(Y).
fish
lamb

X = fish
Y = lamb

Suppressing output of bindings

To get rid of the bindings you can do the following: 

% cat stuff.pl
likes(mary, fish).  likes(john, lamb).

thing :-
        likes(mary, X),
        likes(john, Y),
        write(X), nl,
        write(Y), nl.
% prolog -s stuff.pl
?- thing.
fish
lamb

true.

read

One can also read terms typed on the keyboard:

?- read(X).
|: likes(fido, biscuits).

X = likes(fido, biscuits)

  1. SWI Prolog uses the prompt "|:" to signal that it is waiting for keyboard input. [You may also see a prompt "|"if you type a prolog query into the interpreter spread over more than one line.

  2. Notice that when you enter a term to be input by read, the term must be terminated with a ".". If you leave this out, you'll get another |: prompt.

?- read(X).
|: 23.
X = 23

?- read(X).
|: fido.

X = fido

read continued

Normally one uses read with a variable as parameter, but:

?- read(ok).
|: ok.

true.

?- read(jane).
|: fido.

fail. 

?- read(likes(jane, pizza)).
|: likes(jane, pizza).

true.

?- read(likes(jane, X)).
|: likes(jane, pizza).

X = pizza

tab

The built-in predicate tab(N) causes N spaces to be output:

?- write(hi), tab(1), write(there),nl.
hi there

true.

?- write(hi), tab(15), write(there),nl.
hi               there

true.

Communication with Files

To write to a file, not the screen, you change the current output stream to be the file, then write as usual. The built-in predicate tell(X) sets the current output stream. told closes this stream, and restores screen output. Bratko says otherwise; what follows works in SWI Prolog.

?- tell(myfile),
| write(hello_myfile), nl,
| told, 
| write(writing_to_screen_again), nl.
writing_to_screen_again

true.
?- ^D
% cat myfile
hello_myfile

tell & told continued

? tell(myfile1), write(thing1), nl,
| tell(myfile2), write(thing2), nl,
| tell(myfile1), write(thing3), nl,
| told, write(thing4), nl.
thing4

true.

% cat myfile1
thing1
thing3
% cat myfile2
thing2

Since myfile1 wasn't closed, write(thing3) appends to myfile1.

see & seen

If you wish to read from a file, and not from the keyboard, then you need to change the current input stream to the file, then read as usual. The built-in predicate see(X) sets the current input stream, and seen closes this stream, and restores the screen to be the current input stream. 

% cat mydata
likes(jane, pizza).
eats(fido, bone).
% prolog
?- see(mydata), read(X), read(Y), seen, read(Z).
|: the_end.

X = likes(jane, pizza)
Y = eats(fido, bone)
Z = the_end

File name format in Prolog

see(mydata) and tell(myfile) work, as above. If the file name has the form of a Prolog atom, you can just use the atom: see(mydata) and tell(myfile). If the file name has an extension or requires a path, then single quotation marks are necessary:

see('mydata.dat')
see('/home/cs9414/public/mydata.dat')
see('/home/cs9414/public/mydata')
tell('myfile.out')
tell('/home/cs9414/public/myfile.out')
tell('/home/cs9414/public/myfile')

End of file

How do you know when you have read to the end of the current file? In some cases you may know exactly how many terms there are in the file, but often you don't. In fact when SWI Prolog finds end of file when attempting a read(Term) goal, it binds Term to the special atom end_of_file. [When doing character-by-character reading (see below), the variable in question is bound to -1 instead.] Here is an example of using this end_of_file binding to terminate the processing of a file of data. 

% cat procfil.pl
processfile :-
        read(Term),
	Term \== end_of_file,
        process1(Term).

% we only get to the rule below if the one above fails,
% which happens if end of file is encountered.
processfile :-
        !.  % succeeds and blocks backtracking;
            % i.e. terminates processfile.

process1(Term) :-
        write(Term), nl,
        processfile.

End of file continued

% cat moredata
this(old, man).
he(plays, one).
he(plays, nik, nak).
on(my, tum).

% prolog -s procfil.pl
?- see(moredata), processfile, seen.
this(old, man)
he(plays, one)
he(plays, nik, nak)
on(my, tum)

true.

put - writing one character at a time

?- put(C).

writes the character C on the current output stream. For example,

?- put('f'), put('i'), put('d'), put('o'), nl.
fido
true.

C may in fact be either a character or an integer-expression in the range 0 to 255 - i.e. a character code:

?- put(102), put(105), put(100), put(111), nl.
fido
true.

get & get_byte - reading one character at a time

To read a single character from the current input stream use get_byte(C), where C is a variable. The result is in the form of an integer character code in the range 0 to 255.

?- get_byte(C).
|: abcde
C = 97

get(C) differs in that it reads the first non-blank character.

getc continued, flush_output

More realistically

Assume 
read_a_char(C) :-
   write('Type: '), flush_output,
   get_byte(C).
Then 
?- read_a_char(X).
Type: +
X = 43

Note: The flush_output makes sure the prompt "Type: " gets printed out immediately. Output might not be completed until there is enough to make it worthwhile, or until an operation like flush_output forces it.

atom_chars and other operations on atoms

The Prolog built-in atom_chars(Atom, List) either binds Atom to the atom constructed from the List of characters, or if Atom is instantiated and List is not, then List is bound to the list of characters in the Atom. atom_codes is similar but operates on lists of character codes.

?- atom_chars(A, [f, i, d, o]).
A = fido

?- atom_chars(fido, L).
L = [f, i, d, o]

?- atom_codes(A, [102, 105, 100, 111]).
A = fido

?- atom_codes(fido, L).
L = [102, 105, 100, 111]

A similar built-in is name, see p. 141 in Bratko. Do help(name). in SWI Prolog to find out details on name.

consult

% prolog -s mycode1.pl starts SWI Prolog with the Prolog code in mycode1.pl loaded up (assuming it contains syntactically correct code). Sometimes it is more convenient to load a file of Prolog code from within SWI Prolog. consult(File) allows this.

% prolog mycode1.pl
?- consult('mycode2.pl').
true.

However, it's not quite as simple as it looks. Before loading up the clauses in mycode2.pl, SWI Prolog completely removes any predicates mentioned in mycode2.pl from the Prolog database, and then the code in mycode2.pl is installed in the database. Thus if mycode1.pl contains likes(mary, pizza), and mycode2.pl contains likes(fido, bone), then consulting mycode2.pl will delete both these facts and then reload likes(fido, bone).

consult 2

% prolog -s mycode1.pl
?- likes(mary, pizza).

true.
?- consult('mycode2.pl').
Warning: (//mycode2.pl:1):
        Redefined static procedure likes/2
% mycode2 compiled 0.00 sec, 520 bytes

true.
?- likes(mary, pizza).

fail.
?- likes(fido, bone).

true.

listing

listing prints the current contents of the Prolog database (removing comments and replacing variable names):

% prolog -s procfil.pl
?- listing.
processfile :-
        read(A),
        A\==end_of_file,
        process1(A).
processfile :- !.


process1(A) :-
        write(A),
        nl,
        processfile.

%   Foreign: rl_read_init_file/1
%   Foreign: rl_add_history/1

true.

Further Prolog Built-ins

Aims To study "metalogical predicates" in Prolog, including:
  • predicates to test the type of terms;
  • predicates to construct and decompose terms;
  • a range of equality and comparison operators;
  • database manipulation (assert and retract)
  • control facilities (repeat, fail)
  • setof, findall
References Bratko, ed. 3, chapter 7; SWI Prolog documentation
Keywords var, nonvar, atom, integer, number, atomic, =.., functor, arg, assert, asserta, assertz, retract, fail, true, repeat, call, setof, findall

Term Type Testing

It may be necessary to know if a term is an number or a variable or something else.

Goalsucceeds if X is currently ...
var(X)an uninstantiated variable
nonvar(X)not a variable, or is an instantiated variable
atom(X)bound to an atom
integer(X)bound to an integer
number(X)bound to a number (integer or float)
atomic(X)bound to a number, string, or atom

Constructing and Decomposing Terms

A program might want to construct a goal, and then call that goal. If you have the functor and arguments in a list, then the =.. built-in predicate (pronounced univ), which uses an infix notation, lets you build the goal:

?- Goal =.. [likes, mary, pizza].
Goal = likes(mary, pizza).

In practice, you would only need to create a term in this way if the functor was only available bound to a variable:

?- RelationName = likes, Goal =.. [RelationName, mary, pizza].
RelationName = likes,
Goal = likes(mary, pizza).

You can also take terms apart with =..:

?- likes(mary, pizza) =.. List.
List = [likes, mary, pizza].

Constructing and Testing Goals

You can then test your goal, in SWI Prolog, just by stating it: 

?- likes(mary, pizza).
true.
?- Goal =.. [likes, mary, pizza], Goal.
Goal = likes(mary, pizza)

?- Goal =.. [likes, fido, cheese], Goal.
true.

In other dialects of Prolog, you might need to use call(Goal) to test the goal:

?- Goal =.. [likes, mary, pizza], call(Goal).

univ also works with infix operators:

?- Term =.. [+, 2, 3], Value is Term.

Term = 2+3,
Value = 5

Note that the operator, +, is still placed as the first item in the list, but, because it is an infix operator, it is printed with the + between the arguments.

functor and arg

Sometimes we don't want to convert the entire term into a list, just access its functor or one of its arguments. We can do this with functor(Term, Functor, Arity) which binds the functor of Term to Functor and the arity (number of arguments) to Arity or arg(N, Term, Arg) which binds the N-th argument of Term to Arg.

?- functor(likes(mary, pizza), Func, Arity).
Func = likes
Arity = 2

?- arg(2, likes(mary, pizza), Arg).
Arg = pizza

Equality and comparison tests

ComparisonDefinition
X = YX and Y match in the Prolog sense
X \= YX and Y do not match in the Prolog sense
X is Exptrue if X matches the value of the arithmetic expression Exp
T1 == T2true if terms T1 and T2 are identical; e.g. names of variables have to be the same
T1 \== T2true if terms T1 and T2 are not identical
E1 =:= E2true if values of expressions E1 and E2 are equal
E1 =\= E2true if values of expressions E1 and E2 are not equal
E1 < E2true if value of expression E1 is < value of E2
X @< Ytrue if value of X alphabetically precedes value of Y

Also >, >=, =<, @>, @=<, @>= all work as you would expect.

Equality and comparison examples

?- likes(X, pizza) = likes(mary, Y).
X = mary
Y = pizza

?- likes(X, pizza) == likes(mary, Y).

fail.
?- X = 3, Y = 5, X + 4 =:= Y + 2.
X = 3
Y = 5

?- X = 3, Y = 5, X + 4 =\= Y + 3.
X = 3
Y = 5

More equality and comparison examples

?- X = 3, Y = 5, X + 4 < Y + 3.
X = 3
Y = 5

?- mary @< pizza.

true.
?- likes(mary, pizza) @< likes(rex, cheese).

true.

Adding to the database from within a program

Prolog can infer facts, using rules, other facts, and its logic engine.

Inference can, however, be slow or very slow. It may be efficient, having inferred some fact, to add that fact to the Prolog database rather than possibly re-infer it later in the execution of a program. This is called memoization.

A classic example (though not particularly AI) is in calculation of the Fibonacci sequence using the recursive definition f0 = f1 = 1, and for n > 1, fn = fn-1 + fn-2. A straightforward translation of this into code in Prolog (or any other programming language) generates two recursive calls, each of which generates two recursive calls, each of which generates ... By the time you try to calculate f100, say, you are looking at something like 299 calls, which is around 1030. This would take more than 10 trillion years on a 3Ghz processor. (However, if processor speeds keep increasing at current rates, and you leave this computation until you are a senior citizen, it might only take 100,000 years. Moral: working smart is more effective than procrastinating.)

In some circumstances, a program might also infer new rules, and want to add them to the Prolog database.

assert

The built-in predicates assert, asserta, and assertz allow you to add to the database. 

?- assert(likes(mary, pizza)).
true.

?- listing.
likes(mary, pizza).

true.
?- assert((happy(X) :- is_dog(X), walkies(X))).

true.
?- listing.
happy(A) :-
        is_dog(A),
        walkies(A).
likes(mary, pizza) .

true.

retract

retract allows you to remove facts and rules from the database.

?- retract(likes(mary, pizza)).

true.
?- listing.
happy(A) :-
        is_dog(A),
        walkies(A).

true.

You might want to use a retract if you previously asserted a working hypothesis, then subsequently found evidence that the working hypothesis was wrong, or just to clear out a working memory structure between successive runs of some sub-algorithm.

retractall

% prolog
?- assert(dog(fido)).
?- assert(dog(rex)).
?- assert(dog(fang)).

?- retractall(dog(X)).

true.
?- listing.
true.   %  no clauses in database.

asserta and assertz

assert gives no control over where in the database the new fact or rule is positioned.

Remember that if there are several rules or facts with the same functor and arity, then the rule or fact listed first in the database is the one that is tried first.

Thus if you asserted something in order to avoid re-inferring it later using a rule with the same functor, then you had better ensure that the new fact or rule comes before other facts/rules with the same functor/arity.

asserta does this. For completeness, assertz puts the new fact/rule at the end of the database (or rather at the end of the facts/rules with the same functor and arity). In SWI Prolog assert and assertz are equivalent.

Exercise: Implement fib(+N, -Result), which calculates the Nth Fibonacci number (see description above). First translate the formula for fN directly into Prolog. Test it to find out how large N can be before Prolog "dies". Then add memoization, so that Fibonacci numbers are asserta-ed into the database as soon as they are calculated. How high can you go now?

dynamic

If you load up some facts like likes(mary, pizza). from a file of prolog code, and then try to assert further facts about likes from within your Prolog session, you will get a message like this from SWI Prolog:

ERROR: No permission to modify static_procedure `likes/2'

This is to help stop you from accidentally modifying procedures using assert. If you really want to modify a procedure that you originally loaded from a file of code, you need to have included the following directive in your original file of code:

% cat myfacts
:- dynamic likes/2.

likes(mary, pizza).
likes(john, fried_rat).

If you want to make several procedures dynamic, you can have, e.g.

:- dynamic likes/2, gives/3, gives/2.

Control Facilities

Use of repeat

Here is an example of using repeat: 

dountilstop :-
  repeat,
  read(X),
  (X = stop, !
   ;
   dosomethingwith(X),
   fail
  ).

The fail is there to force backtracking. (goal1 ; goal2) means "goal1 or goal2" - try goal1 first and if it fails, try goal2.

Concrete repeat example

% cat someterms
prerequisite_of(comp9322, comp9321).
prerequisite_of(comp9332, comp9331).
prerequisite_of(comp9415, comp9024).
stop.
more.

% cat dountilstop.pl
dountilstop :-
  repeat,
  read(X),
  (X = stop, !
   ;
   print(X), nl,
   fail
  ).

% prolog -s dountilstop.pl
?- see(someterms).
true.
?- dountilstop.
prerequisite_of(comp9322, comp9321)
prerequisite_of(comp9332, comp9331)
prerequisite_of(comp9415, comp9024)
true.

not

In Prolog, \+, pronounced "not" is built in, but can be defined as: 

\+(P) :-
	P, !, fail
	;
	true.

This says "if P succeeds, then fail (and do not backtrack). Otherwise, succeed." In other words, \+(P) succeeds if P cannot be proven, and fails if P can be proven. \+(P) may also be written as \+ P
This form of negation is known as negation as failure, and it depends on the closed world assumption that everything worth knowing is known to Prolog or is provable by Prolog.

It is better to use X \== Y than \+(X == Y) and similarly for other comparison operators which possess a built-in negation.

You may also see not(P), an older form, now deprecated.

\+ is supposed to be a mnemonic for not (\) provable (+).

For an example of \+ in action, see The path Program, below.

setof

Backtracking in Prolog lets us find all the solutions to a goal or list of goals. However, these goals are produced separately. Sometimes one would like a list of all the solutions. This is what setof and findall are for.

% cat happy.pl
happy(fido).
happy(rex).
happy(lassie).
% prolog -s happy.pl

?- setof(X, happy(X), List).
List = [fido, lassie, rex]

Prolog finds all solutions, sorts them, removes any duplicates, and binds the resulting list to List.

findall

What if you want to keep the duplicates?

% cat happy2.pl
movie_star(rintintin). movie_star(lassie).
happy(fido). happy(rex). happy(lassie).
happy(X) :- movie_star(X).
% prolog -s happy2.pl
?- setof(X, happy(X), List).
List = [fido, lassie, rex, rintintin]

?- findall(X, happy(X), List).
List = [fido, rex, lassie, rintintin, lassie]

Note that if they can't find any items that satisfy the predicate, in SWI Prolog, findall succeeds and binds the list to [], while setof fails.

Data Structures

Aims To study data structures and their implementation in Prolog, including:
  • lists;
  • stacks;
  • queues;
  • graphs;
  • arrays;
  • structs/records;
References Bratko, ed. 3: arrays p. 188, graphs p. 215
Keywords arg, push, pop, empty, join, serve, edge, vertex.

Data Structures in Prolog

This is a very brief introduction - whole courses are normally dedicated to data structures and the algorithms that operate on them.

Revision of Lists

Lists come free in Prolog (and LISP), in the sense that they are built into the language. In languages like C, this is not the case, and relatively complex code is needed to do even the simple basic things with lists.

In Prolog, lists look like this: [1, 2, 3, 4]. You construct a list like this: [1 | 2, 3, 4], and you get bits out of it by matching: 

?- [1, 2, 3, 4] = [First | Rest].
First = 1
Rest = [2, 3, 4]

Stacks

Sometimes it is useful to access a list in a certain disciplined way - new items always get put at the front, and items are always removed from the front. This is what Prolog lists do naturally, so when we declare that a particular list is a stack, we are just emphasising that we will be accessing in a special way. Stacks are sometimes referred to as LIFO (Last-In is First-Out) structures.

Adding to a stack is called pushing the stack.
Removing an items from a stack is called popping the stack.
Before removing something from the stack, it is wise to check to see if it is empty. Here's an implementation: 

% empty(+Stack) succeeds if the Stack is empty
empty([]).

% pop(-Item, +OldStack, -NewStack)
%    takes the Item from the head of the
%    OldStack to produce the NewStack
pop(Item, [Item | NewStack], NewStack).

% push(+Item, +OldStack, -NewStack)
%    adds Item to the *front* of the OldStack
%    to make NewStack
push(Item, OldStack, [Item | OldStack]).

Queues

Queues are analogous to stacks, but are FIFO (First-In First-Out) structures, like queues in real life. A new item joins the end of the queue, and you serve the queue by removing the item at the start of the queue. Again, it is wise to check for emptiness before trying to serve the queue. Implementation:

% empty(+Queue) which succeeds if the Queue is
%   empty - same implementation as for stacks

% join(+Item, +OldQueue, -NewQueue)
%     adds Item to the *end* of the OldQueue
%     to make NewQueue
join(Item, [], [Item]).
join(Item, [First | Rest], [First | NewRest]) :-
        join(Item, Rest, NewRest).

% serve(-Item, +OldQueue, -NewQueue)
%      takes the Item from the head of the
%      OldQueue to produce the NewQueue
serve(Item, [Item | NewQueue], NewQueue).
% NB: this does the same thing as pop

Graph Representation

A graph may be represented by a set of edge predicates and a list of vertices. 

 edge(1, 5). edge(1, 7). edge(2, 1). edge(2, 7).               
 edge(3, 1). edge(3, 6). edge(4, 3). edge(4, 5).
 edge(5, 8). edge(6, 4). edge(6, 5). edge(7, 5).
 edge(8, 6). edge(8, 7).

 vertex(1). vertex(2). vertex(3). vertex(4).
 vertex(5). vertex(6). vertex(7). vertex(8).

Vertex names don't have to be numbers, and sometimes edges come with associated data. For example, in a road-distance graph, you might have vertices that are names of places, and edges might look like this:

edge(maroubra, 3.2, kensington).

meaning that it is 3.2 kilometres from Maroubra to Kensington.

Finding a Path

Whenever you see a new data structure, you can ask "what operations can we do on this structure?" In the case of a graph, one thing you often want to do is find a path from one vertex to another vertex. 

        path(+Start, +Finish, +Visited, -Path).

Start is the name of the starting node
Finish is the name of the finishing node
Visited is the list of nodes already visited - this is an "accumulator"
Path is the list of nodes on the path, including Start and Finish

The Path Program

        path(Node, Node, _, [Node]).


        path(Start, Finish, Visited, [Start | Path]) :-
                edge(Start, X),
                \+(member(X, Visited)),
                path(X, Finish, [X | Visited], Path).

To find the paths from, say, vertex 1 to vertex 3, we'd use the Prolog query:

?- path(1, 3, [1], Path).

Here is an example of the path algorithm in action. There are lots of other things to do with graphs. Some are in Bratko.

Arrays

Most programming languages provide facilities that are convenient for representing matrices and vectors. Prolog does not. It is possible to represent things like this in Prolog, but it can be cumbersome. For example, you can represent a vector as a list of numbers, and a matrix as a list of lists of numbers:

[1, 2, 3, 4, 5]

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

Accessing the items is inconvenient - to get the 4th item in the vector, you have to step through all the preceding items. To access the (2,3)-entry in the matrix, you have to step through to the 2nd row, and then step through that to the 3rd item.

A few operations turn out to be easy to implement - e.g. the inner or dot product of two vectors is fine.

Arrays 2

It is possible to simulate arrays in Prolog, to a degree, using terms, and the arg built-in procedure. For example, you can build a vector term like vector(1, 3, 5, 7, 9) and then to access say the 4th item in it, you can use the goal

?- arg(4, vector(1, 3, 5, 7, 9), Value).
Value = 7

Unlike in languages like C, it is not possible to update the values in such terms, except by making a new copy of the whole structure with the desired value changed. This would be slow if done repeatedly, as is often the case with array structures in C.

An alternative is to write a file with the numerical computation problem specified, get a C program to do the computation, then it writes a file with the answer in it, and a/the Prolog program then reads the answer and proceeds.

Techniques and Efficiency

Aims Prolog Programming Principles and Techniques :
  • principles of good programming
  • improving efficiency
References Bratko, ed. 3: chapter 8
Keywords correctness, usability, efficiency, readability, modifiability, robustness, documentation

Principles of Good Programming

These are covered in other CSE courses, but not in COMP9414.

Correctness

Obvious. But in fact, all large-enough programs have some bugs.:-(

A slow, hard-to-use, non-robust program that produces correct results is preferable to one that produces radically wrong results.

User-friendliness (Usability)

There are psychological principles that provide a guide as to what sort of user interface is easy to use. You can find out about this in COMP9511 Human-Computer Interaction.

Efficiency

Programs shouldn't waste time or memory space.
This includes RAM memory but also disk file space.
An inefficient but correct program running on a large problem may not find a result (in time to be useful).
Spending time on speeding up a fast-enough program is however pointless - the dollar-advantage of making the program more efficient needs to be weighed against the dollar-cost. Issues like this are covered in COMP9101 Design & Analysis of Algorithms.

Readability

Your program should be as easy to understand as possible. If it isn't, you probably don't understand it, which means it may be wrong. If you use some weird trick you read about or thought up - explain what it does.

If your program is worthwhile, it may be used for years, and modified (or corrected) by other programmers. You need to make their job as easy as possible.

Using helpful comments and meaningful identifiers will help to make your program readable. So will layout: indent systematically and use blank lines to break up your code into natural units.

Modifiability

Apart from making your program readable (see above), use of modular structure and clear interfaces to your procedures makes your program easier to test and modify.

In other words:

Robustness

I specifically de-emphasise this in COMP9414, but a good program needs to be able recover from input data that is in an unexpected format or which doesn't meet the assumptions you make about the data.

In the case of data format, you can "parse" the data - e.g. check that you really have read a number (if a number is what you are expecting).

An example of an unmet assumption would be when you go to divide one number by another, only to find that the second number is zero. Solution: check the divisor before you divide. In general, check the assumption holds before you apply the operation that relies on that assumption.

Documentation

Documentation comes in two flavours - internal (comments, etc. in the code), and external (user reference manual, user tutorial manual).

In describing a predicate in its header comment, it can be helpful to specify which arguments are meant to be input (+) and which are meant to be outputs (-). So, if you write a procedure sort(List, SortedList) to sort a List, producing a SortedList, you can briefly indicate the uses of the parameters by writing sort(+List, -SortedList). Some parameters can be used as either input or output - but sort is not like this. Such parameters can be indicated using ? rather than + or -. For example, the built-in atom_chars could have its uses indicated by the expression atom_chars(?Atom, ?List) along with the remark that at least one of Atom and List must be instantiated (see above).

Compilation vs Interpretation

There are two ways to execute a Prolog program.

The first - interpretation - involves taking the rules and facts in the text format in which they are supplied to Prolog and "interpreting" them - that is, figuring out what each goal means, and executing it, then figuring out what the next goal means, and executing that, and so on.

The second way - compilation - involves translating each rule into machine code. When the compiled code is executed, it is typically 10 times faster than interpreted code.

To compile code with SWI Prolog, do something like 

% prolog -c mycode.pl
The compiled code will appear in a file called a.out 
% a.out
then executes this code. [I have done minimal experimentation with this SWI Prolog facility.]

Compilation also provides an opportunity to automatically "improve" the code, which might make it faster still. One area, particularly relevant to Prolog, where this might help, is the elimination of tail-recursion.

Tail-recursion is where the recursive goal is the very last goal of the Prolog rule. When this happens, the recursion can be converted into a loop, which can be executed more efficiently, because of the overheads associated with a procedure call (in this case a sequence of recursive procedure calls).

Making sumlist Tail-Recursive

First Version

% sumlist(+List, -Sum) - Sum is the sum of numbers in List
sumlist([], 0).
sumlist([First | Rest], Sum) :-
    sumlist(Rest, SumRest),
    Sum is First + SumRest. % not tail-recursive

Making sumlist Tail-Recursive 2

% Ivan Bratko, ed. 3, p 187
sumlist(List, Sum) :-
    sumlist(List, 0, Sum). % call auxiliary predicate

% sumlist/3
% sumlist(+List, PartialSum, -TotalSum):
%   TotalSum = PartialSum + sum over List

sumlist([], Sum, Sum).
sumlist([First | Rest], PartialSum, TotalSum) :-
    NewPartialSum is PartialSum + First,
    sumlist(Rest, NewPartialSum, TotalSum).

Making reverse Tail-Recursive

% reverse(+List, -ReversedList)
reverse([], []).
reverse([X | Rest], Reversed) :-
    reverse(Rest, RevRest),
    concat(RevRest, [X], Reversed). % append [X] at end

This is also inefficient because concat takes time proportional to the length of RevRest, which increases as more and more of the list gets reversed.

Making reverse Tail-Recursive 2

% Ivan Bratko, ed. 3, p 188
reverse(List, Reversed) :-
    reverse(List, [], Reversed).

% reverse/3
% reverse(+List, PartReversed, -Reversed)
% Reversed is obtained by adding the elements of List in
%    reversed order to PartReversed
reverse([], Reversed, Reversed).
reverse([X | Rest], PartReversed, TotalReversed) :-
    reverse(Rest, [X | PartReversed], TotalReversed).
                   % add X to accumulator

Making reverse Tail-Recursive 3 

% prolog -s reverse.pl
?- trace.
true.
[trace]  ?- reverse([1,2,3], X).
 Call: (7) reverse([1, 2, 3], _G293)          invoke the rule for reverse/2
 Call: (8) reverse([1, 2, 3], [], _G293)      invoke rule 2 for reverse/3
 Call: (9) reverse([2, 3], [1], _G293)        2nd invocation rule 2 for reverse/3
 Call: (10) reverse([3], [2, 1], _G293)       3rd invocation rule 2 for reverse/3
 Call: (11) reverse([], [3, 2, 1], _G293)     invoke rule 1 for reverse/3
 Exit: (11) reverse([], [3, 2, 1], [3, 2, 1]) rule 1 succeeds at once - no RHS
 Exit: (10) reverse([3], [2, 1], [3, 2, 1])   | successive completions of
 Exit: (9) reverse([2, 3], [1], [3, 2, 1])    | of the calls to rule 2,
 Exit: (8) reverse([1, 2, 3], [], [3, 2, 1])  | reverse/3
 Exit: (7) reverse([1, 2, 3], [3, 2, 1])      rule for reverse/2 succeeds

X = [3, 2, 1]

UNSW's CRICOS Provider No. is 00098G
Last updated on: 15 March 2010
Copyright (C) Bill Wilson, 1996-2008, except where another source is acknowledged. The presentation of the path algorithm derives from lectures by Claude Sammut.