PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/07/86)
PROLOG Digest Monday, 9 Jun 1986 Volume 4 : Issue 17
Today's Topics:
Query - TRO & Micros,
Application - Income Tax Planning,
Implementations - Assert & DFID & Standard Behavior & Tricks
----------------------------------------------------------------------
Date: 3 Jun 86 19:59:24 GMT
From: MorrisseyTJ <tim@ucbvax.berkeley>
Subject: TRO in C-Prolog
Has anyone implemented TRO (tail recursion optimization)
for C-Prolog?
-- Tim Morrissey
------------------------------
Date: 6 Jun 86 02:12:05 GMT
From: FJ Hirsch <fjh@ucbvax.berkeley.edu>
Subject: prolog for ibm pc?
I am looking for information about Turbo Prolog or
other implementations of prolog for the IBM PC
(AT&T 6300). Pointers to reviews or personal
experiences would be appreciated.
Thank you.
------------------------------
Date: 3 Jun 86 14:46:00 GMT
From: pur-ee!uiucdcs!uicsl!gooley@ucbvax.berkeley
Subject: looking for Prolog
UNSW Prolog is *not* a variant of C-Prolog. It was
developed independently,has a slightly different
syntax, behaves quite differently in some situations,
does not try to fake a tagged architecture, lacks
many bells and whistles, and (according to a letter
in a recent issue of "Computer Architecture News"
[the ACM SIGARCH bulletin]) is about half as fast
when run on a VAX-11/780. Its chief advantages are
simplicity, modularity (relatively easy to modify
for instrumentation, except that the source lacks
comments), and portability. It's my opinion that
it will run on any 32-bit machine under UNIX with
only trivial changes, and, with a little work, on
anything that has a C compiler (I ported it to our
Gould PN9050 and had only to change a few pathnames).
------------------------------
Date: 3 Jun 86 18:13:28 GMT
From: MorrisseyTJ <ihnp4!drutx!druhi!tim@ucbvax.berkeley>
Subject: "assert" considered harmful?
In article <1229@lsuc.UUCP>, dave@lsuc.UUCP writes:
> Saumya Debray mentioned recently on the net
> that good Prolog programmers don't make much use of
> assert and retract. [text deleted]
> When I look at the logic, I find it's doing the same
> analysis over and over for certain legal conclusions
> that are really "facts" for other rules to deal with.
> [text deleted]
> Once I've determined that T1 controls T2, should I
> "asserta" that as a fact, so it no longer needs to
> take much time? [text deleted]
Is this an example of lemmas?
I would like to believe that a formal mechanism for managing
and applying previously proved goals could significantly
improve the speed of large programs. However, I do see many
issues like:
- knowing when the lemmas are no longer valid
- making the time cost cheap enough to cause overall speedup
- keeping the space cost "low enough"
- knowing when *not* to store lemmas (I/O, external conditions)
Although it is easy to misuse assert and retract, I think
Prolog is very valuable as a database language. Databases
for practical applications can easily have dozens of relations
and change very often.
Something I find dearly missing from Prolog are uniform
semantics for side-effects. It seems "ugly" that applications
and even Prolog support code use predicates like:
set_xxx(Value)
get_xxx(Value)
or
add_xxx(Key,Value)
find_xxx(Key,Value)
del_xxx(Key)
Just some food for thought.
-- Tim Morrissey
------------------------------
Date: 28 May 86 20:22:00 GMT
From: pur-ee!uiucdcs!uiucdcsb!goldfain@ucbvax.berkeley
Subject: Income Tax Planning
Your "aggregate" predicate looks pretty clever to me ... it
certainly uses some of the deeper concepts of Prolog
(functor-building and calling, etc.) I can suggest one
improvement in elegance, since you mention you wrote a new
aggregate predicate for each number of arguments. You could
rewrite aggregate to always expect three arguments, the first
is the "Goal" as before, the second "ArgList", and the third
"Aggr" to hold the result. Then you could use this form for
goals with any number of arguments:
aggregate(Goal, ArgList, Aggr) :-
append([Goal | ArgList], [Amount], Funct),
Z =.. Funct,
findall(Amount, call(Z), List),
listtotal(List, Aggr).
I haven't actually tried this code, but something
close to it should work. I am using UNSW Prolog,
here.
As to your other question, here is some code that works
for me.
This is the function you want: group([a, b, c, d], X)?
returns X instantiated to the list of all subsets of
[a, b, c, d] excepting the null set, singleton sets,
and the set [a, b, c, d] itself.
groups([], []).
groups([H | T], Result) :-
length([H | T], Full),
powerset([H | T], Sets),
filter(Full, Sets, Result).
This takes a set (written as a list) as its first argument
and returns the set of all NONEMPTY subsets of it in its
second argument. Example:
powerset([a, b, c], X)? gives :
X = [[c], [b,c], [b], [a,c], [a,b,c], [a,b], [a]]
argument. Warning: it returns with every member of the
power set EXCEPT the null set. (It does return the set
itself as one of the subsets, unless the set itself is
the null set.)
powerset([], []).
powerset([H | T], Result) :-
powerset(T, Set1),
include(H, Set1, Set2),
append(Set1, Set2, Result).
This builds a new "powerset" from a new element and a
"sub-powerset".
include(Item, [], [[Item]]).
include(Item, [H | T], [[Item | H] | Rest]) :- include(Item, T, Rest).
A very-often used predicate, which should be pre-defined.
append([], X, X).
append([H | T], X, [H | Rest]) :- append(T, X, Rest).
The "powerset" routine returns too much for our purposes,
so we filter out singleton sets and the whole set.
filter(_, [], []).
filter(Full, [Set | More], Result) :-
length(Set, 1), !, filter(Full, More, Result).
filter(Full, [Set | More], Result) :-
length(Set, Full), !, filter(Full, More, Result).
filter(Full, [Okay | More], [Okay | Rest]) :- filter(Full, More, Rest).
------------------------------
Date: 28 May 86 14:21:47 GMT
From: Micha Meier <!micha@ucbvax.berkeley.edu>
Subject: Depth First Iterative Deepening
Some points to a possible implementation of DFID search
in Prolog:
1] The DFID algorithm always finds the solution; so does
a useful Prolog program, unless it goes into an infinite
loop. This means that DFID can never find a solution in
a shorter time than the usual Prolog: either Prolog's
depth-first search is faster or Prolog fails to find
anything and it loops. The same holds then for a parallell
implementation of DFID, it could only be a way to prevent
infinite loops in a better time than a serial DFID rather
than speeding up the search in comparison with Prolog.
2] DFID always finds the optimal solution, the usual Prolog
finds *any* and maybe all solutions if necessary. If the
user wants to find all solutions and the usual Prolog loops,
DFID will loop as well; therefore the use of DFID could be
only restricted.
3] As Max says, the predicates would have to be divided into
two groups, ordered and unordered; this would be the case
in any non-sequential processing of the subgoals. If we allow
ordered predicates to call the unordered ones and vice versa
then the distribution of processors in a parallell execution
is no more so easy. There is maybe a simple solution to this
problem, otherwise one direction of calls between the two
classes of predicates must be forbidden - is it a significant
restriction?
-- Micha
------------------------------
Date: 28 May 86 14:57:47 GMT
From: Max Hailperin <!max@ucbvax.berkeley.edu>
Subject: Depth First Iterative Deepening
Micha's comments aren't all wrong, but they certainly aren't
100% correct either. The big point he misses is this:
If there is a branch of the tree to the left of the solution
that is much deeper than the solution, but still finite, DFID
is more efficient than depth-first search.
This -- not questions of completeness -- is the argument for
DFID which interests me. Naturally this case only arises in
some class of programs, but that's the point -- I'm curious
whether that class of programs is interesting.
The point about ordered and unordered predicates calling each
other is a bit confused. In reality there is no problem. If
an unordered predicate calls an ordered predicate, and that
ordered predicate fails because its execution was truncated,
some solutions to the unordered predicate are lost -- but
this doesn't matter. If an ordered predicate calls an unordered
predicate, and the execution is truncated, the outer ordered'
predicate fails, because of the general rule I proposed in my
last note. Thus the right thing always happens.
Much of the time all the programmer wants is one solution, any
solution. In this case it doesn't matter whether it is the
leftmost or shallowest (= "optimal"). If we can get the
shallowest faster than the leftmost (or if they are the same,
and we can get it faster by looking for the shallowest), than
that's good.
Naturally if you really want all solutions, DFID has nothing
to offer. This can be viewed as a consequence of my execution
rule for bagof.
By the way, the proposed modified Prolog does not offer one
control structure DFID can support that has been proposed in
the context of other parallel Prologs: an unordered, one-solution
predicate.
------------------------------
Date: 28 May 86 12:38:26 GMT
From: Max Hailperin <!max@ucbvax.berkeley.edu>
Subject: Depth First Iterative Deepening
George Van Treeck raised the interesting question of
depth-first iterative-deepening (DFID) search's applicability
to Prolog execution in general and parallel execution in
particular. A quick check with the gurus around here
(ECRC is a major center of Prolog activity) came up with no
knowledge of any existing literature on DFID and Prolog. But
of course there might be some. What follows are my own comments,
in the absence of any literature.
DFID could be integrated into a Prolog interpreter. The language
it interpreted would have to be a bit modified, as the standard
Prolog control structures and side-effect primitives wouldn't
work. The smallest possible change in language definition (I
think) would be:
- declaration of ordered vs. unordered predicates
- cuts only allowed in ordered predicates
- no side-effects (assert, retract, I/O).
The three non-obvious points in the design of such an
interpreter are
- negation as failure
- bagof
- ordered predicates.
The implementation of these three features has to take as
its guiding rule: truncating the search at a particular depth
may only eliminate solutions, never add any. Concretely this
means that when executing not(X), you have to keep a record of
whether the cutoff-depth is reached in executing X. If so,
then not(X) should fail even if X failed. This is because X
might have succeeded given a greater cutoff-depth. The same
technique is necessary for bagof: if it is possible that not
all members of the bag were found, the bagof should fail.
Similarly, if a clause of an ordered predicate fails, but had
been prematurely truncated by the cutoff-depth, the whole
predicate should fail, even if clauses remain.
The next question is whether DFID would do any good. In
today's Prolog programs it wouldn't, because the average
branching factor is extremely low (between 1 and 2). The
graph in the article in Artificial Intelligence shows quite
clearly how big a loss DFID search is with such a low
branching factor. Moreover Prolog programmers are very
clever about always putting the easiest clauses first, and
also use non-logical constructs to direct the search.
Prolog execution is not a brute-force search in a
well-balanced tree. So for normal Prolog programs, DFID
would make the execution slower rather than faster.
Whether the class of programs no one writes with today's
Prologs but would write if they had a DFID Prolog is an
interesting class of programs is an open question. Note,
however, that DFID can also be used for only those portions
of a program which would benefit from it. There have also
been proposals for adding heuristic control information to
Prolog's search. This would encourage programmers to use
Prolog's built-in search rather than programming their own.
Thus some amount of optimism about DFID's applicability
may be justified.
Finally comes the question of parallel execution (my own
specialty). *If* DFID were useful (see the paragraph above),
or in fact if it even came close to the performance of normal
depth-first search, then a parallel version could be a
practical way of exploiting parallel processing for logic
programming. For example, if we could find interesting
programs that a DFID Prolog executed at half the speed of
normal Prolog, then by using 20 processors we could hope to
get an order-of-magnitude speedup over normal Prolog.
This possibility is so interesting because DFID has an
extremely easy, low overhead parallel version. The idea is
that each depth-first search is still sequential, but the
search for the proper depth is done in parallel. This "DFPD"
(depth-first parallel-deepening) strategy might for example
have processor A search to a depth of 1 in parallel with
processor B searching to a depth of 2. As soon as A is done,
it starts searching to a depth of 3. In general: each time
a processor is free, it starts a depth-first search with
the next untaken cutoff-depth. This has a much lower
communication and coordination overhead than OR-parallel
Prologs.
Returning to my original caution: DFPD is only a speedup
over DFID, *not necessarily* over other forms of search.
With a finite number of processors, there will be many
realistic programs (virtually all of today's Prolog
programs) for which even a normal single-processor
depth-first search will be faster than DFPD. (In the
infinite-processor case DFPD can be no worse than
depth-first search.) Thus this is only a useful use of
parallelism if we write programs for which DFID performs
at least comparably to depth-first search.
Conclusions:
1] a DFID Prolog is easily implementable, though not for
normal Prolog.
2] today's Prolog programs would not benefit from DFID
(in fact, they would suffer)
3] it is possible that conclusion 2 can be changed
(particularly if Prolog is extended to accept heuristic
control information)
4] if conclusion 2 were changed, generalizing DFID to DFPD
would be an easy way to make use of parallel processing
(actually it's not necessary that conclusion 2 be changed
-- DFID need only approach depth-first search in efficiency,
not surpass it)
------------------------------
Date: 2 Jun 86 19:05:50 GMT
From: decwrl!vantreeck@logic.dec.com@ucbvax.berkeley
Subject: Flames about a DFID question
>1] The copious use of cut in PROLOG indicates that
>programmers are frequently interested in only a
>single, first, solution. I thought perhaps DFID
>might be a way of finding a single, first solution
>in very large PROLOG search spaces.
>For example, a program to synthesize new chemicals
>might be find DFID useful for finding the shortest
>synthesise pathway (very large branching factor in a
>very large search space).
The last note wasn't clear about finding solutions
with DFID. I didn't mean to imply that DFID would only
find one solution. DFID could easilly backtrack and
find the next most least cost solution. I just meant
that it might be a quicker way to find that first single
solution in cases cases where the search space is very
large.
--George
------------------------------
Date: 2 Jun 86 18:10:43 GMT
From: decwrl!vantreeck@logic.dec.com@ucbvax.berkeley
Subject: Flames over a DFID question
>(I suspect anyway that this is another of George's
>attempts to bring flames into the network, right? :-)
No! I was just asking questions. I don't understand why
asking if an algorithm (DFID) is applicable to parallel
PROLOGs should be construed as an attempt to raise
tempers. My reasons for asking were:
1] The copious use of cut in PROLOG indicates that
programmers are frequently interested in only a single,
first, solution. I thought perhaps DFID might be a way
of finding a single, first solution in very large PROLOG
search spaces. For example, a program to synthesize new
chemicals might be find DFID useful for finding the
shortest synthesise pathway (very large branching factor
in a very large search space).
2] I've heard logicians complain that PROLOG doesn't
adhere to logic because the order of rules should not
affect whether a proof is found, e.g., sometimes
PROLOG programs go into an endless recursion if the rules
aren't ordered correctly. I never expected flames because
an algorithm like DFID might search and find a proof
regardless of the ordering of rules (was that the flame?).
I thought a predicate called 'dfid/1' could act sort of
like 'call/1' where the proof of dfid would use a different
search strategy (assumes there is no order dependent code
in the proof of DFID).
I'm ignorant about parallel or concurrent implementations
of PROLOG and was just seeking enlightenment -- not flames.
Thank you for the thoughtful replies; they were very
helpful. The replies seem to indicate that most PROLOG
programs have a very small branching factor which would
make DFID more of liability than an asset.
-- George Van Treeck
DEC
------------------------------
Date: 1 Jun 86 23:10:42 GMT
From: Tom Blenko <hplabs!sdcrdcf!burdvax!blenko@ucbvax.berkeley>
Subject: Standard behavior?
In article <1163@sicsten.UUCP> lhe@sicsten.UUCP (Lars-Henrik
>Eriksson) writes:
>In article <1021@watdragon.UUCP> rggoebel@watdragon.UUCP
>writes:
>>I don't believe that cut, var, and nonvar cannot be
>>described logically, just because they aren't in Prolog
>>implementations.
>The reason why cut, var and nonvar cannot be "described
>logically" is that they are non-logical (or meta-logical,
>if you wish) primitives,
>that is primitives used to control the search for proofs.
The meaning of these primitives are dependent of the
particular way an implementation looks for proofs. With a
different implementation you could be forced to give a
different meaning to cut, var and nonvar, or even find
that they couldn't be given any meaning at all.
I disagree with the latter comment. If call() and negation
-by-failure are provided, I claim that you can define
if-then-else() (with your favorite syntax, say P->Q;R),
and that if-then-else() is more expressive than cut().
In particular, you need a scoping construct for cut()
to make it as expressive as if-then-else().
It is a short exercise to show that that var() and
nonvar() can be expressed using call() and cut()
(or if-then-else()).
So the discussion reduces to establishing the logical
or non-logical character of call() and negation-by
-failure(). I will speculate that the meaning of
call() can be captured by a suitable application of
first-order logic, due to its definition in terms of
constructive proofs (I have something along the lines
of Perlis' AIJ (1985) article in mind here). I am
side-stepping the problem of incompleteness of
logic-programming interpreters w.r.t resolution.
-- Tom
------------------------------
Date: 2 Jun 86 14:00:24 GMT
From: Saumya Debray <debray@ucbvax.berkeley.edu>
Subject: Standard behavior? (semantics of nonlogical primitives)
>In article <1021@watdragon.UUCP> rggoebel@watdragon.UUCP writes:
>>I don't believe that cut, var, and
>>nonvar cannot be described logically, just because they aren't
>>in Prolog implementations.
>
>The reason why cut, var and nonvar cannot be "described
>logically" is that they are non-logical (or meta-logical,
>if you wish) primitives, that is primitives used to
>control the search for proofs.
Perhaps you mean "... cannot be described logically using
first order predicate calculus".
>The meaning of these primitives are dependent of the
>particular way an implementation looks for proofs. With a
>different implementation you could be forced to give a
>different meaning to cut, var and nonvar, or even find that
>they couldn't be given any meaning at all.
If the constructs are in any way "understandable", you ought
to be able to find mathematical models for them. In the case
of "cut", "var" etc. there's a good chance these won't look
like the Herbrand models we Prolog hackers are accustomed to,
of course, but that's rather different from saying that they
couldn't be given any meaning at all.
There has, in fact, been some work on giving the semantics
of Prolog (i.e. textual order on literals and clauses + Cut)
using classical denotational semantics, in terms of continuous
functions over CPOs.
References are:
- Jones & Mycroft,
"Stepwise Development of Denotational and Operational
Semantics for Prolog", Proc. 1st ISLP, Atlantic City,
Feb 1984.
- Debray & Mishra,
"Denotational and Operational Semantics for Prolog",
Proc. Conf. on Formal Description of Programming
Concepts, Lyngby, Denmark, Aug 1986 (to appear).
-- Saumya Debray
------------------------------
Date: 27 May 86 23:03:59-EDT (Tue)
From: Zerksis D. Umrigar <Zerksis%sutcase.bitnet@WISCVM.WISC>
Subject: Hacker Tricks
Some hacks of dirty Prolog which come to mind...
a] Creating a term with fresh variables - assert and then
retract it from the database. Depending on your Prolog
implmentation, it may be slower than ripping the term apart
(using =..) and sticking in fresh variables.
b] Using lists and search-trees with unbound variables
representing the empty list/search-tree. Some time ago, I ran
tests on DEC-10 Prolog to compare this with cleaner structures
(using [] and say 'empty'). I found that the cleaner code was
better in both memory and time! Hence this is definitely a
useless hack. However using unbound tails for difference-lists
is definitely worthwhile.
c] The following is a rather special purpose hack, but may be
useful. Given variable-free terms, one needs to keep track of
which equivalence classes they belong to. The user asserts
equality (say a=b), to make the program record the fact that
terms 'a' and 'b' belong to the same equivalence class. The u
ser can also query equality (say a?b) to ask the program
whether 'a' and 'b' belong to the same equivalence class.
The solution is to store the name of its equivalence class along
with each term - however, use an unbound logical variable for
the name of each equivalence class. When an equality is asserted,
use Prolog's unification to bind the two unbound variables
representing the names of the eq. classes together. To query
equality, use == to check whether the names of the two eq.
classes are the same.
In the worst case, linear reference chains would be created,
resulting in time linear in the number of asserted equalities
when answering an equality query. This compares with lg(n)
time for Tarjan's Union-Find algorithm. However, the above
method is extremely simple to program in Prolog, the worst-case
may not occur too often for a particular application and the
constant associated with the above time estimates will probably
be smaller than for an implementation of Tarjan's algorithm.
d) Thinking of the lack of occurs check as a "feature" rather
than a bug of Prolog (there is a paper by Colmerauer on infinite
trees in Logic Prog. ed. by Clark & Tarnlund). The best
application I found of this "feature" was to create recursive
(looping) binding environments when writing an interpreter for
Henderson's Lispkit Lisp.
Finally, a question, possibly related to (d).
Prolog seems ideally suited to manipulate tree-structured
data. Is it possible to handle doubly-linked structures?
- one in which one can access equally easily a "parent"
from its "child" and a "child" from its "parent". I can
use unification without the occurs check to create such
structures. However, in the absence of destructive assignment
in Prolog, updating part of the structure seems to imply
updating the entire structure. I find that rather unsatisfactory.
One can get around this problem by using lists with unbound
vars as tails (as in b) to hold the lists of "parents" and
"children" of a node. However, deleting a node gets messy:
my solution is to use a logical var. as a boolean - unbound
= 'not deleted' and bound = 'deleted'. Is there a cleaner
solution?
------------------------------
End of PROLOG Digest
********************