jdevries@zodiac.ads.com (Jeff De Vries) (02/06/88)
I needed to do a breadth-first search in Prolog, so being the naturally lazy person that I am, I started to look through some Prolog books to see if they had an example program I could just copy. I noticed that one author used lists to maintain which nodes still needed to be expanded, while another author used assert/1 (and retract/1) to maintain those nodes. Since I am not into Prolog internals, I was wondering about the ramifications of the two approaches. Is one approach going to be, in general, faster than the other, (my gut feeling is that the list approach would be faster, but...)? Are there occasions where dynamic assertions are the way to go? Are there things that you can do with assertions that you can't do with lists? Thanks! Jeff De Vries (jdevries@ads.com or jdevries@ads.arpa) Advanced Decision Systems Disclaimer: I am speaking for myself, and not ADS.
ok@quintus.UUCP (Richard A. O'Keefe) (02/06/88)
In article <2207@zodiac.UUCP>, jdevries@zodiac.ads.com (Jeff De Vries) writes: > I needed to do a breadth-first search in Prolog, so being the naturally lazy > person that I am, I started to look through some Prolog books to see if they > had an example program I could just copy. I noticed that one author used > lists to maintain which nodes still needed to be expanded, while another > author used assert/1 (and retract/1) to maintain those nodes. Since I am > not into Prolog internals, I was wondering about the ramifications of the two > approaches. Is one approach going to be, in general, faster than the other, > (my gut feeling is that the list approach would be faster, but...)? Are there > occasions where dynamic assertions are the way to go? Are there things that > you can do with assertions that you can't do with lists? > It all depends on what you want to do. If you *can* do what you want without changing the data-base, you would be well advised to do so. Speed ratios of 1000:1 (data-base hacking slower than list processing) are not uncommon, if you are using a decent compiler. It would be interesting to hear which book suggested using lists (I hope you mean queues or difference lists) and which book suggested using the data base. Give the second book to a friend. Better yet, give it to an enemy (:-). The one thing that you can do by hacking the data base that you can't do with a pure approach is maintain information which will survive across backtracking, but if you really are doing a search you probably don't want that. Suppose we are given three predicates: start(Position) - the initial position solution(Position) - tests whether X is a solution children(Position, Children) - returns the children of a position Here is a version of breadth-first search, due to Fernando Pereira. It is pure and robust. I've obfuscated it a bit, because I'm writing up how to do several sorts of searches in Prolog, and I don't want to put all that explanation here. breadth_first(Answer) :- start(Start), breadth_star(s(0), [Start|Rest], Rest, Answer), solution(Answer). % breadth_start(LengthOfQueue, HeadOfQueue, TailOfQueue, Answer) breadth_star(s(N0), [X|F], B0, Y) :- ( Y = X ; children(X, Children), queue_last_list(Children, N0, B0, N1, B1), breadth_star(N1, F, B1, Y) ). queue_last_list([], N, B, N, B). queue_last_list([X|Xs], N0, [X|B0], N, B) :- queue_last_list(Xs, s(N0), B0, N, B).