Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!SU-SCORE.ARPA!PROLOG-REQUEST
From: PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator)
Newsgroups: net.lang.prolog
Subject: PROLOG Digest   V4 #16
Message-ID: <8606070023.AA03050@ucbvax.Berkeley.EDU>
Date: Fri, 6-Jun-86 09:18:00 EDT
Article-I.D.: ucbvax.8606070023.AA03050
Posted: Fri Jun  6 09:18:00 1986
Date-Received: Sun, 8-Jun-86 04:48:44 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: PROLOG@SU-SCORE.ARPA
Organization: University of California at Berkeley
Lines: 688


PROLOG Digest             Friday, 6 Jun 1986       Volume 4 : Issue 16

Today's Topics:
                       Announcement - New book,
             Queries - References & Reduce & Test Suite,
                Implementation - Income Tax Planning,
          & Depth First Iterative Deepening & Logical Vars,
      "assert" & Harm & Duplicate Solutions & Standard Behavior,
                  & Standard behavior & \+ \+ hack,
                      Humor - Prolog programmers
----------------------------------------------------------------------

Date: 16 May 86 19:25:00 GMT
From: Mozetic@ucbvax.berkeley.edu
Subject: New book

Addison-Wesley published a new book:

            Prolog Programming for Artificial Intelligence
                            by Ivan Bratko

The first part introduces Prolog and shows how Prolog programs
are developed.

The second part applies Prolog to some central areas of AI,
and introduces fundamental AI techniques through complete
Prolog programs. Throughout the book there is a lot of
exercies and sample programs. The following is a table of
contents:

THE PROLOG LANGUAGE
 1. An Overview of Prolog
 2. Syntax and Meaning of Prolog Programs
 3. Lists, Operators, Arithmetic
 4. Using Structures: Example Programs
 5. Controlling Backtracking
 6. Input and Output
 7. More Built-in Procedures
 8. Programming Style and Technique

PROLOG IN ARTIFICIAL INTELLIGENCE
 9. Operations on Data Structures
10. Advanced Tree Representations
11. Basic Problem-Solving Strategies
12. Best-first: A Heuristic Search Principle
13. Problem Reduction and AND/OR Graphs
14. Expert Systems
15. Game Playing
16. Pattern-Directed Programming

------------------------------

Date: 25 May 86 14:25:38 GMT
From: Jacob Levy <Jaakov@ucbvax.berkeley.edu>
Subject: Request for information

Dear fellow AIListers and PrologListers,

I'm interested in obtaining the latest references you
may have to articles concerned with Parallel Logic
Programming languages. If  you have recently written
an article concerned with parallel execution of Prolog
or about a committed-choice non-deterministic LP language,
I'm interested to read it, or at least to receive a
pointer to the article. By RECENT I mean articles which
have been published in 1985 and 1986 or which are about
to appear. I am interested in any and all sub-topics of
the fields listed above.

Thank you very much ahead of time for your response,

-- Jacob Levy (Rusty Red)

------------------------------

Date: 24 May 86 01:43:00 GMT
From: decvax!ima!inmet!bhyde@ucbvax.berkeley.edu
Subject: Reduce?

Consider this.
   : plus_reduce([1,2,3],Result)?
   N = 6.
   :
Not too hard to write.

But what if I want to write a more general reduce
like this one:

: reduce( 0, % Intial value
   Left, Right,   % Input variables in the subexpressions
   InnerResult is Left + Right, % The unit reduction.
   InnerResult,                 % Result of subexpressions.
             [1, 2, 3], Result )?
   N = 6.
   :

I am unable to see how to write this (with out asserting
a new clause during the execution).

This is a very general function once you have it.  Any
ideas?

-- Ben Hyde,
   Cambridge

------------------------------

Date: 3 Jun 86 18:48:34 GMT
From: KDJ <sdcsvax!ncr-sd!se-sd!kdj@ucbvax.berkeley.edu>
Subject: Test suite wanted

We are looking for test suites for Prolog compilers.  We
are interested in any available test suite, either public
domain or commercial.  Please send any information you
have to me.

Thanks you for any help.

-- Doug Johnston
   NCR

------------------------------

Date: 20 May 86 03:57:34 GMT
From: David Sherman <ulysses!burl!clyde!watmath!utzoo
Subject: Income Tax Planning

