A relatively simple Datalog engine

Sure there is a reason: Many applications, alias analysis in particular, only use a subset of Datalog. Subsetting languages very often makes for easier and more efficient implementation. If you know that there is no negation in your alias problems, your special purpose solver can be much more efficient than a Datalog solver that must be prepared to deal with negation.

Of course you might wish for a generic Datalog solver that you could run in a special mode where you promise that it will not encounter negation in the problem you give it. But that is then no longer a Datalog solver but a "well engineered purpose built solver".

As for the "built in" part, anything that is not built in must cross an API boundary and usually translate between different data representations. That is a theoretical reason for being slower.

https://github.com/dwtj/deductive-points-to-analysis-paper/b...

it uses the ability to return multiple times from a continuation to allow sets of results (streams or solution trees) to be expressed directly in scheme and intermixed freely with the functional subset.

a 'nice' mixture of declarative and procedural would be really slick. i should go back and look at mozart/oz again.

I'll definately see if my limited ability to deal with formalisms lets me understand the type system proposed in Datafun.

SLG resolution (also called "tabling" in Prolog) prevents both positive and negative loops, and always terminates for programs that have the bounded term-size property, as is the case for all Datalog programs. XSB Prolog is a notable example of a Prolog system that supports this mode, which you can enable with the table/1 directive:

http://xsb.sourceforge.net/shadow_site/manual1/node2.html

Therefore, you can use a Prolog system such as XSB Prolog also to learn Datalog, and then seamlessly move to Prolog. Conversely, if you know Prolog, then learning Datalog is very easy. Another very nice system for learning Datalog is DES, which you can run in SICStus Prolog and other systems:

http://des.sourceforge.net/

Various extensions such as aggregate functions and object-oriented programming (which are mentioned in the Wikipedia entry for Datalog) are also applicable to both Prolog and Datalog with identical or closely related semantics.

In retrospect I think there might be several ways to improve performance by using other data structures to index the facts, but I haven't had the time to work on it lately. There is a pull request from someone that I'm still looking at, which might just spur me on to think about it some more.

if you allow something to be true only if something else is not true, your solution space is no longer monotonic. meaning that a result you thought was part of the solution can later be retracted. if there is a cycle (trivially "a if not a"), then you may not ever arrive at an answer. that might seem simple to detect, but that cycle can exist through an arbitrary number of rules and data dependencies, so in the limit is undecidable.

ideally, as in this solver, you could keep adding terms you could show to be correct from the data and rules at hand until they and all their consequences have been found, and which point you can stop (fixed point). but negation screws up this plan.

there are various restrictions on negation, solver heuristics, and partial conservative proofs of termination that can be applied. but this is where your beautiful simple declarative world starts getting sad and messy.

[edit: I'd like to leave this because I wish I understood the problem with negation earlier, but I just skimmed and missed stratification, Frank thoughtfully explains below]