restivo@POLYA.STANFORD.EDU (Chuck Restivo) (04/13/88)
Date: Wed 6 Apr 1988 11:58-PDT >From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SUSHI.STANFORD.EDU> Reply-to: PROLOG@SUSHI.STANFORD.EDU US-Mail: P.O. Box 4584, Stanford CA 94305 Subject: PROLOG Digest V6 #14 To: PROLOG@SUSHI.STANFORD.EDU PROLOG Digest Sunday, 10 Apr 1988 Volume 6 : Issue 14 Today's Topics: Query - Modules, Implementation - Morality & Time Tabling, LP Library - AND-parallelism & Backtracking ---------------------------------------------------------------------- Date: Wed, 17 Feb 88 10:09:43 +0100 >From: even@ifi.UIO.NO Subject: Modules in prolog. I am working on a Prolog system that allows the programmer to define theories, and use them to answer queries with a prove or demo relation. The only literature on the subject that I have found, is Bowen and Kowalski's article in "Logic programming". I would like to hear from anybody who knows about later work in that field. -- Even Larsen ------------------------------ Date: 7 Feb 88 03:58:42 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: ripoff It has recently come to my attention that there is a benchmark program floating around which contains a collection of operations on arbitrary precision integers. These operations form the bulk of the file, and include predicates with names like addn/5 divq/4 comz/5 and the data structure used to represent numbers is [d0,d1,...dk] ~~ d0 + R*(d1 + R*(... + R*dk) ...) where R is 10000 on 32-bit machines or 100000 on DEC-10s to represent non-negative integers separate sign (+ or -) and [d0,...,dk] to represent signed integers number(Sign,Numerator,Denominator) where gcd(Numerator,Denominator) = 1 or 0 to represent rationals. This collection of operations comes from either - the freely available DEC-10 Prolog file EVAL.PL, or - the Quintus Prolog file library(long). But the "Author:" comment has been removed. The DEC-10 Prolog version of the rational arithmetic package is freely available, and I have no objection to anyone using and distributing it. However, I am very upset that my name has been taken off it. Taking the author's name off a program that you got for nothing is a mean and contemptible thing to do, unless of course you have the author's permission. (If you make a small extract from the program for instructional purposes, that's another matter. If someone had a file containing one or two of the operations, I wouldn't expect them to retain my name on that.) I am not going to name names, because I believe that the people who distributed the copy I saw are at least two steps away from the culprit. So if you have a copy of this program, don't think that I am accusing the person you got it from. In general: - the DEC-10 Prolog files which I sent to {SU-SCORE} may freely be used and distributed, even in commercial systems. - there is no *legal* requirement on anyone to do anything in particular. - but it is good manners to leave the name of the original author in the source code, and if the code is used in a commercial product, it is good manners to credit the original author in the documentation of the product. I was really hurt and outraged by this. ------------------------------ Date: 5 Feb 88 11:45:10 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Seen in a time-tabling program A couple of days ago, I saw the source code of a Prolog program for constructing school time-tables. While I have found enough bad things in it to keep me going for weeks, I should also tell you that the program apparently solves the problem its author's interested in, on the machine he has, fast enough to be useful, and is acceptable to the people who have to use it. For this message, I'll confine myself to discussing just one of the predicates. Each day has 8 periods. Teaching sessions come in two sizes: a session containing one period, and a session having two periods in succession. The sessions are enumerated in a table tim(a, 1). tim(b, 1). ... tim(h, 1). tim(ab, 2). tim(bc, 2). ... tim(gh, 2). This is not the predicate I'm interested in. The author had an extreme fondness for three-letter names, an equally excessive fondness for one-letter variable names, and an aversion to comments. As a result, I am still trying to work out what bus_cla_gro/4 does. One of the more frequent operations in the program is determining whether two sessions overlap. The program contains the following predicate to make this test: % ove(+Session1, +Session2) % is true when Session1 and Session2 (known to be names of % sessions) have a period in common. This is determined % by checking whether their names have any letter in common. ove(A, B) :- name(A, AL), name(B, BL), member(X, AL), member(X, BL). The comment there is mine: the actual program has no such comment. Now I don't know about you, but I can't like this. -- putting program-visible information in the names of atoms is, to say the least of it, odd. -- it doesn't generalise to multi-letter period names. -- it is inefficient in itself -- it causes the creation of structure (the lists AL, BL) which are of no real interest -- it can only be used to test given atoms, not to enumerate overlapping sessions -- it leaves a choice-point (actually, two!) behind, thus making the rest of the program less efficient. How else could we do this? Good relational data-base design suggests that for each entity type <foo> there should be a relation foo(A_Foo, ~attributes~) listing all the foos and their attributes. (I have worded this carefully. Check "entity" in a data-base textbook.) We would thus expect to see a table somewhere like session(a, ~something~). ... session(gh, ~something~). tim/2 is just such a table, except that it hasn't got the information we need. The first approach that suggests itself is to use bit-masks. We obtain a table such as session_bits(a, 2'10000000). session_bits(b, 2'01000000). ... session_bits(h, 2'00000001). session_bits(ab, 2'11000000). session_bits(bc, 2'01100000). ... session_bits(gh, 2'00000011). overlapping_sessions(Session1, Session2) :- session_bits(Session1, Bits1), session_bits(Session2, Bits2), Bits1 /\ Bits2 =\= 0. This is fully relational, doesn't leave any extra choice points around, and is *much* faster. But there are snags: -- some Prologs do not support the "Edinburgh Standard" bitwise operators /\ (logand), \/ (logor), \ (lognot). -- even those that do often have some smallish limit on integers, e.g. 14 bits (PDP-11 Prolog), 16 bits (some PC Prologs), 18 bits (DEC-10 Prolog), 28 or 29 bits (many modern Prologs), so this solution would not work if we tried to treat periods in different days as different periods (we'd need 8*5=40 bits). -- it is "overkill" to use a bit-mask when the only possibilities are 0--010--0 and 0--0110--0. -- it is hard to extract the "size" information from bitsets. In connexion with this last point, here is a function which computes the number of bits in a bit-mask. It is word-size independent. % bit_count(+Mask, ?Count) % is true when Mask is instantiated to a non-negative % integer and Count is the number of "1" bits in the % binary representation of Mask. bit_count(Mask, Count) :- integer(Mask), Mask >= 0, bit_count(Mask, 0, Count). bit_count(Mask, Count0, Count) :- ( Mask =:= 0 -> Count is Count0 ; Next is (Mask-1) /\ Mask, Count1 is Count0+1, bit_count(Next, Count1, Count) ). To return to our subject: teaching sessions aren't just any sort of set of periods, they are non-empty *intervals* of periods. So we can represent a session by a pair of numbers: the first period of the session and the last period of the session. We obtain % session(Session, First, Last) % is true when Session is an atom naming a teaching session, % First is an integer representing the first period of the % session, and Last is an integer representing the last % period of the session. The eight periods are represented % by the numbers 1 to 8. session(a, 1, 1). session(b, 2, 2). ... session(h, 8, 8). session(ab, 1, 2). session(bc, 2, 3). ... session(gh, 7, 8). % session_length(Session, Length) % is true when Length is the number of periods in Session. % The original program called this tim/2. session_length(Session, Length) :- session(Session, First, Last), Length is Last-First+1. % overlapping_session(?Session, +First, +Last) % is true when Session is the name of a session which % overlaps the interval [First,Last] of periods. overlapping_session(Session, GivenFirst, GivenLast) :- session(Session, SessionFirst, SessionLast), SessionFirst =< GivenLast, GivenFirst =< SessionLast. % overlapping_sessions(Session1, Session2) % is true when Session1 and Session2 are names of sessions % having at least one period in common. overlapping_sessions(Session1, Session2) :- session(Session1, First, Last), overlapping_session(Session2, First, Last). This will work for any representable number of periods. Not only that, but as we just saw with tim/2, other information needed by the program can be derived quite simply from this table. As a further test, there is another variant of tim/2 in the original program: tim_ava(D, T, U) :- recorded(day, day(D), _), tim(T, U), \+ fri_123(D, T, U). fri_123(f, a, 1). fri_123(f, b, 1). fri_123(f, c, 1). fri_123(f, ab, 2). fri_123(f, bc, 2). fri_123(f, cd, 2). I am not making this up! I couldn't! day->day/1 is a table of one- letter day names. It starts out in some funny order, and keeps being shuffled. I have no idea whether days can ever be dropped from the table. I can't replace it by a fixed table for this predicate, because in some parts of the program the order matters, and there is no indication as to whether this is one of them. Note that since T determines U, we don't really need to pass U back. We arrive at tim_ava(Day, Session) :- recorded(day, day(Day), _), day_periods(Day, First, Last), overlapping_session(Session, First, Last). day_periods(m, 1, 8). day_periods(t, 1, 8). day_periods(w, 1, 8). day_periods(h, 1, 8). day_periods(f, 1, 3). My first draft of this version tested Day against the literal "f" and FirstS against the literal 3, but that would have been a bad idea. The day_periods/3 table separates the bounds out cleanly and declaratively. Enough of hygiene. What's the payoff? In Quintus Prolog, if we scale the bit-mask version to 1.0, the "pure" version is 1.3 times slower the "name" version is 19 times slower. Since the pure version is so much cleaner, and simplifies other parts of the program, and is only 1.3 times slower, that's the one I'd pick. ------------------------------ Date: 10 Feb 88 21:58:22 GMT >From: kumar@sally.utexas.edu (Vipin Kumar) Subject: Tech. Reports: AND-parallelism & Intelligent Backtracking The following reports are available: (1) AND-parallel execution of Logic Programs on a Shared Memory Multiprocessor : A Summary of Results by Yow-Jian Lin and Vipin Kumar Abstract: This paper presents the implementation of an AND-parallel execution model of logic programs on a shared-memory multiprocessor. The major features of the implementation are (i) dependency analysis between literals of a clause is done dynamically without incurring excessive runtime overhead; (ii) backtracking is done intelligently at the clause level without incurring any extra cost for the determination of the backtrack literal; (iii) the implementation is based upon the Warren's Abstract Machine (WAM), hence retains most of the efficiency of the WAM for sequential segments of logic programs. Preliminary results on Sequent Balance 21000 show that our parallel implementation can achieve reasonable speedup on dozens of processors. (2) An Execution Model for Exploiting AND-Parallelism in Logic Programs by Yow-Jian Lin and Vipin Kumar. To appear in New Generation Computing, 1988. Also available as a Tech. Report, Artificial Intelligence Lab, Computer Science Department, University of Texas, Austin, Texas 78712. (3) A Data-Dependency Based Intelligent Backtracking Scheme for Prolog by Vipin Kumar & Yow-Jian Lin. To appear in Journal of Logic Programming, 1988. Also available as a Tech. Report, Artificial Intelligence Lab, Computer Science Department, University of Texas, Austin, Texas 78712. US Mail: Dr. Vipin Kumar Assistant Professor Computer science Department University of Texas at Austin Austin, TX 78712 ------------------------------ End of PROLOG Digest ********************