To study input and output in Prolog, including:
|References||Bratko, I. Programming in Prolog for Artificial Intelligence,
4th Edition, Addison-Wesley, 2011, chapter 6;|
SWI Prolog documentation
So far, our primary means of communicating with the Prolog system
has been typing in queries on the keyboard, and getting responses
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(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).
likes(mary, fish). likes(john, lamb).Then
?- likes(mary, X), likes(john, Y), write(X), write(Y). fishlamb X = fish Y = lamb
write does not move to a new line after
printing, so that in the last example,
lamb are concatenated. In the last example, also,
note that the bindings of
are printed as usual, after the output of the two
One way to break up the output is to use the built-in predicate
nl, which moves to the start of a new line:
likes(mary, fish). likes(john, lamb).Then
?- likes(mary, X), likes(john, Y), write(X), nl, write(Y). fish lamb X = fish Y = lamb
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.
One can also read terms typed on the keyboard:
?- read(X). |: likes(fido, biscuits). X = likes(fido, biscuits)
|:" 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.
read, the term must be terminated with a "
.". If you leave this out, you'll get another
?- read(X). |: 23. X = 23 ?- read(X). |: fido. X = fido
Normally one uses
read with a variable as parameter,
?- 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
The built-in predicate
spaces to be output:
?- write(hi), tab(1), write(there),nl. hi there true. ?- write(hi), tab(15), write(there),nl. hi there true.
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
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(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
myfile1 wasn't closed,
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
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
tell(myfile) work, as
above. If the file name has the form of a Prolog atom, you can just use
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')
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
to the special atom
end_of_file. [When doing
character-by-character reading (see below), the variable
in question is bound to
Here is an example of using this
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.
% 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
writes the character
C on the current output stream.
?- 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
?- put(102), put(105), put(100), put(111), nl. fido true.
get_byte- reading one character at a time
To read a single character from the current input stream
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
read_a_char(C) :- write('Type: '), flush_output, get_byte(C).Then
?- read_a_char(X). Type: + X = 43
flush_output makes sure the
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_charsand other operations on atoms
The Prolog built-in
atom_chars(Atom, List) either
Atom to the atom constructed from the
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 description in Bratko.
help(name). in SWI Prolog to find out details on
% prolog -s mycode1.pl
starts SWI Prolog with the Prolog code in
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
likes(mary, pizza), and
likes(fido, bone), then
mycode2.pl will delete both
these facts and then reload
% 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 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.
To study "metalogical predicates" in Prolog, including:
|References||Bratko, ed. 4; SWI Prolog documentation|
It may be necessary to know if a term is an number or a variable or something else.
|Goal||succeeds if X is currently ...|
|an uninstantiated variable|
|not a variable, or is an instantiated variable|
|bound to an atom|
|bound to an integer|
|bound to a number (integer or float)|
|bound to a number, string, or atom|
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].
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.
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
Functor and the arity
(number of arguments) to
arg(N, Term, Arg) which binds the
?- functor(likes(mary, pizza), Func, Arity). Func = likes Arity = 2 ?- arg(2, likes(mary, pizza), Arg). Arg = pizza
|X and Y match in the Prolog sense|
|X and Y do not match in the Prolog sense|
|true if X matches the value of the arithmetic expression Exp|
|true if terms T1 and T2 are identical; e.g. names of variables have to be the same|
|true if terms T1 and T2 are not identical|
|true if values of expressions E1 and E2 are equal|
|true if values of expressions E1 and E2 are not equal|
|true if value of expression E1 is < value of E2|
|true if value of X alphabetically precedes value of Y|
all work as you would expect.
?- 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
?- X = 3, Y = 5, X + 4 < Y + 3. X = 3 Y = 5 ?- mary @< pizza. true. ?- likes(mary, pizza) @< likes(rex, cheese). true.
?- a(b, c) == a(b, c). true. ?- a(b, C) == a(b, C). true. ?- a(B, c) == a(b, C). false.The next two are particularly strange (example due to Jayen Ashar).
?- S == jim, S = jim. fail. ?- S = jim, S == jim. S = jim.
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.
The built-in predicates
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 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
% prolog ?- assert(dog(fido)). ?- assert(dog(rex)). ?- assert(dog(fang)). ?- retractall(dog(X)). true. ?- listing. true. % no clauses in database.
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
assertz are equivalent.
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
into the database as soon as they are calculated. How high can
you go now?
If you load up some facts like
from a file of prolog code, and then try to
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.
failis a goal that always fails
trueis a goal that always succeeds
repeatis a goal which, suitably used, does what the name suggests.
repeat behaves as if defined by:
repeat. repeat :- repeat.
repeat succeeds when first called. On backtracking,
the second clause (
repeat :- repeat.) is tried, and
it initiates a new call to
repeat, which succeeds via
the first clause, and so on.
Here is an example of using
dountilstop :- repeat, read(X), (X = stop, ! ; dosomethingwith(X), fail ).The
failis there to force backtracking.
(goal1 ; goal2)means "goal1 or goal2" - try
goal1first and if it fails, try
% 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.
\+, pronounced "not" is built in, but can be
\+(P) :- P, !, fail ; true.
This says "if
P succeeds, then fail (and do not
backtrack). Otherwise, succeed." In other words,
P cannot be proven, and fails if
P can be proven.
\+(P) may also be written as
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.
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
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
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
To study data structures and their implementation in Prolog, including:
|References||Bratko, ed. 4|
This is a very brief introduction - whole courses are normally dedicated to data structures and the algorithms that operate on them.
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]
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 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
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.
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).
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, , 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.
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.
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.
Prolog Programming Principles and Techniques :
|References||Bratko, ed. 4|
|Keywords||correctness, usability, efficiency, readability, modifiability, robustness, documentation|
These are covered in other CSE courses, but not in COMP9414.
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.
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.
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.
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.
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:
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 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
SortedList, you can briefly indicate
the uses of the parameters by writing
Some parameters can be used as either input or output - but
sort is not like this. Such parameters can be indicated
? rather than
For example, the built-in
atom_chars could have its
uses indicated by the expression
along with the remark that at least one of
List must be instantiated (see above).
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.plThe compiled code will appear in a file called
% a.outthen 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).
% 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
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).
% 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.
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
% 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], , _G293) 2nd invocation rule 2 for reverse/3 Call: (10) reverse(, [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(, [2, 1], [3, 2, 1]) | successive completions of Exit: (9) reverse([2, 3], , [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
Copyright (C) Bill Wilson, 1996-2012, except where another source is acknowledged. The presentation of the
path algorithm derives from lectures
by Claude Sammut.