First, thanks to everyone who responded to my plea for help
in avoiding circularity in my definition of tptype. Most people
suggested using two different predicates, one for stated facts
and one for conclusions. It turns out not to be quite so simple,
but I think that suggestion contains the seeds of the solution
I need. I'm still working on finalizing it.

Second, I've developed an interesting predicate which I call
"aggregate" which I'd like to share with the net. It comes from
the tendency of the Income Tax Act to say things like "the
aggregate of his taxable capital gains for the year". I wanted
to be able to take an arbitrary predicate which puts a number
into its last argument, call it as many times as will succeed,
and total up the numbers. Thus, if I have

        taxablecapitalgain(Taxpayer, Year, TCG)

which itself is defined in terms of more basic things
(like transactions, dispositions, proceeds, cost and
so on), then I can say

        aggregate(taxablecapitalgain, fred, 1986, Aggr).

and get fred's 1986 taxable capital gains returned in Aggr.

Here's my code. I have no idea whether it will be useful to
anyone, but I'm curious as to what those more experienced
with Prolog think of it. It's probably either ingenious or
stupid, but it does work. It uses the "findall" predicate
from Clocksin & Mellish chapter 7.

        aggregate(Goal, Arg1, Arg2, Aggr) :-
                Z =.. [Goal, Arg1, Arg2, Amount],
                findall(Amount, call(Z), List),
                listtotal(List, Aggr).

(3 other copies of "aggregate" exist, one with only
Arg1, one with Arg1, Arg2, Arg3, and one with 4
arguments for the Goal other than the final Amount.)

        listtotal([], 0).
        listtotal([H|T], Total) :-
                integer(H),
                listtotal(T, Ttotal),
                Total is H + Ttotal.

Third, I'm currently wrestling with the task of generating,
for a list, every list which is a subset of that list. Thus,
for [a,b,c,d], I want findall to be able to find each of
[a,b] [a,c] [a,d] [a,b,c] [a,b,d] [a,c,d] [b,c] [b,d]
[b,c,d] [c,d].

I've played with it for a while and can't get a handle on
the approach to take. Can anyone help? (The application is
generating every possible group of taxpayers from the list
of those who own shares in a corporation, so as to determine
whether any of them is a "related group" as defined in the
Act.)

Incidentally, if anyone is interested in knowing more about
my project, I'll be happy to mail or post more. It's a
comprehensive corporate tax planning system based on the
Canadian Income Tax Act.

-- Dave Sherman

------------------------------

Date: 30 May 86 23:44:50 GMT
From: ulysses!mhuxr!mhuxn!mhuxm!mhuxf!mhuxi!mhuhk
Subject: Income Tax Planning system

> From: dave@lsuc.UUCP
> Subject: miscellany re income tax planning system
> ...
> Third, I'm currently wrestling with the task of generating,
> for a list, every list which is a subset of that list. Thus,
> for [a,b,c,d], I want findall to be able to find each of
> [a,b] [a,c] [a,d] [a,b,c] [a,b,d] [a,c,d] [b,c] [b,d]
> [b,c,d] [c,d].

As a first attempt to solve your problem, you could use the
following "included(X,[a,b,c,d])" predicate:

