percival VS mangle

Souffle and Cozo mentioned below already implement the whole of "traditional" datalog.

Percival (https://github.com/ekzhang/percival) has some very nice examples showing how you can interactively write and test rules on top of a datalog interpreter.

Bud (http://bloom-lang.net/bud/) is Hellerstein's proof of concept playground. It has bit-rotted in the past few years, but the examples are readable even if you can't easily get it working.

The complexity can be quite good. You can syntactically determine when you've written linear recursion (equivalent to a for loop) vs not. Otherwise, the complexity is what you'd expect from incremental view maintenance in a normal SQL database. Which is to say O(n^k) with k being the number of relations joined, but usually much, much less with appropriate indexes and skew in the data. All the usual tricks concerning data normalization and indexes from databases apply.

I've worked on percival a bit, it compiles (transpiles?) the datalog ast into javascript code on demand and executes it to get the results, see [1]. Percival's creator, Eric, also submitted a 10m presentation about the project [2] to the HYTRADBOI 'virtual conference' earlier this year [2]. They also submitted a Show HN that received a couple comments [3]. The Have You Tried Rubbing A Database On It conference included several awesome presentations featuring datalog, which readers may find interesting [4].

[1]: https://github.com/ekzhang/percival/blob/main/crates/perciva...

[2]: https://www.hytradboi.com/2022/percival-a-reactive-language-...

[3]: https://news.ycombinator.com/item?id=29521975

[4]: https://www.hytradboi.com/

I haven't written a parser with Chumsky, bit I've played with a little one a bit if you wanna see an example syntax. The error reporting for this project is implemented with `ariadne` which is also really slick.

Parser: https://github.com/ekzhang/percival/blob/main/crates/perciva...

Error reporting: https://github.com/ekzhang/percival/blob/main/crates/perciva...

Datalog playground: https://percival.ink/

To see an error report, delete some punctuation from one of the Datalog code blocks then press shift-return.

Mangle https://github.com/google/mangle is an open-source implementation in golang, it was an explicit goal to make it easy to learn. Meaning: it is easy to recognize the pure datalog part, the syntax is following the good old course material.

It was discussed here: https://news.ycombinator.com/item?id=33756800

Logic programming offers a good foundation for anything that people call "rule engines." Within logic programming, there is some variation on the degree of declarativeness.

Datalog is arguably the minimal core logic programming, similar to what the lambda calculus achieves for functional programming. Unfortunately, it has been forgotten outside of database and query processing realm. A resurgence has happened in recent years, as PL researchers and also industry have discovered the virtues of datalog (e.g. Flix, DataFun). My own attempt at making this more widely known is here https://github.com/google/mangle, a language from the datalog family and its implementation as a go library.

As the example shows: plain "rules" (or: plain datalog) is rarely enough to capture everything that one wants to express: the question then is, how to combine a pure declarative "kernel" with more general purpose programming (e.g. mapping a list).

PROLOG offered one answer, already in the 1980s, but I fully reject it: the fact that the writing a program in the wrong order with negation and recursion makes it non-terminating is not something we'd want everyone to deal with. Datalog with stratified recursion is somewhat better, as "layers of rules" is a concept that is easy to understand.

In mainstream programming languages, the possibility of writing non-terminating programs also exists, but is rarely an issue. That is why I believe a good combination of declarative and general-purpose has to make it really easy to recognize which parts of a program are in the declarative, terminating, safe kernel and which parts require more attention from the programmer.