prolog

Are there any Prolog compilers that can optimize by targeting specific queries?


Given a Prolog theory and a small set of possible queries, it seems plausible that it would be possible to generate the required search tree/graph and then optimize/reduce it down to something that can be easily translated into a fast procedural program.

Obviously, the ability to issue general queries against the Prolog database would be lost once it is compiled in this way. The Prolog theory would also have to include some sort of I/O, otherwise the reduction would leave only static result sets.

Are there any Prolog systems or compilers that have such a facility, or are there any relevant papers on the subject ?


Solution

  • I don't know any specific one, but what you're looking for are terms such as "specializing compiler", "program specialization", "semantics-direction compilation" and "partial evaluation". Try them with and without "Prolog" in your query; the functional programming community has done much research into this area as well.

    Note that Prolog is Turing-complete, so no approach will be perfect. There are well-known subsets of Prolog such as Datalog, but those don't include I/O. I believe Datalog is described in The Art of Prolog by Sterling and Shapiro. (Datalog still includes variables though, which is good enough for simple, stream-based I/O.)

    If that doesn't work, consider asking at cstheory.