Hacker News Reader

Comment by chc4 | Hacker News Reader

The other recent research that's been interesting to watch has been in logic programming (Prolog and Datalog), where there's been a lot of papers extending Datalog with semilattice types that are more efficient for computing dataflow-type queries (and even getting lattice types added to Souffle recently), including papers like datafun[0] extending it to sound incremental queries for more efficient execution - and there's even a paper by the Egg authors using it for efficient eclass-based Datalog queries using lattices[1]. It also seems like there has been more work recently in actually integrating logic programming in existing languages and programs, like ascent[2], instead of it being off in it's own world like it seems has historically been the case.

0: http://www.rntz.net/files/seminaive-datafun.pdf

1: https://www.mwillsey.com/papers/egglog

2: https://s-arash.github.io/ascent/cc22main-p95-seamless-deduc...

View on HN

How does Datalog with e-graphs compare to Datalog with BDDs in terms of what analyses can be performed? bddbddb is a Datalog engine using BDDs, that, according to their 2005 paper[0], can solve problems like context-sensitive pointer analysis for large programs and analyses implemented with it are faster than hand-tuned implementations in dramatically fewer lines of code. I'm not knowledgeable on what modern Datalog engines are based on.

0: https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf

I'm under the impression that BDDs are good for more efficient representation of row membership for values, so that you can query and saturate more facts faster, but eclasses allow for writing rules that "automatically" have transitive connectivity of two rules. If you have X -> Y and Y -> Z, you only need to store one of X or Y :- Z since X and Y have been unioned together and may be treated identically, along with a same(X, Z) rule firing instead of having to have additional transitive same(X, same(Y, Z)) rules. I don't profess to be an expert in BDDs, eqsat, or Datalog, though! I have one friend that did a thesis on eqsat who wasn't that big of a fan of bddbddb but I don't remember exactly why.

Yeah, it's really unfortunate that these amazing advances in datalog don't make it into general purpose languages.

You might be interested in Flix which has first-class Datalog program values:

https://flix.dev/

https://doc.flix.dev/fixpoints.html

(I am one of the developers of Flix)

I was about to post this. If only the vscode plugin worked I would use Flix.

What's the issue? Bug reports are most welcome.

The latest version seems to have solved the issue. At least the compiler plugin runs with an empty file now.

The feature list is impressive

The documentation could use some proof reading. Grammar etc.

> Flix is strongly typed. Any attempt to use predicate symbol with terms of the wrong type (or with the wrong arity) is caught by the type checker.

*Statically typed

Mainstream languages will lag behind others forever. The average programmer in Java or C# neither cares for nor understands 'new' features or concepts. Most people I know in this area have never even heard about prolog, lisp, smalltalk, etc.

Reply on news.ycombinator.com