Deutsch.PA@PARC-MAXC.ARPA (01/24/84)
I like the scheme with multiple versions of arrays very much. The semantics are exactly those of copying on every update, except that the implementation is "rooted" at the most recent version, so you pay only for historical references.
Cohen%UCBDali%Berkeley@sri-unix.UUCP (01/24/84)
From: Cohen%UCBDali@Berkeley (Shimon Cohen)
I was impressed by Ken letter in the Digest V2 #4. For a
few months now I am trying to do a similar thing. My main
concern is the inefficient implementation of sets in Prolog.
It seems that sets as lists are simple but rather clumsy
when you access the set randomly (different element each
time). If you are honestly trying to make Prolog a useful
language then you might consider the following ideas:
"Extensions"
Instead of using the 'setof' or 'bagof' functions which
really do not return "sets" or "bags" (but a list of all
elements in the "set" / "bag") we propose to introduce a
rather familiar data-type namely a \f3set\f1. A real set
will be implemented in the most efficient way (most of the
time as an hash-table, but maybe as a list or bit array)
depending on it's characteristics. The way this new (?)
data-type is going to be used is as follows:
(1) set_of_all( E, P, S).
Which is the same as the familiar 'setof' function except
that S is a "real" set.
(2) one_of(E,S).
Read this as: " E is a member of the set S". The problem in
(2) is that we can't get hold of the rest of the set S. To
allow it we introduce:
(3) one_of(E,S,Sr).
Either S or Sr must be instantiated:
case 1 - Only S is instantiated
Then: E is an element of the set S where Sr is the new set
resulting from the deletion of E from the set S.
case 2 - S and E are instantiated
Then: if E is in S then as the above otherwise fail.
case 3 - Sr is instantiated and E is instantiated
Then: S is the result of adding E to the set Sr.
If S is a list (as in ordinary Prolog) generated for example
by 'setof' then one can easily access one element and the
rest of the elements by using list constructor: [ E | Sr ].
Sets as lists are very simple but can become very inefficient
when dealing with big sets and big set operations like:
intersection or union. If we maintain the set as an hash
-table then The Question is;
" Are we really going to copy S to Sr (excluding E) every
time we execute one_of(E,S,Sr) ?"
I had a scheme of handling this problem rather efficiently,
I also implement it in CProlog as a test program (if you are
interested I will mail it to you). The idea is simply to
attach to eac:PN~h element the "time" when this element is
"dead" or "alive". Each set has sort of internal clock which
is modified whenever we create new pointer to this set.
The overhead for new set pointer is in most cases constant.
In addition we add (as I mentioned ) the dead-or-alive info
to the element.
Example: setof(E,S,Sr).
S is a pointer to a set and E,Sr are variables. We attach to
E one of the element of S. Sr is a new pointer to the set Sr
therefor we increase the internal clock of the set and attach
' dead(Time)' to element E. Since S is a pointer with a different
"time" then E is still alive for S but dead for Sr. (If you are
confused I can send you the test program)
Lets see how we create new sets:
(4) set(S,Specs).
Read this as follows: "S is the set with the Specs specifications"
Where Specs is a list with the following possible items (non is
required):
size(N) -
approximate size of set (the actual size can be bigger) which
help to decide on the size of the hash-table.
integer(N1,N2) -
The set consists of integer numbers in the range of N1..N2.
It might help the compiler to decide whether to implement
it as a bit array.
list(L) -
L is a list of atoms that serve as the base set for the set S.
for example: [sunday,monday,tuesday,wednesday,thursday,friday,
saturday]
base(BaseS) -
BaseS is an existing set which is the base set of the set S.
Etc. Comments ?
-- ShimonCohen%UCBDali%Berkeley@sri-unix.UUCP (01/24/84)
From: Cohen%UCBDali@Berkeley (Shimon Cohen)
I was impressed by Ken letter in the Digest V2 #4. For a
few months now I am trying to do a similar thing. My main
concern is the inefficient implementation of sets in Prolog.
It seems that sets as lists are simple but rather clumsy
when you access the set randomly (different element each
time). If you are honestly trying to make Prolog a useful
language then you might consider the following ideas:
"Extensions"
Instead of using the 'setof' or 'bagof' functions which
really do not return "sets" or "bags" (but a list of all
elements in the "set" / "bag") we propose to introduce a
rather familiar data-type namely a \f3set\f1. A real set
will be implemented in the most efficient way (most of the
time as an hash-table, but maybe as a list or bit array)
depending on it's characteristics. The way this new (?)
data-type is going to be used is as follows:
(1) set_of_all( E, P, S).
Which is the same as the familiar 'setof' function except
that S is a "real" set.
(2) one_of(E,S).
Read this as: " E is a member of the set S". The problem in
(2) is that we can't get hold of the rest of the set S. To
allow it we introduce:
(3) one_of(E,S,Sr).
Either S or Sr must be instantiated:
case 1 - Only S is instantiated
Then: E is an element of the set S where Sr is the new set
resulting from the deletion of E from the set S.
case 2 - S and E are instantiated
Then: if E is in S then as the above otherwise fail.
case 3 - Sr is instantiated and E is instantiated
Then: S is the result of adding E to the set Sr.
If S is a list (as in ordinary Prolog) generated for example
by 'setof' then one can easily access one element and the
rest of the elements by using list constructor: [ E | Sr ].
Sets as lists are very simple but can become very inefficient
when dealing with big sets and big set operations like:
intersection or union. If we maintain the set as an hash
-table then The Question is;
" Are we really going to copy S to Sr (excluding E) every
time we execute one_of(E,S,Sr) ?"
I had a scheme of handling this problem rather efficiently,
I also implement it in CProlog as a test program (if you are
interested I will mail it to you). The idea is simply to
attach to each: PN element the "time" when this element is
"dead" or "alive". Each set has sort of internal clock which
is modified whenever we create new pointer to this set.
The overhead for new set pointer is in most cases constant.
In addition we add (as I mentioned ) the dead-or-alive info
to the element.
Example: setof(E,S,Sr).
S is a pointer to a set and E,Sr are variables. We attach to
E one of the element of S. Sr is a new pointer to the set Sr
therefor we increase the internal clock of the set and attach
' dead(Time)' to element E. Since S is a pointer with a different
"time" then E is still alive for S but dead for Sr. (If you are
confused I can send you the test program)
Lets see how we create new sets:
(4) set(S,Specs).
Read this as follows: "S is the set with the Specs specifications"
Where Specs is a list with the following possible items (non is
required):
size(N) -
approximate size of set (the actual size can be bigger) which
help to decide on the size of the hash-table.
integer(N1,N2) -
The set consists of integer numbers in the range of N1..N2.
It might help the compiler to decide whether to implement
it as a bit array.
list(L) -
L is a list of atoms that serve as the base set for the set S.
for example: [sunday,monday,tuesday,wednesday,thursday,friday,
saturday]
base(BaseS) -
BaseS is an existing set which is the base set of the set S.
Etc. Comments ?
-- ShimonClocksin%EDXA%UCL-CS@sri-unix.UUCP (01/26/84)
From: Bill (on ERCC DEC-10) <Clocksin%EDXA@UCL-CS> Readers of the Prolog Digest interested by Ken's announcement of efficient array implementations in Prolog may care to inspect Richard O'Keefe's similar implementation which has resided in SCORE's Prolog Library for some considerable time. Readers of Ken's announcement may have been misled into thinking that only LM-Prolog offers strings implemented as packed byte arrays. I can think of two others off hand, namely POPLOG (from Sussex), and Prolog-X (from Cambridge (England)). -- W F Clocksin