If you've ever wished your datalog rules could handle implication and universal quantification the way Lambda Prolog does, you weren't alone. The problem has stumped researchers for years. A new runtime approach using sorted arrays as first-class sets in standard Souffle datalog might finally crack it open.
The trick isn't magic—it's compromise. Instead of trying to convert Lambda Prolog's Harrop clauses to Horn clauses at compile time (which proved too difficult to automate), this implementation adds the missing capabilities directly at runtime. For anyone building category theory encodings, theorem provers, or tools like egglog, this could be a quiet turning point.
Key facts
- Lambda Prolog offers implication and universal quantification in rule bodies, which regular datalog lacks
- A new approach encodes these features at runtime in standard Souffle datalog using sorted arrays
- The key was building a naive first-class set implementation using sorted arrays
- Previous attempts in egglog0 hit a wall trying to automate Harrop-to-Horn clause conversion
- The technique relies on Souffle's C++ functor system to handle set operations efficiently
Why Lambda Prolog Features Matter in Datalog
Regular datalog runs on Horn clauses. Lambda Prolog swaps these for Harrop clauses, which brings two powerful tools: implication and universal quantification in the body of rules.
Implication lets you treat rules as temporary facts—locally extending your database mid-proof. Universal quantification lets you introduce fresh symbols as needed within a rule. Lambda Prolog gives these operations a clean logical motivation; regular Prolog can fake them with assert and gensym, but without the same theoretical grounding.
The problem is that most datalog engines don't support Harrop clauses natively. The standard workaround has been to manually convert Lambda Prolog ideas into Horn clause form at compile time. That's what the author did initially for a category theory encoding in egglog0. It worked, but automating the conversion proved elusive.
Runtime offered another path. "Going meta," as one observer put it, is the one move.
The Sorted Array Breakthrough
The new implementation uses sorted arrays (vectors) as a first-class set representation inside Souffle. Sets get encoded as two-field records: a size value and an index pointing to the underlying data array. The sorting ensures every set has a canonical form, which makes operations like union, intersection, and subset checks reliable.
For small universes, bitsets work well—you've got integer types and bitwise operations available. But bitsets fall apart once your value range grows. The sorted array approach handles larger domains without exploding in complexity.
The author implemented a suite of set operations through stateful C++ functors: element checks, sorted insertions, unions, intersections, differences, and subset tests. These functors bridge Souffle's relational logic with imperative array manipulation underneath. It's a hybrid approach—declarative on top, procedural where needed.
Inspecting vectors requires explicitly indexing into them, since Souffle doesn't print nested records in a useful way by default. This makes the code denser than typical high-level language code, but the plumbing works.
What This Means for the Ecosystem
This isn't a new datalog engine or a revolutionary language design. It's a proof-of-concept that runtime encodings of Lambda Prolog concepts can work inside existing systems like Souffle.
If you're working on egglog, e-graphs, or symbolic computation tools, this approach gives you another option when compile-time transformations don't pan out. The author spent months refining the ideas, and the code is available for inspection.
It's not production-ready for every use case. Stateful C++ functors add complexity, and the current implementation trades some elegance for practicality. But the core insight—that first-class sets unlock Lambda Prolog capabilities in vanilla datalog—opens territory worth exploring.
Who Should Care
| Use Case | Relevance |
|---|---|
| Theorem prover development | High — Harrop clauses enable cleaner logical specifications |
| Egglog / e-graph users | High — runtime approach sidesteps compile-time conversion barriers |
| Static analysis tools | Medium — first-class sets simplify tracking variable bindings or call graphs |
| General datalog users | Low — the technique adds complexity without solving common problems |
Bottom Line
The dream of Lambda Datalog just got more practical. A runtime approach using sorted arrays sidesteps the hard compile-time problem and delivers working code in standard Souffle today. Researchers and tool-builders watching this space should keep an eye on how the technique matures. If you need Harrop clause power now and can work within Souffle's model, this is worth a closer look.
Key takeaways
- Runtime set representations in datalog can unlock Lambda Prolog-style features without compile-time magic
- Sorted arrays handle larger domains better than bitsets while keeping sets canonical
- Souffle's C++ functor system bridges declarative rules with imperative array operations
- The technique is ready for experimentation but still requires manual plumbing
Frequently asked questions
What's the difference between Horn clauses and Harrop clauses?
Horn clauses only allow simple positive goals; Harrop clauses add implication and universal quantification, letting you treat rules as temporary facts or introduce fresh symbols locally within a proof.
Why did previous attempts in egglog0 fail?
The author tried to automatically convert Harrop clauses to Horn clauses at compile time, which proved difficult to mechanize after considerable effort.
What are first-class sets in this context?
Sets that are represented as data values (using sorted arrays or bitsets) rather than relations, so they can be passed around, stored, and manipulated directly by datalog rules.
Is this approach faster than traditional datalog?
Not necessarily for simple cases. The overhead of maintaining sorted arrays and calling stateful C++ functors adds complexity, but it enables capabilities that regular datalog can't express directly.
Where can I see the actual code?
The implementation details and example code demonstrate the vector representation, set operation functors, and usage patterns within Souffle.