PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/06/86)
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 ********************
PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/06/86)
PROLOG Digest Friday, 6 Jun 1986 Volume 4 : Issue 16 Today's Topics: New book Request for information Reduce? Prolog test suite wanted Income Tax Planning Income Tax Planning system Income Tax Planning Depth First Iterative Deepening in parallel Depth First Iterative Deepening in parallel Depth First Iterative Deepening in Prolog Examples of logical variables "assert" considered harmful? "assert" considered harmful? eliminating duplicate solutions in Prolog Standard behavior? Standard behavior? Standard behavior? Standard behavior? \+ \+ hack 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: Prolog 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 in parallel 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 in parallel 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 Prolog 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 ********************