Consider using Datalog (the incredible subset of Prolog) for this perfect use case. Compared to Prolog, you get:
1. Free de-duplication. No more debugging why a predicate is returning the same result more than once.
2. Commutativity. Order of predicates does not change the result. Finally, true logic programming!
3. Easy static analysis. There are many papers that describe how to do points-to analysis (and other similar techniques) with Datalog rules that fit on a single page :O
Souffle[0] is a mature Datalog that is highly performant and has many nice features. I highly recommend playing with it!
Souffle seems to suffer from the standard small language issue of no code examples front and center. Also, no "how is this better than X" or "example of usage in Y".
To those who have used Prolog, is the description sufficient to know what it does and if it will be useful? I've never use prolog and I don't know the lingo.
I was in the same group when I wanted to try Mercury (another Prolog-like language, but with ML-like types).
Someone on Mercury's mailing list took pity on me, and told me to just straight up try some Prolog.
Prolog, at least the basics, isn't hard at all, and it takes maybe a day to get you to write something that works. Of course, every language has its inconsistencies, dark corners and unexpected turns, and, sometimes some very deep and general pieces of wisdom that aren't on the surface. But, really, if you want to understand any Prolog derivative, the best way I can think about, is to learn some Prolog. It's the most efficient way to the goal. It doesn't really take long.
I recommend starting with the simple example[0], then taking a look at the tutorial[1].
But I do agree that being familiar with Prolog is a big help in understanding what Souffle is. For a quick intro to Prolog, I recommend this video[2], which speaks from a "industry practical" point of view, and introduces concepts that almost all apply to Datalog :)
So in the great scheme of programming languages, you had imperative languages like Fortran, eventually there was a paper “GOTO considered harmful” which ushered in a scaling-back of complexity to “structured programming” where you had named cells in which you could store values, and looping constructs like `while` and `for` to walk through them and manipulate them. Then we added on lexical closures over environments, which also take the form of “methods on objects” and “dynamic dispatch,” a bunch of different names for different forms of single-threaded OOP. Languages like GIL-ed Python and Ruby and Node.js continue this tradition today, while other languages add threading to have shared-state concurrent programming, with its vocabulary of locks and race conditions and cache invalidation and transactions and commits and consensus algorithms and now CRDTs...
But, other visions of programming have coexisted with this main educational vortex, including logic programming like Prolog. Actually, if you have heard of any of these alternates, you have probably heard of functional programming, which can be ahistorically understood as saying “hey these locks and races and all that, it's actually very complicated, maybe we could have a simpler model of programming for 90% of our work and only break out the Java when we really need it.” And you’re like “what will you replace it with?” and they respond “Template substitutions! It's all the power of lexicographic scopes, all the power of looping (via recursion), but when you want to express the really complex stuff you need templates that have side effects when substituted, we can give those scary names.” So you give me a sunbeam and a raincloud and I give you back a rainbow.
If that's the functional programming idea then logic programming takes the same idea but adds unification and search. The idea is “ok but why do I have to fill in all the parameters to a template before I use it? I should just say “if light shines on a droplet-cloud it makes a rainbow, a sunbeam is a light, a raincloud is a droplet-cloud, hey language, what are all the things that make a rainbow?”
Functional programming was based on the function, the template, the “I take these args and produce a structure looking like such-and-so.” Logic programming is based on the Horn clause, “X verbs Y, for some entities X and Y that I maybe know about and some verb that I am being introduced to.”
Basic things that logic programming does very well, OOP kind of struggles with. You can kind of understand this if you have written a SQL query. The verbs can be thought of as tables that foreign-key to X and to Y, if you want to write OOP to solve a logic puzzle you have to choose explicit ways to search or brute force... SQL DBs come with B-trees and indexes to solve a lot of these problems. Whereas with Prolog you just write the pattern to match and the new pattern to emit.
It's a rather different take on what the building blocks should be.
Prolog is Turing-complete, and Datalog isn't. In light of this, I think it's a bit of a stretch to call it a (logic) programming language. But people seem to do that.
Turing completeness is a bug, not a feature. After writing code in Agda for some years I was convinced that Turing completeness does more harm than good. Non-TC languages have a killer feature: their halting problem is solvable which means you can get arbitrarily strong guarantees from the compiler. The fact that you can't encode "while(true) { }" without putting "unsafe" doesn't make the language impractical, you can still implement algorithms without Turing completeness.
Moreover, using various forms of coinduction you can encode infinite computation even in non-TC languages.
Agda's been around for 24 years, according to Wikipedia, and it hasn't exactly revolutionized software development: I'm not aware of any notable software written in it, or of anyone so much as winning a programming competition while using it (and some of those are designed to promote functional programming) So, frankly, I'm skeptical that Agda's trade-offs in the performance-convenience-correctness space are good.
Ok, ok I understand theoretically what this means in terms of programming languages. But what does it mean practically? What features are removed? How does this work out when you're implementing a program?
Turing completeness is not a requirement of a programming language! Just because you can't do infinite computation doesn't mean you can't do infinitely useful computation :)
That said, Souffle is touring complete due to its adding of constructors to the language.
> 2. Commutativity. Order of predicates does not change the result. Finally, true logic programming!
I'm not sure this is a good selling point. The fact that predicate order matters in Prolog allows performance optimization and more transparent debugging.
It's a great one! From a logical perspective, it's ideal for the order of constraints to not affect the outcome. This missing behavior becomes a quirk quite early on when working with Prolog.
That said, order of constraints can affect performance. But since reordering doesn't affect outcome, you are free resort them as you wish in effort to optimize for better performance :)
1. Free de-duplication. No more debugging why a predicate is returning the same result more than once.
2. Commutativity. Order of predicates does not change the result. Finally, true logic programming!
3. Easy static analysis. There are many papers that describe how to do points-to analysis (and other similar techniques) with Datalog rules that fit on a single page :O
Souffle[0] is a mature Datalog that is highly performant and has many nice features. I highly recommend playing with it!
[0] https://souffle-lang.github.io