This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
> Per Bothner did his PhD thesis > on integrating logic programming with semi-functional programming. My dissertation is unfortunately not available online. However, some of my ideas were inspired by work by Smolka, who is now involved with the Oz language/system, which seems quite nice. Even more relevant, I worked for over a year implementing some (other people's) ideas on efficient implementation of logic programming as a query language. The Principal Investigar was and is Raghu Ramakrishnan at U. Wisconsin (Madison); the system has been released as free software. See http://www.cs.wisc.edu/coral/. However, I can't say I fully grokked all the theory, and it's now been seven years ... However, the basic idea is relatively simple: Normally, Prolog-style languages are implemented top-down (starting from the query) using back-tracking; this can get into infinite loops, even when the query does have a solution. (It's similar to the problem of left-recursion in a recursive-rescent parser.) An alternative implementation works bottom-up, starting from the facts, and basically does joins to generate new facts. This is complete but can do a lot of wasted work. The clever part is that the program is analized and queries re-written (using "magic sets/rules"), so that we only generate the joins (and intermediate tuples) that are relevant to the actual query. --Per Bothner Cygnus Solutions bothner@cygnus.com http://www.cygnus.com/~bothner