Re: high- or low-level interface

[Per Bothner <bothner@cygnus.com>]

> 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