restivo@POLYA.STANFORD.EDU (Chuck Restivo) (07/25/88)
Date: Sat 23 Jul 1988 02:53-PST
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@POLYA.STANFORD.EDU>
Reply-to: PROLOG@POLYA.STANFORD.EDU>
US-Mail: P.O. Box 4584, Stanford CA 94305
Subject: PROLOG Digest V6 #52
To: PROLOG@POLYA.STANFORD.EDU
PROLOG Digest Friday, 22 July 1988 Volume 6 : Issue 52
Today's Topics:
Announcement - Career Opportunity,
Implementation - BFS & Performance & Style
--------------------------------------------------------------------------------------------------------------------------
Date: Friday, 22 July 1988 5:01 BST
From: William F. Clocksin <wfc%cam.cl@nss.cs.ucl.ac.uk>
Subject: Lectureship in Artificial Intelligence, Computer Lab., University of Cambridge
There is a vacancy for a University Lecturer in Artificial Intelligence to take up an appointment as soon as possible. Applicants should have a broad knowledge of the field of Artificial Intelligence, and have practical experience in areas such as planning and distributed problem solving. The ideal applicant would work closely with the Laboratory's artificial intelligence researchers, but would complement the Laboratory's existing strengths in natural language processing and computational logic.
The Computer Laboratory has nineteen members of academic staff, some twenty postdoctoral researchers, and eighty research (Ph.D.) students. About 200 undergraduate are taught. The Laboratory has close links with the computing industry, both local and international.
The appointment would be for three years, withthe possibility of reappointment to the retiring age. The pensionable scale of stipends for a University Lecturer, not ordinarily resident in College, is 13,365 (pounds sterling), rising by eleven annual increments to 20,615 (PS).
Further particulars may be obtained from the Secretary of the Appointments Committee, Computer Laboratory, University of Cambridge, Corn Exchange Street, Cambridge CB2 3QG, England, to whom applications, including a curriculum vitae, list of publications, and the names of not more than three referees, should be sent so as to reach him no later than 16 September 1988.
------------------------------
Date: 19 Jul 88 22:23:55 GMT
From: quintus!ok@unix.sri.com
Subject: breadth-first -vs- iterative deepening
Someone recently mentioned that he was writing a breadth-first interpreter
in Prolog, and Lee Naish suggested that iterative deepening might be a
better idea. I'd like to endorse that. I thought it would be interesting
to compare iterative deepening and breadth-first on a toy example. For
the "Advanced Prolog Course" we gave recently at Quintus I wrote a little
package (it's trivial, really it is) that takes rules to be processed by
iterative deepening and turns them into Prolog. So the example is
tree(X+Y) <- tree(X), tree(Y).
tree(a) <- true.
tree(b) <- true.
which expand_term/2 turns into
tree(A+B, N0, N) :- N0 > 0, N1 is N0-1,
tree(A, N1, N2),
tree(B, N2, N).
tree(a, N0, N) :- N0 > 0, N is N0-1.
tree(b, N0, N) :- N0 > 0, N is N0-1.
which is compiled as usual. There is an "interface" routine
id_call/1 which adds the appropriate arguments and generates
an increasing sequence of depth bounds.
For the breadth-first version, I used the obvious interpreter:
% solve(Goal)
% enumerates solutions for Goal in the usual fashion, but finds them
% by breadth-first interpretation of the clauses in rule/3.
solve(Goal) :-
prove([[Goal|[](Goal)]|Tail], Tail, Goal).
prove([Conj|Conjs], Tail, Orig) :-
nonvar(Conj), % don't run off the end!
prove(Conj, Conjs, Tail, Orig).
prove([](Goal), _, _, Goal). % report answer
prove([](_), Conjs, Tail, Orig) :- % look for another answer
prove(Conjs, Tail, Orig).
prove([Goal|Goals], Conjs, Tail, Orig) :-
findall(NewConj, rule(Goal,NewConj,Goals), NewConjs),
append(NewConjs, NewTail, Tail),
prove(Conjs, NewTail, Orig).
with the example clauses written as
rule(tree(X+Y), [tree(X),tree(Y)|Gs], Gs).
rule(tree(a), Gs, Gs).
rule(tree(b), Gs, Gs).
On quite small examples, solve(tree(X)) ran about 75 times slower than
id_call(tree(X)), and this figure worsened fairly rapidly for larger trees.
findall/3 is a library predicate in the version of Quintus Prolog I was
using, so this figure could be improved somewhat, but the fundamental
problem remains: breadth first search has to copy (as in findall/3) the
entire conjunction NewConj in order to rename variables apart, and the
harder the problem, the harder each step becomes.
------------------------------
Date: 19 Jul 88 08:57:25 GMT
From: mcvax!unido!ecrcvax!micha@uunet.uu.net (Micha Meier)
Subject: "A Note on the Speed of Prolog"
In article <6251@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes:
>Assuming that the comparison is a fair one (i.e. no one's
>writing execrable Pascal code or using the slowest Pascal system
>available), this seems to suggest that using a "state-of-the-art"
>Prolog system, one could actually have a Prolog version of the
>compiler that was faster than the Pascal version.
Well, I must say that our experiences are different, at least
concerning compilers for Prolog. I'm sure everybody agrees that
Quintus Prolog is a very fast Prolog, but our compiler, written in C,
is about 10 times faster than Quintus compiler written in Prolog
(and it does more optimizations). An interesting thing is that
most of the time is spent in the first pass, i.e. reading in
the clauses; maybe this makes Prolog different from other languages.
-- Micha
------------------------------
Date: 20 Jul 88 16:00:09 GMT
From: debray@arizona.edu (Saumya Debray)
Subject: A Note on the Speed of Prolog
In article <564@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes:
> I'm sure everybody agrees that Quintus Prolog is a very fast Prolog,
> but our compiler, written in C, is about 10 times faster than Quintus
> compiler written in Prolog ...
I'm not surprised at that: you'd expect some performance loss in going
from a low-level to a high-level language. A compiler written in
Prolog would have a fair amount of structure copying, runtime type
checking, tagging/untagging of operands, etc., that you wouldn't find
in the corresponding C code. What I found interesting about the
SIGPLAN Notices article I referred to originally was that despite the
overhead of runtime type checking etc., the Prolog code came as close
as it did to the performance of code written in a strongly typed
imperative language.
-- Saumya Debray
------------------------------
Date: 20 Jul 88 01:47:32 GMT
From: quintus!ok@unix.sri.com
I saw (never mind where) the following definition today:
/*1*/ permute(X, [A|Z]) :-
select(A, X, Y),
permute(Y, Z).
permute([], []).
where select/3 is the usual
select(Item, [Item|Set], Set).
select(Item, [OtherItem|Set0], [OtherItem|Set]) :-
select(Item, Set0, Set).
This version of permute/2 looked ugly to me.
(1) From Clocksin & Mellish 1st edition I learned to put base cases
_first_. It is _much_ the clearest place to put them.
(2) It isn't obvious from the code that the induction is really on
the *first* argument of permute/2: if the first argument is unbound
permute/2 may fail to terminate even if the second argument is ground.
A version which has neither of these defects is
/*2*/ permute([], []). % to permute [], return []
permute([X|Xs], Ys1) :- % to permute [X|Xs],
permute(Xs, Ys), % permute Xs giving Ys
select(X, Ys1, Ys). % insert X anywhere in Ys giving Ys1
Now, I think this version is much easier to read.
The reason for the title of this message is that it turns out to be
considerably faster in Quintus Prolog: 4 times faster for tiny lists,
5 times faster for 10 element lists. I can explain the result after
the event, but I wasn't expecting anywhere near that big a difference.
Elegance pays!
Of course, that version still suffers from the well known problem that
it can't be used to solve for the first argument given the second.
But at least it is a bit less surprising that that is so. In fact we
can easily fix that bug and produce a satisfactory permute/2:
/*2*/ permute(Xs, Ys) :-
permute(Xs, Ys, Ys).
permute([], [], []).
permute([X|Xs], Ys1, [_|Zs]) :-
permute(Xs, Ys, Zs),
select(X, Ys1, Ys).
This is a bit less than twice as slow as version /*2*/, but it is
more than twice as fast as version /*1*/ and works both ways around.
[permute(Xs, Ys, Zs) checks that Xs and Zs are the same length, so
that if Ys is known, it will terminate.]
---------------------------------
End of PROLOG Digest