This does look interesting. How does it compare to prolog? From what I saw, this is in some ways similar to working with clpfd (“Constraint Logic Programming over Finite Domains”).

There’s an erlang implementation of prolog, https://github.com/rvirding/erlog, but it does not come with a clpfd library. I think this would also be an interesting area to explore.

AFAIK Backtrex could be used as the basis for a Prolog engine or other unification systems. I’ve made toy projects in Prolog to solve constraint satisfaction problems like Sudoku, but I can’t claim to understand all its semantics. For example, it has impure features to prematurely stop searching part of the tree (known as a “cut”), but I don’t have any experience using it. Backtrex’s API would allow somebody to prematurely prune the search; they could simply stop returning as many unknowns and values. It’s not a recommended use case, but could be worth exploring, and I don’t know if this maps well to the “cut” semantics.

A while back I studied *kanren languages and implemented microKanren in Idris (may not compile anymore since Idris has changed a bit). Kanrens are small logic programming languages, most focusing on purity and determinism. The original authors prefer the term relational programming to emphasize that unification isn’t biased in a particular direction. For instance, “the head of a list” is a relation that could produce the single element at the front of a list or an infinite stream of lists where a given element is at the front (or even simply the set of all non-empty lists along with the first element of each). They’re fascinating languages. Anyone interested in learning more should work through The Reasoned Schemer and read the first few chapters of William E. Byrd’s PhD dissertation where the Core miniKanren language introduced and implemented in Scheme.

I’m not familiar with it. I’ll definitely check it out. Could inspire some fun demo applications and test the limits of the current API.

I recently heard about this, but haven’t had a chance to try it out yet. Looking at the README it’s not clear whether there’s been any focus on parallelism and distributed computing.

Part of why I’m excited about Backtrex is the massive scaling potential provided almost out of the box by the BEAM, and the opportunity to learn how to do that well.

Yup, no sweat compared to all the potential bottlenecks in the backtracking algorithm and callback implementations. I’m working on generating flexible profiler reports now so I can identify bottlenecks and compare multiple implementations.

I’m not really sure what backtrex does yet (I’ve not looked at the docs yet, I’m on my phone ^.^), but what kind of scaling do you need? Is it serialized? Trivially distributable? Do you need one central information store? Is there no shared information?

It implements a generic backtracking algorithm to solve problems amenable to brute force. After implementing a few simple callbacks specific to your problem domain, you get a Backtrex.solve/1 function in return that will find a solution (eventually a stream of all solutions).

Backtracking is a step up from naive brute force. For example, the most naive way to solve a Sudoku puzzle is taking the N blank cells and enumerating all possible 9^N ways to fill them with number 1-9. A significant ratio of those solutions aren’t worth exploring, though, because as soon as a fraction of those cells are in an invalid state you know no possible values for the remaining blank cells could possibly yield a solution. Backtracking actively prunes the search space by checking whether a provisional set of assignments are valid.

Concurrency is a natural fit for a problem like this. Rather than having one process do a depth first search of the space on its own, you could, for instance, assign half the possible values for the first blank cell to one process and the other half to a second process.

As in needing everything to happen in a sequential order? No, not for this API, but I intend to offer a non-concurrent API for cases where users want solutions to arrive in a deterministic order.

Yes, every problem can be broken in many subproblems, each of which can be delegated to another process/node. And in turn, those subproblems may be broken in sub-subproblems, which lends well to a tree of workers and supervisors.

It would be nice to support work stealing when there are unoccupied nodes and worker processes, but that requires more coordination traffic in this work tree.

Solutions discovered by individual workers must be reported back up the tree to the root so they can be appended to a stream which is fed on demand to the Backtrex client.

Not in the sense of a database, no. That would be the Backtrex user’s job. If you mean processes responsible for coordinating other processes, yes, especially if the problem is repeatedly divided into the large tree structure described above. And again, more will be required of these coordinating processes if work stealing is supported (which I’d like).

At this stage, nope, not any more than what’s introduced by the coordination problem. However, a potential optimization may benefit from a way to broadcast information from one worker to all workers, probably by reporting up the tree to the root and then back down.