poole@cs.ubc.ca (David Poole) (02/12/91)
1. Does anyone know whether there is a Prolog that runs on NeXT computers? There are none listed in the NeXT software catalogue. Are there any under development? When will they be available? 2. I recently had the need for an efficient implementation of a priority queue. I wanted to add and remove element in log n time. The "normal" way (using an array called a "heap") that is taught in computer science courses is inappropriate for Prolog. This makes a very interesting exercise for a logic programming class. Try it. David
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/13/91)
In article <1991Feb12.013413.24312@cs.ubc.ca>, poole@cs.ubc.ca (David Poole) writes: > 1. Does anyone know whether there is a Prolog that runs on NeXT computers. You may be able to run binaries from some other 680x0 machines. Or try SB Prolog (but not _too_ hard). > 2. I recently had the need for an efficient implementation of a > priority queue. I wanted to add and remove element in log n time. The > "normal" way (using an array called a "heap") that is taught in > computer science courses is inappropriate for Prolog. Wrong. Heaps work very nicely indeed in Prolog. A file called HEAPS.PL is available in the DEC-10 Prolog library (see library(heaps) in the Quintus library). Your mistake is in identifying "heaps" with one particular *IMPLEMENTATION* of heaps using arrays. A heap is just a node-labelled binary tree with a constraint on the labels. I wouldn't go so far as to call this a trivial exercise, but it's not far off it. -- Professional programming is paranoid programming
stolcke@ICSI.Berkeley.EDU (Andreas Stolcke) (02/13/91)
In article <1991Feb12.013413.24312@cs.ubc.ca>, poole@cs.ubc.ca (David Poole) writes: |> |> 1. Does anyone know whether there is a Prolog that runs on NeXT |> computers? There are none listed in the NeXT software catalogue. Are |> there any under development? When will they be available? IF/Prolog (by InterFace Computer) runs on NeXT (as on almost any UNIX box). -- Andreas Stolcke stolcke@icsi.berkeley.edu International Computer Science Institute stolcke@ucbicsi.bitnet 1957 Center St., Suite 600, Berkeley, CA 94704 (415) 642-4274 ext. 126
poole@cs.ubc.ca (David Poole) (02/14/91)
> > 2. I recently had the need for an efficient implementation of a > > priority queue. I wanted to add and remove element in log n time. The > > "normal" way (using an array called a "heap") that is taught in > > computer science courses is inappropriate for Prolog. > > Wrong. Heaps work very nicely indeed in Prolog. A file called HEAPS.PL > is available in the DEC-10 Prolog library (see library(heaps) in the > Quintus library). Your mistake is in identifying "heaps" with one > particular *IMPLEMENTATION* of heaps using arrays. A heap is just a > node-labelled binary tree with a constraint on the labels. I wouldn't > go so far as to call this a trivial exercise, but it's not far off it. The file HEAPS.PL just adds evidence for my assertion! The reason that I posted it is that there is a neat solution that is very simple in Prolog, that one can get if one liberates one's mind from what is normally taught is the way to implement heaps. Here is a simple solution (written by D.Poole and M.Horsch): % In this section, we implement priority queues as a variant of a % heap, using Prolog-style trees. The empty queue is represented by % nil; otherwise the queue is represented recursively as pq(OBJ,LPQ,RPQ) % where OBJ is the data element, and LPQ & RPQ are the left and right % priority queues respectively. We assume an ordering over data % elements given by greater(E1,E2). OBJ is the data element with higher % priority than any element in either of LPQ or RPQ. % % In our priority queues, we maintain the following invariant: the right % subtree RPQ has either the same number of data elements or exactly one % more than the left subtree LPQ. This invariant assures that both the % depth of the tree is logarithmic in the size of the priority queue. % % There are two operations on priority queues: insertion and deletion. % % The insertion operation behaves as follows: insertPQ(X,Q1,Q2) is % true if inserting X into queue Q1 results in queue Q2. The % invariant is maintained by inserting data elements into the left % subtree of Q1, creating a new subtree. The new subtree is made % the right subtree of Q2, and the right subtree of Q1 becomes % the new left subtree of Q2. Note that if the new element has % higher piority than the element at the root of the queue, the new % element is made the root, and the old root element is inserted into % the queue. insertPQ(NV, nil, pq(NV,nil,nil)). insertPQ(NV, pq(V,LPQ,RPQ), pq(V,RPQ,NLPQ)) :- greater(V,NV), !, insertPQ(NV,LPQ,NLPQ). insertPQ(NV, pq(V,LPQ,RPQ), pq(NV,RPQ,NLPQ)) :- insertPQ(V,LPQ,NLPQ). % The deletion operation behaves as follows: % removePQ(Val,Q1,Q2) % is true if removing Val from priority queue Q1 results in the priority % queue Q2. Recall that the data element Val always has higher priority % than any element in its subtrees, and since it is being deleted, it % must be replaced by the element of next highest priority. The % predicate remany(Val,Q1,Q2) removes a node from the right subtree % (since we always remove from the right to maintain the invariant) and % puts it as the top element in the priority queue. This value is % pushed down through the queue with pushPQ(Q1,Q2), which pushes the % element down until the heap property is attained. Finally, we swap % subtrees, so that the left subtree is always at most one element % lighter than the right. removePQ(Val, pq(Val,nil,PQ),PQ) :- !. removePQ(Val, pq(Val,LPQ,RPQ),NPQ) :- remanyPQ(RMV,RPQ,NRPQ), pushPQ(pq(RMV,NRPQ,LPQ),NPQ). % The predicate pushPQ(Q1,Q2) is true if Q2 is a heap given a % "pseudo--heap" Q1. If LV, the element in the left subtree, is of % higher priority than both RV and Val, we exchange LV and Val, pushing % Val down the left subtree. Otherwise, if Val is greater than RV, then % we exchange these two, pushing Val down the right subtree. Note that % we are not adding or deleting elements, so we don't do any subtree % swapping. Finally, if Val is of higher priority than either RV or LV, % we are finished. pushPQ(pq(Val,pq(LV,PQLL,PQLR),pq(RV,PQRL,PQRR)), pq(LV,LPQ,pq(RV,PQRL,PQRR))) :- greater(LV,RV), greater(LV,Val), !, pushPQ(pq(Val,PQLL,PQLR),LPQ). pushPQ(pq(Val,LPQ, pq(RV,PQRL,PQRR)), pq(RV,LPQ,RPQ)) :- greater(RV,Val), !, pushPQ(pq(Val,PQRL,PQRR),RPQ). pushPQ(PQ,PQ). % We remove an element from a subtree using remanyPQ(V,LQ,RQ). This % predicate finds the right--most element which either has only a right % child, or is itself the right leaf of a node with two children. % Swapping occurs in the latter case. remanyPQ(Val, pq(Val,nil,PQ),PQ) :- !. remanyPQ(V, pq(Val,LPQ,RPQ), pq(Val,NLPQ,LPQ)) :- remanyPQ(V,RPQ,NLPQ).
mattias@arnold.csd.uu.se (Mattias Waldau) (02/16/91)
The Makefile of sicstus mentions NeXT. Academic institituions can get sicstus almost for free. It is a wonderful Prolog, Quintus compatible and includes coroutining (using freeze and dif). I have used it for several years. It is very reliable and fast. Contact sicstus@sics.se for more information. /mattias -- Mattias Waldau Computing Science Department mattias@emil.csd.uu.se P.O. Box 520, S-751 20 Uppsala, Sweden Phone: +46-18-181055