/* included(Set,SuperSet). True if all elements of Set in
/* SuperSet, whatever the order of the elements is.
*/

    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        del(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

However, this predicate generates all the permutations of
the possible solutions (i.e. [a,b,c] and [a,c,b] will be
generated among other solutions).  To eliminate these
permutations, you can use a slightly different version of
the "del" predicate:

/* delUpTo(Element,OriginalList,ResultingList). Deletes
/* first elements of OriginalList until it finds Element,
/* then put result in ResultingList.
*/
    delUpTo(X,[X|Rest],Rest).
    delUpTo(X,[_|ButOne],Rest) :- delUpTo(X,ButOne,Rest).

/* included(Set,SuperSet). True if all elements of Set
/* in SuperSet,in same order. Accepts [], [X] & full set.
*/

    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        delUpTo(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

There is still a small problem. "included" generates some
undesired solutions (i.e. empty list, single element lists
and full set). You can filter them:

/* subset(Set,SuperSet). Like "included", but rejects [],
[X] & full set.
*/

    subset(Set,SuperSet) :-
        included(Set,SuperSet),
        filtered(Set,SuperSet).

    filtered(  []   ,   _   ) :- !,fail.
    filtered(  [_]  ,   _   ) :- !,fail.
    filtered(FullSet,FullSet) :- !,fail.
    filtered(   _   ,   _   ).

    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        delUpTo(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

    delUpTo(X,[X|Rest],Rest).
    delUpTo(X,[_|ButOne],Rest) :- delUpTo(X,ButOne,Rest).

As you mentioned, you can use the "findall" predicate to
generate a list of all solutions:

    findall(X,subset(X,[a,b,c,d]),ListOfSolutions)

Hope this helps.

-- B. Ibrahim

------------------------------

Date: 2 Jun 86 20:33:31 GMT
From: Professor John Hughes <allegra!princeton!caip
Subject: Income Tax Planning

> From: dave@lsuc.UUCP
> Subject: miscellany re income tax planning system
> ...
> Third, I'm currently wrestling with the task of generating,
> for a list, every list which is a subset of that list. Thus,
> for [a,b,c,d], I want findall to be able to find each of
> [a,b] [a,c] [a,d] [a,b,c] [a,b,d] [a,c,d] [b,c] [b,d] [b,c,d]
> [c,d].

This should do the trick:

included(Subset,Set) is true if Subset is a subset of Set

included([],Set).
included([X|Subset],Set):-append(_,[X|Rest],Set),
        included(Subset,Rest).

It only includes subsets whose elements are in the
same order as in the original list.

------------------------------

Date: 21 May 86 17:08:09 GMT
From: decwrl!logic.dec.com!vantreeck@ucbvax.berkeley
Subject: Depth First Iterative Deepening 

I've read that parallel processor implementations of PROLOG
machines use some variant of breadth first search. I was
wondering if anybody has designed a parallel implementation
using DFID (Depth First Iterative Deepening). Because it has
been proven that DFID is the asymptotically optimal brute-force
tree search algorithm (asymptotically optimal in cost of
solution, space, and time), I was thinking that perhaps it may
have usefulness in parallelism.

Would it be worth while for me to try and develop an DFID-PROLOG
for a single processor, e.g., on my Apple Macintosh? Or are their
some problems that would would make such a PROLOG to large for
the Mac? Is the algorithm applicable to a parallel PROLOG?

-- George Van Treeck
   DEC

PS: If you're not familiar with the algorithm, it's
    description and proof of optimality can be found
    in: ARTIFICAL INTELLIGENCE 27(1985) 97-109

------------------------------

Date: 30 May 86 19:19:19 GMT
From: Max Hailperin <allegra!princeton!caip!lll-crg
Subject: Depth First Iterative Deepening 

Well, I've devoted the last three days to working on
the idea of a depth-first iterative-deepening Prolog,
and it's potential for parallel implementation.  The
results are far from optimistic, particularly as far
as parallelism goes.

There are some applications which could be much more
cleanly programmed in DFID-prolog then normal Prolog.
(Read "programmed" as programmed with realistic
efficiency.) In particular, many puzzle-solving
programs fall into this category.  As far as I can tell,
not much else does.

However, I also found that the DFID search can be quite
cleanly programmed in Prolog in a way that keeps the
distinction between logic and control fairly clear.

Thus, I would guess that DFID doesn't warrant a modified
Prolog interpreter, but rather merely inclusion in Prolog
programmers' "bag of tricks."

I also discovered that (contrary to my original claims)
parallel deepening is *not* a good use for parallelism.
The reason is simple: almost all the time in DFID search
is in the last iteration (that's why DFID is asymptotically
optimal).  This means regardless of the depth of the search
or the number of processors available, DFPD's speedup over
DFID can be at most (1-1/b)^-2 (where b is the branching
factor).  Don't be fooled into thinking that for small b
this is a significant speedup: this is merely saying that
for small b DFID performs especially poorly.

This means that even considering parallel processors, DFID
is best considered an option for Prolog programmers and not
for Prolog implementors.

------------------------------

Date: 2 Jun 86 18:09:00 GMT
From: pur-ee!uiucdcs!reddy@ucbvax.berkeley.edu
Subject: Depth First Iterative Deepening in Prolog

DFID can be viewed as an efficient implementation of
Breadth-First search.  It has relevance to single
solution applications as well as multiple solution
applications.  For multiple solution applications,
one naturally continues searching deeper levels even
after one solution has been found.  The solutions
obtained by each search should be seen as increasingly
better approximations to the set of all solutions:

                S0, S1, S2, ..... Sinfinity

Whichever way it is used, it is naturally better than
pure depth-first search, because it is complete whereas
depth-first is not.

Mark Stickel has implemented a theorem prover using a
variant of DFID.

See:

Stickel, A Prolog technology theorem prover, 1984 Intl symp
on logic programming, Atlantic City.

Stickel and Tyson, An analysis of consecutively bounded
depth-first search with applications in automated deduction
(I think) IJCAI 85.

-- Uday Reddy
reddy@uiuc.arpa, uiucdcs!reddy

------------------------------

Date: Mon, 2 Jun 86 20:03:12 CDT
From: Uday S. Reddy <reddy@a.CS.UIUC.EDU>
Subject: Examples of logical variables

I am looking for some simple (at most one page long),
but interesting examples of the use of logical variables.
Some of the well-known examples
are

(i)   difference lists, for appending, double ended lists,
      queues etc        [Clark & Gregory, Clocksin]
(ii)  symbol tables for name translation [Warren, Reddy]
(iii) serialized coding [Warren]
(iv)  partially determined messages [Shapiro]
(v)   type inference and other inference rule based programs
      [Despeyroux, Smolka, Reddy]
(vi)  owner-coupled sets (orthogonal lists?) [Lindstrom]

Are there others I am missing?

-- Uday Reddy

------------------------------

Date: 1 Jun 86 02:50:32 GMT
From: David Sherman <hplabs!pesnta!lsuc!dave@ucbvax.berkeley>
Subject: "assert" considered harmful?

Saumya Debray mentioned recently on the net  that good Prolog
programmers don't make much use of assert and retract.

Although my exposure to Prolog has been limited, I've always
felt that somehow this must be true - assert and retract start
mucking with the very predicates that Prolog's trying to use.
I can sort of imagine the Dijkstras of the Prolog world
intoning "Assert Considered Harmful" and explaining why, like
GOTO in conventional programming languages, assert and retract
really shouldn't be used much.

But now I wonder. I'm developing this Canadian income tax
planning system. I find that on even a simple set of facts it
has to do several thousand predicate calls (matches, logical
inferences, whatever you call them), and I'm nowhere near done
implementing all the rules I want to put in. 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. For example:

        related(Taxpayer1, Taxpayer2) :-
                tptype(Taxpayer2, corporation),
                controls(Taxpayer1, Taxpayer2).

Now, "controls" can be viewed as a fact when considering whether
T1 and T2 are related, but actually it's a predicate that takes a
whole lot of analysis (in its simplest incarnation, it looks for
all the outstanding common shares in T2, looks for the owners of
those shares to match T1, totals up the two numbers and checks to
see if T1's shares exceed 50% of the total).

Once I've determined that T1 controls T2, should I "asserta" that
as a fact, so it no longer needs to take much time? And having
done so, do I then "asserta" the fact that they are related? Many
of the rules which I'm implementing have an initial test of related
-ness or control, and obviously the analysis will be much more
efficient if the program can decide almost instantly whether to
take a particular analysis path or not.

There's a further complication, too. Most of the rules
need to know whether a given pair of taxpayers are related
*at a particular point in time*. So if I start using assert,
I can imagine that I'll have to run a set of asserts for
each relevant time period during the several transactions
which the system would be analysing (since control will
change due to the transactions in corporate reorganizations,
for example).

Comments?

-- Dave Sherman

------------------------------

Date: 1 Jun 86 18:19:30 GMT
From: Jean-Francois Lamy <ulysses!burl!clyde!watmath>
Subject: "assert" considered harmful?

In article <1229@lsuc.UUCP> dave@lsuc.UUCP (David Sherman) writes:
>[...] 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. For example:

>       related(Taxpayer1, Taxpayer2) :-
>               tptype(Taxpayer2, corporation),
>               controls(Taxpayer1, Taxpayer2).

>Now, "controls" can be viewed as a fact when considering whether
>a T1 and T2 are related, but actually it's a predicate that takes
>whole lot of analysis (in its simplest incarnation, it looks for
>all.

Using assert and retract as a caching mechanism for inferences
has far reaching implications.  What you really want to say is:
in this fiscal year, A controls B, but your are telling this
using a predicate (assert) that really means "It is a theorem
that A controls B".

Under the logical interpretation, what you have asserted in one
execution should be present in the next execution of your
program.  This would break under your use of 'assert', because
what is true in one fiscal year may not be true in the next.

You may know that all information is related to only one fiscal
year and, under that assumption, you may convince yourself that
no undesirable inference will occur because of your extra
assertions.  But I consider this to be 'programming' if the
assumptions made (about time, say) are not or cannot be put as
axioms in the knowledge base. Furthermore, your reasoning probably
requires knowledge of the underlying implementation of 'assert'

Happy new June!

--  Jean-Francois Lamy

------------------------------

Date: 31 May 86 05:52:16 GMT
From: Lars-Henrik Eriksson <allegra!princeton!caip>
Subject: Eliminating duplicate solutions

In article <126@sbcs.UUCP> debray@sbcs.UUCP writes:
>.... I'm thinking of the rather
>mundane fact that any "real" system, to be useful,
>must interact with the outside world, and hence
>necessarily have side effects like "read" and "write".

I/o must do side effects, of course, but it is quite
possible to hide this from a logic program, so that it
appears to be in a completely "logical" environment.

Example: Input could be done in a logical fashion by
having a special kind of list with elements
corresponding to successive objects read from the
outside world. That is, the list would initially be an
uninstantiated variable.  Attempts to use the variable
would cause an object to be read in and the variable
would be bound to a pair of the first element and another
uninstantiated variable. Attempts to use the rest of the
list would cause the process to be repeated.

That is, to the program, the list would look like it had
everything read in on it from the start, but actually
things would be read in only as they were needed.

Of course, special precautions would have to be taken to
make sure this worked when the program backtracked, but
it is quite possible. (In fact, I have implemented input
working in this way).

Output could be done in a similar way, with objects being
output as a list was bound.

In both cases the program would think it was processing
or creating a list, while it was actually reading or
writing.

------------------------------

Date: 29 May 86 05:58:38 GMT
From: Lars-Henrik Eriksson <allegra!princeton!caip>
Subject: Standard behavior?

There are indeed two resolution proofs of a([]), but
as the two proofs produce indentical bindings (in this
case, none), it is not obvious that you'd want two
matches rather than one.

The problem gets worse if you give the query a(X). Again
you have two resolution proofs, but with different
bindings. As one of the proofs subsumes the other, you
could argue for a single match in this case as well
(with the most general binding). I would prefer the single
match in both cases.

------------------------------

Date: 30 May 86 02:28:59 GMT
From: Lars-Henrik Eriksson <allegra!princeton!caip>
Subject: Standard behavior?

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.

------------------------------

Date: 2 Jun 86 15:55:41 GMT
From: Randy Goebel <ulysses!burl!clyde!watmath!
Subject: Standard behavior?

The standard implementation of Prolog provides a
standard meaning for the primitives described as
non-logical.  These primitives have an interpretation
in a semantic domain that includes Prolog proofs (and
partial proofs) as  objects.  Such a formalization, if
produced, would provide a standard  specification for
``non-logical'' primitives of ordinary Prolog
implementations.

I don't believe that anyone really believes that any
Prolog primitive is inherently unformalizable?

------------------------------

Date: 3 Jun 86 02:05:00 GMT
From: pur-ee!uiucdcs!reddy@ucbvax.berkeley.edu
Subject: Standard behavior?

To rggoebel@watdragon:

You can try explaining cut, var and nonvar logically.
If you do it successfully, you could become a star of
the logic programming community.

------------------------------

Date: Sat 24 May 86 08:39:32-CDT
From: Dave Plummer <ATP.PLUMMER@R20.UTEXAS.EDU>
Subject: \+ \+ hack

The \+ \+ p(X) hack does more than save space as suggested
by Emneufeld@ucbvax.berkeley.edu in the V4 #14 of this
Digest.  The difference between \+ \+ p(X) and p(X) is that
if p(X) succeeds by binding X, \+ \+ p(X) also succeeds but
does not make the binding.

Cheers,

-- Dave

------------------------------

Date: 13 May 86 10:28:42 GMT
From: Roger Cordes <ulysses!unc!mcnc!ncsu!fcstools
Subject: Prolog programmers

While I regret increasing the noise-to-signal ratio of
this group, I must offer the following as refutation,
extracted from "Programming with P-Shell", by Newton S.
Lee, as published in the Summer, 1986 issue of "IEEE
Expert", p. 51:

"In Prolog, it is denoted as

  a :- b1, b2, ..., bn (n>=0)

where the head of the clause (to the left of :-) is the
unnegated atom and the body (to the right of :-) consists
of all the negated atoms."

Humorless, indeed!

-- Roger L. Cordes, Jr.
   William G. Daniel & Associates

------------------------------

End of PROLOG Digest
********************