Lambda the Ultimate

inactiveTopic Efficient tree searches in Logic Languages
started 12/25/2000; 6:59:22 PM - last post 12/29/2000; 4:22:49 AM
Chris Rathman - Efficient tree searches in Logic Languages  blueArrow
12/25/2000; 6:59:22 PM (reads: 1468, responses: 2)
Efficient tree searches in Logic Languages
I've been on the Mercury mailing list for a while, slowing trying to get acquanted with the language. The above post caught my eye since the author makes the claim that searches through XML documents can be done as efficiently in the logic languages as with pointer languages like C - O(1) for neighbors.

I certainly think that Prolog (and by extension Mercury) provide some distinct capabilities when it comes to dealing with tree data structures. With XML documents being little more than tree structures - at least when viewed in the DOM manner, the logic languages seem to provide some potential for XML processing (though the author points out some problems with DOM and Logic Languages.

My Prolog is rather rusty and I'm still not comfortable enuf with Mercury to comment on the question of efficiency. Be interesting to see if the claim holds up once the author publishes.
Posted to Logic/Declerative by Chris Rathman on 12/25/00; 7:00:30 PM

Chris Rathman - Re: Efficient tree searches in Logic Languages  blueArrow
12/25/2000; 7:13:50 PM (reads: 739, responses: 0)
I guess as long as I'm on the subject of Mercury, I should comment on why it's a language worth studying. :-)

First, it provides mechanisms for making logic programming more efficient. More specifically, Mercury provides a method for declaring the relatively determinism of the predicates (det, semi-det, and non-det). This allows the compiler to optimize the generated code in the scenario of determinism. Note, Prolog compiles all statements with the default of non-determinism, thus having the added overhead of pursuing various multiple solutions (or no solutions).

Second, Mercury makes for a happy marriage between logic and functional programming. Although most functional languages (like Scheme) can mimic the logic languages, it's not necessarily natural nor intuitive. Though Mercury is really a pure logic language, the authors of the language have found a way to use functional techniques in way that compiles to pure logic techniques. If you are interested in the relationship between the two paradigms, Mercury is perhaps the best answer to the interrelationship between declarative and functional programming.

Ehud Lamm - Re: Efficient tree searches in Logic Languages  blueArrow
12/29/2000; 4:22:49 AM (reads: 712, responses: 0)
While on efficiency and logic programming, it may be worthwhile to mention that there are many 'tricks' that are useful to speed up Prolog programs. Things like first argument indexing etc.

O'keefe's The Craft of Prolog covers many interesting techniques.